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

محورهای موضوعی : آمار

رضا ندیمی ¹ ( استادیار، گروه علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه مازندران، بابلسر، ایران )
امید رنجبر ² ( گروه علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه مازندران، بابلسر، ایران )

تاریخ دریافت : 1396/07/06 تاریخ پذیرش : 1398/04/22 تاریخ انتشار : 1398/08/10

کلید واژه: Network flows, Partial digest problem, Restriction site mapping,

چکیده مقاله :

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

چکیده انگلیسی:

Restriction Site Mapping is one of the interesting tasks in Computational Biology. A DNA strand can be thought of as a string on the letters A, T, C, and G. When a particular restriction enzyme is added to a DNA solution, the DNA is cut at particular restriction sites. The goal of the restriction site mapping is to determine the location of every site for a given enzyme. In partial digest method, all pairwise distances between restriction sites are produced. Mathematically, given pairwise distances between n points on a line segment, the goal is to find that points. This problem has been named Partial Digest Problem(PDP). In this paper we present a new model for PDP using generalized network flows. Since complexity class of this problem is one of the most important open problems in bioinformatics (there is no polynomial algorithm and no proof for Np-completeness) reducing to a network flow problem create a new viewpoint to challenge with this problem.

منابع و مأخذ:

[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.