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]
Preview
PDF (art10.1007--00285-017-1117-6) - Published Version
Available under License Creative Commons Attribution.

Download (541kB) | 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: 22 Apr 2020 02:55
URI: https://ueaeprints.uea.ac.uk/id/eprint/62884
DOI: 10.1007/s00285-017-1117-6

Actions (login required)

View Item View Item