A Lagrangian relaxation approach for the multiple sequence alignment problem

Ernst Althaus; Stefan Canzar

doi:10.1007/978-3-540-73556-4_29

A Lagrangian relaxation approach for the multiple sequence alignment problem

Ernst Althaus, Stefan Canzar

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian sub-problem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem.

Original language	English (US)
Title of host publication	Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings
Publisher	Springer Verlag
Pages	267-278
Number of pages	12
ISBN (Print)	9783540735557
DOIs	https://doi.org/10.1007/978-3-540-73556-4_29
State	Published - 2007
Event	1st International Conference on Combinatorial Optimization and Applications, COCOA 2007 - Xi'an, China Duration: Aug 14 2007 → Aug 16 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4616 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Conference on Combinatorial Optimization and Applications, COCOA 2007
Country/Territory	China
City	Xi'an
Period	8/14/07 → 8/16/07

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-73556-4_29

Cite this

Althaus, E., & Canzar, S. (2007). A Lagrangian relaxation approach for the multiple sequence alignment problem. In Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings (pp. 267-278). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4616 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-73556-4_29

Althaus, Ernst ; Canzar, Stefan. / A Lagrangian relaxation approach for the multiple sequence alignment problem. Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings. Springer Verlag, 2007. pp. 267-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{df77ca25ef0a421c9604300ef732c123,

title = "A Lagrangian relaxation approach for the multiple sequence alignment problem",

abstract = "We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian sub-problem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem.",

author = "Ernst Althaus and Stefan Canzar",

year = "2007",

doi = "10.1007/978-3-540-73556-4_29",

language = "English (US)",

isbn = "9783540735557",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "267--278",

booktitle = "Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings",

address = "Germany",

note = "1st International Conference on Combinatorial Optimization and Applications, COCOA 2007 ; Conference date: 14-08-2007 Through 16-08-2007",

}

Althaus, E & Canzar, S 2007, A Lagrangian relaxation approach for the multiple sequence alignment problem. in Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4616 LNCS, Springer Verlag, pp. 267-278, 1st International Conference on Combinatorial Optimization and Applications, COCOA 2007, Xi'an, China, 8/14/07. https://doi.org/10.1007/978-3-540-73556-4_29

A Lagrangian relaxation approach for the multiple sequence alignment problem. / Althaus, Ernst; Canzar, Stefan.
Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings. Springer Verlag, 2007. p. 267-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4616 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A Lagrangian relaxation approach for the multiple sequence alignment problem

AU - Althaus, Ernst

AU - Canzar, Stefan

PY - 2007

Y1 - 2007

N2 - We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian sub-problem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem.

AB - We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian sub-problem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem.

UR - http://www.scopus.com/inward/record.url?scp=38149042024&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38149042024&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-73556-4_29

DO - 10.1007/978-3-540-73556-4_29

M3 - Conference contribution

AN - SCOPUS:38149042024

SN - 9783540735557

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 267

EP - 278

BT - Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings

PB - Springer Verlag

T2 - 1st International Conference on Combinatorial Optimization and Applications, COCOA 2007

Y2 - 14 August 2007 through 16 August 2007

ER -

Althaus E, Canzar S. A Lagrangian relaxation approach for the multiple sequence alignment problem. In Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings. Springer Verlag. 2007. p. 267-278. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-73556-4_29

A Lagrangian relaxation approach for the multiple sequence alignment problem

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this