Minimum triplet covers of binary phylogenetic X-trees

Huber, Katharina T., Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 and Steel, Mike (2017) Minimum triplet covers of binary phylogenetic X-trees. Journal of Mathematical Biology, 75 (6-7). 1827–1840. ISSN 0303-6812

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
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	Pure Connector
Date Deposited:	08 Mar 2017 01:41
Last Modified:	19 Apr 2023 20:31
URI:	https://ueaeprints.uea.ac.uk/id/eprint/62884
DOI:	10.1007/s00285-017-1117-6

Downloads

Actions (login required)

View Item