A branch-and-cut algorithm for multiple sequence alignment
Knut Reinert, Hans‐Peter Lenhof, Petra Mutzel et al. · Annual International Conference on Research in Computational Molecular Biology (RECOMB) · 1997
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 classes of valid inequalities are facet-defining and the description of the separation algorithms are far from trivial. Experimental results on several benchmark instances show that our method outperforms the best tools developed so far, in that it produces alignments that are better from a biological point of view. A noteworthy outcome of the results is the effectiveness of using branch-and-cut with only a carefully-selected subset of the variables as a heuristic.
Cited by 66 works. doi:10.1145/267521.267845
Authors
References
- Basic Local Alignment Search Tool
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Amino acid substitution matrices from protein blocks.
- An improved algorithm for matching biological sequences
- Algorithmic Graph Theory and Perfect Graphs
- Algorithms on strings, trees, and sequences computer science and computational biology
- LEDA: a platform for combinatorial and geometric computing
- The Multiple Sequence Alignment Problem in Biology
- On the Complexity of Multiple Sequence Alignment
- Properties of vertex packing and independence system polyhedra