Metoda Monte-Carlo podle Markovových řetězců

Metoda Monte-Carlo podle Markovových řetězců
Podtřída Vzorkování
Pojmenováno odkazem na Andreï Markov , Monte Carlo

Tyto metody Monte Carlo Markov řetězu , nebo MCMC metody pro Markov Chain Monte Carlo v angličtině , jsou třídou metod pro odběr vzorků z rozdělení pravděpodobnosti. Tyto metody Monte-Carlo jsou založeny na dráze Markovových řetězců, jejichž stacionární zákony jsou distribuce, které mají být vzorkovány.

Některé metody používají náhodné procházky po Markovových řetězcích ( algoritmus Metropolis-Hastings , vzorkování Gibbs ), zatímco jiné, složitější algoritmy, zavádějí omezení na cesty, aby se pokusili urychlit konvergenci ( Monte Carlo Hybrid  (en) , Postupná nadměrná relaxace )

Tyto metody se uplatňují zejména v rámci Bayesiánského závěru .

Intuitivní přístup

Umístíme se do vektorového prostoru konečné dimenze n . Chceme náhodně generovat vektory podle rozdělení pravděpodobnosti π . Proto chceme mít sekvenci vektorů takovou, aby distribuce přístupů π .

Metody Monte-Carlo podle Markovových řetězců spočívají ve generování vektoru pouze z dat vektoru  ; jedná se tedy o „paměťový“ proces, který charakterizuje markovské řetězce. Musíme tedy najít náhodný generátor s distribucí pravděpodobnosti , který nám umožní generovat z . Proto jsme se nahradit problém generace s distribuční n u problémů generace s distribucí , které, jak doufáme, bude jednodušší.

Zásada

Chceme simulovat zákon π na obecném stavovém prostoru ( Ω  ; Ɛ ) . Přechod na ( Ω  ; Ɛ ) je mapa P  : ( Ω  ; Ɛ ) → [0; 1] tak, že P (·, A ) pro všechna A ∈ Ɛ je měřitelná a P ( x , ·) pro všechna x ∈ Ω je pravděpodobnost zapnuto ( Ω  ; Ɛ ) . Nechť X  = ( X K , k ∈ℕ) homogenní Markov řetěz přechodu P a počáteční advokátní X 0  ~  V , je P v zákon řetězec X .

Abychom simulovali π , chceme vědět, jak vytvořit přechod P tak, že ∀  v , vP k  →  π , s konvergencí v normě v celkové variaci ∥ μ ∥ = sup A ∈ Ɛ μ ( A ) - inf A ∈ Ɛ μ ( A ) . Přechodový řetězec P je ergodický .

Konvergence Markovova řetězce  -  Pokud je přechod P je π- redukovatelný, π -invariantní, neperiodický, Harrisův rekurentní, pak ∀ x , P k ( x , ·) → k → ∞  π .

Poslední delikátní podmínka je splněna v případě Gibbsova vzorkování a algoritmu Metropolis-Hastings .

Metody odběru vzorků

K odhadu zadní (úplné) distribuce parametrů modelu se používají metody odběru vzorků. Mezi nimi jsou metody Monte Carlo velmi přesné. Jsou však výpočetně nákladné a konvergence trvá dlouho. Jsou také omezeny velikostí vzorku, protože se stanou nerozpustnými, když jsou příliš velké. I na malých vzorcích může být výpočet rozdělení pravděpodobnosti obtížný. Existuje několik přístupů k tomuto problému, které se používají k získání sady dobrých vzorkovacích sítí ze zadní distribuce.

Konstrukce náhodných sítí a hledání vzorů

Metoda Monte Carlo podle Markovových řetězců se často používá v algoritmech zabývajících se sítěmi (biologickými i jinými). Je možné několik různých aplikací, včetně 2 hlavních: generování náhodných sítí a klasifikace prvků v grafech. Příklady pro ilustraci použití MCMC níže budou založeny na biologii.

Náhodné sítě

MCMC se velmi často používá ke generování náhodných sítí sloužících jako nulové modely, co nejblíže náhodě, při zachování základních charakteristik sítě, která je studována, aby zůstala srovnatelná. Tyto nulové modely pak umožňují určit, zda jsou charakteristiky studované sítě statisticky významné nebo ne.

