Clustering Algorithms for Gene Expression Analysis

Adaptado de uma apresentação de

Pablo Viana

Fagner Nascimento

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.

O padrão de ativação dos genes pode caracterizar doenças e assim gerar novas ferramentas precisas de diagnóstico.

Micro Arrays

probe(on chip)

sample(labelled)

pseudo-colourimage

[image from Jeremy Buhler]

Micro array Output Image

Color-coded spots:

Gene Expression Analysis

Micro Array Data Matrix:

Gene Expression Analysis

Diversas técnicas de análise de dados têm sido aplicadas para problemas dessa classe: Redução de Dimensionalidade:

Principal Component Analysis Clustering:

Hierarchical Clustering K-Means

Self-Organizing Maps

Redução de Dimensionalidade

Vetores de dados biológicos possuem muitas dimensões.

Métodos que diminuem a dimensionalidade dos dados facilitam a extração de informações.

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: Baseado num conjunto de vetores ou classes

dados. Não-Supervisionado:

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 co-regulados.

A função de muitos genes não-caracterizados podem ser descobertas a partir das funções de genes co-expressados 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 transcripcional.

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/Clustering/tutorial_html/AppletH.html

http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html

http://davis.wpi.edu/~matt/courses/soms/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_resource/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