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.     

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.     

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.     

Binomial tau-leap spatial stochastic simulation algorithm for applications in chemical kinetics

In cell biology, cell signaling pathway problems are often tackled with deterministic temporal models, well mixed stochastic simulators, and/or hybrid methods. But, in fact, three dimensional stochastic spatial modeling of reactions happening inside the cell is needed in order to fully understand these cell signaling pathways. This is because noise effects, low molecular concentrations, and spatial heterogeneity can all affect the cellular dynamics. However, there are ways in which important effects can be accounted without going to the extent of using highly resolved spatial simulators (such as single-particle software), hence reducing the overall computation time significantly. We present a new coarse grained modified version of the next subvolume method that allows the user to consider both diffusion and reaction events in relatively long simulation time spans as compared with the original method and other commonly used fully stochastic computational methods. Benchmarking of the simulation algorithm was performed through comparison with the next subvolume method and well mixed models (MATLAB), as well as stochastic particle reaction and transport simulations (CHEMCELL, Sandia National Laboratories). Additionally, we construct a model based on a set of chemical reactions in the epidermal growth factor receptor pathway. For this particular application and a bistable chemical system example, we analyze and outline the advantages of our presented binomial tau-leap spatial stochastic simulation algorithm, in terms of efficiency and accuracy, in scenarios of both molecular homogeneity and heterogeneity.     

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.     

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.     

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.     

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.     

Overcoming stiffness in stochastic simulation stemming from partial equilibrium: a multiscale Monte Carlo algorithm

In this paper the problem of stiffness in stochastic simulation of singularly perturbed systems is discussed. Such stiffness arises often from partial equilibrium or quasi-steady-state type of conditions. A multiscale Monte Carlo method is discussed that first assesses whether partial equilibrium is established using a simple criterion. The exact stochastic simulation algorithm (SSA) is next employed to sample among fast reactions over short time intervals (microscopic time steps) in order to compute numerically the proper probability distribution function for sampling the slow reactions. Subsequently, the SSA is used to sample among slow reactions and advance the time by large (macroscopic) time steps. Numerical examples indicate that not only long times can be simulated but also fluctuations are properly captured and substantial computational savings result.     

An accelerated algorithm for discrete stochastic simulation of reaction-diffusion systems using gradient-based diffusion and tau-leaping

Stochastic simulation of reaction-diffusion systems enables the investigation of stochastic events arising from the small numbers and heterogeneous distribution of molecular species in biological cells. Stochastic variations in intracellular microdomains and in diffusional gradients play a significant part in the spatiotemporal activity and behavior of cells. Although an exact stochastic simulation that simulates every individual reaction and diffusion event gives a most accurate trajectory of the system's state over time, it can be too slow for many practical applications. We present an accelerated algorithm for discrete stochastic simulation of reaction-diffusion systems designed to improve the speed of simulation by reducing the number of time-steps required to complete a simulation run. This method is unique in that it employs two strategies that have not been incorporated in existing spatial stochastic simulation algorithms. First, diffusive transfers between neighboring subvolumes are based on concentration gradients. This treatment necessitates sampling of only the net or observed diffusion events from higher to lower concentration gradients rather than sampling all diffusion events regardless of local concentration gradients. Second, we extend the non-negative Poisson tau-leaping method that was originally developed for speeding up nonspatial or homogeneous stochastic simulation algorithms. This method calculates each leap time in a unified step for both reaction and diffusion processes while satisfying the leap condition that the propensities do not change appreciably during the leap and ensuring that leaping does not cause molecular populations to become negative. Numerical results are presented that illustrate the improvement in simulation speed achieved by incorporating these two new strategies.     

A stochastic simulation of nonisothermal nucleation

The results of stochastic simulations of growth and evaporation of small clusters in vapor are reported. Energy dependent growth rates are determined from the monomer-cluster collision rate and decay rates are found from a detailed balance, with the equilibrium size and energy distribution of clusters calculated using the capillarity approximation and the equilibrium vapor pressure. These rates are used in simulations of two-dimensional random walks in size and energy space to determine the fraction of clusters in supersaturated vapor of size (i(min)+1) that reach a size i(max). By assuming that clusters of size i(min) are in equilibrium, this fraction can be related to the nonisothermal nucleation rate. The simulated rates show good agreement with the previously published analytical results. In the absence of an inert carrier gas, the nonisothermal nucleation rates are typically between 1% and 5% of the isothermal rates.     

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.     

COAST: Controllable approximative stochastic reaction algorithm

We present an approximative algorithm for stochastic simulations of chemical reaction systems, called COAST, based on three different modeling levels: for small numbers of particles an exact stochastic model; for intermediate numbers an approximative, but computationally more efficient stochastic model based on discrete Gaussian distributions; and for large numbers the deterministic reaction kinetics. In every simulation time step, the subdivision of the reaction channels into the three different modeling levels is done automatically, where all approximations applied can be controlled by a single error parameter for which an appropriate value can easily be found. Test simulations show that the results of COAST simulations agree well with the outcomes of exact algorithms; however, the asymptotic run times of COAST are asymptotically proportional to smaller powers of the particle numbers than exact algorithms.     

