Tree structure in phylogenetic networks
Degree GrantorUniversity of Canterbury
Degree NameDoctor of Philosophy
Phylogenetic trees are widely used to express and explore evolutionary relationships. In recent times, the observation of evolutionary processes that cannot be expressed by individual phylogenetic trees has prompted interest in the study of phylogenetic networks. Phylogenetic networks generalise phylogenetic trees by allowing non-treelike events to be represented. A particular consequence of this is that a phylogenetic network may be understood to simultaneously express the relationships of a number of different phylogenetic trees. These phylogenetic trees are then said to be embedded in the network.
In this thesis, the connections between various classes of phylogenetic networks and their corresponding sets of embedded phylogenetic trees are explored. Among others, the following questions are expanded on and answered.
1. For a given set of trees does there exist a network that embeds each tree? In the case of level-1 networks a polynomial time algorithm is given that outputs, up-to a particular topological ambiguity, the unique level-1 network with minimum reticulations that displays a given set of trees or identities that no such network exists.
2. From a given set of trees embedded in a network can the network be reconstructed? It is proven that a normal network can be reconstructed from a subset of the trees it displays that grows linearly with respect to the number of leaves in the network.
3. For a given network how many embedded trees are required to use every vertex and every edge of the network? It is proven that the class of stack-free network is precisely the class of networks for which only two embedded trees are required to use every vertex and every edge of the network.
4. For a given network and tree does the network embed the tree? In the case of sibling-free networks a polynomial time algorithm is given that outputs, for a given network and tree, whether or not the network embeds the tree.