Limits...
Phylogenetic inference via sequential Monte Carlo.

Bouchard-Côté A, Sankararaman S, Jordan MI - Syst. Biol. (2012)

Bottom Line: We provide a theoretical treatment of PosetSMC and also present experimental evaluation of PosetSMC on both synthetic and real data.The empirical results demonstrate that PosetSMC is a very promising alternative to MCMC, providing up to two orders of magnitude faster convergence.We discuss other factors favorable to the adoption of PosetSMC in phylogenetics, including its ability to estimate marginal likelihoods, its ready implementability on parallel and distributed computing platforms, and the possibility of combining with MCMC in hybrid MCMC-SMC schemes.

View Article: PubMed Central - PubMed

Affiliation: Department of Statistics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada.

ABSTRACT
Bayesian inference provides an appealing general framework for phylogenetic analysis, able to incorporate a wide variety of modeling assumptions and to provide a coherent treatment of uncertainty. Existing computational approaches to bayesian inference based on Markov chain Monte Carlo (MCMC) have not, however, kept pace with the scale of the data analysis problems in phylogenetics, and this has hindered the adoption of bayesian methods. In this paper, we present an alternative to MCMC based on Sequential Monte Carlo (SMC). We develop an extension of classical SMC based on partially ordered sets and show how to apply this framework--which we refer to as PosetSMC--to phylogenetic analysis. We provide a theoretical treatment of PosetSMC and also present experimental evaluation of PosetSMC on both synthetic and real data. The empirical results demonstrate that PosetSMC is a very promising alternative to MCMC, providing up to two orders of magnitude faster convergence. We discuss other factors favorable to the adoption of PosetSMC in phylogenetics, including its ability to estimate marginal likelihoods, its ready implementability on parallel and distributed computing platforms, and the possibility of combining with MCMC in hybrid MCMC-SMC schemes. Software for PosetSMC is available at http://www.stat.ubc.ca/ bouchard/PosetSMC.

Show MeSH
A partial state s is extended to a new partial partial state  by merging trees  and  to form a tree  with height . In the PriorPrior proposal,  and  are chosen uniformly from the three possible pairs, whereas the height increment  is chosen from an exponential distribution. In the PriorPost proposal,  is chosen from the exponential prior and, given , the pair to merge is chosen from a multinomial with parameters proportional to the likelihood of the tree .
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3376373&req=5

fig12: A partial state s is extended to a new partial partial state by merging trees and to form a tree with height . In the PriorPrior proposal, and are chosen uniformly from the three possible pairs, whereas the height increment is chosen from an exponential distribution. In the PriorPost proposal, is chosen from the exponential prior and, given , the pair to merge is chosen from a multinomial with parameters proportional to the likelihood of the tree .

Mentions: In both cases, given a partial state s, a successor partial state (forest), , is obtained from a previous partial state s by merging two trees, and , creating a new tree (see Fig. A1). Formally, we have that implies that there are disjoint sets such that:FIGURE A1.


Phylogenetic inference via sequential Monte Carlo.

Bouchard-Côté A, Sankararaman S, Jordan MI - Syst. Biol. (2012)

A partial state s is extended to a new partial partial state  by merging trees  and  to form a tree  with height . In the PriorPrior proposal,  and  are chosen uniformly from the three possible pairs, whereas the height increment  is chosen from an exponential distribution. In the PriorPost proposal,  is chosen from the exponential prior and, given , the pair to merge is chosen from a multinomial with parameters proportional to the likelihood of the tree .
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3376373&req=5

fig12: A partial state s is extended to a new partial partial state by merging trees and to form a tree with height . In the PriorPrior proposal, and are chosen uniformly from the three possible pairs, whereas the height increment is chosen from an exponential distribution. In the PriorPost proposal, is chosen from the exponential prior and, given , the pair to merge is chosen from a multinomial with parameters proportional to the likelihood of the tree .
Mentions: In both cases, given a partial state s, a successor partial state (forest), , is obtained from a previous partial state s by merging two trees, and , creating a new tree (see Fig. A1). Formally, we have that implies that there are disjoint sets such that:FIGURE A1.

Bottom Line: We provide a theoretical treatment of PosetSMC and also present experimental evaluation of PosetSMC on both synthetic and real data.The empirical results demonstrate that PosetSMC is a very promising alternative to MCMC, providing up to two orders of magnitude faster convergence.We discuss other factors favorable to the adoption of PosetSMC in phylogenetics, including its ability to estimate marginal likelihoods, its ready implementability on parallel and distributed computing platforms, and the possibility of combining with MCMC in hybrid MCMC-SMC schemes.

View Article: PubMed Central - PubMed

Affiliation: Department of Statistics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada.

ABSTRACT
Bayesian inference provides an appealing general framework for phylogenetic analysis, able to incorporate a wide variety of modeling assumptions and to provide a coherent treatment of uncertainty. Existing computational approaches to bayesian inference based on Markov chain Monte Carlo (MCMC) have not, however, kept pace with the scale of the data analysis problems in phylogenetics, and this has hindered the adoption of bayesian methods. In this paper, we present an alternative to MCMC based on Sequential Monte Carlo (SMC). We develop an extension of classical SMC based on partially ordered sets and show how to apply this framework--which we refer to as PosetSMC--to phylogenetic analysis. We provide a theoretical treatment of PosetSMC and also present experimental evaluation of PosetSMC on both synthetic and real data. The empirical results demonstrate that PosetSMC is a very promising alternative to MCMC, providing up to two orders of magnitude faster convergence. We discuss other factors favorable to the adoption of PosetSMC in phylogenetics, including its ability to estimate marginal likelihoods, its ready implementability on parallel and distributed computing platforms, and the possibility of combining with MCMC in hybrid MCMC-SMC schemes. Software for PosetSMC is available at http://www.stat.ubc.ca/ bouchard/PosetSMC.

Show MeSH