Open Access

Lina Herbst

• In phylogenetics, evolutionary relationships of different species are represented by phylogenetic trees. In this thesis, we are mainly concerned with the reconstruction of ancestral sequences and the accuracy of this reconstruction given a rooted binary phylogenetic tree. For example, we wish to estimate the DNA sequences of the ancestors given the observed DNA sequences of today living species. In particular, we are interested in reconstructing the DNA sequence of the last common ancestor of all species under consideration. Note that this last common ancestor corresponds to the root of the tree. There exist various methods for the reconstruction of ancestral sequences. A widely used principle for ancestral sequence reconstruction is the principle of parsimony (Maximum Parsimony). This principle means that the simplest explanation it the best. Applied to the reconstruction of ancestral sequences this means that a sequence which requires the fewest evolutionary changes along the tree is reconstructed. Thus, the number of changes is minimized, which explains the name of Maximum Parsimony. Instead of estimating a whole DNA sequence, Maximum Parsimony considers each position in the sequence separately. Thus in the following, each sequence position is regarded separately, and we call a single position in a sequence state. It can happen that the state of the last common ancestor is reconstructed unambiguously, for example as A. On the other hand, Maximum Parsimony might be indecisive between two DNA nucleotides, say for example A and C. In this case, the last common ancestor will be reconstructed as {A,C}. Therefore we consider, after an introduction and some preliminary definitions, the following question in Section 3: how many present-day species need to be in a certain state, for example A, such that the Maximum Parsimony estimate of the last common ancestor is also {A}? The answer of this question depends on the tree topology as well as on the number of different states. In Section 4, we provide a sufficient condition for Maximum Parsimony to recover the ancestral state at the root correctly from the observed states at the leaves. The so-called reconstruction accuracy for the reconstruction of ancestral states is introduced in Section 5. The reconstruction accuracy is the probability that the true root state is indeed reconstructed and always takes two processes into account: on the one hand the approach to reconstruct ancestral states, and on the other hand the way how the states evolve along the edges of the tree. The latter is given by an evolutionary model. In the present thesis, we focus on a simple symmetric model, the Neyman model. The symmetry of the model means for example that a change from A to C is equally likely than a change from C to A. Intuitively, one could expect that the reconstruction accuracy it the highest when all present-day species are taken into account. However, it has long been known that the reconstruction accuracy improves when some taxa are disregarded for the estimation. Therefore, the question if there exits at least a lower bound for the reconstruction accuracy arises, i.e. if it is best to consider all today living species instead of just one for the reconstruction. This is bad news for Maximum Parsimony as a criterion for ancestral state reconstruction, and therefore the question if there exists at least a lower bound for the reconstruction accuracy arises. In Section 5, we start with considering ultrametric trees, which are trees where the expected number of substitutions from the root to each leaf is the same. For such trees, we investigate a lower bound for the reconstruction accuracy, when the number of different states at the leaves of the tree is 3 or 4. Subsequently in Section 6, in order to generalize this result, we introduce a new method for ancestral state reconstruction: the coin-toss method. We obtain new results for the reconstruction accuracy of Maximum Parsimony by relating Maximum Parsimony to the coin-toss method. Some of these results do not require the underlying tree to be ultrametric. Then, in Section 7 we investigate the influence of specific tree topologies on the reconstruction accuracy of Maximum Parsimony. In particular, we consider balanced and imbalanced trees as the balance of a tree may have an influence on the reconstruction accuracy. We end by introducing the Colless index in Section 8, an index which measures the degree of balance a rooted binary tree can have, and analyze its extremal properties.
• Evolutionäre Beziehungen von verschiedenen Spezies werden in der Phylogenetik mit Hilfe von Evolutionsbäumen, sogenannten phylogenetischen Bäumen, veranschaulicht. Die vorliegende Arbeit beschäftigt sich mit der Rekonstruktion von anzestralen Sequenzen in gewurzelten binären phylogenetischen Bäumen und der Genauigkeit dieser Rekonstruktion. Das bedeutet, dass zum Beispiel aus gegebenen DNA-Sequenzen von heute lebenden Spezies die DNA der gemeinsamen Vorfahren rekonstruiert werden soll. Ein besonderes Interesse liegt dabei in der Rekonstruktion der DNA-Sequenz des letzten gemeinsamen Vorfahrens aller betrachteten Spezies, welcher mit der Wurzel des Baums assoziiert wird. Für die Rekonstruktion von anzestralen Sequenzen existieren viele verschiedene Methoden. Eine Möglichkeit, anzestrale Sequenzen zu rekonstruieren, liefert das parsimonische Prinzip (Maximum Parsimony). Dieses Prinzip besagt, dass die einfachste Erklärung die beste ist. Für die Rekonstruktion einer anzestralen Sequenz bedeutet das, dass eine Sequenz rekonstruiert wird, die die wenigsten evolutionären Änderungen, also Mutationen, durchlaufen hat. Die Anzahl an Wechseln in der Sequenz wird also minimiert, was die Namensgebung Maximum Parsimony (maximale Sparsamkeit) erklärt. Anstatt eine ganze DNA-Sequenz zu schätzen, wird bei Maximum Parsimony jede Stelle in der Sequenz einzeln behandelt. Daher betrachten wir die Positionen in einer Sequenz im folgenden einzeln und bezeichnen diese als Zustand. Mittels Maximum Parsimony kann es dann sein, dass der Zustand des letzten gemeinsamen Vorfahren eindeutig geschätzt wird, zum Beispiel als $A$. Andererseits ist es auch möglich, dass keine eindeutige Entscheidung zwischen verschiedenen Zuständen getroffen werden kann. In dem Fall würde Parsimony dann zum Beispiel {A,C} als mögliche Schätzung liefern. Aus diesem Grund wird, nach einer Einführung in die Thematik und einleitenden Definitionen, in Kapitel 3 dieser Arbeit die folgende Frage untersucht: Für einen bestimmten Zustand A, wie viele von den heute lebenden Spezies müssen mindestens diesen Zustand haben, damit Maximum Parsimony zu dem Schluss kommt, dass auch der letzte gemeinsame Vorfahre ein {A} hatte? Die Antwort hängt von der sogenannten Topologie des Evolutionsbaumes und der Anzahl an verschiedenen Zuständen ab. Im Anschluss wird in Kapitel 4 eine hinreichende Bedingung vorgestellt, mit Hilfe derer Maximum Parsimony den anzestralen Zustand der Wurzel richtig von den Zuständen an den Blättern rekonstruiert. Das fünfte Kapitel befasst sich daraufhin mit der sogenannte Rekonstruktionsgenauigkeit, die für die Rekonstruktion von anzestralen Zuständen eingeführt wird. Die Rekonstruktionsgenauigkeit ist die Wahrscheinlichkeit, dass der wahre Wurzelzustand auch wirklich rekonstruiert wird und umfasst immer zwei mathematische Prozesse: einerseits die Methode zur Rekonstruktion von anzestralen Zuständen und andererseits die Art und Weise wie sich die Zustände entlang der Kanten im Baum ändern. Letzteres ist durch ein zugrunde liegenden Evolutionsmodell gegeben. In der vorliegenden Arbeit wird ein einfaches, symmetrisches Modell, das sogenannte Neyman-Modell, betrachtet. Die Symmetrie des Modells bedeutet zum Beispiel, dass ein Wechsel von A nach C gleich wahrscheinlich ist zu einem Wechsel von C nach A. Intuitiv würde man zunächst erwarten, dass die Rekonstruktionsgenauigkeit am größten ist, wenn alle heute lebenden Spezies bei der Berechnung berücksichtigt werden. Allerdings ist schon lange bekannt, dass sich die Rekonstruktionsgenauigkeit verbessern kann, wenn einige heute lebende Spezies für die Berechnung nicht berücksichtigt werden. Daher stellt sich die Frage, ob wenigstens eine untere Schranke für die Rekonstruktionsgenauigkeit existiert, das heißt ob es immer besser ist alle heute lebenden Spezies anstatt nur einer beliebig gewählten heute lebenden Spezies zu betrachten. Dies ist jedoch keine positive Eigenschaft von Maximum Parsimony und es stellt sich daher die Frage, ob wenigstens eine untere Schranke für die Rekonstruktionsgenauigkeit existiert. Anfänglich werden in Kapitel 5 ultrametrische Bäume, also Bäume in denen die erwartete Anzahl an Wechseln von der Wurzel zu jedem Blatt gleich ist, betrachtet. Für diese Bäume wird eine untere Schranke hergeleitet, wenn die Blätter mit drei oder vier verschiedenen Zuständen gelabelt sind. Dieses Ergebnis soll im Anschluss verallgemeinert werden. Hierfür wird in Kapitel 6 eine neue Methode, die sogenannte Münzwurfmethode, für die Rekonstruktion von anzestralen Zuständen eingeführt. Anhand dieser Methode ist es möglich, neue Ergebnisse für die Rekonstruktionsgenauigkeit von Maximum Parsimony herzuleiten. Einige dieser Ergebnisse gelten insbesondere für Bäume, die nicht zwingend ultrametrisch sein müssen. Daraufhin untersucht Kapitel 7 den Einfluss von verschiedenen Baumtopologien auf die Rekonstruktionsgenauigkeit. Insbesondere werden balancierte und unbalancierte Bäume betrachtet, da die Balanciertheit der Bäume gegebenenfalls Einfluss auf die Rekonstruktionsgenauigkeit haben kann. Abschließend wird in Kapitel 8 der Colless Index zur Messung der Balanciertheit von Bäumen eingeführt und dessen extremale Eigenschaften untersucht.