Modeling of Partial Digest Problem as a Network flows problem

Subject Areas : Statistics

R. Nadimi ¹ ( Assistant Professor, Department of Computer science, Faculty of Mathematics, University of Mazandaran, Babolsar, Iran )
O. Ranjbar ² ( Department of Computer science, Faculty of Mathematics, University of Mazandaran, Babolsar, Iran )

Received: 2017-09-28 Accepted : 2019-07-13 Published : 2019-11-01

Keywords: شبکه جریان, نگاشت نقاط مرزی, مسأله هضم جزئی,

Abstract :

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.

References:

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