UNIVERSITA’ DI MILANO-BICOCCAUNIVERSITA’ DI MILANO-BICOCCALAUREA MAGISTRALE IN LAUREA MAGISTRALE IN

BIOINFORMATICABIOINFORMATICA

Corso di

BIOINFORMATICA: TECNICHE DI BASE

Prof. Giancarlo Mauri

Lezione 13

Clustering di dati da microarrays

2

Introduzione

La tecnologia dei DNA microarrays

Algoritmi di Clustering

algoritmi gerarchici

metodo del centroide

K-Means

Metodi evoluti (CLICK)

Sommario

3

Cosa si intende per clustering

Il clustering è un procedimento che si pone come obiettivo la suddivisione di un insieme di elementi in sottoinsiemi

Gli elementi di ogni sottoinsieme sono accomunati da caratteristiche simili

4

Dati necessari per il clustering

Insieme di elementi da classificare

Ogni elemento è specificato da un vettore caratteristico

Misura di similarità (o dissimilarità) tra gli elementi

Criteri da rispettare:

OMOGENEITA’: elementi dello stesso cluster hanno alto livello di similarità

SEPARAZIONE: elementi di cluster diversi hanno basso livello di similarità

5

Cenni matematici (1)

Sia N = {e1, …, en} un insieme di n elementi, e sia C = {C1, …, Cn} una partizione di N in sottoinsiemi. Ogni sottoinsieme è chiamato cluster e C è detto clustering di N

Due elementi e1 e e2 sono chiamati mates rispetto a C se sono membri dello stesso cluster in C

6

Il clustering in biologia

Elementi geni

Vettore caratteristico vettore con i livelli di espressione di ogni gene, sotto le diverse condizioni

Misura di similarità distanza tra vettori

( ) ( )

( )

( )k

i

k

ii

iii

iii

yxd

yxd

yxd

1

2

1

2

, Minkowski di Distanza

, Manhattan di Distanza

, euclidea Distanza

⎥⎦

⎤⎢⎣

⎡−=

−=

⎥⎦

⎤⎢⎣

⎡−=

∑

∑

∑

yx

yx

yx

7

Uno dei principali meccanismi di regolazione cellulare è il controllo dell’espressione genica che permette alla cellula di coordinare operazioni complesse adattando la concentrazione di proteine alle variazioni dell’ambiente

E’ possibile identificare gruppi di geni coinvolti in un particolare evento (es. shock termico) sperimentalmente (es. riscaldando la colonia cellulare).

Vengono misurati i livelli di mRNA di ogni gene nelle ore successive. Confrontando i dati con i livelli di mRNA tipici di ogni gene, è possibile individuare geni sovra o sottoespressi.

Espressione genica

8

Espressione genica

Tecniche principali per la generazione di livelli di espressione: Microarray cDNA

Microarray oligonucleotidici

Fingerprint oligonucletidici

Si basano tutte su un alto numero di esperimenti

Differiscono: per natura indagini e obiettivi

per le tecnologie usate

9

Microarray cDNA

Un insieme di probe univoci (sequenze di DNA a elica singola) vengono immobilizzati su una superificie solida (vetro, nylon, etc.)

L’mRNA estratto da campioni cellulari viene trattato in modo da generare un campione di cDNA etichettato con una particolare tintura (fluorescente o radioattiva)

Il campione viene poi incubato con l’array così che ogni probe ibridizza con la molecola di cDNA campione complementare (se presente)

Esperimenti con mRNA da diversi campioni possono essere realizzati contemporaneamente, usando tinture diverse o diversi array. I risultati vengono poi confrontati per dare una stima qualitativa dell’abbondanza relativa dell’mRNA nella popolazione cellulare in esame

10

+Array con probes immobilizzati

Soluzione di bersaglie da campione 1 e 2,etichettati con tintura 1 e 2 rispettivamente

1

2 2

2

1

1

1

2

21

2

Array con molecole etichettate di bersagliibridizzate con i probes

Microarray cDNA

11

L’ibridizzazione non dà una misura quantitativa dell’espressione genica: l’efficienza nell’estrazione di DNA, la sintesi del campione, l’etichettatura del campione e le reazioni di ibridizzazione variano da campione a campione e tra un gene e l’altro. Si può avere solo una stima relativa del tasso di cambiamento della concentrazione di mRNA tra due campioni

Matrice dell’Espressione Genica

Microarray cDNA

12

Microarray cDNA

13

Algoritmi di clustering - Classificazione

Organizzazione dei cluster GERARCHICI

NON GERARCHICI

Uso di informazioni note, per guidare l’algoritmo SUPERVISIONATI

NON SUPERVISIONATI

Costruzione della soluzione di clustering AGGLOMERATIVI (si parte dal singolo gene)

DIVISIVI (si parte dalla totalità dei geni)

14

