Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

A new algorithmic approach to the construction of multiple alignments and evolutionary trees

 
: Schwikowski, B.

:
urn:nbn:de:0011-b-731163 (1.2 MByte PDF)
MD5 Fingerprint: 7f19884485d80e9844c6b6e7de529c98


Sankt Augustin: GMD Forschungszentrum Informationstechnik, 1998, 174 pp.
Zugl.: Bonn, Univ., Diss., 1998
GMD research series, 1998,14
ISBN: 3-88457-338-1
English
Dissertation, Electronic Publication
Fraunhofer SCAI ()
molekulare Bioinformatik; Algorithmen; multiples Alignment; evolutionärer Baum; phylogenetischer Baum; computational molecular biology; algorithm; multiple alignment; evolutionary tree; phylogenetic tree; generalized tree alignment problem

Abstract
Betrachtet man die Evolution biologischer Sequenzen, konzentriert man sich häufig auf einen von zwei Aspekten: deren multiples Alignment, das die Buchstaben verschiedener Sequenzen miteinander in Beziehung setzt, oder den evolutionären Baum, der die Abstammungsgeschichte der vollständigen Sequenzen beschreibt. In der Praxis müssen Alignment und Baum meist beide aus den Sequenzen selbst rekonstruiert werden, und beide Aspekte sind eng miteinander korreliert. Deshalb bietet sich die gleichzeitige Berechnung von Alignment und Baum an. Das entsprechende Optimierungsproblem stellt allerdings in theoretischer und in praktischer Hinsicht ein schwieriges Problem dar. Mit dieser Arbeit wird der erste Ansatz vorgestellt, multiple Alignments und evolutionäre Bäume gleichzeitig und für reale Probleminstanzen zu lösen. Er ist motiviert durch eine Analogie zum Steiner-Problem aus der Informatik einerseits, und den in der praktischen Bioinformatik erfolgreichen iterativen Alignmentverfahren andererseits. Dabei vermeidet die neue Datenstruktur des gewichteten Sequenzgraphen typische Nachteile iterativer Alignmentverfahren. Neben dem Verfahren selbst werden auch die im Zuge dieser Arbeit entstandene Implementierung, sowie Experimente auf simulierten und realen Daten besprochen.

 

In understanding the evolution of biological sequences, it is common practice to focus at one of two aspects: either the multiple alignment of the characters that relates the individual characters of the sequences, or the evolutionary tree that describes the evolutionary history of the complete sequences. Usually, alignment and tree must both be reconstructed from the sequences alone, and both aspects are closely interrelated. It is therefore desirable to simultaneously reconstruct alignment and tree from the given sequences. However, this represents a difficult task in theory and in practice. This study presents the first approach to the simultaneous reconstruction of multiple alignments and evolutionary trees for real data. It is motivated by an analogy to the Steiner problem from computer science and to iterative alignment algorithms, which are successful in practical bioinformatics. The data structure of the weighed sequence graph avoids typical disadvantages of previous iterative algorithms. Besides the new algorithm, we describe implementation and experimental results on simulated and real biological data.

: http://publica.fraunhofer.de/documents/B-73116.html