Metodo Monte-Carlo delle catene di Markov

Metodo Monte-Carlo delle catene di Markov
Sottoclasse Campionamento
Chiamato in riferimento a Andreï Markov , Monte-Carlo

I metodi della catena di Markov Monte Carlo , o metodi MCMC per la catena di Markov Monte Carlo in inglese , sono una classe di metodi per il campionamento dalle distribuzioni di probabilità. Questi metodi Monte-Carlo si basano sul percorso delle catene di Markov le cui leggi stazionarie sono le distribuzioni da campionare.

Alcuni metodi utilizzano passeggiate casuali su catene di Markov ( algoritmo Metropolis-Hastings , campionamento di Gibbs ), mentre altri algoritmi più complessi introducono vincoli sui percorsi per cercare di accelerare la convergenza ( Monte Carlo Hybrid  (en) , Successive over-relax )

Questi metodi sono applicati in particolare nell'ambito dell'inferenza bayesiana .

Approccio intuitivo

Ci poniamo in uno spazio vettoriale di dimensione finita n . Vogliamo generare in modo casuale vettori secondo una distribuzione di probabilità π . Vogliamo quindi avere una sequenza di vettori tale che la distribuzione degli approcci π .

I metodi Monte-Carlo della catena di Markov consistono nel generare un vettore solo dai dati del vettore  ; è quindi un processo "senza memoria", che caratterizza le catene di Markov. Dobbiamo quindi trovare un generatore casuale con una distribuzione di probabilità che ci permetta di generare da . Sostituiamo così il problema di generazione con una distribuzione π con problemi di generazione con le distribuzioni , che speriamo sarà più semplice.

Principio

Vogliamo simulare una legge π su uno spazio degli stati generale ( Ω  ; Ɛ ) . Una transizione su ( Ω  ; Ɛ ) è una mappa P  : ( Ω  ; Ɛ ) → [0; 1] tale che P (·, A ) per ogni A ∈ Ɛ sia misurabile e P ( x , ·) per ogni x ∈ Ω sia una probabilità su ( Ω  ; Ɛ ) . Let X  = ( X k , k ∈ℕ) una omogenea transizione catena di Markov P e iniziale legge X 0  ~  v , v'è P v catena legge X .

Per simulare π , vogliamo sapere come costruire una transizione P tale che ∀  v , vP k  →  π , con convergenza in norma in variazione totale ∥ μ ∥ = sup A ∈ Ɛ μ ( A ) - inf A ∈ Ɛ μ ( A ) . La catena di transizione P è ergodica .

Convergenza di una catena di Markov  -  Se una transizione P è π -iducibile, π -invariant, aperiodica, Harris-ricorrente, allora ∀ x , P k ( x , ·) → k → ∞  π .

L'ultima, delicata condizione è soddisfatta nei casi del campionamento di Gibbs e dell'algoritmo Metropolis-Hastings .

Metodi di campionamento

I metodi di campionamento vengono utilizzati per stimare la distribuzione posteriore (completa) dei parametri di un modello. Tra questi, i metodi Monte Carlo sono molto precisi. Tuttavia, sono computazionalmente costosi e richiedono molto tempo per convergere. Sono anche limitati dalle dimensioni del campione, poiché diventano insolubili quando sono troppo grandi. Anche su piccoli campioni, il calcolo di una distribuzione di probabilità può essere difficile. Esistono diversi approcci a questo problema, utilizzati per ottenere un insieme di buone reti di campionamento dalla distribuzione a posteriori.

Costruzione di reti casuali e ricerca di pattern

Il metodo Monte Carlo delle catene di Markov è spesso utilizzato negli algoritmi che si occupano di reti (biologiche o meno). Sono possibili diverse applicazioni, due delle quali principali: la generazione di reti casuali e la classificazione degli elementi nei grafici. Gli esempi presi per illustrare l'uso degli MCMC di seguito saranno basati sulla biologia.

Reti casuali

MCMC è molto spesso utilizzato per generare reti casuali che fungono da modelli nulli, il più vicino possibile al caso, mantenendo le caratteristiche di base di una rete studiata per rimanere confrontabili. Questi modelli nulli consentono quindi di determinare se le caratteristiche di una rete studiata sono statisticamente significative o meno.

Il corso del metodo è semplice: vengono presi in considerazione 2 archi (A -> B; C -> D) e viene quindi considerato e accettato uno scambio dei nodi di questi archi (A -> D; C -> B) solo se i nuovi bordi non esistono già e non esiste un fronte ciclico (A -> A). Il numero di scambi considerato segue spesso la formula Q x E, dove E è il numero di spigoli di una rete reale (spesso la rete studiata) e Q è un numero sufficientemente alto da garantire la casualità della rete prodotto, spesso impostata a 100 .

