Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems


Sagar Indurkhya, Jacob Beal

PLoS ONE 5(1), pages e8125, 01 2010
Public Library of Science

<p>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 <inline-formula><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="info:doi/10.1371/journal.pone.0008125.e001" mimetype="image" xlink:type="simple"/></inline-formula> storage for <inline-formula><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="info:doi/10.1371/journal.pone.0008125.e002" mimetype="image" xlink:type="simple"/></inline-formula> reactions, rather than the <inline-formula><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="info:doi/10.1371/journal.pone.0008125.e003" mimetype="image" xlink:type="simple"/></inline-formula> 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.</p>

 
@article{IndurkhyaPLoSONE2010,
   author = {Indurkhya, Sagar AND Beal, Jacob},
   journal = {PLoS ONE},
   publisher = {Public Library of Science},
   title = {Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems},
   year = {2010},
   month = {01},
   volume = {5},
   url = {http://dx.doi.org/10.1371%2Fjournal.pone.0008125},
   pages = {e8125},
   abstract = {
<p>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 <inline-formula><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="info:doi/10.1371/journal.pone.0008125.e001" mimetype="image" xlink:type="simple"/></inline-formula> storage for <inline-formula><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="info:doi/10.1371/journal.pone.0008125.e002" mimetype="image" xlink:type="simple"/></inline-formula> reactions, rather than the <inline-formula><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="info:doi/10.1371/journal.pone.0008125.e003" mimetype="image" xlink:type="simple"/></inline-formula> 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.</p>
}
,
   number = {1},
   doi = {10.1371/journal.pone.0008125}
}        
 

Tags:

Publication

— authors

Sagar Indurkhya, Jacob Beal

— status

published

— sort

article in journal

Venue

— journal

PLoS ONE

— volume

5

— issue

1

— pages

e8125

— publication date

01 2010

URLs

original page

Identifiers

— DOI

10.1371/journal.pone.0008125

BibTeX

— BibTeX ID
IndurkhyaPLoSONE2010
— BibTeX category
article

Partita IVA: 01131710376 - Copyright © 2008-2022 APICe@DISI Research Group - PRIVACY