Options
1998
Doctoral Thesis
Titel
A new algorithmic approach to the construction of multiple alignments and evolutionary trees
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.
ThesisNote
Zugl.: Bonn, Univ., Diss., 1998