de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44003

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44909

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45277

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44907

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
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: http://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.