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

DOI10.1214/09-AOAS247zbMATH Open1196.62139arXiv0910.1683OpenAlexW3101924122WikidataQ42920633 ScholiaQ42920633MaRDI QIDQ985037FDOQ985037

Authors: Asger Hobolth, Eric A. Stone 

Publication date: 20 July 2010

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

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.

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

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

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)

Cites Work

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

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 clustering for continuous‐time hidden Markov models
• Bayesian inference for multistate `step and turn' animal movement in continuous time
• 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)