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

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( n log n )-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 - 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. [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. [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. [3] J. Blazewicz and M. Jaroszewski, New algorithm for the Simplified Partial Digest Problem. Lect. Notes Bioinformatics 2812 (2003) 95–110. 
  4. [4] J. Blazewicz and M. Kasprzak, Complexity of DNA sequencing by hybridization. Theoret. Comput. Sci. 290 (2003) 1459–1473. Zbl1044.68065
  5. [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. [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. [7] G.B. Fogel and D.W. Corne, eds. Evolutionary Computations in Bioinformatics. Morgan Kaufman, Boston (2003). 
  8. [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. [9] L. Goldstein and M.S. Waterman, Mapping DNA by stochastic relaxation. Adv. Appl. Math. 8 (1987) 194–207. Zbl0638.92005
  10. [10] D.S. Johnson, The NP-completeness column: an ongoing guide. J. Algorithms (1985) 6 291–305. Zbl0588.68020
  11. [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. [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. [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. [14] G. Pandurangan and H. Ramesh, The restriction mapping problem revisited. J. Comput. Syst. Sci. 65 (2002) 526–544. Zbl1059.68159
  15. [15] P.A. Pevzner, Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000). Zbl0972.92011MR1790966
  16. [16] W. Schmitt and M.S. Waterman, Multiple solutions of DNA restriction mapping problem. Adv. Appl. Math. 12 (1991) 412–427. Zbl0760.92007
  17. [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. [18] J. Setubal and J. Meidanis, Introduction to Computational Biology. PWS Publishing Company, Boston (1997). 
  19. [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. [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. [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. [22] M.S. Waterman, Introduction to Computational Biology. Maps, Sequences and Genomes, Chapman and Hall: London (1995). Zbl0831.92011

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.