Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-2007-1-002

A Lagrangian relaxation approach for the multiple sequence alignment problem

Althaus, Ernst and Canzar, Stefan

MPI-I-2007-1-002. September 2007, 41 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.

Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2007-1-002.pdf349 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://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},
}