Método de Monte-Carlo por cadeias de Markov

Método de Monte-Carlo por cadeias de Markov
Subclasse Amostragem
Nomeado em referência a Andreï Markov , Monte-Carlo

Os métodos da cadeia de Markov de Monte Carlo , ou métodos MCMC para a Cadeia de Markov Monte Carlo em inglês , são uma classe de métodos para amostragem de distribuições de probabilidade. Esses métodos de Monte-Carlo são baseados no caminho de cadeias de Markov cujas leis estacionárias são as distribuições a serem amostradas.

Alguns métodos usam passeios aleatórios em cadeias de Markov ( algoritmo de Metropolis-Hastings , amostragem de Gibbs ), enquanto outros, algoritmos mais complexos, introduzem restrições nos caminhos para tentar acelerar a convergência ( Monte Carlo Hybrid  (en) , sobre-relaxamento sucessivo )

Esses métodos são notadamente aplicados no âmbito da inferência bayesiana .

Abordagem intuitiva

Nós nos colocamos em um espaço vetorial de dimensão finita n . Queremos gerar vetores aleatoriamente de acordo com uma distribuição de probabilidade π . Queremos, portanto, ter uma sequência de vetores tal que a distribuição de se aproxime de π .

Os métodos de Monte-Carlo de cadeia de Markov consistem em gerar um vetor apenas a partir dos dados do vetor  ; é, portanto, um processo “sem memória”, o que caracteriza as cadeias de Markov. Devemos, portanto, encontrar um gerador aleatório com uma distribuição de probabilidade que nos permita gerar a partir de . Assim, substituímos o problema de geração com uma distribuição π por problemas de geração com distribuições , que esperamos que sejam mais simples.

Princípio

Queremos simular uma lei π em um espaço de estado geral ( Ω  ; Ɛ ) . Uma transição em ( Ω  ; Ɛ ) é um mapa P  : ( Ω  ; Ɛ ) → [0; 1] tal que P (·, A ) para todo A ∈ Ɛ é mensurável e P ( x , ·) para todo x ∈ Ω é uma probabilidade em ( Ω  ; Ɛ ) . Deixe que X  = ( X k , k ∈ℕ) uma transição homogénea cadeia de Markov P e inicial lei X 0  ~  v , há P v cadeia lei X .

Para simular π , queremos saber como construir uma transição P tal que ∀  v , vP k  →  π , com convergência na norma na variação total ∥ μ ∥ = sup A ∈ Ɛ μ ( A ) - inf A ∈ Ɛ μ ( A ) . A cadeia de transição P é ergódica .

Convergência de uma cadeia de Markov  -  Se uma transição P é π -redutível, π -invariante, aperiódica, recorrente de Harris, então ∀ x , P k ( x , ·) → k → ∞  π .

A última e delicada condição é satisfeita nos casos da amostragem de Gibbs e do algoritmo Metropolis-Hastings .

Métodos de amostragem

Métodos de amostragem são usados ​​para estimar a distribuição posterior (completa) dos parâmetros de um modelo. Entre eles, os métodos de Monte Carlo são muito precisos. No entanto, eles são caros do ponto de vista computacional e demoram muito para convergir. Eles também são limitados pelo tamanho da amostra, uma vez que se tornam insolúveis quando são muito grandes. Mesmo em pequenas amostras, calcular uma distribuição de probabilidade pode ser difícil. Existem várias abordagens para este problema, utilizadas para obter um conjunto de boas redes de amostragem da distribuição posterior.

Construção de redes aleatórias e busca de padrões

O método Monte Carlo por cadeias de Markov é frequentemente utilizado em algoritmos que tratam de redes (biológicas ou não). Várias aplicações diferentes são possíveis, duas das quais são as principais: a geração de redes aleatórias e a classificação de elementos em grafos. Os exemplos tomados para ilustrar o uso de MCMCs a seguir serão baseados na biologia.

Redes aleatórias

O MCMC é frequentemente utilizado para gerar redes aleatórias servindo como modelos nulos, o mais próximo possível do acaso, mantendo as características básicas de uma rede estudada para permanecer comparável. Esses modelos nulos permitem, então, determinar se as características de uma rede estudada são estatisticamente significativas ou não.

