English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3001-0 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3003-C
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Althaus, Ernst1, Author           
Caprara, Alberto, Author
Lenhof, Hans-Peter1, Author           
Reinert, Knut1, Author           
Lengauer, Thomas2, Editor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society, ou_40046              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2003-08-282002
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 202065
Other: Local-ID: C1256428004B93B8-14DF56BBB5470A4DC1256C930054F370-Althaus2002b
 Degree: -

Event

show
hide
Title: ECCB 2002
Place of Event: Saarbrücken
Start-/End Date: 2002-10-06 - 2002-10-09

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the European Conference on Computational Biology (ECCB 2002)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Oxford, UK : Oxford University Press
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: S4 - S16 Identifier: -

Source 2

show
hide
Title: Bioinformatics
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -