El Algoritmo de Doob Gillespie

Fuente:
http://planetafisico.blogspot.com/2011/12/el-algoritmo-de-doob-gillespie.html

En la teoría de probabilidad, el algoritmo de Gillespie (u ocasionalmente el algoritmo de Doob-Gillespie) genera una trayectoria estadísticamente correcta (una posible solución) de una ecuación estocástica. Fue creado por Joseph L. Doob y otros (circa 1945) y popularizado por Dan Gillespie en 1977 en un articulo donde se utiliza para simular sistemas químicos o bioquímicos de reacciones de manera eficiente y precisa usando un limitado poder computacional. A medida que las computadoras se hicieron más rápidas, el algoritmo se empezó a utilizar para resolver sistemas complejos. Matemáticamente, es una variación del método de Monte Carlo dinámico y similar al método de Monte Carlo cinético y es ampliamente utilizado en sistemas biológicos computacionales.

HISTORIA

El proceso que condujo al algoritmo reconoce varios pasos importantes. En 1931, Andrei Kolmogorov introduce las ecuaciones diferenciales correspondientes a los tiempos de evolución de los procesos estocásticos que proceden por saltos, que hoy en día se conoce como la ecuación de Kolmogorov (proceso de saltos de Markov) (una versión simplificada que se conoce como ecuación maestra en ciencias naturales). Fue William Feller, en 1940, que encontró bajo que condiciones la ecuación de Kolmogorov admite probabilidades como soluciones. En su teorema I (en su trabajo de 1940) establece que el siguiente tiempo de salto esta distribuido exponencialmente y la probabilidad del siguiente evento es proporcional a la velocidad. Como tal, establece la relación de la ecuación de Kolmogorov con los procesos estocásticos. Más tarde, Doob (1942,1945) extiende las soluciones de Feller mas allá del caso de los procesos de puros saltos. El método fue implementado computacionalmente por David George Kendall (en 1950) usando una computadora Manchester Mark I y después fue usado por M.S. Bartlett (en 1953) en su estudio de brotes epidémicos. Gillespie (en 1977) trabajo haciendo caso omiso de esta historia como el escribe “Cabe destacar, sin embargo, que la ecuación maestra en si no juega ningún rol en la derivación o en la implementación del algoritmo de simulación estocástica”. Gillespie entonces procede a través de un argumento heurístico para introducir el algoritmo.

IDEA DETRÁS DEL ALGORITMO

Tradicionalmente las ecuaciones de velocidad continuas y determinista no predicen con precisión la reacciones celulares ya que se basan en las reacciones a granel que requieren la interacción de millones de moléculas. Que son típicamente modeladas con un conjunto de ecuaciones diferenciales ordinarias acopladas. Por el contrario, el algoritmo de Gillespie permite una simulación discreta y estocástica de un sistema con pocos reactivos debido a que cada reacción es simulada explícitamente. Cuando se simula, una realización de Gillespie describe a un camino aleatorio que representa exactamente la distribución de la ecuación maestra.

La base física del algoritmo son las colisiones de las moléculas dentro un recipiente de reacción. Se supone que las colisiones son frecuentes, pero las colisiones con la orientación y la energía correcta son poco frecuentes. Por lo tanto, todas las reacciones en el marco de Gillespie deben involucrar a lo más dos moléculas. La reacciones que involucran tres moléculas se suponen que son muy raras y son modeladas como una sucesión de reacciones binarias. También se supone que el medio ambiente de la reacción esta bien mezclado.

ALGORITMO

Gillespie desarrolla dos formulaciones distintas pero equivalentes: el método directo y el método de la primera reacción. A continuación se muestra un resumen de los pasos para ejecutar el algoritmo (la matemáticas se omite):

1. Inicialización: Se inicializa el número de moléculas del sistema, las constantes de reacción y el generador de números aleatorios.
2. Paso de Monte Carlo: Se genera dos números aleatorios para determinar la siguiente reacción que ocurrirá y el intervalo de tiempo. La probabilidad de una reacción dada para ser elegido es proporcional al número de moléculas de sustrato.
3. Actualización: Se incrementa el paso del tiempo por el tiempo generado aleatoriamente en el paso 2 y se actualiza las moléculas basadas en la reacción que ocurrió.
4. Iteración: Se vuelve al paso 2 al menos que el numero de moléculas sea igual a cero o el tiempo de simulación se ha excedido.

ALGUNAS SIMULACIONES OBTENIDAS CON EL ALGORITMO

LECTURA RECOMENDADAS

