Monte-Carlo módszer Markov-láncokkal

Monte-Carlo módszer Markov-láncokkal
Alosztály Mintavétel
Névre hivatkozva nevezték el Andreï Markov , Monte-Carlo

A Monte Carlo Markov-lánc módszerei , vagy az MCMC-módszerek a Markov Chain Monte Carlo -hoz angol nyelven , a valószínűségi eloszlásokból történő mintavétel módszereinek osztálya . Ezek a Monte-Carlo módszerek azon Markov-láncok útvonalán alapulnak, amelyek stacionárius törvényei az eloszlásokat kell mintavételezni.

Egyes módszerek véletlenszerű sétákat alkalmaznak Markov-láncokon ( Metropolis-Hastings algoritmus , Gibbs mintavétel ), míg más bonyolultabb algoritmusok korlátokat vezetnek be az utakra, hogy megpróbálják felgyorsítani a konvergenciát ( Monte Carlo Hybrid  (en) , Successive over-relaxation )

Ezeket a módszereket különösen a Bayes-i következtetés keretein belül alkalmazzák .

Intuitív megközelítés

Helyezzük magunkat az n véges dimenzió vektorterébe . Azt akarjuk, hogy véletlenszerűen generál vektorok szerint valószínűségi eloszlás π . Ezért olyan vektorok szekvenciáját szeretnénk elérni , amelyek a π megközelítések eloszlását mutatják .

A Markov-láncok által végzett Monte-Carlo-módszerek abból állnak, hogy csak a vektor adataiból állítanak elő vektort  ; ezért „memória nélküli” folyamat, amely Markov-láncokat jellemzi. Meg kell tehát találni a véletlenszám-generátort egy valószínűségi eloszlás , amely lehetővé teszi számunkra, hogy létrehoz re . Mi így helyettesíti a generációs probléma a forgalmazás π által generációs problémák disztribúció , amely reméljük, egyszerűbb lesz.

Elv

Π törvényt akarunk szimulálni egy általános állapottérben ( Ω  ; Ɛ ) . A ( Ω  ; Ɛ ) átmenet a P térkép  : ( Ω  ; Ɛ ) → [0; 1] oly módon, hogy P (·, A ) minden A ∈ Ɛ esetén mérhető, és P ( x , ·) minden x ∈ Ω esetén a ( Ω  ; Ɛ ) bekapcsolás valószínűsége . Legyen X  = ( X k , k ∈ℕ) homogén Markov-lánc átmeneti P és kezdeti jogi X 0  ~  V , van P v törvény lánc X .

A π szimulációjához meg akarjuk tudni, hogyan lehet létrehozni egy P átmenetet úgy, hogy ∀  v , vP k  →  π , normai konvergenciával a teljes variációban μ ∥ = sup AƐ μ ( A ) - inf AƐ μ ( A ) . Az átmenet lánc P jelentése ergodikus .

Konvergencia egy Markov-lánc  -  Ha egy átmenet P jelentése π -reducible, π -invariant, aperiodikus, Harris-visszatérő, majd ∀ x , P k ( x , ·) → k → ∞  π .

Az utolsó, kényes feltétel teljesül Gibbs mintavétel és a Metropolis-Hastings algoritmus esetében .

Mintavételi módszerek

Mintavételi módszerekkel becsülik meg a modell paramétereinek hátsó (teljes) eloszlását. Közülük a Monte Carlo-módszerek nagyon pontosak. Számítási szempontból azonban drágák, és hosszú időbe telik a konvergálás. Korlátozza őket a minta mérete is, mivel túl nagyoknál oldhatatlanná válnak. Kis valószínűségű minták esetében is nehéz lehet a valószínűségeloszlás kiszámítása. Ennek a problémának többféle megközelítése létezik, amelyeket arra használnak, hogy jó mintavételi hálózatokat kapjanak a hátsó eloszlásból.

Véletlenszerű hálózatok kiépítése és minták keresése

