Computing Measures for Tree-Basedness of Phylogenetic Networks

Phylogenetic networks are a type of directed acyclic graph used to represent evolutionary relationships that contain events such as hybridization or horizontal gene transfer. When a network lacks such events it is a phylogenetic tree. Some phylogenetic networks that are not trees can however be represented as a tree with additional linking arcs, e.g. representing transfer of genetic materials. We have implemented an algorithm that can be used to determine whether a given network is tree-based or not. Moreover if the network is not tree-based, the algorithm shows how it can be made tree-based by adding a minimum number of additional leaves, representing possible extinct or un-sampled species. We also describe the theory behind the algorithm and apply it to several synthetic as well as biological datasets.