O curso do método é simples: 2 arestas são levadas em consideração (A -> B; C -> D) e uma troca dos nós dessas arestas (A -> D; C -> B) é então considerada e aceita somente se as novas arestas ainda não existirem e não houver aresta cíclica (A -> A). O número de trocas consideradas geralmente segue a fórmula Q x E, onde E é o número de arestas de uma rede real (muitas vezes a rede estudada) e Q é um número alto o suficiente para garantir a aleatoriedade da rede de produtos, muitas vezes definida como 100 .

O uso do método Monte Carlo por cadeias de Markov para gerar um modelo nulo contra o qual determinamos a significância de um (ou mais) caractere (s) pode ser encontrado sob o nome de "algoritmo de comutação", com o "algoritmo de correspondência" sendo a alternativa na geração de redes aleatórias. Este último, que não utiliza o MCMC, também apresenta como desvantagem a presença de viés nas redes de produtos. Esses algoritmos são mais frequentemente usados ​​em biologia para pesquisar padrões em redes, subgráficos compostos por um número limitado de nós e que são encontrados em um número muito grande de redes. Entre as ferramentas que utilizam o MCMC para gerar redes aleatórias estão mfinder, FANMOD, KAVOSH e NetMODE.

Pesquisa de padrão

Em relação ao uso de MCMC para a classificação de elementos em um gráfico, fala-se em particular de "Markov clustering" (MCL), um método de classificação não supervisionado baseado no conceito de "passeio aleatório", quase não necessitando de informações a priori para ser capaz de classificar os elementos de um gráfico. Mais especificamente, partindo de um nó, se “caminharmos” de nó em nó pelas bordas, tendemos a passar com mais frequência entre nós que estão dentro do mesmo grupo do que a fazer uma passagem uniforme entre todos os nós. Assim, ao aumentar a importância das arestas frequentemente cruzadas e diminuir a de menos arestas cruzadas, os grupos em uma rede são atualizados progressivamente.

Aplicação à biologia

Existem dois tipos principais de utilização de MCMC em biologia de sistemas , nomeadamente arranjos de genes e dinâmica molecular, que podem ser resumidos como um sistema de moléculas. Em ambos os casos, trata-se de compreender as interações complexas entre vários elementos. É por isso que o método MCMC é combinado com redes Bayesianas.

Redes bayesianas

As redes Bayesianas são comumente usadas em biologia e sistemas associados ao MCMC. Eles fornecem uma representação clara e compacta da distribuição de probabilidades comuns de sistemas. Seu uso em modelos gráficos tem várias vantagens. Primeiro, eles podem representar as relações / dependências causais entre as variáveis ​​e, portanto, ser interpretados como um modelo causal que gera os dados. Além disso, as redes bayesianas são úteis para ajustar os parâmetros de um modelo de aprendizado de máquina, seja ele usado para realizar predições ou classificação de dados. A teoria de probabilidade bayesiana também se mostrou eficaz na descrição da incerteza e na adaptação do número de parâmetros ao tamanho dos dados. A representação e o uso da teoria da probabilidade em redes biológicas permite combinar conhecimento e dados de um domínio, expressar relações de causa e efeito, evitar sobreajuste de um modelo para treinar dados e aprender a partir de conjuntos de dados incompletos.

Redes Bayesianas Dinâmicas

O feedback é uma característica essencial de muitos sistemas biológicos. O que torna a criação de medições experimentais de séries temporais um desafio particularmente importante na modelagem de sistemas biológicos.

As redes bayesianas são adequadas para modelar loops de feedback, bem como séries temporais. Estas são as redes Bayesianas dinâmicas que consistem no uso de redes Bayesianas na modelagem de séries temporais ou loops de feedback. Nessas condições, as variáveis ​​são indexadas pelo tempo e reproduzidas nas redes. De modelos ocultos de Markov e sistemas dinâmicos lineares são casos especiais de redes Bayesianas dinâmicas. Em modelos de Markov ocultos, há um conjunto oculto de nós (normalmente estados discretos), um conjunto de variáveis ​​observadas e as fatias do gráfico não precisam ser temporais. Eles são freqüentemente usados ​​para análise de sequência, em particular no caso de redes de genes.

Redes Bayesianas dinâmicas têm sido usadas para deduzir interações regulatórias genéticas de dados de chip de DNA, de algumas dezenas de pontos de tempo de um ciclo celular. Particularmente quando combinado com o MCMC, isso permitiu acesso ao desempenho de inferência da rede com diferentes tamanhos de conjuntos de treinamento, antecedentes e estratégias de amostragem.

Redes de genes

As redes gênicas são adequadas para modelar sistemas biológicos complexos e estocásticos. Eles representam a expressão de cada gene por uma variável que descreve a regulação entre os genes.

