Método de Montecarlo por cadenas de Markov

Método de Montecarlo por cadenas de Markov
Subclase Muestreo
Nombrado en referencia a Andreï Markov , Montecarlo

Los métodos de la cadena de Markov de Monte Carlo , o métodos MCMC para la cadena de Markov de Monte Carlo en inglés , son una clase de métodos para el muestreo de distribuciones de probabilidad. Estos métodos de Monte-Carlo se basan en el camino de las cadenas de Markov cuyas leyes estacionarias son las distribuciones a muestrear.

Algunos métodos utilizan caminatas aleatorias en cadenas de Markov ( algoritmo Metropolis-Hastings , muestreo de Gibbs ), mientras que otros algoritmos más complejos introducen restricciones en las rutas para intentar acelerar la convergencia ( Monte Carlo Hybrid  (en) , sobre-relajación sucesiva )

Estos métodos se aplican sobre todo en el marco de la inferencia bayesiana .

Enfoque intuitivo

Nos ubicamos en un espacio vectorial de dimensión finita n . Queremos generar vectores aleatoriamente según una distribución de probabilidad π . Por lo tanto, queremos tener una secuencia de vectores tal que la distribución de los enfoques π .

Los métodos de Monte-Carlo por cadenas de Markov consisten en generar un vector solo a partir de los datos del vector  ; se trata, por tanto, de un proceso "sin memoria", que caracteriza a las cadenas de Markov. Por tanto, debemos encontrar un generador aleatorio con una distribución de probabilidad que nos permita generar a partir de . Por lo tanto, reemplazamos el problema de generación con una distribución π por problemas de generación con distribuciones , que esperamos sea más simple.

Principio

Queremos simular una ley π en un espacio de estados general ( Ω  ; Ɛ ) . Una transición en ( Ω  ; Ɛ ) es un mapa P  : ( Ω  ; Ɛ ) → [0; 1] tal que P (·, A ) para todo A ∈ Ɛ es medible y P ( x , ·) para todo x ∈ Ω es una probabilidad en ( Ω  ; Ɛ ) . Deje que X  = ( X k , k ∈ℕ) una transición cadena de Markov homogénea P y inicial ley X 0  ~  v , hay P v cadena ley X .

Para simular π , queremos saber cómo construir una transición P tal que ∀  v , vP k  →  π , con la convergencia en norma en la variación total ∥ μ ∥ = sup A ∈ Ɛ μ ( A ) - inf A ∈ Ɛ μ ( A ) . La cadena de transición P es ergódica .

Convergencia de una cadena de Markov  :  si una transición P es π -reducible, π -invariante, aperiódica, recurrente de Harris, entonces ∀ x , P k ( x , ·) → k → ∞  π .

La última y delicada condición se satisface en los casos de muestreo de Gibbs y el algoritmo Metropolis-Hastings .

Métodos de muestreo

Los métodos de muestreo se utilizan para estimar la distribución posterior (completa) de los parámetros de un modelo. Entre ellos, los métodos de Monte Carlo son muy precisos. Sin embargo, son computacionalmente costosos y requieren mucho tiempo para converger. También están limitados por el tamaño de la muestra, ya que se vuelven insolubles cuando son demasiado grandes. Incluso en muestras pequeñas, calcular una distribución de probabilidad puede resultar difícil. Hay varios enfoques para este problema, que se utilizan para obtener un conjunto de buenas redes de muestreo a partir de la distribución posterior.

Construcción de redes aleatorias y búsqueda de patrones.

El método de Monte Carlo por cadenas de Markov se utiliza a menudo en algoritmos que tratan con redes (biológicas o no). Son posibles varias aplicaciones diferentes, 2 de las cuales son las principales: la generación de redes aleatorias y la clasificación de elementos en gráficos. Los ejemplos que se tomen para ilustrar el uso de MCMC de aquí en adelante se basarán en la biología.

Redes aleatorias

MCMC se utiliza muy a menudo para generar redes aleatorias que sirven como modelos nulos, lo más cerca posible del azar, manteniendo las características básicas de una red estudiada para seguir siendo comparable. Estos modelos nulos permiten luego determinar si las características de una red estudiada son estadísticamente significativas o no.

El curso del método es simple: se tienen en cuenta 2 aristas (A -> B; C -> D) y luego se considera y acepta un intercambio de los nodos de estas aristas (A -> D; C -> B) solo si los nuevos bordes no existen ya y no hay ningún borde cíclico (A -> A). El número de intercambios considerados a menudo sigue la fórmula Q x E, donde E es el número de bordes de una red real (a menudo la red estudiada) y Q es un número lo suficientemente alto como para garantizar la aleatoriedad de la red de productos, a menudo establecido en 100 .

El uso del método Monte Carlo por las cadenas de Markov para generar un modelo nulo contra el cual determinamos la importancia de uno (o más) caracteres se puede encontrar bajo el nombre de "algoritmo de conmutación", siendo el "algoritmo de coincidencia" la alternativa en la generación de redes aleatorias. Este último, que no utiliza el MCMC, también presenta como desventaja la presencia de un sesgo en las redes de productos. Estos algoritmos se utilizan con mayor frecuencia en biología para buscar patrones en redes, subgrafos compuestos por un número limitado de nodos y que se encuentran en un gran número de redes. Entre las herramientas que utilizan MCMC para generar redes aleatorias se encuentran mfinder, FANMOD, KAVOSH y NetMODE.

Búsqueda de patrones

En cuanto al uso de MCMC para la clasificación de elementos en un gráfico, se habla en particular de "Clustering de Markov" (MCL), un método de clasificación no supervisado basado en el concepto de "recorrido aleatorio", que casi no requiere información a priori para Ser capaz de clasificar los elementos de un gráfico. Más concretamente, partiendo de un nudo, si “caminamos” de nudo en nudo por los bordes, tendemos a pasar más a menudo entre nudos que están dentro del mismo grupo que a hacer un paso uniforme entre todos los nudos. Así, al aumentar la importancia de los bordes frecuentemente cruzados y disminuir la de los bordes menos cruzados, los grupos de una red se actualizan progresivamente.

Aplicación a la biología

Hay dos tipos principales de uso de MCMC en biología de sistemas , a saber, matrices de genes y dinámica molecular, que se pueden resumir como un sistema de moléculas. En ambos casos, se trata de comprender las complejas interacciones entre varios elementos. Es por eso que el método MCMC se combina con redes bayesianas.

Redes bayesianas

Las redes bayesianas se utilizan comúnmente en biología y sistemas asociados con MCMC. Proporcionan una representación ordenada y compacta de la distribución de probabilidades comunes de sistemas. Su uso en modelos gráficos tiene varias ventajas. Primero, pueden representar las relaciones / dependencias causales entre variables y, por lo tanto, pueden interpretarse como un modelo causal que genera los datos. Además, las redes bayesianas son útiles para adaptar los parámetros de un modelo de aprendizaje automático, ya sea que se utilicen para realizar predicciones o clasificación de datos. También se ha demostrado que la teoría de la probabilidad bayesiana es eficaz para describir la incertidumbre y adaptar el número de parámetros al tamaño de los datos. La representación y el uso de la teoría de la probabilidad en redes biológicas permite combinar conocimientos y datos de un dominio, expresar relaciones de causa y efecto, evitar el ajuste excesivo de un modelo para entrenar datos y aprender de conjuntos de datos incompletos.

Redes bayesianas dinámicas

La retroalimentación es una característica esencial de muchos sistemas biológicos. Lo que hace que la creación de mediciones experimentales de series de tiempo sea un desafío particularmente importante en el modelado de sistemas biológicos

Las redes bayesianas son adecuadas para modelar ciclos de retroalimentación, así como series de tiempo. Estas son las redes dinámicas bayesianas que consisten en el uso de redes bayesianas al modelar series de tiempo o ciclos de retroalimentación. En estas condiciones, las variables se indexan por tiempo y se reproducen en las redes. Los modelos ocultos de Markov y los sistemas dinámicos lineales son casos especiales de redes dinámicas bayesianas. En los modelos de Markov ocultos, hay un conjunto oculto de nodos (normalmente estados discretos), un conjunto de variables observadas y los cortes del gráfico no necesitan ser temporales. A menudo se utilizan para el análisis de secuencias, en particular en el caso de redes de genes.

Las redes dinámicas bayesianas se han utilizado para deducir interacciones reguladoras genéticas a partir de datos de chips de ADN, a partir de unas pocas docenas de puntos de tiempo de un ciclo celular. Particularmente cuando se combinó con el MCMC, esto permitió el acceso al rendimiento de inferencia de la red con diferentes tamaños de conjuntos de entrenamiento, antecedentes y estrategias de muestreo.

Redes de genes

Las redes de genes son adecuadas para modelar sistemas biológicos complejos y estocásticos. Representan la expresión de cada gen mediante una variable que describe la regulación entre genes.

En este tipo de redes, la inferencia de sus estructuras, por ejemplo, la identificación de redes de regulación y señalización a partir de datos, es el aspecto más interesante. La distinción de correlación permite dilucidar las dependencias entre las variables medidas y, por lo tanto, el aprendizaje de relaciones desconocidas y excelentes modelos predictivos. Sin embargo, el aprendizaje de las estructuras del modelo es difícil y, a menudo, requiere un diseño experimental cuidadoso.

Dinámica molecular

El método clásico para simular la evolución de las moléculas que reaccionan a lo largo del tiempo se basa en la hipótesis del continuo. Cuando el número de estas moléculas que reaccionan en un conjunto de reacciones es del orden del número de Avogadro, podemos asumir que esta concentración (número de moléculas en el conjunto) es una variable real continua. En este caso, la cinética clásica de acción de masas se puede utilizar para describir las velocidades de reacción. Sin embargo, cuando el número de estas moléculas es del orden de cientos o miles, ya no podemos utilizar la hipótesis del continuo. Por lo tanto, en lugar de concentraciones con valores reales, debemos considerar el número de moléculas con valores enteros. Otro efecto del bajo número de moléculas es que la cinética clásica de acción de masas ya no es válida. Las tasas de reacción ya no son deterministas, por lo que se necesita un enfoque probabilístico. En lugar de tener en cuenta la cantidad de reactivos consumidos y productos producidos en un intervalo de tiempo, debemos considerar la probabilidad de que ocurra una reacción en un intervalo de tiempo. Este enfoque para modelar reacciones se conoce como cinética estocástica.

Ejemplos en biología de sistemas

Los procesos celulares en la biología de sistemas suelen ser aleatorios debido al bajo número de moléculas que reaccionan.

Estimación de parámetros por MCMC

La cinética estocástica se ha convertido en un elemento básico para el modelado de diversos fenómenos en biología de sistemas. Estos modelos, incluso más que los modelos deterministas, plantean un problema difícil en la estimación de parámetros cinéticos a partir de datos experimentales. Inicialmente, los parámetros se establecieron en valores biológicamente plausibles, luego se ajustaron a simple vista para que la simulación del modelo se asemejara a los datos experimentales. En este caso, las estimaciones de los parámetros se pueden obtener fácilmente mediante un ajuste por mínimos cuadrados o mediante una estimación de máxima verosimilitud. Sin embargo, el uso de métodos estadísticos de Monte Carlo permite mantener la estocasticidad del modelo al estimar estos parámetros. Estos métodos de estimación se pueden clasificar en dos categorías bien conocidas: métodos de máxima verosimilitud y métodos de inferencia bayesiana.

Los métodos de inferencia bayesiana intentan obtener la distribución posterior de los parámetros, que luego se puede maximizar para obtener estimaciones posteriores máximas. La mayoría de los métodos de inferencia bayesianos se basan en técnicas MCMC. La aplicación a la biología de sistemas no es una excepción:

Ver también

Bibliografía

Artículos relacionados

Otro muestreo de distribución

