English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

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

MPS-Authors
/persons/resource/persons44003

Althaus,  Ernst
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44909

Lenhof,  Hans-Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45277

Reinert,  Knut
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44907

Lengauer,  Thomas
Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Althaus, E., Caprara, A., Lenhof, H.-P., & Reinert, K. (2002). Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics. In Proceedings of the European Conference on Computational Biology (ECCB 2002) (pp. S4-S16). Oxford, UK: Oxford University Press.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-3001-0
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.