A Lagrangian Relaxation Approach for the Multiple Sequence Alignment Problem

problems in computational biology. A branch-and-bound (bb) algorithm will
be presented in which the upper bound at each bb node is based on a Lagrangian
relaxation of an integer linear programming formulation for MSA. Dualizing certain
inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which
can be solved efficiently by a dynamic programming approach. Due to a reformulation
w.r.t. additionally introduced variables prior to relaxation we improve the convergence
rate dramatically while at the same time being able to solve the Lagrangian problem efficiently.