Průběh metody je jednoduchý: berou se v úvahu 2 hrany (A -> B; C -> D) a poté je zvážena a přijata výměna uzlů těchto hran (A -> D; C -> B) pouze pokud nové hrany již neexistují a není zde žádná cyklická hrana (A -> A). Počet uvažovaných výměn se často řídí vzorcem Q x E, kde E je počet hran skutečné sítě (často studovaná síť) a Q je dostatečně vysoké číslo, aby byla zajištěna náhodnost produktové sítě, často nastavená na 100 .

Použití metody Monte Carlo Markovovými řetězci ke generování nulového modelu, proti kterému určujeme význam jednoho (nebo více) znaků, lze nalézt pod názvem „přepínací algoritmus“, přičemž „odpovídající algoritmus“ je alternativa při generování náhodných sítí. Ten, který nepoužívá MCMC, také představuje nevýhodu přítomnosti zkreslení v produktových sítích. Tyto algoritmy se v biologii nejčastěji používají k hledání vzorů v sítích, podgrafů složených z omezeného počtu uzlů a které se nacházejí ve velmi velkém počtu sítí. Mezi nástroje, které používají MCMC ke generování náhodných sítí, patří mfinder, FANMOD, KAVOSH a NetMODE.

Hledání vzoru

Pokud jde o použití MCMC pro klasifikaci prvků v grafu, hovoří se zejména o „Markovově shlukování“ (MCL), což je bezkontaktní klasifikační metoda založená na konceptu „náhodného procházení“, která nevyžaduje téměř žádné apriorní informace, aby umět klasifikovat prvky grafu. Přesněji řečeno, počínaje od uzlu, když „procházíme“ od uzlu k uzlu přes okraje, máme tendenci častěji procházet mezi uzly, které jsou ve stejné skupině, než vytvořit jednotný průchod mezi všemi uzly. Tím, že se zvyšuje důležitost často překračovaných hran a snižuje se význam méně překřížených hran, se skupiny v síti postupně aktualizují.

Aplikace na biologii

Existují dva hlavní typy použití MCMC v systémové biologii , jmenovitě genová pole a molekulární dynamika, které lze shrnout jako systém molekul. V obou případech jde o pochopení složitých interakcí mezi několika prvky. Proto je metoda MCMC kombinována s Bayesianskými sítěmi.

Bayesovské sítě

Tyto Bayesovské sítě se běžně používají v biologii a systémů spojených s MCMC. Poskytují úhledné a kompaktní znázornění distribuce běžných pravděpodobností systémů. Jejich použití v grafických modelech má několik výhod. Nejprve mohou představovat kauzální vztahy / závislosti mezi proměnnými a lze je tedy interpretovat jako kauzální model, který generuje data. Bayesovské sítě jsou navíc užitečné pro přizpůsobení parametrů modelu strojového učení, ať už se používá k provádění predikce nebo klasifikace dat. Bayesovská teorie pravděpodobnosti se také ukázala jako účinná při popisu nejistoty a při přizpůsobování počtu parametrů velikosti dat. Reprezentace a použití teorie pravděpodobnosti v biologických sítích umožňuje jak kombinovat znalosti a data z domény, vyjádřit vztahy příčiny a následku, vyhnout se přílišnému modelu pro trénování dat a poučení se z neúplných datových sad.

Dynamické Bayesovské sítě

Zpětná vazba je základní charakteristikou mnoha biologických systémů. Díky čemuž je tvorba experimentálních měření časových řad obzvláště důležitou výzvou při modelování biologických systémů.

Bayesovské sítě jsou vhodné pro modelování zpětnovazebních smyček i časových řad. Jedná se o dynamické Bayesovské sítě, které spočívají v použití Bayesianských sítí při modelování časových řad nebo zpětnovazebních smyček. Za těchto podmínek jsou proměnné indexovány podle času a reprodukovány v sítích. Ze skrytých Markovových modelů a lineárních dynamických systémů jsou speciální případy dynamických Bayesovských sítí. Ve skrytých Markovových modelech existuje skrytá sada uzlů (obvykle diskrétní stavy), sada pozorovaných proměnných a řezy grafu nemusí být časové. Často se používají pro sekvenční analýzu, zejména v případě genových sítí.

Dynamické Bayesiánské sítě byly použity k odvození genetických regulačních interakcí z dat DNA čipů z několika desítek časových bodů z buněčného cyklu. Zejména v kombinaci s MCMC to umožnilo přístup k výkonu síťové inference s různými velikostmi tréninkových sad, předchůdců a strategií vzorkování.

Genové sítě

