Clustering de Dados de Expressão Gênica Diogo Fernando Veiga Centro de Informática - UFPE

Clustering de Dados de Expressão Gênica

Diogo Fernando VeigaCentro de Informática - UFPE


Roteiro• Introdução ao Clustering• Microarrays• Medidas de Distância e Similaridade• Clustering Hierárquico• Clustering com Partição• Clustering com Grafos• Avaliação de Soluções


Clustering - Definição• Técnicas para agrupar objetos baseados em suas

similaridades ou diferenças• Encontrar grupos mais homogêneos e separados

possíveis nos dados• Facilita a análise• Em Data Mining, é mais uma técnica de descoberta

de conhecimento (padrões) nos dados• resumo dos dados • compra casada (Amazon, Wall-Mart)


Expressão Gênica - Microarray• Microarrays medem a atividade (nível de

expressão) de genes • Nível de expressão é estimado pela quantidade de

mRNA do gene• Experimentos projetados para diferentes condições

• sem O2, deleção de gene, inserção de nutriente, etc)• várias amostragens no tempo (0 min, 30 min, 60 min, ...)

• Snapshot da célula: milhares de genes em paralelo


Interpretando Microarrays• Acompanhar duas amostras diferentes sob a mesma

condição (ou o inverso)

Cada gráfico é a expressão do gene ao longo do tempo


Microarray Data• dados (normalizados) em matrizes de intensidade I • I(i,j) = nível do gene i no experimento j• I(i,*) = padrão de expressão do gene i (linha)

Time: Time X Time Y Time Z

Gene 1 10 8 10

Gene 2 10 0 9

Gene 3 4 8.6 3

Gene 4 7 8 3

Gene 5 1 2 3


Aplicações de Clustering• Atribuir função a um gene (onde a similaridade entre

seqüências foi fraca)• Revelar grupos de genes co-regulados, participando de

um mesmo processo biológico (signal transduction, gene regulatory pathway, ...)

• Outras aplicações em bioinfo: clustering de estruturas de proteínas, famílias, motiffs, )


Clustering de Dados Microarray

Clusters


Medidas de Distância• Manhattan ou city-block (para binários: hamming)

• Euclidiana

• Chebyshev


Medidas de Similaridade• Produto interno (vetores

normalizados)

• Coeficiente de correlação

yx

xy

ssS

r


Métodos de Clustering• Existem várias técnicas de clustering, que vem

sendo aplicadas aos dados de microarray: • Hierárquico (divisivo e aglomerativo)• Partição• Grafos• Cobertura (fuzzy, probabilísticos)• Self-organized maps (SOM)


Clustering Hierárquico Organiza os elementos em uma árvore binária com

escala de similaridade (dendograma), onde: Nodo folha: um cluster singleton Nodo não-folha: um agrupamento associado a um nível de

similaridade

Divisivos e aglomerativos


Clustering Hierárquico - Exemplo


Hierárquico Aglomerativo Esquema

Nex = número de elementos a agrupar

Nc = número de clusters


Hierárquico Aglomerativo Como encontrar o par de clusters mais próximos:


Hierárquico Aglomerativo - Algoritmo d – matriz de distâncias n – número de elementos

1. Hierarchical Clustering (d , n)2. Forme n clusters cada um com 1 elemento3. Construa um grafo T atribuido um vértice a cada cluster4. while existe mais de um cluster5. Encontre o par de clusters C1 e C2 mais próximos6. Merge C1 e C2 em um novo cluster C com |C1| +|C2| elementos7. Calcule a distância de C para todos os outros clusters8. Adicione um novo vértice C aT e conecte os vertices C1 e C2

9. Remova linhas e colunas de d correspondentes a C1 e C210. Adicione uma linha e coluna em d para o novo cluster C11. retorne T


Hierárquico Aglomerativo - Exemplo

60 min 120 min 180 min

g1 10 8 10

g2 10 0 9

g3 4 8,5 3

g4 9,5 0,5 8,5

g5 4,5 8,5 2,5

g1 g2 g3 g4 g5

g1 0 8,06 9,23 7,66 9,31

g2 0 12,01 0,86 12,03

g3 0 11,15 0,7

g4 0 11,18

g5 0

Matriz D

Matriz I (expressão) Executar o clustering hierárquico

aglomerativo para os genes 1..5 Dist. entre clusters: média Entrada: matriz D, int n


Hierárquico Aglomerativo - Exemplo Passo 0)

g1 g2 g3 g4 g5

Passo 1)

Dmed(g1,g3,5) = (9,23+9,31)/2 = 9,27

g1 g2 g4 g3,5

g1 0 8,06 7,66 9,27

g2 0 0,86 12,02

g4 0 11,16

g3,5 0

g1

g2

g3

g4 g5

g3,5


Hierárquico Aglomerativo - Exemplo

g1 g2,4 g3,5

g1 0 7,86 9,27

g2,4 0 11,59

g3,5 0

Passo 2)

g1g2g3 g4g5

g3,5 g2,4

Passo 3)

g1,2,4 g3,5

g1,2,4 0 10,81

g3,5 0

g1,2,4

g3

g2

g5

g4

g1

g3,5

g2,4


Hierárquico Aglomerativo - Exemplo Passo 4)

g1.. 5

g1..5 0

g1,2,4

g3

g2

g5

g4

g1

g3,5

g2,4

g1..5

g3 g5 g2 g4 g1

0.70.86

7.81

10.81


Clustering Hierárquico - Divisivo Esquema (top-down)

Nex = número de elementos a agrupar

Nc = número de clusters


Clustering Hierárquico - Divisivo 2 decisões: como redistribuir os elementos e como

escolher o próximo cluster para particionar (pior) Como escolher o pior cluster:

• Maior número de exemplos• Maior variância• Maior erro quadrático médio

• Como redistribuir:• Elemento mais próximo do centro de gravidade• Distância média em relação aos elementos do cluster


Hierárquico Divisivo - Algoritmo






Clustering Partição - Definição• Objetivo: encontrar, dentre todas as partições

possíveis, a melhor partição dos dados em um número pré-definido de grupos.

• Envolve 3 passos:• Definir uma medida de dis(similaridade) entre os

exemplos;• Definir uma função objetivo do clustering;• Definir um algoritmo para minimizar a função objetivo.


Clustering Partição – Notação

nixi ..1 com objetos,

