Optimization problems in molecular biology: a survey and critical review

Computational molecular biology has emerged as one of the most exciting interdisciplinary fields, riding on the success of the ongoing Human Genome Project, which culminated in the 2001 announcement of the complete sequencing of the human genome. It is only in the past few years that it has been shown that a large number of molecular biology problems can be formulated as combinatorial optimization problems, including sequence alignment problems, genome rearrangement problems, string selection and comparison problems, and protein structure prediction and recognition. This paper provides a detailed description of several interesting molecular biology problems that can be formulated as combinatorial optimization problems and surveys the most efficient state-of-the-art techniques and algorithms to exactly or approximately solve them.