MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments

MPI-I-2007-1-002

A Lagrangian relaxation approach for the multiple sequence alignment problem

Althaus, Ernst and Canzar, Stefan

September 2007, 41 pages.

.
Status: available - back from printing

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.

  • MPI-I-2007-1-002.pdf
  • Attachement: MPI-I-2007-1-002.pdf (349 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2007-1-002

Hide details for BibTeXBibTeX
@TECHREPORT{AlthausCanzer2007,
  AUTHOR = {Althaus, Ernst and Canzar, Stefan},
  TITLE = {A Lagrangian relaxation approach for the multiple sequence alignment problem},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2007-1-002},
  MONTH = {September},
  YEAR = {2007},
  ISSN = {0946-011X},
}