Combinatorial optimization in DNA mapping - A computational thread of the simplified partial digest problem
RAIRO - Operations Research - Recherche Opérationnelle, Volume 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.

DOI: 10.1051/ro:2006007
Keywords: combinatorial optimization, DNA restriction mapping, partial digest, computational complexity
@article{RO_2005__39_4_227_0,
     author = {Blazewicz, Jacek and Kasprzak, Marta},
     title = {Combinatorial optimization in {DNA} mapping - {A} computational thread of the simplified partial digest problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {227--241},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {4},
     year = {2005},
     doi = {10.1051/ro:2006007},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2006007/}
}
TY  - JOUR
AU  - Blazewicz, Jacek
AU  - Kasprzak, Marta
TI  - Combinatorial optimization in DNA mapping - A computational thread of the simplified partial digest problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2005
SP  - 227
EP  - 241
VL  - 39
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2006007/
DO  - 10.1051/ro:2006007
LA  - en
ID  - RO_2005__39_4_227_0
ER  - 
%0 Journal Article
%A Blazewicz, Jacek
%A Kasprzak, Marta
%T Combinatorial optimization in DNA mapping - A computational thread of the simplified partial digest problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2005
%P 227-241
%V 39
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2006007/
%R 10.1051/ro:2006007
%G en
%F RO_2005__39_4_227_0
Blazewicz, Jacek; Kasprzak, Marta. Combinatorial optimization in DNA mapping - A computational thread of the simplified partial digest problem. RAIRO - Operations Research - Recherche Opérationnelle, Volume 39 (2005) no. 4, pp. 227-241. doi : 10.1051/ro:2006007. http://archive.numdam.org/articles/10.1051/ro:2006007/

[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

Cited by Sources: