Abstract:
Die Phylogenetik ist die Lehre der Entwicklung des Lebens auf der Erde. Das Auf-
decken alter evolutionärer Beziehungen zwischen lebenden Arten ist von großem
Wert, da sie zu wichtigen Entdeckungen in der Biologie führte, wie beispielsweise
zur Entwicklung neuer Medikamente, zur Nachverfolgung der Dynamik einer globa-
len Pandemie sowie zu Erkenntnissen über den Ursprung der Menschheit. Heutzu-
tage werden phylogenetische Analysen typischerweise mit Hilfe statistischer Modelle
durchgeführt, wobei Sequenzdaten, in der Regel molekulare Sequenzen, als Einga-
bedaten verwendet werden. ... mehrBasierend auf diesen statistischen Modellen wird die
wahrscheinlichste Erklärung für die Eingabedaten berechnet. Das heißt, der (ver-
meintlich) korrekte phylogenetische Baum ist der Baum, der gemäß eines bestimm-
ten Modells der Sequenzentwicklung am wahrscheinlichsten ist.
Die rasche Zunahme verfügbarer Daten in den letzten Jahren ermöglicht wesentlich
kompliziertere phylogenetische Analysen. Paradoxerweise hat diese massive Zunah-
me der für die Analyse verfügbaren Daten nicht in allen Fällen zu einer endgültigen
Schlussfolgerung geführt, d. h. das verwendete Modell ist unsicher bezüglich der
wahrscheinlichsten Schlussfolgerung. Dies kann auf eine Vielzahl von Faktoren zu-
rückzuführen sein, wie beispielsweise hochkomplexe Modelle, Rauschen in einigen
oder allen Daten sowie physikalische Prozesse, die durch das Modell nicht angemes-
sen berücksichtigt werden. Schwierigkeiten aufgrund von Ungewissheit sind weder in
der Phylogenetik noch in der Wissenschaft im Allgemeinen neu, doch die Entwick-
lung komplizierterer Analysemethoden fordert neue Methoden zur Angabe, Analyse
und Integration von Unsicherheiten.
Die vorliegende Arbeit präsentiert drei Beiträge zur Verbesserung der Unsicherheits-
bewertung. Der erste Beitrag betrifft die Bestimmung der Wurzel von ungewurzelten
phylogenetischen Bäumen. Phylogenetische Bäume sind entweder bezüglich der Zeit
orientiert, in diesem Fall nennt man sie verwurzelt, oder sie haben keine Orientie-
rung, in diesem Fall sind sie unverwurzelt. Die meisten Programme zur Bestimmung
phylogenetischer Bäume erzeugen aus rechnerischen Gründen einen ungewurzelten
phylogenetischen Baum. Ich habe das Open-Source-Softwaretool RootDigger entwi-
ckelt, das sowohl einen ungewurzelten phylogenetischen Baum, als auch eine Vertei-
lung der wahrscheinlichen Wurzeln berechnet. Darüber hinaus verfügt RootDigger
über ein Parallelisierungsschema mit verteiltem Speicher, welches auch die Analyse
großer Datensätze erlaubt, wie beispielsweise die Bestimmung eines phylogenetischen
Baumes aus 8736 SARS-CoV-2-Virussequenzen.
Mein zweiter Beitrag in der vorliegenden Arbeit ist das Open-Source-Softwaretool
Phylourny zur Berechnung des wahrscheinlichsten Gewinners eines Knock-out-Turniers.
Der Algorithmus in Phylourny ist angelehnt an den Felsenstein Pruning Algorith-
mus, einen dynamischen Programmierungsalgorithmus zur Berechnung der Wahr-
scheinlichkeit eines phylogenetischen Baums. Die Verwendung dieses Algorithmus
erlaubt eine erhebliche Beschleunigung der Berechnung im Vergleich zu Standard-
Turniersimulationen. Mit dieser beschleunigten Methode untersucht Phylourny auch
den Parameterraum des Modells mit Hilfe einer MCMC-Methode, um Ergebnisse zu
bewerten und zusammenzufassen, die eine ähnliche Wahrscheinlichkeit des Auftre-
tens haben. Diese Ergebnisse weichen oft erheblich vom wahrscheinlichsten Ergebnis
ab. In der vorliegenden Arbeit präsentiere ich die Performanz von Phylourny anhand
zweier realer Fußball- und Basketballturniere.
Der finale Beitrag in dieser Arbeit ist die Neugestaltung und Neuimplementierung
eines bekannten Tools für historische Biogeografie, mit dem sich Rückschlüsse auf
die Verteilung der angestammten Verbreitungsgebiete ziehen lassen. Ein Hauptin-
teresse der Biogeographie besteht in der Bestimmung der Verbreitungsgebiete von
Arten. Die historische Biogeografie befasst sich daher häufig mit der Ableitung des
Verbreitungsgebiets der Vorfahren lebender Arten. Diese Verteilungen des Verbrei-
tungsgebiets der Vorfahren sind ein häufiges Ergebnis von biogeografischen Studien,
die oft mit einem Modell abgeleitet werden, das zahlreiche Ähnlichkeiten mit Mo-
dellen der Sequenzevolution aufweist. Meine neue Version, Lagrange-NG, berechnet
die Ergebnisse bis zu 50 Mal schneller als die vorherige Version und bis zu zwei Grö-
ßenordnungen schneller als das beliebte analoge Tool BioGeoBEARS. Darüber hinaus
habe ich eine neue Abstandsmetrik entwickelt, die es erlaubt Ergebnisse alternativer
Tools und Algorithmen zu vergleichen.
Abstract (englisch):
Phylogenetics is the study of the evolution of life on earth. Uncovering the ancient
evolutionary relationships between living species is valuable, as it has led to impor-
tant discoveries in biology, such as new drug formulations, tracking the dynamics
of a global pandemic and insights into the origin of humanity. Nowadays, a typical
phylogenetic analysis will be performed using statistical models which use as their
input sequence data, generally molecular sequences, which are then used to find the
most likely explanation of the data. That is, the (putatively) correct phylogenetic
... mehr
tree is the tree which is the most likely under some particular model of sequence
evolution.
In recent years, the ability to perform substantially more complicated phylogenetic
analysis has been unlocked by the rapid increase in available data. Somewhat para-
doxically, this massive increase of data available for analysis has not in all cases made
it possible to arrive at a definitive conclusion, that is the model used is uncertain
about the most likely conclusion. This can be due to a plethora of factors, including
highly complex models, noise in some or all of the data, or physical processes which
are not adequately accounted for by the model. Difficulties from uncertainty are not
new to phylogenetics or to science in general, however the advent of more compli-
cated analysis has fostered to the need for new methods of reporting, analyzing, and
integrating uncertainty.
This thesis presents three contributions to improve uncertainty assessment. The first
contribution concerns rooting previously unrooted phylogenetic trees. Phylogenetic
trees are either oriented with respect to time, in which case they are called rooted,
or they lack an orientation, in which case they are unrooted. For computational
reasons, most tool which infer phylogenetic trees produce an unrooted phylogenetic
tree. I developed the open source software tool RootDigger, which can both root an
unrooted phylogenetic tree, or compute a distribution of likely roots. In addition,
RootDigger is engineered with a distributed memory parallelization scheme, which
allows it analyze large datasets, such as a tree built from 8736 SARS-CoV-2 virus
sequences.
My second contribution in this thesis is the open source software tool Phylourny,
which computes the most probable winner of a knock-out tournament. Phylourny
uses an algorithm inspired by the Felsenstein Pruning Algorithm, a dynamic pro-
gramming algorithm to compute the likelihood of a phylogenetic tree, to substan-
tially accelerate the computation of results when compared to using standard tour-
nament simulations. Using this accelerated method, Phylourny also explores the
parameter space of the model via an MCMC method to asses and summarize the
outcomes which have similar likelihood of occurring. These outcomes often diverge
substantially from than the most likely outcome. I present the performance of Phy-
lourny using two real football and basketball tournaments.
My final contribution in this thesis is the redesign and reimplementation of a popular
historical biogeography tool to infer ancestral range distributions. A primary interest
in biogeography is to determine the range of species (i.e., where a species can be
found). Naturally, historical biogeography is therefore often concerned with inferring
the range of ancestral species for a set of living species. These ancestral range
distributions are a common result of biogeography studies, which are often inferred
using a model that exhibits numerous similarities to models of sequence evolution.
My new version, Lagrange-NG, computes results up to 50 times faster than the old
version, and up to 2 orders of magnitude faster than the popular analogous tool
BioGeoBEARS. In addition, I also develop a novel distance metric which allows for
the comparison of results from alternative tools and algorithms.
