Triplet Matroids and Closure in Phylogenetics
| dc.contributor.author | Levy, Maayan | |
| dc.date.accessioned | 2024-10-22T22:04:48Z | |
| dc.date.available | 2024-10-22T22:04:48Z | |
| dc.date.issued | 2024 | |
| dc.description.abstract | This thesis examines a meeting point of two combinatorial structures: matroids and phylogenetic trees. Matroids are a tool for generalising the notion of independence, with areas of application including graph theory, linear algebra, and coding theory among others. Meanwhile, phylogenetic trees are representations of ancestral relationships, with common applications in computational biology including hypothesising evolutionary histories, modelling disease transmission, and classifying species. These trees can be broken down into sets of rooted triples, which serve as a list of lineage constraints that encode a phylogenetic tree. Rooted triples are useful for determining tree compatibility and constructing supertrees from overlapping datasets. In this thesis, we investigate a class of matroids arising from sets of rooted triples that minimally encode trees, which we term triplet matroids. The matroid structure is useful for revealing which rooted triples in a set are essential and which are redundant. This ties in closely with the notion of closure, which concerns the lineage constraints logically implied by a set of rooted triples or phylogenetic trees. Our main result is that all triplet matroids are graphic. We provide a polynomial-time algorithm for constructing a graphic representation of a given triplet matroid, which serves as a helpful visualisation of the closure and dependencies of a set of rooted triples. In addition to this, we explore the unusual behaviour of the class of triplet matroids under deletion and contraction. We also demonstrate the effects of modifying a phylogenetic tree on its associated triplet matroid. Finally, we characterise the class of graphs that arise as graphic representations of triplet matroids. An additional chapter departs from triplet matroids, focusing instead on network greedoids. Greedoids and phylogenetic networks are generalisations of matroids and phylogetic trees respectively. We prove that a greedoid structure arises from exactly the networks that are tree-child, thus providing an additional characterisation of the class of tree-child networks. For future investigation, we introduce the greedoid polynomial and pose a question about its ability to distinguish network greedoids. | |
| dc.identifier.uri | https://hdl.handle.net/10092/107704 | |
| dc.language | English | |
| dc.language.iso | en | |
| dc.rights | All Right Reserved | |
| dc.rights.uri | https://canterbury.libguides.com/rights/theses | |
| dc.title | Triplet Matroids and Closure in Phylogenetics | |
| dc.type | Theses / Dissertations | |
| thesis.degree.discipline | Mathematics | |
| thesis.degree.grantor | University of Canterbury | |
| thesis.degree.level | Masters | |
| thesis.degree.name | Master of Mathematical Sciences | |
| uc.bibnumber | in1384704 | |
| uc.college | Faculty of Engineering |