• Daniel T. Gillespie (1977). "Exact Stochastic Simulation of Coupled Chemical Reactions". The Journal of Physical Chemistry 81 (25): 2340–2361. doi:10.1021/j100540a008.
• Daniel T. Gillespie (1976). "A General Method for Numerically Simulating the Stochastic Time Evolution of Coupled Chemical Reactions". Journal of Computational Physics 22 (4): 403–434. doi:10.1016/0021-9991(76)90041-3.
• Jacob L. Doob (1942). "Topics in the Theory of Markoff Chains". Transactions of the American Mathematical Society 52 (1): 37–64. doi:10.1090/S0002-9947-1942-0006633-7. JSTOR 1990152.
• Jacob L. Doob (1945). "Markoff chains – Denumerable case". Transactions of the American Mathematical Society 58 (3): 455–473. doi:10.2307/1990339. JSTOR 1990339.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 17.7. Stochastic Simulation of Chemical Reaction Networks". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. http://apps.nrbook.com/empanel/index.html#pg=946.
• A Kolmogorov (1931). "Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung". Mathematische Annalen 104: 415. doi:10.1007/BF01457949. http://www.springerlink.com/content/v724507673277262/fulltext.pdf.
• W Feller (1940). "On the Integro-Differential Equations of Purely Discontinous Markoff Processes". Transactions of the American Mathematical Society 48 (3): 4885–15. JSTOR 1970064.
• David G. Kendall (1950). "An Artificial Realization of a Simple "Birth-and-Death" Process". Journal of the Royal Statistical Society. Series B (Methodological), 12 (1): 116–119. JSTOR 2983837.
• Maurice S. Bartlett (1953). "Stochastic Processes or the Statistics of Change". : Journal of the Royal Statistical Society. Series C (Applied Statistics), 2 (1): 44–64. JSTOR 2985327.
• M. Rathinam, L. R. Petzold, Y. Cao, and Daniel T. Gillespie, (2003). "Stiffness in stochastic chemically reacting systems: The implicit tau-leaping method". Journal of Chemical Physics 119 (24): 12784–12794. doi:10.1063/1.1627296.
• Sinitsyn, NA; Hengartner, N; Nemenman, I (2009). "Adiabatic coarse-graining and simulations of stochastic biochemical networks". Proceed. Nat. Acad. Science U. S. A. 106 (20): 10546–10551. doi:10.1073/pnas.0809340106. PMC 2705573. PMID 19525397. http://www.menem.com/~ilya/wiki/images/1/18/Sinitsyn-etal-09.pdf.
• M. A. Gibson and J. Bruck, (2000). "Efficient Exact Stochastic Simulation of Chemical Systems with Many Species and Many Channels". J. Phys. Chem. A 104 (9): 1876–1889. doi:10.1021/jp993732q. http://www.cs.caltech.edu/courses/cs191/paperscs191/JPhysChemA(2000-104)1876.pdf.
• Salis, H; Kaznessis, Y (2005). "Accurate hybrid stochastic simulation of a system of coupled chemical or biochemical reactions". Journal of Chemical Physics 122 (5): 054103. doi:10.1063/1.1835951. PMID 15740306.
• (Slepoy 2008): Slepoy, A; Thompson, AP; Plimpton, SJ (2008). "A constant-time kinetic Monte Carlo algorithm for simulation of large biochemical reaction networks". Journal of Chemical Physics 128 (20): 205101. doi:10.1063/1.2919546. PMID 18513044.
• (Bratsun 2005): D. Bratsun, D. Volfson, J. Hasty, L. Tsimring, (2005). "Delay-induced stochastic oscillations in gene regulation". PNAS 102 (41): 14593–8. doi:10.1073/pnas.0503858102. PMC 1253555. PMID 16199522. http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pmcentrez&artid=1253555.
• (Barrio 2005): M. Barrio, K. Burrage, A. Leier and T. Tian, (2006). "Oscillatory Regulation of Hes1: Discrete Stochastic Delay Modelling and Simulation". PLoS Comput Biol 2 (9): 1017. doi:10.1371/journal.pcbi.0020117. PMC 1560403. PMID 16965175. http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pmcentrez&artid=1560403.
• (Cai 2007): X. Cai, (2007). "Exact stochastic simulation of coupled chemical reactions with delays". J. Chem. Phys. 126 (12): 124108. doi:10.1063/1.2710253. PMID 17411109.
• (Barnes 2010): D. Barnes, D. Chu, (2010). Introduction to Modelling for Biosciences. Springer Verlag.

• (Ramaswamy 2009): R. Ramaswamy, N. Gonzalez-Segredo, I. F. Sbalzarini, (2009). "A new class of highly efficient exact stochastic simulation algorithms for chemical reaction networks". J. Chem. Phys. 130 (24): 244104. doi:10.1063/1.3154624. PMID 19566139.
• (Ramaswamy 2010): R. Ramaswamy, I. F. Sbalzarini, (2010). "A partial-propensity variant of the composition-rejection stochastic simulation algorithm for chemical reaction networks". J. Chem. Phys. 132 (4): 044102. doi:10.1063/1.3297948. PMID 20113014.
• (Indurkhya 2010): S. Indurkhya, J. Beal, (2005). Isalan, Mark. ed. "Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems". PLoS ONE 5 (1): e8125. doi:10.1371/journal.pone.0008125. PMC 2798956. PMID 20066048. http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pmcentrez&artid=2798956.
• (Ramaswamy 2011): R. Ramaswamy, I. F. Sbalzarini, (2011). "A partial-propensity formulation of the stochastic simulation algorithm for chemical reaction networks with delays". J. Chem. Phys. 134 (1): 014106. doi:10.1063/1.3521496. PMID 21218996

Si te ha gustado este artículo, compártelo en facebook, twitter, google+, coméntalo, envíalo por correo, y si quieres mas información, pídela. Si quieres recibir estos artículos por correo electrónico, subscríbete a este blog usando la opción que está en el panel derecho. Finalmente, si no te ha gustado, critícalo. Tu tienes completo control sobre los contenidos de este blog.