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.     

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(βγ)).     

Stochastic simulation of chemically reacting systems using multi-core processors

In recent years, computer simulations have become increasingly useful when trying to understand the complex dynamics of biochemical networks, particularly in stochastic systems. In such situations stochastic simulation is vital in gaining an understanding of the inherent stochasticity present, as these models are rarely analytically tractable. However, a stochastic approach can be computationally prohibitive for many models. A number of approximations have been proposed that aim to speed up stochastic simulations. However, the majority of these approaches are fundamentally serial in terms of central processing unit (CPU) usage. In this paper, we propose a novel simulation algorithm that utilises the potential of multi-core machines. This algorithm partitions the model into smaller sub-models. These sub-models are then simulated, in parallel, on separate CPUs. We demonstrate that this method is accurate and can speed-up the simulation by a factor proportional to the number of processors available.     

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.     

Efficient stochastic simulation of simultaneous reaction and diffusion in a gas-liquid interface

A stochastic simulation of simultaneous reaction and diffusion is proposed for the gas-liquid interface formed in the surface of a gas bubble within a liquid. The interface between a carbon dioxide bubble and an aqueous solution of calcium hydroxide was simulated as an application example, taken from the integrated production of calcium carbonate. First Gillespie’s stochastic simulation algorithm was applied in separate reaction and diffusion simulations. The results from these simulations were consistent with deterministic solutions based on differential equations. However it was observed that stochastic diffusion simulations are extremely slow. The sampling of diffusion events was accelerated applying a group molecule transfer scheme based on the binomial distribution function. Simulations of the reaction-diffusion in the gas-liquid interface based on the standard Gillespie’s stochastic algorithm were also slow. However the application of the binomial distribution function scheme allowed to compute the concentration profiles in the gas-liquid interface in a fraction of the time required with the standard Gillespie’s stochastic algorithm.     

An efficient method for computing steady state solutions with Gillespie's direct method

Gillespie's direct method is a stochastic simulation algorithm that may be used to calculate the steady state solution of a chemically reacting system. Recently the all possible states method was introduced as a way of accelerating the convergence of the simulations. We demonstrate that while the all possible states (APS) method does reduce the number of required trajectories, it is actually much slower than the original algorithm for most problems. We introduce the elapsed time method, which reformulates the process of recording the species populations. The resulting algorithm yields the same results as the original method, but is more efficient, particularly for large models. In implementing the elapsed time method, we present robust methods for recording statistics and empirical probability distributions. We demonstrate how to use the histogram distance to estimate the error in steady state solutions.     

An ant colony approach for clustering

This paper presents an ant colony optimization methodology for optimally clustering N objects into K clusters. The algorithm employs distributed agents which mimic the way real ants find a shortest path from their nest to food source and back. This algorithm has been implemented and tested on several simulated and real datasets. The performance of this algorithm is compared with other popular stochastic/heuristic methods viz. genetic algorithm, simulated annealing and tabu search. Our computational simulations reveal very encouraging results in terms of the quality of solution found, the average number of function evaluations and the processing time required.     

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.     

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.     

Efficient Stochastic Simulation Algorithm for Chemically Reacting Systems Based on Support Vector Regression

The stochastic simulation algorithm （SSA） accurately depicts spatially homogeneous wellstirred chemically reacting systems 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, a twin support vector regression based stochastic simulations algorithm （TS^3A） is proposed by combining the twin support vector regression and SSA, the former is a well-known robust regression method in machine learning. Numerical results indicate that this proposed algorithm can be applied to a wide range of chemically reacting systems and obtain significant improvements on efficiency and accuracy with fewer simulating runs over the existing 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.     

On combining molecular dynamics and stochastic dynamics simulations to compute reaction rates in liquids

An approach that combines molecular dynamics and stochastic dynamics calculations for obtaining reaction rates in liquids is investigated by studying the cis-->trans isomerization of HONO in liquid krypton. The isomerization rates are computed for several liquid densities by employing full-dimensional molecular-dynamics simulations. The rates are also computed by employing the stochastic dynamics method for a wide range of collision frequencies. Comparisons of the two sets of the computed rates show that for a wide range of liquid densities there is a simple linear relation between the liquid density rho and the collision frequency alpha, that is, alpha=crho. This suggests that once the constant c is determined from a molecular-dynamics calculation at a single density, the reaction rates can be obtained from stochastic dynamics calculations for the entire range of liquid densities where alpha=crho holds. The applicability of the combined molecular dynamics and stochastic dynamics approach provides a practical means for obtaining rate constants at considerable savings of computer time compared to that required by using full-dimensional molecular-dynamics simulations alone.     

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.     

Molecule-based kinetic modeling by Monte Carlo methods for heavy petroleum conversion

A methodology for kinetic modeling of conversion processes is presented.The proposed approach allows to overcome the lack of molecular detail of the petroleum fractions and to simulate the reactions of the process by means of a two-step procedure.In the first step,a synthetic mixture of molecules representing the feedstock is generated via a molecular reconstruction method,termed SR-REM molecular reconstruction.In the second step,a kinetic Monte Carlo method,termed stochastic simulation algorithm(SSA),is used to simulate the effect of the conversion reactions on the mixture of molecules.The resulting methodology is applied to the Athabasca vacuum residue hydrocracking.An adequate molecular representation of the vacuum residue is obtained using the SR-REM algorithm.The reaction simulations present a good agreement with the laboratory data for Athabasca vacuum residue conversion.In addition,the proposed methodology provides the molecular detail of the vacuum residue conversion throughout the reactions simulations.     

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.     

