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