Clustering Algorithms for
Gene Expression Analysis
Pablo Viana
Fagner Nascimento
Roteiro
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Gene Expression Analysis
Redução de Dimensionalidade
Clustering
Hierarchical Clustering
K-Means
Self-Organizing Maps
Gene Clustering
Sample Clustering
Região Reguladora
Conclusão
Gene Expression Analysis

Micro Array Data Matrix:
Gene Expression Analysis
Gene Expression Analysis


Estudo dos padrões de ativação
(expressão) dos genes sobre diversas
condições.
Genes que possuem a mesma
funcionalidade são comumente
ativados pelas mesmas condições.
Gene Expression Analysis



Genes codificadores de enzimas que catalisam
um conjunto de reações encadeadas são
geralmente co-regulados (e normalmente se
localizam próximos no cromossomo).
A ativação conjunta também ajuda a inferir
funcionalidades de genes dos quais ainda não
temos informações.
Ou ainda o inverso, o padrão de ativação dos
genes pode caracterizar doenças e assim
gerar novas ferramentas precisas de
diagnóstico.
Gene Expression Analysis

Dessa forma diversas técnicas de
análise de dados tem sido aplicadas
para problemas dessa classe:

Redução de Dimensionalidade:


Clustering:



Principal Component Analysis
Hierarchical Clustering
K-Means
Self-Organizing Maps
Redução de Dimensionalidade

Vetores de dados biológicos possuem
muitas dimensões, desta forma
métodos que diminuem a
dimensionalidade dos dados, facilitam
a extração de informações dos
mesmos. Seja para sua melhor
visualização ou como métodos de préprocessamento.
Redução de Dimensionalidade

Principal Component Analysis (PCA):


Método estatístico para projetar pontos de
dimensão M num espaço de dimensão K (K <<
M).
Encontra a representação num espaço de
dimensionalidade menor que descreve os pontos
dados com o menor erro possível.
Clustering

O que é clusterizar?

Classificar, agrupar, comprimir.
Clustering
Clustering

Tipos de dados



Numérico
Relacional
Nominal

Similaridade / Distância

Número de Clusters
Clustering

Supervisionado:


Não-Supervisionado:


Baseado num conjunto de vetores ou classes
dados.
Não existe nenhum conhecimento prévio de
classificação.
Métodos Híbridos:

Métodos supervisionados utilizando
classificações previamente obtidas pela
aplicação de um método não-supervisionado.
Hierarchical Clustering

Algoritmo:



Os dois elementos mais similares(na matriz de
similaridade) unem-se criando-se um novo nó.
A matriz de similaridade é recalculada, com o
novo nó substituindo os dois antigos e com valor
igual a média dos anteriores.
Com N pontos iniciais, esse processo é repetido
N-1 vezes até restar apenas um nó.
Hierarchical Clustering
Hierarchical Clustering

Árvore de Visualização

Problema:



Encontrar a melhor ordenação da árvore.
Cada filho pode estar a esquerda ou direita.
2N-1 possibilidades.
Solução:

Conhecido algoritmo de programação
dinâmica: inside portion of the inside-outside
algorithm for stochastic context-free grammar
Hierarchical Clustering

Desvantagens:


A divisão da árvore em clusters não é clara.
Métodos de classificação usando hierarchical
clustering são imprecisos.
K-Means

Algoritmo:

Inicialização:




Defina K;
Gere K vetores representantes;
Para cada ponto associe-o ao representante
mais próximo.
Para cada representante, redefina sua posição
como sendo a média das distâncias dos
componentes associados a ele no passo
anterior. Caso a variação dos representantes
seja menor que um limiar finalize o algoritmo,
caso contrário, volte ao passo anterior.
K-Means
K-Means

Vantagens:



Fácil implementação
Convergência rápida
Desvantagens:


Nem sempre gera uma divisão ótima
Má escolha dos representantes
K-Means
Self-Organizing Maps




Também conhecido como Kohonen
Map, foi descrito pela primeira vez
como uma rede neural artificial.
Parecido com o K-Means.
Preserva as propriedade topológicas
dos dados.
Algoritmo não-supervisionado.
Self-Organizing Maps

Algoritmo:




Crie um conjunto de nós.
Mapeie-os aleatoriamente pelo espaço de
entrada.
A cada iteração escolha um ponto da entrada
aleatoriamente e encontre o nó mais próximo a
ele.
Este nó e seus vizinhos se moverão em direção
a este ponto. A influência do nó escolhido nos
vizinhos decresce com relação à distância entre
eles e a iteração.
Self-Organizing Maps

Vantagens:




O algoritmo converge para um mapa de classificação e
topologia ótimas.
Possui uma forma muito conveniente para visualização
dos dados.
Manipula bem dados não uniformes e irregulares.
Desvantagens:


Não tem base teórica para determinar a dimensão ótima.
Pode demorar muitas iterações para convergir (20.000 50.000).
Gene Clustering


A co-expressão de genes sugere que
eles são relacionados funcionalmente
e que eles são possivelmente coregulados.
A função de muitos genes nãocaracterizados podem ser descobertas
a partir das funções de genes coexpressados conhecidos.
Gene Clustering

Os principais objetivos de gene
clustering são:




Organização funcional de genes.
Interpretar o estado da célula de acordo
com um determinado padrão de
expressão gênica.
Deduzir a função de genes
desconhecidos.
Explorar a regulação transcricional.
Sample Clustering




Verificar a expressão gênica relativa a uma
condição fisiológica.
Classificar doenças utilizando perfis de
expressão gênica baseados em micro-array.
Agrupar experimentos de acordo com a
similaridade dos perfis.
Os clusters identificados podem ser
analisados diretamente dos padrões de
expressão gênica associados sob
perspectivas moleculares ou clínicas.
Visualization of Gene
Expression Data
Applets



http://home.dei.polimi.it/matteucc/Clust
ering/tutorial_html/AppletH.html
http://home.dei.polimi.it/matteucc/Clust
ering/tutorial_html/AppletKM.html
http://davis.wpi.edu/~matt/courses/som
s/applet.html
Referências







Handbook of Computational Molecular Biology
(Chapman & Hall/CRC Computer and Information
Science Series) Cap. 25;
http://compbio.utmem.edu/MSCI814/Module10.htm
http://www.ucl.ac.uk/oncology/MicroCore/HTML_res
ource/PCA_1.htm
http://en.wikipedia.org/wiki/DNA_microarray
http://en.wikipedia.org/wiki/Data_clustering
http://en.wikipedia.org/wiki/Self_organizing_maps
http://www.autonlab.org/tutorials/kmeans.html