MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Althaus, Ernst
Caprara, Alberto
Lenhof, Hans-Peter
Reinert, Knut
dblp
dblp
dblp
dblp
Not MPG Author(s):
Caprara, Alberto
Lenhof, Hans-Peter
Reinert, Knut
Editor(s):
Lengauer, Thomasdblp
Not MPII Editor(s):
Lenhof, Hans-Peter
BibTeX cite key*:
Althaus2002b
Title, Booktitle
Title*:
Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics
Booktitle*:
Proceedings of the European Conference on Computational Biology (ECCB 2002)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Saarbrücken
Language:
English
Event Date*
(no longer used):
-- October 6 - October 9
Organization:
Event Start Date:
6 October 2002
Event End Date:
9 October 2002
Publisher
Name*:
Oxford University Press
URL:
Address*:
Oxford, UK
Type:
Vol, No, Year, pp.
Series:
Bioinformatics
Volume:
18
Number:
Supplement 2
Month:
October
Pages:
S4-S16
Year*:
2002
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Althaus2002b,
AUTHOR = {Althaus, Ernst and Caprara, Alberto and Lenhof, Hans-Peter and Reinert, Knut},
EDITOR = {Lengauer, Thomas},
TITLE = {Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics},
BOOKTITLE = {Proceedings of the European Conference on Computational Biology (ECCB 2002)},
PUBLISHER = {Oxford University Press},
YEAR = {2002},
NUMBER = {Supplement 2},
VOLUME = {18},
PAGES = {S4--S16},
SERIES = {Bioinformatics},
ADDRESS = {Saarbr{\"u}cken},
MONTH = {October},
}


Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ernst Althaus
Created
12/18/2002 04:27:53 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
28.08.2003 16:36:18
27.08.2003 20:29:24
27.08.2003 20:11:06
27.08.2003 20:09:35
27.08.2003 20:08:56