Efficient stochastic sampling of first-passage times with applications to self-assembly simulations

Models of reaction chemistry based on the stochastic simulation algorithm (SSA) have become a crucial tool for simulating complicated biological reaction networks due to their ability to handle extremely complicated networks and to represent noise in small-scale chemistry. These methods can, however, become highly inefficient for stiff reaction systems, those in which different reaction channels operate on widely varying time scales. In this paper, we develop two methods for accelerating sampling in SSA models: an exact method and a scheme allowing for sampling accuracy up to any arbitrary error bound. Both methods depend on the analysis of the eigenvalues of continuous time Markov models that define the behavior of the SSA. We show how each can be applied to accelerate sampling within known Markov models or to subgraphs discovered automatically during execution. We demonstrate these methods for two applications of sampling in stiff SSAs that are important for modeling self-assembly reactions: sampling breakage times for multiply connected bond networks and sampling assembly times for multisubunit nucleation reactions. We show theoretically and empirically that our eigenvalue methods provide substantially reduced sampling times for a large class of models used in simulating self-assembly. These techniques are also likely to have broader use in accelerating SSA models so as to apply them to systems and parameter ranges that are currently computationally intractable.