Skip Navigation

This Article
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (12)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Lenhof, H.
Right arrow Articles by Reinert, K
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Lenhof, H.
Right arrow Articles by Reinert, K
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Bioinformatics, Vol 15, 203-210, Copyright © 1999 by Oxford University Press

ARTICLES

An exact solution for the segment-to-segment multiple sequence alignment problem

HP Lenhof, B Morgenstern and K Reinert
MPI fur Informatik, Im Stadtwald, 66123 Saarbrucken, Germany.

MOTIVATION: In molecular biology, sequence alignment is a crucial tool in studying the structure and function of molecules, as well as the evolution of species. In the segment-to-segment variation of the multiple alignment problem, the input can be seen as a set of non- gapped segment pairs (diagonals). Given a weight function that assigns a weight score to every possible diagonal, the goal is to choose a consistent set of diagonals of maximum weight. We show that the segment- to-segment multiple alignment problem is equivalent to a novel formulation of the Maximum Trace problem: the Generalized Maximum Trace (GMT) problem. Solving this problem to optimality, therefore, may improve upon the previous greedy strategies that are used for solving the segment-to-segment multiple sequence alignment problem. We show that the GMT can be stated in terms of an integer linear program and then solve the integer linear program using methods from polyhedral combinatorics. This leads to a branch-and-cut algorithm for segment-to- segment multiple sequence alignment. RESULTS: We report on our first computational experiences with this novel method and show that the program is able to find optimal solutions for real-world test examples.
Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 BioinformaticsHome page
T. Rausch, A.-K. Emde, D. Weese, A. Doring, C. Notredame, and K. Reinert
Segment-based multiple sequence alignment
Bioinformatics, August 15, 2008; 24(16): i187 - i192.
[Abstract] [PDF]

Home page
 Nucleic Acids ResHome page
I. M. Wallace, O. O'Sullivan, D. G. Higgins, and C. Notredame
M-Coffee: combining multiple sequence alignment methods with T-Coffee
Nucleic Acids Res., March 23, 2006; 34(6): 1692 - 1699.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
B. Morgenstern
DIALIGN: multiple DNA and protein sequence alignment at BiBiServ
Nucleic Acids Res., July 1, 2004; 32(suppl_2): W33 - W36.
[Abstract] [Full Text] [PDF]

Home page
 Antimicrob. Agents Chemother.Home page
S. A. Granier, V. Leflon-Guibout, F. W. Goldstein, and M.-H. Nicolas-Chanoine
New Klebsiella oxytoca {beta}-Lactamase Genes blaOXY-3 and blaOXY-4 and a Third Genetic Group of K. oxytoca Based on blaOXY-3
Antimicrob. Agents Chemother., September 1, 2003; 47(9): 2922 - 2928.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.