Minimum triplet covers of binary phylogenetic X-trees

Huber, Katharina T., Moulton, Vincent and Steel, Mike (2017) Minimum triplet covers of binary phylogenetic X-trees. Journal of Mathematical Biology, 75 (6-7). 1827–1840. ISSN 0303-6812

[img] PDF (Accepted manuscript) - Submitted Version
Restricted to Repository staff only until 31 December 2099.

Download (200kB) | Request a copy
    [img]
    Preview
    PDF (art10.1007--00285-017-1117-6) - Published Version
    Available under License Creative Commons Attribution.

    Download (528kB) | Preview

      Abstract

      Trees with labelled leaves and with all other vertices of degree three play an important role in systematic biology and other areas of classification. A classical combinatorial result ensures that such trees can be uniquely reconstructed from the distances between the leaves (when the edges are given any strictly positive lengths). Moreover, a linear number of these pairwise distance values suffices to determine both the tree and its edge lengths. A natural set of pairs of leaves is provided by any `triplet cover' of the tree (based on the fact that each non-leaf vertex is the median vertex of three leaves). In this paper we describe a number of new results concerning triplet covers of minimum size. In particular, we characterize such covers in terms of an associated graph being a 2-tree. Also, we show that minimum triplet covers are `shellable' and thereby provide a set of pairs for which the inter-leaf distance values will uniquely determine the underlying tree and its associated branch lengths.

      Item Type: Article
      Additional Information: Open Access: This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
      Uncontrolled Keywords: trees,median vertex,2-trees,shellability,reconstruction
      Faculty \ School: Faculty of Science > School of Computing Sciences
      Depositing User: Pure Connector
      Date Deposited: 08 Mar 2017 01:41
      Last Modified: 25 Jul 2018 13:24
      URI: https://ueaeprints.uea.ac.uk/id/eprint/62884
      DOI: 10.1007/s00285-017-1117-6

      Actions (login required)

      View Item