Clustering Gerarchico

Questo approccio prova a collocare gli elementi in input in una struttura gerarchica ad albero, in cui le distanze all’interno dell’albero riflettono le similarità degli elementi. Gli elementi sono localizzati sulle foglie dell’albero

Vantaggi:

Una figura singola, coerente e globale

Intuitivo per i biologi

Svantaggi:

Non ci sono esplicite partizioni nel cluster

Anche per un biologo esperto potrebbe risultare impossibile fare intuizioni semplicemente guardando il grafo ad albero, a causa della dimensione dei dati, e del numero di errori

15

Radicato

Non radicato

Viene impiegata una struttura ad albero

Una particolare rappresentazione è il dendrogramma

Clustering Gerarchico

16

L’algoritmo di clustering gerarchico fonde cluster simili, e calcola la nuova distanza per i cluster fusi.

Se i è clusterizzato con j ed entrambi non sono simili ad r allora D(i,r)=D(j,r) anche se D(i,j)>0. (ricordiamo che D(n,m) è la funzione distanza)

Clustering Gerarchico

17

Algoritmi presentati

Clustering gerarchico

Neighbor joining

Metodo del centroide

Clustering non gerarchico

K-means

Basati sulla teoria dei grafi:

Highly Connected Subgraph (HCS)

CLustering Identification via Connectivity Kernels (CLICK)

Euristica per un algoritmo polinomiale:

Clustering Affinity Search Technique (CAST)

Self-Organizing Maps (SOM)

18

Clustering gerarchico

Può essere supervisionato; è agglomerativo e gerarchico

Le soluzioni individuate vengono tipicamente rappresentate con un dendogramma

Si procede da una partizione iniziale in cluster singoli ad un merging dei cluster fino a che tutti gli elementi appartengono allo stesso cluster

Ogni passo di merge corrisponde all’unione di due cluster

19

1. Input: la matrice delle distanze Dij

2. Trovare gli elementi r,s tali che: Drs = minij(Dij)

3. Fondere i cluster r,s

4. Eliminare gli elementi r,s, e aggiungere un nuovo elemento t con:

5. Ripetere, finché non rimane un solo elemento.

2rsisir

tiit

DDDDD

−+==

Neighbor Joining Algorithm

20

Metodo del Centroide

Si tratta di un metodo gerarchico aggregativo nel quale la misura di vicinanza tra due cluster viene valutata sulla base della distanza dei relativi centroidi

Il centroide di un cluster è il vettore la cui j-esima coordinata è la media aritmetica delle j-esime variabili di tutti gli elementi del cluster in questione

21

Si supponga di avere la matrice X di 5 elementi di dimensione 3:

0 2 5 x1

2 4 0 x2

X = 1 1 4 x3

0 0 2 x4

5 11 0 x5

Presi i cluster A = {x1, x2} e B = {x3, x4, x5}, i loro centroidi

sono rispettivamente c(A) = (1, 3, 2.5) e c(B) = (2, 4, 2) e la loro distanza (Manhattan) è d(A,B) = |1-2|+|3-4|+|2.5-2| = 2.5

Esempio

22

Metodo del Centroide

23

Quindi: inizialmente ogni gene rappresenta un cluster contenente solo sé stesso. Si cercano i 2 cluster r e s con la minima distanza tra loro in modo da fonderli insieme. r viene rimpiazzato con il nuovo cluster mentre s viene eliminato. Le distanze che sono state interessate dalla fusione vengono ricalcolate con la formula mostrata.Si ripetono le fasi 2, 3 e 4 finché il numero totale dei cluster non diviene 1, cioè finché non sono stati presi in considerazione tutti i geni.

Vediamo ora un semplicissimo esempio di esecuzione dell’algoritmo, partendo dalla seguente matrice delle distanze:

Neighbor Joining Algorithm

24

