Journal article
Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems
PloS one, Vol.5(1), pp.e8125-e8125
01/06/2010
DOI: 10.1371/journal.pone.0008125
PMCID: PMC2798956
PMID: 20066048
Abstract
ODE simulations of chemical systems perform poorly when some of the species have extremely low concentrations. Stochastic simulation methods, which can handle this case, have been impractical for large systems due to computational complexity. We observe, however, that when modeling complex biological systems: (1) a small number of reactions tend to occur a disproportionately large percentage of the time, and (2) a small number of species tend to participate in a disproportionately large percentage of reactions. We exploit these properties in LOLCAT Method, a new implementation of the Gillespie Algorithm. First, factoring reaction propensities allows many propensities dependent on a single species to be updated in a single operation. Second, representing dependencies between reactions with a bipartite graph of reactions and species requires only
storage for
reactions, rather than the
required for a graph that includes only reactions. Together, these improvements allow our implementation of LOLCAT Method to execute orders of magnitude faster than currently existing Gillespie Algorithm variants when simulating several yeast MAPK cascade models.
Details
- Title: Subtitle
- Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems
- Creators
- Sagar Indurkhya - Massachusetts Institute of TechnologyJacob Beal - Center for Genomic Regulation, Spain
- Resource Type
- Journal article
- Publication Details
- PloS one, Vol.5(1), pp.e8125-e8125
- Publisher
- Public Library of Science
- DOI
- 10.1371/journal.pone.0008125
- PMID
- 20066048
- PMCID
- PMC2798956
- ISSN
- 1932-6203
- eISSN
- 1932-6203
- Alternative title
- Factored SSA
- Language
- English
- Date published
- 01/06/2010
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984627247502771
Metrics
6 Record Views