A Markov-láncok által a Monte Carlo-módszert gyakran használják a hálózatokkal foglalkozó algoritmusokban (biológiai vagy nem). Többféle alkalmazás lehetséges, amelyek közül kettő fő: a véletlenszerű hálózatok létrehozása és az elemek grafikonokba történő osztályozása. Az alábbiakban az MCMC-k használatának szemléltetésére vett példák a biológián alapulnak.

Véletlenszerű hálózatok

Az MCMC-t nagyon gyakran használják véletlenszerű hálózatok létrehozására, amelyek null modellként szolgálnak, a lehető legközelebb a véletlenhez, miközben megtartják a vizsgált hálózat alapvető jellemzőit az összehasonlíthatóság érdekében. Ezek a null modellek lehetővé teszik annak megállapítását, hogy a vizsgált hálózat jellemzői statisztikailag szignifikánsak-e vagy sem.

A módszer menete egyszerű: 2 élt veszünk figyelembe (A -> B; C -> D), majd mérlegeljük és elfogadjuk ezen élek csomópontjainak cseréjét (A -> D; C -> B) csak akkor, ha az új élek még nem léteznek, és nincs ciklikus él (A -> A). A figyelembe vett cserék száma gyakran a Q x E képletet követi, ahol E a valós hálózat éleinek száma (gyakran a vizsgált hálózat), Q pedig elég nagy szám a termékhálózat véletlenszerűségének biztosításához, gyakran 100-ra állítva .

A Monte Carlo-módszer alkalmazása Markov-láncoknál egy olyan null modell előállítására, amely alapján meghatározzuk egy (vagy több) karakter jelentőségét, megtalálható a "kapcsolási algoritmus" név alatt, az "egyező algoritmus" az alternatíva a véletlenszerű hálózatok létrehozásában. Ez utóbbi, amely nem használja az MCMC-t, szintén hátrányként mutatja az elfogultság jelenlétét a termékhálózatokban. Ezeket az algoritmusokat a biológia leggyakrabban a hálózatok mintáinak, korlátozott számú csomópontból álló részgráfok keresésére használják, amelyek nagyon sok hálózatban találhatók. Az MCMC-vel véletlenszerű hálózatok létrehozására szolgáló eszközök között megtalálható az mfinder, a FANMOD, a KAVOSH és a NetMODE.

Minta keresés

Ami az MCMC használatát az elemek grafikonba sorolásához használja, különösen a "Markov-klaszterezés" (MCL), egy felügyelet nélküli, a "véletlenszerű séta" fogalmán alapuló osztályozási módszerről beszélünk, amely szinte semmilyen előzetes információt nem igényel annak érdekében, hogy képes legyen osztályozni egy gráf elemeit. Pontosabban, ha egy csomótól indulunk, ha csomóról csomóra „járunk” az éleken, akkor hajlamosak vagyunk gyakrabban áthaladni az azonos csoportba tartozó csomók között, mintsem hogy minden csomópont között egyenletesen haladjunk. Így a gyakran keresztezett élek jelentőségének növelésével és a kevésbé keresztezett élek jelentőségének csökkentésével a hálózat csoportjai fokozatosan frissülnek.

Alkalmazás a biológiára

Az MCMC alkalmazásának két fő típusa van a rendszerbiológiában , nevezetesen a géntömbök és a molekuladinamika, amelyek összefoglalhatók molekularendszerként. Mindkét esetben a több elem közötti összetett kölcsönhatások megértéséről van szó. Ezért kombinálják az MCMC módszert a Bayes-hálózatokkal.

Bayesi hálózatok

A Bayes-hálózatokat általában használják a biológiában és az MCMC-hez kapcsolódó rendszerekben. Tiszta és kompakt ábrázolást nyújtanak a rendszerek közös valószínűségeinek eloszlásáról. Használatuk grafikai modellekben számos előnnyel jár. Először is képviselhetik a változók közötti oksági kapcsolatokat / függőségeket, és így az adatokat létrehozó oksági modellként értelmezhetők. Ezenkívül a Bayes-hálózatok hasznosak a gépi tanulási modell paramétereinek testreszabásához, függetlenül attól, hogy ezt előrejelzésre vagy adatok osztályozására használják-e. A bayesi valószínűségelmélet szintén bebizonyosodott, hogy hatékony a bizonytalanság leírásában és a paraméterek számának az adatok méretéhez való igazításában. A valószínűségelmélet reprezentációja és felhasználása a biológiai hálózatokban lehetővé teszi a tudás és a tartományból származó adatok egyesítését, az ok-okozati összefüggések kifejezését, annak elkerülését, hogy a modell túl illeszkedjen az adatok képzéséhez és a hiányos adathalmazokból való tanuláshoz.

