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

Abstract

top
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.

How to cite

top

Blazewicz, 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
  1. S. Benzer, On the topology of the genetic fine structure, in Proceedings of the National Academy of Sciences of the USA45 (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. Bioinformatics17 (2001) 398–404.  
  3. J. Blazewicz and M. Jaroszewski, New algorithm for the Simplified Partial Digest Problem. Lect. Notes Bioinformatics2812 (2003) 95–110.  
  4. J. Blazewicz and M. Kasprzak, Complexity of DNA sequencing by hybridization. Theoret. Comput. Sci.290 (2003) 1459–1473.  
  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 Bioinformatics2812 (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).  
  9. L. Goldstein and M.S. Waterman, Mapping DNA by stochastic relaxation. Adv. Appl. Math.8 (1987) 194–207.  
  10. D.S. Johnson, The NP-completeness column: an ongoing guide. J. Algorithms (1985) 6 291–305.  
  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.  
  14. G. Pandurangan and H. Ramesh, The restriction mapping problem revisited. J. Comput. Syst. Sci.65 (2002) 526–544.  
  15. P.A. Pevzner, Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000).  
  16. W. Schmitt and M.S. Waterman, Multiple solutions of DNA restriction mapping problem. Adv. Appl. Math.12 (1991) 412–427.  
  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. Science262 (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.  
  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. Biology56 (1994) 275–294.  
  22. M.S. Waterman, Introduction to Computational Biology. Maps, Sequences and Genomes, Chapman and Hall: London (1995).  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.