Building trees, hunting for trees, and comparing trees : theory and methods in phylogenetic analysis

Abstract

Phylogenetics is the study and identification of evolutionary patterns and structures in nature; this thesis explores the mathematics of these structures. The basic objects of study are the leaf labelled tree and its substructures: quartets, splits, clusters and rooted triples, among others. We present fundamental theorems and characterisations, as well as efficient algorithms for a range of phylogenetic problems. It is often possible to deduce phylogenetic information not in the original data. We characterise an intriguing system of inference 'rules' that arise in this way, and prove that there exist rules of every order that cannot be reduced to lower order rules. We describe a polynomial time algorithm that extracts maximum weight bounded degree trees from a given binary character set. The algorithm enables compatibility analysis of large data sets, in this case the daunting "Out of Africa" human mtDNA sequences. Other applications include consensus, quartet puzzling and split decomposition. We accelerate the Minimum Evolution method with an optimal O(n²) time algorithm for calculating OLS edge lengths and fast algorithms for WLS and GLS edge lengths. We show how a Minimum Evolution tree can be efficiently extracted from a collection of splits. Consensus methods are surveyed, characterised and classified. A new intuitive consensus method for edge weighted trees is introduced, together with an efficient algorithm for constructing it. We present an algorithm for the Maximum Agreement Subtree problem that is based on rooted triples and is much simpler than existing algorithms. We also provide algorithms for obtaining agreement subtrees with the largest number of edges, rooted triples or quartets. Issues of complexity are discussed throughout the thesis, with several new NP-completeness results and a list of standard NP-complete phylogenetic problems.