Genové sítě jsou velmi vhodné pro modelování složitých a stochastických biologických systémů. Představují expresi každého genu proměnnou popisující regulaci mezi geny.

V tomto typu sítí je nejzajímavějším aspektem odvození jejich struktur, například identifikace regulačních a signalizačních sítí z dat. Korelační rozlišení umožňuje objasnit závislosti mezi měřenými proměnnými, a tedy naučit se neznámé vztahy a vynikající prediktivní modely. Učení modelových struktur je však obtížné a často vyžaduje pečlivý experimentální návrh.

Molekulární dynamika

Klasická metoda simulace vývoje reagujících molekul v čase je založena na hypotéze kontinua. Když je počet těchto molekul reagujících v sadě reakcí řádově jako číslo Avogadro, můžeme předpokládat, že tato koncentrace (počet molekul v sadě) je spojitá reálná proměnná. V tomto případě lze k popisu reakčních rychlostí použít klasickou kinetiku masové akce. Když je však počet těchto molekul řádově stovky nebo tisíce, nemůžeme již používat hypotézu kontinua. Proto namísto koncentrací se skutečnou hodnotou musíme vzít v úvahu počet molekul s celočíselnou hodnotou. Dalším účinkem nízkého počtu molekul je, že klasická kinetika hromadného působení již není platná. Reakční rychlosti již nejsou deterministické, proto je nutný pravděpodobnostní přístup. Místo toho, abychom vzali v úvahu množství spotřebovaných činidel a produktů vyrobených v časovém intervalu, musíme vzít v úvahu pravděpodobnost reakce, která nastane v časovém intervalu. Tento přístup k modelování reakcí je znám jako stochastická kinetika.

Příklady v biologii systémů

Buněčné procesy v biologii systémů často vykazují náhodnost způsobenou nízkým počtem reagujících molekul.

Odhad parametrů pomocí MCMC

Stochastická kinetika se stala základním prvkem pro modelování různých jevů v systémové biologii. Tyto modely, dokonce více než deterministické modely, představují obtížný problém v odhadu kinetických parametrů z experimentálních dat. Zpočátku byly parametry nastaveny na biologicky přijatelné hodnoty, poté upraveny pouhým okem tak, aby simulace modelu připomínala experimentální data. V tomto případě lze odhady parametrů snadno získat úpravou nejmenších čtverců nebo odhadem maximální pravděpodobnosti. Použití statistických metod Monte Carlo však umožňuje udržovat stochasticitu modelu během odhadu těchto parametrů. Tyto metody odhadu lze rozdělit do dvou dobře známých kategorií: metody maximální věrohodnosti a Bayesovské metody odvození.

Bayesovské odvozovací metody se pokoušejí získat zadní rozdělení parametrů, které lze poté maximalizovat, aby se získaly maximální zadní odhady. Většina Bayesianových odvozovacích metod je založena na technikách MCMC. Aplikace na biologii systémů není výjimkou:

Podívejte se také

Bibliografie

Související články

Další vzorkování distribuce

