# A branch-and-cut algorithm for multiple sequence alignment

@article{Althaus2006ABA, title={A branch-and-cut algorithm for multiple sequence alignment}, author={Ernst Althaus and Alberto Caprara and Hans-Peter Lenhof and Knut Reinert}, journal={Mathematical Programming}, year={2006}, volume={105}, pages={387-425} }

We consider a branch-and-cut approach for solving the multiple sequence alignment problem, which is a central problem in computational biology. We propose a general model for this problem in which arbitrary gap costs are allowed. An interesting aspect of our approach is that the three (exponentially large) classes of natural valid inequalities that we consider turn out to be both facet-defining for the convex hull of integer solutions and separable in polynomial time. Both the proofs that these… Expand

#### Figures, Tables, and Topics from this paper

#### 21 Citations

LASA: A Tool for Non-heuristic Alignment of Multiple Sequences

- Mathematics, Computer Science
- BIRD
- 2008

The experiments show that the implementation LASA outperforms all exact algorithms for the multiple sequence alignment problem and the quality of the alignments ranks among the best computed so far. Expand

A Lagrangian relaxation approach for the multiple sequence alignment problem

- Computer Science
- J. Comb. Optim.
- 2008

This work presents a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology, based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Expand

A Lagrangian Relaxation Approach for the Multiple Sequence Alignment Problem

- Mathematics, Computer Science
- COCOA
- 2007

This work presents a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology, based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Expand

A Branch-and-Cut Algorithm for the 2-Species Duplication-Loss Phylogeny Problem

- Mathematics, Computer Science
- ArXiv
- 2012

This work defines classes of valid inequalities and provides algorithms to separate them efficiently and prove the NP-hardness of the duplication-loss alignment problem. Expand

Computational Problems in Evolution Multiple Alignment

Reconstructing the evolutionary history of a set of species is a fundamental problem in biology. This thesis concerns computational problems that arise in different settings and stages of… Expand

An Exact Mathematical Programming Approach to Multiple RNA Sequence-Structure Alignment

- Computer Science
- Algorithmic Oper. Res.
- 2008

A graph-theoretic representation of the sequence-structure alignment problem is given and a class of constraints that make the problem easier to solve and relax the original integer linear program in a Lagrangian manner are identified. Expand

Segment-based multiple sequence alignment

- Computer Science, Medicine
- ECCB
- 2008

The main problem is to define segments of the sequences in such a way that a graph-based alignment is possible, and the consistency idea can be extended to align multiple genomic sequences. Expand

Dissecting multiple sequence alignment methods: the analysis, design and development of generic multiple sequence alignment components in SeqAn

- Computer Science
- 2010

A novel graph-based multiple sequence alignment program and a new method for multi-read alignments occurring in assembly projects, both of which are apparently one of the rst methods that can readily be used for insert sequencing. Expand

The Duplication-Loss Small Phylogeny Problem: From Cherries to Trees

- Computer Science, Medicine
- J. Comput. Biol.
- 2013

The experiments show that its repeated computation considerably reduces the number of duplications and losses along the tree both on simulated instances comprising 128 leaves and a set of Bacillus genomes, and it is proved that the small phylogeny problem in the duplication-loss model is NP-complete already for two species. Expand

Upcoming challenges for multiple sequence alignment methods in the high-throughput era

- Biology, Computer Science
- Bioinform.
- 2009

This review focuses on recent trends in multiple sequence alignment tools. It describes the latest algorithmic improvements including the extension of consistency-based methods to the problem of… Expand

#### References

SHOWING 1-10 OF 43 REFERENCES

A polyhedral approach to sequence alignment problems

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1999

This work studies two new problems in sequence alignment both from a practical and a theoretical view, using tools from combinatorial optimization to develop branch-and-cut algorithms for pairwise sequence alignment that are not based on dynamic programming. Expand

The Practical Use of the A* Algorithm for Exact Multiple Sequence Alignment

- Mathematics, Medicine
- J. Comput. Biol.
- 2000

The A* algorithm together with a standard bounding technique is superior to the well-known Carrillo-Lipman bounding since it excludes more nodes from consideration and can speed up computations considerably. Expand

An exact solution for the Segment-to-Segment multiple sequence alignment problem

- Mathematics, Computer Science
- German Conference on Bioinformatics
- 1998

It is shown that the segment-to-segment multiple alignment problem is equivalent to a novel formulation of the Maximum Trace problem: the Generalized Maximum Trace (GMT) problem, which can be stated in terms of an integer linear program and then solved using methods from polyhedral combinatorics. Expand

An iterative method for faster sum-of-pairs multiple sequence alignment

- Computer Science, Medicine
- Bioinform.
- 2000

An algorithm is presented that uses the divide-and-conquer alignment approach together with recent results on search space reduction to speed up the computation of multiple sequence alignments and applies the alpha(*) algorithm which leads to a procedure provably more efficient than previous exact algorithms. Expand

The multiple sequence alignment problem in biology

- Mathematics
- 1988

The study and comparison of sequences of characters from a finite alphabet is relevant to various areas of science, notably molecular biology. The measurement of sequence similarity involves the… Expand

A Polyhedral Approach to the Asymmetric Traveling Salesman Problem

- Mathematics
- 1997

Several branch-and-bound algorithms for the exact solution of the asymmetric traveling salesman problem ATSP, based on the assignment problem AP relaxation, have been proposed in the literature.… Expand

Improving the Practical Space and Time Efficiency of the Shortest-Paths Approach to Sum-of-Pairs Multiple Sequence Alignment

- Mathematics, Computer Science
- J. Comput. Biol.
- 1995

The MSA program implements a branch-and-bound technique together with a variant of Dijkstra's shortest paths algorithm to prune the basic dynamic programming graph to find optimal alignments of multiple protein or DNA sequences. Expand

T-Coffee: A novel method for fast and accurate multiple sequence alignment.

- Biology, Medicine
- Journal of molecular biology
- 2000

A new method for multiple sequence alignment that provides a dramatic improvement in accuracy with a modest sacrifice in speed as compared to the most commonly used alternatives but avoids the most serious pitfalls caused by the greedy nature of this algorithm. Expand

Generalized Sequence Alignment and Duality

- Mathematics
- 1993

Although a number of efficient algorithms for the longest common subsequence (LCS) problem have been suggested since the 1970s, there is no duality theorem for the LCS problem. In the present paper a… Expand

On-line dynamic programming with applications to the prediction of RNA secondary structure

- Computer Science, Mathematics
- SODA '90
- 1990

An efficient algorithm for Waterman's problem, an on-line two-dimensional dynamic programming problem that is used for the prediction of RNA secondary structure, and an O(n + h log min{h, n2h}) time algorithm for the sparse convex case, where h is the number of possible base pairs in the RNA structure. Expand