Binomial distribution based tau-leap accelerated stochastic simulation

Recently, Gillespie introduced the tau-leap approximate, accelerated stochastic Monte Carlo method for well-mixed reacting systems [J. Chem. Phys. 115, 1716 (2001)]. In each time increment of that method, one executes a number of reaction events, selected randomly from a Poisson distribution, to enable simulation of long times. Here we introduce a binomial distribution tau-leap algorithm (abbreviated as BD-tau method). This method combines the bounded nature of the binomial distribution variable with the limiting reactant and constrained firing concepts to avoid negative populations encountered in the original tau-leap method of Gillespie for large time increments, and thus conserve mass. Simulations using prototype reaction networks show that the BD-tau method is more accurate than the original method for comparable coarse-graining in time.     

Binomial leap methods for simulating stochastic chemical kinetics

This paper discusses efficient simulation methods for stochastic chemical kinetics. Based on the tau-leap and midpoint tau-leap methods of Gillespie [D. T. Gillespie, J. Chem. Phys. 115, 1716 (2001)], binomial random variables are used in these leap methods rather than Poisson random variables. The motivation for this approach is to improve the efficiency of the Poisson leap methods by using larger stepsizes. Unlike Poisson random variables whose range of sample values is from zero to infinity, binomial random variables have a finite range of sample values. This probabilistic property has been used to restrict possible reaction numbers and to avoid negative molecular numbers in stochastic simulations when larger stepsize is used. In this approach a binomial random variable is defined for a single reaction channel in order to keep the reaction number of this channel below the numbers of molecules that undergo this reaction channel. A sampling technique is also designed for the total reaction number of a reactant species that undergoes two or more reaction channels. Samples for the total reaction number are not greater than the molecular number of this species. In addition, probability properties of the binomial random variables provide stepsize conditions for restricting reaction numbers in a chosen time interval. These stepsize conditions are important properties of robust leap control strategies. Numerical results indicate that the proposed binomial leap methods can be applied to a wide range of chemical reaction systems with very good accuracy and significant improvement on efficiency over existing approaches.     

Unbiased tau-leap methods for stochastic simulation of chemically reacting systems

The tau-leap method first developed by Gillespie [D. T. Gillespie, J. Chem. Phys. 115, 1716 (2001)] can significantly speed up stochastic simulation of certain chemically reacting systems with acceptable losses in accuracy. Recently, several improved tau-leap methods, including the binomial, multinomial, and modified tau-leap methods, have been developed. However, in all these tau-leap methods, the mean of the number of times, K(m), that the mth reaction channel fires during a leap is not equal to the true mean. Therefore, all existing tau-leap methods produce biased simulation results, which limit the simulation accuracy and speed. In this paper, we analyze the mean of K(m) based on the chemical master equation. Using this analytical result, we develop unbiased Poisson and binomial tau-leap methods. Moreover, we analyze the variance of K(m), and then develop an unbiased Poisson/Gaussian/binomial tau-leap method to correct the errors in both the mean and variance of K(m). Simulation results demonstrate that our unbiased tau-leap method can significantly improve simulation accuracy without sacrificing speed.     

Accelerated stochastic simulation algorithm for coupled chemical reactions with delays

Some biochemical processes do not occur instantaneously but have considerably delays associated with them. In the existed methods which solve these chemically reacting systems with delays, averaging over a great deal of simulations is needed for reliable statistical characters. Here we present an accelerating approach, called the "Delay Final All Possible Steps" (DFAPS) approach, which does not alter the course of stochastic simulation, but reduces the required running times. Numerical simulation results indicate that the proposed method can be applied to a wide range of chemically reacting systems with delays and obtain a significant improvement on efficiency and accuracy over the existed methods.     

Nested stochastic simulation algorithm for chemical kinetic systems with disparate rates

