Combinatorial optimization in DNA mapping - A computational thread of the simplified partial digest problem

Blazewicz, Jacek; Kasprzak, Marta

RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 4, pp. 227-241.

In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach - the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O($n\log n$)-time algorithm is given, where $n$ is a number of restriction sites.

[1] S. Benzer, On the topology of the genetic fine structure, in Proceedings of the National Academy of Sciences of the USA 45 (1959) 1607-1620.

[2] J. Blazewicz, P. Formanowicz, M. Kasprzak, M. Jaroszewski and W.T. Markiewicz, Construction of DNA restriction maps based on a simplified experiment. Bioinformatics 17 (2001) 398-404.

[3] J. Blazewicz and M. Jaroszewski, New algorithm for the Simplified Partial Digest Problem. Lect. Notes Bioinformatics 2812 (2003) 95-110.

[4] J. Blazewicz and M. Kasprzak, Complexity of DNA sequencing by hybridization. Theoret. Comput. Sci. 290 (2003) 1459-1473. | Zbl

[5] M. Cieliebak and S. Eidenbenz, Measurement errors make the partial digest problem NP-hard. Lect. Notes Comput. Sci. 2976 (2004) 379-390.

[6] M. Cieliebak, S. Eidenbenz and P. Penna, Noisy data make the partial digest problem NP-hard. Lect. Notes Bioinformatics 2812 (2003) 111-123.

[7] G.B. Fogel and D.W. Corne, eds. Evolutionary Computations in Bioinformatics. Morgan Kaufman, Boston (2003).

[8] M.R. Garey and D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco (1979). | MR | Zbl

[9] L. Goldstein and M.S. Waterman, Mapping DNA by stochastic relaxation. Adv. Appl. Math. 8 (1987) 194-207. | Zbl

[10] D.S. Johnson, The NP-completeness column: an ongoing guide. J. Algorithms (1985) 6 291-305. | Zbl

[11] R.M. Karp and R. Shamir, Algorithms for optical mapping, in Proceedings of the Second International Conference on Computational Biology (RECOMB), New York, (1998) 117-124.

[12] M. Kasprzak, Computational complexity of the Simplified Partial Digest Problem, in 05441 Abstracts Collection - Managing and Mining Genome Information: Frontiers in Bioinformatics, edited by J. Blazewicz, J.Ch. Freytag and M. Vingron. IBFI, Dagstuhl (2005).

[13] L. Newberg and D. Naor, A lower bound on the number of solutions of the probed partial digest problem. Adv. Appl. Math. 14 (1993) 172-183. | Zbl

[14] G. Pandurangan and H. Ramesh, The restriction mapping problem revisited. J. Comput. Syst. Sci. 65 (2002) 526-544. | Zbl

[15] P.A. Pevzner, Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000). | MR | Zbl

[16] W. Schmitt and M.S. Waterman, Multiple solutions of DNA restriction mapping problem. Adv. Appl. Math. 12 (1991) 412-427. | Zbl

[17] D.C. Schwartz, X. Li, L.I. Hernandez, S.P. Ramnarain, E.J. Huff and Y.K. Wang, Ordered restriction maps of Saccharomyces cerevisiac chromosomes constructed by optical mapping. Science 262 (1993) 110-114.

[18] J. Setubal and J. Meidanis, Introduction to Computational Biology. PWS Publishing Company, Boston (1997).

[19] S.S. Skiena, Geometric reconstruction problems, in Handbook of Discrete and Computational Geometry edited by J.E. Goodman and J. O'Rourke. CRC Press, Boca Raton (1997), 481-490. | Zbl

[20] S.S. Skiena, W.D. Smith and P. Lemke, Reconstructing sets from interpoint distances in Proceedings of Sixth ACM Symposium on Computational Geometry (1990) 332-339.

[21] S.S. Skiena and G. Sundaram, A partial digest approach to restriction site mapping. Bull. Math. Biology 56 (1994) 275-294. | Zbl

[22] M.S. Waterman, Introduction to Computational Biology. Maps, Sequences and Genomes, Chapman and Hall: London (1995). | Zbl