Nesse tipo de rede, a inferência de suas estruturas, por exemplo, a identificação de redes de regulação e sinalização a partir de dados, é o aspecto mais interessante. A distinção de correlação permite a elucidação das dependências entre as variáveis ​​medidas e, assim, o aprendizado de relações desconhecidas e excelentes modelos preditivos. No entanto, aprender estruturas de modelo é difícil e geralmente requer um projeto experimental cuidadoso.

Dinâmica Molecular

O método clássico para simular a evolução das moléculas reagentes ao longo do tempo é baseado na hipótese do contínuo. Quando o número dessas moléculas reagindo em um conjunto de reações é da ordem do número de Avogadro, pode-se supor que essa concentração (número de moléculas no conjunto) seja uma variável real contínua. Nesse caso, a cinética clássica de ação de massa pode ser usada para descrever as taxas de reação. No entanto, quando o número dessas moléculas é da ordem de centenas ou milhares, não podemos mais usar a hipótese do contínuo. Portanto, em vez de concentrações de valor verdadeiro, precisamos considerar o número de moléculas inteiras. Outro efeito do baixo número de moléculas é que a cinética clássica de ação da massa não é mais válida. As taxas de reação não são mais determinísticas, portanto, uma abordagem probabilística é necessária. Em vez de levar em conta a quantidade de reagentes consumidos e produtos produzidos em um intervalo de tempo, precisamos considerar a probabilidade de que uma reação ocorra em um intervalo de tempo. Esta abordagem para modelar reações é conhecida como cinética estocástica.

Exemplos em biologia de sistemas

Os processos celulares em biologia de sistemas são frequentemente aleatórios devido ao baixo número de moléculas reagentes.

Estimativa de parâmetro por MCMC

A cinética estocástica tornou-se um elemento básico para a modelagem de vários fenômenos em biologia de sistemas. Esses modelos, ainda mais do que modelos determinísticos, representam um problema difícil para estimar parâmetros cinéticos a partir de dados experimentais. Inicialmente, os parâmetros foram definidos em valores biologicamente plausíveis, depois ajustados a olho nu para que a simulação do modelo se assemelhe aos dados experimentais. Nesse caso, as estimativas dos parâmetros podem ser facilmente obtidas pelo ajuste dos mínimos quadrados ou pela estimativa da máxima verossimilhança. No entanto, a utilização de métodos estatísticos de Monte Carlo permitem a manutenção da estocasticidade do modelo durante a estimação desses parâmetros. Esses métodos de estimativa podem ser classificados em duas categorias bem conhecidas: métodos de máxima verossimilhança e métodos de inferência bayesiana.

Os métodos de inferência bayesiana tentam obter a distribuição posterior dos parâmetros, que pode então ser maximizada para obter estimativas posteriores máximas. A maioria dos métodos de inferência bayesiana são baseados em técnicas MCMC. A aplicação à biologia de sistemas não é exceção:

Veja também

Bibliografia

Artigos relacionados

Outra amostragem de distribuição

