Optimization Techniques in Computing Good Quality Solutions to Sequence Alignment Problems

In the past few years a large number of molecular biology problems have been 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 describes the combinatorial formulation of some among the most interesting molecular biology problems and surveys the most efficient state-of-the-art techniques and algorithms to exactly or approximately solve them.