title: Multiple sequence alignment with arbitrary gap costs: computing an optimal solution using polyhedral combinatorics.
abstract: 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.
authors.affiliation: International Computer Science Institute, Berkeley, CA 94704-1198, USA. althaus@icsi.berkeley.edu
authors.forename: Ernst
authors.initials: E
authors.lastname: Althaus
authors.forename: Alberto
authors.initials: A
authors.lastname: Caprara
authors.forename: Hans-Peter
authors.initials: HP
authors.lastname: Lenhof
authors.forename: Knut
authors.initials: K
authors.lastname: Reinert
mesh_terms: D000465:Algorithms; D017124:Conserved Sequence; D008954:Models, Biological; D008956:Models, Chemical; D015233:Models, Statistical; D009716:Numerical Analysis, Computer-Assisted; D010363:Pattern Recognition, Automated / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology