Send to

Choose Destination
Bioinformatics. 2002;18 Suppl 2:S4-S16.

Multiple sequence alignment with arbitrary gap costs: computing an optimal solution using polyhedral combinatorics.

Author information

International Computer Science Institute, Berkeley, CA 94704-1198, USA.


Multiple sequence alignment is one of the dominant problems in computational molecular biology. Numerous scoring functions and methods have been proposed, most of which result in NP-hard problems. In this paper we propose for the first time a general formulation for multiple alignment with arbitrary gap-costs based on an integer linear program (ILP). In addition we describe a branch-and-cut algorithm to effectively solve the ILP to optimality. We evaluate the performances of our approach in terms of running time and quality of the alignments using the BAliBase database of reference alignments. The results show that our implementation ranks amongst the best programs developed so far.

[Indexed for MEDLINE]

Supplemental Content

Loading ...
Support Center