An efficient simulation algorithm for chemical kinetic systems with disparate rates is proposed. This new algorithm is quite general, and it amounts to a simple and seamless modification of the classical stochastic simulation algorithm (SSA), also known as the Gillespie [J. Comput. Phys. 22, 403 (1976); J. Phys. Chem. 81, 2340 (1977)] algorithm. The basic idea is to use an outer SSA to simulate the slow processes with rates computed from an inner SSA which simulates the fast reactions. Averaging theorems for Markov processes can be used to identify the fast and slow variables in the system as well as the effective dynamics over the slow time scale, even though the algorithm itself does not rely on such information. This nested SSA can be easily generalized to systems with more than two separated time scales. Convergence and efficiency of the algorithm are discussed using the established error estimates and illustrated through examples.     

A partial-propensity formulation of the stochastic simulation algorithm for chemical reaction networks with delays

Several real-world systems, such as gene expression networks in biological cells, contain coupled chemical reactions with a time delay between reaction initiation and completion. The non-Markovian kinetics of such reaction networks can be exactly simulated using the delay stochastic simulation algorithm (dSSA). The computational cost of dSSA scales with the total number of reactions in the network. We reduce this cost to scale at most with the smaller number of species by using the concept of partial reaction propensities. The resulting delay partial-propensity direct method (dPDM) is an exact dSSA formulation for well-stirred systems of coupled chemical reactions with delays. We detail dPDM and present a theoretical analysis of its computational cost. Furthermore, we demonstrate the implications of the theoretical cost analysis in two prototypical benchmark applications. The dPDM formulation is shown to be particularly efficient for strongly coupled reaction networks, where the number of reactions is much larger than the number of species.     

On the origins of approximations for stochastic chemical kinetics

This paper considers the derivation of approximations for stochastic chemical kinetics governed by the discrete master equation. Here, the concepts of (1) partitioning on the basis of fast and slow reactions as opposed to fast and slow species and (2) conditional probability densities are used to derive approximate, partitioned master equations, which are Markovian in nature, from the original master equation. Under different conditions dictated by relaxation time arguments, such approximations give rise to both the equilibrium and hybrid (deterministic or Langevin equations coupled with discrete stochastic simulation) approximations previously reported. In addition, the derivation points out several weaknesses in previous justifications of both the hybrid and equilibrium systems and demonstrates the connection between the original and approximate master equations. Two simple examples illustrate situations in which these two approximate methods are applicable and demonstrate the two methods' efficiencies.     

基于Arrhenius定理的化学动力学数值计算法

基于Arrhenius定理建立了一种新的化学动力学数值模拟方法.将其与化学动力学过程契合,能较好地体现化学动力学过程.将该方法对简单一级反应、平行反应和复杂的综合反应进行模拟计算,模拟结果与准确解相对误差小于0.5%.     

The slow-scale stochastic simulation algorithm

Reactions in real chemical systems often take place on vastly different time scales, with "fast" reaction channels firing very much more frequently than "slow" ones. These firings will be interdependent if, as is usually the case, the fast and slow reactions involve some of the same species. An exact stochastic simulation of such a system will necessarily spend most of its time simulating the more numerous fast reaction events. This is a frustratingly inefficient allocation of computational effort when dynamical stiffness is present, since in that case a fast reaction event will be of much less importance to the system's evolution than will a slow reaction event. For such situations, this paper develops a systematic approximate theory that allows one to stochastically advance the system in time by simulating the firings of only the slow reaction events. Developing an effective strategy to implement this theory poses some challenges, but as is illustrated here for two simple systems, when those challenges can be overcome, very substantial increases in simulation speed can be realized.     

Abstract Next Subvolume Method: a logical process-based approach for spatial stochastic simulation of chemical reactions

