FINDING STRUCTURE IN THE PHYLOGENY SEARCH SPACE

Abstract

A phylogenetic tree is a graphical representation of inferred evolutionary relationships between a set of species or taxa. Phylogenetic trees play an important role in diverse research fields, including molecular biology, ecology, and physiology. Inferring the optimal phylogenetic tree using the maximum likelihood optimality criterion (a popular optimality criterion for phylogenies), is an NP-hard problem. Therefore, use of heuristics and optimization algorithms is necessary to solve this problem. Here, I offer some insights into the structure of the phylogeny search space by analysing novel ruggedness measures. I use a variety of nine-taxon and larger datasets as well as Subtree Prune and Regraft (SPR) and Nearest Neighbour Interchange (NNI) tree rearrangements to characterize and capture the ruggedness of the resulting phylogeny search spaces. Finally, inspired by my analysis of the structure of phylogeny search space, I propose two randomized algorithms to find the optimal tree in the phylogeny search space.