Dinamikus Bayesi hálózatok

A visszajelzés számos biológiai rendszer alapvető jellemzője. Mi teszi a kísérleti idősoros mérések létrehozását különösen fontos kihívássá a biológiai rendszerek modellezésében.

A bayesi hálózatok alkalmasak a visszacsatolási ciklusok, valamint az idősorok modellezésére. Ezek azok a dinamikus Bayesi hálózatok, amelyek a Bayesi hálózatok használatából állnak az idősorok vagy visszacsatolási hurkok modellezésénél. Ilyen körülmények között a változókat idő szerint indexelik, és a hálózatokban reprodukálják. A rejtett Markov-modellek és a lineáris dinamikus rendszerek a dinamikus Bayes-hálózatok speciális esetei. Rejtett Markov-modellekben van egy rejtett csomópontkészlet (általában diszkrét állapotok), megfigyelt változók halmaza, és a grafikon szeleteinek nem kell időbeli. Gyakran használják szekvenciaelemzésre, különösen génhálózatok esetén.

Dinamikus Bayes-hálózatokat alkalmaztak a genetikai szabályozói interakciók levezetésére a DNS-chip adatokból, egy sejtciklus néhány tucatnyi időpontjából. Különösen az MCMC-vel kombinálva ez lehetővé tette a hálózat következtetési teljesítményéhez való hozzáférést, különböző méretű oktatókészletekkel, előzményekkel és mintavételi stratégiákkal.

Génhálózatok

A génhálózatok jól alkalmazhatók komplex és sztochasztikus biológiai rendszerek modellezésére. Az egyes génexpressziókat egy változóval ábrázolják, amely leírja a gének közötti szabályozást.

Az ilyen típusú hálózatokban a struktúrájuk következtetése, például a szabályozó és jelző hálózatok adatokból történő azonosítása a legérdekesebb szempont. A korrelációs megkülönböztetés lehetővé teszi a mért változók közötti függőségek tisztázását, ezáltal ismeretlen összefüggések és kiváló prediktív modellek megismerését. A modellszerkezetek megtanulása azonban nehéz, és gyakran gondos kísérleti tervezést igényel.

Molekuladinamika

A klasszikus módszer a reakcióba lépő molekulák evolúciójának szimulációjára a kontinuum hipotézisén alapszik. Amikor ezeknek a molekuláknak a reakciócsoportjában reakcióba lépő száma az Avogadro-szám nagyságrendjébe esik, akkor feltételezhető, hogy ez a koncentráció (a halmazban lévő molekulák száma) folyamatos valós változó. Ebben az esetben a tömeghatás klasszikus kinetikája használható a reakciósebességek leírására. Amikor azonban ezeknek a molekuláknak a száma száz vagy ezer nagyságrendű, a kontinuum hipotézist már nem használhatjuk. Ezért a valós értékű koncentrációk helyett az egész számmal értékelt molekulák számát kell figyelembe vennünk. Az alacsony számú molekula másik hatása, hogy a tömeges hatás klasszikus kinetikája már nem érvényes. A reakció sebessége már nem meghatározó, ezért valószínűségi megközelítésre van szükség. Ahelyett, hogy figyelembe vesszük az elfogyasztott reagensek és az időintervallumban előállított termékek mennyiségét, figyelembe kell vennünk annak valószínűségét, hogy egy reakció időközönként bekövetkezik. A reakciók modellezésének ezt a megközelítését sztochasztikus kinetikának nevezik.

Példák a rendszerbiológiára

A sejtbiológiai folyamatok a rendszerbiológiában gyakran véletlenszerűek, a reakcióba lépő molekulák alacsony száma miatt.

