1 Modelowanie zależności ekspresji genówSieci Bayesa Paweł Szlendak Promotor: dr inż. Robert Nowak

2 O co chodzi? INPUT: zestaw danychAtrybut A Atrybut … Atrybut X 12.4 ‘istnieje’ 23.6 1 ‘nie istnieje’ OUTPUT: zależności przyczynowo-skutkowe atrybutów A C D B X …

3 Przykład - Dane Występy w poprzednich turniejachDrużyna M Z F L T Drużyna 1 1 Drużyna 2 Drużyna 3 … M – byli już mistrzami Z – są zmęczeni sezonem F – są w formie L – mają łatwą grupę T – mają dobrą technikę

4 Przykład – Graf zależności IBUDOWA STRUKTURY Z F L M M – byli już mistrzami Z – są zmęczeni sezonem F – są w formie L – mają łatwą grupę T – grają technicznie T

5 Przykład – Graf zależności IIUCZENIE PARAMETRÓW P(z1) = 0.6 Z P(f1|z1) = 0.05 P(f1|z0) =0.3 F P(m1|f1, l1) = 0.2 P(m1|f1, l0) = 0.1 P(m1|f0, l1) = 0.02 P(m1|f0, l0) = 0.01 L P(l1) = 0.2 M INTERFERENCJA P(m1|l1, f1, z0) = ? P(t1|m1) = 0.7 P(t1|m0) = 0.4 T

6 Przykład – Graf zależności IIIJakie jest prawdopodobieństwo, że Polska zdobędzie mistrzostwo, wiedząc że mamy łatwą grupę a zawodnicy są w formie i nie są zmęczeni?

7 Warunek Markova Z F L M T 20% szans, że Polacy zdobędą mistrzostwo

8 Sieć Bayesa - DefinicjaSieć Bayesa to para (G, P) spełniająca warunek Markova, gdzie P to łączny rozkład prawdopodobieństwa zmiennych losowych ze zbioru V, a G = (V, E) to DAG.

9 Sieci Bayesa – Data miningUczenie sieci Bayesa Budowa grafu Z wiedzy eksperta Z danych Uczenie się parametrów Interferencja

10 Budowa grafu z danych Problem optymalizacji kombinatorycznejSearch zbiór grafów DAG Score Na przykład: |G3| = 25 |G5| = 29000 |G10| = 4.2 x 1018

11 Algorytmy budowy grafuAlgorytm ‘k2’ Gdy znamy potencjalnych kandydatów na rodziców dla danego węzła Algorytm ‘dag search’ Każdy węzeł może być rodzicem danego węzła

12 Algorytm k2 void k2(int k, int n, data d, Pred(Xi), ParentSet& PAi ) {for(i=1; i <= n; i++) { PAi= Ø; P = score(d, Xi, PAi); findmore = true; //są nieprzejrzane węzły w Pred(Xi) while (findmore && |PAi| < k) { Z = node in Pred(Xi) – PAi that maximizes score(d, Xi, PAi u {Z}); Pnew = score(d, Xi, PAi u {Z}); if (Pnew > Pold) { Pold = Pnew; PAi = PAi u {Z}; } else findmore = false;

13 Przykład Kolejność : Z, F, L, M, T Graf: Score = 5

14 Algorytm dag search void dag_search (data d, EdgeSet& E) { E = Ø; G = (V, E); do if (any DAG in the neighborhood of current DAG increases score(d, G)) modify E according to the one that increases score(d, G) the most; while (some operation increases score(d, G)); } Grafy w sąsiedztwie grafu G: grafy otrzymane przez operacje dodaj krawędź, usuń krawędź, zmień kierunek krawędzi na grafie G

15 Sieci Bayesa w bioinformatyceZastosowanie sieci Bayesa do modelowania ekspresji (aktywności) genów Technologia microarray DNA

16 Technologia mikromacierzy DNA

17 Dane z mikromacierzy N << M ‘Ciągłe’ wartości ekspresji genówBadany Gen 1 … Gen M 1 12.3 45.6 N 18.3 23.9 N << M ‘Ciągłe’ wartości ekspresji genów

18 Szukanie wzorców ekspresjiRelacje Markova Kilka podobnie ocenionych sieci, szukamy stałych Markov blankets Relacje kolejności Kilka najwyżej ocenionych sieci, sprawdzamy czy X jest rodzicem Y we wszystkich sieciach

19 Jak łatwo zbudować sieć?Dla każdej pary atrybutów X, Y policzyć: Obliczyć maksymalne drzewo rozpinające na grafie pełnym z powyższymi wagami krawędzi (np. Boost Graph Library) Ukierunkować krawędzie wedle uznania

20 Sieci Bayesa – Pytania?