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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Sagar Indurkhya, Jacob Beal
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2010
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/4602820133f24bfe84e72c5d172c0e3a
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:4602820133f24bfe84e72c5d172c0e3a
record_format	dspace
spelling	oai:doaj.org-article:4602820133f24bfe84e72c5d172c0e3a2021-11-25T06:26:53ZReaction factoring and bipartite update graphs accelerate the Gillespie Algorithm for large-scale biochemical systems.1932-620310.1371/journal.pone.0008125https://doaj.org/article/4602820133f24bfe84e72c5d172c0e3a2010-01-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/pmid/20066048/?tool=EBIhttps://doaj.org/toc/1932-6203ODE 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.Sagar IndurkhyaJacob BealPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 5, Iss 1, p e8125 (2010)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Sagar Indurkhya Jacob Beal Reaction factoring and bipartite update graphs accelerate the Gillespie Algorithm for large-scale biochemical systems.
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 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.
format	article
author	Sagar Indurkhya Jacob Beal
author_facet	Sagar Indurkhya Jacob Beal
author_sort	Sagar Indurkhya
title	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_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_sort	reaction factoring and bipartite update graphs accelerate the gillespie algorithm for large-scale biochemical systems.
publisher	Public Library of Science (PLoS)
publishDate	2010
url	https://doaj.org/article/4602820133f24bfe84e72c5d172c0e3a
work_keys_str_mv	AT sagarindurkhya reactionfactoringandbipartiteupdategraphsacceleratethegillespiealgorithmforlargescalebiochemicalsystems AT jacobbeal reactionfactoringandbipartiteupdategraphsacceleratethegillespiealgorithmforlargescalebiochemicalsystems
_version_	1718413677845020672

Reaction factoring and bipartite update graphs accelerate the Gillespie Algorithm for large-scale biochemical systems.

Ejemplares similares