Paraméterbecslés MCMC-vel

A sztochasztikus kinetika a rendszerbiológia különféle jelenségeinek modellezésének alapvető elemévé vált. Ezek a modellek, még inkább a determinisztikus modelleknél, nehéz problémát jelentenek a kinetikai paraméterek kísérleti adatokból történő becslésében. Kezdetben a paramétereket biológiailag elfogadható értékekre állítottuk be, majd szabad szemmel úgy állítottuk be, hogy a modell szimulációja hasonlítson a kísérleti adatokra. Ebben az esetben a paraméterbecslések könnyen megszerezhetők a legkisebb négyzetek kiigazításával vagy a legnagyobb valószínűség becslésével. A statisztikai Monte Carlo módszerek alkalmazása azonban lehetővé teszi a modell sztochaszticitásának fenntartását ezen paraméterek becslése során. Ezek a becslési módszerek két jól ismert kategóriába sorolhatók: a maximális valószínűségű és a Bayes-i következtetési módszerek.

A Bayes-i következtetési módszerek megkísérlik megszerezni a paraméterek hátsó eloszlását, amelyet aztán maximalizálni lehet a maximális hátsó becslés megszerzéséhez. A legtöbb bayesi következtetési módszer MCMC technikákon alapszik. A rendszerbiológia alkalmazása sem kivétel:

Lásd is

Bibliográfia

Kapcsolódó cikkek

Egyéb terjesztési mintavétel

