Agrupamento de sequências biológicas

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.

29

Dúvidas?

mcastrosouza@live.comtwitter.com/mcastrosouza