Constant-complexity stochastic simulation algorithm with optimal binning

Kevin R. Sanft, Hans G. Othmer

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


At the molecular level, biochemical processes are governed by random interactions between reactant molecules, and the dynamics of such systems are inherently stochastic. When the copy numbers of reactants are large, a deterministic description is adequate, but when they are small, such systems are often modeled as continuous-time Markov jump processes that can be described by the chemical master equation. Gillespie's Stochastic Simulation Algorithm (SSA) generates exact trajectories of these systems, but the amount of computational work required for each step of the original SSA is proportional to the number of reaction channels, leading to computational complexity that scales linearly with the problem size. The original SSA is therefore inefficient for large problems, which has prompted the development of several alternative formulations with improved scaling properties. We describe an exact SSA that uses a table data structure with event time binning to achieve constant computational complexity with respect to the number of reaction channels for weakly coupled reaction networks. We present a novel adaptive binning strategy and discuss optimal algorithm parameters. We compare the computational efficiency of the algorithm to existing methods and demonstrate excellent scaling for large problems. This method is well suited for generating exact trajectories of large weakly coupled models, including those that can be described by the reaction-diffusion master equation that arises from spatially discretized reaction-diffusion processes.

Original languageEnglish (US)
Article number074108
JournalJournal of Chemical Physics
Issue number7
StatePublished - Aug 21 2015

Bibliographical note

Publisher Copyright:
© 2015 AIP Publishing LLC.


Dive into the research topics of 'Constant-complexity stochastic simulation algorithm with optimal binning'. Together they form a unique fingerprint.

Cite this