Megjegyzések és hivatkozások

  1. (en) R. Milo , N. Kashtan , S. Itzkovitz és MEJ Newman : „  A véletlenszerű gráfok egységes előállításáról előírt fokozatokkal  ” , arXiv: cond-mat / 0312028 ,2004. május 30( online olvasás , konzultáció 2021. február 11 - én )
  2. (in) NTL Tran , S. Mohan , Z. Xu és C.-H. Huang , „  A hálózati motívumok észlelésének aktuális újításai és jövőbeli kihívásai  ” , Briefings in Bioinformatics , vol.  16, n o  3,1 st május 2015, P.  497-525 ( ISSN  1467-5463 és 1477-4054 , DOI  10.1093 / bib / bbu021 , online olvasás , hozzáférés 2021. február 11. )
  3. (in) N. Kashtan S. Itzkovitz , R. Milo és U. Alon , "  Hatékony mintavételi algoritmus a koncentrációk becsléséhez algráf becsléséhez és a hálózati motívumok detektálásához  " , Bioinformatika , vol.  20, n o  11,2004. július 22, P.  1746–1758 ( ISSN  1367-4803 és 1460-2059 , DOI  10.1093 / bioinformatics / bth163 , online olvasás , hozzáférés 2021. február 11. )
  4. (a) S. Wernicke és F. Rasche , "  FANMOD egy eszköz a gyors hálózati minta kimutatására  " , Bioinformatics , vol.  22, n o  9,1 st május 2006, P.  1152–1153 ( ISSN  1367-4803 és 1460-2059 , DOI  10.1093 / bioinformatics / btl038 , online olvasás , hozzáférés 2021. február 11. )
  5. (in) Zahra Razaghi Moghadam Kashani , Hayedeh Ahrabian , Elahe Elahi és Abbas Nowzari-Dalini , "  Kavosh: új algoritmus a hálózati motívumok megtalálásához  " , BMC Bioinformatics , vol.  10, n o  1,2009. október 4, P.  318 ( ISSN  1471-2105 , PMID  19799800 , PMCID  PMC2765973 , DOI  10.1186 / 1471-2105-10-318 , online olvasás , hozzáférés 2021. február 11. )
  6. (in) Xin Li , Rebecca J. Stones , Haidong Wang és Hualiang Deng , "  NetMODE: Pattern Detection Network Nauty nélkül  " , PLoS ONE , vol.  7, n o  12,2012. december 18, e50093 ( ISSN  1932-6203 , PMID  23272055 , PMCID  PMC3525646 , DOI  10.1371 / journal.pone.0050093 , online olvasás , hozzáférés 2021. február 11. )
  7. (in) Stijn van Dongen, "  Graph Klaszterek Flow Simulation  " , doktori értekezés, University of Utrecht ,2000. május
  8. Husmeier, Dirk. , Valószínűségi modellezés a bioinformatikában és az orvosi informatikában , Springer-Verlag London Limited,2005( ISBN  978-1-84628-119-8 és 1-84628-119-9 , OCLC  981318762 , online olvasható )
  9. (in) Ankur Gupta és James B. Rawlings , "  Paraméterbecslési módszerek összehasonlítása sztochasztikus kémiai kinetikai modellekben: Példák a rendszerbiológiára  " , AIChE Journal , Vol.  60, n o  4,2014. április, P.  1253–1268 ( PMID  27429455 , PMCID  PMC4946376 , DOI  10.1002 / aic.14409 , online olvasás , hozzáférés 2021. február 14. )
  10. Michael B. Elowitz , Arnold J. Levine , Eric D. Siggia és Peter S. Swain , "  Sztochasztikus génexpresszió egyetlen sejtben  ", Science (New York, NY) , vol.  297, n o  5584,2002. augusztus 16, P.  1183-1186 ( ISSN  1095-9203 , PMID  12.183.631 , DOI  10,1126 / science.1070919 , olvasható online , elérhető február 14, 2021 )
  11. William J. Blake , Mads KAErn , Charles R. Cantor és JJ Collins , „  Zaj az eukarióta gén expressziójában  ”, Nature , vol.  422, n o  69322003. április 10, P.  633-637 ( ISSN  0028-0836 , PMID  12.687.005 , DOI  10.1038 / nature01546 , olvasható online , elérhető február 14, 2021 )
  12. Jonathan M. Raser és Erin K. O'Shea , „  A sztochaszticitás ellenőrzése az eukarióta gén expresszióban  ”, Science (New York, NY) , vol.  304, n °  5678,2004. június 18, P.  1811–1814 ( ISSN  1095-9203 , PMID  15166317 , PMCID  1410811 , DOI  10.1126 / science.1098641 , online olvasás , hozzáférés 2021. február 14. )
  13. HH McAdams és A. Arkin , „  Sztochasztikus mechanizmusok a génexpresszióban  ”, Proceedings of the National Academy of Sciences of the United States of America , vol.  94, n o  3,1997. február 4, P.  814-819 ( ISSN  0027-8424 , PMID  9023339 , PMCID  PMC19596 , DOI  10,1073 / pnas.94.3.814 , olvasható online , elérhető február 14, 2021 )
  14. A. Arkin , J. Ross és HH McAdams , „  A fejlődési út bifurkációjának sztochasztikus kinetikai elemzése lambda-fertőzött fág Escherichia coli sejtekben  ”, Genetics , vol.  149, n o  4,1998 augusztus, P.  1633–1648 ( ISSN  0016-6731 , PMID  9691025 , PMCID  1460268 , online olvasás , hozzáférés 2021. február 14. )
  15. Leor S. Weinberger , John C. Burnett , Jared E. Toettcher és Adam P. Arkin , „  Sztochasztikus génexpresszió lentivirális pozitív-visszacsatolási hurokban: HIV-1 Tat-ingadozások hajtják a fenotípusos sokféleséget  ”, Cell , vol.  122, n o  22005. július 29, P.  169–182 ( ISSN  0092-8674 , PMID  16051143 , DOI  10.1016 / j.cell.2005.06.006 , online olvasás , hozzáférés 2021. február 14. )
  16. Sebastian C. Hensel , James B. Rawlings és John Yin , „  A vezikuláris stomatitis vírus intracelluláris növekedésének sztochasztikus kinetikai modellezése  ”, Bulletin of Mathematical Biology , vol.  71, n o  7,2009. október, P.  1671–1692 ( ISSN  1522-9602 , PMID  19459014 , PMCID  3169382 , DOI  10.1007 / s11538-009-9419-5 , online olvasás , hozzáférés 2021. február 14. )
  17. Grzegorz A. Rempala , Kenneth S. Ramos és Ted Kalbfleisch , „  A géntranszkripció sztochasztikus modellje: alkalmazás L1 retrotranszpozíciós eseményekhez  ”, Journal of Theoretical Biology , vol.  242, n o  1,2006. szeptember 7, P.  101–116 ( ISSN  0022-5193 , PMID  16624324 , DOI  10.1016 / j.jtbi.2006.02.010 , online olvasás , hozzáférés 2021. február 14. )
  18. Daniel A. Henderson , Richard J. Boys , Kim J. Krishnan és Conor Lawless : „  Bayesi emuláció és a mitokondriális DNS-deléciók sztochasztikus számítógépes modelljének kalibrálása Substantia Nigra Neuronsban  ”, Journal of the American Statistics Association , vol. .  104, n o  485,2009. március, P.  76–87 ( ISSN  0162-1459 és 1537-274X , DOI  10.1198 / jasa.2009.0005 , online olvasás , hozzáférés 2021. február 14. )
  19. A. Golightly és DJ Wilkinson , „  Bayesi következtetés hibával megfigyelt nemlineáris többváltozós diffúziós modellekhez  ”, Computational Statistics & Data Analysis , vol.  52, n o  3,2008. január, P.  1674–1693 ( ISSN  0167–9473 , DOI  10.1016 / j.csda.2007.05.019 , online olvasás , hozzáférés 2021. február 14. )
  20. (a) Darren J. Wilkinson , sztochasztikus modellezés Systems Biology , 3,2018. december 7( ISBN  9781351000918 , DOI  10.1201 / 9781351000918 , online olvasás )
  21. Andrew Golightly és Darren J. Wilkinson , „  Bayesi paraméter-következtetés sztochasztikus biokémiai hálózatmodellekhez, részecske Markov-lánc Monte Carlo felhasználásával  ”, Interface Focus , vol.  1, n o  6,2011. december 6, P.  807–820 ( ISSN  2042-8901 , PMID  23226583 , PMCID  3262293 , DOI  10.1098 / rsfs.2011.0047 , online olvasás , hozzáférés 2021. február 14. )
  22. Andrew Golightly és Darren J. Wilkinson , „  Bayes-i szekvenciális következtetés sztochasztikus kinetikus biokémiai hálózati modellekhez  ”, Journal of Computational Biology: A Journal of Computational Molecular Cell Biology , vol.  13, n o  3,2006. április, P.  838–851 ( ISSN  1066-5277 , PMID  16706729 , DOI  10.1089 / cmb.2006.13.838 , online olvasás , hozzáférés 2021. február 14. )
  23. Tommaso Mazza , Gennaro Iaccarino és Corrado Priami , „  Snazer: a szimulációk és hálózatok elemzője  ”, BMC rendszerek biológiája , vol.  4,2010. január 7, P.  1 ( ISSN  1752-0509 , PMID  20056001 , PMCID  2880970 , DOI  10.1186 / 1752-0509-4-1 , online olvasás , hozzáférés 2021. február 14. )
  24. S. Reinker , RM Altman és J. Timmer , „  Parameter becslés sztochasztikus biokémiai reakciókban  ”, IEE Proceedings - Systems Biology , vol.  153, n o  4,2006, P.  168. szám ( ISSN  1741-2471 , DOI  10.1049 / ip-syb: 20050105 , online olvasás , hozzáférés : 2021. február 14. )
  25. Ido Golding , Johan Paulsson , Scott M. Zawilski és Edward C. Cox , „Az  egyes baktériumok génaktivitásának valós idejű kinetikája  ”, Cell , vol.  123, n o  6,2005. december 16, P.  1025–1036 ( ISSN  0092-8674 , PMID  16360033 , DOI  10.1016 / 2005.09.031. J.cell. , Online olvasás , hozzáférés : 2021. február 14. )
  26. Suresh Kumar Poovathingal és Rudiyanto Gunawan , „  Globális paraméterbecslési módszerek sztochasztikus biokémiai rendszerekhez  ”, BMC Bioinformatics , vol.  11, n o  1,2010. augusztus 6( ISSN  1471-2105 , DOI  10.1186 / 1471-2105-11-414 , online olvasás , konzultáció 2021. február 14 - én )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">