Minimum triplet covers of binary phylogenetic X-trees

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
6 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1827–1840
Number of pages14
JournalJournal of Mathematical Biology
Volume75
Issue number6-7
Early online date12 Jun 2017
DOIs
Publication statusPublished - Dec 2017

Keywords

  • trees
  • median vertex
  • 2-trees
  • shellability
  • reconstruction

Cite this