Phylogenetic Networks that Display a Tree Twice

Type of content
Theses / Dissertations
Publisher's DOI/URI
Thesis discipline
Mathematics
Degree name
Doctor of Philosophy
Publisher
University of Canterbury
Journal Title
Journal ISSN
Volume Title
Language
English
Date
2016
Authors
Cordue, Paul Joseph
Abstract

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.

Description
Citation
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Rights
All Right Reserved