Objevování skupin (class discovery) Výuka IBA Společná schéma analýzy dat Biologická otázka (hypotéza) N matic základních dat (jedna pro každý z N vzorků) Kontrola kvality Normalizace Sumarizace Provedení experimentu (hybridizace mikročipů, hmotnostní spektrometrie...) Design experimentu Objevování skupin? (Shlukování) Porovnání skupin? (Testování) Predikce skupin? (Klasifikace) Analýza přežití Analýza časových řad Charakterizace nových skupin List genů se stejným profilem změn exprese v čase Interpretace Validace Publikace Matice informací o vzorcích N x P (např. klinická data v medicíně) Finální datová matice N vzorků a K genů (proteinů) Nové skupiny genů nebo vzorků List genů s odlišnou expresí mezi skupinami vzorků Klasifikační pravidlo využívající genovou expresi Seznam prognostických genů Tradiční schéma analýzy • Učení s učitelem (supervised learning) • V tomto případě zobecňujeme známou strukturu dat na nové data • Porovnávání skupin (class comparison) • hledáme rozdíly v expresi, počtu kopií genů nebo abundanci proteinů mezi již definovanými skupinami • Předpovídání skupin (class prediction) • na známých skupinách se snažíme vytvořit klasifikátor, který by dokázal zařadit nového pacienta do jedné ze skupin • Učení bez učitele (unsupervised learning) • V tomto případe struktura v datech není známá a musíme ji objevit • Objevování skupin (class discovery) • na základě informací o genech/proteinech hledáme nové skupiny • onemocnění X je velmi heterogenní a snažíme se identifikovat specifičtější podtypy, které by mohli být cílem cílené terapie Společné znaky analýzy dat • Velké množství proměnných • Malé množství vzorek • Proměnné jsou často korelované, s velmi komplexními vztahy • Data obsahují množství šumu – biologická i technická variabilita Objevování skupin • Snažíme se vytvořit závěry o datovém souboru bez (braní do úvahy) jakékoliv předchozí znalostí biologických skupin (=shlukování) • Cílem je vytvořit skupiny objektů na základě jejich vzájemné podobnosti • Objekty uvnitř skupiny mají být co nejpodobnější a objekty z různých skupin mají být tak odlišné, jak jen je to možné • Skupina metod pro objevování skupin je představovaná metodami shlukování bez učitele Co shlukujeme v molekulární biologii • Geny/proteiny • Chceme identifikovat skupiny ko-regulovaných genů/proteinů • Chceme zredukovat dimenzi dat na základě funkčních genových/proteinových skupin • Vzorky • Kontrolujeme kvalitu vzorků • Chceme najít nové skupiny vzorků (například podtypy) • Chceme zkontrolovat diskriminační schopnost genů vybraných při porovnávání známých skupin do vzorek Princip • Máme datovu matici X velikosti N x P • N – počet objektů (vzorek) • P – počet proměnných (geny/proteiny) • Hledáme nejlepší rozdělení dat na skupiny tak, aby nalezené skupiny byly uvnitř skupiny vysoce homogenní a mezi sebou vysoce heterogenní N vzorek P proměnných (geny, proteiny) Typy shlukovacích metod • Shlukovací metody se dělí na dvě hlavní skupiny: 1. Metody založené na vzdálenostech • neparametrické • nejčastěji používané, intuitivní • hierarchické a nehierarchické shlukování 2. Metody založené na modelování • parametrické, kladou silné předpoklady na rozložení dat • založeny na statistickém modelování – přiřazují každému objektu pravděpodobnost s jakou patří do daného shluku Metody založené na vzdálenostech I. • Princip: 1. Vypočítáme matici vzdáleností mezi objekty 2. Vybereme shlukovací algoritmus 3. Stanovíme počet shluků – jen u některých metod 4. Aplikujeme shlukovací algoritmus na matici vzdálenosti získáme shluky • Shlukovací algoritmy: • Hierarchické • Aglomerativní – Single, Complete, Average, Ward linkage, … • Divizní - DIANA • Nehierarchické • K-means • PAM Metriky vzdáleností I. Máme 2 vektory hodnot x = (x1, …, xn), y = (y1, …, yn) • Euklideovská vzdálenost: • Standardizovaná Euklideovská vzdálenost: Metrika penalizuje – snižuje vzdálenost mezi objekty s velkou variabilitou, předpokládajíc, že jsou důležitější než objekty s malou variabilitou. • Manhattanovská vzdálenost: Robustnější vůči odlehlým hodnotám. å - n =i iiE )y(x=y)(x,d 1 2 | |. 1 å - n =i iiM yx=y)(x,d ( ) å - n =i iiiE σ)y(x=yx,d 1 2 2 / Metriky vzdáleností II. • Metriky založené na korelačním koeficientu r(x,y) • Můžeme odvodit dvě různé metriky: • Ukázka rozdílu mezi metrikama d2( x,y)= 1− [r( x,y )]2 d1(x,y)= [1− r(x,y)]/2 d1=0.05, d2=0.19 d1=0.5, d2=1 d1=0.95, d2=0.19 Pří použití d1 budou geny s opačnými profily patřit do odlišných shluků, zatímco při použití metriky d2 budou patřit do toho stejného shluku. Pokud chceme shluky interpretovat jako množiny genů ze stejné regulační sítě, použijeme raději d2. Výběr metriky • Výběr metriky záleží na tom, jaký typ podobnosti nás zajímá • Pokud nás zajímá průměrná exprese genů (A a B jsou podobné), aplikujeme Euklidovskou vzdálenost • Pokud nás zajímá vzor exprese genů (A a C jsou podobné), aplikujeme vzdálenost založenou na korelaci A B C Gene ID Log2Ratio 0 3 2 1 4 Na co si dávat pozor I. • Mnoho shlukovacích technik najde shluky i v datech, ve kterých nejsou žádné přirozené shluky, jen proto, že byly pro tento účel zkonstruované 728197631140 35596624693082625875875903741 7732789173465395105135734315 238654392949196265211338601488 276807410082641722283129852 728619495067897944784769244 20455655719942931487016438536 1533189668 3663842582 549253524858774966840100975761 10869160322099791642681237648 9437735649756990725211776758 917708334182833314558819650 29317127162413551956544464798 239894543893781580133071266 425922643821 Na co si dávat pozor II. • Výsledek jediného shlukování by nikdy neměl být považovaný za objektivní reprezentaci informace skryté v datech, protože je závislý od použité metody a také v rámci metody od nastavení! Další problémy • Výběr shlukovacího algoritmu a metriky ovlivňuje konečné výsledky • Výsledky jsou závislé na samotných datech • Kolik shluků? • Potřebujeme odhad jistoty, že nalezené shluky jsou správné • Odhad kvality shluků je založen na metrikách z dat z kterých byli shluky vytvořené Kolik shluků? • V případě nehierarchických metod počet shluků určujeme dopředu • V případě hierarchického shlukování vytváříme strom, dendrogram, který se potom prořezává • Počet shluků je následně určený tak, aby heterogenita v rámci shluků byla co nejmenší a mezi shluky co největší • Různé metriky heterogenity shluků – variabilita, Silhouette, ... Řezání dendrogamu jeho problém • U hiararchického shlukování se stanovuje fixní výška řezu dendrogramu >cutree() • Problém: u genomických dat se často vyskytují shluky v různých výškách řezu AML AML AML AML AML AML AML AML AML AML AML ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_T-cell ALL_T-cell ALL_T-cell ALL_T-cell ALL_T-cell ALL_T-cell ALL_B-cell ALL_T-cell ALL_T-cell 0.20.40.60.81.01.2 Cluster Dendrogram hclust (*, "complete") as.dist(1 - cor(d)) Height static cutreeHybrid_5 cutreeHybrid_3 Dynamic tree cut • Metoda prořezávání dendrogramu (Langfelder et al, 2007) • Dynamické řezání dendrogramu na základě minimální velikosti shluků, maximální výšky řezu a dalších parametrů >library(dynamicTreeCut) AML AML AML AML AML AML AML AML AML AML AML ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_B-cell ALL_T-cell ALL_T-cell ALL_T-cell ALL_T-cell ALL_T-cell ALL_T-cell ALL_B-cell ALL_T-cell ALL_T-cell 0.20.40.60.81.01.2 Cluster Dendrogram hclust (*, "complete") as.dist(1 - cor(d)) Height static cutreeHybrid_5 cutreeHybrid_3 Robustní shlukování • V analýze vysokopokryvných molekulárních dat mají výše uvedené problémy větší váhu • Malý počet vzorek a vysoký počet genů/proteinů spolu s vyšším množstvím šumu v datech jsou důvodem, proč je shlukování těchto dat citlivé na přeučení (overfitting) • Shlukování je méně robustní (více ovlivněné variabilitou dat) • Variabilita dat a výsledky shlukování se dají simulovat opakovaným náhodným výběrem z dat Consensus clustering • Forma robustního shlukování (Monti et al., 2003) • Opakované vzorkování a shlukování jako způsob nalezení konsenzusu mezi jednotlivýma výsledkama shlukování za účelem: • Určení počtu a stability shluků v datech • Vytvoření nové metriky vzdálenosti - konsenzusu • Základní princip: 1. Rozrušení struktůry originální N x P datové matice pomocí náhodného výběru podmnožiny vzorků a/nebo genů 2. Na novém datovém souboru aplikujeme shlukovací algoritmus se stejnou mírou similarity a počtem shluků Oba body jsou opakované L krát pro jiný počet shluků. Consensus clustering II å å = = = L l l ij L l l ij ij I C M 1 )( 1 )( Consensus clustering III – myšlenka • Pokud se dva vzorky v jednotlivých výběrech nacházejí často spolu ve shluku, jsou důvěryhodnějšími členy shluku než ty, které se ve shluku nacházejí méně často Data bez struktury (náhodný výběr z normálního rozložení) Data se třemi skupinami A. B. Consensus clustering IV – další metriky Konsenzus shluku k Konsenzus vzorku si v shluku k •Obě míry se používají pro identifikaci odlehlých hodnot (vzorky s nízkou mírou konsenzusu k jakémukoliv jinému vzorku v jinak homogenním shluku; shluky s nízkou mírou konsenzusu všeobecně) å < Î- = ji Iji ij ll k k M NN m ,2/)1( 1 { }å ¹ ÎÎ- = ij Ij ij kil k i l M IsN m 1 1 kde je indikátorová funkcia{ }ki Is Î1 Consensus clustering V - výběr počtu shluků I { } 2/)1( 1 - £ = å< NN xM CDF ji ij x golub data, k=3 Consensus measure Frequency 0.0 0.2 0.4 0.6 0.8 1.0 0204060 golub data, k=6 Consensus measure Frequency 0.0 0.2 0.4 0.6 0.8 1.0 050100150 Empirická kumulativní distribuční funkce (pravděpodobnost, že proměnná Mij nabyde hodnoty menší anebo rovné jako x) 6 shluků má podstatně míň vzorků s konsenzusem 1 a tím pádem jsou tyto shluky míň důvěryhodné Struktura s 3 shluky naopak vypadá jako optimum Jako rozhodovací pravidlo – rozdíl v plochách pod CDF křivkami Consensus clustering V - výběr počtu shluků II { } 2/)1( 1 - £ = å< NN xM CDF ji ij x Optimální počet shluků je určený vypočtením ploch pod CDF křivkami jednotlivých počtů shluků a porovnáním relativní změny mezi různým shlukováním (plocha delta). 3 shluky Consensus clustering VI – R balík > source(“http://bioconductor.org/biocLite.R”) > biocLite(“ConsensusClusterPlus”) Metody založené na modelech • Modely Gaussových směsí (mixture models) • Předpokládají, že naměřené hodnoty genu/proteinu g ve všech vzorkách (Xg) jsou náhodným výběrem a jejich rozložení závisí na skupině do které gen g patří • Náhodnost Xg souvisí s pozorovanou variabilitou v datech z genomických a proteomických experimentů • Na rozdíl od metod založených na vzdálenosti poskytují tyto modely: • odhad parametrů, které charakterizují každou skupinu (průměr, rozptyl, …) • pravděpodobnost příslušnosti genu ke každé ze skupin • statistické kritéria pro výběr počtu skupin Modely Gaussových směsí 1=πkå Pokud objekt patří do více skupin shluků • Většina shlukovačích technik vytváří disjunktní shluky: každý objekt je součástí jediného shluku • Toto zvlášť v genomice a proteomice nemusí být nejlepší přístup, protože většina proteinů/genů je součástí více biologických drah -> proto by měli patřit do více skupin • Jak zohlednit tuto informaci: • Aplikujeme speciální shlukovací metody (například fuzzy clustering) • Aplikujeme metody založené na modelech a vyvodíme závěry z přiřazených pravděpodobností • Biclustering (two-way clustering) shlukuje zaráz řádky i sloupce Jak shlukovat efektivně • V genomice a proteomice obvykle nemá význam shlukovat úplně všechny objekty (proteiny/geny) • Většina z nich není významná • Vnášejí do procesu šum, který zakryje pravou strukturu dat • Je vhodné zredukovat dimenzi dat: • PCA, gene-shaving, … - dokáží extrahovat informaci o genech/proteinech s podobnými charakteristikami, stačí potom ve shlukování reprezentovat charakteristikami těchto skupin • Redukce na základě SD anebo CV Kde hledat shluky I. • Data můžou vytvářet shluky v odlišných dimenzích from Giovanni Montana's presentation Kde hledat shluky II. • V případě, že předpokládáme shlukování v nižších dimenzích, můžeme: • Hledat v nižších dimenzích vytvořených PCA • Použijeme podprostorové shlukovací algoritmy, které jsou schopné detekovat shluky, které existují ve více podprostorech a mohou se překrývat Podprostorové shlukovaní • Hledá shluky ve všech podprostorech • Počet podprostorů je 2d, kde d je počet dimenzí (počet genů/proteinů) • Typy algoritmů: • Top-down – najde iniciální rozložení na všech dimenzích a potom se dívá na podprostory každého shluku, iterativně zlepšují výsledky • Bottom-up – najdou regiony v nižších dimenzích a potom je zkombinují a vytvoří shluky • MAFIA (Nagesh, 1999) • ENCLUS (Chen, 1999) • COSA (Damian et al., 2007) • SMART (Jing et al., 2009) > library(orclus) Vizualizace výsledků • Správná vizualizace výsledků je nejdůležitější součást analýzy! Boxploty exprese genůVizualizace korelací mezi vzorky Alizadeh et al., Nature 403:503-11, 2000 Shrnutí • Více metod v rámci jedné studie • Konsenzuální shlukování • Dynamické řezání stromu • Vizualizace výsledků • Propojení výsledků s biologickými či klinickými proměnnými • Validace výsledků na testovém souboru!