Spaces of phylogenetic networks

Abstract

Rooted phylogenetic trees and networks are rooted, acyclic, leaf-labelled graphs that are used to model the inferred evolutionary history of taxa; for example species. While a phylogenetic tree models only bifurcating events, a phylogenetic network can also model reticulation events like hybridisation, recombination, and horizontal gene transfer. A rearrangement operation transforms one phylogenetic tree into another via a local graph-based change. For example, the subtree prune and regraft (SPR) operation prunes(cuts) a subtree of a phylogenetic tree and then regrafts (attaches) it to an edge of the remaining tree, resulting in another phylogenetic tree. Another operation is nearest neighbour interchange (NNI), which is a special case of SPR where the pruned edge has to be regrafted closely to where it was pruned. The set of all phylogenetic trees for a fixed set of taxa together with a rearrangement operations forms a graph where the vertices are the trees and two trees are adjacent when one can be transformed into the other by applying the rearrangement operation exactly once. In such a space, the distance of two trees is given by the minimum number of operations needed to transform one into the other. The SPR-distance of two trees can be characterised with a maximum agreement forest; a forest with a minimum number of components that covers both trees. In this thesis we study spaces of phylogenetic networks under generalisations of NNI and SPR, in particular, the subnet prune and regraft (SNPR) operation and the here introduced prune and regraft (PR) operation. First, we consider connectedness and diameters of spaces of different classes of phylogenetic networks. We then look at the size of the neighbourhood of a phylogenetic network. Furthermore, we investigate properties of shortest paths under SNPR and PR. This includes several bounds on the distances of two networks. Finally, we introduce maximum agreement graphs as a generalisation of maximum agreement forests for phylogenetic networks. We show that maximum agreement graphs induce a metric – the agreement distance – and study its relation to the SNPR-and PR-distance.