Titelaufnahme

Titel
Phylogenetic trees : selected combinatorial problems / von Peter Regner
VerfasserRegner, Peter
Begutachter / BegutachterinGittenberger, Bernhard
Erschienen2012
UmfangXIV, 141 S. : Ill.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2012
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)phylogenetischer Baum / analytische Kombinatorik / Maximum Parsimony / ungeordneter Baum / Phylogenetik / markierter Baum
Schlagwörter (EN)phylogenetic tree / analytic combinatorics / maximum parsimony / nonplane tree / leaf-labeled tree / phylogenetics
URNurn:nbn:at:at-ubtuw:1-46281 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Phylogenetic trees [2.37 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Phylogenetische Bäume werden im Bereich der Evolutionsbiologie verwendet, um evolutionäre Beziehungen innerhalb einer Gruppe von Arten darzustellen. Ein phylogenetischer Baum entspricht - im Sinne der Graphentheorie - einem gewurzelten Baum, dessen Blätter markiert sind.

Die Blätter korrespondieren mit den betrachteten Arten und die internen Knoten des Baums können als ihre hypothetische Vorfahren gesehen werden.

Die Verfügbarkeit von genetischen Daten seit den 1960er-Jahren hat es ermöglicht, formale Modelle für die Evolution der Arten zu entwickeln und mathematische Methoden anzuwenden, um die evolutionäre Geschichte von Arten zu rekonstruieren.

In Kapitel 1 wird das Forschungsgebiet grob umrissen, einschließlich einiger Themen, die in dieser Arbeit nicht näher ausgeführt werden können. In Kapitel 2 werden alle später verwendeten Begriffe und Objekte formal definiert und grundlegende Konzepte werden vorgestellt. Sowohl der weit verbreitete Maximum-Parsimony-Ansatz ("maximale Sparsamkeit") als auch das symmetrische Nr -Modell werden erläutert.

In Kapitel 3 und Kapitel 4 werden speziellere Problemstellungen behandelt. Kapitel 3 umfasst eine Sammlung verschiedener auf phylogenetische Bäume bezogener Abzählprobleme, die in den vergangenen Jahrzehnten gelöst wurden. Die Anzahl der Bäume in unterschiedlichen Klassen phylogenetischer Bäume wird bestimmt. Ferner werden zwei Fragestellungen mit wahrscheinlichkeitstheoretischem Ansatz diskutiert.

In Kapitel 4 wird Maximum-Parsimony mit dem symmetrischen Nr-Modell verglichen, indem die Rekonstruktion von Merkmalen der Vorfahren untersucht wird. Es werden Resultate von Li et al. und Fischer und Thatte vorgestellt, die die Zuverlässigkeit dieser Rekonstruktion behandeln. Schließlich werden erste Teilresultate zur Verallgemeinerung eines Theorems von Fischer und Thatte vorgestellt, die im Rahmen dieser Arbeit erzielt werden konnten. Insbesondere wurde das Mathematika-Paket Phylgen entwickelt, um Spezialfälle dieses Theorems zu untersuchen.

Zusammenfassung (Englisch)

In evolutionary biology phylogenetic trees are used to represent evolutionary relationships within a group of species. Typically treelike branching diagrams are used. In graph theoretic terminology a phylogenetic tree corresponds to a rooted leaf-labeled tree, i.e. a (finite) simple, connected, acyclic graph, where one vertex is distinguished as root and distinct labels are assigned to the leaves of the tree. The labels refer to the various species under consideration and the internal nodes of the tree represent hypothetic ancestral species. The availability of genetic data in the 1960s made it possible to develop formal models of the evolution of species and to apply mathematical methods to infer the evolutionary history of a group of species. Still, phylogenetics is an ongoing field of research, the existing models and algorithms are improved and new questions arise.

Chapter 1 gives a rough overview of the field of study and mentions some of the topics not covered in this thesis. In Chapter 2 all fundamental objects will be defined and basic concepts used later will be introduced. The well-known maximum parsimony approach is described as well as the symmetric Nr-model. In Chapter 3 and Chapter 4 more specific problems are discussed. Chapter 3 contains a collection of several enumeration problems concerning phylogenetic trees, which were solved by different authors in the last decades. The size of several classes of phylogenetic trees will be determined and two problems concerning random phylogenetic trees will be discussed.

In Chapter 4 maximum parsimony and the symmetric Nr-model will be compared by studying the reconstruction of states of ancestral species.

Results by Li et al. and Fischer and Thatte concerning the accuracy of this reconstruction with the Fitch-Hartigan algorithm are presented.

Finally, initial results (proved within the scope of this thesis) towards generalizing a theorem by Fischer and Thatte are outlined. In particular, the Mathematica package Phylgen was developed to examine special cases of this theorem.