A Lagrangian relaxation approach for the multiple sequence alignment problem

Ernst Althaus, Stefan Canzar

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. 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. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem. Furthermore, the quality of the alignments is among the best computed so far.

Original languageEnglish (US)
Pages (from-to)127-154
Number of pages28
JournalJournal of Combinatorial Optimization
Issue number2
StatePublished - Aug 2008

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'A Lagrangian relaxation approach for the multiple sequence alignment problem'. Together they form a unique fingerprint.

Cite this