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.
back