Cargando…
A topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm
Bayesian phylogenetics is a computationally challenging inferential problem. Classical methods are based on random-walk Markov chain Monte Carlo (MCMC), where random proposals are made on the tree parameter and the continuous parameters simultaneously. Variational phylogenetics is a promising altern...
Autores principales: | , , , , , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2023
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10391877/ https://www.ncbi.nlm.nih.gov/pubmed/37525243 http://dx.doi.org/10.1186/s13015-023-00235-1 |
_version_ | 1785082818426044416 |
---|---|
author | Jun, Seong-Hwan Nasif, Hassan Jennings-Shaffer, Chris Rich, David H Kooperberg, Anna Fourment, Mathieu Zhang, Cheng Suchard, Marc A Matsen, Frederick A |
author_facet | Jun, Seong-Hwan Nasif, Hassan Jennings-Shaffer, Chris Rich, David H Kooperberg, Anna Fourment, Mathieu Zhang, Cheng Suchard, Marc A Matsen, Frederick A |
author_sort | Jun, Seong-Hwan |
collection | PubMed |
description | Bayesian phylogenetics is a computationally challenging inferential problem. Classical methods are based on random-walk Markov chain Monte Carlo (MCMC), where random proposals are made on the tree parameter and the continuous parameters simultaneously. Variational phylogenetics is a promising alternative to MCMC, in which one fits an approximating distribution to the unnormalized phylogenetic posterior. Previous work fit this variational approximation using stochastic gradient descent, which is the canonical way of fitting general variational approximations. However, phylogenetic trees are special structures, giving opportunities for efficient computation. In this paper we describe a new algorithm that directly generalizes the Felsenstein pruning algorithm (a.k.a. sum-product algorithm) to compute a composite-like likelihood by marginalizing out ancestral states and subtrees simultaneously. We show the utility of this algorithm by rapidly making point estimates for branch lengths of a multi-tree phylogenetic model. These estimates accord with a long MCMC run and with estimates obtained using a variational method, but are much faster to obtain. Thus, although generalized pruning does not lead to a variational algorithm as such, we believe that it will form a useful starting point for variational inference. SUPPLEMENTARY INFORMATION: The online version contains supplementary material available at 10.1186/s13015-023-00235-1. |
format | Online Article Text |
id | pubmed-10391877 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2023 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-103918772023-08-02 A topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm Jun, Seong-Hwan Nasif, Hassan Jennings-Shaffer, Chris Rich, David H Kooperberg, Anna Fourment, Mathieu Zhang, Cheng Suchard, Marc A Matsen, Frederick A Algorithms Mol Biol Research Bayesian phylogenetics is a computationally challenging inferential problem. Classical methods are based on random-walk Markov chain Monte Carlo (MCMC), where random proposals are made on the tree parameter and the continuous parameters simultaneously. Variational phylogenetics is a promising alternative to MCMC, in which one fits an approximating distribution to the unnormalized phylogenetic posterior. Previous work fit this variational approximation using stochastic gradient descent, which is the canonical way of fitting general variational approximations. However, phylogenetic trees are special structures, giving opportunities for efficient computation. In this paper we describe a new algorithm that directly generalizes the Felsenstein pruning algorithm (a.k.a. sum-product algorithm) to compute a composite-like likelihood by marginalizing out ancestral states and subtrees simultaneously. We show the utility of this algorithm by rapidly making point estimates for branch lengths of a multi-tree phylogenetic model. These estimates accord with a long MCMC run and with estimates obtained using a variational method, but are much faster to obtain. Thus, although generalized pruning does not lead to a variational algorithm as such, we believe that it will form a useful starting point for variational inference. SUPPLEMENTARY INFORMATION: The online version contains supplementary material available at 10.1186/s13015-023-00235-1. BioMed Central 2023-07-31 /pmc/articles/PMC10391877/ /pubmed/37525243 http://dx.doi.org/10.1186/s13015-023-00235-1 Text en © The Author(s) 2023 https://creativecommons.org/licenses/by/4.0/Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) . The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/ (https://creativecommons.org/publicdomain/zero/1.0/) ) applies to the data made available in this article, unless otherwise stated in a credit line to the data. |
spellingShingle | Research Jun, Seong-Hwan Nasif, Hassan Jennings-Shaffer, Chris Rich, David H Kooperberg, Anna Fourment, Mathieu Zhang, Cheng Suchard, Marc A Matsen, Frederick A A topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm |
title | A topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm |
title_full | A topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm |
title_fullStr | A topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm |
title_full_unstemmed | A topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm |
title_short | A topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm |
title_sort | topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10391877/ https://www.ncbi.nlm.nih.gov/pubmed/37525243 http://dx.doi.org/10.1186/s13015-023-00235-1 |
work_keys_str_mv | AT junseonghwan atopologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT nasifhassan atopologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT jenningsshafferchris atopologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT richdavidh atopologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT kooperberganna atopologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT fourmentmathieu atopologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT zhangcheng atopologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT suchardmarca atopologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT matsenfredericka atopologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT junseonghwan topologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT nasifhassan topologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT jenningsshafferchris topologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT richdavidh topologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT kooperberganna topologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT fourmentmathieu topologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT zhangcheng topologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT suchardmarca topologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm AT matsenfredericka topologymarginalcompositelikelihoodviaageneralizedphylogeneticpruningalgorithm |