Abstract
Discretestate, continuoustime Markov models are widely used in the modeling of biochemical reaction networks. Their complexity often precludes analytic solution, and we rely on stochastic simulation algorithms to estimate system statistics. The Gillespie algorithm is exact, but computationally costly as it simulates every single reaction. As such, approximate stochastic simulation algorithms such as the tauleap algorithm are often used. Potentially computationally more efficient, the system statistics generated suffer from significant bias unless tau is relatively small, in which case the computational time can be comparable to that of the Gillespie algorithm.
The multilevel method (Anderson and Higham, Multiscale Model. Simul. 10:146179, 2012) tackles this problem. A base estimator is computed using many (cheap) sample paths at low accuracy. The bias inherent in this estimator is then reduced using a number of corrections. Each correction term is estimated using a collection of paired sample paths where one path of each pair is generated at a higher accuracy compared to the other (and so more expensive). By sharing random variables between these paired paths the variance of each correction estimator can be reduced. This renders the multilevel method very efficient as only a relatively small number of paired paths are required to calculate each correction term.
In the original multilevel method, each sample path is simulated using the tauleap algorithm with a fixed value of $\tau$. This approach can result in poor performance when the reaction activity of a system changes substantially over the timescale of interest. By introducing a novel, adaptive timestepping approach where $\tau$ is chosen according to the stochastic behaviour of each sample path we extend the applicability of the multilevel method to such cases. We demonstrate the efficiency of our method using a number of examples.
The multilevel method (Anderson and Higham, Multiscale Model. Simul. 10:146179, 2012) tackles this problem. A base estimator is computed using many (cheap) sample paths at low accuracy. The bias inherent in this estimator is then reduced using a number of corrections. Each correction term is estimated using a collection of paired sample paths where one path of each pair is generated at a higher accuracy compared to the other (and so more expensive). By sharing random variables between these paired paths the variance of each correction estimator can be reduced. This renders the multilevel method very efficient as only a relatively small number of paired paths are required to calculate each correction term.
In the original multilevel method, each sample path is simulated using the tauleap algorithm with a fixed value of $\tau$. This approach can result in poor performance when the reaction activity of a system changes substantially over the timescale of interest. By introducing a novel, adaptive timestepping approach where $\tau$ is chosen according to the stochastic behaviour of each sample path we extend the applicability of the multilevel method to such cases. We demonstrate the efficiency of our method using a number of examples.
Original language  English 

Article number  024113 
Number of pages  10 
Journal  Journal of Chemical Physics 
Volume  142 
Issue number  2 
DOIs  
Publication status  Published  14 Jan 2015 
Keywords
 stochastic siulation, multilevel
Fingerprint
Dive into the research topics of 'An adaptive multilevel simulation algorithm for stochastic biological systems'. Together they form a unique fingerprint.Profiles

Kit Yates
 Department of Mathematical Sciences  Senior Lecturer
 EPSRC Centre for Doctoral Training in Statistical Applied Mathematics (SAMBa)
 Centre for Mathematical Biology  CoDirector
 Institute for Mathematical Innovation (IMI)
Person: Research & Teaching