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

Title:
An exact solution for the segment-to-segment multiple sequence alignment problem
Authors:
LENHOF, H.-P, MORGENSTERN, B, REINERT, K
Source:
Selection of papers presented at the German Conference on Bioinformatics (GCB'98, Cologne, Germany, October 1998Bioinformatics (Oxford. Print). 15(3):203-210
Publisher Information:
Oxford: Oxford University Press, 1999.
Publication Year:
1999
Physical Description:
print, 22 ref
Original Material:
INIST-CNRS
Subject Terms:
Bioinformatics, Bioinformatique, Sciences biologiques et medicales, Biological and medical sciences, Sciences biologiques fondamentales et appliquees. Psychologie, Fundamental and applied biological sciences. Psychology, Generalites, General aspects, Mathématiques biologiques. Statistiques. Modèles. Métrologie. Informatique en biologie (généralités), Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects), Traitement informatique, Computerized processing, Tratamiento informático, Alignement séquence, Sequence alignment, Alineación secuencia, Détection, Detection, Detección, Etude comparative, Comparative study, Estudio comparativo, Homologie, Homology, Homología, Logiciel, Software, Logicial, Méthode, Method, Método, Protéine, Protein, Proteína
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
MPI für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany
GSF - National Research Center for Environment and Health, Institute of Biomathematics and Biometry, Ingolstädter Landstrasse 1, 85764 Neuherberg, Germany
ISSN:
1367-4803
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=1831439
Rights:
Copyright 1999 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Biological sciences. Generalities. Modelling. Methods

Generalities in biological sciences
Accession Number:
edscal.1831439
Database:
PASCAL Archive

Weitere Informationen

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 ofthe 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 ofan 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.