Characterising tree-based phylogenetic networks

Commonly, the evolutionary history of a set of taxa is described by a phylogenetic tree. However, in certain cases, evolution can best be described by a phylogenetic network. In previous research, the term tree-based was introduced for a phylogenetic network, meaning that it can be drawn as a phylogenetic tree with additional horizontal arcs. In particular, an algorithm was given to determine whether a binary network is tree-based or not. Here we give a simple graph-theoretic classification of all tree-based and non-tree-based binary phylogenetic networks. In addition, we give an upper bound on how many leaves need to be added to make any binary network tree-based. We also give an upper bound for the number of base trees that a tree-based binary phylogenetic network contains. Finally, since there has not been done any previous research on the tree-basedness of non-binary phylogenetic networks, some theorems of the binary case are studied and checked whether they also apply in the non-binary case. We show that some of these theorems apply in the non-binary case and some do not. In particular, we give a classification for non-binary phylogenetic networks that are tree-based.