L'uso del metodo Monte Carlo da parte delle catene di Markov per generare un modello nullo rispetto al quale determiniamo il significato di uno (o più) caratteri può essere trovato sotto il nome di "algoritmo di commutazione", con "algoritmo di corrispondenza" che è l'alternativa nella generazione di reti casuali. Quest'ultimo, che non utilizza l'MCMC, presenta anche come svantaggio la presenza di un bias nelle reti di prodotto. Questi algoritmi sono utilizzati più spesso in biologia per cercare modelli nelle reti, sottografi composti da un numero limitato di nodi e che si trovano in un numero molto elevato di reti. Tra gli strumenti che utilizzano MCMC per generare reti casuali ci sono mfinder, FANMOD, KAVOSH e NetMODE.

Ricerca pattern

Per quanto riguarda l'uso di MCMC per la classificazione degli elementi in un grafo, si parla in particolare di "Markov clustering" (MCL), un metodo di classificazione non supervisionato basato sul concetto di "random walk", che quasi non richiede informazioni a priori per essere in grado di classificare gli elementi di un grafico. Più precisamente, partendo da un nodo, se “camminiamo” di nodo in nodo attraverso i bordi, tendiamo a passare più spesso tra nodi che si trovano all'interno dello stesso gruppo che a fare un passaggio uniforme tra tutti i nodi. Pertanto, aumentando l'importanza dei bordi incrociati frequentemente e diminuendo quella dei bordi meno incrociati, i gruppi in una rete vengono progressivamente aggiornati.

Applicazione alla biologia

Esistono due tipi principali di utilizzo di MCMC nella biologia dei sistemi , vale a dire gli array di geni e la dinamica molecolare che possono essere riassunti come un sistema di molecole. In entrambi i casi, si tratta di comprendere le complesse interazioni tra diversi elementi. Questo è il motivo per cui il metodo MCMC è combinato con le reti bayesiane.

Reti bayesiane

Le reti bayesiane sono comunemente utilizzate in biologia e nei sistemi associati all'MCMC. Forniscono una rappresentazione chiara e compatta della distribuzione delle probabilità comuni dei sistemi. Il loro utilizzo nei modelli grafici presenta diversi vantaggi. In primo luogo, possono rappresentare le relazioni / dipendenze causali tra le variabili e quindi essere interpretate come un modello causale che genera i dati. Inoltre, le reti bayesiane sono utili per personalizzare i parametri di un modello di apprendimento automatico, sia che venga utilizzato per eseguire la previsione o la classificazione dei dati. La teoria della probabilità bayesiana si è anche dimostrata efficace nel descrivere l'incertezza e nell'adattare il numero di parametri alla dimensione dei dati. La rappresentazione e l'uso della teoria della probabilità nelle reti biologiche consente sia di combinare conoscenze e dati da un dominio, di esprimere relazioni di causa ed effetto, di evitare di adattare eccessivamente un modello per addestrare dati e apprendere da set di dati incompleti.

Reti bayesiane dinamiche

Il feedback è una caratteristica essenziale di molti sistemi biologici. Ciò che rende la creazione di misurazioni di serie temporali sperimentali una sfida particolarmente importante nella modellazione di sistemi biologici.

Le reti bayesiane sono adatte per modellare cicli di feedback, nonché serie temporali. Queste sono le reti bayesiane dinamiche che consistono nell'uso di reti bayesiane durante la modellazione di serie temporali o cicli di feedback. In queste condizioni le variabili vengono indicizzate nel tempo e riprodotte nelle reti. Di modelli di Markov nascosti e dei sistemi dinamici lineari sono casi particolari di reti bayesiane dinamiche. Nei modelli di Markov nascosti, esiste un insieme nascosto di nodi (normalmente stati discreti), un insieme di variabili osservate e le sezioni del grafico non devono essere temporali. Sono spesso utilizzati per l'analisi delle sequenze, in particolare nel caso delle reti geniche.

Le reti bayesiane dinamiche sono state utilizzate per dedurre le interazioni di regolazione genetica dai dati del DNA microarray, da poche dozzine di punti temporali da un ciclo cellulare. Soprattutto se combinato con l'MCMC, ciò ha consentito l'accesso alle prestazioni di inferenza della rete con diverse dimensioni di insiemi di addestramento, antecedenti e strategie di campionamento.

