Intervalově lineární' aproximace transkripční regulace Booleovské sítě PB054-' Formální modely v systémové biologii David Šafránek 14.5.2010 Intervalově lineární aproximace transkripční regulace Obsah Booleovské sítě Intervalově lineární aproximace transkripční regulace Booleovské sítě Intervalově lineární aproximace transkripční regulace Obsah Booleovské sítě Intervalově lineární aproximace transkripční regulace Booleovské sítě Intervalově lineární aproximace transkripční regulace Booleovské sítě Aproximace vstupních funkcí • vzhledem k S-charakteru vstupní funkce lze uplatnit její aproximaci pomocí schodové funkce regulace aktivátorem X: f+(X) = pmaxg+(X) » /3maxs+(X, K) regulace represorem X: r (X) = l3maxQ-{X) » (3maxs-{X, K) s+(X, K) = | £ || * > KK s-(X, K) = 1 - s+(X, K) • spojitý model je aproximován náhradou Hillových funkcí schodovými funkcemi (kinetická logika) Intervalově lineární' aproximace transkripční regulace Booleovské sítě Diskretizace vstupní funkce (s+(X) « g+(X)) Hill Function ■ 1st Derivative - 2nd Derivative Intervalově lineární' aproximace transkripční regulace Booleovské sítě Diskretizace vstupní funkce (s+(X) « g+(X)) Hill Function 1 0.8 --- 1st Derivative 0,6 0.4 '/i / /V ----2nd Derivative 0.2 / / / \ \ 2 6 8 10 0.2 \/ Intervalově lineární aproximace transkripční regulace Příklad modelu regulace Booleovské sítě d[Crp] dt Signal S Crp:S ("Čip) [P2l 1 crp 1 —>■ Crp —> Crp; Fis, Crp, S Crp —>■ P°Pl + ffl? r (Fis) + PP?f-(Fis)f+(Crp, S) - 7[Crp] Intervalově lineární aproximace transkripční regulace Příklad modelu regulace Booleovské sítě Signal S K2 Crp:S [Pil 1 <=rp 1 —> Crp —> Crp; Fis, Crp, S Crp —> ^1 » fPPl+fi%xs-{Fis, K1)+pP2axs-(Fis, K2)f+(Crp, S)-7[Crp] Intervalově lineární aproximace transkripční regulace Příklad modelu regulace Booleovské sítě Signal S K2 Crp:S (Š) [Pil 1 <=rp 1 —> Crp —> Crp; Fis, Crp, S Crp —> ^1 » /rPl+Pftxs-(Fis, K1)+pP2axs-(Fis, K2)f+(Crp, S)-7[Crp] Intervalově lineární aproximace transkripční regulace Booleovské sítě Příklad modelu regulace K2 K3 Signál S Ks Crp:S Crp [Pil 1 <=rp | Crp Crp; Fis, Crp, S Crp « ffPx+f}%*s-{Fis, K1)+f3^s-{Fis, K2)s+{Crp, K,)s+{5, Ks)-7[Crp] Intervalově lineární' aproximace transkripční regulace Booleovské sítě Intervalově lineární model transkripční regulace Intervalově lineární aproximace transkripční regulace Booleovské sítě Koncentrační prahy • prahy na proměnné [A] • vstup pro represní funkci proteinu A, práh 0\ • intervalová charakteristika oboru hodnot: 0 < 6\ < maxa ^[A]e{(o,el),el(elm3xa)} • prahy na proměnné [B] • vstup pro represní funkci proteinu A, práh 0\ • vstup pro represní funkci proteinu B, práh d\ • intervalová charakteristika oboru hodnot: 0 < e\ < d\ < maxb [B] e {(o, e\), el (el e\\ e\, {el maXb)} Intervalově lineární aproximace transkripční regulace Booleovské sítě Kvalitativní charakteristika ^4, ^ s-(A,el) s-(B,el) s-(B,el) dA dt dB dt <$>A *e 0 * 1 -7ÄA] 13b - lb[B] 0 Ěk. 76 0 * 0 -lb[B] 0 0 1 1 1 Pb ~ lb[B] ̱ 7a Ěk 7fc 1 1 0 /3a ~ 7e[A] -lb[B] Ěí 7a 0 • pro každou kombinaci je soustava lineární • množina domén lineární regulace (regulatornídomény): {(o, el), (el maxa)} x {(o, e\i (el e\\ (e2b, maxb)} • řešení v doméně D směřují ke stejnému ekvilibriu Í>(D) • v příkladu celkem 6 regulatorních domén Intervalově lineární' aproximace transkripční regulace Booleovské maxa [A] Rozděleni prostoru řešeni [B] maxb Intervalově lineární aproximace transkripční regulace Booleovské sítě maxa 7a [A] Určeni pozice ekvilibrii [B] maxb Intervalově lineární aproximace transkripční regulace Booleovské sítě Vývoj v regulatorních doménách maxa 7a [A] —-x—- —-v— 1 1 1 1 (o,o) i Wa ' lb> / (0>t) i i i i (0,0); [B] ib maxb Intervalově lineární aproximace transkripční regulace Booleovské Stavový prostor [A] O ( m > O ( > o O ( r W > O ( V > o maxb Intervalově lineární' aproximace transkripční regulace Booleovské sítě Chováni v regulatorních doménách maxa [A] maxb Intervalově lineární aproximace transkripční regulace Booleovské sítě Přechodové domény • nadroviny dimenze striktně nižší než počet proměnných • alespoň jedna z proměnných přechodová (rovna některému prahu): {ol} x {(o,o\),el {elel),e\, (e\, maxb)} U{(O,0l),(0l,maxa)}x{0l,0l} • celkem 9 přechodových domén • právě všechny úseky nespojitosti (nedefinovanosti) step-funkcí • řád domény - počet regulatorních (nepřechodových) proměnných Intervalově lineární aproximace transkripční regulace Booleovské sítě Aproximace systému (Filippov) aproximace systému rovnic systémem inkluzí [Filippov]: systém tvaru ^ = f(x) aproximujeme systémem inkluzí H(x): f e H(x) (1) • pro lib. reg. doménu D je Vx G D. H{x) = {Íd{x)}, kde Íd{x) je lineární funkce směřující dynamiku do bodu Í>(D) • pro lib. přech. doménu D je: Vx G D. H{x) = co({fo'(x) | D' reg. dom. sousedíc i s D}) co(E) ... konvexní obal množiny bodů E Intervalově lineární aproximace transkripční regulace Booleovské sítě Aproximace systému (Filippov) • aproximace systému rovnic systémem inkluzí [Filippov]: systém tvaru ^ = f(x) aproximujeme systémem inkluzí H(x): f e H(x) (1) • pro lib. reg. doménu D je Vx G D. H(x) = {fo(->?)}, kde Íd{x) je lineární funkce směřující dynamiku do bodu Í>(D) • pro lib. přech. doménu D je: Vx G D. H(x) = co({fo'(x) | D' reg. dom. sousedíc i s D}) co(E) ... konvexní obal množiny bodů E Filippovova věta: Spojitá funkce x(t) je pro iniciální problém x(0) = xo řešením systému (1) na (0,t), t > O, pokud pro skoro všechna t G (O, t) platí G H(x(t)). Intervalově lineární aproximace transkripční regulace Booleovské sítě Chováni v přechodových doménách • pro přechodovou doménu D řádu k vývoj definován množinou cílových ekvilibrií: (D) = C n co({<ř>(D')|| D' sousední reg. dom.}) C ... nadrovina dimenze (n — k) obsahující D • Í>(D) = 0 — okamžitý odskok spojitost řešení zachována návazností domén D tzv. transparentní zeď • í>(D) ^ 0 — mód skluzu D tzv. černá zed (dochází ke zlomu) • pokud navíc Í>(D) n D ^ 0, existuje na D stabilní bod Intervalově lineární aproximace transkripční regulace Booleovské sítě Chováni v přechodových doménách • pro přechodovou doménu D řádu k vývoj definován množinou cílových ekvilibrií: (D) = C n co({<ř>(D')|| D' sousední reg. dom.}) C ... nadrovina dimenze (n — k) obsahující D • Í>(D) = 0 — okamžitý odskok spojitost řešení zachována návazností domén D tzv. transparentní zeď • í>(D) ^ 0 — mód skluzu D tzv. černá zeď (dochází ke zlomu) • pokud navíc Í>(D) n D ^ 0, existuje na D stabilní bod • dále (nad)aproximujeme Q>{D) C ip(D): ip(D) = C n rect^í^D')!! D' sousední reg. dom.}) rect(E) □ co(E) ... nejmenší (hyper)obdélník zahrnující E Intervalově lineární' aproximace transkripční' regulace Booleovské sítě Chováni v přechodových doménách - skluz maxa 7a [A] 1 1 1 1 X | \ Wa ' lb> / < f [B] ib maxb Intervalově lineární' aproximace transkripční' regulace Booleovské sítě Chováni v přechodových doménách - ekvilibrium maxa 7a [A] (0,0) [6] maxb Intervalově lineární aproximace transkripční regulace Booleovské sítě Chováni v přechodových doménách - odskok maxa 7a [A] 1 1 1 1 Wa ' lb> / « [B] ib maxb Intervalově lineární aproximace transkripční regulace Booleovské sítě Konstrukce diskrétní (kvalitativní) simulace Uvažme systém tXl^'x°' = r~((xi, ...,x„)) kde na každé proměnné x,(ř) G M+ je definována množina prahů Tr, = {0j,0j, ...,0f!}, k; > 0, t.ž. 0 < 6} < 9f < ... < Qnt < maxi. Definujeme přechodový systém QS = (S, T, So) kde • S je konečná množina všech domén systému (stav příslušný k doméně D značíme DS) • 7 C S x S je přechodová relace (def. viz dále) • So C S je neprázdná množina iniciálních stavů Intervalově lineární aproximace transkripční regulace Booleovské sítě Konstrukce diskrétní (kvalitativní) simulace Necht D, D' domény a necht w G {—1, 0,1}" vektor určující vzájemnou pozici D a D'. • Pokud D vyššího řádu než D' pak {DS, DS') ÉÍ« 1. V(D)^0 2. Pro každou x,- přechodovou proměnnou v D', přitom regulatorní v D, existují body p G D a p' G ^(C) t.ž. V;', (p' - p),- • w,- > 0. • Pokud D nižšího řádu než D' pak {DS, DS') e7« 1. V(D')^0 2. Pro každou x,- přechodovou proměnnou v D', přitom regulatorní v D, existují body p G D' a p' G 4>{D') t.ž. V;', (p' - p),- • w/ > 0. Intervalově lineární aproximace transkripční regulace Booleovské sítě Přechod z domény nižšího do vyššího řádu maxa 7a [A] —V— (|,0) \ ----i Wa ' lb> / [B] ib maxb Intervalově lineární aproximace transkripční regulace Booleovské sítě Diskrétní (kvalitativní) simulace maxa Intervalově lineární aproximace transkripční regulace Booleovské sítě Vlastnosti kvalitativní simulace Necht Á4 je intervalově lineární model daný systémem rovnic t/(xi^.,x„) _ ff^y pro jniciálnf podmínku x(0) = xo definujeme spojitou sémantiku modelu M, {Mjc : Rq H"=i Ko~' Necht pro každé x; je definována množina prahů Tr, = {O},02, 0-'}, k; > 0, t.ž. O<0j <02 < ... < 61? < max;, 09 = 0 a 0-i+1 = max,. Označme: N, = {{6?, 0?) C R I p, q G N, 0 < p < kh q = p + 1} U {6? | 0 < p < k,}. Necht QS = (S, T, {DSo}) kvalitativní přechodový systém. Pro iniciální doménu Do definujeme diskrétni sémantiku modelu M, iMjd ■ n n"=i n,-, . IMUO) = Do . IMUO = D', kde (DS, DS>) G T, D = {MMi - 1). Intervalově lineární aproximace transkripční regulace Booleovské sítě Vlastnosti kvalitativní simulace Konzervativnost Necht x(0) = xo iniciální podmínka a Do doména t.ž. xb G Do. Pro libovolné r G R+, r > 0 existuje ô G N, ô > 0 a posloupnost stavů ri/LoI-^lUO) (s 'tý"1 členem značeným 7r(/)), tak že platí Vr G <0,t). [M]c(t) e 7r(j) kde j < ô. Neúplnost Existuje simulační posloupnost II/LolI-^lUO)' iniciální podmínka xo G Do a r > 0 pro něž |[.A4]]c(ŕ) není řešením systému pro ŕ e <0,t). Intervalově lineární' aproximace transkripční regulace Booleovské Nástroj GNA (Genetic Network Analyzer) • nástroj Genetic Network Analyzer (GNA) http://www.genostar.com/en/genostar-software/ gnasim.html • umožňuje kvalitativní simulaci kinetiky • využití aproximace pomocí schodových funkcí (represe, aktivace) • prostor řešení lze diskretizovat na konečný počet oblastí, v nichž chování degraduje v lineární rovnice • umožňuje abstrahovat od konkrétních hodnot • místo přesné hodnoty koncentrace rozlišujeme několik diskrétních úrovní • úrovně určeny pozicemi prahových hodnot a pozicemi v rozmezí mezi bezprostředně následujícími prahovými hodnotami schodových funkcí • různá chování pro různé uspořádání prahových hodnot schodových funkcí Intervalově lineární aproximace transkripční regulace Booleovské sítě Simulace v GNA (Model nutričního stresu E. coli) max_Crp— t_Crp_B— CRP t_Op_2-t_Crp_l— z_Crp— n iax_Cya— t_Cya_3-CYA t_Cya_2-t_Cya_l- 1_fí5_4— FIS *-^-3~ 1_Fis_2-T_FÍ5_1-z_FÍ5— 55 57 543 571 569 SE7 565 535 533 534 55 57 543 571 S69 565 S35 S33 534 GYR max_GyrA5-t_GyrAB_2" t_GyrAB_l" z_GyrA3" max_TopA-t_TopA_2" t_TopA_l" zJTopA" ■ís c,7 ^ 71 569 S67 ■iss 5ís ^33 ™ RRN 55 57 543 571 569 S67 565 S35 S33 534 I I—h z_nn S5 S7 S43 571 569 S67 S65 535 533 S 34 max_5ignal— jip T_Signal- z_5ignal 55 57 543 S71 569 S67 565 535 533 534 55 57 543 S71 569 567 565 S35 533 534 Intervalově lineární' aproximace transkripční regulace Booleovské sítě Simulace v GNA - vlastnosti • abstrakce od kvantitativní znalosti kinetiky • ztrácíme informaci o čase • zachováváme však informaci o tranzientnosti všech diskrétních domén Doména D je tranzientní pokud pro libovolný bod v e D existuje trajektorie, která v konečném čase opustí D. • algoritmus kvalitativní simulace GNA nadaproximuje (konzervativnost) znalost o tranzientních stavech Intervalově lineární aproximace transkripční regulace Booleovské sítě Simulace v GNA - neúplnost ■O A. + r 1 %=f3a{l-s+{a,6l)s+{b,6l))-laa ft=l3b(l-s+{a,el)s+{b,el))-lbb rozsah exprese genu a: 0 < 6\ < maxa rozsah exprese genu b: 0 < Q\ < maxb Intervalově lineární aproximace transkripční regulace Booleovské sítě Simulace v GNA - neúplnost A-B I B (D6) e D6 v|/(D6) e |J Di Intervalově lineární' aproximace transkripční' regulace Booleovské sítě Simulace v GNA - neúplnost 9 (D6) e D6 v|/(D6) e |J Di i=l Ha 7b Ol Intervalově lineární' aproximace transkripční regulace Simulace v GNA - neúplnost 9 (D6) G D5 M/(D6) G |J Dj Intervalově lineární' aproximace transkripční regulace Booleovské sítě Simulace v GNA - neúplnost 9 (D6) G D5 v|/(D6) G |J Di i=l Ja_Kb = dl Ha 7b Ol Intervalově lineární' aproximace transkripční regulace Simulace v GNA - neúplnost 9 4>(D6) G D5 v|/(D6) G |J D; i=l 9 (D5) e D5 M/(D5) G |J Di Intervalově lineární' aproximace transkripční' regulace Simulace v GNA - neúplnost ma.Xj, u QS'1 QS1 QS* > • QS" 4>(Dn Ůl maxa 9 4>(D6) G D4 v|/(D6) G |J D, QS1 Intervalově lineární' aproximace transkripční regulace Booleovské sítě Simulace v GNA - neúplnost 9 (D6) G D4 v|/(D6) G |J D,- ;=i k3 7b o\ Intervalově lineární' aproximace transkripční regulace Simulace v GNA - neúplnost max}, I>1 u í(De) o-- » QS1 maxa 4>(D6) G D4 V|/(D6) G |J D; i=l 9 4>(D5) G D4 M/(D5) G |J D,- Intervalově lineární aproximace transkripční regulace Obsah Booleovské Intervalově lineární aproximace transkripční regulace Booleovské sítě Intervalově lineární aproximace transkripční regulace Booleovské sítě Příklad modelu - autoregulace o\ protein A gene a Intervalově lineární aproximace transkripční regulace Booleovské sítě Příklad modelu - autoregulace <=\ protein A gene a 0 12 3 4 • identifikace diskrétních úrovní exprese Intervalově lineární aproximace transkripční regulace Booleovské sítě Příklad modelu - autoregulace protein A gene a 0 12 3 © • spontánní (tzv. bázová) transkripce: A —> 4 Intervalově lineární' aproximace transkripční' regulace Booleovské sítě Příklad modelu - autoregulace -1>( protein A ) __I I_ gene a 0 1 2 • místo projevu regulace (A e {3,4} => regulace aktivní) Intervalově lineární aproximace transkripční regulace Booleovské sítě Příklad modelu - autoregulace -t>( protein A gene a • cílový bod regulace (A e {3,4} => A —> 0) Intervalově lineární' aproximace transkripční regulace Booleovské sítě Stavový prostor - autoregulace • přechodový systém (S, T, So) • S množina stavů, S = {0,1, 2, 3, 4} • Sq 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; [4 4] 2 2 0; [A 4] 3 3 4 4; [4 -»■ 0] 2 4 A 4; [4 -»■ 0] 3 Intervalově lineární aproximace transkripční regulace Booleovské sítě Stavový prostor - autoregulace přechodový systém pro negativní autoregulaci (S, T, So = S) Intervalově lineární aproximace transkripční regulace Booleovské sítě Příklad modelu složené regulace gene a gene b Intervalově lineární aproximace transkripční regulace Booleovské sítě Diskrétní charakteristika dynamiky gene a gene b 0 1 0 12 • identifikace diskrétních úrovní exprese Intervalově lineární aproximace transkripční regulace Booleovské sítě Diskrétní charakteristika dynamiky • spontánní (tzv. bázová) transkripce: A —> 1, B —> 2 Intervalově lineární' aproximace transkripční regulace Booleovské sítě Charakteristika regulace - autoregulace • místo projevu regulace B —> B (B = 2 => regulace aktivní) Intervalově lineární' aproximace transkripční regulace Booleovské sítě Charakteristika regulace - autoregulace Intervalově lineární' aproximace transkripční' regulace Booleovské sítě Charakteristika regulace - vstupní funkce • místo projevu regulace B —> A {B e {1,2} => reg. aktivní) Intervalově lineární' aproximace transkripční regulace Booleovské sítě Charakteristika regulace - vstupní funkce Intervalově lineární aproximace transkripční regulace Booleovské sítě Charakteristika regulace - vstupní funkce • AND-kompozice regulací A —> A A B —> A: A = 1 A B G {1,2} => regulace aktivní Intervalově lineární aproximace transkripční regulace Booleovské sítě Charakteristika regulace - vstupní funkce • cílový bod složené regulace A —> A A B —> A: A = 1 Aß G {1,2} ^4^0 Intervalově lineární aproximace transkripční regulace Booleovské 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 Sn = S • T C S x S přechodová relace (zobrazení): zdrojový stav aktivní regulace cílový stav [0,0] 0; [A -+ 1, B -+ 2] [1,1] [0,1] S _►- A; [A 0, B 2] [0,2] [0,2] [4 0, e 0] [0,1] [1,0] A^- A; [A 0, 6 2] [0,1] [1,1] 4^/lAB^4; [4 0, 6 2] [0,2] [1,2] A A A B A A B B; [A 0, 6 0] [0,1] Intervalově lineární aproximace transkripční regulace Booleovské sítě Stavový prostor - synchronní sémantika přechodový systém (S, T, Sq = S) Y v Intervalově lineární aproximace transkripční regulace Booleovské sítě Stavový prostor - asynchronní sémantika • přechodový systém (S, T, Sq) • S = {0,1} x {0,1, 2} • So C S, uvažujeme Sq = 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] [o, i] S _►- A; [A 0, B 2] [0,2] [0,2] B BhB A; [A 0, B 0] [0,1] [1,0] A A; [A 0, B 2] [0,0], [1,1] [1,1] 4^/lAB^4; [4 0, B 2] [0,1], [1,2] [1,2] /1^-4AB^-4AB^- B; [A 0, 6 0] [0,2], [1,1] Intervalově lineární aproximace transkripční regulace Booleovské sítě Stavový prostor - asynchronní sémantika přechodový systém (S, T, Sq = S) Intervalově lineární aproximace transkripční regulace Booleovské 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 Intervalově lineární aproximace transkripční regulace Booleovské 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 Intervalově lineární' aproximace transkripční regulace Booleovské sítě Literatura [■I de Jong, et. al. Qualitative Simulation of Genetic Regulatory Networks Using Piecewise-Linear Models. INRIA Technical Report RR-4407, 2002. 2 Brim, et.al. On Algorithmic Analysis of Transcriptional Regulation by LTL Model Checking, Theoretical Computer Science, in press, 2009. Q Alon, U. An Introduction to Systems Biology: Design Principles of Biological Circuits. Chapman & Hall, 2006. 9 Bower, J.M. & Bolouri, H. Computational Modeling of Genetic and Biochemical Networks. Bradford Book, 2001.