Abstract:
Das Konzept der Evolution ist in der modernen Biologie von zentraler Bedeutung.
Deswegen liefert die Phylogenetik, die Lehre über die Verwandschaften und Abstam-
mung von Organismen bzw. Spezies, entscheidende Hinweise zur Entschlüsselung
einer Vielzahl biologischer Prozesse. Phylogenetische Stammbäume sind einerseits
für die Grundlagenforschung wichtig, da sie in Studien über die Diversifizierung und
Umweltanpassung einzelner Organismengruppen (z.B. Insekten oder Vögel) bis hin
zu der großen Herausforderung, die Entstehung und Entwicklung aller Lebensfor-
men in einem umfassenden evolutionären Baum darzustellen (der sog. ... mehrTree of Life)
Anwendung finden. Andererseits werden phylogenetische Methoden auch in prax-
isnahen Anwendungen eingesetzt, um beispielsweise die Verbreitungsdynamik von
HIV-Infektionen oder, die Heterogenität der Krebszellen eines Tumors, zu verstehen.
Den aktuellen Stand der Technik in der Stammbaumrekonstruktion stellen Meth-
oden Maximum Likelihood (ML) und Bayes’sche Inferenz (BI) dar, welche auf der
Analyse molekularer Sequenzendaten (DNA und Proteine) anhand probabilistis-
cher Evolutionsmodelle basieren. Diese Methoden weisen eine hohe Laufzeitkom-
plexität auf (N P -schwer), welche die Entwicklung effizienter Heuristiken unabding-
bar macht. Hinzu kommt, dass die Berechnung der Zielfunktion (sog. Phylogenetic
Likelihood Function, PLF) neben einem hohen Speicherverbrauch auch eine Vielzahl
an Gleitkommaarithmetik-Operationen erfordert und somit extrem rechenaufwendig
ist.
Die neuesten Entwicklungen im Bereich der DNA-Sequenzierung (Next Gener-
ation Sequencing, NGS) steigern kontinuierlich den Durchsatz und senken zugleich
die Sequenzierungskosten um ein Vielfaches. Für die Phylogenetik hat dies zur
Folge, dass die Dimensionen der zu analysierenden Datensätze alle 2–3 Jahre, um
eine Grössenordnung zunhemen. War es bisher üblich, einige Dutzend bis Hun-
derte Spezies anhand einzelner bzw. weniger Gene zu analysieren (Sequenzlänge:
1–10 Kilobasen), stellen derzeit Studien mit Tausenden Sequenzen oder Genen keine
Seltenheit mehr dar. In den nächsten 1–2 Jahren ist zu erwarten, dass die Anal-
ysen Tausender bis Zehntausender vollständiger Genome bzw. Transkriptome (Se-
quenzlänge: 1–100 Megabasen und mehr) anstehen. Um diesen Aufgaben gewachsen
zu sein, müssen die bestehenden Methoden weiterentwickelt und optimiert werden,
um vor allem Höchstleistungsrechner sowie neue Hardware-Architekturen optimal
nutzen zu können.
Außerdem führt die sich beschleunigende Speicherung von Sequenzen in öffentli-
chen Datenbanken wie NCBI GenBank (und ihren Derivaten) dazu, dass eine hohe
Qualität der Sequenzannotierungen (z. B. Organismus- bzw. Speziesname, tax-
onomische Klassifikation, Name eines Gens usw.) nicht zwangsläufig gewährleistet
ist. Das hängt unter anderem auch damit zusammen, dass eine zeitnahe Korrektur
durch entsprechende Experten nicht mehr möglich ist, solange ihnen keine adäquaten
Software-Tools zur Verfügung stehen.
In dieser Doktroarbeit leisten wir mehrere Beiträge zur Bewältigung der oben
genannten Herausforderungen.
Erstens haben wir ExaML, eine dedizierte Software zur ML-basierten Stamm-
baumrekonstruktion für Höchstleistungsrechner, auf den Intel Xeon Phi Hardware-
beschleuniger portiert. Der Xeon Phi bietet im Vergleich zu klassischen x86 CPUs
eine höhere Rechenleistung, die allerdings nur anhand architekturspezifischer Op-
timierungen vollständig genutzt werden kann. Aus diesem Grund haben wir zum
einen die PLF-Berechnung für die 512-bit-Vektoreinheit des Xeon Phi umstrukturi-
ert und optimiert. Zum anderen haben wir die in ExaML bereits vorhandene reine
MPI-Parallelisierung durch eine hybride MPI/OpenMP-Lösung ersetzt. Diese hy-
bride Lösung weist eine wesentlich bessere Skalierbarkeit für eine hohe Zahl von
Kernen bzw. Threads innerhalb eines Rechenknotens auf (>100 HW-Threads für
Xeon Phi).
Des Weiteren haben wir eine neue Software zur ML-Baumrekonstruktion na-
mens RAxML-NG entwickelt. Diese implementiert, bis auf kleinere Anpassungen, zwar
denselben Suchalgorithmus wie das weit verbreitete Programm RAxML, bietet aber
gegenüber RAxML mehrere Vorteile: (a) dank den sorgfältigen Optimierungen der
PLF-Berechnung ist es gelungen, die Laufzeiten um den Faktor 2 bis 3 zu reduzieren
(b) die Skalierbarkeit auf extrem großen Eingabedatensätzen wurde verbessert, in-
dem ineffiziente topologische Operationen eliminiert bzw. optimiert wurden, (c) die
bisher nur in ExaML verfügbaren, für große Datensätze relevanten Funktionen wie
Checkpointing sowie ein dedizierter Datenverteilungsalgorithmus wurden nachimple-
mentiert (d) dem Benutzer steht eine größere Auswahl an statistischen DNA-Evo-
lutionsmodellen zur Verfügung, die zudem flexibler kombiniert und parametrisiert
werden können (e) die Weiterentwicklung der Software wird aufgrund der modularen
Architektur wesentlich erleichtert (die Funktionen zur PLF-Berechnung wurden in
eine gesonderte Bibliothek ausgeglidert).
Als nächstes haben wir untersucht, wie sich Sequenzierungsfehler auf die Genau-
igkeit phylogenetischr Stammbaumrekonstruktionen auswirken. Wir modifizieren
den RAxML bzw. RAxML-NG Code dahingehend, dass sowohl die explizite Angabe von
Fehlerwahrscheinlichkeiten als auch die automatische Schätzung von Fehlerraten
mittels der ML-Methode möglich ist. Unsere Simulationen zeigen: (a) Wenn die
Fehler gleichverteilt sind, kann die Fehlerrate direkt aus den Sequenzdaten geschätzt
werden. (b) Ab einer Fehlerrate von ca. 1% liefert die Baumrekonstruktion unter
Berücksichtigung des Fehlermodells genauere Ergebnisse als die klassische Methode,
welche die Eingabe als fehlerfrei annimmt.
Ein weiterer Beitrag im Rahmen dieser Arbeit ist die Software-Pipeline SATIVA
zur rechnergestützten Identifizierung und Korrektur fehlerhafter taxonomischer An-
notierungen in großen Sequenzendatenbanken. Der Algorithmus funktioniert wie
folgt: für jede Sequenz wird die Platzierung im Stammbaum mit dem höchst-
möglichen Likelihood-Wert ermittelt und anschließend geprüft, ob diese mit der
vorgegeben taxonomischen Klassifikation übereinstimmt. Ist dies nicht der Fall,
wird also eine Sequenz beispielsweise innerhalb einer anderen Gattung platziert,
wird die Sequenz als falsch annotiert gemeldet, und es wird eine entsprechende
Umklassifizierung vorgeschlagen. Auf simulierten Datensätzen mit zufällig eingefüg-
ten Fehlern, erreichte unsere Pipeline eine hohe Identifikationsquote (>90%) sowie
Genauigkeit (>95%). Zur Evaluierung anhand empirischer Daten, haben wir vier
öffentliche rRNA Datenbanken untersucht, welche zur Klassifizierung von Bakterien
häufig als Referenz benutzt werden. Dabei haben wir je nach Datenbank 0.2% bis
2.5% aller Sequenzen als potenzielle Fehlannotierungen identifiziert.
Abstract (englisch):
Evolution is a central paradigm of current biology, and thus phylogenetics, the study of
evolutionary relationships between organisms, is essential for understanding biological pro-
cesses. Phylogenetic trees are as important for fundamental research (e.g, reconstructing
the Tree of Life) as for numerous practical applications (e.g., studying HIV transmis-
sion dynamics or tumor heterogeneity in cancer). State-of-the-art phylogenetic inference
methods, such as Maximum Likelihood (ML) and Bayesian Inference (BI), rely on prob-
abilistic models of molecular sequence evolution. ... mehrThis makes them computationally ex-
pensive both, in theory (N P -hardness), and in practice (extensive use of floating-point
arithmetics and high memory requirements). At the same time, recent advances in DNA
sequencing technology have dramatically increased the data generation pace, creating a
demand for reconstructing ever larger trees from ever longer sequences (whole genomes
or transcriptomes). Additionally, the fast accumulation of sequences in public databases
has led to concerns about metadata quality, as human curation often lags behind the data
tsunami. In this thesis, we make several contributions which address different aspects of
the aforementioned challenges.
First, we adapt ExaML, an MPI-parallelized ML inference code for genome-scale align-
ments, to run efficiently on Intel Xeon Phi hardware accelerators. To this end, we opti-
mize likelihood computations for the 512-bit wide vector unit, and implement a hybrid
MPI/OpenMP parallelization approach which can better handle the high level of intra-
node parallelism that characterizes the Xeon Phi (>100 threads/card).
Then, we introduce RAxML-NG, a novel, fast, scalable, and flexible ML tree inference
tool. It implements roughly the same basic tree search heuristic as the existing and
widely-used program RAxML, but offers improvements in accuracy, speed, scalability, and
user-friendliness. Moreover, RAxML-NG is substantially more flexible with respect to the
evolutionary model that can be specified and used. Finally, the code is easier to maintain
and extend because of its modular design.
Further, we explore the effects of sequencing error and sequence uncertainty metrics
on phylogenetic inference. In simulation, we show that: (a) an uniform error rate can be
reliably estimated from the molecular input data, and (b) using an explicit error model
improves the accuracy of phylogenetic inference from noisy data.
Finally, we developed a software pipeline for semi-automatic identification and correc-
tion of taxonomically mislabeled sequences based on phylogenetic inference and phyloge-
netic placement approaches. We evaluate our approach on simulated datasets where it
attains high accuracy (>95% precision and >90% recall). Then, we apply it to re-validate
the taxonomic labels in four widely-used reference rRNA databases. We find 0.2% to 2.5%
potentially mislabeled sequences in those databases.
