Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems
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 biologica...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Public Library of Science
2010
|
| Online Access: | http://hdl.handle.net/1721.1/55387 https://orcid.org/0000-0002-1663-5102 https://orcid.org/0000-0001-9595-252X |
| _version_ | 1826202584192385024 |
|---|---|
| author | Indurkhya, Sagar Beal, Jacob S. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Indurkhya, Sagar Beal, Jacob S. |
| author_sort | Indurkhya, Sagar |
| collection | MIT |
| description | 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 O(n) storage for n reactions, rather than the O(n[superscript 2]) 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. |
| first_indexed | 2024-09-23T12:09:57Z |
| format | Article |
| id | mit-1721.1/55387 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:09:57Z |
| publishDate | 2010 |
| publisher | Public Library of Science |
| record_format | dspace |
| spelling | mit-1721.1/553872022-09-28T00:36:33Z Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems Indurkhya, Sagar Beal, Jacob S. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Beal, Jacob S. Indurkhy, Sagar Beal, Jacob S. 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 O(n) storage for n reactions, rather than the O(n[superscript 2]) 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. National Science Foundation (Grant 6898853) 2010-06-03T18:56:25Z 2010-06-03T18:56:25Z 2010-01 2009-05 Article http://purl.org/eprint/type/JournalArticle 1932-6203 http://hdl.handle.net/1721.1/55387 Indurkhya, Sagar, and Jacob Beal. “Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems.” PLoS ONE 5.1 (2010): e8125. © 2010 Indurkhya, Beal. https://orcid.org/0000-0002-1663-5102 https://orcid.org/0000-0001-9595-252X en_US http://dx.doi.org/10.1371/journal.pone.0008125 PloS one Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Public Library of Science PLoS |
| spellingShingle | Indurkhya, Sagar Beal, Jacob S. Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems |
| title | Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems |
| title_full | Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems |
| title_fullStr | Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems |
| title_full_unstemmed | Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems |
| title_short | Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems |
| title_sort | reaction factoring and bipartite update graphs accelerate the gillespie algorithm for large scale biochemical systems |
| url | http://hdl.handle.net/1721.1/55387 https://orcid.org/0000-0002-1663-5102 https://orcid.org/0000-0001-9595-252X |
| work_keys_str_mv | AT indurkhyasagar reactionfactoringandbipartiteupdategraphsacceleratethegillespiealgorithmforlargescalebiochemicalsystems AT bealjacobs reactionfactoringandbipartiteupdategraphsacceleratethegillespiealgorithmforlargescalebiochemicalsystems |