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...

Descripción completa

Detalles Bibliográficos
Autores principales: Jun, Seong-Hwan, Nasif, Hassan, Jennings-Shaffer, Chris, Rich, David H, Kooperberg, Anna, Fourment, Mathieu, Zhang, Cheng, Suchard, Marc A, Matsen, Frederick A
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