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

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.