Simulation from endpoint-conditioned, continuous-time Markov chains on a finite state space, with applications to molecular evolution

DOI10.1214/09-AOAS247MaRDI QIDQ985037zbMATH OpenOpenAlexWikidataFDO

Authors Asger Hobolth, Eric A. Stone

Publication date 20 July 2010

Published in The Annals of Applied Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.1683

zbMATH Keywords

simulationcontinuous-time Markov chainsmolecular evolution

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Applications of statistics to biology and medical sciences; meta analysis (62P10) Biochemistry, molecular biology (92C40) Problems related to evolution (92D15)

Abstract: Analyses of serially-sampled data often begin with the assumption that the observations represent discrete samples from a latent continuous-time stochastic process. The continuous-time Markov chain (CTMC) is one such generative model whose popularity extends to a variety of disciplines ranging from computational finance to human genetics and genomics. A common theme among these diverse applications is the need to simulate sample paths of a CTMC conditional on realized data that is discretely observed. Here we present a general solution to this sampling problem when the CTMC is defined on a discrete and finite state space. Specifically, we consider the generation of sample paths, including intermediate states and times of transition, from a CTMC whose beginning and ending states are known across a time interval of length $T$. We first unify the literature through a discussion of the three predominant approaches: (1) modified rejection sampling, (2) direct sampling, and (3) uniformization. We then give analytical results for the complexity and efficiency of each method in terms of the instantaneous transition rate matrix $Q$ of the CTMC, its beginning and ending states, and the length of sampling time $T$. In doing so, we show that no method dominates the others across all model specifications, and we give explicit proof of which method prevails for any given $Q,T,$ and endpoints. Finally, we introduce and compare three applications of CTMCs to demonstrate the pitfalls of choosing an inefficient sampler.

Recommendations

• An introduction to Markov state models and their application to long timescale molecular simulation
• Counting labeled transitions in continuous-time Markov models of evolution
• Artificial Evolution
• scientific article; zbMATH DE number 1927572
• scientific article; zbMATH DE number 1337869
• On the convergence of the Markov chain simulation method
• On the exact simulation of functionals of stationary Markov chains
• Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics
• Bayesian analysis of continuous time Markov chains with application to phylogenetic modelling

Cites work

• scientific article; zbMATH DE number 3082073 (Why is no real title available?)
• An Exact Gibbs Sampler for the Markov-Modulated Poisson Process
• Bayesian inference for Markov processes with diffusion and discrete components
• Counting labeled transitions in continuous-time Markov models of evolution
• New Methods for Detecting Lineage-Specific Selection
• Probabilistic models of DNA sequence evolution with context dependent rates of substitution
• Statistical Inference for Discretely Observed Markov Jump Processes
• Statistical Inference in Evolutionary Models of DNA Sequences via the EM Algorithm
• Stochastic Modeling of Scientific Data

Cited in

(19)

• Bayesian inference for continuous-time hidden Markov models with an unknown number of states
• Auxiliary variables for Bayesian inference in multi-class queueing networks
• Rate estimation in partially observed Markov jump processes with measurement errors
• Markov Bridges, Bisection and Variance Reduction
• Computational methods for birth-death processes
• An extended likelihood framework for modelling discretely observed credit rating transitions
• Bayesian latent multi‐state modeling for nonequidistant longitudinal electronic health records
• Likelihood-Based Inference for Partially Observed Epidemics on Dynamic Networks
• Detecting changes in the transmission rate of a stochastic epidemic model
• Bayesian inference for discretely observed continuous time multi-state models
• Variational inference for Markovian queueing networks
• Structure learning for continuous time Bayesian networks via penalized likelihood
• Exchangeable Markov multi-state survival processes
• Bayesian inference for multistate `step and turn' animal movement in continuous time
• Bayesian clustering for continuous‐time hidden Markov models
• Efficient Parameter Sampling for Markov Jump Processes
• Estimation for general birth-death processes
• Counting labeled transitions in continuous-time Markov models of evolution
• Exact and computationally efficient Bayesian inference for generalized Markov modulated Poisson processes

This page was built for publication: Simulation from endpoint-conditioned, continuous-time Markov chains on a finite state space, with applications to molecular evolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q985037)