Alla 1° iterazione 2)2,1( ==distDrs per cui si devono fondere i cluster 1 e 2:

Alla 2° iterazione 2)2,1( ==distDrs per cui si devono fondere i cluster 3 e 4:

Alla 3° iterazione fondiamo i due cluster così ottenuti e otteniamo per cuiuna matrice con un unico elemento. L’esecuzione quindi termina.

Neighbor Joining Algorithm

25

Vediamo come avviene la generazione dell’albero (ricordando che i pesi degli archi sono determinati tramite ):2rsD

Neighbor Joining Algorithm

26

Clustering gerarchico (3)

Varianti:

si basano sul differente Linkage Method usato. Questo metodo è quello utilizzato per calcolare le distanze tra due cluster quando si costruisce il dendrogramma

Single Linkage: le distanze sono misurate da ogni membro di un cluster ad ogni membro dell’altro cluster. Si considera come distanza tra i cluster quella minima

Average Linkage: la misura della distanza tra due cluster è calcolata come media della distanza di ogni membro del cluster da ogni membro dell’altro

Complete Linkage: le distanze sono misurate da ogni membro di un cluster ad ogni membro dell’altro cluster. Si considera come distanza tra i cluster quella massima

27

L’Average Linkage è una variante del Neighbor Joining algorithm. L’idea è la stessa ma nel momento in cui calcoliamo le nuove distanze dei cluster creati, vengono prese in considerazione le dimensioni dei cluster che sono stati fusi insieme.

1. Input: La matrice distanza Dij, dimensione del cluster iniziale nr

2. iterazione k: come nel Neighbor Joining algorithm con la differenza che la distanza da un nuovo elemento t è definita attraverso:

issr

sir

sr

rtiit D

nn

nD

nn

nDD ⋅

++⋅

+==

La misura della distanza tra due cluster è considerata la media della distanza di ogni membro del cluster da ogni membro dell’altro

Average Linkage

28

Esistono 2 metodi alternativi:

Single Linkage Complete Linkage

Average Linkage

29

Data la seguente matrice delle distanze vediamo un esempio pratico di tutti e tre i metodi sopra citati:

Average Linkage

30

Il seguente è il dendrogramma relativo al Single Linkage dell’esempio riportato sopra. Gli altri due sono differenti ma si ricavano esattamente nello stesso modo.

Average Linkage

31

Riportiamo la struttura generale del clustering gerarchico:

isirissirrtiit DDDDDD −++== γαα

Nell’algoritmo dell’Average Linkage avremo che i parametri assumeranno i seguenti valori:

sr

ss

sr

rr

nn

n

nn

n

+=

+=

=

α

α

γ 0

Una struttura generale

32

Metodi non gerarchici

I metodi non gerarchici mirano a ripartire le n unità della popolazione in k gruppi, fornendo una sola partizione anziché una successione di partizioni tipica dei metodi gerarchici

Es.: metodo di Forgy o delle K-Medie o delle aggregazioni dinamiche

33

K-means (1)

È divisivo e generalmente non supervisionato

La soluzione non è visualizzabile attraverso dendogrammi

L’algoritmo K-means assume che il numero k di cluster sia noto

Si propone di minimizzare le distanze tra elementi e i centroidi dei cluster loro assegnati

34

K-means (2)

Algoritmo

1. Si inizia fissando k centroidi iniziali di altrettanti cluster

2. Per ogni gene si calcola la distanza da ciascun centroide e lo si assegna al più vicino

3. Per la partizione provvisoria così ottenuta si ricalcolano i centroidi di ogni cluster (media aritmetica)

4. Per ogni gene si ricalcola la distanza dai centroidi e si effettuano gli eventuali spostamenti tra cluster

5. Si ripetono le operazioni 3 e 4 finché si raggiunge il numero massimo di iterazioni impostate o non si verificano altri spostamenti

35

HCS e CLICK

I dati di input vengono rappresentati come un grafo di similarità

OBIETTIVO: costruzione dei kernel

L’algoritmo partiziona ricorsivamente l’insieme corrente di elementi in due sottoinsiemi

Prima di una partizione, si considera il sottografo indotto dal corrente sottoinsieme di elementi

Se il sottografo soddisfa un criterio di arresto allora viene dichiarato un kernel

Altrimenti viene eseguito un taglio minimo pesato su quel sottografo e l’insieme viene diviso in due sottoinsiemi separati dal taglio, su cui verrà ripetuta la procedura di costruzione dei kernel

L’output è una lista di kernel che serve come base per gli eventuali cluster

36

HCS (1)

Costruisce un grafo di similarità non pesato (gli archi in realtà hanno peso 1 o 0) in cui esiste un arco tra due vertici sse la similarità tra i loro corrispondenti elementi supera una soglia predefinita

Un HCS è un sottografo indotto H di G il cui valore di taglio minimo eccede |V(H)|/2

L’algoritmo identifica gli HCS come kernel

Possiede due buone proprietà per il clustering:

il diametro di ogni cluster che produce è al massimo due

ogni cluster è denso almeno la metà di una cricca

37

HCS (2)

Varianti

Iterated-HCS: quando il minimo valore di taglio viene ottenuto da diversi tagli distinti, l’algoritmo HCS ne sceglie uno arbitrariamente. Questo processo potrebbe suddividere piccoli cluster in singoletti. Per superare questo inconveniente, è possibile eseguire diverse (1-5) iterazioni di HCS fino a che nessun nuovo cluster viene trovato

Singletons Adoption: i singoletti possono essere “adottati” dai cluster. Per ogni elemento singolo x si calcola il numero dei vicini presenti in ogni cluster e nell’insieme dei singoletti S. Se il massimo numero di vicini è sufficientemente grande ed è ottenuto da uno dei cluster (piuttosto che da S) allora x viene aggiunto a quel cluster. Questo processo viene ripetuto diverse volte

38

HCS (3)

Removing Low Degree Vertices: quando il grafo di similarità contiene vertici con grado basso, un’iterazione dell’algoritmo di taglio minimo potrebbe semplicemente separare i vertici di grado basso dal resto del grafo. Eliminare i vertici di grado basso da G elimina queste iterazioni e riduce in modo significativo il tempo di esecuzione. Il processo è ripetuto con diverse soglie sul grado

39

( )( ) ( )

( ) ( )( ) ( )

{ }cluster stesso nello stiano geni due

,diversicluster in stanno ,

,cluster stesso nello stanno ,

j gene il e i gene il trasimilarità la arappresent che casuale Variabile

diversicluster in stanno ,1

cluster stesso nello stanno ,log

2

2

Pp

NjiSf

NjiSf

S

jiSfp

jiSfpw

FT

FFij

TTij

ij

ij

ijij

=

>

≈

≈

⋅−

⋅=

μμ

σμ

σμ

CLICK

L’informazione iniziale è rappresentata dalla matrice nxp dell’Espressione Genica M.

Ogni riga i di M rappresenta l’impronta digitale del gene i-esimo. L’obiettivo dell’algoritmo è quello di determinare cluster di geni tali che i geni in ogni cluster siano altamente simili nell’espressione mentre geni in cluster diversi siano dissimili nell’espressione.

Sulla base di M si costruisce un grafo i cui vertici sono i geni mentre gli archi rappresentano la probabilità che i due vertici dell’arco stiano in uno stesso cluster. Ad essa si assegna il valore:

40

L’idea dell’algoritmo è la seguente: dato un grafo G si vorrebbe decidere se i suoi vertici rappresentano geni appartenenti ad un solo cluster oppure no. Nel primo caso di dice cheG è puro. Per decidere questo si determinano tutti i tagli del grafo G e si valutano le seguenti ipotesi per ogni taglio C del grafo: H0C: il taglio contiene solo geni di uno stesso cluster H1C: il taglio contiene almeno due geni di cluster diversiSe P[H0C]>P[H1C] per ogni taglio C di G allora si dice che G è un kernel

Basic-CLICK(G(V,E)) if (V(G)={v}) then sposta v nell’insieme di singoletti R elseif (G è un kernel) then return V(G) else (H,Q,taglio) = Taglio_A_Peso_Minimo(G) Basic-CLICK(H) Basic-CLICK(Q) end ifend

( ) { }{ }( ) { } { }

{ } { } kernel un essere può nonG dunque e CHPCHP

taglio quel per allora positivo non é minimo taglio il

seViceversa tagli. altri gli sarannolo ragione maggir a positivo é

minimo taglio il SeCHPCHP sseCW Ovviamente

CHP

CHPCW

che vede siBayes di regola la oUtilizzand

positivo é

G di minimo peso a taglio il se soloe sekernel un éG

CC

CC

C

C

01

01

0

1

.0

log

≤

>>

=

:dim

Lemma

Le performance di CLICK raffrontate con altri algoritmi di clustering risultano superiori sia in qualità che velocità

CLICK: l’algoritmo

41

La PCA è una tecnica per la riduzione del numero di variabili casuali che descrivono un fenomeno. L’obiettivo e’ quello di identificare un sottoinsieme di variabili casuali dalle quali dipende la maggiore varianza (‘variabilità’) del fenomeno

y descrive meglio di x la variabilità del fenomeno

Analisi Componenti Principali (PCA)

42

Matrice di Covarianza

R =E xxT{ }

input Componente principale i

)(irTx

)()( iir λ→

r(i) è l’autovettorecorrispondente all’i-esimoautovalore λ(i)

Il sottospazio generato da r(1), …, r(M),(M<d), è chiamato sottospazio PCA

x

PCA: i dati

43

Obiettivo: mappare vettori x = (x1,…, xd) in vettori z = (z1,…, zM) con M<d.

x = xiuii=1

d∑

ui sono d vettori ortonormali

ijji δ=uuT

xuTiiz =

∑ ∑= +=

+=M

i

d

Miiiii bz

1 1

uux~ ∑+=

−=d

Mii

ni

nn bz1

iu)(x~-x

Errore

Somma dei quadrati degli errori

∑ ∑∑= +==

−=−=N

n

d

Mii

ni

N

n

nnM bzE

1 1

22

1

)(2

1x~x

2

1xu1

1

T∑=

==N

ni

nii z

Nb∑

+=

∑=d

MiiiME

1

T uu2

1

iii uu λ=∑ ∑+=

=d

MiiME

12

1λ

L’errore minimo è ottenuto scegliendoi più piccoli d-M autovalori; ogni autovettore ui è chiamato componenteprincipale

Trasformazione di Karhunen-Loéve