Accelerated stochastic simulation of the stiff enzyme-substrate reaction

The enzyme-catalyzed conversion of a substrate into a product is a common reaction motif in cellular chemical systems. In the three reactions that comprise this process, the intermediate enzyme-substrate complex is usually much more likely to decay into its original constituents than to produce a product molecule. This condition makes the reaction set mathematically "stiff." We show here how the simulation of this stiff reaction set can be dramatically speeded up relative to the standard stochastic simulation algorithm (SSA) by using a recently introduced procedure called the slow-scale SSA. The speedup occurs because the slow-scale SSA explicitly simulates only the relatively rare conversion reactions, skipping over occurrences of the other two less interesting but much more frequent reactions. We describe, explain, and illustrate this simulation procedure for the isolated enzyme-substrate reaction set, and then we show how the procedure extends to the more typical case in which the enzyme-substrate reactions occur together with other reactions and species. Finally, we explain the connection between this slow-scale SSA approach and the Michaelis-Menten [Biochem. Z. 49, 333 (1913)] formula, which has long been used in deterministic chemical kinetics to describe the enzyme-substrate reaction.     

Discrete-time stochastic modeling and simulation of biochemical networks

Since inherent randomness in chemically reacting systems is evident, stochastic modeling and simulation are exceedingly important for investigating complex biological networks. Within the most common stochastic approach a network is modeled by a continuous-time Markov chain governed by the chemical master equation. We show how the continuous-time Markov chain can be converted to a stochastically identical discrete-time Markov chain and obtain a discrete-time version of the chemical master equation. Simulating the discrete-time Markov chain is equivalent to the Gillespie algorithm but requires less effort in that it eliminates the generation of exponential random variables. Thus, exactness as possessed by the Gillespie algorithm is preserved while the simulation can be performed more efficiently.     

Deterministic modeling and stochastic simulation of poly-alkoxylation reactions

The main scope of this work is to show the feasibility and the advantage of using a stochastic approach to describe the poly-alkoxylation kinetics of different substrates. For this purpose, the reactions of ethylene and propylene oxides with respectively ethylene glycol, 1-octanol, and 2-octanol were considered. Two kinetic models were used for interpreting all the kinetic runs available in the literature, one deterministic and another one stochastic, for a useful comparison between the two different approaches. As the adopted reaction mechanism, rate laws, and related kinetic parameters were the same for both the kinetic models, the obtained results for what concerns the substrate consumption, and the oligomers distribution profiles were the same in both cases. In the case of the stochastic kinetic approach, the calculations must be made on a small volume of the reacting mixture containing a sufficiently high number of molecules that is suitable for the statistical analysis but as small as possible for reducing the calculation time. The calculations made have allowed individuating this optimal volume. This study is propaedeutic to the application of a stochastic kinetic approach to the study of ethylene-propylene oxides copolymerization that cannot be faced with a deterministic model for the extremely long or impracticable calculation time due to the great number of material balance differential equations that must be integrated.     

The numerical stability of leaping methods for stochastic simulation of chemically reacting systems

Tau-leaping methods have recently been proposed for the acceleration of discrete stochastic simulation of chemically reacting systems. This paper considers the numerical stability of these methods. The concept of stochastic absolute stability is defined, discussed, and applied to the following leaping methods: the explicit tau, implicit tau, and trapezoidal tau.     

Automatic identification of model reductions for discrete stochastic simulation

Multiple time scales in cellular chemical reaction systems present a challenge for the efficiency of stochastic simulation. Numerous model reductions have been proposed to accelerate the simulation of chemically reacting systems by exploiting time scale separation. However, these are often identified and deployed manually, requiring expert knowledge. This is time-consuming, prone to error, and opportunities for model reduction may be missed, particularly for large models. We propose an automatic model analysis algorithm using an adaptively weighted Petri net to dynamically identify opportunities for model reductions for both the stochastic simulation algorithm and tau-leaping simulation, with no requirement of expert knowledge input. Results are presented to demonstrate the utility and effectiveness of this approach.     

The sorting direct method for stochastic simulation of biochemical systems with varying reaction execution behavior

A key to advancing the understanding of molecular biology in the post-genomic age is the development of accurate predictive models for genetic regulation, protein interaction, metabolism, and other biochemical processes. To facilitate model development, simulation algorithms must provide an accurate representation of the system, while performing the simulation in a reasonable amount of time. Gillespie's stochastic simulation algorithm (SSA) accurately depicts spatially homogeneous models with small populations of chemical species and properly represents noise, but it is often abandoned when modeling larger systems because of its computational complexity. In this work, we examine the performance of different versions of the SSA when applied to several biochemical models. Through our analysis, we discover that transient changes in reaction execution frequencies, which are typical of biochemical models with gene induction and repression, can dramatically affect simulator performance. To account for these shifts, we propose a new algorithm called the sorting direct method that maintains a loosely sorted order of the reactions as the simulation executes. Our measurements show that the sorting direct method performs favorably when compared to other well-known exact stochastic simulation algorithms.