Notas y referencias

  1. (en) R. Milo , N. Kashtan , S. Itzkovitz y MEJ Newman , “  en la generación uniforme de grafos aleatorios con secuencias grado prescrito  ” , arXiv: cond-mat / 0312028 ,30 de mayo de 2004( leer en línea , consultado el 11 de febrero de 2021 )
  2. (en) NTL Tran , S. Mohan , Z. Xu y C.-H. Huang , "  Innovaciones actuales y desafíos futuros de la detección de motivos de red  " , Briefings in Bioinformatics , vol.  16, n o  3,1 st de mayo de el año 2015, p.  497-525 ( ISSN  1467-5463 y 1477-4054 , DOI  10.1093 / bib / bbu021 , leído en línea , consultado el 11 de febrero de 2021 )
  3. (in) N. Kashtan S. Itzkovitz , R. Milo y U. Alon , "  Algoritmo de muestreo eficiente para estimar concentraciones subgraficas y Detectar motivos de red  " , Bioinformática , vol.  20, n o  11,22 de julio de 2004, p.  1746-1758 ( ISSN  1367-4803 y 1460-2059 , DOI  10.1093 / bioinformatics / bth163 , leído en línea , consultado el 11 de febrero de 2021 )
  4. (in) S. Wernicke y F. Rasche , "  FANMOD una herramienta para la detección rápida de patrones de red  " , Bioinformática , vol.  22, n o  9,1 st de mayo de de 2006, p.  1152-1153 ( ISSN  1367-4803 y 1460-2059 , DOI  10.1093 / bioinformatics / btl038 , leído en línea , consultado el 11 de febrero de 2021 )
  5. (en) Zahra Razaghi Moghadam Kashani , Hayedeh Ahrabian , Elahe Elahi y Abbas Nowzari-Dalini , "  Kavosh: un nuevo algoritmo para encontrar motivos de red  " , BMC Bioinformatics , vol.  10, n o  1,4 de octubre de 2009, p.  318 ( ISSN  1471-2105 , PMID  19799800 , PMCID  PMC2765973 , DOI  10.1186 / 1471-2105-10-318 , leído en línea , consultado el 11 de febrero de 2021 )
  6. (en) Xin Li , Rebecca J. Stones , Haidong Wang y Hualiang Deng , "  NetMODE: Red de detección de patrones sin Nauty  " , PLoS ONE , vol.  7, n o  12,18 de diciembre de 2012, e50093 ( ISSN  1932-6203 , PMID  23272055 , PMCID  PMC3525646 , DOI  10.1371 / journal.pone.0050093 , leído en línea , consultado el 11 de febrero de 2021 )
  7. (en) Stijn van Dongen, "  Agrupación de gráficos por simulación de flujo  " , tesis de doctorado, Universidad de Utrecht ,Mayo de 2000
  8. Husmeier, Dirk. , Modelado probabilístico en bioinformática e informática médica , Springer-Verlag London Limited,2005( ISBN  978-1-84628-119-8 y 1-84628-119-9 , OCLC  981318762 , leer en línea )
  9. (in) Ankur Gupta y James B. Rawlings , "  Comparación de métodos de estimación de parámetros en modelos cinéticos químicos estocásticos: ejemplos en biología de sistemas  " , AIChE Journal , vol.  60, n o  4,abril de 2014, p.  1253–1268 ( PMID  27429455 , PMCID  PMC4946376 , DOI  10.1002 / aic.14409 , leído en línea , consultado el 14 de febrero de 2021 )
  10. Michael B. Elowitz , Arnold J. Levine , Eric D. Siggia y Peter S. Swain , "  Expresión genética estocástica en una sola célula  ", Science (Nueva York, NY) , vol.  297, n o  5584,16 de agosto de 2002, p.  1183-1186 ( ISSN  1095-9203 , PMID  12183631 , DOI  10.1126 / science.1070919 , leído en línea , consultado el 14 de febrero de 2021 )
  11. William J. Blake , Mads KAErn , Charles R. Cantor y JJ Collins , "  Ruido en la expresión génica eucariota  ", Nature , vol.  422, n o  6932,10 de abril de 2003, p.  633–637 ( ISSN  0028-0836 , PMID  12687005 , DOI  10.1038 / nature01546 , leído en línea , consultado el 14 de febrero de 2021 )
  12. Jonathan M. Raser y Erin K. O'Shea , "  Control de la estocasticidad en la expresión génica eucariota  ", Science (Nueva York, NY) , vol.  304, n o  5678,18 de junio de 2004, p.  1811–1814 ( ISSN  1095-9203 , PMID  15166317 , PMCID  1410811 , DOI  10.1126 / science.1098641 , leído en línea , consultado el 14 de febrero de 2021 )
  13. HH McAdams y A. Arkin , "  Mecanismos estocásticos en la expresión génica  ", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , vol.  94, n o  3,4 de febrero de 1997, p.  814–819 ( ISSN  0027-8424 , PMID  9023339 , PMCID  PMC19596 , DOI  10.1073 / pnas.94.3.814 , leído en línea , consultado el 14 de febrero de 2021 )
  14. A. Arkin , J. Ross y HH McAdams , “  análisis cinético estocástico de desarrollo vía de bifurcación en el fago células de Escherichia coli infectadas con lambda  ”, Genética , vol.  149, n o  4,Agosto de 1998, p.  1633–1648 ( ISSN  0016-6731 , PMID  9691025 , PMCID  1460268 , leído en línea , consultado el 14 de febrero de 2021 )
  15. Leor S. Weinberger , John C. Burnett , Jared E. Toettcher y Adam P. Arkin , "  Expresión de genes estocásticos en un bucle de retroalimentación positiva lentiviral: las fluctuaciones de Tat del VIH-1 impulsan la diversidad fenotípica  ", Cell , vol.  122, n o  229 de julio de 2005, p.  169–182 ( ISSN  0092-8674 , PMID  16051143 , DOI  10.1016 / j.cell.2005.06.006 , leído en línea , consultado el 14 de febrero de 2021 )
  16. Sebastian C. Hensel , James B. Rawlings y John Yin , “  Modelado cinético estocástico del crecimiento intracelular del virus de la estomatitis vesicular  ”, Boletín de Biología Matemática , vol.  71, n o  7,octubre de 2009, p.  1671–1692 ( ISSN  1522-9602 , PMID  19459014 , PMCID  3169382 , DOI  10.1007 / s11538-009-9419-5 , leído en línea , consultado el 14 de febrero de 2021 )
  17. Grzegorz A. Rempała , Kenneth S. Ramos y Ted Kalbfleisch , “  Un modelo estocástico de la transcripción de genes: una aplicación a eventos L1 retrotransposition  ”, Journal of Theoretical Biology , vol.  242, n o  1,7 de septiembre de 2006, p.  101-116 ( ISSN  0022-5193 , PMID  16624324 , DOI  10.1016 / j.jtbi.2006.02.010 , leído en línea , consultado el 14 de febrero de 2021 )
  18. Daniel A. Henderson , Richard J. Niños , Kim J. Krishnan y Conor Lawless , “  bayesiano emulación y la calibración de un modelo estocástico ordenador de ADN mitocondrial deleciones en sustancia negra neuronas  ”, Revista de la Asociación Americana de Estadística , vol .  104, n o  485,Marzo de 2009, p.  76–87 ( ISSN  0162-1459 y 1537-274X , DOI  10.1198 / jasa.2009.0005 , leído en línea , consultado el 14 de febrero de 2021 )
  19. A. Golightly y DJ Wilkinson , "  Inferencia bayesiana para modelos de difusión multivariante no lineales observados con error  ", Estadística computacional y análisis de datos , vol.  52, n o  3,Enero de 2008, p.  1674–1693 ( ISSN  0167-9473 , DOI  10.1016 / j.csda.2007.05.019 , leído en línea , consultado el 14 de febrero de 2021 )
  20. (en) Darren J. Wilkinson , Modelado estocástico para biología de sistemas , 3,7 de diciembre de 2018( ISBN  9781351000918 , DOI  10.1201 / 9781351000918 , leer en línea )
  21. Andrew Golightly y Darren J. Wilkinson , “  inferencia bayesiana parámetro para modelos de red bioquímicos estocásticos utilizando partícula cadena de Markov Monte Carlo  ”, Interface Focus , vol.  1, n o  6,6 de diciembre de 2011, p.  807–820 ( ISSN  2042-8901 , PMID  23226583 , PMCID  3262293 , DOI  10.1098 / rsfs.2011.0047 , leído en línea , consultado el 14 de febrero de 2021 )
  22. Andrew Golightly y Darren J. Wilkinson , "  Inferencia secuencial bayesiana para modelos de redes bioquímicas cinéticas estocásticas  ", Revista de Biología Computacional: Una Revista de Biología Celular Molecular Computacional , vol.  13, n o  3,Abril de 2006, p.  838–851 ( ISSN  1066-5277 , PMID  16706729 , DOI  10.1089 / cmb.2006.13.838 , leído en línea , consultado el 14 de febrero de 2021 )
  23. Tommaso Mazza , Gennaro Iaccarino y Corrado Priami , “  Snazer: el analizador de simulaciones y redes  ”, Biología de sistemas BMC , vol.  4,7 de enero de 2010, p.  1 ( ISSN  1752-0509 , PMID  20056001 , PMCID  2880970 , DOI  10.1186 / 1752-0509-4-1 , leído en línea , consultado el 14 de febrero de 2021 )
  24. S. Reinker , RM Altman y J. Timmer , “  Estimación de parámetros en las reacciones bioquímicas estocásticos  ”, IEE Proceedings - Biología de Sistemas , vol.  153, n o  4,2006, p.  168 ( ISSN  1741-2471 , DOI  10.1049 / ip-syb: 20050105 , leído en línea , consultado el 14 de febrero de 2021 )
  25. Ido Golding , Johan Paulsson , Scott M. Zawilski y Edward C. Cox , "  Cinética en tiempo real de la actividad genética en bacterias individuales  ", Cell , vol.  123, n o  6,16 de diciembre de 2005, p.  1025-1036 ( ISSN  0092-8674 , PMID  16360033 , DOI  10.1016 / j.cell.2005.09.031 , leído en línea , consultado el 14 de febrero de 2021 )
  26. Suresh Kumar Poovathingal y Rudiyanto Gunawan , “  Métodos de estimación de parámetros globales para sistemas bioquímicos estocásticos  ”, BMC Bioinformatics , vol.  11, n o  1,6 de agosto de 2010( ISSN  1471-2105 , DOI  10.1186 / 1471-2105-11-414 , leído en línea , consultado el 14 de febrero de 2021 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">