Trees and terraces. (2016)
AuthorsMark, Sarah Jayneshow all
The reconstruction of evolutionary trees from data sets on overlapping sets of species is a central problem in phylogenetics. Provided that the tree reconstructed for each subset of species is rooted and that these trees fit together consistently, the space of all parent trees that `display' these trees was recently shown to satisfy the following property: there exists a path from any one parent tree to any other parent tree by a sequence of local rearrangements (nearest neighbour interchanges) so that each intermediate tree also lies in this same tree space. However, the proof of this result uses a non-constructive argument. In this thesis we describe a specific, polynomial-time procedure for navigating from any given parent tree to another while remaining in this tree space. We then investigate a related problem, the conditions under which there is only one parent tree. These results are of particular relevance to the recent study of `phylogenetic terraces'.