Embed Size (px)
Citation preview
Agrupamento de sequências biológicas
Marcos CastroGrupo de Bioinformática
ICT-Unifesp
2
Agrupamento de sequências biológicas• Agrupamento = clustering• Clustering é uma técnica de Data Mining (mineração de dados).• O objetivo é agrupar dados de forma automática conforme um grau
de semelhança.• O critério de semelhança faz parte da definição do problema.
3
Agrupamento de sequências biológicas
4
Agrupamento de sequências biológicas• Um agrupamento consiste em agrupar dados em clusters onde um
agrupamento em um determinado cluster seja uma coleção de objetos que são semelhantes um ao outro e diferentes de objetos que estão em outros grupos.• Exemplo: agrupar clientes de um banco para selecionar aqueles que
tem o menor risco de dar calote num empréstimo.• Um bom agrupamento assegura que a similaridade inter-cluster seja
baixa e a similaridade intra-cluster seja alta.
5
Agrupamento de sequências biológicas• Existem várias medidas de dissimilaridade ou de proximidade entre
cada par de objetos. Exemplos de distâncias:• Distância euclidiana• Distância Manhattan• Distância de Mahalanobis
6
K-Means• Apresentado por J.B. MacQueen em 1967.• K-Means é uma heurística de agrupamento não-hierárquico que
busca minimizar a distância dos elementos a um conjunto de K centros.• Métodos não-hierárquicos: dividem os N dados existentes em K
partições.• Métodos hierárquicos: os agrupamentos são representados em uma
estrutura, na forma de árvore, denominada dendograma.
7
K-Means• Agrupamento não-hierárquico e hierárquico.
8
K-Means• Passos do K-Means:• 1. Escolhe-se K distintos valores para centros dos grupos (esse passo pode ser
feito de forma aleatória ou utilizando algum método/heurística).• 2. Associar cada ponto ao centro mais próximo.• 3. Recalcular o centro de cada grupo.• 4. Repetir os passos 2-3 até nenhum elemento mudar de grupo ou atingir o
máximo de iterações.
9
K-Means• Algoritmo:
10
K-Means++• K-Means++ é uma tentativa de melhorar a acurácia do K-Means.• O K-Means escolhe os K centros randomicamente, isso é rápido e
simples de fazer, mas pode prejudicar no processo de agrupamento.• O K-Means++ é uma técnica baseada em sementes para inicialização
dos clusters.
11
K-Means++• Algoritmo K-Means++:
• O D(x) é a menor distância de um data point para um centro que já foi escolhido.• Referência: kmeans++ The Advantages of Careful Seeding.
12
Elbow method• O parâmetro K é a quantidade de clusters, isso é definido pelo
usuário, mas existem métodos que nos ajudam a escolher o melhor K.• Exemplo: Elbow.• O método Elbow calcula o SSE (sum of squared error) para alguns
valores de K (exemplo: 2, 4, 6, etc.).• O SSE é a soma da distância ao quadrado entre cada membro do
cluster e seu centroide. Matematicamente:
13
Elbow method• Algoritmo:
14
Elbow method• A ideia do elbow é escolher um K no qual o SSE cai abruptamente,
isso é chamado de “elbow effect” no gráfico:
Nesse caso foiescolhido k = 6
15
Elbow method• O método elbow é uma heurística, portanto, pode não trabalhar bem
em determinados casos.
16
Agrupamento híbrido• O K-Means recomputa os centros baseado em uma média simples.• A proposta aqui é utilizar duas técnicas para calcular a média.• De acordo com o artigo “A Hybrid Clustering Algorithm for Data
Mining”, a acurácia é melhor.• No artigo em questão, é proposto um algoritmo que hora recalcula os
centros usando a média harmônica e hora recalcula utilizando a média aritmética.
17
Agrupamento híbrido• Por que um híbrido?• O algoritmo do K-Means é baseado na média. A média é afetada fortemente
por outliers (valores extremos). Por isso é proposto um algoritmo que executa dois métodos para encontrar a média ao invés de um.• A média harmônica converge bem quando tem-se uma inicialização ruim.
18
Agrupamento híbrido• Algoritmo de agrupamento híbrido:
19
Agrupamento de sequências biológicas• E as sequências biológicas?• Precisamos comparar essas sequências, transformá-las em pontos.• Várias métricas de similaridade:• Needleman-Wunsch (alinhamento ótimo global)• Smith-Waterman (alinhamento ótimo local)• Longest common subsequence (mais longa subsequência comum)• White-Similarity/Dice’s coefficient (ranking de similaridades)• Hamming distance (strings de comprimentos iguais)• Edit distance
20
Clustering of Biological Sequences• Projeto open-source que visa agrupar sequências biológicas.• https://github.com/marcoscastro/clustering_bio_sequences
• Implementa:• K-Means• K-Means++• Agrupamento híbrido• Várias métricas de similaridade• Elbow method• ODIN (outlier detection based in-degree of the kNN graph)
• Implementação em C++
21
Clustering of Biological Sequences• Podem ser passados vários parâmetros, mas a princípio necessita
somente do número de clusters e de um arquivo com as sequências no formato FASTA.• Testes foram feitos com dataset “splice data”:• https://archive.ics.uci.edu/ml/datasets/Molecular+Biology+(Splice-junction+
Gene+Sequences) • Todos os exemplos retirados do Genbank.• 3 classes (EI, IE, N) e 3190 sequências.
22
Clustering of Biological Sequences• Foram feitos vários testes variando vários parâmetros, o dataset
“splice data” foi dividido em datasets menores.• O primeiro teste foi com 600 sequências (mesma quantidade para
cada classe) utilizando K-Means++ híbrido com K = 3 e distância Hamming.
EI IE N
Cluster 1 166 7 27
Cluster 2 14 191 26
Cluster 3 20 2 147
23
Clustering of Biological Sequences• O segundo teste foram com 600 sequências (mesma quantidade para
cada classe) utilizando K-Means++ com K = 3 e LCS.
EI IE N
Cluster 1 46 153 56
Cluster 2 38 39 87
Cluster 3 116 8 57
24
Clustering of Biological Sequences• O terceiro teste foram com as 3190 sequências (todas as sequências)
utilizando K-Means++ com K = 3 e distância Hamming.
EI IE N
Cluster 1 39 722 124
Cluster 2 656 31 181
Cluster 3 72 16 1349
25
Clustering of Biological Sequences• Se não souber o K (número de clusters), o método elbow pode lhe
ajudar. Precisa-se instalar a biblioteca koolplot.
26
Clustering of Biological Sequences• ODIN• Outlier detection using in-degree number.• Utiliza kNN graph.• ODIN é um método para detecção de outliers (valores extremos).• Por que detectar outliers?
• Para eliminá-los.• Utilizar qualquer método para o agrupamento.
• Caso o usuário utilize o método de detecção de outliers, a ferramenta gera um grupo só com os outliers e elimina eles do processo de agrupamento.
27
Clustering of Biological Sequences• ODIN algorithm
• Referência: http://cs.joensuu.fi/~villeh/35400978.pdf
28
Trabalhos futuros• Refinamento do agrupamento.• Algoritmos genéticos (AGs).• ACO (Ant colony optimization)
• Alinhamento de sequências utilizando AGs.
