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()-time algorithm is given, where is a number of restriction sites.
@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] On the topology of the genetic fine structure, in Proceedings of the National Academy of Sciences of the USA 45 (1959) 1607-1620.
,[2] Construction of DNA restriction maps based on a simplified experiment. Bioinformatics 17 (2001) 398-404.
, , , and ,[3] New algorithm for the Simplified Partial Digest Problem. Lect. Notes Bioinformatics 2812 (2003) 95-110.
and ,[4] Complexity of DNA sequencing by hybridization. Theoret. Comput. Sci. 290 (2003) 1459-1473. | Zbl
and ,[5] Measurement errors make the partial digest problem NP-hard. Lect. Notes Comput. Sci. 2976 (2004) 379-390.
and ,[6] Noisy data make the partial digest problem NP-hard. Lect. Notes Bioinformatics 2812 (2003) 111-123.
, and ,[7] Evolutionary Computations in Bioinformatics. Morgan Kaufman, Boston (2003).
and , eds.[8] Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco (1979). | MR | Zbl
and ,[9] Mapping DNA by stochastic relaxation. Adv. Appl. Math. 8 (1987) 194-207. | Zbl
and ,[10] The NP-completeness column: an ongoing guide. J. Algorithms (1985) 6 291-305. | Zbl
,[11] Algorithms for optical mapping, in Proceedings of the Second International Conference on Computational Biology (RECOMB), New York, (1998) 117-124.
and ,[12] 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] A lower bound on the number of solutions of the probed partial digest problem. Adv. Appl. Math. 14 (1993) 172-183. | Zbl
and ,[14] The restriction mapping problem revisited. J. Comput. Syst. Sci. 65 (2002) 526-544. | Zbl
and ,[15] Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000). | MR | Zbl
,[16] Multiple solutions of DNA restriction mapping problem. Adv. Appl. Math. 12 (1991) 412-427. | Zbl
and ,[17] Ordered restriction maps of Saccharomyces cerevisiac chromosomes constructed by optical mapping. Science 262 (1993) 110-114.
, , , , and ,[18] Introduction to Computational Biology. PWS Publishing Company, Boston (1997).
and ,[19] 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] Reconstructing sets from interpoint distances in Proceedings of Sixth ACM Symposium on Computational Geometry (1990) 332-339.
, and ,[21] A partial digest approach to restriction site mapping. Bull. Math. Biology 56 (1994) 275-294. | Zbl
and ,[22] Introduction to Computational Biology. Maps, Sequences and Genomes, Chapman and Hall: London (1995). | Zbl
,Cited by Sources: