sábado, 10 de diciembre de 2011

El Algoritmo de Doob Gillespie


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


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.

No hay comentarios:

Publicar un comentario