Reti geniche

Le reti geniche sono adatte per modellare sistemi biologici complessi e stocastici. Rappresentano ogni espressione genica da una variabile che descrive la regolazione tra i geni.

In questo tipo di reti, l'aspetto più interessante è l'inferenza delle loro strutture, ad esempio l'identificazione delle reti di regolazione e di segnalazione dai dati. La distinzione di correlazione consente la delucidazione delle dipendenze tra le variabili misurate e quindi l'apprendimento di relazioni sconosciute e ottimi modelli predittivi. Tuttavia, l'apprendimento delle strutture dei modelli è difficile e spesso richiede un'attenta progettazione sperimentale.

Dinamica molecolare

Il metodo classico per simulare l'evoluzione delle molecole reagenti nel tempo si basa sull'ipotesi del continuo. Quando il numero di queste molecole che reagiscono in un insieme di reazioni è dell'ordine del numero di Avogadro, si può presumere che questa concentrazione (numero di molecole nell'insieme) sia una variabile reale continua. In questo caso, la cinetica classica dell'azione di massa può essere utilizzata per descrivere le velocità di reazione. Tuttavia, quando il numero di queste molecole è dell'ordine di centinaia o migliaia, non possiamo più utilizzare l'ipotesi del continuo. Pertanto, invece di concentrazioni a valori reali, dobbiamo considerare il numero di molecole a valori interi. Un altro effetto del basso numero di molecole è che la cinetica classica dell'azione di massa non è più valida. I tassi di reazione non sono più deterministici, quindi è necessario un approccio probabilistico. Invece di prendere in considerazione la quantità di reagenti consumati e prodotti prodotti in un intervallo di tempo, dobbiamo considerare la probabilità che si verifichi una reazione in un intervallo di tempo. Questo approccio alla modellazione delle reazioni è noto come cinetica stocastica.

Esempi di biologia dei sistemi

I processi cellulari nella biologia dei sistemi sono spesso casuali a causa del basso numero di molecole che reagiscono.

Stima dei parametri mediante MCMC

La cinetica stocastica è diventata un elemento base per la modellazione di vari fenomeni nella biologia dei sistemi. Questi modelli, ancor più dei modelli deterministici, pongono un problema difficile nella stima dei parametri cinetici da dati sperimentali. Inizialmente, i parametri sono stati impostati su valori biologicamente plausibili, quindi regolati ad occhio nudo in modo che la simulazione del modello somigliasse ai dati sperimentali. In questo caso, le stime dei parametri possono essere facilmente ottenute mediante aggiustamento ai minimi quadrati o stima di massima verosimiglianza. Tuttavia, l'uso di metodi statistici Monte Carlo consente il mantenimento della stocasticità del modello durante la stima di questi parametri. Questi metodi di stima possono essere classificati in due categorie ben note: metodi di massima verosimiglianza e metodi di inferenza bayesiana.

I metodi di inferenza bayesiana tentano di ottenere la distribuzione a posteriori dei parametri, che può quindi essere massimizzata per ottenere le stime a posteriori massime. La maggior parte dei metodi di inferenza bayesiana sono basati su tecniche MCMC. L'applicazione alla biologia dei sistemi non fa eccezione:

Vedi anche

Bibliografia

Articoli Correlati

Altro campionamento di distribuzione

