On the complexity of the Double Digest Problem

• Autorzy: Błażewicz J. , Burke E. , Jaroszewski M. , Kasprzak M. , Paliswiat B. , Pryputniewicz P.
• Języki publikacji: EN

Abstrakty

EN

The problem of genome mapping is considered. It is showed that the Double Digest Problem (DDP) is NP-hard in its search version, while its decision version is trivially easy.

Słowa kluczowe

EN

computational complexity; DNA restriction maps

PL

złożoność obliczeniowa

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2004
• Tom: Vol. 33, no 1
• Strony: 133--140
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Błażewicz J.

• nstitute of Computing Science, Poznań University of Technology, Piotrowo 3A, 60-965 Poznań, Poland
• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznań, Poland.

autor

Burke E.

• University of Nottingham

autor

Jaroszewski M.

• Institute of Computing Science, Poznań University of Technology, Piotrowo 3A, 60-965 Poznań, Poland.
• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznań, Poland.

autor

Kasprzak M.

• Institute of Computing Science, Poznań University of Technology, Piotrowo 3A, 60-965 Poznań, Poland.
• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznań, Poland.

autor

Paliswiat B.

• Institute of Computing Science, Poznań University of Technology, Piotrowo 3A, 60-965 Poznań, Poland.

autor

Pryputniewicz P.

• Institute of Computing Science, Poznań University of Technology, Piotrowo 3A, 60-965 Poznań, Poland.

Bibliografia

• Alizadeh, F., Karp, R.M., Weisser, D.K. and Zweig, G. (1995) Physical mapping of chromosomes using unique end-probes. Journal of Computational Biology 2, 159-184.
• Błażewicz, J., Formanowicz, P., Jaroszewski, M., Kasprzak, M. and Markiewicz, W.T.(2001) Construction of DNA restriction maps basedon a simplified experiment. Bioinformatics 5, 398-404.
• Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability. A Guide to the theory of NP-Completeness. W.H. Freeman and Company, San Francisco.
• Goldstein, L. and Waterman, M.S. (1987) Mapping DNA by stochastic relaxation. Advanced Applied Mathematics 8, 194-207.
• Karp, R.M. (1972) Reducibility among combinatorial problems. In: R.E.Miller and J.W. Thatcher, eds., Complexity of Computer Computations. Plenum Press, New York, 85-103.
• Rosenblatt, J. and Seymour, P. (1982) The structure of homeometric sets. SIAM J. Alg. Disc. Math. 3, 343-350.
• Schmitt, W. and Waterman, M.S. (1991) Multiple solutions of DNA restriction mapping problem. Advanced Applied Mathematics 12, 412-427.
• Setubal, J. and Meidanis, J. (1997) Introduction to Computational Biology. PWS Publishing Company, Boston.
• Skiena, S.S., Smith, W.D. and Lemke, P. (1990) Reconstructing sets frominterpoint distances. In: Proc. Sixth ACM Symp. Computational Geometry. 332-339.
• Skiena, S.S. and Sundaram, G. (1994) A partial digest approach to restriction site mapping. Bulletin of Mathematical Biology 56, 275-294.
• Waterman, M.S. (1995) Introduction to Computational Biology. Maps, Sequences and Genomes. Chapman & Hall, London.