# Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem

Jacek Blazewicz; Marta Kasprzak

RAIRO - Operations Research (2006)

- 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 39.4 (2006): 227-241. <http://eudml.org/doc/105331>.

@article{Blazewicz2006,

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(nlogn)-time algorithm is given, where n is a number of restriction sites.
},

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

journal = {RAIRO - Operations Research},

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

language = {eng},

month = {4},

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/105331},

volume = {39},

year = {2006},

}

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

DA - 2006/4//

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(nlogn)-time algorithm is given, where n is a number of restriction sites.

LA - eng

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

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

ER -

## References

top- S. Benzer, On the topology of the genetic fine structure, in Proceedings of the National Academy of Sciences of the USA45 (1959) 1607–1620.
- J. Blazewicz, P. Formanowicz, M. Kasprzak, M. Jaroszewski and W.T. Markiewicz, Construction of DNA restriction maps based on a simplified experiment. Bioinformatics17 (2001) 398–404.
- J. Blazewicz and M. Jaroszewski, New algorithm for the Simplified Partial Digest Problem. Lect. Notes Bioinformatics2812 (2003) 95–110.
- J. Blazewicz and M. Kasprzak, Complexity of DNA sequencing by hybridization. Theoret. Comput. Sci.290 (2003) 1459–1473.
- M. Cieliebak and S. Eidenbenz, Measurement errors make the partial digest problem NP-hard. Lect. Notes Comput. Sci.2976 (2004) 379–390.
- M. Cieliebak, S. Eidenbenz and P. Penna, Noisy data make the partial digest problem NP-hard. Lect. Notes Bioinformatics2812 (2003) 111–123.
- G.B. Fogel and D.W. Corne, eds. Evolutionary Computations in Bioinformatics. Morgan Kaufman, Boston (2003).
- 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).
- L. Goldstein and M.S. Waterman, Mapping DNA by stochastic relaxation. Adv. Appl. Math.8 (1987) 194–207.
- D.S. Johnson, The NP-completeness column: an ongoing guide. J. Algorithms (1985) 6 291–305.
- 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.
- 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).
- 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.
- G. Pandurangan and H. Ramesh, The restriction mapping problem revisited. J. Comput. Syst. Sci.65 (2002) 526–544.
- P.A. Pevzner, Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000).
- W. Schmitt and M.S. Waterman, Multiple solutions of DNA restriction mapping problem. Adv. Appl. Math.12 (1991) 412–427.
- 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. Science262 (1993) 110–114.
- J. Setubal and J. Meidanis, Introduction to Computational Biology. PWS Publishing Company, Boston (1997).
- 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.
- 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.
- S.S. Skiena and G. Sundaram, A partial digest approach to restriction site mapping. Bull. Math. Biology56 (1994) 275–294.
- M.S. Waterman, Introduction to Computational Biology. Maps, Sequences and Genomes, Chapman and Hall: London (1995).

## Citations in EuDML Documents

top## NotesEmbed ?

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