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

V.H. Thanh, R. Zunino, C. Priami

Research output: Contribution to journalArticleScientificpeer-review


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
Issue number3
Publication statusPublished - 2017
MoE publication typeA1 Journal article-refereed


  • 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


Dive into the research topics of 'Efficient constant-time complexity algorithm for stochastic simulation of large reaction networks'. Together they form a unique fingerprint.

Cite this