A topology-marginal composite likelihood via a generalized phylogenetic pruning algorithm
Abstract 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 phylogeneti...
| Main Authors: | , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
BioMed Central
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151771 |
| _version_ | 1826192962099347456 |
|---|---|
| author | Jun, Seong-Hwan Nasif, Hassan Jennings-Shaffer, Chris Rich, David H. Kooperberg, Anna Fourment, Mathieu Zhang, Cheng Suchard, Marc A. Matsen, Frederick A. |
| author2 | Center for Brains, Minds, and Machines |
| author_facet | Center for Brains, Minds, and Machines 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 | MIT |
| description | Abstract
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. |
| first_indexed | 2024-09-23T09:31:30Z |
| format | Article |
| id | mit-1721.1/151771 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:31:30Z |
| publishDate | 2023 |
| publisher | BioMed Central |
| record_format | dspace |
| spelling | mit-1721.1/1517712024-01-22T18:33:26Z 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. Center for Brains, Minds, and Machines Abstract 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. 2023-08-16T20:50:11Z 2023-08-16T20:50:11Z 2023-07-31 2023-08-06T03:12:31Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/151771 Algorithms for Molecular Biology. 2023 Jul 31;18(1):10 PUBLISHER_CC en https://doi.org/10.1186/s13015-023-00235-1 Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf BioMed Central BioMed Central |
| spellingShingle | 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 |
| url | https://hdl.handle.net/1721.1/151771 |
| 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 |