Complexity Issues in Computational Biology

Issue title: Watching the Daisies Grow: from Biology to Biomathematics and Bioinformatics — Alan Turing Centenary Special Issue

Article type: Research Article

Authors: Blazewicz, Jacek^; | Kasprzak, Marta^;

Affiliations: Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland | Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland, marta@cs.put.poznan.pl

Note: [] Address for correspondence: Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland

Abstract: 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.

Keywords: computational complexity, computational biology, graph theory, nondeterministic Turing machines, DNA computing

DOI: 10.3233/FI-2012-721

Journal: Fundamenta Informaticae, vol. 118, no. 4, pp. 385-401, 2012