1 Komputerowa analiza sieci genowych (GRN)Agnieszka Marmołowska Jacek Ławrynowicz Promotor: prof. Krzysztof Giaro

2 Przypomnienie Gene regulatory network – sieć genów komórki, które wpływają na siebie

3

4 Selektywność (assortativity)Parametr określający, czy wierzchołki o wysokich stopniach „lubią” łączyć się z ze sobą Różne wzory Różny zakres wartości

5 Selektywność IlustracjaBrak korelacji A = 0 A = 0.26 A = 0.43 Maksymalna (dla sieci o takim rozkładzie stopni) korelacja A = 0.62

6 Selektywność Neighbour connectivityWzór funkcji Funkcja rosnąca – assortative network Funkcja malejąca – disassortative network

7 Neighbour connectivity PrzykładAssortative

8 Neighbour connectivity PrzykładSteel assortative

9 Neighbour connectivity PrzykładDisassortative

10 Współczynnik selektywności Pearson correlation coefficientWzór Sumy po wszystkich krawędziach ji i ki – stopnie wierzchołków, które łączy i-ta krawędź r jest znormalizowane

11 Współczynnik selektywności Przykład

12 Współczynnik selektywności Przykład

13 Współczynnik selektywności Sieci z życiaSieci społeczne – assortative Sieci techniczne/biologiczne – disassortative Dlaczego tak jest?

14 Współczynnik klasteryzacjiWzór u – wierzchołek k – stopień wierzchołka u e – ilość krawędzi łączących k sąsiadów u C – średni współczynnik klasteryzacji dla wszystkich wierzchołków C(k) – średni współczynnik klasteryzacji dla wierzchołków o stopniu k

15 Współczynnik klasteryzacjiZbadano: Sieci metabolicznych 43 organizmów Sieci interakcji białek (S. cerevisiae, H. pylori, E. coli, C. elegans) Regulacyjnych sieci genowych (S. Cerevisiae) C(k)~k-1 Wnioski: Pojedyncze moduły składają się z gęsto zgrupowanych wierzchołków o relatywnie niskim stopniu Moduły są połączone przez centralne wierzchołki o wysokim stopniu

16 Współczynnik klasteryzacji Wyewoluowana siećn = 14, m = 128 C = 0,335 C(k)~k-1?

17 Współczynnik klasteryzacji Wyewoluowana siećn = 48, m = 1028 C = 0,327 C(k)~k-1?

18 Współczynnik klasteryzacji Dlaczego?Sieć jest grafem: skierowanym dopuszcza krawędzie wielokrotne

19 Struktruty społeczne Występowanie grup wierzchołków gęściej połączonych między sobą niż z wierzchołkami spoza grupy. Wiele algorytmów znajdowania modułów.

20 Algorytmy wykrywania modułówKlasteryzacja hierarchiczna Algorytm Girvan–Newman Maksymalizacja Modularity Filtracja klik (Clique percolation) Minimalne rozdzięcie

21 Klasteryzacja hierarchicznaDwa rodzaje: Agglomerative – bottom-up, każdy wierzchołek w oddzielnym klastrze Divisive – top-down, wszystkie wierzchołki w jednym klastrz Zarys algorytmu: Każdej krawędzi przypisywana jest waga (edge betweeness centrality ) Wierzchołki są łączone według malejącej wagi (rozdzielane według malejącej wagi) Złożoność O(mn + m) = O(mn)

22 Girvan–Newman Krawędzie są usuwane, tworząc klastry Zarys algorytmu:Każdej krawędzi przypisywana jest waga (edge betweeness) Usuwana jest krawędź o najwyższej wadze Wagi przeliczane są na nowo Złożoność O(nm2)

23 Maksymalizacja ModularityPrzeszukiwanie możliwych podziałów na klastry i wybór najlepszego Miara dobroci podziału (modularity) eij – ilość krawędzi między i-tym i j-tym klastrem Przeszukanie wszystkich możliwości – bardzo nieoptymalne

24 Maksymalizacja ModularityZarys algorytmu zachłannego: Każdy wierzchołek jest w oddzielnym klastrze, tworzona jest macierz E Krok algorytmu: Obliczenie dla każdej krawędzi - O(m) Wybór krawędzi o największym Poprawienie macierzy E – O(n) Złożoność O((m+n)n)