Orienting phylogenetic networks

Abstract

This thesis provides you with basic information on graph theory as well as phylogenetic networks, it studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks, based on the manuscript 'Rooting for phylogenetic networks' . Undirected phylogenetic networks can be oriented to become a directed network. In this manuscript the authors come up with multiple algorithms for orienting phylogenetic networks meeting different characteristics. A network is built up of reticulation vertices (where lineages merge) and tree vertices (where lineages separate). A network can be binary, meaning every node in the body of the network has a degree of three or a network can be non-binary, meaning there are no restrictions to the amount of edges a vertex can have.
When a network is binary, an algorithm is described that given the location of the root as well as a set of reticulation points, is used to find an orientation (Algorithm 1). If a network is non-binary, an algorithm is described that given a location of the root as well as the indegree of each vertex, is used to find an orientation (Algorithm 2 ). Once an orientation is found for a certain undirected network this orientation can be checked to see whether it meets the characteristics of a certain network class. Three network classes are considered. First of all an orientation can be tree-child, meaning that every non-leaf vertex has a child that is not a reticulation. Secondly an orientation can be stack-free, meaning that no reticulation has a child which is a reticulation. And last, an orientation can be valid, meaning that it is stack-free and deleting a single reticulation edge and suppressing its endpoints does not give parallel arcs. When we either did not find an orientation in the class we wanted or want to know all the orientations for a certain network in a certain class, we use Algorithm 3 or 4. The location of the root and the set of reticulation points were necessary input for Algorithm 1; whereas Algorithms 3 and 4 do not require this information. Algorithm 3 returns you the first found orientation in the class you wanted and Algorithm 4 returns you a collection of all orientations in the class. All orientations found by the program are returned in an output format that can be read by a network visualisation website.