Sampling Discrete Combinatorial Spaces in Phylogenetics

Abstract

Phylogenetics is the study and identification of evolutionary structure, and phylogeneticists often present evolutionary inferences as leaf-labelled trees. We investigate the combinatorial nature of phylogenetic tree reconstruction as an applied problem of combinatorics.

This thesis strives to improve techniques for tree reconstruction and evolutionary inference by characterizing the fitness landscape of tree search. Introduced are some of the challenges faced when performing heuristic searches of the phylogenetic fitness landscape. Also introduced are strategies for restricting that search. I discuss techniques to sample the space, rather than merely find an optimum, including an applied metaheuristic of Ant Colony Optimization. This metaheuristic was found to sparsely sample a set of phylogenetic landscapes across their diameters. Finally, I present implementation details and discussion regarding a software framework that was developed to facilitate heuristic searches and exploration of the space. This framework was developed with a number of existing tools and creates new ones.