The spatial stochastic simulation of biochemical systems requires significant calculation efforts. Parallel discrete-event simulation is a promising approach to accelerate the execution of simulation runs. However, achievable speedup depends on the parallelism inherent in the model. One of our goals is to explore this degree of parallelism in the Next Subvolume Method type simulations. Therefore we introduce the Abstract Next Subvolume Method, in which we decouple the model representation from the sequential simulation algorithms, and prove that state trajectories generated by its executions statistically accord with those generated by the Next Subvolume Method. The experimental performance analysis shows that optimistic synchronization algorithms, together with careful controls over the speculative execution, are necessary to achieve considerable speedup and scalability in parallel spatial stochastic simulation of chemical reactions. Our proposed method facilitates a flexible incorporation of different synchronization algorithms, and can be used to select the proper synchronization algorithm to achieve the efficient parallel simulation of chemical reactions.     

K-leap method for accelerating stochastic simulation of coupled chemical reactions

Leap methods are very promising for accelerating stochastic simulation of a well stirred chemically reacting system, while providing acceptable simulation accuracy. In Gillespie's tau-leap method [D. Gillespie, J. Phys. Chem. 115, 1716 (2001)], the number of firings of each reaction channel during a leap is a Poisson random variable, whose sample values are unbounded. This may cause large changes in the populations of certain molecular species during a leap, thereby violating the leap condition. In this paper, we develop an alternative leap method called the K-leap method, in which we constrain the total number of reactions occurring during a leap to be a number K calculated from the leap condition. As the number of firings of each reaction channel during a leap is upper bounded by a properly chosen number, our K-leap method can better satisfy the leap condition, thereby improving simulation accuracy. Since the exact stochastic simulation algorithm (SSA) is a special case of our K-leap method when K=1, our K-leap method can naturally change from the exact SSA to an approximate leap method during simulation, whenever the leap condition allows to do so.     

Effect of reactant size on discrete stochastic chemical kinetics

This paper is aimed at understanding what happens to the propensity functions (rates) of bimolecular chemical reactions when the volume occupied by the reactant molecules is not negligible compared to the containing volume of the system. For simplicity our analysis focuses on a one-dimensional gas of N hard-rod molecules, each of length l. Assuming these molecules are distributed randomly and uniformly inside the real interval [0,L] in a nonoverlapping way, and that they have Maxwellian distributed velocities, the authors derive an expression for the probability that two rods will collide in the next infinitesimal time dt. This probability controls the rate of any chemical reaction whose occurrence is initiated by such a collision. The result turns out to be a simple generalization of the well-known result for the point molecule case l=0: the system volume L in the formula for the propensity function in the point molecule case gets replaced by the "free volume" L-Nl. They confirm the result in a series of one-dimensional molecular dynamics simulations. Some possible wider implications of this result are discussed.     

State-dependent doubly weighted stochastic simulation algorithm for automatic characterization of stochastic biochemical rare events

In recent years there has been substantial growth in the development of algorithms for characterizing rare events in stochastic biochemical systems. Two such algorithms, the state-dependent weighted stochastic simulation algorithm (swSSA) and the doubly weighted SSA (dwSSA) are extensions of the weighted SSA (wSSA) by H. Kuwahara and I. Mura [J. Chem. Phys. 129, 165101 (2008)]. The swSSA substantially reduces estimator variance by implementing system state-dependent importance sampling (IS) parameters, but lacks an automatic parameter identification strategy. In contrast, the dwSSA provides for the automatic determination of state-independent IS parameters, thus it is inefficient for systems whose states vary widely in time. We present a novel modification of the dwSSA--the state-dependent doubly weighted SSA (sdwSSA)--that combines the strengths of the swSSA and the dwSSA without inheriting their weaknesses. The sdwSSA automatically computes state-dependent IS parameters via the multilevel cross-entropy method. We apply the method to three examples: a reversible isomerization process, a yeast polarization model, and a lac operon model. Our results demonstrate that the sdwSSA offers substantial improvements over previous methods in terms of both accuracy and efficiency.     

A study of the accuracy of moment-closure approximations for stochastic chemical kinetics

