Facility Location in the Phylogenetic Tree Space

Phylogenetics is a field of biology trying to describe the evolutionary history of a given set of populations or species. Evolutionary relationships are obtained through statistical models for phylogenetic inference. In this thesis we aim to find the phylogenetic tree that best describes the evolutionary history of the given species, also called the species tree. Unfortunately, when applying phylogenetic inference methods to different genes that the species share, the outcome varies. This results in a set of possible phylogenetic trees, which we use to try to infer the true species tree. This problem of inferring the species tree from the gene trees is modeled in a metric space consisting of all possible phylogenetic trees for a fixed set of species. To solve the problem, we investigate it from a new point of view and interpret it as a facility location problem and adapt known algorithms from this field to our specific setting. In the thesis, three different location problems are discussed. We develop solution algorithms for several interesting special cases of these problems and moreover propose a solution algorithm for the median problem for the general case. The convergence of the algorithm for the median problem is investigated in depth. Furthermore, an implementation of the algorithm has been applied to several random data sets to evaluate its behavior and performance as well as to a real data set consisting of species from the Apicomplexa phylum.