Tools
Tools
Grunewald, Stefan, Huber, Katharina T., Moulton, Vincent 
ORCID: https://orcid.org/0000-0001-9371-6435 and Steel, Mike
(2018)
Combinatorial properties of triplet covers for binary trees.
Advances in Applied Mathematics, 99.
pp. 59-82.
ISSN 0196-8858
Preview |
PDF (Accepted manuscript)
- Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (557kB) | Preview |
Abstract
It is a classical result that an unrooted tree $T$ having positive real-valued edge lengths and no vertices of degree two can be reconstructed from the induced distance between each pair of leaves. Moreover, if each non-leaf vertex of $T$ has degree 3 then the number of distance values required is linear in the number of leaves. A canonical candidate for such a set of pairs of leaves in $T$ is the following: for each non-leaf vertex $v$, choose a leaf in each of the three components of $T-v$, group these three leaves into three pairs, and take the union of this set over all choices of $v$. This forms a so-called `triplet cover' for $T$. In the first part of this paper we answer an open question (from 2012) by showing that the induced leaf-to-leaf distances for any triplet cover for $T$ uniquely determine $T$ and its edge lengths. We then investigate the finer combinatorial properties of triplet covers. In particular, we describe the structure of triplet covers that satisfy one or more of the following properties of being minimal, `sparse', and `shellable'.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | phylogenetic tree,triplet cover, tree-distances, hall's theorem,ample patchwork, shellability |
| Faculty \ School: | Faculty of Science > School of Computing Sciences |
| UEA Research Groups: | Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre |
| Related URLs: | |
| Depositing User: | Pure Connector |
| Date Deposited: | 16 Apr 2018 13:30 |
| Last Modified: | 14 Jun 2023 13:21 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/66773 |
| DOI: | 10.1016/j.aam.2018.04.002 |
Downloads
Downloads per month over past year
Actions (login required)
 |
View Item |