Moment-closure approximations have in recent years become a popular means to estimate the mean concentrations and the variances and covariances of the concentration fluctuations of species involved in stochastic chemical reactions, such as those inside cells. The typical assumption behind these methods is that all cumulants of the probability distribution function solution of the chemical master equation which are higher than a certain order are negligibly small and hence can be set to zero. These approximations are ad hoc and hence the reliability of the predictions of these class of methods is presently unclear. In this article, we study the accuracy of the two moment approximation (2MA) (third and higher order cumulants are zero) and of the three moment approximation (3MA) (fourth and higher order cumulants are zero) for chemical systems which are monostable and composed of unimolecular and bimolecular reactions. We use the system-size expansion, a systematic method of solving the chemical master equation for monostable reaction systems, to calculate in the limit of large reaction volumes, the first- and second-order corrections to the mean concentration prediction of the rate equations and the first-order correction to the variance and covariance predictions of the linear-noise approximation. We also compute these corrections using the 2MA and the 3MA. Comparison of the latter results with those of the system-size expansion shows that: (i) the 2MA accurately captures the first-order correction to the rate equations but its first-order correction to the linear-noise approximation exhibits the wrong dependence on the rate constants. (ii) the 3MA accurately captures the first- and second-order corrections to the rate equation predictions and the first-order correction to the linear-noise approximation. Hence while both the 2MA and the 3MA are more accurate than the rate equations, only the 3MA is more accurate than the linear-noise approximation across all of parameter space. The analytical results are numerically validated for dimerization and enzyme-catalyzed reactions.     

State-dependent biasing method for importance sampling in the weighted stochastic simulation algorithm

The weighted stochastic simulation algorithm (wSSA) was developed by Kuwahara and Mura [J. Chem. Phys. 129, 165101 (2008)] to efficiently estimate the probabilities of rare events in discrete stochastic systems. The wSSA uses importance sampling to enhance the statistical accuracy in the estimation of the probability of the rare event. The original algorithm biases the reaction selection step with a fixed importance sampling parameter. In this paper, we introduce a novel method where the biasing parameter is state-dependent. The new method features improved accuracy, efficiency, and robustness.     

Efficient formulation of the stochastic simulation algorithm for chemically reacting systems

In this paper we examine the different formulations of Gillespie's stochastic simulation algorithm (SSA) [D. Gillespie, J. Phys. Chem. 81, 2340 (1977)] with respect to computational efficiency, and propose an optimization to improve the efficiency of the direct method. Based on careful timing studies and an analysis of the time-consuming operations, we conclude that for most practical problems the optimized direct method is the most efficient formulation of SSA. This is in contrast to the widely held belief that Gibson and Bruck's next reaction method [M. Gibson and J. Bruck, J. Phys. Chem. A 104, 1876 (2000)] is the best way to implement the SSA for large systems. Our analysis explains the source of the discrepancy.     

R-leaping: accelerating the stochastic simulation algorithm by reaction leaps

A novel algorithm is proposed for the acceleration of the exact stochastic simulation algorithm by a predefined number of reaction firings (R-leaping) that may occur across several reaction channels. In the present approach, the numbers of reaction firings are correlated binomial distributions and the sampling procedure is independent of any permutation of the reaction channels. This enables the algorithm to efficiently handle large systems with disparate rates, providing substantial computational savings in certain cases. Several mechanisms for controlling the accuracy and the appearance of negative species are described. The advantages and drawbacks of R-leaping are assessed by simulations on a number of benchmark problems and the results are discussed in comparison with established methods.     

A computational algorithm for the Green's function method of sensitivity analysis in chemical kinetics

The recent interest in numerical modeling of chemical kinetics has generated the need for proper analysis of the system sensitivities in such models. This paper describes the logic for a program developed by the authors to implement the Green's function method of sensitivity analysis in complex kinetic schemes. The relevant equations and numerical details of the algorithm are outlined, two flow charts are provided, and some special programming considerations are discussed in some detail. Computer storage and computational time considerations are also treated. Finally, applications of sensitivity information to understanding complex kinetic system behavior and analyzing experimental results are suggested.