@inproceedings{cbea9730bb54499a9b4a753bd5ff21de,
title = "LASA: A tool for non-heuristic alignment of multiple sequences",
abstract = "We have developed a non-heuristic tool (LASA) for the multiple sequence alignment problem (MSA), one of the most important problems in computational molecular biology. It is based on a dynamic programming algorithm for solving a Lagrangian relaxation of an integer linear programming (ILP) formulation for MSA. The objective function that is optimized by LASA models the sum-of-pairs scoring scheme and {"}truly{"} affine gap costs. 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 LASA outperforms all exact algorithms for the multiple sequence alignment problem. Furthermore, the quality of the alignments ranks among the best computed so far.",
author = "Ernst Althaus and Stefan Canzar",
year = "2008",
doi = "10.1007/978-3-540-70600-7_38",
language = "English (US)",
isbn = "9783540705987",
series = "Communications in Computer and Information Science",
publisher = "Springer Verlag",
pages = "489--498",
booktitle = "Bioinformatics Research and Development - Second International Conference, BIRD 2008, Proceedings",
address = "Germany",
note = "2nd International Conference on Bioinformatics Research and Development, BIRD 2008 ; Conference date: 07-07-2008 Through 09-07-2008",
}