clusters com , partição kCCCP k },...,,{ 21

..kjj 1 com gravidade, de centros

associado ),...,,(, 21 piiii xxxescriçãovetor de dx

..kj||Cn jj 1 com ,


Clustering Partição – Função Objetivo• A função amplamente utilizada é a soma das

distâncias quadráticas• Este critério mede o quanto o conjunto de dados X é bem

representado pelos centros dos clusters

jj Cxj

jj

k

j CxSDQ x

nμ)μ(x,dJ 1,

1

2 onde


Clustering Partição – Otimização Iterativa• Uma vez definido o critério de clustering, devemos encontrar

uma partição dos dados que minimize esse critério;• Busca por todas as possibilidades (enumeração) não é tratável• Por exemplo, para 5 clusters com 100 exemplos, temos 1067

particionamentos ( kNex diferentes partições)• A abordagem utilizada é proceder de modo iterativo:

• Definir uma partição inicial aleatória• Mover elementos de um cluster para o outro, buscando

minimizar a função objetivo• Estas abordagens iterativas produzem soluções não ótimas,

mas são computacionalmente tratáveis• Clustering hierárquico também é implicitamente otimização


Clustering – Algoritmo das Transferências

para vá então , Se

então se

que tal determinar

, Para

iterativa Etapa

centróidescalcular e P aleatória partição umaDefinir

(b)test(c)n e nn nxC e CxCC

nxn

nxntest

sl

xdn

nxdn

nl

l

..n i xtestb

..k, ja

ssllissill

s

isss

l

illl

sis

sji

j

j

s..k, k j

Ci

j

s

011

111

,1

,,1

minminarg

10

)(

1)(

22

1


Clustering – Algoritmo k-means

para vá então , Se

então se

que tal determinar

, Para

iterativa Etapa

centróidescalcular e P aleatória partição umaDefinir

(b)test(c)n e nn nxC e CxCC

nxn

nxntest

sl

xdl

l

..n i xtestb

..k, ja

ssllissill

s

isss

l

illl

ji..kj

Ci

j

s

011

111

,minarg

10

)(

1)(

2

1


Clustering – Algoritmo Centros Móveis

para vá então , Se (d)

então se

que tal determinar

, Para

iterativa Etapa (c)

centróidescalcular :çãorepresenta de Etapa (b) P aleatória partição umaDefinir (a)

(b)testn e nn nxC e CxCCtest

sl

xdl

l

..n i xtest

..k, j

ssllissill

ji..kj

Ci

j

s

0111

,minarg

10

1

2

1


Clustering Partição – Considerações• A atualização dos centróides no k-means ocorre na

etapa de afetação, ao contrário do centros móveis.• No centro móveis: Com distancia city-block o

representante deve ser o vetor mediana (formado pela mediana de cada componente)


Clustering com Grafos• Grafo completo Kn – grafo não-orientado com n

vértices sendo que qualquer vértice está conectado a todos os outros

• Grafo clique – grafo no qual todas as componentes são grafos completos.


Clustering com Grafos• Um grafo pode ser transformado em um grafo clique

adicionando-se ou removendo-se arestas.• Exemplo: remoção de duas arestas para tornar o

grafo abaixo em um grafo clique


Grafo de distância• Vértices são os genes• Existe uma aresta entre o gene i e i com peso d(i,j)

sse d(i,j) < (threshold)• Um corte C em G é um subcojunto de suas arestas

que se removidas disconectam G. • Um corte de peso mínimo é um corte em G com o

peso mínimo (equivale ao número de arestas quando todas tem o mesmo peso).

• Pode ser construído a partir da similaridade s(i,j) >


Grafo de distância em Grafo Clique


Clique corrompido• Uma solução de clustering corresponde a um grafo

de similaridade que também é um grafo clique (k clusters k cliques)

• Grafos Cliques corrompidos• Erros em dados de expressão • Inexistência de um parâmetro universalmente bom (cria

ou remove arestas para genes não relacionados/relacionados)

• Problema do clique corrompido• Determinar o menor número de arestas a serem

adicionadas ou removidas para transformar o grafo em um grafo clique


Clique Corrompido Aleatório

Clustering com 4 grupos Contaminção aleatória: inserir ou remover com p < 0,5 para Ejv ),(

Grafo contaminado


PCC (Parallel Classification with Cores) Clustering • Agrupar um subconjunto S pequeno de vértices• Extender o clustering utilizando o critério de

afinidade maximal• N(i,Cj) – número de arestas entre o gene i e os genes do

cluster Cj• Afinidade maximal – maximizar

• É demonstrado que se o clustering de S está correto então com alta probabilidade V \ S também está corretamente agrupado

||),(

j

j

CCiN


PCC Clustering - Algoritmo

clique.tornar se para sadicionada e removidas arestas

minimiza queanterior passo do clustering o Escolha (d)

de clustering um em clustering o Extenda

clustering um em de clustering o Extenda

:faça em em clustering cada Para (c)

determine nteUniformeme (b)

, determine nteUniformeme (a)

},...,C,C{C

V},...,C,C{C},...,C,C{C

SS},...,C,C{CS},...,C,C{C

},...,C,C {Ck clustersS

n) O(| |S, tal que V\S S

n))(O(|tal que |SS

k

kk

kk

k

21

2111

211

1011

2110

002

01

002

010

101

00

,

,

log

loglog


PCC Clustering - Esquema


Cast Clustering• Na prática, usa-se uma heurística chamada CAST,

pois o PCC é muito lento.

• Distância entre um gene s e cluster Cj:

• Gene i está próximo do cluster Cj quando d(i, µj) < e distante caso contrário.

• Uma partição é formada construindo-se um cluster por vez (permite-se a saída e entrada de elementos no cluster).

• Boa performance em dados simulados e em dados reais biológicos.

j

Cx i

C

xsdji

),(


Cast Clustering - Algoritmo1. CAST(S, G, θ)2. P Ø3. while S ≠ Ø4. V vértice de grau máximo no grafo de distância G5. C {v}6. while existir um gene i próximo a C ou distante em C7. Encontre o gene mais próximo i ∉ C e o adicione a C8. Remova o gene mais distante i em C9. Adicione o cluster C a partição P10. S S \ C11. Remova os vértices do cluster C de G12. return P


HCS e Click Clustering• Entrada: grafo de similaridade• Compartilham o esquema básico abaixo:

Form-Kernels(G):If V(G) = then

mover v para o conjunto de singletons

Else if then

output V(G)Else

Form-Kernels(H); Form-Kernels(H’);

kernel um éG

);(', , GutMinWeightCcutHH


HCS Clustering• Grafo de entrada modificado:

• grafo sem pesos • arestas somente entre genes que excederam o treshold de

similaridade • Kernel H: é um HCS (highly connected subgraph).

Retirando-se arestas continua conectado • Funcionamento:

• Em cada iteração determina-se o corte de peso mínimo no grafo, e o separa em dois subgrafos.

• Se o subgrafo é um fortemente conectado ele pára (encontrou um cluster), senão continua processando recursivamente o subgrafo.

2HV


HCS Clustering - Exemplo


HCS - Heurísticas• Singletons são “adotados” por clusters ou continuam

no grupo de singleton, dependendo da afinidade.• Vértices de grau baixo são retirados do grafo: reduz

significamente o tempo de execução. Genes pouco relacionados são pouco informativos para o clustering.

• Merge de clusters caso sejam similares o bastante• HCS Iterativo: o algoritmo é executado com vários

valores inteiros de threshold para eliminação de vértices.


Click Clustering• Suposições: similaridade entre mates e nonmates

seguem uma normal • Parâmetros estimados dos dados: algoritmo EM• Grafo com peso: wij é a probabilidade de i e j serem

do mesmo cluster• Arestas abaixo de um determinado threshold são

omitidas• Noção de kernel: se o corte de peso mínimo nele for

positivo (probabilidade que contenha arestas somente entre mates excede a que contém somente não mates)

2, TTN 2, F

FN matesp


Algoritmo Click

),Lleton(LAdotarSing

)Merge(L

),Lleton(LAdotarSing

)ls(GForm-Kerne

(V,θR

R

singletonskernels

kernels

singletonskernels

façaacontecer mudança alguma while

)ticeeliminaVer


Click - Esquema


Avaliação do Clustering• Solução Conhecida• n11 – pertencem ao mesmo cluster de fato e na solução• n01, n10 - discordâncias• n00 – não pertencem ao mesmo cluster de fato e na

solução

00011011

11

nnnnnmatching

011011

11.nnn

nJaccardcoef

1011

1001nn

nnMinkowsky


Avaliação do Clustering (2)• Solução Não-Conhecida

),(max),(1

)))((,(min)))((,(1

),,(max),,(

),,(

..1,min1

jijiCCjiCCjiji

jiCCji

med

iinixi

n

iimed

xxii

SSSnnnn

S

xCFxSHxCFxSn

H

) e F(C xcluster de) C(x

jiji

ji

i

Máxima Separação Média Separação

mínima adeHomogeneid média adeHomogeneid

Considere


Saídas do Clustering


Métodos de Clustering - Cobertura Obter grupos que

podem compartilhar elementos

Abordagens Fuzzy, Probabilística


Artigos publicados Bioinformatics Journal: 337 hits

• Incremental generation of summarized clustering hierarchy for protein family analysis Nov 2004; 20: 2586 - 2596.

• Iterative cluster analysis of protein interaction data September 16, 2004

• HMMGEP: clustering gene expression data using hidden Markov models Jul 2004; 20: 1799 – 1800

• Incremental generation of summarized clustering hierarchy for protein family analysis Nov 2004; 20: 2586 – 2596

• CLICK and EXPANDER: a system for clustering and visualizing gene expression data Sep 2003; 19: 1787 - 1799


Artigos publicados (2) Journal of Computational Biology

• CUBIC: identification of regulatory binding sites through data clustering.Olman V, Xu D, Xu Y. 2003 Apr;1(1):21-40

• Genome Biology• Consensus clustering and functional interpretation of gene-

expression data 2004, 5(11):R94• Detection of evolutionarily stable fragments of cellular

pathways by hierarchical clustering of phyletic patterns 2004, 5(5):R32

• Exploring the conditional coregulation of yeast gene expression through fuzzy k-means clustering 2002, 3(11)


Artigos publicados (3) Nucleic Acids Research

• MSCAN: identification of functional clusters of transcription factor binding sites Jul,2004

• Transcription factor binding element detection using functional clustering of mutant expression data, Apr 2004; 32: 2362 - 2371.

• PHYTOPROT: a database of clusters of plant proteins, Jan 2004; 32: 351 – 353.

• Interaction of DNA with clusters of amino acids in proteins, Aug 2004; 32: 4109 – 4118.

• Visualization and interpretation of protein networks in Mycobacterium tuberculosis based on hierarchical clustering of genome-wide functional linkage maps, Dec 2003; 31: 7099 - 7109


Referências Clustering and Trees. An Introduction to Bioinformatics

Algorithms. Jones,NC & Pevzner,P.A. Chapter 10. MIT Press. Algorithmic Approaches to Clustering Gene Expression Data.

Shamir,Ron & Sharan,Roded. Current Topics in Computational Biology, Chapter 11.

• Inferring Cellular Networks Using Probabilistic Graphical Models. Friedman,Nir. Science, Feb.6,303:2004.

• Métodos de Partição: Numéricos e Simbólicos. Souza,R, Carvalho,F.A.T. Notas de aula.

• Aprendizagem de Dados Simbólicos e Numéricos. Carvalho,F.A.T. Notas de Aula

• Clustering Gene Expression Data. Shamir,R. Lecture 4 and 6 in Analysis of Gene Expression Data. Lectures notes, May 2002.


Referências (2) Data Mining. Witten,I & Frank,E. 2000,Morgan Kaufmann. How to Solve It: Modern Heuristics. Michalewicz,Z & Fogel,D.

3ed,2000,Springer. Introduction to Pattern Analysis. Osuna-Gutierrez,R.Lectures

notes.

Documents

Clustering de Dados de Expressão Gênica Diogo Fernando Veiga Centro de Informática - UFPE