Phylogenetic Networks that Display a Tree Twice
Degree GrantorUniversity of Canterbury
Degree NameDoctor of Philosophy
In the study of phylogenetics, which is the study of how forms of life evolve and relate to each other, there is great scope for mathematics to get involved. One such study of phylogenetics that currently employs mathematics is the study of phylogenetic networks and phylogenetic trees. Phylogenetic networks and trees can be used to represent how life evolved with the former having the ability to represent biological processes such as hybridization, horizontal gene transfer, and gene recombination. In terms of mathematics, one sees phylogenetic networks and trees as directed graphs. A phylogenetic network N displays a rooted phylogenetic tree T if all of the ancestral history inferred by T is also inferred by N. The main result of this thesis is a quartic-time, in terms of the number of leaves in the network, algorithm that decides whether or not a given phylogenetic network displays a tree twice. As a consequence of the work leading to the main result, a class of phylogenetic networks is discovered such that there is a quadratic-time, in terms of the number of leaves in the network, algorithm for counting the number of distinct trees displayed by a given network in the class. These results are interesting because it has been shown that in general counting the number of trees displayed by a given phylogenetic network is #P-complete. Thus the main result of this thesis opens the door to insights regarding a computationally hard problem.