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

Jacek Blazewicz; Marta Kasprzak

RAIRO - Operations Research - Recherche Opérationnelle (2005)

- Volume: 39, Issue: 4, page 227-241
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBlazewicz, Jacek, and Kasprzak, Marta. "Combinatorial optimization in DNA mapping — A computational thread of the simplified partial digest problem." RAIRO - Operations Research - Recherche Opérationnelle 39.4 (2005): 227-241. <http://eudml.org/doc/244665>.

@article{Blazewicz2005,

abstract = {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\,\mathrm \{log\}\,n$)-time algorithm is given, where $n$ is a number of restriction sites.},

author = {Blazewicz, Jacek, Kasprzak, Marta},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {combinatorial optimization; DNA restriction mapping; partial digest; computational complexity},

language = {eng},

number = {4},

pages = {227-241},

publisher = {EDP-Sciences},

title = {Combinatorial optimization in DNA mapping — A computational thread of the simplified partial digest problem},

url = {http://eudml.org/doc/244665},

volume = {39},

year = {2005},

}

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

PB - EDP-Sciences

VL - 39

IS - 4

SP - 227

EP - 241

AB - 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\,\mathrm {log}\,n$)-time algorithm is given, where $n$ is a number of restriction sites.

LA - eng

KW - combinatorial optimization; DNA restriction mapping; partial digest; computational complexity

UR - http://eudml.org/doc/244665

ER -

## References

top- [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. Zbl1044.68065
- [5] M. Cieliebak and S. Eidenbenz, Measurement errors make the partial digest problem NP-hard. Lect. Notes Comput. Sci. 2976 (2004) 379–390. Zbl1196.68100
- [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). Zbl0411.68039MR519066
- [9] L. Goldstein and M.S. Waterman, Mapping DNA by stochastic relaxation. Adv. Appl. Math. 8 (1987) 194–207. Zbl0638.92005
- [10] D.S. Johnson, The NP-completeness column: an ongoing guide. J. Algorithms (1985) 6 291–305. Zbl0588.68020
- [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. Zbl0776.92006
- [14] G. Pandurangan and H. Ramesh, The restriction mapping problem revisited. J. Comput. Syst. Sci. 65 (2002) 526–544. Zbl1059.68159
- [15] P.A. Pevzner, Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000). Zbl0972.92011MR1790966
- [16] W. Schmitt and M.S. Waterman, Multiple solutions of DNA restriction mapping problem. Adv. Appl. Math. 12 (1991) 412–427. Zbl0760.92007
- [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. Zbl0916.51001
- [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. Zbl0790.92014
- [22] M.S. Waterman, Introduction to Computational Biology. Maps, Sequences and Genomes, Chapman and Hall: London (1995). Zbl0831.92011

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.