Poznámky a odkazy

  1. (en) R. Milo , N. Kashtan , S. Itzkovitz a MEJ Newman , „  O jednotném generování náhodných grafů s předepsanými sekvencemi stupňů  “ , arXiv: cond-mat / 0312028 ,30. května 2004( číst online , konzultováno 11. února 2021 )
  2. (in) NTL Tran , S. Mohan , Z. Xu a C.-H. Huang , „  Aktuální inovace a budoucí výzvy detekce síťových motivů  “ , Briefings in Bioinformatics , sv.  16, n o  3,1 st 05. 2015, str.  497-525 ( ISSN  1467-5463 a 1477-4054 , DOI  10.1093 / bib / bbu021 , číst online , přístup k 11. února 2021 )
  3. (in) N. Kashtan S. Itzkovitz , R. Milo a U. Alon , „  Efektivní algoritmus vzorkování pro odhad podgrafu koncentrací a Detection Network motivs  “ , Bioinformatics , sv.  20, n o  11,22. července 2004, str.  1746–1758 ( ISSN  1367-4803 a 1460-2059 , DOI  10.1093 / bioinformatika / bth163 , číst online , přístup k 11. února 2021 )
  4. (in) S. Wernicke a F. Rasche , „  FANMOD nástroj pro rychlou detekci síťových vzorů  “ , Bioinformatics , sv.  22, n o  9,1 st 05. 2006, str.  1152–1153 ( ISSN  1367-4803 a 1460-2059 , DOI  10.1093 / bioinformatics / btl038 , číst online , přístup k 11. února 2021 )
  5. (in) Zahra Razaghi Moghadam Kashani , Hayedeh Ahrabian , Elahe Elahi a Abbas Nowzari-Dalini , „  Kavosh: nový algoritmus pro hledání síťových motivů  “ , BMC Bioinformatics , sv.  10, n o  1,4. října 2009, str.  318 ( ISSN  1471-2105 , PMID  19799800 , PMCID  PMC2765973 , DOI  10.1186 / 1471-2105-10-318 , číst online , přistupováno 11. února 2021 )
  6. (in) Xin Li , Rebecca J. Stones , Haidong Wang a Hualiang Deng , „  NetMODE: Pattern Detection Network without Nauty  “ , PLoS ONE , sv.  7, n O  12,18. prosince 2012, e50093 ( ISSN  1932-6203 , PMID  23272055 , PMCID  PMC3525646 , DOI  10.1371 / journal.pone.0050093 , číst online , přistupováno 11. února 2021 )
  7. (in) Stijn van Dongen, „  Shlukování grafů pomocí simulace toku  “ , disertační práce, University of Utrecht ,Květen 2000
  8. Husmeier, Dirku. , Pravděpodobnostní modelování v bioinformatice a lékařské informatice , Springer-Verlag London Limited,2005( ISBN  978-1-84628-119-8 a 1-84628-119-9 , OCLC  981318762 , číst online )
  9. (in) Ankur Gupta a James B. Rawlings , „  Srovnání metod odhadu parametrů ve stochastických chemických kinetických modelech: Příklady v biologii systémů  “ , AIChE Journal , Vol.  60, n O  4,dubna 2014, str.  1253–1268 ( PMID  27429455 , PMCID  PMC4946376 , DOI  10.1002 / aic.14409 , číst online , přístup k 14. února 2021 )
  10. Michael B. Elowitz , Arnold J. Levine , Eric D. Siggia a Peter S. Swain , „  Stochastická genová exprese v jedné buňce  ,“ Science (New York, NY) , sv.  297, n O  5584,16. srpna 2002, str.  1183–1186 ( ISSN  1095-9203 , PMID  12183631 , DOI  10.1126 / science.1070919 , číst online , přístup ke dni 14. února 2021 )
  11. William J. Blake , Mads KAErn , Charles R. Cantor a JJ Collins , „  Hluk v expresi eukaryotických genů  “, Nature , sv.  422, n O  6932,10. dubna 2003, str.  633–637 ( ISSN  0028-0836 , PMID  12687005 , DOI  10.1038 / nature01546 , číst online , přistupovat 14. února 2021 )
  12. Jonathan M. Raser a Erin K. O'Shea , „  Kontrola stochasticity v expresi eukaryotických genů  “, Science (New York, NY) , sv.  304, n O  5678,18. června 2004, str.  1811–1814 ( ISSN  1095-9203 , PMID  15166317 , PMCID  1410811 , DOI  10.1126 / science.1098641 , číst online , zpřístupněno 14. února 2021 )
  13. HH McAdams a A. Arkin , „  Stochastické mechanismy v genové expresi  “, Sborník Národní akademie věd Spojených států amerických , sv.  94, n o  3,4. února 1997, str.  814–819 ( ISSN  0027-8424 , PMID  9023339 , PMCID  PMC19596 , DOI  10.1073 / pnas.94.3.814 , číst online , přístup ke dni 14. února 2021 )
  14. A. Arkin , J. Ross a HH McAdams , „  Stochastická kinetická analýza bifurkace vývojových cest v buňkách Escherichia coli infikovaných fágovými lambda  “, Genetics , sv.  149, n O  4,Srpna 1998, str.  1633–1648 ( ISSN  0016-6731 , PMID  9691025 , PMCID  1460268 , číst online , přístup ke dni 14. února 2021 )
  15. Leor S. Weinberger , John C. Burnett , Jared E. Toettcher a Adam P. Arkin , „  Stochastická genová exprese v lentivirové smyčce pozitivní zpětné vazby: fluktuace HIV-1 Tat řídí fenotypovou rozmanitost  “, Cell , sv.  122, n O  229. července 2005, str.  169–182 ( ISSN  0092-8674 , PMID  16051143 , DOI  10.1016 / j.cell.2005.06.006 , číst online , přístup ke dni 14. února 2021 )
  16. Sebastian C. Hensel , James B. Rawlings a John Yin , „  Stochastické kinetické modelování intracelulárního růstu viru vezikulární stomatitidy  “, Bulletin of Mathematical Biology , sv.  71, n o  7,října 2009, str.  1671–1692 ( ISSN  1522-9602 , PMID  19459014 , PMCID  3169382 , DOI  10.1007 / s11538-009-9419-5 , číst online , přístup ke dni 14. února 2021 )
  17. Grzegorz A. Rempala , Kenneth S. Ramos a Ted Kalbfleisch , „  Stochastický model genové transkripce: aplikace na události retrotranspozice L1  “, Journal of Theoretical Biology , sv.  242, n o  1,7. září 2006, str.  101–116 ( ISSN  0022-5193 , PMID  16624324 , DOI  10.1016 / j.jtbi.2006.02.010 , číst online , přístup ke dni 14. února 2021 )
  18. Daniel A. Henderson , Richard J. Boys , Kim J. Krishnan a Conor Lawless , „  Bayesiánská emulace a kalibrace stochastického počítačového modelu delecí mitochondriální DNA u Substantia Nigra Neurons  “, Journal of the American Statistical Association , sv. .  104, n o  485,Březen 2009, str.  76–87 ( ISSN  0162-1459 a 1537-274X , DOI  10.1198 / jasa.2009.0005 , číst online , přístup ke dni 14. února 2021 )
  19. A. Golightly a DJ Wilkinson , „  Bayesiánský závěr pro nelineární vícerozměrné difúzní modely pozorovaný s chybou  “, Computational Statistics & Data Analysis , sv.  52, n o  3,Leden 2008, str.  1674–1693 ( ISSN  0167-9473 , DOI  10.1016 / j.csda.2007.05.019 , číst online , přístup ke dni 14. února 2021 )
  20. (in) Darren J. Wilkinson , Stochastic Modeling for Systems Biology , 3,7. prosince 2018( ISBN  9781351000918 , DOI  10.1201 / 9781351000918 , číst online )
  21. Andrew Golightly a Darren J. Wilkinson , „  Bayesiánská inference parametrů pro stochastické modely biochemických sítí využívající částicový Markovův řetězec Monte Carlo  “, Interface Focus , sv.  1, n O  6,6. prosince 2011, str.  807–820 ( ISSN  2042-8901 , PMID  23226583 , PMCID  3262293 , DOI  10.1098 / rsfs.2011.0047 , číst online , přístup k 14. února 2021 )
  22. Andrew Golightly a Darren J. Wilkinson , „  Bayesianova sekvenční inference pro stochastické kinetické biochemické síťové modely  “, Journal of Computational Biology: A Journal of Computational Molecular Cell Biology , sv.  13, n o  3,Dubna 2006, str.  838–851 ( ISSN  1066-5277 , PMID  16706729 , DOI  10.1089 / cmb.2006.13.838 , číst online , přístup ke dni 14. února 2021 )
  23. Tommaso Mazza , Gennaro Iaccarino a Corrado Priami , „  Snazer: simulátor a síťový analyzátor  “, BMC systems biologie , sv.  4,7. ledna 2010, str.  1 ( ISSN  1752-0509 , PMID  20056001 , PMCID  2880970 , DOI  10.1186 / 1752-0509-4-1 , číst online , přístup ke dni 14. února 2021 )
  24. S. Reinker , RM Altman a J. Timmer , „  Odhad parametrů ve stochastických biochemických reakcích  “, IEE Proceedings - Systems Biology , sv.  153, n O  4,2006, str.  168 ( ISSN  1741-2471 , DOI  10.1049 / ip-syb: 20050105 , číst online , přístup ke dni 14. února 2021 )
  25. Ido Golding , Johan Paulsson , Scott M. Zawilski a Edward C. Cox , „  Kinetika genové aktivity v jednotlivých bakteriích v reálném čase  “, Cell , sv.  123, n O  6,16. prosince 2005, str.  1025–1036 ( ISSN  0092-8674 , PMID  16360033 , DOI  10.1016 / j.cell.2005.09.031 , číst online , přístup ke dni 14. února 2021 )
  26. Suresh Kumar Poovathingal a Rudiyanto Gunawan , „  globální metody odhadu parametrů pro náhodných biochemických systémů  “, BMC Bioinformatics , vol.  11, n o  1,6. srpna 2010( ISSN  1471-2105 , DOI  10.1186 / 1471-2105-11-414 , číst online , konzultováno 14. února 2021 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">