مدل بندی مسأله هضم جزئی بصورت مساله شبکه جریان

الموضوعات :

رضا ندیمی ¹ , امید رنجبر ²

1 - استادیار، گروه علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه مازندران، بابلسر، ایران
2 - گروه علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه مازندران، بابلسر، ایران

تاريخ الإرسال : 08 الخميس , محرم, 1439 تاريخ التأكيد : 10 السبت , ذو القعدة, 1440 تاريخ الإصدار : 04 الجمعة , ربيع الأول, 1441

الکلمات المفتاحية: Network flows, Partial digest problem, Restriction site mapping,

ملخص المقالة :

نگاشت نقاط مرزی یکی از مسائل جالب توجه در زیست شناسی محاسباتی به شمار می‌رود. یک رشته DNA به صورت دنباله‌ای از حروف A, T, C, G می‌باشد. هنگامی که یک آنزیم محدود کننده به یک محلول DNA اضافه می‌شود، مولکول DNA از مکان‌های خاصی بریده می شود. هدف از نگاشت نقاط مرزی پیدا کردن نقاط برش برای یک آنزیم معین است. در روش هضم جزیی، برشها طوری انجام می‌شود که فاصله دو به دوی همه نقاط برش حاصل شود. در بیان ریاضی مساله، فاصله دو به دوی n نقطه واقع بر یک پاره خط داده شده است و هدف بدست آوردن خود این نقاط است. در بیوانفورماتیک این مساله به مساله هضم جزیی معروف شده است. در این مقاله یک مدل شبکه جریان تعمیم یافته برای مساله ارایه می‌دهیم. با توجه به اینکه کلاس پیچیدگی این مساله یکی از قدیمی‌ترین و مهمترین مسایل باز در بیوانفورماتیک نظری است(تاکنون نه الگوریتمی با زمان چند جمله ای و نه اثباتی بر Np-complete بودن آن ارایه شده است)، کاهش مساله هضم جزیی به مساله شبکه جریان دریچه جدیدی را برای چالش با این مساله می‌گشاید.

المصادر:

[1] R. K. Ahuja; T. L. Magnanti.; J. B. Orlin, (1993). Network flow: theory, algorithms, and           applications. Prentice Hall.

 

[2] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. (1993). Nonlinear programming theory and algorithms, Second edition, John Wiley and Sons, Inc. p:512.

[3] M. Cieliebak, S. Eidenbenz, and P. Penna. (2005). Partial Digest is hard to solve for erroneous input data. Theory. Computer. Sci., 349(3): 361-381.

[4] T. Dakic, (2000). On the Turnpike Problem. PhD thesis, Simon Fraser University.

[5] P. Lemke, M. Werman. (1988). on the complexity of inverting the autocorrelation function of a finite integer sequence, and the problem of locating n points on a line, giventhe   unlabeled distances between them. Preprint 453, Institute for Mathematics and its Application IMA.

[6] A. L. Patterson. (1935). A direct method for the determination of the components of interatomic distances in crystals, Zeitschr. Krist. 90: 517-542,

[7] S. S. Skiena, W. Smith, and P. Lemke. (1990). Reconstructing sets from interpoint distances. In Proc. of the 6th ACM Symposium on Computational Geometry (SoCG 1990), pages 332-339.

[8] Z. Zhang. (1994). An exponential example for a partial digest mapping algorithm. Journal of Computational Biology, 1(3):235-239.

[9] Salehi Fathabadi, H. Nadimi, R. (2010). A Continuous Optimization Model for Partial Digest Problem. Journal of Sciences, Islamic Republic of Iran 21.2

[10] Nadimi, Reza, Hassan Salehi Fathabadi, and Mohammad Ganjtabesh. (2011). A fast algorithm for the partial digest problem. Japan journal of industrial and applied mathematics 315-325.