Global approach for calculation of minimum miscibility pressure

An algorithm has been developed for calculation of minimum miscibility pressure (MMP) for the displacement of oil by multicomponent gas injection. The algorithm is based on the key tie line identification approach initially addressed by Wang and Orr [Y. Wang and F.M. Orr Jr., Analytical calculation of minimum miscibility pressure, Fluid Phase Equilibria, 139 (1997) 101–124]. In this work a new global approach is introduced. A number of deficiencies of the sequential approach have been eliminated resulting in a robust and highly efficient algorithm. The time consumption for calculation of the MMP in multicomponent displacement processes has been reduced significantly and can now be performed within a few seconds on a PC for a 15-component gas mixture. The algorithm is hence particularly suitable for gas enrichment studies or other case studies where a large number of MMP calculations is required. Predicted results from the key tie line identification approach are shown to be in excellent agreement with slimtube data and with other multicell/slimtube simulators presented in the literature.     

How to obtain statistically converged MM/GBSA results

The molecular mechanics/generalized Born surface area (MM/GBSA) method has been investigated with the aim of achieving a statistical precision of 1 kJ/mol for the results. We studied the binding of seven biotin analogues to avidin, taking advantage of the fact that the protein is a tetramer with four independent binding sites, which should give the same estimated binding affinities. We show that it is not enough to use a single long simulation (10 ns), because the standard error of such a calculation underestimates the difference between the four binding sites. Instead, it is better to run several independent simulations and average the results. With such an approach, we obtain the same results for the four binding sites, and any desired precision can be obtained by running a proper number of simulations. We discuss how the simulations should be performed to optimize the use of computer time. The correlation time between the MM/GBSA energies is ～5 ps and an equilibration time of 100 ps is needed. For MM/GBSA, we recommend a sampling time of 20–200 ps for each separate simulation, depending on the protein. With 200 ps production time, 5–50 separate simulations are required to reach a statistical precision of 1 kJ/mol (800–8000 energy calculations or 1.5–15 ns total simulation time per ligand) for the seven avidin ligands. This is an order of magnitude more than what is normally used, but such a number of simulations is needed to obtain statistically valid results for the MM/GBSA method. © 2009 Wiley Periodicals, Inc. J Comput Chem 2010     

Reduction and solution of the chemical master equation using time scale separation and finite state projection

The dynamics of chemical reaction networks often takes place on widely differing time scales--from the order of nanoseconds to the order of several days. This is particularly true for gene regulatory networks, which are modeled by chemical kinetics. Multiple time scales in mathematical models often lead to serious computational difficulties, such as numerical stiffness in the case of differential equations or excessively redundant Monte Carlo simulations in the case of stochastic processes. We present a model reduction method for study of stochastic chemical kinetic systems that takes advantage of multiple time scales. The method applies to finite projections of the chemical master equation and allows for effective time scale separation of the system dynamics. We implement this method in a novel numerical algorithm that exploits the time scale separation to achieve model order reductions while enabling error checking and control. We illustrate the efficiency of our method in several examples motivated by recent developments in gene regulatory networks.     

Automated estimation of rare event probabilities in biochemical systems

In biochemical systems, the occurrence of a rare event can be accompanied by catastrophic consequences. Precise characterization of these events using Monte Carlo simulation methods is often intractable, as the number of realizations needed to witness even a single rare event can be very large. The weighted stochastic simulation algorithm (wSSA) [J. Chem. Phys. 129, 165101 (2008)] and its subsequent extension [J. Chem. Phys. 130, 174103 (2009)] alleviate this difficulty with importance sampling, which effectively biases the system toward the desired rare event. However, extensive computation coupled with substantial insight into a given system is required, as there is currently no automatic approach for choosing wSSA parameters. We present a novel modification of the wSSA--the doubly weighted SSA (dwSSA)--that makes possible a fully automated parameter selection method. Our approach uses the information-theoretic concept of cross entropy to identify parameter values yielding minimum variance rare event probability estimates. We apply the method to four examples: a pure birth process, a birth-death process, an enzymatic futile cycle, and a yeast polarization model. Our results demonstrate that the proposed method (1) enables probability estimation for a class of rare events that cannot be interrogated with the wSSA, and (2) for all examples tested, reduces the number of runs needed to achieve comparable accuracy by multiple orders of magnitude. For a particular rare event in the yeast polarization model, our method transforms a projected simulation time of 600 years to three hours. Furthermore, by incorporating information-theoretic principles, our approach provides a framework for the development of more sophisticated influencing schemes that should further improve estimation accuracy.     

Molecular dynamics with stochastic boundary conditions

We present and illustrate a simple approach for carrying out molecular dynamics simulations subject to stochastic boundary conditions. Methods of this type are expected to be useful in the study of chemical reactions and other localized processes in dense media.