Models, Optimizations, and Tools for Large-Scale Phylogenetic Inference, Handling Sequence Uncertainty,  and Taxonomic Validation
Creators: name: Kozlov, Oleksii
Publisher: name: Karlsruhe
Year: 2018
Subjects: phylogenetics
maximum-likelihood
taxonomic validation
high performance computing
Intel Xeon Phi

description: 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. Tree 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 (&gt;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 (&gt;90%) sowie
Genauigkeit (&gt;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.