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.

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.

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.

Refining the weighted stochastic simulation algorithm.

The weighted stochastic simulation algorithm (wSSA) recently introduced by Kuwahara and Mura [J. Chem. Phys. 129, 165101 (2008)] is an innovative variation on the stochastic simulation algorithm (SSA). It enables one to estimate, with much less computational effort than was previously thought possible using a Monte Carlo simulation procedure, the probability that a specified event will occur in a chemically reacting system within a specified time when that probability is very small. This paper presents some procedural extensions to the wSSA that enhance its effectiveness in practical applications. The paper also attempts to clarify some theoretical issues connected with the wSSA, including its connection to first passage time theory and its relation to the SSA.

Effect of excluded volume on 2D discrete stochastic chemical kinetics.

The Stochastic Simulation Algorithm (SSA) is widely used in the discrete stochastic simulation of chemical kinetics. The propensity functions which play a central role in this algorithm have been derived under the point-molecule assumption, i.e., that the total volume of the molecules is negligible compared to the volume of the container. It has been shown analytically that for a one dimensional system and the A+A reaction, when the point molecule assumption is relaxed, the propensity function need only be adjusted by replacing the total volume of the system with the free volume of the system. In this paper we investigate via numerical simulations the impact of relaxing the point-molecule assumption in two dimensions. We find that the distribution of times to the first collision is close to exponential in most cases, so that the formalism of the propensity function is still applicable. In addition, we find that the area excluded by the molecules in two dimensions is usually higher than their close-packed area, requiring a larger correction to the propensity function than just the replacement of the total volume by the free volume.

The multinomial simulation algorithm for discrete stochastic simulation of reaction-diffusion systems.

The Inhomogeneous Stochastic Simulation Algorithm (ISSA) is a variant of the stochastic simulation algorithm in which the spatially inhomogeneous volume of the system is divided into homogeneous subvolumes, and the chemical reactions in those subvolumes are augmented by diffusive transfers of molecules between adjacent subvolumes. The ISSA can be prohibitively slow when the system is such that diffusive transfers occur much more frequently than chemical reactions. In this paper we present the Multinomial Simulation Algorithm (MSA), which is designed to, on the one hand, outperform the ISSA when diffusive transfer events outnumber reaction events, and on the other, to handle small reactant populations with greater accuracy than deterministic-stochastic hybrid algorithms. The MSA treats reactions in the usual ISSA fashion, but uses appropriately conditioned binomial random variables for representing the net numbers of molecules diffusing from any given subvolume to a neighbor within a prescribed distance. Simulation results illustrate the benefits of the algorithm.

The subtle business of model reduction for stochastic chemical kinetics.

This paper addresses the problem of simplifying chemical reaction networks by adroitly reducing the number of reaction channels and chemical species. The analysis adopts a discrete-stochastic point of view and focuses on the model reaction set S(1)<=>S(2)-->S(3), whose simplicity allows all the mathematics to be done exactly. The advantages and disadvantages of replacing this reaction set with a single S(3)-producing reaction are analyzed quantitatively using novel criteria for measuring simulation accuracy and simulation efficiency. It is shown that in all cases in which such a model reduction can be accomplished accurately and with a significant gain in simulation efficiency, a procedure called the slow-scale stochastic simulation algorithm provides a robust and theoretically transparent way of implementing the reduction.

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.