boolovské sítě Rekonstrukce boolovských sítí PB051: Výpočetní metody v bioinformatice a systémové biologii David Šafránek 11.5.2012 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky, EVROPSKÁ UNIE INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ boolovské sítě rekonstrukce boolovskych sítí Obsah Boolovské sítě -L C boolovské sítě Rekonstrukce boolovských sítí Příklad modelu - autoregulace t>{ protein A gene a boolovské sítě Rekonstrukce boolovských sítí Příklad modelu - autoregulace o( protein A gene a 0 12 3 4 • identifikace diskrétních úrovní exprese boolovské sítě Rekonstrukce boolovských sítí Příklad modelu - autoregulace protein A gene a 0 1 2 spontánní (tzv. bázová) transkripce: A —> 4 boolovské sítě Rekonstrukce boolovských sítí Příklad modelu - autoregulace ->( protein A ) gene a 0 1 2 • místo projevu regulace (A 6 {3,4} =4> regulace aktivní) boolovské sítě Rekonstrukce boolovských sítí Příklad modelu - autoregulace protein A gene a cílový bod regulace (A G {3, 4} A 0) boolovské sítě Rekonstrukce boolovských sítí Stavový prostor - autoregulace • přechodový systém (S, T, So) • S množina stavů, S = {0,1, 2, 3,4} • So C S množina počátečních stavů • T C S x S přechodová relace: zdrojový stav aktivní regulace cílový stav 0 0; [A -> 4] 1 1 0; [A 4] 2 2 0; [4 4] 3 3 >A ->•- 4; [A ->• 0] 2 4 /4 A 0] 3 boolovské sítě rekonstrukce boolovskych sítí Stavový prostor - autoregulace přechodový systém pro negativní autoregulaci (S, T, Sq = S) : 4 0 V \r 3 1 V v / 2 boolovské sítě Rekonstrukce boolovských sítí Příklad modelu složené regulace gene a gene b boolovské sítě Rekonstrukce boolovských sítí Diskrétní charakteristika dynamiky • identifikace diskrétních úrovní exprese boolovské sítě rekonstrukce boolovskych sítí Diskrétní charakteristika dynamiky • spontánní (tzv. bázová) transkripce: /\ —^ 1, B —> 2 boolovské sítě Rekonstrukce boolovských sítí Charakteristika regulace - autoregulace protein A gene a gene b 0 1 místo projevu regulace B B (B = 2 =4> regulace aktivní) boolovské sítě Rekonstrukce boolovských sítí Charakteristika regulace - autoregulace protein A gene a gene b 0 1 cílový bod regulace B B (B = 2 B -> 0) boolovské sítě rekonstrukce boolovskych sítí Charakteristika regulace - vstupní funkce • místo projevu regulace B —> A (B £ {1, 2} =4> reg. aktivní) boolovské sítě rekonstrukce boolovskych sítí Charakteristika regulace - vstupní funkce • místo projevu regulace A —> A (A = 1 =4> reg. aktivní) boolovské sítě rekonstrukce boolovskych sítí Charakteristika regulace - vstupní funkce • AND-kompozice regulací A —>► A A B —>► A /4 = 1 A ß e {1, 2} =4> regulace aktivní boolovské sítě Rekonstrukce boolovských sítí Charakteristika regulace - vstupní funkce • cílový bod složené regulace A —> A A B —> A: A = lABe{l,2}=>A^>0 boolovské sítě Rekonstrukce boolovských sítí Stavový prostor - synchronní sémantika • přechodový systém (S, T, So) • S = {0,1} x {0,1, 2} • So C S, uvažujeme So = S • T C S x S přechodová relace (zobrazení): zdrojový stav aktivní regulace cílový stav [0,0] 0; [A -+ 1, 8 -> 2] [1,1] [0,1] B A; [A -> 1, e -> 2] [1,2] [0,2] 8 —>~ B A B —>- /4; [>4 1, 8 ->0] [1,1] [1,0] 4 /*; [4 ->■ 1, 8 2] [1,1] [1,1] /4 —>~ A A B —>- /4; [/A 0, 8 -+2] [0,2] [1,2] /4 —>~ /4 a 8 —>_ /4 a 8 —>~ 8; [/l^ o, e - + 0] [0,1] boolovské sítě Rekonstrukce boolovských sítí Stavový prostor - synchronní sémantika přechodový systém (S, 7", Sq = S \ 12 boolovské sítě Rekonstrukce boolovských sítí Stavový prostor - asynchronní sémantika • přechodový systém (S, T, So) • S = {0,1} x {0,1,2} • So C S, uvažujeme So = S • T C S x S přechodová relace: zdroj, stav aktivní regulace cílové stavy [0,0] 0; [A ->■ 1, B -> 2] [1,0], [0,1] [0,1] 6->-/l; [>4 -> 1, 6 -> 2] [1,1], [0,2] [0,2] e ->- e a e a [/\ -> i, e ->0] [0,1], [1,2] [1,0] a [a -> i, e ->• 2] [1,1] [1,1] /4 —»~ /4 a 8 —>~ A; [A->0,B- -►2] [0,1], [1,2] [1,2] A —»~ /4 a 8 —>~ /l a 8 —>~ 6; [>4 -> o, e -> o] [0,2], [1,1] boolovské sítě Rekonstrukce boolovských sítí Stavový prostor - asynchronní sémantika přechodový systém (S, 7", Sq = S -□ 10 boolovské sítě Rekonstrukce boolovských sítí Vlastnosti diskrétních sémantik • synchronní sémantika • efekt aktivních regulací uplatněn pro všechny proteiny ve stejný okamžik • nerealistická approximace, dává však deterministický přechodový systém • asynchronní sémantika • efekt aktivních regulací uplatněn pro každý protein individuálně (interleaving) • nutno uvažovat všechny možné souběhy • věrnější aproximace, dává však nedeterministický přechodový systém • možnost definovat priority boolovské sítě Rekonstrukce boolovských sítí Nástroj GINsim • nástroj Gene Interaction Network simulation (GINsim) http://gin.univ-mrs.fr/GINsim/accueil.html • umožňuje asynchronní i synchronní simulaci transkripční regulace • inherentně diskrétní model (vícehodnotová logika) • místo přesné hodnoty koncentrace rozlišujeme několik diskrétních úrovní • s každou regulací spjat aktivační interval diskrétních úrovní specifikující kdy je regulující protein aktivní • u každého proteinu je specifikován individuální/kompozitiní projev vstupních regulací • možnost neregulované (bázové) transkripce • grafové algoritmy pro transkripční sít i přechodový systém boolovské sítě rekonstrukce boolovskych sítí Obsah Rekonstrukce boolovských sítí boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat • diskretizace microarray dat (časová řada, množina řad) • clustering genů do skupin s podobným profilem • inference logiky v dynamice klastrů boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat Diskretizace • metody řízené absolutními hodnotami • metody citlivé na variace mezi jednotlivými časovými body • matice expresních dat Ajj £ K. • cílem je získat matici diskretizovanou An £ {0,1} boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat Diskretizace metody řízené absolutními hodnotami: dle průměrné hodnoty exprese A- = l l'A'ij ~ A'ÍJ Q Jinak A\j zn. průměrnou hodnotu exprese (lze nahradit Ay, Au) boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat Diskretizace metody řízené absolutními hodnotami: dle průměrné hodnoty exprese A- = l l'A'ij ~ A'ÍJ Q Jinak A\j zn. průměrnou hodnotu exprese (lze nahradit Ay, Au) boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat Diskretizace metody řízené absolutními hodnotami: dle mediánu exprese (mezi nejnižší a nejvyšší hodnotou) 0 Jinak M/j zn. medián exprese (lze nahradit My, M;j) boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat Diskretizace metody řízené absolutními hodnotami: dle maxima exprese 1,A'..>HU{1-X) 0 Jinak H/j zn. maximum exprese (lze nahradit Hy, Hu) X £ [0,1] je procento maxima uvažované jako prahová hodnota boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat Diskretizace metody řízené absolutními hodnotami TOP X% Aí! = l 1, pokud Pozice{A^sort{Af))>^ Q Jinak sort(Á) zn. seznam prvků matice A setříděných vzestupně pozice(x, L) zn. pozici prvku x v seznamu L boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat Diskretizace metody citlivé na variaci časové řady: diskriminační metoda (Transitional State Discrimination) využívá normalizace hodnot prostřednictvím z-skóre: x — fl z =- a kde a je standardní odchylka, ji je průměrná hodnota exprese Ar, = l l'\A'ti ~ A'i[j-i)\ - 1 0 Jinak ŕ je diskriminační počet std. odchylek boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat • vstup: množina uzlů (odp. klastrů) V = {v±, v2,vn} • pro každý uzel v; urči, jakým způsobem podmnožina uzlů U — {ui,Uq] C V vysvětluje expresní profil uzlu v\ (detekce způsobu regulace) • k tomu je nutno projít všechny časové body všech časových řad • výsledkem předch. kroku je aktivační-inhibiční funkce tvaru v;(t + 1) = (ui(t) V u2(t) V ...) A ->(ü/(t) V uj+i(t) V ...) kde ui, u2, ••• ^ U jsou aktivátory, uj, ... C (V jsou inhibitory • procedura je spuštěna pro každé možné nastavení q, tedy • typicky stačí q < 5 • výstup: množina potenciálních modelů (sítí) boolovské sítě Rekonstrukce boolovských sítí Rekonstrukce boolovských sítí z microarray dat • v = {vi, v2, ^3} • výstupem pro q = 3 a uzel u3 je funkce vs(t+l) = ui(t) A-.vž(t) Time 1 2 4 5 6 Gene <) 0 1 í) 0 i": 0 0 1 0 0 0 0 0 boolovské sítě Rekonstrukce boolovských sítí Literatura Bower, J.M. & Bolouri, H. Computational Modeling of Genetic and Biochemical Networks. Bradford Book, 2001. A.G. Gonzalez, A. Naldi, L. Sanchez, D.Thieffry, C. Chaouiya. GINsim: a software suite for the qualitative modelling, simulation and analysis of regulatory networks. Biosystems (2006), 84(2):91-100 Kauffman, S. A. (1969). Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of Theoretical Biology, 22:437-467 Martin, S. et al. (2007) Boolean dynamics of genetic regulatory networks inferred from microarray time series data. Bioinformatics, 23(7):866-874