Note e riferimenti

  1. (en) R. Milo , N. Kashtan , S. Itzkovitz e MEJ Newman , “  Sulla generazione uniforme grafi random con sequenze prescritto gradi  ” , arXiv: cond-mat / 0.312.028 ,30 maggio 2004( leggi online , consultato l' 11 febbraio 2021 )
  2. ( entra ) NTL Tran , S. Mohan , Z. Xu e C.-H. Huang , "  Innovazioni attuali e sfide future del rilevamento di motivi di rete  " , Briefings in Bioinformatics , vol.  16, n o  3,1 ° maggio 2015, p.  497-525 ( ISSN  1467-5463 e 1477-4054 , DOI  10.1093 / bib / bbu021 , letto online , accesso 11 febbraio 2021 )
  3. (in) N. Kashtan S. Itzkovitz , R. Milo e U. Alon , "  Algoritmo di campionamento efficiente per la stima delle concentrazioni sottografo e rilevamento dei motivi della rete  " , Bioinformatics , vol.  20, n o  11,22 luglio 2004, p.  1746-1758 ( ISSN  1367-4803 e 1460-2059 , DOI  10.1093 / bioinformatics / bth163 , letto online , accesso 11 febbraio 2021 )
  4. (in) S. Wernicke e F. Rasche , "  FANMOD a tool for fast network pattern detection  " , Bioinformatics , vol.  22, n o  9,1 ° maggio 2006, p.  1152–1153 ( ISSN  1367-4803 e 1460-2059 , DOI  10.1093 / bioinformatics / btl038 , letto online , accesso 11 febbraio 2021 )
  5. (in) Zahra Razaghi Moghadam Kashani , Hayedeh Ahrabian , Elahe Elahi e Abbas Nowzari-Dalini , "  Kavosh: un nuovo algoritmo per la ricerca di motivi di rete  " , BMC Bioinformatics , vol.  10, n o  1,4 ottobre 2009, p.  318 ( ISSN  1471-2105 , PMID  19799800 , PMCID  PMC2765973 , DOI  10.1186 / 1471-2105-10-318 , letto online , accesso 11 febbraio 2021 )
  6. (in) Xin Li , Rebecca J. Stones , Haidong Wang e Hualiang Deng , "  NetMODE: Pattern Detection Network without Nauty  " , PLoS ONE , vol.  7, n o  12,18 dicembre 2012, e50093 ( ISSN  1932-6203 , PMID  23272055 , PMCID  PMC3525646 , DOI  10.1371 / journal.pone.0050093 , letto online , accesso 11 febbraio 2021 )
  7. (in) Stijn van Dongen, "  Graph Clustering by Flow Simulation  " , tesi di dottorato, Università di Utrecht ,Maggio 2000
  8. Husmeier, Dirk. , Modellazione probabilistica in bioinformatica e informatica medica , Springer-Verlag London Limited,2005( ISBN  978-1-84628-119-8 e 1-84628-119-9 , OCLC  981318762 , leggi online )
  9. (in) Ankur Gupta e James B. Rawlings , "  Comparison of parameter estimation methods in stochastic chemical kinetic models: examples in systems biology  " , AIChE Journal , Vol.  60, n o  4,aprile 2014, p.  1253–1268 ( PMID  27429455 , PMCID  PMC4946376 , DOI  10.1002 / aic.14409 , letto online , accesso 14 febbraio 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 agosto 2002, p.  1183–1186 ( ISSN  1095-9203 , PMID  12183631 , DOI  10.1126 / science.1070919 , letto online , accesso 14 febbraio 2021 )
  11. William J. Blake , Mads KAErn , Charles R. Cantor e JJ Collins , "  Noise in eukaryotic gene expression  ", Nature , vol.  422, n o  6932,10 aprile 2003, p.  633-637 ( ISSN  0028-0836 , PMID  12687005 , DOI  10.1038 / nature01546 , letto online , accesso 14 febbraio 2021 )
  12. Jonathan M. Raser e Erin K. O'Shea , "  Controllo della stocasticità nell'espressione genica eucariotica  ", Science (New York, NY) , vol.  304, n o  5678,18 giugno 2004, p.  1811-1814 ( ISSN  1095-9203 , PMID  15166317 , PMCID  1410811 , DOI  10.1126 / science.1098641 , letto online , accesso 14 febbraio 2021 )
  13. HH McAdams e A. Arkin , "  Meccanismi stocastici nell'espressione genica  ", Atti della National Academy of Sciences degli Stati Uniti d'America , vol.  94, n o  3,4 febbraio 1997, p.  814–819 ( ISSN  0027-8424 , PMID  9023339 , PMCID  PMC19596 , DOI  10.1073 / pnas.94.3.814 , letto online , accesso 14 febbraio 2021 )
  14. A. Arkin , J. Ross e HH McAdams , "  Analisi cinetica stocastica della biforcazione del percorso di sviluppo in cellule di Escherichia coli infettate da fago lambda  ", Genetics , vol.  149, n o  4,Agosto 1998, p.  1633-1648 ( ISSN  0016-6731 , PMID  9691025 , PMCID  1460268 , letto online , accesso 14 febbraio 2021 )
  15. Leor S. Weinberger , John C. Burnett , Jared E. Toettcher e Adam P. Arkin , "  Espressione genica stocastica in un ciclo di feedback positivo lentivirale: le fluttuazioni di HIV-1 Tat guidano la diversità fenotipica  ", Cell , vol.  122, n o  229 luglio 2005, p.  169–182 ( ISSN  0092-8674 , PMID  16051143 , DOI  10.1016 / j.cell.2005.06.006 , letto online , accesso 14 febbraio 2021 )
  16. Sebastian C. Hensel , James B. Rawlings e John Yin , "  Modellazione cinetica stocastica della crescita intracellulare del virus della stomatite vescicolare  ", Bulletin of Mathematical Biology , vol.  71, n o  7,ottobre 2009, p.  1671–1692 ( ISSN  1522-9602 , PMID  19459014 , PMCID  3169382 , DOI  10.1007 / s11538-009-9419-5 , letto online , accesso 14 febbraio 2021 )
  17. Grzegorz A. Rempala , Kenneth S. Ramos e Ted Kalbfleisch , “  Un modello stocastico della trascrizione genica: un'applicazione per L1 eventi retrotrasposizione  ”, Journal of Theoretical Biology , vol.  242, n o  1,7 settembre 2006, p.  101–116 ( ISSN  0022-5193 , PMID  16624324 , DOI  10.1016 / j.jtbi.2006.02.010 , letto online , accesso 14 febbraio 2021 )
  18. Daniel A. Henderson , Richard J. Ragazzi , Kim J. Krishnan e Conor Lawless , “  Emulazione bayesiana e calibrazione di un modello stocastico computer del DNA mitocondriale delezioni in sostanza nera neuroni  ”, ufficiale American Statistical Association , vol .  104, n o  485,Marzo 2009, p.  76-87 ( ISSN  0162-1459 e 1537-274X , DOI  10.1198 / jasa.2009.0005 , letto online , accesso 14 febbraio 2021 )
  19. A. Golightly e DJ Wilkinson , "  Inferenza bayesiana per modelli di diffusione multivariata non lineare osservati con errore  ", Computational Statistics & Data Analysis , vol.  52, n o  3,Gennaio 2008, p.  1674–1693 ( ISSN  0167-9473 , DOI  10.1016 / j.csda.2007.05.019 , letto online , accesso 14 febbraio 2021 )
  20. (a) Darren J. Wilkinson , Stochastic Modeling for Systems Biology , 3,7 dicembre 2018( ISBN  9781351000918 , DOI  10.1201 / 9781351000918 , leggi online )
  21. Andrew Golightly e Darren J. Wilkinson , “  parametro di inferenza bayesiana per i modelli di rete biochimici stocastici utilizzando particelle catena di Markov Monte Carlo  ”, interfaccia messa a fuoco , vol.  1, n o  6,6 dicembre 2011, p.  807–820 ( ISSN  2042-8901 , PMID  23226583 , PMCID  3262293 , DOI  10.1098 / rsfs.2011.0047 , letto online , accesso 14 febbraio 2021 )
  22. Andrew Golightly e Darren J. Wilkinson , "  inferenza sequenziale bayesiana per modelli di rete biochimica cinetica stocastica  ", Journal of Computational Biology: A Journal of Computational Molecular Cell Biology , vol.  13, n o  3,Aprile 2006, p.  838-851 ( ISSN  1066-5277 , PMID  16706729 , DOI  10.1089 / cmb.2006.13.838 , letto online , accesso 14 febbraio 2021 )
  23. Tommaso Mazza , Gennaro Iaccarino e Corrado Priami , “  Snazer: le simulazioni e l'analizzatore di reti  ”, Biologia dei sistemi BMC , vol.  4,7 gennaio 2010, p.  1 ( ISSN  1752-0509 , PMID  20056001 , PMCID  2880970 , DOI  10.1186 / 1752-0509-4-1 , letto online , accesso 14 febbraio 2021 )
  24. S. Reinker , RM Altman e J. Timmer “  la stima dei parametri di reazioni biochimiche stocastici  ”, IEE Proceedings - Systems Biology , vol.  153, n o  4,2006, p.  168 ( ISSN  1741-2471 , DOI  10.1049 / ip-syb: 20050105 , letto online , accesso 14 febbraio 2021 )
  25. Ido Golding , Johan Paulsson , Scott M. Zawilski e Edward C. Cox , "  Cinetica in tempo reale dell'attività genica nei singoli batteri  ", Cell , vol.  123, n o  6,16 dicembre 2005, p.  1025-1036 ( ISSN  0092-8674 , PMID  16360033 , DOI  10.1016 / j.cell.2005.09.031 , letto online , accesso 14 febbraio 2021 )
  26. Suresh Kumar Poovathingal e Rudiyanto Gunawan , "  Metodi di stima dei parametri globali per sistemi biochimici stocastici  ", BMC Bioinformatics , vol.  11, n o  1,6 agosto 2010( ISSN  1471-2105 , DOI  10.1186 / 1471-2105-11-414 , letto online , consultato il 14 febbraio 2021 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">