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