Efficient constant-time complexity algorithm for stochastic simulation of large reaction networks

Research output: Contribution to journalArticle


Research units

  • The Microsoft Research - University of Trento Centre for Computational and Systems Biology


Exact stochastic simulation is an indispensable tool for a quantitative study of biochemical reaction networks. The simulation realizes the time evolution of the model by randomly choosing a reaction to fire and update the system state according to a probability that is proportional to the reaction propensity. Two computationally expensive tasks in simulating large biochemical networks are the selection of next reaction firings and the update of reaction propensities due to state changes. We present in this work a new exact algorithm to optimize both of these simulation bottlenecks. Our algorithm employs the composition-rejection on the propensity bounds of reactions to select the next reaction firing. The selection of next reaction firings is independent of the number reactions while the update of propensities is skipped and performed only when necessary. It therefore provides a favorable scaling for the computational complexity in simulating large reaction networks. We benchmark our new algorithm with the state of the art algorithms available in literature to demonstrate its applicability and efficiency. © 2004-2012 IEEE.


Original languageEnglish
Pages (from-to)657-667
Number of pages11
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number3
Publication statusPublished - 2017
MoE publication typeA1 Journal article-refereed

    Research areas

  • Biology, Complex networks, Stochastic models, Stochastic systems, Biochemical network, Biochemical reaction network, Computational biology, Constant time complexity, Indispensable tools, State-of-the-art algorithms, Stochastic simulation algorithms, Stochastic simulations, Computational complexity, algorithm, biological model, biology, computer simulation, Markov chain, procedures, time factor, Algorithms, Computational Biology, Computer Simulation, Models, Biological, Stochastic Processes, Time Factors

ID: 27839854