Cargando…
Minimum triplet covers of binary phylogenetic X-trees
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 give...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer Berlin Heidelberg
2017
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5641367/ https://www.ncbi.nlm.nih.gov/pubmed/28608005 http://dx.doi.org/10.1007/s00285-017-1117-6 |
_version_ | 1783271211324669952 |
---|---|
author | Huber, K. T. Moulton, V. Steel, M. |
author_facet | Huber, K. T. Moulton, V. Steel, M. |
author_sort | Huber, K. T. |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-5641367 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2017 |
publisher | Springer Berlin Heidelberg |
record_format | MEDLINE/PubMed |
spelling | pubmed-56413672017-10-30 Minimum triplet covers of binary phylogenetic X-trees Huber, K. T. Moulton, V. Steel, M. J Math Biol Article 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. Springer Berlin Heidelberg 2017-06-12 2017 /pmc/articles/PMC5641367/ /pubmed/28608005 http://dx.doi.org/10.1007/s00285-017-1117-6 Text en © The Author(s) 2017 Open AccessThis 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. |
spellingShingle | Article Huber, K. T. Moulton, V. Steel, M. Minimum triplet covers of binary phylogenetic X-trees |
title | Minimum triplet covers of binary phylogenetic X-trees |
title_full | Minimum triplet covers of binary phylogenetic X-trees |
title_fullStr | Minimum triplet covers of binary phylogenetic X-trees |
title_full_unstemmed | Minimum triplet covers of binary phylogenetic X-trees |
title_short | Minimum triplet covers of binary phylogenetic X-trees |
title_sort | minimum triplet covers of binary phylogenetic x-trees |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5641367/ https://www.ncbi.nlm.nih.gov/pubmed/28608005 http://dx.doi.org/10.1007/s00285-017-1117-6 |
work_keys_str_mv | AT huberkt minimumtripletcoversofbinaryphylogeneticxtrees AT moultonv minimumtripletcoversofbinaryphylogeneticxtrees AT steelm minimumtripletcoversofbinaryphylogeneticxtrees |