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.     

A kinetic Monte Carlo simulation study of inositol 1,4,5-trisphosphate receptor (IP3R) calcium release channel

Most of the previously theoretical studies about the stochastic nature of the IP3R calcium release channel gating use the chemical master equation (CME) approach. Because of the limitations of this approach we have used a stochastic simulation algorithm (SSA) presented by Gillespie. A single subunit of De Young-Keizer (DYK) model was simulated using Gillespie algorithm. The model has been considered in its complete form with eight states. We investigate the conditions which affect the open state of the model. Calcium concentrations were the subject of fluctuation in the previous works while in this study the population of the states is the subject of stochastic fluctuations. We found out that decreasing open probability is a function of Ca(2+) concentration in fast time domain, while in slow time domain it is a function of IP3 concentration. Studying the population of each state shows a time dependent reaction pattern in fast and medium time domains (10(-4) and 10(-3)s). In this pattern the state of X(010) has a determinative role in selecting the open state path. Also, intensity and frequency of fluctuations and Ca(2+) inhibitions have been studied. The results indicate that Gillespie algorithm can be a better choice for studying such systems, without using any approximation or elimination while having acceptable accuracy. In comparison with the chemical master equation, Gillespie algorithm is also provides a wide area for studying biological systems from other points of view.     

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.     

Hybrid stochastic simulations of intracellular reaction–diffusion systems

With the observation that stochasticity is important in biological systems, chemical kinetics have begun to receive wider interest. While the use of Monte Carlo discrete event simulations most accurately capture the variability of molecular species, they become computationally costly for complex reaction–diffusion systems with large populations of molecules. On the other hand, continuous time models are computationally efficient but they fail to capture any variability in the molecular species. In this study a hybrid stochastic approach is introduced for simulating reaction–diffusion systems. We developed an adaptive partitioning strategy in which processes with high frequency are simulated with deterministic rate-based equations, and those with low frequency using the exact stochastic algorithm of Gillespie. Therefore the stochastic behavior of cellular pathways is preserved while being able to apply it to large populations of molecules. We describe our method and demonstrate its accuracy and efficiency compared with the Gillespie algorithm for two different systems. First, a model of intracellular viral kinetics with two steady states and second, a compartmental model of the postsynaptic spine head for studying the dynamics of Ca+2 and NMDA receptors.     

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.     

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.     

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.     

"All possible steps" approach to the accelerated use of Gillespie's algorithm

Many physical and biological processes are stochastic in nature. Computational models and simulations of such processes are a mathematical and computational challenge. The basic stochastic simulation algorithm was published by Gillespie about three decades ago [J. Phys. Chem. 81, 2340 (1977)]. Since then, intensive work has been done to make the algorithm more efficient in terms of running time. All accelerated versions of the algorithm are aimed at minimizing the running time required to produce a stochastic trajectory in state space. In these simulations, a necessary condition for reliable statistics is averaging over a large number of simulations. In this study the author presents a new accelerating approach which does not alter the stochastic algorithm, but reduces the number of required runs. By analysis of collected data the author demonstrates high precision levels with fewer simulations. Moreover, the suggested approach provides a good estimation of statistical error, which may serve as a tool for determining the number of required runs.     

A constant-time kinetic Monte Carlo algorithm for simulation of large biochemical reaction networks

The time evolution of species concentrations in biochemical reaction networks is often modeled using the stochastic simulation algorithm (SSA) [Gillespie, J. Phys. Chem. 81, 2340 (1977)]. The computational cost of the original SSA scaled linearly with the number of reactions in the network. Gibson and Bruck developed a logarithmic scaling version of the SSA which uses a priority queue or binary tree for more efficient reaction selection [Gibson and Bruck, J. Phys. Chem. A 104, 1876 (2000)]. More generally, this problem is one of dynamic discrete random variate generation which finds many uses in kinetic Monte Carlo and discrete event simulation. We present here a constant-time algorithm, whose cost is independent of the number of reactions, enabled by a slightly more complex underlying data structure. While applicable to kinetic Monte Carlo simulations in general, we describe the algorithm in the context of biochemical simulations and demonstrate its competitive performance on small- and medium-size networks, as well as its superior constant-time performance on very large networks, which are becoming necessary to represent the increasing complexity of biochemical data for pathways that mediate cell function.     

A constrained approach to multiscale stochastic simulation of chemically reacting systems

Stochastic simulation of coupled chemical reactions is often computationally intensive, especially if a chemical system contains reactions occurring on different time scales. In this paper, we introduce a multiscale methodology suitable to address this problem, assuming that the evolution of the slow species in the system is well approximated by a Langevin process. It is based on the conditional stochastic simulation algorithm (CSSA) which samples from the conditional distribution of the suitably defined fast variables, given values for the slow variables. In the constrained multiscale algorithm (CMA) a single realization of the CSSA is then used for each value of the slow variable to approximate the effective drift and diffusion terms, in a similar manner to the constrained mean-force computations in other applications such as molecular dynamics. We then show how using the ensuing Fokker-Planck equation approximation, we can in turn approximate average switching times in stochastic chemical systems.     

Reactions on cell membranes: comparison of continuum theory and Brownian dynamics simulations

