Comparing networks of life: cherry picking the path between orchards

Abstract

Phylogenetic trees have been the traditional model for evolutionary relationships between species, but it has become clear that networks are a better model. Networks add reticulation vertices and edges which can better capture complex evolutionary scenarios such as hybridization and horizontal gene transfer. Network distance, a measure of discrepancy between two networks, is an important problem in the development of the network model as it is often used to validate construction methods. In phylogenetic networks, a cherry describes a structure containing either sibling leaves or leaves whose parents are the endpoints of a reticulation edge. A reduction operation induced on this structure removes the cherry by the deletion of a leaf or a reticulation edge. Cherry reductions have been shown to have algorithmic applications to networks, including determining containment and isomorphism, pointing to sequences of cherry reductions representing some level of similarity between two networks. With this in mind, we define a novel phylogenetic network distance, design an algorithm that solves for it, and show that it is usable for real network applications. We give a number of equal distance formulations we call "cherry distance". We show that it is NP-hard to calculate, even between a tree and network. Because cherry distance is NP-hard, we likely cannot avoid an exponential runtime to calculate it exactly. We do, however, design an FPT algorithm that runs in time exponential only in the combined number of reticulations in the queried networks. This is made possible by the constraint that 'blobs' remain uncomplicated by having no more than one reticulation each. Finally, we show the efficient operation of software that calculates cherry distance. This new package, CherryRed, implements the algorithm previously designed, and includes a new optimization and a fast heuristic. We furthermore use the software to show some interesting behaviours of cherry distance by comparing it to other distances, in particular we show there is a nice correlation between cherry distance and the number of network leaves downstream from a structural disagreement. In all, the impact of this program of research is in furnishing the computational toolkit available to practitioners in comparative genomics.