Complexity Issues in Computational Biology

• Autorzy: Blazewicz J. , Kasprzak M.
• Języki publikacji: EN

Abstrakty

EN

The progress of research in the area of computational biology, visible in last decades, brought, among others, a new insight into the complexity issues. The latter, previously studied mainly on the ground of computer science or operational research, gained by a confrontation with problems from the new area. In the paper, several complexity issues inspired by computational biology are presented.

Słowa kluczowe

EN

computational complexity; computational biology; graph theory; nondeterministic Turing machines; DNA computing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 118, nr 4
• Strony: 385--401
• Opis fizyczny: Bibliogr. 52 poz., rys.

Twórcy

autor

Blazewicz J.

autor

Kasprzak M.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland,

Bibliografia

• [1] L.M. Adleman, Molecular computation of solutions to combinatorial problems, Science 266 (1994) 1021-1024.
• [2] A. Aho, J. Hopcroft, and J. Ullman, The Design and Analysis of Computer Algorithms, Addison Wesley, Reading, Massachusetts (1974).
• [3] F. Alizadeh, R.M. Karp, L.A. Newberg, D.K. Weisser, Physical mapping of chromosomes: a combinatorial problem in molecular biology, Algorithmica 13 (1995) 52-76.
• [4] N. Apollonio and P.G. Franciosa, A characterization of partial directed line graphs, Discrete Mathematics 307 (2007) 2598-2614.
• [5] W. Bains and G.C. Smith, A novel method for nucleic acid sequence determination, Journal of Theoretical Biology 135 (1988) 303-307.
• [6] J. Baumgardner et al., Solving a Hamiltonian Path Problem with a bacterial computer, Journal of Biological Engineering 3:11 (2009).
• [7] S. Benzer, On the topology of the genetic fine structure, Proceedings of the National Academy of Sciences of USA 45 (1959) 1607-1620.
• [8] C. Berge, Graphs and Hypergraphs, North-Holland Publishing Company, London (1973).
• [9] A.A. Bertossi, The edge Hamiltonian path problem is NP-complete, Information Processing Letters 13 (1981) 157-159.
• [10] J. Blazewicz, Computational Complexity of Combinatorial Problems, WNT, Warszawa (1988) (in Polish).
• [11] J. Blazewicz, M. Bryja, M. Figlerowicz, P. Gawron, M. Kasprzak, E. Kirton, D. Platt, J. Przybytek, A. Swiercz, and L. Szajkowski, Whole genome assembly from 454 sequencing output via modified DNA graph concept, Computational Biology and Chemistry 33 (2009) 224-230.
• [12] J. Blazewicz, E. Burke, M. Jaroszewski, M. Kasprzak, B. Paliswiat, and P. Pryputniewicz, On the complexity of the Double Digest Problem, Control and Cybernetics 33 (2004) 133-140.
• [13] J. Blazewicz, P. Formanowicz, M. Kasprzak, and D. Kobler, On the recognition of de Bruijn graphs and their induced subgraphs, Discrete Mathematics 245 (2002) 81-92.
• [14] J. Blazewicz, P. Formanowicz, M. Kasprzak, and W.T. Markiewicz, Sequencing by hybridization with isothermic oligonucleotide libraries, Discrete Applied Mathematics 145 (2004) 40-51.
• [15] J. Blazewicz, P. Formanowicz, M. Kasprzak, P. Schuurman, and G.J. Woeginger, A polynomial time equivalence between DNA sequencing and the exact perfect matching problem, Discrete Optimization 4 (2007) 154-162.
• [16] J. Blazewicz, A. Hertz, D. Kobler, and D. de Werra, On some properties of DNA graphs, Discrete Applied Mathematics 98 (1999) 1-19.
• [17] J. Blazewicz and M. Kasprzak, Complexity of DNA sequencing by hybridization, Theoretical Computer Science 290 (2003) 1459-1473.
• [18] J. Blazewicz and M. Kasprzak, Combinatorial optimization in DNA mapping - a computational thread of the Simplified Partial Digest Problem, RAIRO - Operations Research 39 (2005) 227-241.
• [19] J. Blazewicz and M. Kasprzak, Computational complexity of isothermic DNA sequencing by hybridization, Discrete Applied Mathematics 154 (2006) 718-729.
• [20] J. Blazewicz and M. Kasprzak, Graph reduction and its application to DNA sequence assembly, Bulletin of the Polish Academy of Sciences. Technical Sciences 56 (2008) 65-70.
• [21] J. Blazewicz and M. Kasprzak, Reduced-by-matching graphs: toward simplifying Hamiltonian circuit problem, Fundamenta Informaticae, in press.
• [22] J. Blazewicz, M. Kasprzak, B. Leroy-Beaulieu, and D. de Werra, Finding Hamiltonian circuits in quasiadjoint graphs, Discrete Applied Mathematics 156 (2008) 2573-2580.
• [23] N.G. de Bruijn, A combinatorial problem, Koninklijke Nederlandse Akademie v. Wetenschappen Proceedings 49 (1946) 758-764.
• [24] M. Cieliebak and S. Eidenbenz, Measurement errors make the Partial Digest Problem NP-hard, Lecture Notes in Computer Science 2976 (2004) 379-390.
• [25] M. Cieliebak, S. Eidenbenz, and P. Penna, Noisy data make the Partial Digest Problem NP-hard, Lecture Notes in Bioinformatics 2812 (2003) 111-123.
• [26] R. Drmanac, I. Labat, I. Brukner, and R. Crkvenjakov, Sequencing of megabase plus DNA by hybridization: theory of the method, Genomics 4 (1989) 114-128.
• [27] 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).
• [28] A. Han and D. Zhu, DNA encoding method of weight for Chinese postman problem, Proceedings of the IEEE Congress on Evolutionary Computation, IEEE Press, Vancouver (2006) 681-686.
• [29] R. Idury and M.Waterman, A new algorithm for DNA sequence assembly, Journal of Computational Biology 2 (1995) 291-306.
• [30] D.S. Johnson, The NP-completeness column: an ongoing guide, Journal of Algorithms 6 (1985) 291-305.
• [31] J.D. Kececioglu and E.W. Myers, Combinatorial algorithms for DNA sequence assembly, Algorithmica 13 (1995) 7-51.
• [32] J.M. Keil, Finding Hamiltonian circuits in interval graphs, Information Processing Letters 20 (1985) 201-206.
• [33] E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York (1976).
• [34] J.Y. Lee, S.Y. Shin, T.H. Park, and B.T. Zhang, Solving traveling salesman problems with DNA molecules encoding numerical values, Biosystems 78 (2004) 39-47.
• [35] R.J. Lipton, DNA solution of hard computational problems, Science 268 (1995) 542-545.
• [36] Y. Liu, J. Xu, L. Pan, and S. Wang, DNA solution of graph coloring problem, Journal of Chemical Information and Computer Sciences 42 (2002) 524-528.
• [37] Yu.P. Lysov, V.L. Florentiev, A.A. Khorlin, K.R. Khrapko, V.V. Shik, and A.D. Mirzabekov, Determination of the nucleotide sequence of DNA using hybridization with oligonucleotides. A new method, Doklady Akademii Nauk SSSR 303 (1988) 1508-1511.
• [38] P. Medvedev, S. Pham, M. Chaisson, G. Tesler, and P. Pevzner, Paired de Bruijn graphs: a novel approach for incorporating mate pair information into genome assemblers, Lecture Notes in Computer Science 6577 (2011) 238-251.
• [39] N. Nagy and S.G. Akl, Aspects of biomolecular computing, Parallel Processing Letters 17 (2007) 185-211.
• [40] Q. Ouyang, P.D. Kaplan, S. Liu, and A. Libchaber, DNA solution of the maximal clique problem, Science 278 (1997) 446-449.
• [41] C. Papadimitriou, Computational Complexity, Addison Wesley, Reading, Massachusetts (1994).
• [42] J. Parker, Computing with DNA, EMBO reports 4 (2003) 7-10.
• [43] P.A. Pevzner, l-tuple DNA sequencing: computer analysis, Journal of Biomolecular Structure and Dynamics 7 (1989) 63-73.
• [44] P.A. Pevzner, Computational Molecular Biology: an Algorithmic Approach, MIT Press, Cambridge (2000).
• [45] P.A. Pevzner, H. Tang, and M.S.Waterman, An Eulerian path approach to DNA fragment assembly, Proceedings of the National Academy of Sciences of the USA 98 (2001) 9748-9753.
• [46] A. Sackmann, Network Algorithms and Bioinformatics Problems, Ph.D.Thesis, Poznan University of Technology (2008).
• [47] W.J. Savitch, Relationship between nondeterministic and deterministic tape classes, Journal of Computer and System Sciences 4 (1970) 177-192.
• [48] J.D. Ullman, Complexity of sequencing problems, Chapter 4 in E.G. Coffman, Jr. (ed.) Computer and Job-Shop Scheduling Theory, John Wiley & Sons, New York (1976).
• [49] M.S. Waterman, Introduction to Computational Biology. Maps, Sequences, and Genomes, Chapman & Hall, London (1995).
• [50] T. Xia T, J. SantaLucia Jr., M.E. Burkard, R. Kierzek, S.J. Schroeder, X. Jiao, C. Cox, and D.H. Turner, Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson-Crick base pairs, Biochemistry 37 (1998) 14719-14735.
• [51] J. Xiong, Podstawy bioinformatyki, transl. J. Bujnicki et al., Wydawnictwa Uniwersytetu Warszawskiego, Warszawa (2009).
• [52] D.R. Zerbino and E. Birney, Velvet: Algorithms for de novo short read assembly using de Bruijn graphs, Genome Research 18 (2008) 821-829.