Massey Documents by Type

Permanent URI for this communityhttps://mro.massey.ac.nz/handle/10179/294

Browse

Filters

2001 - 200912010 - 20171

Settings

Subject: search.filters.subject.Trees (Graph theory)

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    The edge slide graph of the n-dimensional cube : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Mathematics at Massey University, Manawatū, New Zealand
    (Massey University, 2017) Al Fran, Howida Adel
    The goal of this thesis is to understand the spanning trees of the n-dimensional cube Qn by understanding their edge slide graph. An edge slide is a move that “slides” an edge of a spanning tree of Qn across a two-dimensional face, and the edge slide graph is the graph on the spanning trees of Qn with an edge between two trees if they are connected by an edge slide. Edge slides are a restricted form of an edge move, in which the edges involved in the move are constrained by the structure of Qn, and the edge slide graph is a subgraph of the tree graph of Qn given by edge moves. The signature of a spanning tree of Qn is the n-tuple (a1; : : : ; an), where ai is the number of edges in the ith direction. The signature of a tree is invariant under edge slides and is therefore constant on connected components. We say that a signature is connected if the trees with that signature lie in a single connected component, and disconnected otherwise. The goal of this research is to determine which signatures are connected. Signatures can be naturally classified as reducible or irreducible, with the reducible signatures being further divided into strictly reducible and quasi-irreducible signatures. We determine necessary and sufficient conditions for (a1; : : : ; an) to be a signature of Qn, and show that strictly reducible signatures are disconnected. We conjecture that strict reducibility is the only obstruction to connectivity, and present substantial partial progress towards an inductive proof of this conjecture. In particular, we reduce the inductive step to the problem of proving under the inductive hypothesis that every irreducible signature has a “splitting signature” for which the upright trees with that signature and splitting signature all lie in the same component. We establish this step for certain classes of signatures, but at present are unable to complete it for all. Hall’s Theorem plays an important role throughout the work, both in characterising the signatures, and in proving the existence of certain trees used in the arguments.
  • Thumbnail Image
    Item
    Evolutionary analyses of large data sets : trees and beyond : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Mathematics at Massey University
    (Massey University, 2001) Holland, Barbara Ruth
    The increasing amount of molecular data available for phylogenetic studies means that larger, often intra-species, data sets are being analysed. Treating such data sets with methods designed for small interspecies data may not be useful. This thesis comprises four projects within the field of phylogenetics that focus on cases where the application of current tree estimation methods is not sufficient to answer the biological questions of interest. A simulation study contrasts the accuracy of several tree estimation methods for a particular class of five-taxon, equal-rate, trees. This study highlights several difficulties with tree estimation, including the fact that some tree topologies produce “misleading" patterns that are incorrectly interpreted; that correction for multiple changes does not always increase accuracy, because of increased variance; and the difficulty of correctly placing outgroup taxa. A mitochondrial DNA data set, containing over 400 modern and ancient Adélie penguin samples, is used to estimate the rate of evolution. Straightforward tree-estimation is unhelpful because the amount of homoplasy in the data makes the construction of a single reliable tree impossible. Instead the data is represented by a network. A method, that extends statistical geometry, assesses whether or not a data set can be well-represented by a tree. The "tree-likeness" of each quartet in the data is evaluated and displayed visually, either for the entire data set or by taxon. This aids in identifying reticulate (or simply noisy) data sets, and also particular taxa that confound tree-like signal. Novel methods are developed that use pairwise dissimilarities between isolates in intra-species microbial data sets, to identify strains that are good representatives of their species or subspecies.