UNIVERSITA’ DI MILANO-BICOCCA
LAUREA MAGISTRALE IN
BIOINFORMATICA
Corso di
BIOINFORMATICA: TECNICHE DI BASE
Prof. Giancarlo Mauri
Lezione 13
Clustering di dati da microarrays
Sommario

Introduzione

La tecnologia dei DNA microarrays

Algoritmi di Clustering

algoritmi gerarchici

metodo del centroide

K-Means

Metodi evoluti (CLICK)
2
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
3
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à
4
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
5
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
Distanza euclidea
Distanza di Manhattan

2
d x, y     xi  yi  
 i

d x, y    xi  yi
1
2
i

k
Distanza di Minkowski d x, y    xi  yi 
 i

1
k
6
Espressione genica
 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.
7
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
8
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
9
Microarray cDNA
2
1
2
1
+
1
2
Array con probes immobilizzati
2
Soluzione di bersaglie da campione 1 e 2,
etichettati con tintura 1 e 2 rispettivamente
1
2
12
Array con molecole etichettate di bersagli
ibridizzate con i probes
10
Microarray cDNA
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
11
Microarray cDNA
12
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)
13
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
14
Clustering Gerarchico
Viene impiegata una struttura ad albero
Radicato
Una particolare rappresentazione è il
dendrogramma
Non radicato
15
Clustering Gerarchico
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)
16
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)
17
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
18
Neighbor Joining Algorithm
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:
Dit  Dti 
Dir  Dis  Drs
2
5. Ripetere, finché non rimane un solo elemento.
19
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
20
Esempio
Si supponga di avere la matrice X di 5 elementi di dimensione 3:
0
2
X = 1
0
5
2
4
1
0
11
5
0
4
2
0
x1
x2
x3
x4
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
21
Metodo del Centroide
22
Neighbor Joining Algorithm
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:
23
Neighbor Joining Algorithm
Alla 1° iterazione Drs  dist (1,2)  2 per cui si devono fondere i cluster 1 e 2:
Alla 2° iterazione Drs  dist (1,2)  2 per cui si devono fondere i cluster 3 e 4:
Alla 3° iterazione fondiamo i due cluster così ottenuti e otteniamo per cui
una matrice con un unico elemento. L’esecuzione quindi termina.
24
Neighbor Joining Algorithm
Vediamo come avviene la generazione dell’albero (ricordando che i pesi degli
archi sono determinati tramite D 2 ):
rs
25
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
26
Average Linkage
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:
Dit  Dti 
ns
nr
 Dir 
 Dis
nr  n s
nr  n s
La misura della distanza tra due cluster è considerata la media della distanza
di ogni membro del cluster da ogni membro dell’altro
27
Average Linkage
Esistono 2 metodi alternativi:
Single Linkage
Complete Linkage
28
Average Linkage
Data la seguente matrice delle distanze vediamo un esempio pratico di tutti e
tre i metodi sopra citati:
29
Average Linkage
Il seguente è il dendrogramma
relativo al Single Linkage
dell’esempio riportato sopra. Gli
altri due sono differenti ma si
ricavano esattamente nello stesso
modo.
30
Una struttura generale
Riportiamo la struttura generale del clustering gerarchico:
Dit  Dti   r Dir   s Dis   Dir  Dis
Nell’algoritmo dell’Average Linkage avremo che i parametri assumeranno i
seguenti valori:
 0
nr
r 
nr  ns
ns
s 
nr  ns
31
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
32
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
33
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
34
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
35
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
36
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
37
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
38
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:
wij  log
Sij
p  f Sij i, j stanno nello stesso cluster 
1  p   f Sij i, j stanno in cluster
diversi 
Variabile casuale che rappresent a la similarità tra il gene i e il gene j

f Sij i, j stanno nello stesso cluster   N T ,  T2

f Sij i, j stanno in cluster diversi   N  F ,  F2


T   F
p  Pdue geni stiano nello stesso cluster 
39
CLICK: l’algoritmo
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 che
G è 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 diversi
Se 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 if
end
Lemma G é un kernel se e solo se il taglio a peso minimo di G
é positivo
dim :
Utilizzand o la regola di Bayes si vede che
W C   log
 
PH C 
P H1C C
C
0

 

OvviamenteW C   0 sse P H1C C  P H 0C C . Se il taglio minimo
é positivo a maggir ragione lo saranno gli altri tagli. Viceversa se
il taglio minimo é non positivo allora per quel taglio

 

P H1C C  P H 0C C e dunque G non può essere un kernel
Le performance di CLICK raffrontate con altri algoritmi di clustering risultano superiori
sia in qualità che velocità
40
Analisi Componenti Principali (PCA)
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
41
PCA: i dati
input
x
Matrice di Covarianza
 
R  E xx T
Il sottospazio generato da r(1), …, r(M),
(M<d), è chiamato sottospazio PCA
Componente principale i
xT r (i )
r (i )   (i )
r(i) è l’autovettore
corrispondente all’i-esimo
autovalore (i)
42
Trasformazione di Karhunen-Loéve
Obiettivo: mappare vettori x = (x1,…, xd) in vettori z = (z1,…, zM) con
M<d.
Errore
u iT u j   ij
d
M
x   x iu i
i1
zi  u iT x
~
x   zi u i 
i 1
d
 bi u i
x -~
xn 
n
i  M 1
d
 ( zin  bi )u i
i  M 1
ui sono d vettori ortonormali
Somma dei quadrati degli errori
1 d T
EM   u i  u i
2 i M 1
 u i  i u i
1 N n
bi   zi  u iT x
N n1
1 d
EM   i
2 i M 1
1 N
EM   x n  ~
xn
2 n1
2

1 N d n
( zi  bi ) 2


2 n1 iM 1
L’errore minimo è ottenuto scegliendo
i più piccoli d-M autovalori; ogni
autovettore ui è chiamato componente
principale
43