Biochemical transduction of signals received by living cells typically involves molecular interactions and enzyme-mediated reactions at the cell membrane, a problem that is analogous to reacting species on a catalyst surface or interface. We have developed an efficient Brownian dynamics algorithm that is especially suited for such systems and have compared the simulation results with various continuum theories through prediction of effective enzymatic rate constant values. We specifically consider reaction versus diffusion limitation, the effect of increasing enzyme density, and the spontaneous membrane association/dissociation of enzyme molecules. In all cases, we find the theory and simulations to be in quantitative agreement. This algorithm may be readily adapted for the stochastic simulation of more complex cell signaling systems.     

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.     

Developing Itô stochastic differential equation models for neuronal signal transduction pathways

Mathematical modeling and simulation of dynamic biochemical systems are receiving considerable attention due to the increasing availability of experimental knowledge of complex intracellular functions. In addition to deterministic approaches, several stochastic approaches have been developed for simulating the time-series behavior of biochemical systems. The problem with stochastic approaches, however, is the larger computational time compared to deterministic approaches. It is therefore necessary to study alternative ways to incorporate stochasticity and to seek approaches that reduce the computational time needed for simulations, yet preserve the characteristic behavior of the system in question. In this work, we develop a computational framework based on the It? stochastic differential equations for neuronal signal transduction networks. There are several different ways to incorporate stochasticity into deterministic differential equation models and to obtain It? stochastic differential equations. Two of the developed models are found most suitable for stochastic modeling of neuronal signal transduction. The best models give stable responses which means that the variances of the responses with time are not increasing and negative concentrations are avoided. We also make a comparative analysis of different kinds of stochastic approaches, that is the It? stochastic differential equations, the chemical Langevin equation, and the Gillespie stochastic simulation algorithm. Different kinds of stochastic approaches can be used to produce similar responses for the neuronal protein kinase C signal transduction pathway. The fine details of the responses vary slightly, depending on the approach and the parameter values. However, when simulating great numbers of chemical species, the Gillespie algorithm is computationally several orders of magnitude slower than the It? stochastic differential equations and the chemical Langevin equation. Furthermore, the chemical Langevin equation produces negative concentrations. The It? stochastic differential equations developed in this work are shown to overcome the problem of obtaining negative values.     

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.     

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.     

Stochastic hybrid modeling of intracellular calcium dynamics

Deterministic models of biochemical processes at the subcellular level might become inadequate when a cascade of chemical reactions is induced by a few molecules. Inherent randomness of such phenomena calls for the use of stochastic simulations. However, being computationally intensive, such simulations become infeasible for large and complex reaction networks. To improve their computational efficiency in handling these networks, we present a hybrid approach, in which slow reactions and fluxes are handled through exact stochastic simulation and their fast counterparts are treated partially deterministically through chemical Langevin equation. The classification of reactions as fast or slow is accompanied by the assumption that in the time-scale of fast reactions, slow reactions do not occur and hence do not affect the probability of the state. Our new approach also handles reactions with complex rate expressions such as Michaelis-Menten kinetics. Fluxes which cannot be modeled explicitly through reactions, such as flux of Ca(2+) from endoplasmic reticulum to the cytosol through inositol 1,4,5-trisphosphate receptor channels, are handled deterministically. The proposed hybrid algorithm is used to model the regulation of the dynamics of cytosolic calcium ions in mouse macrophage RAW 264.7 cells. At relatively large number of molecules, the response characteristics obtained with the stochastic and deterministic simulations coincide, which validates our approach in the limit of large numbers. At low doses, the response characteristics of some key chemical species, such as levels of cytosolic calcium, predicted with stochastic simulations, differ quantitatively from their deterministic counterparts. These observations are ubiquitous throughout dose response, sensitivity, and gene-knockdown response analyses. While the relative differences between the peak-heights of the cytosolic [Ca(2+)] time-courses obtained from stochastic (mean of 16 realizations) and deterministic simulations are merely 1%-4% for most perturbations, it is specially sensitive to levels of G(βγ) (relative difference as large as 90% at very low G(βγ)).     

Efficient binomial leap method for simulating chemical kinetics

The binomial tau-leaping method of simulating the stochastic time evolution in a reaction system uses a binomial random number to approximate the number of reaction events. Theory implies that this method can avoid negative molecular numbers in stochastic simulations when a larger time step tau is used. Presented here is a modified binomial leap method for improving the accuracy and application range of the binomial leap method. The maximum existing population is first defined in this approach in order to determine a better bound of the number reactions. To derive a general leap procedure in chemically reacting systems, in this method a new sampling procedure based on the species is also designed for the maximum bound of consumed molecules of a reactant species in reaction channel. Numerical results indicate that the modified binomial leap method can be applied to a wider application range of chemically reacting systems with much better accuracy than the existing binomial leap method.     

基于随机扩散理论的色谱模拟辅助化学教学研究

为了满足当今教学的信息化发展趋势,本研究基于随机扩散理论建立了气相色谱仿真模型并开发了相关的计算模拟软件Stochastic Diffusion-Chroma。以混合组分分别在气相色谱填充柱和毛细管柱中的扩散分离模拟为例,探究了随机扩散理论模型在色谱理论教学和实验教学方面的应用。基于随机扩散理论的仿真教学改变了传统的教学模式,将学生较难理解的抽象色谱动力学基本理论转变为动态的具体形象,激发了学生的学习兴趣,提高教学质量。