Cargando…
Recursive algorithms for phylogenetic tree counting
BACKGROUND: In Bayesian phylogenetic inference we are interested in distributions over a space of trees. The number of trees in a tree space is an important characteristic of the space and is useful for specifying prior distributions. When all samples come from the same time point and no prior infor...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2013
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3829674/ https://www.ncbi.nlm.nih.gov/pubmed/24164709 http://dx.doi.org/10.1186/1748-7188-8-26 |
_version_ | 1782291369717399552 |
---|---|
author | Gavryushkina, Alexandra Welch, David Drummond, Alexei J |
author_facet | Gavryushkina, Alexandra Welch, David Drummond, Alexei J |
author_sort | Gavryushkina, Alexandra |
collection | PubMed |
description | BACKGROUND: In Bayesian phylogenetic inference we are interested in distributions over a space of trees. The number of trees in a tree space is an important characteristic of the space and is useful for specifying prior distributions. When all samples come from the same time point and no prior information available on divergence times, the tree counting problem is easy. However, when fossil evidence is used in the inference to constrain the tree or data are sampled serially, new tree spaces arise and counting the number of trees is more difficult. RESULTS: We describe an algorithm that is polynomial in the number of sampled individuals for counting of resolutions of a constraint tree assuming that the number of constraints is fixed. We generalise this algorithm to counting resolutions of a fully ranked constraint tree. We describe a quadratic algorithm for counting the number of possible fully ranked trees on n sampled individuals. We introduce a new type of tree, called a fully ranked tree with sampled ancestors, and describe a cubic time algorithm for counting the number of such trees on n sampled individuals. CONCLUSIONS: These algorithms should be employed for Bayesian Markov chain Monte Carlo inference when fossil data are included or data are serially sampled. |
format | Online Article Text |
id | pubmed-3829674 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2013 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-38296742013-11-20 Recursive algorithms for phylogenetic tree counting Gavryushkina, Alexandra Welch, David Drummond, Alexei J Algorithms Mol Biol Research BACKGROUND: In Bayesian phylogenetic inference we are interested in distributions over a space of trees. The number of trees in a tree space is an important characteristic of the space and is useful for specifying prior distributions. When all samples come from the same time point and no prior information available on divergence times, the tree counting problem is easy. However, when fossil evidence is used in the inference to constrain the tree or data are sampled serially, new tree spaces arise and counting the number of trees is more difficult. RESULTS: We describe an algorithm that is polynomial in the number of sampled individuals for counting of resolutions of a constraint tree assuming that the number of constraints is fixed. We generalise this algorithm to counting resolutions of a fully ranked constraint tree. We describe a quadratic algorithm for counting the number of possible fully ranked trees on n sampled individuals. We introduce a new type of tree, called a fully ranked tree with sampled ancestors, and describe a cubic time algorithm for counting the number of such trees on n sampled individuals. CONCLUSIONS: These algorithms should be employed for Bayesian Markov chain Monte Carlo inference when fossil data are included or data are serially sampled. BioMed Central 2013-10-28 /pmc/articles/PMC3829674/ /pubmed/24164709 http://dx.doi.org/10.1186/1748-7188-8-26 Text en Copyright © 2013 Gavryushkina et al.; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License(http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Research Gavryushkina, Alexandra Welch, David Drummond, Alexei J Recursive algorithms for phylogenetic tree counting |
title | Recursive algorithms for phylogenetic tree counting |
title_full | Recursive algorithms for phylogenetic tree counting |
title_fullStr | Recursive algorithms for phylogenetic tree counting |
title_full_unstemmed | Recursive algorithms for phylogenetic tree counting |
title_short | Recursive algorithms for phylogenetic tree counting |
title_sort | recursive algorithms for phylogenetic tree counting |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3829674/ https://www.ncbi.nlm.nih.gov/pubmed/24164709 http://dx.doi.org/10.1186/1748-7188-8-26 |
work_keys_str_mv | AT gavryushkinaalexandra recursivealgorithmsforphylogenetictreecounting AT welchdavid recursivealgorithmsforphylogenetictreecounting AT drummondalexeij recursivealgorithmsforphylogenetictreecounting |