A path selection approach to global pairwise sequence alignment using integer linear optimization†

†Dedicated to H. Th. Jongen on the occasion of his 60th birthday.

Abstract

An important and well-studied problem in the area of computational biology is the sequence alignment problem. A novel integer linear programming (ILP) model has been developed to rigorously address the global pairwise sequence alignment problem. The important components of the model formulation, in addition to its rigour are (a) the natural introduction of functionally important conservation constraints, (b) the creation of a rank-ordered list of the highest scoring alignments and (c) the possible refinement of alignments by pairwise interaction scores. By using a path selection approach that employs some of the algorithmic advantages of dynamic programming methods, this integer linear optimization model gains efficiency while maintaining the rigour of the combinatorial optimization approach.

†Dedicated to H. Th. Jongen on the occasion of his 60th birthday.

Keywords:

• sequence alignment
• integer linear optimization
• global pairwise alignment
• rank-order list of alignments.

2000 Mathematics Subject Classifications: :

• 90C10
• 92-08

Acknowledgements

C.A. Floudas gratefully acknowledges financial support from the National Science Foundation (R01 GM52032), the National Institutes of Health (R24 GM069736), and the US EPA (GAD R 832721-010). This work has not been reviewed by and does not represent the opinions of the funding agencies.

Notes

†Dedicated to H. Th. Jongen on the occasion of his 60th birthday.