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


A branch-and-cut algorithm for multiple sequence alignment

Reinert, Knut and Lenhof, Hans-Peter and Mutzel, Petra and Mehlhorn, Kurt and Kececioglou, John D.

MPI-I-96-1-028. November 1996, 15 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Multiple sequence alignment is an important problem in computational biology.
We study the Maximum Trace formulation introduced by
We first phrase the problem in terms of forbidden subgraphs,
which enables us to express Maximum Trace as an integer linear-programming
and then solve the integer linear program using methods from polyhedral
The trace {\it polytope\/} is the convex hull of all feasible solutions
to the Maximum Trace problem;
for the case of two sequences,
we give a complete characterization of this polytope.
This yields a polynomial-time algorithm
for a general version of pairwise sequence alignment
that, perhaps suprisingly, does not use dynamic programming;
this yields, for instance, a non-dynamic-programming algorithm for
sequence comparison under the 0-1 metric,
which gives another answer to a long-open question in the area of string algorithms
For the multiple-sequence case,
we derive several classes of facet-defining inequalities
and show that for all but one class, the corresponding separation problem
can be solved in polynomial time.
This leads to a branch-and-cut algorithm for multiple sequence alignment,
and we report on our first computational experience.
It appears that a polyhedral approach to multiple sequence alignment
can solve instances that are beyond present dynamic-programming approaches.

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-96-1-028.ps202 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:

Hide details for BibTeXBibTeX
  AUTHOR = {Reinert, Knut and Lenhof, Hans-Peter and Mutzel, Petra and Mehlhorn, Kurt and Kececioglou, John D.},
  TITLE = {A branch-and-cut algorithm for multiple sequence alignment},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-96-1-028},
  MONTH = {November},
  YEAR = {1996},
  ISSN = {0946-011X},