Notas e referências

  1. (en) R. Milo , N. Kashtan , S. Itzkovitz e MEJ Newman , “  Na geração de gráficos uniforme ao acaso com sequências fixado grau  ” , arXiv: cond-mat / 0312028 ,30 de maio de 2004( leia online , consultado em 11 de fevereiro de 2021 )
  2. (em) NTL Tran , S. Mohan , Z. Xu e C.-H. Huang , “  Inovações atuais e desafios futuros da detecção de motivos de rede  ” , Briefings in Bioinformatics , vol.  16, n o  3,1 ° de maio de 2015, p.  497-525 ( ISSN  1467-5463 e 1477-4054 , DOI  10.1093 / bib / bbu021 , ler online , acessado em 11 de fevereiro de 2021 )
  3. (em) N. Kashtan S. Itzkovitz , R. Milo e U. Alon , "  Efficient sampling algoritmo for estimar concentrações subgraph and Detecting network motifs  " , Bioinformatics , vol.  20, n o  11,22 de julho de 2004, p.  1746–1758 ( ISSN  1367-4803 e 1460-2059 , DOI  10.1093 / bioinformatics / bth163 , lido online , acessado em 11 de fevereiro de 2021 )
  4. (em) S. Wernicke e F. Rasche , "  FANMOD uma ferramenta para detecção rápida de padrão de rede  " , Bioinformatics , vol.  22, n o  9,1 ° de maio de 2006, p.  1152–1153 ( ISSN  1367-4803 e 1460-2059 , DOI  10.1093 / bioinformatics / btl038 , ler online , acessado em 11 de fevereiro de 2021 )
  5. (em) Zahra Razaghi Moghadam Kashani , Hayedeh Ahrabian , Elahe Elahi e Abbas Nowzari-Dalini , "  Kavosh: um novo algoritmo para encontrar motivos de rede  " , BMC Bioinformatics , vol.  10, n o  1,4 de outubro de 2009, p.  318 ( ISSN  1471-2105 , PMID  19799800 , PMCID  PMC2765973 , DOI  10.1186 / 1471-2105-10-318 , ler online , acessado em 11 de fevereiro de 2021 )
  6. (em) Xin Li , Rebecca J. Stones , Haidong Wang e Hualiang Deng , "  NetMODE: Pattern Detection Network without Nauty  " , PLoS ONE , vol.  7, N o  12,18 de dezembro de 2012, e50093 ( ISSN  1932-6203 , PMID  23272055 , PMCID  PMC3525646 , DOI  10.1371 / journal.pone.0050093 , ler online , acessado em 11 de fevereiro de 2021 )
  7. (em) Stijn van Dongen, "  Graph Clustering by Flow Simulation  " , tese de doutorado, University of Utrecht ,Maio de 2000
  8. Husmeier, Dirk. , Modelagem Probabilística em Bioinformática e Informática Médica , Springer-Verlag London Limited,2005( ISBN  978-1-84628-119-8 e 1-84628-119-9 , OCLC  981318762 , leia online )
  9. (in) Ankur Gupta e James B. Rawlings , "  Comparison of parameter estimation methods in stochastic chemical cinetic models: Examples in systems biology  " , AIChE Journal , Vol.  60, n o  4,abril de 2014, p.  1253–1268 ( PMID  27429455 , PMCID  PMC4946376 , DOI  10.1002 / aic.14409 , ler online , acessado em 14 de fevereiro de 2021 )
  10. Michael B. Elowitz , Arnold J. Levine , Eric D. Siggia e Peter S. Swain , "  Stochastic gene expression in a single cell  ", Science (New 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 , lido online , acessado em 14 de fevereiro de 2021 )
  11. William J. Blake , Mads KAErn , Charles R. Cantor e JJ Collins , “  Noise in ekaryotic gene expression  ”, Nature , vol.  422, n o  6932,10 de abril de 2003, p.  633-637 ( ISSN  0028-0836 , PMID  12687005 , DOI  10.1038 / nature01546 , ler online , acessado em 14 de fevereiro de 2021 )
  12. Jonathan M. Raser e Erin K. O'Shea , “  Control of stochasticity in ekaryotic gene expression  ”, Science (New York, NY) , vol.  304, n o  5678,18 de junho de 2004, p.  1811–1814 ( ISSN  1095-9203 , PMID  15166317 , PMCID  1410811 , DOI  10.1126 / science.1098641 , ler online , acessado em 14 de fevereiro de 2021 )
  13. HH McAdams e A. Arkin , “  Stochastic mecanismos in gene expression  ”, Proceedings of the National Academy of Sciences dos Estados Unidos da América , vol.  94, n o  3,4 de fevereiro de 1997, p.  814–819 ( ISSN  0027-8424 , PMID  9023339 , PMCID  PMC19596 , DOI  10.1073 / pnas.94.3.814 , ler online , acessado em 14 de fevereiro de 2021 )
  14. A. Arkin , J. Ross e HH McAdams , "  Stochastic kinetic analysis of developmental pathway bifurcation in fhage lambda-infectado Escherichia coli cells  ", Genetics , vol.  149, n o  4,Agosto de 1998, p.  1633-1648 ( ISSN  0016-6731 , PMID  9691025 , PMCID  1460268 , ler online , acessado em 14 de fevereiro de 2021 )
  15. Leor S. Weinberger , John C. Burnett , Jared E. Toettcher e Adam P. Arkin , “  Stochastic gene expression in a lentiviral positive-feedback loop: HIV-1 Tat fluctuations drive phenotypic diversidade  ”, Cell , vol.  122, n o  229 de julho de 2005, p.  169–182 ( ISSN  0092-8674 , PMID  16051143 , DOI  10.1016 / j.cell.2005.06.006 , lido online , acessado em 14 de fevereiro de 2021 )
  16. Sebastian C. Hensel , James B. Rawlings e John Yin , “  Modelagem cinética estocástica do crescimento intracelular do vírus da estomatite vesicular  ”, Bulletin of Mathematical Biology , vol.  71, n o  7,outubro de 2009, p.  1671-1692 ( ISSN  1522-9602 , PMID  19459014 , PMCID  3169382 , DOI  10.1007 / s11538-009-9419-5 , ler online , acessado em 14 de fevereiro de 2021 )
  17. Grzegorz A. Rempala , Kenneth S. Ramos e Ted Kalbfleisch , “  Um modelo estocástico da transcrição de genes: um pedido para L1 eventos de retrotransposição  ”, Journal of Theoretical Biology , vol.  242, n o  1,7 de setembro de 2006, p.  101-116 ( ISSN  0022-5193 , PMID  16624324 , DOI  10.1016 / j.jtbi.2006.02.010 , lido on-line , acessado 14 de fevereiro de 2021 )
  18. Daniel A. Henderson , Richard J. Meninos , Kim J. Krishnan e Conor Lawless “  Bayesian Emulação e Calibração de um modelo de computador estocástica de DNA mitocondrial supressões no substância negra Neurons  ”, Jornal da Associação Americana de Estatística , vol .  104, n o  485,Março de 2009, p.  76–87 ( ISSN  0162-1459 e 1537-274X , DOI  10.1198 / jasa.2009.0005 , lido online , acessado em 14 de fevereiro de 2021 )
  19. A. Golightly e DJ Wilkinson , “  Inferência Bayesiana para modelos de difusão multivariados não lineares observados com erro  ”, Computational Statistics & Data Analysis , vol.  52, n o  3,Janeiro de 2008, p.  1674–1693 ( ISSN  0167-9473 , DOI  10.1016 / j.csda.2007.05.019 , ler online , acessado em 14 de fevereiro de 2021 )
  20. (em) Darren J. Wilkinson , Stochastic Modeling for Systems Biology , 3,7 de dezembro de 2018( ISBN  9781351000918 , DOI  10.1201 / 9781351000918 , leia online )
  21. Andrew Golightly e Darren J. Wilkinson , “  Bayesian parâmetro inferência para modelos de rede bioquímicos estocásticos usando partícula cadeia de Markov de Monte Carlo  ”, Interface de foco , vol.  1, n o  6,6 de dezembro de 2011, p.  807–820 ( ISSN  2042-8901 , PMID  23226583 , PMCID  3262293 , DOI  10.1098 / rsfs.2011.0047 , ler online , acessado em 14 de fevereiro de 2021 )
  22. Andrew Golightly e Darren J. Wilkinson , “  Inferência sequencial bayesiana para modelos de rede bioquímica cinética estocástica  ”, Journal of Computational Biology: A Journal of Computational Molecular Cell Biology , vol.  13, n o  3,Abril de 2006, p.  838-851 ( ISSN  1066-5277 , PMID  16706729 , DOI  10.1089 / cmb.2006.13.838 , ler online , acessado em 14 de fevereiro de 2021 )
  23. Tommaso Mazza , Gennaro Iaccarino e Corrado Priami , “  Snazer: as simulações e analisador de redes  ”, BMC systems biology , vol.  4,7 de janeiro de 2010, p.  1 ( ISSN  1752-0509 , PMID  20056001 , PMCID  2880970 , DOI  10.1186 / 1752-0509-4-1 , ler online , acessado em 14 de fevereiro de 2021 )
  24. S. Reinker , RM Altman e J. Timmer , “  estimativa de parâmetros em reacções bioquímicas estocásticos  ”, IEE Proceedings - Biologia de Sistemas , vol.  153, n o  4,2006, p.  168 ( ISSN  1741-2471 , DOI  10.1049 / ip-syb: 20050105 , lido online , acessado em 14 de fevereiro de 2021 )
  25. Ido Golding , Johan Paulsson , Scott M. Zawilski e Edward C. Cox , “  Real-time kinetics of gene activity in individual bactéria  ”, Cell , vol.  123, n o  6,16 de dezembro de 2005, p.  1025–1036 ( ISSN  0092-8674 , PMID  16360033 , DOI  10.1016 / j.cell.2005.09.031 , ler online , acessado em 14 de fevereiro de 2021 )
  26. Suresh Kumar Poovathingal e Rudiyanto Gunawan , “  Métodos de estimativa de parâmetros globais 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 , lido online , consultado em 14 de fevereiro 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;">