Universidade da Beira Interior
Departamento de Informática
BiGGEsTS
Biclustering Gene Expression Time-Series
Joana Sofia de Pinho Gonçalves
Orientador do Projecto:
Sara C. Madeira
2007
Agradecimentos
Um agradecimento
muito especial à Sara,
pelo apoio, dedicação e amizade.
À minha família,
amigos e todos os que,
interessando-se ou não pelo meu
trabalho, contribuíram para que nunca
perdesse a vontade de perseguir os meus objectivos.
i
Conteúdo
Agradecimentos
i
Conteúdo
iii
Lista de Figuras
vii
Lista de Tabelas
xi
Lista de Algoritmos
xiii
Acrónimos
xv
1
.
.
.
.
.
.
.
1
1
3
4
4
6
7
10
.
.
.
.
.
11
11
12
12
14
15
Introdução
1.1 Contexto . . . . . . . . . . .
1.1.1 ADN e ARN . . . . .
1.1.2 Código genético . . .
1.1.3 Síntese de proteínas
1.2 Motivação . . . . . . . . . .
1.3 Objectivos . . . . . . . . . .
1.4 Conteúdo do Relatório . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Microarrays e Dados de Expressão
2.1 Microarrays . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 O que é exactamente um microarray de ADN? . . .
2.1.2 Passos básicos de uma experiência com microarrays
2.1.3 As cores de um microarray . . . . . . . . . . . . . . .
2.2 Dados de expressão genética . . . . . . . . . . . . . . . . . .
iii
iv
CONTEÚDO
3 Biclustering
3.1 Conceito de Biclustering . . . . . . . . . . . . . . . . .
3.1.1 Clustering vs biclustering . . . . . . . . . . . . .
3.2 Definições e Formulação do Problema . . . . . . . . .
3.2.1 Grafos pesados bipartidos e matrizes de dados
3.3 Complexidade do Problema . . . . . . . . . . . . . . .
3.4 Dimensões da Análise . . . . . . . . . . . . . . . . . .
3.4.1 Tipo de bicluster . . . . . . . . . . . . . . . . . .
3.4.2 Estrutura do bicluster . . . . . . . . . . . . . . .
3.4.3 Objectivos dos algoritmos de biclustering . . .
3.5 Aplicações de Biclustering . . . . . . . . . . . . . . . .
3.6 Biclustering em Séries Temporais . . . . . . . . . . . .
4
5
Trabalho Relacionado
4.1 Biclustering para Séries Temporais . . .
4.1.1 Algoritmos na aplicação . . . .
4.1.2 Algoritmos analisados . . . . .
4.2 Algoritmos de Clustering Hierárquico
4.2.1 Single-linkage clustering . . . . .
4.2.2 Complete-linkage clustering . . .
4.2.3 Average-linkage clustering . . . .
4.2.4 Centroid-linkage clustering . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A Ferramenta BiGGEsTS
5.1 Modelação . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Análise de Requisitos e Desenho . . . . . . . .
5.1.2 Estrutura . . . . . . . . . . . . . . . . . . . . . .
5.1.3 Arquitectura . . . . . . . . . . . . . . . . . . . .
5.2 Implementação . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Carregamento de dados . . . . . . . . . . . . .
5.2.2 Integração do algoritmo CC-TSB-Biclustering
5.2.3 Download de ficheiros da Gene Ontology . . .
5.2.4 Threads e barras de progresso . . . . . . . . .
5.2.5 Pós-processamento . . . . . . . . . . . . . . . .
5.2.6 Gestão de sessões . . . . . . . . . . . . . . . . .
5.2.7 Informação . . . . . . . . . . . . . . . . . . . .
5.2.8 Gráficos de expressão e padrão de expressão .
5.2.9 Clustering hierárquico e dendrogramas . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
17
18
19
21
21
22
22
24
26
27
27
.
.
.
.
.
.
.
.
29
29
30
33
47
48
48
48
49
51
. . . . 51
. . . . 52
. . . . 67
. . . . 67
. . . . 70
. . . . 71
. . . . 72
. . . . 72
. . . . 73
. . . . 73
. . . . 74
. . . . 75
. . . . 75
. . . . 76
CONTEÚDO
5.3
6
7
Finalização e Divulgação .
5.3.1 Executáveis . . . .
5.3.2 Instaladores . . . .
5.3.3 Licença . . . . . . .
5.3.4 Imagem e logótipo
5.3.5 Documentação . .
5.3.6 Site . . . . . . . . .
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Estudo de Caso
6.1 Carregamento de Dados . . .
6.2 Visualização de Matrizes . . .
6.3 Dendrograma . . . . . . . . .
6.4 Tabela de Funções . . . . . . .
6.5 Pré-Processamento . . . . . .
6.6 Biclustering . . . . . . . . . . .
6.7 Gráficos de Expressão . . . .
6.8 Análise de Funções Biológicas
6.9 Pós-Processamento . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
85
. 85
. 86
. 88
. 90
. 90
. 92
. 94
. 97
. 101
Conclusões e Trabalho Futuro
Bibliografia
.
.
.
.
.
.
.
77
77
81
82
82
83
83
103
105
Lista de Figuras
1.1
2
1.3
Relação entre a célula, os cromossomas e o ADN. O ADN
das células eucarióticas encontra-se no núcleo, dividido em
unidades estruturais (cromossomas). Os cromossomas são
formados por cadeias de ADN cujos segmentos codificam
genes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Representação de um gene na molécula de ADN e respectiva
localização no cromossoma. Exões (segmentos codificadores) e intrões (segmentos não codificadores). . . . . . . . . .
A síntese de proteínas e as funções do mRNA e tRNA. . . .
2.1
2.2
As fases de uma experiência com microarrays. . . . . . . . . .
Cores visíveis numa imagem digital de um microarray. . . . .
13
15
3.1
Diferentes tipos de biclusters. (a) bicluster constante; (b) linhas constantes; (c) colunas constantes; (d) valores coerentes
- modelo aditivo; (e) valores coerentes - modelo multiplicativo; (f) evolução global coerente; (g) evoluções coerentes
nas linhas; (h) evoluções coerentes nas colunas; (i) evoluções coerentes nas colunas; (j) evoluções coerentes em linhas
e colunas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Estrutura dos biclusters. (a) único; (b) exclusivos; (c) em
xadrez; (d) linhas exclusivas; (e) colunas exclusivas; (f) não
sobrepostos com estrutura em árvore; (g) não sobrepostos e
não exclusivos; (h) sobrepostos com estrutura hierárquica;
(i) sobrepostos e arbitrariamente posicionados. . . . . . . . .
Três processos biológicos identificados em séries temporais
de expressão genética. . . . . . . . . . . . . . . . . . . . . . .
1.2
3.2
3.3
vii
4
6
23
25
28
viii
4.1
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
5.12
5.13
6.1
6.2
6.3
6.4
6.5
6.6
LISTA DE FIGURAS
Aplicação do algoritmo D-Miner sobre a matriz de expressão
genética de valores discretos representada na Tabela 4.1. . .
40
Diagrama de casos das funcionalidades principais da ferramenta BiGGEsTS. . . . . . . . . . . . . . . . . . . . . . . . . . 53
Diagrama de casos do módulo de carregamento de dados. . 55
Diagrama de casos da selecção do organismo, no módulo de
carregamento de dados. . . . . . . . . . . . . . . . . . . . . . 56
Diagrama de casos do módulo de pré-processamento. . . . . 58
Diagrama de casos do módulo de aplicação de algoritmos
de biclustering e cálculo de funções biológicas dos biclusters
encontrados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Diagrama de casos do módulo de análise e visualização. . . 62
Diagrama de casos do módulo de pós-processamento. . . . . 65
Diagrama de casos da selecção do critério de filtragem, no
módulo de pós-processamento. . . . . . . . . . . . . . . . . . 66
Diagrama de casos da selecção do critério de ordenação, no
módulo de pós-processamento. . . . . . . . . . . . . . . . . . 67
Diagrama de pacotes da ferramenta BiGGEsTS. No centro,
o pacote que implementa a interface gráfica - applicationgui.gui; em volta, as suas dependências. . . . . . . . . . . . . 68
Diagrama de pacotes centrado no pacote smadeira.biclustering. 69
Logótipo do BiGGEsTS. . . . . . . . . . . . . . . . . . . . . . 83
Site do BiGGEsTS. . . . . . . . . . . . . . . . . . . . . . . . . . 84
Painel de carregamento de dados. . . . . . . . . . . . . . . . .
Matriz de valores original colorida. . . . . . . . . . . . . . . .
Matriz de valores original colorida e ordenada por ordem
crescente da condição t2 . . . . . . . . . . . . . . . . . . . . . .
Matriz de valores original colorida e ordenada por ordem
decrescente da condição t2 . . . . . . . . . . . . . . . . . . . . .
Matriz original de valores. As células que cujos valores estão
em falta são coloridas a azul-escuro. A navegação com o rato
por cima das células permite identificar a linha, a coluna e
o valor de cada célula em particular. . . . . . . . . . . . . . .
Painel de opções para o algoritmo de clustering hierárquico.
85
86
87
87
88
89
LISTA DE FIGURAS
6.7
Janela do BiGGEsTS com a janela do Java TreeView sobreposta. O Java TreeView apresenta o dendrograma resultante
do algoritmo de clustering hierárquico aplicado aos dados da
matriz de expressão original. . . . . . . . . . . . . . . . . . .
ix
89
6.8
Tabela de funções biológicas para os genes da matriz original. 90
6.9
Painel com as opções de pré-processamento. . . . . . . . . .
91
6.10 Matriz discreta sob a forma de uma tabela de símbolos colorida. A navegação do rato sobre as células permite identificar a linha, a coluna e o símbolo de cada célula em particular. 92
6.11 Painel com as opções para aplicação de algoritmos de biclustering e de análise de funções biológicas. . . . . . . . . . . . .
93
6.12 Matriz de valores colorida para os cinco primeiros biclusters do grupo de biclusters extraído pelo algoritmo CCCBiclustering sobre a matriz discreta. Na Figura vemos apenas o primeiro bicluster. Para ter acesso aos restantes é necessário mover a barra de deslocação (à direita) para baixo. .
93
6.13 Miniaturas dos gráficos de expressão dos 24 primeiros biclusters do grupo de biclusters extraído pelo algoritmo CCCBiclustering aplicado à matriz discreta. . . . . . . . . . . . . .
94
6.14 Miniaturas do padrão de expressão dos primeiros 96 biclusters do grupo de biclusters extraído pelo algoritmo CCCBiclustering aplicado à matriz discreta. Na imagem são
visíveis os biclusters com números entre o 45 e o 60. . . . . .
95
6.15 Gráfico de expressão do bicluster 10. Representa a expressão
de todos os seus genes nas suas condições. . . . . . . . . . .
96
6.16 Gráfico de expressão do bicluster 10 com os valores de expressão normalizados por gene para média 0 e desvio padrão 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
6.17 Gráfico de expressão dos genes do bicluster 10 em todas as
condições da experiência. . . . . . . . . . . . . . . . . . . . .
97
6.18 Gráfico do padrão de expressão do bicluster 10. . . . . . . . .
97
6.19 Tabela de funções biológicas para o grupo de biclusters calculadas usando um theshold de 0.01 para o p-value corrigido
pela correcção de Bonferroni. Os biclusters com funções biológicas estatisticamente significativas são assinalados a verde. 98
x
LISTA DE FIGURAS
6.20 Tabela de funções biológicas para o bicluster 95. Estão assinaladas três funções estatisticamente significativas: manutenção e assemblagem de subunidades ribossómicas de
grandes dimensões, assemblagem de complexos proteínaARN, processos metabólicos primários. . . . . . . . . . . . .
6.21 Grafo de funções biológicas significativas do bicluster 95. . .
6.22 Painel de pós-processamento. . . . . . . . . . . . . . . . . . .
6.23 Gráficos de expressão do grupo de biclusters pós-processado.
99
100
101
102
Lista de Tabelas
1.1
O código genético, da perspectiva do mRNA. Os codões
UUG, CUG, AUU, AUG e GUG funcionam também como
codões Start, ou seja, codões que assinalam o início da transcrição. Os codões UAA, UAG e UGA são codões Stop, que
indicam o fim da transcrição. Phe/F - Fenilalanina; Ser/S - Serina; Gln/Q - Glutamina; Cys/C - Cisteína; Leu/L - Leucina;
Pro/P - Prolina; Asn/N - Asparagina; Trp/W - Triptofano; Ile/I
- Isoleucina; Thr/T - Treonina; Lys/K - Lisina; Arg/R - Arginina; Met/M - Metionina; Ala/A - Alanina; Asp/D - Ácido
Aspártico; Gly/G - Glicina; Val/V - Valina; His/H - Histidina;
Glu/E - Ácido Glutâmico; Tyr/Y - Tirosina . . . . . . . . . . .
5
3.1
Matriz de dados de expressão genética. . . . . . . . . . . . .
20
4.1
Matriz de expressão genética discretizada com um alfabeto
binário {D, U}. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Matriz de expressão genética original (valores de expressão
reais). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Matriz de valores discretos (obtida a partir da matriz original da Tabela 4.2). Representa as variações dos valores de
expressão genética dos genes da experiência entre os sucessivos instantes temporais. Alfabeto: {D, N, U} . . . . . . . . .
q-clusters extraídos pelo algoritmo q-Clustering sobre a matriz de expressão da Tabela 4.3 com q = 7. . . . . . . . . . . .
Biclusters de instantes iniciais 15, 16 e 17 identificados no
q-cluster 551 da Tabela 4.4 com o padrão DNDUND. . . . . .
Biclusters de instantes iniciais 10, 14 e 15 identificados no
q-cluster 289 da Tabela 4.4 com o padrão UNUDNU. . . . . .
4.2
4.3
4.4
4.5
4.6
xi
40
42
42
43
45
46
Lista de Algoritmos
1
2
3
4
Algoritmo CDK-Means . . . . . . . . . . . . . . . . . .
Algoritmo D-Miner . . . . . . . . . . . . . . . . . . . . .
Algoritmo Divisão . . . . . . . . . . . . . . . . . . . . .
Algoritmo q-Clustering (fase 2: extracção de q-clusters)
xiii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
38
39
44
Acrónimos
ADN Ácido desoxirribonucleico (DNA - desoxyribonucleic acid)
ARN Ácido ribonucleico (RNA - ribonucleic acid)
mRNA RNA mensageiro
tRNA RNA transporte
rRNA RNA ribossómico
MS Mass Spectrometry (espectrometria de massa)
PCR Polymerase Chain Reaction (reacção polimerase em cadeia)
cDNA ADN complementar
IDE Integrated Development Environment
XML eXtended Markup Language
PNG Portable Network Graphics
GIF Graphics Interchange Format
JPG de JPEG - Joint Photographic Experts Group
SVG Scalable Vector Graphics
GNU GNU’s Not Unix
GPL General Public License
LGPL Lesser General Public License
xv
xvi
HTML Hypertext Markup Language
CSS Cascading Style Sheets
PDA Personal Digital Assistant
RPM Red Hat Package Manager
Acrónimos
Capítulo 1
Introdução
O presente capítulo apresenta uma introdução ao trabalho desenvolvido
durante a disciplina de Projecto II do 5o ano do curso de Engenharia Informática na Universidade da Beira Interior. Num primeiro momento, será
feita uma contextualização e motivação do projecto na área específica em
que se enquadra, a Bioinformática. Seguidamente, serão definidos os objectivos do projecto desenvolvido no âmbito da disciplina e, por último, a
estrutura e conteúdo do relatório.
1.1
Contexto
Todos os organismos vivos dependem de três tipos de moléculas: ADN,
ARN, e proteínas, embora existam outras, tais como os lípidos, que desempenham funções críticas, nomeadamente na manutenção da estrutura
celular. De uma maneira geral, o ADN de uma célula contém uma vasta
biblioteca que descreve o seu funcionamento. O ARN actua no transporte
de pequenos fragmentos desta biblioteca para diferentes locais dentro da
célula, nos quais a informação transportada é utilizada como modelo na
síntese de proteínas. Por sua vez, as proteínas formam enzimas que desempenham reacções bioquímicas, enviam sinais para outras células, compõem
os maiores componentes do nosso organismo (como a queratina na nossa
pele), e executam o trabalho real da célula.
A informação genética de cada organismo ou célula, que é transmitida
à descendência, está organizada em genes que, por sua vez, residem em
cromossomas (ver Figura 1.1). Os genes codificam as proteínas, elemen1
2
Introdução
tos essenciais para o desempenho das várias funções biológicas ao nível
celular. Cada gene pode codificar mais do que uma proteína.
Figura 1.1: Relação entre a célula, os cromossomas e o ADN. O ADN das células
eucarióticas encontra-se no núcleo, dividido em unidades estruturais (cromossomas). Os
cromossomas são formados por cadeias de ADN cujos segmentos codificam genes.
1.1 Contexto
1.1.1
3
ADN e ARN
O ADN, ou ácido desoxirribonucleico, é uma molécula simples composta
por um açúcar (um tipo comum de composto orgânico, neste caso uma
pentose, a desoxirribose), um grupo fosfato (contento o elemento fósforo)
e uma de quatro bases azotadas (A, T, G ou C). As ligações químicas que
ligam os nucleótidos no ADN são sempre as mesmas, de modo que a base
das moléculas de ADN é muito regular. São as bases A, T, G e C que
conferem a individualidade a cada molécula de ADN. O ADN tem uma
estrutura helicoidal dupla, em que cada cadeia é complementar à outra,
isto é, as cadeias emparelham-se pela ligação entre as suas bases azotadas
(pares de bases) complementares entre si. Esta complementaridade permite que, na presença de uma das cadeias da hélice, a estrutura da sua
complementar possa ser directamente reproduzida, facto que está na base
de todo o processo de replicação de ADN.
Quimicamente falando, o ARN, ou ácido ribonucleico, é muito semelhante ao ADN. As duas diferenças essenciais entre os dois tipos de ácidos
nucleicos são: não existe T no ARN - a base U (uracilo) semelhante toma
o seu lugar - e o componente de açúcar do ARN possui um átomo de
oxigénio adicional. Estas diferenças, aparentemente irrelevantes, têm um
impacto importante nas funções biológicas das duas moléculas. O ADN é
praticamente inerte e quase sempre de cadeia dupla, permitindo-lhe funcionar como um repositório estático de informação. O ARN, por outro
lado, é quimicamente mais activo, e encontra-se, geralmente, na forma de
cadeia simples. Como resultado, o ARN pode transportar pequenas mensagens desde o ADN até à maquinaria celular que fabrica as proteínas,
participando activamente em reacções químicas importantes.
Nos organismos eucariotas, um gene é tipicamente dividido em vários
fragmentos, exões, mas ainda assim produz uma proteína coerente (ver
Figura 1.2).
Para tal, é necessário retirar os intrões, segmentos que não codificadores, do ARN transcrito e concatenar os exões antes da entrada do ARN
mensageiro no ribossoma. Este processo de cortar e colar a versão ARN
do gene na versão ARN mensageiro que entra no ribossoma é designado
splicing e consiste num processo bastante complexo ao nível molecular.
4
Introdução
Figura 1.2: Representação de um gene na molécula de ADN e respectiva localização no
cromossoma. Exões (segmentos codificadores) e intrões (segmentos não codificadores).
1.1.2
Código genético
O código genético consiste na correspondência entre o alfabeto do ADN/ARN
e o alfabeto das proteínas. Enquanto o primeiro contém apenas 4 símbolos, correspondentes aos 4 diferentes nucleótidos, o segundo inclui 20,
correspondentes aos 20 aminoácidos que podem ser utilizados na construção das proteínas. Assim, cada conjunto de três nucleótidos consecutivos
de ADN/ARN (codão) é responsável pela codificação de um determinado
aminoácido numa proteína (ver Tabela 1.1).
1.1.3
Síntese de proteínas
A síntese de proteínas processa-se da seguinte forma: a RNA polimerase
(complexo proteico designado enzima), inicia a transcrição de um gene
copiando a sua sequência de bases para uma sequência de bases de ARN
(emparelhando uma base T de ADN com uma base A de ARN, uma base
A de ADN com uma base U de ARN e assim consecutivamente) designada RNA mensageiro ou mRNA (mais precisamente, este é o caso dos
procariotas; nos eucariotas, este modelo de ARN passa por um processo
de splicing, descrito acima, para formar o mRNA). Esta pequena molécula é então abordada por complexos moleculares de grandes dimensões,
os ribossomas, que lêem codões consecutivos e localizam os aminoácidos
correspondentes para inclusão na cadeia polipeptídica em crescimento. Os
1.1 Contexto
U
C
A
G
U
UUU (Phe/F)
UUC (Phe/F)
UUA (Leu/L)
UUG (Leu/L)
CUU (Leu/L)
CUC (Leu/L)
CUA (Leu/L)
CUG (Leu/L)
AUU (Ile/I)
AUC (Ile/I)
AUA (Ile/I)
AUG (Met/M)
GUU (Val/V)
GUC (Val/V)
GUA (Val/V)
GUG (Val/V)
5
C
UCU (Ser/S)
UCC (Ser/S)
UCA (Ser/S)
UCG (Ser/S)
CCU (Pro/P)
CCC (Pro/P)
CCA (Pro/P)
CCG (Pro/P)
ACU (Thr/T)
ACC (Thr/T)
ACA (Thr/T)
ACG (Thr/T)
GCU (Ala/A)
GCC (Ala/A)
GCA (Ala/A)
GCG (Ala/A)
A
UAU (Tyr/T)
UAC (Tyr/T)
UAA (’Ocre’)
UAG (’Âmbar’)
CAU (His/H)
CAC (His/H)
CAA (Gln/Q)
CAG (Gln/Q)
AAU (Asn/N)
AAC (Asn/N)
AAA (Lys/K)
AAG (Lys/K)
GAU (Asp/D)
GAC (Asp/D)
GAA (Glu/E)
GAG (Glu/E)
G
UGU (Cys/C)
UGC (Cys/C)
UGA (’Opala’)
UGG (Trp/W)
CGU (Arg/R)
CGC (Arg/R)
CGA (Arg/R)
CGG (Arg/R)
AGU (Ser/S)
AGC (Ser/S)
AGA (Arg/R)
AGG (Arg/R)
GGU (Gly/G)
GGC (Gly/G)
GGA (Gly/G)
GGG (Gly/G)
Tabela 1.1: O código genético, da perspectiva do mRNA. Os codões UUG, CUG, AUU,
AUG e GUG funcionam também como codões Start, ou seja, codões que assinalam o
início da transcrição. Os codões UAA, UAG e UGA são codões Stop, que indicam o
fim da transcrição. Phe/F - Fenilalanina; Ser/S - Serina; Gln/Q - Glutamina; Cys/C Cisteína; Leu/L - Leucina; Pro/P - Prolina; Asn/N - Asparagina; Trp/W - Triptofano; Ile/I Isoleucina; Thr/T - Treonina; Lys/K - Lisina; Arg/R - Arginina; Met/M - Metionina; Ala/A
- Alanina; Asp/D - Ácido Aspártico; Gly/G - Glicina; Val/V - Valina; His/H - Histidina;
Glu/E - Ácido Glutâmico; Tyr/Y - Tirosina
ribossomas são, na realidade, fábricas moleculares onde as proteínas são
fabricadas.
Para ajudar na localização do aminoácido específico para um dado codão, um tipo especial de ARN, o ARN transporte (tRNA) desempenha uma
função específica e elegante. Existem vinte tipos de tRNAs e vinte tipos
de aminoácidos. Cada tipo de aminoácido liga-se a um tRNA diferente.
As moléculas de tRNA são fragmentos de três bases (anti-codões) que são,
por sua vez, complementares aos codões do mRNA. Tal como no emparelhamento das bases de ADN, o anti-codão do tRNA emparelha com o
codão do mRNA correspondente, o que faz com que o aminoácido fique
livre para ser adicionado pelo ribossoma à cadeia polipeptídica. Assim
que o aminoácido é adicionado, o ribossoma desloca-se um codão para
6
Introdução
a direita e o processo repete-se. O processo de transformação do mRNA
numa proteína é designado tradução, pois traduz a informação do ARN
(escrita num alfabeto de quatro letras) numa proteína (escrita num alfabeto
de vinte letras). Todas as proteínas, incluindo as necessárias ao processo,
são fabricadas por este mesmo processo (ver Figura 1.3).
Figura 1.3: A síntese de proteínas e as funções do mRNA e tRNA.
Este fluxo de informação,
ADN -> transcrição -> ARN -> tradução ->proteína
é enfaticamente referido como o dogma central da biologia molecular.
1.2
Motivação
Como vimos, os processos biológicos que ocorrem no contexto celular, ao
longo do ciclo de vida de uma célula, são quase sempre mediados por proteínas, que desempenham tarefas específicas no decorrer desses mesmos
1.3 Objectivos
7
processos: formam enzimas que desempenham reacções bioquímicas, enviam sinais para outras células e fazem parte dos maiores componentes do
nosso organismo (como a queratina na nossa pele). As proteínas são por
sua vez codificadas por genes, sendo que um gene pode codificar várias
proteínas. O processo de transformação do código genético para o código
proteico envolve a transcrição de ADN em ARN. Assim, e sabendo que a
função do ADN é essencialmente de armazenamento de informação (até
pela sua estrutura estável e praticamente inerte), a concentração de ADN
na célula mantém-se sensivelmente constante ao longo do tempo, enquanto
que a de ARN varia consoante os processos biológicos que decorrem na
célula em cada momento.
É através da medição dessa concentração de mRNA nas células que os
investigadores procuram estabelecer uma relação entre o nível de expressão dos genes e os processos biológicos que ocorrem nas células, atribuir
funções específicas a cada gene estudado, identificar possíveis relações
entre genes e, finalmente, dar os primeiros passos na importante e complexa tarefa de inferência de redes de regulação genética (gene regulatory
networks).
1.3
Objectivos
O aparecimento de microarrays levou à necessidade de desenvolver ferramentas computacionais de apoio à análise de dados de expressão genética
(gene expression data). Como veremos em mais detalhe no Capítulo 2, os
microarrays permitem medir a resposta ou o nível de expressão (gene expression) de um elevado número de genes, potencialmente todos os genes
de um dado organismo, em determinadas condições experimentais. Estas condições podem corresponder à medição da expressão genética em
órgãos diferentes, em tecidos diferentes, ou até mesmo em indivíduos diferentes. Permitem ainda analisar, em simultâneo, o nível de expressão
dos genes como reacção a estímulos diferentes tais como utilização de drogas, existência ou não de determinada doença, ou observar a evolução da
expressão em diferentes instantes temporais em determinada condição de
teste.
A análise de dados de expressão genética provenientes de séries temporais (time-series gene expression data) tem como objectivo identificar processos biológicos relevantes que possam ser úteis para a identificação de
8
Introdução
redes de regulação genética (gene expression networks). De facto, a observação da evolução da expressão em diferentes instantes temporais pode ser
especialmente útil para a identificação de conjuntos de genes com comportamentos semelhantes em determinados instantes temporais contíguos
(padrões de expressão) e posteriormente identificar potenciais processos
biológicos relevantes.
Neste contexto, as técnicas de biclustering têm-se revelado particularmente adequadas ao problema visto permitirem identificar subgrupos de
genes co-regulados em subgrupos de condições (biclusters) que correspondem a potenciais processos biológicos relevantes. Os biclusters considerados biologicamente significativos, identificam de facto módulos regulatórios (conjuntos de genes co-regulados pelos mesmos factores de transcrição
que partilham a mesma função biológica) e poderão depois ser usados na
inferência de redes de regulação genética.
O problema de biclustering é NP-completo. Este facto leva a que os
algoritmos existentes na literatura utilizem abordagens heurísticas para
obter soluções sub-óptimas usando recursos computacionais razoáveis.
Existem também abordagens exaustivas que usam restrições, normalmente
no tamanho dos biclusters reportados.
No caso das séries temporais a restrição das condições de um bicluster a
instantes de tempo contíguos (que identificam um processo biológico com
princípio e fim bem definidos) permite desenvolver algoritmos eficientes e
calcular a solução óptima. No entanto, e apesar da relevância da identificação de módulos regulatórios para a biologia/medicina utilizando este tipo
de dados, apenas temos conhecimento de cinco algoritmos na literatura
que abordam o problema de biclustering em dados de expressão genética
provenientes de séries temporais de expressão de forma directa [13] [14]
[23] [9] [19], isto é, têm como objectivo identificar biclusters formados por
um conjunto de genes com expressão coerente num conjunto contíguo de
instantes temporais.
O projecto desenvolvido ao longo dos dois semestres lectivos pretendeu
desenvolver uma ferramenta que permita a integração destes algoritmos e a
respectiva visualização e análise de resultados. Embora existam já algumas
ferramentas que integrem algoritmos de biclustering aplicados a dados de
expressão genética em geral, o desenvolvimento de uma ferramenta para o
caso específico das séries temporais, dada a particularidade dos algoritmos
usados e dos resultados obtidos, é relevante para a comunidade científica.
Apresentamos seguidamente o plano de trabalho definido para o pro-
1.3 Objectivos
9
jecto do segundo semestre, revisto e adaptado desde a proposta de projecto apresentada inicialmente para o desenvolvimento da ferramenta
BiGGEsTS - Biclustering Gene Expression Time-Series.
1. Reformulação e optimização do módulo de carregamento de dados.
2. Implementação do módulo de pós-processamento (filtragem e ordenação dos biclusters resultantes da execução dos algoritmos segundo
diferentes critérios).
3. Implementação do módulo de download de ficheiros a partir do site
da Gene Ontology.
4. Integração do algoritmo CC-TSB-Biclustering na ferramenta.
5. Integração e criação de suporte para biclusters e grupos de biclusters
com padrões de expressão simétricos (anti-correlation) e/ou com atrasos (time-lags), nomeadamente ao nível da aplicação de algoritmos
de biclustering e dos gráficos de expressão.
6. Reimplementação dos algoritmos de clustering hierárquico da ferramenta Cluster 3.0 [6] [5] e desenvolvimento do módulo de visualização de dendrogramas.
7. Leitura e análise de dois algoritmos de biclustering existentes na literatura para séries temporais de expressão genética [9] [19] para
decisão sobre a sua implementação e integração na ferramenta. Ênfase na análise de tipos de biclusters identificados e complexidade
computacional.
8. Implementação de threads de execução autónoma para as funcionalidades mais exigentes em termos de tempo, com as respectivas barras
de progresso.
9. Implementação dos módulos de gestão de sessões e de informação.
10. Criação de executáveis nativos e instaladores para os sistemas operativos Windows, Linux e Mac OS X. Realização de testes para estabelecimento dos pré-requisitos do software, benchmarking e detecção
de problemas. Produção da documentação para o utilizador e programador, bem como da licença de utilização do software.
10
Introdução
11. Criação de uma imagem (cores, logótipo) para a ferramenta e desenvolvimento de um site para disponibilização do BiGGEsTS à comunidade científica.
1.4
Conteúdo do Relatório
Este relatório é constituído por sete capítulos com a seguinte estrutura:
Capítulo 1 - Introdução :
Contextualização e motivação do projecto, breve descrição do projecto e dos seus objectivos e estrutura do relatório.
Capítulo 2 - Microarrays e Dados de Expressão :
O conceito de microarray. Introdução às experiências com microarrays
e aos dados de expressão genética.
Capítulo 3 - Biclustering :
Algoritmos de biclustering. Distinção das várias classes de algoritmos
existentes. Biclusters em matrizes de expressão genética e biclusters
em séries temporais de expressão genética.
Capítulo 4 - Trabalho Relacionado :
Breve resumo sobre os algoritmos integrados na aplicação. Análise
compreensiva de novos algoritmos de biclustering para séries temporais de expressão genética.
Capítulo 5 - A Ferramenta BiGGEsTS :
Análise das várias fases de desenvolvimento da ferramenta BiGGEsTS:
modelação, implementação e produção do software.
Capítulo 6 - Estudo de Caso :
Demonstração da utilização da ferramenta BiGGEsTS para análise de
dados reais de séries temporais de expressão genética.
Capítulo 7 - Conclusões e Trabalho Futuro :
Apresentação das conclusões e propostas para trabalho futuro.
Adicionalmente são incluídos os seguintes conteúdos num CD-ROM
distribuído com o presente relatório:
Diagramas de Classes da Ferramenta BiGGEsTS
Capítulo 2
Microarrays e Dados de Expressão
Como vimos anteriormente, é através da medição da quantidade de mRNA
nas células em condições experimentais específicas que podemos estabelecer relações entre os níveis de expressão dos vários genes de um organismo,
de forma a identificar padrões de actividade semelhantes. Neste capítulo
pretendemos introduzir o conceito de microarray e explicar de que forma
este componente pode ser utilizado em experiências de carácter biológico
para medir o nível de expressão dos genes numa determinada condição
experimental [22]. Faremos também uma referência às várias fases das experiências com microarrays [21] e, por último, uma clarificação ao conceito
de dados de expressão genética e à sua organização em matrizes [12], com
vista a uma análise posterior.
2.1
Microarrays
A medição de mRNA é efectuada em experiências biológicas com microarrays, também designados chips de ADN ou chips de genes. As experiências
com microarrays envolvem seis fases essenciais:
1. Selecção dos elementos de prova (probes): oligonucleótidos (fragmentos de ADN de cadeia simples com cerca de 5 a 50 nucleótidos),
cDNA (ADN complementar, obtido através da remoção dos intrões
do ADN original), cromossomas, genoma completo de um determinado organismo;
11
Microarrays e Dados de Expressão
12
2. Fabricação do chip (processo através do qual os elementos de prova
são colocados no chip): fotolitografia, pipetagem, piezoelectricidade;
3. Etiquetagem da amostra por fluorescência: ARN, mRNA, cDNA;
4. Experiência: hibridação, ligase, adição de bases, espectrometria de
massa (MS - mass spectrometry), electroforese, fluxocitometria, PCR
(polymerase chain reaction);
5. Leitura ou medição: fluorescência, espectrometria de massa, electroforese;
6. Preparação e análise dos dados: controlo robótico, processamento
de imagem, sistemas de gestão de bases de dados, bioinformática,
mineração de dados, visualização.
2.1.1
O que é exactamente um microarray de ADN?
Um microarray de ADN é um suporte sólido de dimensões reduzidas, no
qual são afixadas sequências de milhares de genes, em posições específicas.
O suporte é geralmente uma lâmina de vidro ou silicone microscópica, ou
uma membrana de nylon. O ADN é impresso, pontilhado ou sintetizado
directamente no suporte (ver Figura 2.1). Cada sequência de ADN, correspondente a um gene, é colocada num ponto específico do suporte. Os
vários pontos formam uma matriz, cuja disposição ordenada e fixa permite, posteriormente, saber qual a sequência de ADN que se encontra em
cada uma das posições. Os pontos podem ser constituídos por sequências
de ADN, cDNA ou oligonucleótidos.
2.1.2
Passos básicos de uma experiência com microarrays
Como é possível extrair informação sobre uma determinada condição patológica a partir de um vidro de dimensões reduzidas ou de uma placa de
silicone contendo milhares de sequências de genes?
O processo é baseado na hibridação de provas de ADN (probes), uma
técnica que usa moléculas de ácido nucleico identificadas por fluorescência como provas móveis para identificar moléculas complementares, isto
é, moléculas de ADN ou ARN cuja sequência de bases emparelha com a
2.1 Microarrays
13
sequência da molécula de prova. Quando duas sequências complementares se encontram, tais como o ADN imobilizado e a prova de ADN, cDNA
ou mRNA, dá-se uma ligação entre elas, ou hibridação (ver Figura 2.1).
Figura 2.1: As fases de uma experiência com microarrays.
Consideremos duas células: uma célula de tipo 1, saudável, e uma
célula de tipo 2, doente. Suponhamos que ambas contêm um conjunto
de quatro genes idênticos, A, B, C e D. O objectivo é determinar o perfil de expressão destes quatro genes nos dois tipos de células. Para isso,
procede-se ao isolamento do mRNA de cada um dos tipos de células, que
se usa depois como modelo para produzir cDNA, ao qual se acrescenta
um composto fluorescente. As fluorescências usadas têm cores diferentes, para que as amostras possam ser distinguidas em fases posteriores.
As amostras marcadas são então misturadas e incubadas num microarray
contendo os genes A, B, C e D imobilizados. As moléculas fluorescentes
ligam-se aos vários pontos do array, que correspondem aos genes expres-
14
Microarrays e Dados de Expressão
sos em cada célula. Os genes consideram-se expressos (up-expressed) ou
regulados (up-regulated) se, durante a experiência, as sequências de ADN
que lhes correspondem se ligarem por hibridação ao ADN-alvo, permitindo inferir que esses genes estão a contribuir para a realização de uma
tarefa biológica específica. Se a sequência de um determinado gene não
hibrida com nenhuma sequência do ADN-alvo, então estamos perante o
caso em que o gene não está expresso (down-expressed) ou não está regulado
(down-regulated). O nível de expressão é determinado pela concentração
relativa de mRNA na célula, pelo que o valor a partir do qual se considera
que um determinado gene está expresso ou não varia consoante a técnica
de análise utilizada posteriormente.
Após a finalização do passo de hibridação, o microarray é introduzido
num "leitor"ou scanner que contém alguns lasers, um microscópio especial
e uma câmara. As marcações fluorescentes são excitadas pelo laser e o
microscópio e a câmara trabalham em conjunto para criar uma imagem
digital do array. Estes dados são posteriormente armazenados em suporte
digital e analisados por software específico que calcula a razão entre as
fluorescências vermelha e verde, através da análise da sua imagem digital.
Para calcular a razão, o programa cria então uma tabela que contém as taxas
de intensidade de fluorescência vermelho-verde para cada um dos pontos
do array. Por exemplo, para o cenário acima descrito, poder-se-á concluir
que ambos os tipos de células expressavam o gene A ao mesmo nível, que a
célula 1 expressava mais o gene B, a célula 2 expressava mais o gene C e que
nenhuma das células expressava o gene D. É necessário lembrar que este
é apenas um exemplo simples que usamos para demonstrar os pontoschave do desenho experimental. Algumas experiências de microarrays
podem conter até 30 ou 40 mil pontos, ou mesmo representar um genoma
completo. Assim sendo, os dados gerados a partir de um simples array
podem aumentar de forma significativa.
2.1.3
As cores de um microarray
Geralmente, as cores resultantes das experiências com microarrays são as
seguintes (ver Figura 2.2):
Verde - representa o ADN de controlo, em que o ADN ou cDNA deriva de
tecido normal hibridado com o ADN-alvo.
Vermelho - representa o ADN de amostra, em que o ADN ou cDNA deriva
2.2 Dados de expressão genética
15
de tecido doente hibridado com o ADN-alvo.
Amarelo - representa uma combinação de ADN de controlo e de amostra,
em que ambos hibridam igualmente com o ADN-alvo.
Preto - representa áreas em que nem o ADN de controlo nem o de amostra
hibridam com o ADN-alvo.
Figura 2.2: Cores visíveis numa imagem digital de um microarray.
Cada ponto do array está associado a um gene particular. Cada cor
do array representa tecido saudável (controlo) ou tecido doente (amostra).
Dependendo do tipo de array usado, a localização e intensidade da cor
identifica se o gene, ou a mutação, está presente quer no ADN de controlo,
quer no ADN da amostra. Fornece também uma estimativa do nível de
expressão do(s) gene(s) no ADN da amostra e no ADN de controlo.
2.2
Dados de expressão genética
Os dados obtidos nas experiências com microarrays correspondem, como
observámos, ao nível de expressão de um elevado número de genes, por
vezes todos os genes de um determinado organismo, num determinado número de amostras (condições experimentais) [1]. As amostras podem corresponder a instantes temporais ou condições ambientais distintas. Noutros casos, podem pertencer a órgãos, tecidos - tecidos saudáveis e doentes,
por exemplo - ou indivíduos distintos. A simples visualização dos dados
provenientes das experiências com microarrays - dados de expressão genética (gene expression data) - é, só por si, complexa, mas a extracção de
conhecimento biológico relevante representa um desafio ainda maior [10].
16
Microarrays e Dados de Expressão
Os dados de expressão genética são dispostos numa matriz de expressão genética (gene expression matrix), em que cada gene corresponde a uma
linha e cada condição a uma coluna. Cada elemento da matriz contém o
nível de expressão de um gene numa determinada condição e é representado por um valor real, geralmente o logaritmo da quantidade relativa do
mRNA do gene numa condição experimental específica.
As matrizes de expressão genética têm sido analisadas extensivamente
em duas dimensões: a dimensão dos genes e a dimensão das condições.
Estes dois tipos de análise correspondem, respectivamente, a identificar
os padrões de expressão dos genes comparando as linhas da matriz, e a
identificar os padrões de expressão das amostras comparando as colunas
da matriz.
Entre os objectivos da análise de dados de expressão genética (gene
expression data analysis), são de salientar os seguintes:
1. Agrupamento de genes de acordo com a sua expressão em diversas
condições;
2. Classificação de um novo gene, dada a expressão de outros genes,
cuja classificação é conhecida;
3. Agrupamento de condições de acordo com a expressão de um determinado número de genes;
4. Classificação de um novo gene, dada a expressão dos genes nessa
condição experimental;
5. Identificação de mecanismos de regulação genética (regulatory mechanisms) e inferência de redes de regulação genética (regulatory networks).
Capítulo 3
Biclustering
O presente capítulo tem como objectivo introduzir o conceito de algoritmos
de biclustering, apresentar um breve resumo dos tipos de algoritmos de
biclustering existentes e da sua aplicação, quer no âmbito geral dos dados
de expressão genética [12], quer no caso específico das séries temporais de
expressão genética [13].
3.1
Conceito de Biclustering
As técnicas de clustering (agrupamento) podem e têm sido largamente usadas para agrupar genes ou condições e, desta forma, contribuir também
para a classificação de novos genes ou novas amostras (condições). Contudo, a aplicação de algoritmos de clustering a dados de expressão genética
depara-se com uma dificuldade acrescida. Na base desta afirmação está o
facto de muitos padrões de activação serem comuns a um grupo de genes
apenas em determinadas condições experimentais e não na totalidade das
condições analisadas. Para além disso, o número de condições experimentais disponível para análise é reduzido (na ordem de escassas dezenas),
comparativamente ao número de genes (na ordem dos milhares), o que
invalida a utilização de técnicas de redução do espaço das características
(feature selection), normalmente usadas em conjunto com os algoritmos de
clustering. De facto, o nosso entendimento geral de processos celulares
leva-nos a esperar que os subconjuntos de genes sejam co-regulados ou
co-expressos apenas em algumas condições experimentais e que se comportem quase independentemente noutras condições.
17
Biclustering
18
A descoberta destes padrões locais de expressão, em oposição aos padrões globais encontrados pelos algoritmos de clustering, pode ser a chave
para encontrar mecanismos regulatórios que, caso contrário, passariam
despercebidos. Assim, torna-se desejável ir para além do paradigma de
clustering e desenvolver abordagens distintas, capazes de revelar padrões
locais em dados de microarrays [2].
O termo biclustering foi introduzido pela primeira vez por Cheng e
Church [3] na análise de dados de expressão genética. Refere-se a uma
classe distinta de algoritmos de clustering que aplica clustering simultâneo
a linhas e colunas. Os algoritmos de biclustering têm sido propostos e
utilizados também noutras áreas de aplicação. Vários nomes, tais como
co-clustering, clustering bidimensional, subspace clustering, entre outros, são
usados frequentemente na literatura para referir a mesma formulação deste
problema. Uma das primeiras técnicas de biclustering foi o algoritmo de
clustering directo (direct clustering) introduzido por Hartigan [8], também
conhecido como clustering em bloco [15] (block clustering), embora na prática este tipo de algoritmos não tenha sido explorado até aos anos 2000.
3.1.1
Clustering vs biclustering
As técnicas de clustering permitem extrair clusters de genes ou clusters de
condições, quando aplicadas sobre as linhas ou as colunas de uma matriz
de dados, respectivamente, produzindo modelos globais. Cada gene de
um cluster de genes é definido usando todas as condições da experiência. De forma semelhante, cada condição de um cluster de condições é
caracterizada pela actividade de todos os genes envolvidos na experiência.
Os algoritmos de biclustering, por sua vez, aplicam clustering simultaneamente nas duas dimensões (linhas e colunas), produzindo modelos locais.
Num bicluster cada gene é seleccionado usando apenas um subconjunto das
condições e cada condição é seleccionada usando apenas um subconjunto
de genes. O objectivo das técnicas de biclustering consiste em identificar
grupos de genes que apresentam padrões de actividade semelhantes num
determinado subconjunto de condições experimentais. Assim, as técnicas
de biclustering são mais adequadas para quando uma ou mais das seguintes
situações ocorrem:
1. Apenas um reduzido número de genes participa num processo celular de interesse.
3.2 Definições e Formulação do Problema
19
2. Um processo celular interessante só permanece activo num determinado subconjunto das condições experimentais.
3. Cada gene pode participar em diversos processos biológicos que
podem ou não estar co-activos em todas as condições experimentais.
Por estas razões, os algoritmos de biclustering devem identificar grupos
de genes e condições obedecendo às seguintes restrições:
1. Um cluster de genes deve ser definido apenas em relação a um subconjunto das condições.
2. Um cluster de condições deve ser definido apenas em relação a um
subconjunto de genes.
3. Os clusters não devem ser exclusivos e/ou exaustivos: um gene/condição
pode pertencer a mais do que um cluster (ou mesmo a nenhum) e ser
agrupado(a) usando um subconjunto de condições/genes.
Adicionalmente, a robustez dos algoritmos de biclustering é particularmente relevante devido a duas características adicionais dos sistemas
em estudo. A primeira é a complexidade inerente aos processos de regulação genética que requer ferramentas de análise poderosas. A segunda
característica diz respeito ao nível de ruído introduzido nas experiências
de expressão genética, que torna a utilização de ferramentas inteligentes,
e tão eficientes quanto possível, indispensável.
3.2
Definições e Formulação do Problema
A maioria das aplicações que utilizam algoritmos de biclustering lida com
matrizes de expressão genética (ver Tabela 3.1). Existem contudo muitas
outras aplicações para estes algoritmos. Por esta razão, consideraremos o
caso geral de uma matriz de dados A, com um conjunto de linhas R e um
conjunto de colunas C, em que o elemento Ai j corresponde a um valor que
representa a relação entre a linha i e a coluna j. Tal matriz A, com |R| linhas
e |C| colunas, é definida pelo seu conjunto de linhas, R = {r1 , ..., r|R| } e pelo
seu conjunto de colunas C = {c1 , ..., c|C| }. Usaremos (R, C) para denotar a
matriz A. Considerando que I ⊆ R e J ⊆ C são subconjuntos de linhas e
colunas, respectivamente, AIJ = (I, J) denota a submatriz de A que contém
Biclustering
20
apenas os elementos Aij que pertencem à submatriz com um conjunto de
linhas I e um conjunto de colunas J.
Gene 1
Gene ...
Gene i
Gene ...
Gene |R|
Condição 1
A11
...
Ai1
...
A|R|1
...
...
...
...
...
...
Condição j
A1j
...
Aij
...
A|R| j
...
...
...
...
...
...
Condição |C|
A1|C|
...
Ai|C|
...
A|R||C|
Tabela 3.1: Matriz de dados de expressão genética.
Dada a matriz A, assim definida, definimos um cluster de linhas como
um subconjunto de linhas que exibe um comportamento semelhante em
todo o conjunto de colunas. Isto significa que um cluster de linhas AIC =
(I, C) é um subconjunto de linhas definido sobre todo o conjunto de colunas
C em que I = {i1 , ..., ik } é um subconjunto de linhas (I ⊆ R e k ≤ |C|). Um
cluster de linhas (I, C) pode assim ser definido como uma submatriz de A
com k linhas por |C| colunas.
Analogamente, um cluster de colunas é um subconjunto de colunas
que exibem um comportamento semelhante em todo o conjunto de linhas.
Um cluster de colunas ARJ = (R, J) é um subconjunto de colunas definido
sobre todo o conjunto de linhas R, onde J = { j1 , ..., js } é um subconjunto
de colunas (J ⊆ C e s ≤ |C|). Um cluster de colunas (R, J) pode ser assim
definido como uma submatriz A com |R| linhas por s colunas.
Um bicluster é um subconjunto de linhas que exibem um comportamento semelhante em todo o subconjunto de colunas e vice-versa. O
bicluster AIJ = (I, J) é, então, um subconjunto de linhas e colunas em que
I = {i1 , ..., ik } é um subconjunto de linhas (I ⊆ |R| e k ≤ |C|), e J = { j1 , ..., js }
é um subconjunto de colunas (J ⊆ C e s ≤ |C|). Um bicluster (I, J) pode ser
definido como uma submatriz de A com k linhas por s colunas.
O problema específico endereçado pelos algoritmos de biclustering pode
agora ser definido. Dada uma matriz de dados, A, pretendemos identificar
um conjunto de biclusters Bk = (Ik , Jk ) tal que cada bicluster Bk satisfaça
algumas características específicas de homogeneidade.
3.3 Complexidade do Problema
3.2.1
21
Grafos pesados bipartidos e matrizes de dados
Pode-se estabelecer uma relação interessante entre as matrizes de dados e
a teoria de grafos. Uma matriz de dados pode ser vista como um grafo
bipartido com pesos. Um grafo G = (V, E), em que V é o conjunto de
vértices e E o conjunto de arestas, é designado bipartido se os seus vértices
podem ser separados em dois conjuntos, C1 e C2 , tais que todaS
a aresta em
E tem exactamente um vértice em C1 e o outro em C2 : V = C1 C2 . Nesta
ordem de ideias, a matriz de dados A = (R, C) pode ser vista como um
grafo bipartido com pesos onde cada nodo ni ∈ R corresponde a uma linha
e cada nodo n j ∈ C corresponde a uma coluna. A aresta entre o nodo ni
e o nodo n j tem um peso Ai j , denotando o elemento da matriz na posição
de intersecção entre a linha i e a coluna j (o nível de activação, no caso das
matrizes de expressão genética).
Esta relação entre as matrizes e a teoria de grafos está na base de diversas
abordagens interessantes à análise de dados de expressão baseadas em
algoritmos de grafos.
3.3
Complexidade do Problema
Embora a complexidade do problema de biclustering possa depender da
sua formulação exacta e, mais especificamente, da função de mérito (merit
function, fitness function) usada para avaliar a qualidade de um determinado
bicluster, quase todas as variantes interessantes deste problema são NPcompletas.
Na sua forma mais simples, a matriz de dados A é uma matriz binária,
em que cada elemento Ai j toma o valor 0 ou 1. Neste caso, um bicluster
corresponde a uma biclique no grafo bipartido que lhe corresponde. Encontrar um bicluster de tamanho máximo é, então, equivalente a encontrar
a biclique com o maior número de arestas num grafo bipartido, o que constitui um problema NP-completo [16]. Em casos mais complexos, em que
os valores numéricos reais da matriz A são tomados em consideração para
determinar a qualidade de um bicluster, teremos uma complexidade que
não pode, necessariamente, ser inferior a esta, uma vez que, de um modo
geral, os problemas complexos podem também ser usados para resolver as
versões mais restritivas do problema conhecido como NP-completo. Neste
contexto, a grande maioria dos algoritmos propostos para o problema de
Biclustering
22
biclustering utiliza abordagens heurísticas, em muitos casos precedidas por
um passo de normalização aplicado à matriz de dados de forma a evidenciar os padrões de interesse. Algumas técnicas evitam as abordagens
heurísticas, usando a enumeração exaustiva de biclusters, normalmente
com restrições que envolvem o seu tamanho.
3.4
Dimensões da Análise
Nas secções que se seguem apresentamos uma classificação dos algoritmos
de biclustering de acordo com as quatro dimensões de análise apresentadas
por Madeira e Oliveira [12]:
• O tipo de biclusters que permitem encontrar.
• A estrutura do(s) bicluster(s) produzido(s).
• O algoritmo específico usado para identificar cada bicluster.
• O domínio de aplicação de cada algoritmo.
3.4.1
Tipo de bicluster
Um dos critérios para avaliar um algoritmo de biclustering envolve a identificação do tipo de biclusters que o algoritmo permite encontrar. Madeira
e Oliveira identificam quatro classes essenciais (ver Figura 3.4.1):
1. Biclusters com valores constantes.
2. Biclusters com valores constantes em linhas ou colunas.
3. Biclusters com valores coerentes.
4. Biclusters com evoluções coerentes.
As três primeiras classes analisam directamente os valores numéricos das matrizes de dados e tentam encontrar subconjuntos de linhas e
subconjuntos de colunas com comportamentos semelhantes. Estes comportamentos podem ser observados nas linhas, nas colunas, ou em ambas
as dimensões da matriz de dados, como nas Figuras 3.1(a), 3.1(b), 3.1(c),
3.1(d) e 3.1(e). A quarta classe de algoritmos engloba os algoritmos que
3.4 Dimensões da Análise
23
1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0
1.0 2.0 3.0 4.0
1.0 2.0 5.0 0.0
1.0 2.0 0.5 1.5
1.0 1.0 1.0 1.0
2.0 2.0 2.0 2.0
1.0 2.0 3.0 4.0
2.0 3.0 6.0 1.0
2.0 4.0 1.0 3.0
1.0 1.0 1.0 1.0
3.0 3.0 3.0 3.0
1.0 2.0 3.0 4.0
4.0 5.0 8.0 3.0
4.0 8.0 2.0 6.0
1.0 1.0 1.0 1.0
4.0 4.0 4.0 4.0
1.0 2.0 3.0 4.0
5.0 6.0 9.0 4.0
3.0 6.0 1.5 4.5
(a)
(b)
(c)
(d)
(e)
S1 S1 S1 S1
S1 S1 S1 S1
S1 S2 S3 S4
70
13
19
10
S1 S1 S1 S1
S2 S2 S2 S2
S1 S2 S3 S4
49
40
49
35
S1 S1 S1 S1
S3 S3 S3 S3
S1 S2 S3 S4
40
20
27
15
S1 S1 S1 S1
S4 S4 S4 S4
S1 S2 S3 S4
90
15
20
12
(f)
(g)
(h)
(i)
(j)
Figura 3.1: Diferentes tipos de biclusters. (a) bicluster constante; (b) linhas constantes;
(c) colunas constantes; (d) valores coerentes - modelo aditivo; (e) valores coerentes modelo multiplicativo; (f) evolução global coerente; (g) evoluções coerentes nas linhas;
(h) evoluções coerentes nas colunas; (i) evoluções coerentes nas colunas; (j) evoluções
coerentes em linhas e colunas
procuram comportamentos coerentes, independentemente dos valores numéricos exactos na matriz de dados. Assim, os biclusters com evoluções
coerentes vêem os elementos da matriz de dados como símbolos. Estes
símbolos podem ser puramente nominais, como nas Figuras 3.1(f), 3.1(g)
e 3.1(h); podem corresponder a uma determinada ordem, como na Figura
3.1(i); ou representar alterações positivas e negativas em relação a um valor
normal, como na Figura 3.1(j).
No caso dos dados de expressão genética, os biclusters constantes revelam subconjuntos de genes com valores de expressão semelhantes num determinado subconjunto de condições. Um bicluster com linhas constantes
identifica um subconjunto de genes com valores de expressão semelhantes
num determinado subconjunto de condições, permitindo que os níveis de
expressão sejam diferentes de gene para gene. De forma semelhante, um
bicluster com colunas constantes identifica um subconjunto de condições
no qual um conjunto de genes apresenta valores de expressão semelhantes
assumindo que os seus valores de expressão podem variar de condição
para condição. Contudo, podemos estar interessados em identificar relações mais complexas entre os genes e as condições analisando directa ou
indirectamente os valores numéricos.
Biclustering
24
Assim, um bicluster com valores coerentes identifica um subconjunto
de genes e condições com valores coerentes nas linhas e colunas da matriz
de dados. Por outro lado, identificar um bicluster com evoluções coerentes
pode ser útil se estivermos interessados em encontrar um subconjunto
de genes que estão regulados acima ou abaixo do normal (up-regulated,
down-regulated) num subconjunto de condições sem ter em conta os seus
valores de expressão reais; ou se estivermos interessado em identificar um
subconjunto de condições que têm os mesmos efeitos ou efeitos opostos
num subconjunto de genes.
De acordo com as propriedades específicas de cada problema, um ou
mais destes diferentes tipos de biclusters é, geralmente, considerado interessante. Para além disso, a função de mérito utilizada para avaliar a
qualidade dos biclusters encontrados deve ser a mais adequada, de acordo
com o tipo de biclusters pretendido. A selecção da função de mérito está
fortemente relacionada com as características dos biclusters que o algoritmo
pretende encontrar. A grande maioria dos algoritmos aplicam clustering
simultâneo em ambas as dimensões da matriz de dados, de forma a encontrar biclusters das quatro classes que mencionámos anteriormente. Existem
também abordagens de clustering de duas vias (two-way clustering) que
usam clustering de uma via (one-way clustering) para produzir clusters em
cada uma das duas dimensões da matriz de dados separadamente. Os
resultados unidimensionais são então combinados para produzir subgrupos de linhas e colunas cujas propriedades nos permitem considerar o
resultado final como biclustering. O tipo de biclusters produzido por estes
algoritmos depende, então, da distância ou medida de similaridade usada
pelos algoritmos de clustering de uma via.
3.4.2
Estrutura do bicluster
Os algoritmos de biclustering assumem que existe apenas um bicluster na
matriz, tal como na Figura 3.2(a), ou partem do princípio que a matriz
contém k biclusters, em que k é o número de biclusters que se esperam identificar, definido previamente. Enquanto a maioria dos algoritmos assume a
existência de vários biclusters, existem outros que apenas pretendem identificar um. Sendo assim, embora estes algoritmos possam identificar mais
do que um bicluster, o bicluster que resulta da execução do algoritmo é
geralmente o melhor, de acordo com um determinado critério.
3.4 Dimensões da Análise
(a)
25
(b)
(f)
(c)
(g)
(d)
(h)
(e)
(i)
Figura 3.2: Estrutura dos biclusters. (a) único; (b) exclusivos; (c) em xadrez; (d) linhas
exclusivas; (e) colunas exclusivas; (f) não sobrepostos com estrutura em árvore; (g) não
sobrepostos e não exclusivos; (h) sobrepostos com estrutura hierárquica; (i) sobrepostos e
arbitrariamente posicionados.
Quando o algoritmo de biclustering assume a existência de vários biclusters na matriz de dados, os biclusters identificados podem ter as seguintes
estruturas (ver Figura 3.4.2):
1. Biclusters de linhas ou colunas exclusivas (blocos rectangulares diagonais após o reordenamento de linhas e colunas).
2. Biclusters não sobrepostos com uma estrutura em xadrez.
3. Biclusters de linhas exclusivas.
4. Biclusters de colunas exclusivas.
5. Biclusters não sobrepostos com estrutura em árvore.
6. Biclusters não sobrepostos e não exclusivos.
7. Biclusters sobrepostos com estrutura hierárquica.
8. Biclusters sobrepostos com posicionamento arbitrário.
Biclustering
26
3.4.3
Objectivos dos algoritmos de biclustering
Os algoritmos de biclustering podem ter dois tipos de objectivos: identificar
um bicluster ou identificar um conjunto de biclusters. Algumas abordagens
procuram identificar um bicluster de cada vez. Outras permitem descobrir um conjunto de biclusters em cada aplicação. Existem também alguns
algoritmos que fazem a identificação de biclusters em simultâneo, isto é,
descobrem todos os biclusters com uma única aplicação. Dada a complexidade do problema, têm sido usadas diversas abordagens:
1. Combinação iterativa de clustering em linhas e colunas (iterative row
and column clustering combination).
2. Divisão e conquista (divide and conquer).
3. Pesquisa gulosa (greedy search).
4. Enumeração exaustiva de biclusters (exhaustive bicluster enumeration).
5. Identificação de parâmetros de uma dada distribuição (distribution
parameter identification).
A forma mais directa para identificar biclusters é a aplicação de algoritmos de biclustering às linhas e colunas da matriz de dados separadamente
e, posteriormente, combinar os resultados através de um método iterativo
que combine as disposições de ambos os clusters. Vários algoritmos usam
esta ideia de combinação iterativa de clustering em linhas e colunas. Outras
técnicas utilizam a abordagem de divisão e conquista: dividem o problema
em vários sub-problemas semelhantes ao original, mas de dimensões mais
reduzidas, resolvem os sub-problemas recursivamente e depois combinam
as soluções para criar uma solução global para o problema original [4]. Um
grande número de métodos aplica a pesquisa gulosa. Esta abordagem consiste em efectuar escolhas óptimas para os casos locais, na esperança de
que a optimização local leve a uma solução global aceitável [4]. Alguns
autores propõem métodos que fazem uma enumeração exaustiva de biclusters, bem como algumas técnicas para acelerar o processo, nomeadamente
através da restrição da dimensão dos biclusters que devem ser identificados. O último tipo de abordagem faz a identificação de parâmetros de uma
dada distribuição. Para isso, assume que os biclusters são gerados segundo
um determinado modelo estatístico e procura identificar os parâmetros
3.5 Aplicações de Biclustering
27
da distribuição que aproximam da melhor forma a distribuição observada
nos dados reais, minimizando iterativamente um determinado critério de
qualidade.
3.5
Aplicações de Biclustering
A técnica de biclustering pode, em geral, ser aplicada quando os dados
que se pretendem analisar tomam a forma de uma matriz A de valores
reais, em que o conjunto de valores Ai j representa a relação entre as linhas
i e as colunas j, e o objectivo é identificar subconjuntos de linhas/colunas
com determinadas propriedades de coerência num dado subconjunto de
colunas/linhas.
A maioria das aplicações de biclustering em Biologia/Medicina utiliza
dados de expressão genética. Contudo, as técnicas de biclustering podem
ser interessantes na análise de outro tipo de dados biológicos. Exemplo
disso é a aplicação destes algoritmos a dados da indústria farmacêutica,
dados nutricionais, entre outros.
Outras áreas aplicacionais de interesse e onde esta técnica tem sido
aplicada são: a pesquisa de informação (information retrieval) e a mineração
de texto (text mining); sistemas de recomendação (recommendation systems,
colaborative filtering), marketing aplicado e estudos de mercado; pesquisas
em bases de dados e mineração de dados (data mining).
3.6
Biclustering em Séries Temporais
Em séries temporais de expressão genética, as condições da matriz de dados correspondem a instantes temporais consecutivos. Dada a natureza
dos dados em análise, a tarefa de isolar actividades coerentes entre genes
num determinado subconjunto de condições pode ser simplificada pela
restrição a biclusters de colunas contíguas (instantes temporais consecutivos).
Esta restrição baseia-se na seguinte observação: à medida que o tempo
passa, os processos biológicos vão-se sucedendo, iniciando e terminando,
levando a um aumento ou decréscimo da actividade de conjuntos de genes, que podem ser identificados pela formação de biclusters com colunas
contíguas. Neste contexto, a activação de conjuntos de genes em determi-
Biclustering
28
nadas condições corresponde, em muitos casos, à activação de um dado
processo biológico.
Genes
Time
P1
P3
P2
P3
Figura 3.3: Três processos biológicos identificados em séries temporais de expressão
genética.
A Figura 3.3 ilustra a existência de três processos biológicos (P1, P2 e
P3) que originam um aumento da actividade de diferentes conjuntos de
genes, representados por três biclusters. Note-se que, embora as colunas
de cada bicluster sejam contíguas, as linhas podem-se encontrar em posições arbitrárias, aparecendo representadas como contíguas apenas por
conveniência. A sobreposição de biclusters também é permitida, isto é,
alguns genes podem contribuir para vários processos biológicos simultaneamente, assim como num determinado conjunto de instantes temporais
poderão ocorrer diversos processos.
As séries temporais de expressão genética são muitas vezes usadas no
estudo de sistemas biológicos dinâmicos e redes de regulação genética,
pois a sua análise pode fornecer elementos que potenciem uma melhor
compreensão dos sistemas biológicos [11]. Neste contexto, a identificação
de processos biológicos que levam à criação de biclusters, bem como a relação entre estes, é crucial para a identificação de mecanismos de regulação
genética e, mais ambiciosamente, para a inferência de redes de regulação
genética.
Capítulo 4
Trabalho Relacionado
O objectivo do presente capítulo é apresentar o trabalho relacionado com
a ferramenta desenvolvida. Apresentaremos uma breve referência aos algoritmos já implementados e integrados no contexto da análise de séries
temporais de expressão genética da aplicação, nomeadamente os algoritmos CCC-Biclustering [13], e-CCC-Biclustering [14] e CC-TSB-Biclustering
[23]. Incidiremos em particular sobre as novas extensões do algoritmo
CCC-Biclustering, que permitem actualmente extrair dois novos tipos de
biclusters: biclusters com padrões de expressão simétricos (anti-correlation)
e/ou desfasamento temporal entre os diferentes instantes temporais (timelags) em que se inicia o padrão de expressão dos genes que pertencem ao
bicluster.
Apresentaremos também a análise compreensiva dos algoritmos qClustering [9] e CDK-Means [19], realizada durante o segundo semestre,
e uma breve referência aos algoritmos de clustering hierárquico reimplementados em Java com base numa biblioteca de clustering em linguagem
C [5].
4.1
Biclustering para Séries Temporais
Os algoritmos seleccionados para integrar a ferramenta BiGGEsTS têm em
comum a sua aplicação à análise de dados de expressão genética cujas
condições correspondem a instantes temporais consecutivos e permitem,
no geral, encontrar biclusters cujos níveis de expressão dos subconjuntos de
genes que os compõem apresentam evoluções coerentes para os respectivos
29
30
Trabalho Relacionado
subconjuntos de condições. Os biclusters identificados pelos algoritmos
utilizados podem-se sobrepor, isto é, apresentar genes ou condições em
comum.
4.1.1
Algoritmos na aplicação
Dos algoritmos integrados na aplicação, dois tinham já sido implementados (CCC-Biclustering e e-CCC-Biclustering) e foram apenas integrados na
ferramenta, enquanto um terceiro foi implementado no desenvolvimento
do projecto (CC-TSB-Biclustering).
Algoritmos integrados
CCC-Biclustering
CCC-Biclustering é um algoritmo proposto recentemente [13] e permite
encontrar e identificar todos os biclusters máximos de colunas coerentes
contíguas em tempo linear no tamanho da matriz de expressão. Para isso é
efectuado o processamento de uma matriz de valores discretos, utilizando
técnicas de processamento de strings (cadeias de caracteres) baseadas em
árvores de sufixos. Cada padrão de expressão partilhado pelos genes
de um bicluster no seu subconjunto de instantes temporais consecutivos
representa um processo biológico potencialmente relevante. O seu funcionamento foi explicado de forma precisa no relatório do primeiro semestre
[7].
CCC-Biclustering com gene shifts
Dado que diferentes genes apresentam níveis de expressão diferentes que,
juntamente com a discretização, podem limitar a capacidade do algoritmo
CCC-Biclustering para descobrir todos os padrões de expressão relevantes,
Madeira e Oliveira propõem um algoritmo CCC-Biclustering com shifting
(translação) de padrões de expressão. Esta extensão do algoritmo permite
o shifting dos padrões de expressão genética k símbolos para cima e para
baixo, de forma a encontrar CCC-Biclusters máximos que não seriam encontrados devido aos diferentes níveis de expressão entre os genes. O valor
de k é, geralmente, um valor inteiro entre 1 e |Σ|, em que Σ é o conjunto
de símbolos, por ordem lexicográfica, usado para discretizar a matriz de
4.1 Biclustering para Séries Temporais
31
expressão original. Com esta extensão, o algoritmo CCC-Biclustering, cuja
complexidade inicial é O(|R||C|), passa a ter complexidade O(2|R||C||Σ|) no
pior caso.
CCC-Biclustering com padrões de expressão simétricos
Uma das novidades no algoritmo CCC-Biclustering é a possibilidade de
extracção de biclusters com genes com padrões de expressão simétricos (sign
changes), isto é, biclusters que agrupam genes que apresentam uma evolução
coerente, embora simétrica, do nível de expressão. Estes biclusters podem
ser considerados interessantes, na medida em que identificam genes que
apresentam um comportamento exactamente oposto quando confrontados
com as mesmas condições experimentais ou participando em processos
biológicos idênticos, tornando assim evidentes fenómenos de activação ou
repressão. A complexidade do algoritmo CCC-Biclustering com padrões
de expressão simétricos é O(2|R||C|) no pior caso.
CCC-Biclustering com atrasos
A segunda novidade no CCC-Biclustering é a integração, no mesmo bicluster, de genes que apresentam padrões de expressão semelhantes, mas
instantes iniciais distintos (time-lags). Este facto indicia que os vários genes
possuem diferentes tempos de resposta às condições experimentais produzindo, no entanto, um comportamento semelhante. Para permitir biclusters
com desfasamento temporal do padrão, o algoritmo CCC-Biclustering é estendido garantindo uma complexidade O(|R||C| + |R||C|2 ), O(|R||C|2 ) no pior
caso.
CCC-Biclustering com padrões de expressão simétricos e atrasos
As opções de padrões de expressão simétricos e atrasos podem ser utilizadas em simultâneo, gerando biclusters com ambas as características
acima descritas. A combinação destes algoritmos, dada a sua natureza,
representa um aumento considerável relativamente à complexidade do
algoritmo original, com O(2|R||C| + 2|R||C|2 ) no pior caso.
32
Trabalho Relacionado
e-CCC-Biclustering
As técnicas de discretização, bem como o ruído inerente à medição dos
dados das experiências com microarrays, podem limitar a capacidade do
algoritmo CCC-Biclustering para identificar padrões biologicamente relevantes. Para tentar ultrapassar este problema, Madeira e Oliveira propuseram um novo algoritmo, e-CCC-Biclustering [14], que permite a ocorrência
de um determinado número de erros no padrão de cada um dos genes do
CCC-Bicluster encontrado. Os biclusters encontrados são então designados
e-CCC-Biclusters, em que e é o número de erros permitido. Os erros podem, em geral, ser substituições de um determinado símbolo do padrão de
expressão por outros símbolos que constituem o alfabeto de discretização
(caso que corresponde a erros de medição), ou substituições restringidas
aos símbolos de discretização mais próximos na ordem lexicográfica (correspondentes a erros de discretização). A complexidade deste algoritmo é
polinomial no tamanho da matriz de expressão genética a processar.
e-CCC-Biclustering com erros restritos
O algoritmo e-CCC-Biclustering apresentado permite erros gerais, isto é,
substituições dos símbolos Aij do CCC-Bicluster Bk = (Ik , Jk ) por qualquer
símbolos do alfabeto Σ0j excepto Ai j . Este tipo de erros são particularmente relevantes para a identificação de erros de medição que ocorrem
durante as experiências com microarrays. Contudo, se estivermos interessados em identificar erros de discretização podemos considerar erros
restritos: substituições dos símbolos Ai j pelos símbolos lexicograficamente
mais próximos em Σ0j .
e-CCC-Biclustering com erros restritos e gene shifts
O gene shifting implementado no algoritmo e-CCC-Biclustering é, em tudo,
semelhante ao referido para o algoritmo CCC-Biclustering e pode ser combinado com com os erros restritos, permitindo aumentar, em muitos casos,
o número de e-CCC-Biclusters extraídos pelo algoritmo.
4.1 Biclustering para Séries Temporais
33
CC-TSB-Biclustering
O algoritmo CC-TSB-Biclustering [23], desenvolvido para séries temporais
de expressão genética, usa a média dos quadrados dos resíduos (MSR mean-squared residue) como medida de qualidade dos biclusters. Forçando
a MSR a diminuir até atingir um determinado valor considerado como
o valor máximo permitido, o algoritmo vai eliminando genes e instantes
temporais (condições) de acordo com a sua correlação no bicluster. Para
assegurar a coerência dos instantes temporais, apenas as condições inicial
e final são elegíveis para serem removidas. Como consequência, o número
de genes e o tamanho do intervalo de tempo são simultaneamente maximizados. A complexidade assimptótica do algoritmo CC-TSB-biclustering
é O(nK|R||C|), em que n é o número de biclusters a extrair pelo algoritmo
(definido a priori), K o número máximo de iterações para optimizar cada
bicluster e |R| e |C| os números de linhas e colunas da matriz, respectivamente.
4.1.2
Algoritmos analisados
Nesta secção são analisados dois algoritmos de biclustering para séries
temporais de expressão genética que não se encontram implementados
ou integrados na ferramenta desenvolvida no projecto, dado que as extensões do algoritmo CCC-Biclustering permitem obter os mesmos resultados
com complexidade inferior e também que, em casos específicos, o resultado
pretendido não corresponde aos objectivos da ferramenta, como verificaremos na nossa análise. Os algoritmos designam-se CDK-Means [19] e
q-Clustering [9].
CDK-Means e D-Miner
CDK-Means [19] [18] consiste num agrupamento (clustering) de biclusters
segundo um determinado critério de qualidade associado à restrição a
colunas contíguas (instantes temporais consecutivos e, portanto, intervalos
de tempo). Para tal, a técnica CDK-Means requer uma extracção prévia
de um conjunto de biclusters possivelmente interessantes, através de um
outro algoritmo, D-Miner [17]. Ambos se aplicam a dados de expressão
genética discretos obtidos a partir de valores reais com alfabetos de apenas
34
Trabalho Relacionado
dois símbolos (dados binários) e cujas condições correspondem a instantes
temporais sucessivos.
CDK-Means
A ideia essencial do CDK-Means é extrair clusters a partir de biclusters que
revelam associações locais fortes entre subconjuntos de genes e subconjuntos de condições (ver Algoritmo 1).
Assume para isso que um conjunto B de biclusters interessantes foi
extraído previamente pelo algoritmo de biclustering D-Miner sobre uma
matriz de expressão genética A de valores discretos obtida a partir de uma
matriz de expressão genética A0 de valores reais com um alfabeto binário
(de dois símbolos, por exemplo: {D, U}, {0, 1} , {A, B} ).
Assume também que o alfabeto está ordenado lexicograficamente. Denotando cada um dos biclusters extraídos por bk = (Rk , Ck ), (Rk ⊆ R, Ck ⊆ C)
e o descrevermos como um vector < rk >< ck >=< rk1 , ..., rkm >< ck1 , ..., ckn >
em que rk j = 1 se r j ∈ Rk (0 caso contrário) e ck j = 1 se c j ∈ Ck (0 caso
contrário). O objectivo consiste então em encontrar K clusters de biclusters
{P1 B , ..., PK B }(Pi B ⊆ B).
O centróide de um cluster de biclusters Pi B é definido por µi =< τi ><
γi >=< τi1 , ..., τim >< γi1 , ..., γin > em que τ e γ são os habituais componentes
do centróide, assim definidos:
1 X
1 X
rk j , γij = B
ck j
τij = B
|Pi | b ∈P B
|Pi | b ∈P B
k
i
k
i
Especificado o cálculo do centróide, pode-se então definir a distância
entre um determinado
bicluster e o centróide
do conjunto:
|ck ∪γi |−|ck ∩γi |
1 |rk ∪τi |−|rk ∩τi |
d(bk , µi ) = 2
+
|rk ∪τi |
ck ∪γi
Esta distância é a média das diferenças simétricas pesadas entre os
P
r +τi j
vários componentes do conjunto. Assume-se que rk ∩ τi = mj=1 a j k j 2 e
P r +τi j
rk ∪ τi = mj=1 k j 2 em que a j = 1 se rk j · τi j , 0, a j = 0 caso contrário.
Intuitivamente, a intersecção é igual à média entre o número de linhas
(genes) comuns e a soma dos seus pesos no centróide. A união é a média
entre o número de linhas e a soma dos seus pesos no centróide. Estas
medidas são definidas de forma semelhante para as colunas (condições)
da matriz de dados.
As linhas rk e, de forma semelhante, as colunas ck , são atribuídas a
um dos K clusters (denotado por i) para o qual τik , respectivamente γik ,
4.1 Biclustering para Séries Temporais
35
é máximo. Podemos permitir que as linhas (genes) e/ou colunas (condições) pertençam a mais do que um cluster controlando o tamanho da
parte sobreposta de cada cluster, através de um parâmetro definido pelo
utilizador.
Algoritmo 1: Algoritmo CDK-Means
Input: r, matriz de expressão genética de valores discretos (alfabeto
binário); B, colecção de biclusters em r; K, número de clusters a
extrair; MI, número máximo de iterações; δr , δc , valores limite
para controlo da sobreposição dos clusters
Output: Clusters de linhas (genes) e de colunas (condições)
µ1 , ..., µK , centróides iniciais dos clusters; k = 0
while centróides alterados e k < MI do
foreach bicluster c ∈ B do
atribuir c ao cluster C tal que d(c, µi ) é mínima
foreach cluster Ci do
calcular τi e γi
k=k+1
if sobreposição permitida then
foreach r j ∈ R do
atribuir r j a cada cluster Cri , tal que τij ≥ (1 − δr ) · max τij
foreach c j ∈ C do
atribuir c j a cada cluster Cci , tal que γi j ≥ (1 − δc ) · max γij
else
foreach r j ∈ R do
atribuir r j ao primeiro cluster Cri , tal que τi j é máximo
foreach c j ∈ C do
atribuir c j a cada cluster Cci , tal que γij é máximo
return {Cr1 , ..., CrK } e {Cc1 , ..., CcK }
D-Miner
O algoritmo D-Miner permite extrair biclusters a partir de matrizes com
dados de expressão genética do tipo referido no Capítulo 3. Considerando
uma matriz A de valores discretos, com um alfabeto binário (de dois símbolos) e os subconjuntos de linhas (genes) I ⊂ R e de colunas (condições)
J ⊂ C, os autores definem os seguintes conceitos [17]:
36
Trabalho Relacionado
Linguagem dos biclusters: L = LR × LC , em que LR = 2R (conjuntos de
linhas - genes) e LC = 2C (conjuntos de colunas - condições).
Conjunto de linhas (genes) comuns a um conjunto de colunas (condições): φ(I, A) = {r ∈ I|∀c ∈ J, (r, c) ∈ A}.
Conjunto de colunas (condições) comuns a um conjunto de linhas (genes): ψ(J, A) = {c ∈ J|∀r ∈ I, (r, c) ∈ A}.
Ligação de Galois: (φ, ψ) denota uma ligação de Galois entre I e J.
Fechos de Galois: os operadores de fecho de Galois são h = φ ◦ ψ e
h0 = ψ ◦ φ.
Frequência de um conjunto de linhas: |ψ(I, A)|.
Frequência de um conjunto de colunas: |φ(J, A)|.
Restrições sobre a frequência de linhas (genes): Consmin f req (A, γ, I) ≡
|ψ(I, A)|) ≥ γ e Consmax f req (A, γ0 , I) ≡ |ψ(I, A)| ≤ γ0 , em que γ e γ0
são valores limite para as frequências mínima e máxima, respectivamente.
Restrições sobre a frequência de colunas (condições): Consmin f req (A, γ, J) ≡
|φ(J, A)|) ≥ γ e Consmax f req (A, γ0 , J) ≡ |φ(J, A)| ≤ γ0 , em que γ e γ0 são valores limite para as frequências mínima e máxima, respectivamente.
Conjunto de linhas fechado: I é fechado se satisfaz a restrição Consclose (I, A) ≡
h(I, A) = I.
Conjunto de colunas fechado: J é fechado se satisfaz a restrição Consclose (J, A) ≡
h(J, A) = J.
1-rectângulo: (I, J) é um 1-rectângulo se e só se ∀r ∈ I e ∀c ∈ J, (r, c) ∈ A .
0-rectângulo: (I, J) é um 0-rectângulo se e só se ∀r ∈ I e ∀c ∈ J, (r, c) < A.
Conceito (formal): (I, J) é um conceito (formal) em A se I = ψ(I, A) e
J = φ(J, A). Um conceito (formal) não é mais do que um 1-rectângulo
máximo, isto é, um rectângulo em que todos os valores de expressão correspondem ao valor máximo do alfabeto de discretização da
matriz de expressão genética e cujos conjuntos de linhas e colunas
4.1 Biclustering para Séries Temporais
37
não podem ser aumentados sem originarem uma perda no número
de colunas e de linhas, respectivamente.
Transposição: a transposta de A é AT ⊆ R × C, em que (r, c) ∈ AT ≡ (r, c) ∈
A.
Propriedade (transposição): ψ(I, AT ) = φ(I, A), φ(J, AT ) = ψ(J, A), h(I, AT ) =
h0 (I, A) , h0 (J, AT ) = h0 (J, A) .
Relação de Especialização: temos uma relação de especialização (I1 , J1 ) ≤
(I2 , J2 ) se e só se I1 ⊆ I2 e J1 ⊆ J2 , em que (I1 , I2 ) e (J1 , J2 ) são biclusters
com linguagem L.
Monotonia: a restrição Cons é anti-monótona com respeito à ordem ≤
se e só se ∀α, β ∈ L : α ≤ β, Cons(β) ⇒ Cons(α). A restrição Cons
é monótona com respeito à ordem ≤ se e só se ∀α, β ∈ L : α ≤
β, Cons(α) ⇒ Cons(β).
Conceito (formal) frequente: o conceito (I, J) é frequente quando ConsI (A, σ1 , I)
se I ≥ σ1 ou Cons J (A, σ2 , J) se J ≥ σ2 . Estas restrições são ambas monótonas com respeito à ordem ≤ em L.
Baseados nestas definições, podemos agora explicar o funcionamento
do algoritmo D-Miner (ver Algoritmo 2). Numa primeira fase é criado um
conjunto H com todos os 0-rectângulos em A, isto é, todas as sequências
do primeiro símbolo do alfabeto da matriz discreta (sequências de 0 se o
alfabeto for {0, 1} ou de D se o alfabeto for {D, U}, por exemplo). Cada
sequência tem apenas uma linha (gene) e poderá ter uma ou mais colunas
(condições). Os elementos de H, 0-rectângulos, são também designados
cutters.
Após a construção de H, o algoritmo inicia a execução com a matriz
A, que vai dividindo sucessivamente com a aplicação dos cutters até que o
conjunto H fique vazio e que cada conjunto resultante da matriz A seja um
1-rectângulo (ver Algoritmo 3).
O conjunto H é definido da seguinte forma: ∀r ∈ R e ∀c ∈ C : (r, c) <
A, ∃(X, Y) de H : r ∈ X e c ∈ Y.
Um elemento (a, b) de H é usado para dividir uma submatriz (X, Y) se
a ∩ X , ∅ e b ∩ Y , ∅.
38
Trabalho Relacionado
Algoritmo 2: Algoritmo D-Miner
Input: A, matriz com n linhas (genes) e m colunas (condições); R, o
conjunto de genes; C, o conjunto de condições; Consr e Consc ,
as restrições de monotonia em R e C, respectivamente
Output: Q, o conjunto de conceitos que satisfazem Consr e Consc
HL ← vazio()
H é calculado a partir de A
Q ← divisao((R, C), H, 0, HL )
return Q
Na divisão de uma submatriz (X, Y) por um 0-rectângulo de H, (a, b),
as submatrizes resultantes são as seguintes: filho esquerdo - (X\a, Y), filho
direito - (X, Y\b).
Antes da divisão de (X, Y) por (a, b) nos dois subconjuntos (X\a, Y) e
(X, Y\b), dois tipos de restrições devem ser verificadas: as restrições de
monotonia e a restrição de corte à esquerda. A maximização está implícita
neste processo de divisão. O algoritmo D-Miner é um método de pesquisa
primeiro em profundidade (depth-first search) que gera biclusters ordenados
pela relação ≤. As restrições de monotonia em R e C são usadas para reduzir
o espaço de procura: se X, Y não satisfaz uma restrição de monotonia
Cons, então nenhum dos seus filhos satisfaz Cons e é desnecessário aplicar
a divisão a (X, Y). A restrição Cons é a conjunção de uma restrição de
monotonia Consr em R com uma restrição de monotonia Consc em C.
Propriedade (conceito/1-rectângulo máximo): Seja (X, Y) uma folha da
árvore e HL (X, Y) o conjunto de cutters associado aos ramos esquerdos
do caminho desde a raiz até (X, Y). (X, Y) é um conceito se e só se Y
contém pelo menos uma condição de cada conjunto de condições em
HL (X, I).
Consideremos, como exemplo, a matriz de expressão genética apresentada na Tabela 4.1.
A Figura 4.1 apresenta um exemplo de aplicação do algoritmo D-Miner
sobre a matriz de expressão genética de valores discretos da Tabela 4.1,
cujo alfabeto binário é {D, U}. As submatrizes representadas em caixas de
texto correspondem aos 0-rectângulos, elementos do conjunto H.
Na Figura 4.1 podemos ver que (r2 , c2 ) e (r3 , c1 c2 ) do conjunto H não
são usados para dividir a submatriz (r1 r2 r3 , c3 ), dado que {c2 } ∩ {c3 } = ∅ e
4.1 Biclustering para Séries Temporais
39
Algoritmo 3: Algoritmo Divisão
Input: (X, Y), uma submatriz de 2R × 2C elementos; H, a lista de
cutters; i, a profundidade da iteração; HL , o conjunto de
cutters precendentes nos cortes à esquerda; Consr e Consc , as
restrições de monotonia em R e C, respectivamente
Output: Q, o conjunto de conceitos que satisfazem Consr e Consc
(a, b) ← H[i], centróides iniciais dos clusters
if i ≤ |H| − 1 then
if (a ∩ X = ∅) ou (b ∩ Y = ∅) then
Q ← Q ∪ divisao((X, Y), H, i + 1, HL )
else
if Consr (A, σ1 , X\a) for satisfeita then
HL ← HL ∪ (a, b)
Q ← Q ∪ divisao((X\a, Y), H, i + 1, HL )
HL ← HL \(a, b)
if Consc (A, σ2 , Y\b) for satisfeita e ∀(a0 , b0 ) ∈ HL , b0 ∩ Y\b , ∅ then
Q ← Q ∪ divisao((X, Y\b), H, i + 1, HL )
else
Q ← (X, Y)
return Q
{c1 c2 } ∩ {c3 } = ∅. O conjunto de biclusters extraído da matriz da Tabela 4.1 é:
{(r1 r2 r3 , c3 ), (r2 , c1 c3 ), (∅, c1 c2 c3 ), (r3 , c3 ), (r2 r3 , c3 )}.
Verificamos que (r3 , c3 ) ≤ (r1 r2 r3 , c3 ) e (r2 r3 , c3 ) ≤ (r1 r2 r3 , c3 ), pelo que os
1-rectângulos (r3 , c3 ) e (r2 r3 , c3 ) não são conceitos formais, isto é, não são
máximos.
Considerações sobre o algoritmo CDK-Means/D-Miner
O algoritmo D-Miner para extracção de biclusters máximos potencialmente
interessantes possui, claramente, uma complexidade exponencial no tamanho da matriz de expressão genética.
No entanto, e apesar de tal complexidade, o algoritmo considera como
bicluster (designado pelos autores como 1-rectângulo) apenas um subconjunto de linhas (genes) e colunas (condições) cujos elementos apresentam
na sua totalidade o segundo símbolo do alfabeto (1 no caso do alfabeto
{0, 1} ou U no caso do alfabeto {D, U}, por exemplo). Tais submatrizes,
40
Trabalho Relacionado
r1
r2
r3
c1
D
U
D
c2
D
D
D
c3
U
U
U
Tabela 4.1: Matriz de expressão genética discretizada com um alfabeto binário {D, U}.
Figura 4.1: Aplicação do algoritmo D-Miner sobre a matriz de expressão genética de
valores discretos representada na Tabela 4.1.
embora possam ser interessantes, são apenas uma parte dos biclusters existentes na matriz, uma vez que os padrões de expressão que procuramos
podem conter todos os símbolos do alfabeto, isto é, interessam-nos tanto
os genes que possuem um valor de expressão mais baixo como os que
possuem um valor mais elevado para uma dada condição experimental,
pois estes valores são indicativos da inibição ou activação do gene nessa
condição, respectivamente, e permitem estabelecer uma sucessão de variação da expressão genética no tempo, acompanhando os diversos processos
biológicos que se vão sucedendo nas células em estudo.
O algoritmo D-Miner permite extrair todos os biclusters máximos de ge-
4.1 Biclustering para Séries Temporais
41
nes activados em determinadas condições experimentais. Dada a natureza
e especificação do algoritmo, os biclusters resultantes não têm garantida
a propriedade de condições sucessivas, isto é, instantes temporais consecutivos. Este aspecto é colmatado pela introdução da restrição a colunas
contíguas no algoritmo CDK-Means. No entanto, mais uma vez, o resultado deste algoritmo não serve os nossos propósitos, uma vez que devolve
clusters de linhas (genes) e colunas (condições) formados a partir dos biclusters extraídos pelo algoritmo D-Miner.
A solução seria uma implementação do algoritmo D-Miner com a introdução da restrição a colunas contíguas e uma alteração profunda que
permitisse extrair subconjuntos de linhas e colunas compostos pelos dois
símbolos do alfabeto da matriz discreta. Tais operações iriam, por um
lado, descaracterizar completamente o algoritmo original e, por outro, aumentar a sua complexidade. Dado que esta é originalmente exponencial,
a implementação deste algoritmo perde o interesse do nosso ponto de
vista, uma vez que possuímos actualmente um algoritmo de biclustering
de complexidade linear no tamanho da matriz de expressão genética: o
CCC-Biclustering [13].
q-Clustering
O algoritmo q-Clustering tem como objectivo a extracção de biclusters, isto
é, subconjuntos de genes que possuem um padrão de expressão coerente
em determinados subconjuntos de condições. Estes biclusters são extraídos
a partir de q-clusters identificados por um processo específico. Numa fase
posterior, o algoritmo identifica co-regulações de activação e inibição entre
os biclusters extraídos, isto é, biclusters cuja actividade dos genes pode ser
activadora ou inibidora da actividade dos genes de outros biclusters.
FASE 1: Transformação da matriz de expressão genética
O q-Clustering decorre em três passos essenciais. Num primeiro momento a matriz de expressão genética com valores reais, A0 , é transformada
numa matriz de valores discretos, A, com um alfabeto de 3 símbolos (por
exemplo: {−1, 0, 1}, {D, N, U}, {A, B, C}) ordenados lexicograficamente. Denotaremos o alfabeto por α e os seus três símbolos por α1 , α2 e α3 . A
matriz resultante representa a variação simbólica dos valores de expressão
da população de genes da experiência biológica entre condições (instantes
temporais) sucessivas (ver Tabelas 4.2 e 4.3). O facto de a matriz resultante
42
Trabalho Relacionado
representar variações entre instantes temporais faz com que possua menos
uma coluna do que a matriz original.
G2163
G1223
T1
−0.44
−1.51
T2
−0.44
−1.57
T3
0.08
−1.35
T4
0.35
0.04
T5
0.26
1.30
T6
0.17
1.15
T7
−0.46
0.94
T8
−0.13
−0.08
T9
−0.05
−0.13
T10
−0.36
−0.72
Tabela 4.2: Matriz de expressão genética original (valores de expressão reais).
G2163
G1223
T1 T2
N
N
T2 T3
U
N
T3 T4
U
U
T4 T5
N
U
T5 T6
N
N
T6 T7
D
N
T7 T8
N
D
T8 T9
N
N
T9 T10
D
D
Tabela 4.3: Matriz de valores discretos (obtida a partir da matriz original da Tabela 4.2).
Representa as variações dos valores de expressão genética dos genes da experiência entre
os sucessivos instantes temporais. Alfabeto: {D, N, U}
FASE 2 : Extracção de q-clusters
A segunda fase do algoritmo consiste na extracção dos q-clusters que
contêm informação sobre os subconjuntos de genes que apresentam um
padrão de expressão semelhante em q condições sucessivas. O objectivo
principal deste passo é encontrar genes que partilham subsequências idênticas de comprimento q − 1, em que q é um parâmetro definido pelo utilizador (ver Tabela 4.4). Dado que cada elemento da matriz de expressão tem
apenas 3 valores possíveis (os 3 símbolos distintos do alfabeto discreto), o
número máximo de q-clusters que podem ser encontrados é 3q−1 .
Cada q-cluster tem um identificador único, designado q-clusterID, gerado da seguinte forma: Seja P = {p[1], p[2], ..., p[q − 1]} um padrão de
expressão; p[i] = α1 , α2 ou α3 ∀i ∈ [1, q − 1].

0 se p[i] = α2



1 se p[i] = α3
Seja f (p[i]) = 


 2 se p[i] = α1
Pq−1
O q-clusterID para o padrão P é: q-clusterID(P) = i=1 f (p[i])3q−1−i .
A extracção dos q-clusters processa-se da seguinte forma: para cada linha (gene) da matriz A, aplica-se uma janela deslizante de amplitude q − 1.
As várias substrings de comprimento q−1 são analisadas individualmente,
com o cálculo do respectivo q-clusterID e a introdução do par (geneID, st)
4.1 Biclustering para Séries Temporais
Padrão
...
NNUUNN
...
NNDNND
...
NUUNND
...
UNNDNN
UNNDND
...
UUNNDN
...
DNDUND
q-clusterID
...
36
...
56
...
110
...
261
263
...
326
...
551
43
Pares (geneID, st)
...
(1223, 1)
...
(2163, 1)
...
(2163, 1)(1223, 2)
...
(2163, 3)
(2163, 4)
...
(2163, 2)(1223, 3)
...
(580,15) (679,16) (836,15) (906,17) (1308,16) (1518,17)
(1527,16) (1622,16) (1681,15) (1811,17) (1875,16)
(2045,16) (2704,17) (4448,16) (4516,15) (5222,16)
(5535,17) (5758,17) (6049,16)
Tabela 4.4: q-clusters extraídos pelo algoritmo q-Clustering sobre a matriz de expressão
da Tabela 4.3 com q = 7.
no q-cluster correspondente. O geneID é o identificador do gene e st representa o instante temporal inicial da substring de comprimento q − 1 (ver
Algoritmo 4).
Análise de complexidade do algoritmo q-Clustering
A determinação do q-clusterID tem uma complexidade O(q − 1), dada a
necessidade de percorrer todos os elementos da janela de tamanho q − 1
para efectuar o cálculo.
O procedimento de inserção do par r, st num q-cluster com um determinado q-clusterID considera-se constante, O(k), pois pode ser implementado
com estruturas de dados que permitem inserções, remoções e pesquisas
em tempo constante (como uma hash table, por exemplo).
O deslizamento da janela de amplitude q − 1 pelas várias posições
possíveis de uma determinada linha da matriz de dados apresenta uma
complexidade (|C| − q + 2)(q − 1 + k). No pior caso temos que q = |C|
+1ea
2
2
complexidade pode simplificar-se para O(q ).
44
Trabalho Relacionado
Algoritmo 4: Algoritmo q-Clustering (fase 2: extracção de q-clusters)
Input: A, matriz de valores discretos (variations betweeen time-points 3 símbolos); R, C, |R| e |C|, linhas, colunas, número de linhas e
número de colunas de A, respectivamente; q, tamanho do
padrão dos q-clusters a extrair pelo algoritmo
Output: q-clusters com padrão de q condições consecutivas
qClusters = ∅
foreach r ∈ R do
st = 0
while st ≤ |C| − (q − 1) do
i = st
qClusterID = 0
while i < st + (q − 1) do
qClusterID = qClusterID + f (A[i]) × 3q−1−i−st
i=i+1
qClusters = inserir(qClusters, (r, st), qClusterID)
st = st + 1
return qClusters
A iteração sobre as linhas da matriz de expressão genética, englobando
todos os passos referidos anteriormente, revela uma complexidade |R|(|C|−
q + 2)(q − 1 + k). Novamente para o pior caso, a complexidade assimptótica
é O(|R|q2 ).
O Algoritmo 4 permite apenas extrair os q-clusters com um determinado valor de q, isto é, da sua aplicação resultam apenas q-clusters com
padrão de expressão de q − 1 colunas consecutivas. O nosso objectivo é
a obtenção de q-clusters para todos os valores possíveis de q, dado que
nos interessam todos os padrões de expressão possivelmente partilhados
por grupos de genes, independentemente do número de condições que
lhes correspondem. Devido a esta característica, é necessário acrescentar
um passo ao algoritmo original que nos permita repetir o procedimento
especificado no Algoritmo 4 para valores de q desde 2 (com q = 2 os padrões de expressão encontrados têm um comprimento de 1 coluna que,
dada a discretização utilizada, corresponde a duas condições - instantes
temporais - da matriz de expressão original; eliminamos assim à partida os
q-clusters com apenas uma condição) até ao número de condições |C|. Este
P
ciclo iterativo apresenta uma complexidade |C|
q=2 |R|(|C| − q + 2)(q − 1 + k).
4.1 Biclustering para Séries Temporais
45
Simplificando a expressão para o pior caso, podemos considerar como
complexidade assimptótica O(|R||C|2 ).
FASE 3 : Extracção dos biclusters e pesquisa de co-regulações de
activação e inibição
O último passo do algoritmo q-Clustering engloba a extracção dos biclusters a partir dos q-clusters e a pesquisa de co-regulações de activação e
inibição entre os biclusters extraídos.
A tarefa de extracção dos biclusters exige que os pares (geneID, st) sejam ordenados pelo instante inicial st para que os que possuem a mesma
condição inicial sejam agrupados. De acordo com as características de
um q-cluster, todos os pares (geneID, st) com o mesmo instante temporal
inicial partilham o mesmo padrão de expressão para as mesmas condições
(instantes temporais), isto é, constituem um bicluster (ver Tabela 4.5).
Instante Inicial
15
16
17
Identificadores dos genes
580 836 1681 4516
679 1308 1527 1622 1875 2045 4448 5222 6049
906 1518 1811 2704 5535 5758
Tabela 4.5: Biclusters de instantes iniciais 15, 16 e 17 identificados no q-cluster 551 da
Tabela 4.4 com o padrão DNDUND.
A identificação de co-regulações de activação entre os biclusters extraídos é também um passo bastante simples e intuitivo. Dadas as características dos q-clusters, todos os biclusters extraídos de um mesmo q-cluster têm
exactamente o mesmo padrão de expressão, diferindo apenas na condição
inicial. Este facto permite que a simples comparação dos instantes temporais iniciais dos vários biclusters de um determinado q-cluster nos revele
que biclusters podem ser potencialmente activados por outros biclusters,
isto é, quais os biclusters que, tendo o mesmo padrão de expressão que
outros, tendem a revelá-lo mais tardiamente.
As co-regulações de inibição exigem, num primeiro momento, a pesquisa de q-clusters com padrões de expressão simétricos. A tarefa seguinte
consiste em comparar as condições iniciais dos biclusters dos q-clusters com
padrão simétrico. Se um bicluster pertencente a um dos q-clusters possui
um instante temporal inicial posterior ao de um bicluster de um q-cluster
com um padrão de expressão simétrico, considera-se que este bicluster é
inibido por aquele. Os q-clusters 551 e 289 apresentados nas Tabelas 4.5 e
46
Trabalho Relacionado
4.6, respectivamente, possuem padrões de expressão simétricos, pelo que
o bicluster com instante inicial 14 do q-cluster 289 (Tabela 4.6) pode ser considerado inibidor do bicluster de instante inicial 17 do q-cluster 551 (Tabela
4.5) com um intervalo (time-lag) de 3 instantes temporais, por exemplo.
Instante Inicial
10
14
15
Identificadores dos genes
868 968 1254 1434 1609 1973 2256 2330 4064 5733
3962 4210 4378 5415 6118
320 321 344 419 1699 6147
Tabela 4.6: Biclusters de instantes iniciais 10, 14 e 15 identificados no q-cluster 289 da
Tabela 4.4 com o padrão UNUDNU.
Considerações sobre o algoritmo q-Clustering
A análise do algoritmo q-clustering revelou a existência de três fases distintas e independentes, que proporcionam uma integração completa no
modelo conceptual já desenvolvido e que se encontra implementado na
aplicação BiGGEsTS. A primeira fase consiste num pré-processamento da
matriz de expressão genética em que se aplica uma transformação dos dados reais em dados discretos, com um alfabeto três símbolos (tipicamente
{D, N, U}), representando as variações do valor de expressão genética entre
condições (instantes temporais) consecutivas (variations between time-points.
Posteriormente, a extracção dos q-clusters associada à identificação dos
biclusters consiste na aplicação da técnica de biclustering. Como demonstrámos anteriormente, a complexidade da extracção dos q-clusters utilizando
o algoritmo indicado pelos autores é O(|R||C|2 ). A identificação dos biclusters a partir dos q-clusters extraídos acrescenta ainda algum tempo de
processamento adicional devido à necessidade de ordenação dos pares
(geneID, st) em cada q-cluster. No entanto, este passo pode ser evitado
trocando a ordem das iterações sobre as linhas da matriz e da janela de
comprimento q − 1 nas linhas, isto é, processar as janelas de igual instante inicial em todas as linhas da matriz e só depois passar para a janela
seguinte. Desta forma, aquando da conclusão do algoritmo, os pares
(geneID, st) estarão automaticamente ordenados.
Dado que existe uma alternativa ao algoritmo dos autores cuja complexidade é apenas linear no tamanho da matriz de expressão, O(|R||C|),
consideramos que a implementação deste algoritmo não é vantajosa para
4.2 Algoritmos de Clustering Hierárquico
47
a aplicação.A última fase do algoritmo q-Clustering foi identificada na
nossa análise como uma fase de pós-processamento, na qual são identificadas co-regulações de activação e inibição entre os biclusters extraídos
previamente. Estas técnicas foram integradas no CCC-Biclustering, dando
origem ao que anteriormente designámos por biclusters com padrões simétricos (sign changes) e atrasos (time-lags).
4.2
Algoritmos de Clustering Hierárquico
Os algoritmos de clustering hierárquico foram reimplementados em Java a
partir de uma biblioteca de clustering em linguagem C pertencente à ferramenta Cluster 3.0, um software de clustering livre e open source que inclui
diversos algoritmos de clustering, nomeadamente clustering hierárquico e
K-Means.
A técnica hierárquica consiste numa série de partições sucessivas a
partir de um cluster inicial que contém todos os objectos até se obter um
determinado número de clusters. Os métodos de clustering hierárquico
subdividem-se em métodos aglomerativos, que procedem à fusão dos vários objectos em grupos, e métodos divisivos, que separam os objectos
sucessivamente em agrupamentos cada vez mais pequenos.
De uma forma geral, um algoritmo aglomerativo produz um conjunto
de partições, Pn , Pn−1 , ..., P1 dos dados. A partição Pn contém n clusters
individuais, enquanto a partição P1 consiste num único cluster contendo
todos os n casos. Em cada passo, o método aglomera os dois clusters mais
próximos (mais semelhantes). As diferenças entre os métodos utilizados
devem-se, essencialmente, às diversas formas de definir a distância (ou
similaridade) entre os clusters. Os algoritmos de clustering hierárquico no
BiGGEsTS podem ser aplicados com as seguintes medidas de similaridade:
distância baseada na correlação, na correlação de Pearson, correlação absoluta, correlação absoluta de Pearson, correlação de Spearman ou correlação
de Kendall, e distância euclideana ou cityblock. Não apresentaremos as suas
definições, dado que são técnicas conhecidas e se situam fora do âmbito
do presente relatório.
As técnicas implementadas, que passaremos a explicar, pertencem à
classe aglomerativa e designam-se: single-linkage, complete-linkage, averagelinkage e centroid-linkage clustering.
48
4.2.1
Trabalho Relacionado
Single-linkage clustering
Também conhecida como a técnica nearest neighbor, a sua característica
principal é o facto de a distância entre os clusters ser definida como a
distância entre o par de objectos mais próximo.
A distância entre dois clusters, r e s, define-se da seguinte forma:
D(r, s) = min{d(i, j) : i ∈ r, j ∈ s}
A distância é calculada para todos os pares de objectos (i, j), em que o
objecto i pertence ao cluster r e o objecto j pertence ao cluster s. O valor
mínimo das distâncias é a distância entre os clusters r e s, isto é, a distância
entre dois clusters é dada pelo comprimento da ligação mais próxima entre
eles.
Em cada passo do algoritmo, os dois clusters r e s para os quais a
distância D(r, s) é mínima são agrupados.
4.2.2
Complete-linkage clustering
O método complete-linkage, ou farthest neighbor é o oposto do anterior. A
distância entre os clusters é definida como a distância entre o par de objectos
mais distante (um de cada cluster).
A distância D(r, s) é assim definida: D(r, s) = max{d(i, j) : i ∈ r, j ∈ s}
A distância é calculada para todos os pares de objectos (i, j), em que o
objecto i pertence ao cluster r e o objecto j pertence ao cluster s. O valor
máximo das distâncias é a distância entre os clusters r e s, isto é, a distância
entre dois clusters é dada pelo comprimento da ligação mais distante entre
eles. Em cada passo do algoritmo, os dois clusters r e s para os quais a
distância D(r, s) é máxima são agrupados.
4.2.3
Average-linkage clustering
Neste tipo de clustering hierárquico, a distância entre dois clusters é definida
como a média das distâncias entre todos os pares de objectos, em que cada
par é constituído por um objecto de cada um dos clusters:
rs
D(r, s) = (NTr ·N
s)
Em que Trs é a soma de todas as distâncias entre os pares de objectos
dos clusters r e s. Nr e Ns são os tamanhos dos clusters r e s, respectivamente.
Em cada iteração do algoritmo average-linkage, os clusters r e s para os
quais a distância D(r, s) é mínima são agrupados.
4.2 Algoritmos de Clustering Hierárquico
4.2.4
49
Centroid-linkage clustering
Nesta técnica, os clusters formados são representados pelos seus valores
médios para cada variável, isto é, o seu vector intermédio. A distância
entre clusters é definida como a distância entre os vectores intermédios dos
mesmos.
Os dois clusters, r e s, são agrupados de tal forma que, após a fusão, a
distância média entre os pares de objectos com o novo cluster (constituído
pelos dois clusters originais) é mínima.
Designemos o novo cluster formado pelos clusters r e s por t. A distância
D(r, s) entre os clusters r e s é definida por:
D(r, s) = average{d(i, j) : i ∈ t, j ∈ t}
Em cada iteração, os clusters r e s para os quais a distância D(r, s) é
mínima, são agrupados. Neste caso, os dois clusters são agrupados de tal
forma que o novo cluster, por eles formado, apresente distâncias mínimas
entre os seus pares de objectos.
Capítulo 5
A Ferramenta BiGGEsTS
A aplicação desenvolvida no projecto designa-se BiGGEsTS (Biclustering
Gene Expression Time-Series) e consiste numa ferramenta de análise, manipulação e visualização de séries temporais de expressão genética. As suas
funcionalidades principais envolvem a manipulação de diversos conjuntos de dados de expressão genética em simultâneo, a aplicação de diversos
algoritmos de pré-processamento (filtragem de genes, preenchimento de
valores em falta, normalização, smoothing e discretização), algoritmos de
biclustering e cálculo de funções biológicas significativas para análise dos
dados. Permitem ainda a visualização dos dados ao longo de todo o processo de manipulação, segundo diversos tipos de representações gráficas
que serão referidas posteriormente, assim como uma análise detalhada dos
resultados.
5.1
Modelação
Na modelação da ferramenta BiGGEsTS serão apresentadas:
• A análise de requisitos e desenho da aplicação, apoiada pelos respectivos diagramas de casos.
• A análise de estrutura, em conjunto com os diagramas de classes.
• A análise da arquitectura, suportada pelo diagrama que relaciona os
vários pacotes internos e externos utilizados na implementação das
funcionalidades pretendidas.
51
52
A Ferramenta BiGGEsTS
As ferramentas utilizadas na modelação do BiGGEsTS foram: o Visual
Paradigm for UML 6.0 Enterprise Edition e o Visual Paradigm Smart Development Environment 4.0 for JBuilder Enterprise Edition (ambos cópias
de avaliação). A escolha foi motivada pelo conhecimento prévio das referidas aplicações e das suas potencialidades, bem como ao seu perfeito
enquadramento com o IDE utilizado na implementação.
5.1.1
Análise de Requisitos e Desenho
A análise de requisitos para a ferramenta BiGGEsTS teve início com o
levantamento de potencialidades e problemas das diversas ferramentas
disponíveis para análise de dados de expressão genética, sobre o qual foi
apresentada uma síntese no relatório do primeiro semestre.
As decisões sobre as funcionalidades da aplicação a desenvolver foram
tomadas numa primeira fase de análise de requisitos e posteriormente revistas ao longo de todo o processo de desenvolvimento, numa tentativa de
produzir um software de utilização intuitiva e agradável, procurando uma
integração fluida das funcionalidades disponibilizadas. Os diagramas e
funcionalidades apresentados neste relatório são os que correspondem à
ferramenta actual, após as alterações sofridas ao longo do segundo semestre.
Funcionalidades principais
Para uma utilização intuitiva, todos os dados carregados na aplicação são
apresentados numa estrutura hierárquica em árvore. A selecção de um
determinado nodo da árvore de dados despoleta automaticamente o reconhecimento do objecto nele contido e a apresentação das funcionalidades
que lhe correspondem. As funcionalidades que não podem ser aplicadas ao objecto identificado permanecem visíveis, mas são desactivadas,
evitando assim mensagens de erro desnecessárias para o utilizador.
As funcionalidades principais da aplicação, apresentadas no diagrama
de casos da Figura 5.1, permitem:
• Carregar dados de expressão genética sob a forma de ficheiros de
texto, nos quais os dados aparecem dispostos tal como numa tabela,
separados por um determinado delimitador: os nomes dos genes
são incluídos na primeira coluna, os nomes das condições (instantes
5.1 Modelação
53
Figura 5.1: Diagrama de casos das funcionalidades principais da ferramenta BiGGEsTS.
temporais) na primeira linha e cada um dos restantes valores, correspondente ao nível de expressão de um determinado gene numa
determinada condição, na posição da tabela que lhe corresponde; a
tabela de valores pode ter alguns valores em falta, que deverão ser
tratados antes de qualquer outro processamento sobre os dados de
expressão.
• Pré-processar matrizes de dados previamente carregadas.
• Aplicar um algoritmo de biclustering, e correspondente análise de
54
A Ferramenta BiGGEsTS
funções biológicas relevantes, a uma determinada matriz; do algoritmo de biclustering resulta sempre um grupo de biclusters que, por
sua vez, é constituído por vários biclusters individuais.
• Analisar ou visualizar os dados de expressão genética contidos numa
matriz, bicluster ou grupo de biclusters.
• Pós-processar grupos de biclusters extraídos pelos algoritmos de biclustering.
• Gravar e restaurar sessões.
• Terminar a sessão actual, guardando ou não os seus dados para
posterior utilização.
Módulo de carregamento de dados (Load dataset)
O carregamento de dados de expressão genética, cujo diagrama de casos
é ilustrado na figura 5.2, implica, num primeiro momento, a indicação do
caminho para o ficheiro de texto que contém os referidos dados (a selecção
do ficheiro pode ser feita recorrendo à navegação no sistema de ficheiros
local).
Após este passo, o sistema analisa os dados contidos no ficheiro e
apresenta-os numa tabela colorida, assinalando a cores distintas: as linhas
que contêm nomes (possivelmente os nomes das condições), as colunas
que contêm nomes (possivelmente os nomes dos genes) e todos os valores
de expressão que serão integrados na matriz de dados caso o carregamento
seja concretizado. Nos casos em que a aplicação não encontra os nomes
dos genes ou das condições, é oferecida a possibilidade de gerar essa(s)
mesma(s) linha(s) ou coluna(s) de forma automática ou seleccionar a primeira linha/coluna do ficheiro como a que contém os nomes pretendidos.
Seguidamente o utilizador deve:
• Seleccionar a linha que contém os nomes das condições, de entre as
várias identificadas automaticamente pelo sistema;
• Seleccionar o identificador dos genes, que indica o tipo de identificador utilizador para designar os genes no ficheiro de dados; por
omissão, o sistema pressupõe que os identificadores correspondem
aos gene IDs utilizados pela Gene Ontology; se os identificadores da
5.1 Modelação
55
Figura 5.2: Diagrama de casos do módulo de carregamento de dados.
experiência forem distintos dos referidos, o utilizador deverá retirar
a selecção da check box File contains gene IDs e indicar o caminho para
o ficheiro de conversão, que contém a correspondência entre os identificadores no ficheiro e os respectivos gene IDs, para que o sistema
possa fazer a conversão; é também necessário indicar qual a coluna
que contém os nomes dos genes, de entre as várias identificadas automaticamente; caso os nomes dos genes não possam ser convertidos,
por falta de ficheiro de conversão ou erro na própria transformação, a
análise de funções biológicas relevantes (posteriormente) não poderá
ser realizada;
56
A Ferramenta BiGGEsTS
Figura 5.3: Diagrama de casos da selecção do organismo, no módulo de carregamento de
dados.
• Seleccionar o tipo de nucleótidos utilizado na medição do nível de
expressão genética (cDNA ou oligonucleótidos, são os tipos disponíveis);
• Seleccionar o organismo (diagrama de casos da Figura 5.3) ao qual
os dados se referem e que possibilitará, posteriormente, a análise de
funções biológicas relevantes através de uma comparação entre os genes analisados e os genes já conhecidos e anotados para o organismo
específico;
• Decidir aplicar ou não uma transformação logarítmica aos dados de
expressão; na maioria das vezes, os dados de expressão contidos nos
ficheiros representam já a transformação logarítmica dos valores originais medidos na experiência; o utilizador deverá conhecer os dados
5.1 Modelação
57
que pretende carregar, de modo a que a análise posterior produza os
resultados esperados.
Todas estas selecções possuem valores pré-definidos, que o utilizador
poderá aproveitar, sobretudo se não for conhecedor da área (a selecção do
organismo afecta somente a análise de funções, por exemplo) ou se desejar
apenas testar a aplicação.
Finalmente, após a selecção de todos os parâmetros, o utilizador deverá
premir o botão Load que se encontra na parte inferior do painel. Os dados
são carregados e a aplicação apresenta então a matriz de expressão genética
colorida. Se existirem no sistema local ficheiros da Gene Ontology com as
anotações correspondentes ao organismo em causa, a aplicação executa em
simultâneo a análise de funções sobre os genes. O resultado desta análise
poderá ser posteriormente acedido através das abas Analyzing, Function e
Table.
Módulo de Pré-Processamento
O diagrama de casos apresentado na Figura 5.4 contém as opções de
pré-processamento de dados de expressão genética. Só são aceites para
pré-processamento matrizes originais, provenientes do carregamento directo dos dados de um ficheiro de texto, ou matrizes pré-processadas (que
não tenham sido sujeitas a técnicas de discretização). Os tipos de préprocessamento disponíveis são:
• Filtragem de genes: acessível (e obrigatória) apenas para matrizes de
dados originais ou pré-processadas (de valores reais) que possuam
valores em falta. É possível filtrar todos os genes que possuam valores
em falta ou apenas os genes com uma percentagem de valores em falta
superior a uma determinada percentagem estipulada pelo utilizador.
• Preenchimento de valores em falta (missing values): acessível (e obrigatório) para matrizes (originais ou pré-processadas) que possuam
valores em falta, quando conjugado com a opção do utilizador pela
filtragem de genes com uma percentagem de valores em falta superior a uma determinada percentagem. O preenchimento de valores
em falta pode ser efectuado com um valor específico indicado pelo
utilizador, com o valor médio da linha ou ainda com a média dos
valores de expressão dos k-vizinhos mais próximos, em que o valor
de k é introduzido pelo utilizador.
58
A Ferramenta BiGGEsTS
Figura 5.4: Diagrama de casos do módulo de pré-processamento.
• Normalização dos dados da matriz: aplicada por linha ou em toda a
matriz. O objectivo é que a média nas linhas/matriz seja 0 e o desviopadrão das linhas/matriz seja 1 ou que os valores das linhas/matriz
tenham determinada média e determinado desvio-padrão definidos
pelo utilizador.
• Smoothing: aplicado a todos os valores da matriz, utilizando uma
janela de tamanho w definido pelo utilizador e um conjunto de pesos calculado automaticamente. O algoritmo de smoothing funciona como um filtro passa-baixo, eliminando valores estranhos facilmente identificáveis como erros experimentais. Nestes casos a ideia
é aproximá-los dos valores dos w − 1 vizinhos mais próximos de
5.1 Modelação
59
forma ponderada pelos pesos (quanto mais próximo o vizinho, mais
relevante é o seu valor para o cálculo).
• Discretização: estão disponíveis para selecção 15 técnicas distintas.
O utilizador poderá seleccionar qualquer uma delas, introduzindo
o parâmetro de discretização exigido (no caso de técnicas que usam
parâmetros).
Módulo de aplicação de algoritmos de biclustering e cálculo de funções
biológicas dos biclusters encontrados
Figura 5.5: Diagrama de casos do módulo de aplicação de algoritmos de biclustering e
cálculo de funções biológicas dos biclusters encontrados.
Este módulo permite aplicar um determinado algoritmo de biclustering
a uma matriz de dados e, em simultâneo, gerar a informação sobre as
funções biológicas dos biclusters identificados pelo algoritmo.
60
A Ferramenta BiGGEsTS
Nesta funcionalidade o utilizador poderá seleccionar o algoritmo de
biclustering que pretende aplicar, inserindo os parâmetros que lhe correspondem. Os algoritmos CCC-Biclustering e e-CCC-Biclustering aceitam
apenas matrizes de valores discretos, pelo que apenas ficam disponíveis
quando uma matriz discretizada é seleccionada na árvore de dados. Ambos oferecem a hipótese de considerar gene shifts.
O algoritmo CCC-Biclustering permite ainda seleccionar a inclusão de
genes com padrões simétricos e/ou de genes cujos padrões de expressão
surgem com um determinado atraso (time-lag) em relação aos restantes.
Nenhuma destas duas opções (ou ambas) pode(m) ser utilizada(s) em
simultâneo com gene shifts.
Os parâmetros para o algoritmo e-CCC-Biclustering incluem, adicionalmente: o número de erros permitido no padrão de expressão de cada
gene de um bicluster e a possibilidade de considerar erros restritos ou erros
gerais. Os erros gerais permitem a substituição de um (ou mais, dependendo do número de erros permitido) símbolo(s) do padrão de expressão
do bicluster por qualquer outro símbolo do alfabeto de discretização, enquanto os erros restritos apenas permitem a substituição de um (ou mais)
símbolo(s) por um dos k símbolos lexicograficamente mais próximos no
alfabeto. O valor de k é introduzido pelo utilizador.
O algoritmo CC-TSB-Biclustering só fica disponível quando a matriz
seleccionada na árvore é uma matriz original ou pré-processada sem valores em falta. Os parâmetros a introduzir são: α, o limite máximo para a
razão entre a MSR (mean-squared residue) da linha e a MSR da submatriz; δ,
o limite superior para a MSR do bicluster; o número de biclusters a extrair e
o número máximo de iterações para optimização dos biclusters.
A análise de funções biológicas potencialmente relevantes utiliza os
identificadores dos genes que integram os vários biclusters (como referimos anteriormente, considera-se que os biclusters representam possíveis
processos biológicos relevantes) e compara-os com os identificadores dos
genes conhecidos e anotados na Gene Ontology - projecto que procura
manter uma descrição consistente nos nomes e funções de genes descobertos e estudados pelos biólogos - para o organismo específico ao qual
os genes pertencem. A esses genes estão atribuídas determinadas funções
ou tarefas biológicas. Após uma análise estatística que compara o número
de genes na matriz original, o número de genes da matriz original que
desempenham uma tarefa específica, o número de genes no bicluster e o
número de genes no bicluster reconhecidos na Gene Ontology como desem-
5.1 Modelação
61
penhando tal tarefa, são calculados valores estatísticos (p-values calculados
usando uma distribuição hipergeométrica e corrigidos com a correcção de
Bonferroni para testes múltiplos) que indicam a relevância biológica do
bicluster segundo a Gene Ontology.
A análise de funções requer dois ficheiros de dados, um com todos os
termos classificados na Gene Ontology e outro específico para o organismo
em análise. Para proceder à análise de funções, o utilizador deverá indicar
o caminho para estes ficheiros no sistema local de ficheiros. Poderá também
efectuar o download a partir do site da Gene Ontology, caso os ficheiros
não existam ou pretenda actualizá-los. O outro parâmetro necessário é o
valor limite para o p-value que indica a relevância das funções biológicas.
Funções que apresentam um p-value corrigido pelo método de Bonferroni
igual ou inferior ao introduzido pelo utilizador, serão consideradas funções
relevantes.
Caso os ficheiros não existam no sistema local e/ou não possam ser descarregados, é possível aplicar apenas o algoritmo de biclustering e realizar
a análise de funções relevantes numa fase posterior.
Módulo de análise e visualização
A análise de dados de expressão genética engloba um conjunto interessante
de visualizações diversas que têm como objectivo facilitar a análise de
dados que, pela sua natureza (valores reais com várias casas decimais) e
elevada quantidade, dificultam a inferência de conclusões (ver Figura 5.6).
As funcionalidades disponíveis neste módulo permitem a análise de:
• Matrizes de valores - apresentam os valores reais de expressão de
matrizes originais e pré-processadas e de biclusters com valores reais.
Esta visualização também é permitida nas matrizes discretas e nos biclusters gerados a partir de matrizes discretas sendo que, nestes casos,
os valores apresentados correspondem aos valores da matriz original
ou pré-processada que deu origem à matriz de valores discretos.
• Matrizes de valores coloridas - apresentam matrizes coloridas em
função dos seus valores reais. As células são coloridas de acordo
com os respectivos valores de expressão que contêm. A visualização
de matrizes de valores coloridas está disponível para os mesmos tipos
de matrizes da análise de matrizes de valores.
62
A Ferramenta BiGGEsTS
Figura 5.6: Diagrama de casos do módulo de análise e visualização.
• Matrizes de símbolos coloridas - apresentam matrizes coloridas em
função dos seus símbolos. As células são coloridas de acordo com os
respectivos símbolos discretos que contêm. Esta visualização permite
mostrar matrizes discretas e biclusters com valores discretos.
A análise de matrizes para grupos de biclusters, seja ela de valores
reais, valores coloridos ou símbolos coloridos, permite mostrar as matrizes
de todos os biclusters. Por omissão são apresentados os cinco primeiros
biclusters. No entanto, o utilizador tem a possibilidade de seleccionar o
número de biclusters que pretende visualizar.
• Dendrogramas. Os dendrogramas apresentam a hierarquia de clusters que resulta da aplicação de um algoritmo de clustering hierárquico sobre uma determinada matriz de expressão genética. Só são
elegíveis para a visualização do dendrograma matrizes originais, préprocessadas e discretas (neste caso usando a matriz que foi utilizada
5.1 Modelação
63
pelo algoritmo de discretização). O BiGGEsTS tem implementadas
quatro técnicas de clustering hierárquico distintas (centroid-linkage,
single-linkage, complete-linkage e average-linkage clustering), que podem
ser aplicadas com uma de cinco medidas de similaridade (correlação
descentrada, de Pearson, descentrada absoluta, de Pearson absoluta,
de Spearman, de Kendall, distância euclidiana ou cityblock).
Após a selecção dos parâmetros, o clustering hierárquico é aplicado
sobre os dados e os resultados são apresentados numa nova janela.
A janela, Java TreeView [20], inclui vários painéis que mostram a
matriz de expressão colorida, as linhas hierárquicas que indicam os
genes e/ou as condições incluídas nos vários clusters e que, ao serem
seleccionadas, provocam o aparecimento do cluster individual num
dos painéis de visualização. São também incluídos os nomes dos
genes/condições que pertencem ao cluster em análise.
O Java TreeView [20] disponibiliza ainda diversas opções de personalização e utilitários como: o controlo do tamanho dos pixéis e das
cores utilizadas na matriz, a pesquisa de genes e de condições, a
exportação para ficheiros de texto e imagem, entre outras.
• Gráficos de expressão dos genes de um bicluster nos respectivos instantes temporais. É possível ver os gráficos de expressão de biclusters
individuais ou grupos de biclusters. Para os biclusters individuais o
utilizador pode optar por normalizar o gráfico de expressão enquanto
este lhe é apresentado. O painel correspondente à visualização de
grupos de biclusters mostra as miniaturas dos gráficos de expressão
dos biclusters individuais que integram o grupo. Por omissão são
apresentados os 12 primeiros biclusters, valor que o utilizador pode
modificar em qualquer altura, durante a visualização dos gráficos.
• Gráficos de expressão dos genes de um determinado bicluster individual (grupos de biclusters não são permitidos) em todas as condições da experiência, e não apenas nas condições do bicluster.
• Gráficos do padrão de expressão de um determinado bicluster para
as condições que o integram. Esta visualização só é permitida para
biclusters que possuam valores discretos. A análise de gráficos de
padrão de expressão está ainda disponível para grupos de biclusters
64
A Ferramenta BiGGEsTS
em condições semelhantes às dos gráficos de expressão dos genes de
um bicluster nos respectivos instantes temporais.
Todos os gráficos, excepto as miniaturas, permitem ampliar pontos
de interesse, imprimir e exportar como imagem no formato PNG. Estas
funcionalidades estão disponíveis a partir de um menu (context menu)
acedido através do botão direito do rato.
• Tabelas de funções biológicas relevantes para biclusters e grupos
de biclusters. As tabelas de funções dos biclusters individuais apresentam os identificadores e termos utilizados na Gene Ontology para
classificação de todos os genes que compõem o bicluster, bem como
os p-values calculados (da forma anteriormente referida) e a marcação
das funções biológicas potencialmente relevantes. A visualização das
funções para os grupos de biclusters apresenta uma tabela com estatísticas gerais tais como os números de genes e condições de cada um
dos biclusters que constituem o grupo, os p-values calculados e o número de funções biológicas potencialmente relevantes para cada um
deles (uma função biológica é considerada potencialmente relevante
se o p-value correspondente for inferior ou igual a um determinado
limite definido pelo utilizador, 0.01 por omissão). O utilizador tem a
oportunidade de recalcular os valores utilizando um limite diferente
do que foi usado para os valores apresentados. No caso de a análise
de funções não ter sido calculada anteriormente, é possível calculá-la
no painel de funções relevantes.
• Grafo de funções biológicas significativas, disponível apenas para
biclusters cuja análise de funções tenha revelado funções significativas. O gráfico apresenta os termos das funções significativas do
bicluster representados segundo a hierarquia da Gene Ontology sob a
forma de um grafo dirigido. Existem duas funcionalidades adicionais que permitem ao utilizador ampliar ou reduzir o tamanho do
grafo e exportá-lo nos formatos PNG e SVG.
Módulo de pós-processamento
O pós-processamento permite aplicar filtragem e/ou ordenação de biclusters
sobre um determinado grupo de biclusters (ver Figura 5.7). Ambas são
realizadas utilizando métricas que calculam a coerência dos valores reais
5.1 Modelação
65
Figura 5.7: Diagrama de casos do módulo de pós-processamento.
no bicluster ou a significância estatística de encontrar um bicluster com
determinado número de genes e determinado padrão, por exemplo (para
isso utiliza-se a hipótese nula que descreve a probabilidade de encontrar
um padrão com determinado tamanho, calculada usando a cauda de uma
distribuição binomial).
Enquanto a filtragem consiste em gerar um novo grupo de biclusters
excluindo todos os que não cumpram os requisitos especificados, a ordenação procede à geração de um novo grupo reorganizando os biclusters do
grupo original de acordo com a ordem estabelecida para a(s) métrica(s) em
causa.
Para a filtragem podem ser considerados os seguintes critérios: biclusters triviais (com apenas um gene e/ou uma condição), número de genes,
número de condições, variância média das linhas (ARV), variância média
das colunas (ACV), média dos quadrados dos resíduos (MSR), tamanho do
bicluster, sobreposição de genes, sobreposição de genes e condições, biclusters com padrão de expressão constante. Alguns destes critérios podem
ser combinados (ver Figura 5.8).
Os biclusters podem ser ordenados por: variância média das linhas
66
A Ferramenta BiGGEsTS
Figura 5.8: Diagrama de casos da selecção do critério de filtragem, no módulo de pósprocessamento.
(ARV), variância média das colunas (ACV), média dos quadrados dos
resíduos (MSR), diferença entre a variância média das linhas (ARV) e a
variância média das colunas (ACV), diferença entre a ARV e a MSR, número de genes, número de condições, tamanho, variância, melhor p-value,
melhor p-value corrigido, melhor p-value para o padrão do bicluster, melhor
p-value corrigido para o padrão do bicluster com colunas (ver Figura 5.9).
5.1 Modelação
67
Figura 5.9: Diagrama de casos da selecção do critério de ordenação, no módulo de pósprocessamento.
5.1.2
Estrutura
A modelação da estrutura consiste na definição das várias classes necessárias à implementação das funcionalidades referidas na modelação de requisitos e desenho da aplicação. A estrutura do BiGGEsTS é apresentada
em diversos diagramas de classes compilados num CD-ROM distribuído
com o presente relatório.
5.1.3
Arquitectura
A modelação da arquitectura promove a organização das classes implementadas/utilizadas em vários pacotes ou componentes, definidos se-
68
A Ferramenta BiGGEsTS
gundo critérios estruturais ou funcionais. A arquitectura da ferramenta
Figura 5.10: Diagrama de pacotes da ferramenta BiGGEsTS. No centro, o pacote que
implementa a interface gráfica - applicationgui.gui; em volta, as suas dependências.
BiGGEsTS inclui os pacotes construídos de raiz durante a fase de desenvolvimento do projecto e pacotes externos que foram utilizados para implementar algumas funcionalidades específicas (ver Figura 5.10). Destacamos
então os seguintes componentes arquitecturais:
• biggests.gui contém todas as classes que definem a interface com o
utilizador e o comportamento geral da aplicação (painéis, janelas,
threads).
• biggests.tree inclui as classes que definem a estrutura base da árvore
de dados e resultados.
• biggests.tables integra todas as tabelas, modelos de ordenação de
tabelas e tipos de cabeçalhos de tabelas utilizados pelos painéis de
visualização.
5.1 Modelação
69
• biggests.clustering concentra as classes que implementam algoritmos
de clustering e as respectivas estruturas de dados.
• biggests.utils engloba algumas classes que não fazem propriamente
parte da interface com o utilizador, mas que permitem implementar
determinados pormenores específicos (utilitários para auxiliar em
determinadas tarefas ou complementar componentes utilizados na
interface com o utilizador).
• smadeira.biclustering inclui todas as classes que definem os tipos
de matrizes, grupos de biclusters e biclusters individuais, bem como
a implementação das técnicas de pré-processamento e discretização,
algoritmos de biclustering e também a interpretação e armazenamento
dos dados resultantes da análise de funções (a figura 5.11 apresenta
as dependências do pacote smadeira.biclustering).
Figura 5.11: Diagrama de pacotes centrado no pacote smadeira.biclustering.
• de.schlichterle.io inclui componentes para a compressão, descompressão e manipulação de ficheiros comprimidos com suporte para
diversos algoritmos.
70
A Ferramenta BiGGEsTS
• org.jfree.chart (e derivados) e org.jfree.data.category, cujas classes
permitem definir os vários tipos de gráficos de expressão incluídos
na aplicação.
• org.apache.batik.swing.svg contém as classes que possibilitam a interpretação e integração de documentos SVG em componentes de
visualização gráfica.
• smadeira.ontologizer, classes de definição e processamento dos dados estatísticos gerados pela análise de funções.
• edu.stanford.genetics.treeview integra diversos componentes de interface gráfica com o utilizador e visualização de clusters que permitem a apresentação de dendrogramas a partir dos ficheiros CDT, ATR
e GTR produzidos pelo algoritmo de clustering hierárquico, descrevendo a estrutura da árvore de clusters resultante.
Os restantes pacotes utilizados são nativos do Java e incluem, sobretudo, componentes gráficos (javax.swing), classes para manipulação de
streams de dados (java.io), utilitários como colecções de dados (java.util) e
também classes de geometria, que permitem aplicar transformações sobre
rendering de gráficos a duas dimensões (java.awt.geom).
5.2 Implementação
A implementação foi desenvolvida em Java, utilizando o IDE Borland
JBuilder 2006 Enterprise Edition. A selecção desta ferramenta deveu-se
às poderosas funcionalidades de visualização prévia dos componentes
gráficos e geração automática de código para tratamento de eventos, bem
como à possibilidade de visualização directa das relações entre classes e
pacotes e da documentação Javadoc produzida, geração de executáveis,
entre outras.
Ao longo da implementação foram tomadas diversas decisões, na maioria das vezes relacionadas com a redução do atrito na interface com o
utilizador e com a maximização da eficiência. Esta (eficiência) constituiu
uma linha de preocupação constante ao longo de todo o desenvolvimento,
não só porque as experiências com microarrays permitem efectuar medições
de níveis de expressão em milhares de genes, mas também porque se pretendia que o BiGGEsTS permitisse carregar diversos conjuntos de dados de
5.2 Implementação
71
expressão genética de dimensões semelhantes, manipulá-los gerando novas matrizes com dimensões também idênticas e aplicar-lhes algoritmos
de biclustering que, tipicamente, extraem grupos de milhares de biclusters. Como se poderá concluir, a quantidade de dados manipulada pela
ferramenta é considerável, o que representou um esforço no sentido de
optimização da capacidade de processamento e utilização de memória.
Nesta secção apresentamos apenas os pormenores de implementação
relativos aos módulos desenvolvidos ou alterações efectuadas durante o
segundo semestre lectivo.
5.2.1
Carregamento de dados
O carregamento de dados foi completamente reformulado para permitir
uma maior flexibilidade e robustez na leitura de dados dos ficheiros de
texto. O painel de carregamento é agora mais amigo do utilizador, apresentando uma tabela com a visualização prévia dos dados contidos no
ficheiro. A tabela é actualizada automaticamente sempre que há uma alteração no caminho do ficheiro de dados indicado, o que, apesar de menos
eficiente, torna a utilização da aplicação mais agradável e intuitiva para
o utilizador. A pré-visualização dos dados resulta de uma análise por
parte do sistema, com o objectivo de identificar os nomes das condições,
os nomes dos genes e os valores de expressão da matriz a carregar. Estes
três tipos de elementos são assinalados a verde, amarelo e cor-de-rosa, respectivamente. É o próprio sistema que selecciona o delimitador de dados
adequado à leitura de cada ficheiro, de entre os vários que a aplicação
suporta.
Com o tipo de análise implementado, é possível carregar dados a partir
de um ficheiro que contém, por exemplo, algumas linhas com outro tipo
de informação antes do conjunto de dados, várias linhas com nomes de
condições ou várias colunas com nomes de genes. Nestes casos é o utilizador quem decide qual a coluna e/ou linha a utilizar. A técnica usada
permite também a geração automática de nomes de genes ou condições,
caso estes não se encontrem presentes no ficheiro de dados.
Dada a multiplicidade de sistemas de identificação de genes existentes
(Ensembl, Entrez, UniGene, Affymetrix, etc.) e também a possibilidade de
os nomes dos genes contidos no ficheiro não pertencerem a nenhum deles,
tendo sido atribuídos pela equipa que realizou a experiência, decidimos
72
A Ferramenta BiGGEsTS
delegar ao utilizador a responsabilidade de fornecer um ficheiro com a
conversão entre os identificadores usados na experiência e os identificadores correspondentes, usados pela Gene Ontology nos ficheiros de anotação.
Desta forma, a conversão é sempre garantida, qualquer que seja o sistema
de identificação dos genes na experiência.
O leque de organismos suportados pela aplicação foi alargado a todos
os organismos que possuem ficheiros de anotação para os seus genes na
Gene Ontology, possibilitando uma maior abrangência na utilização do
BiGGEsTS.
5.2.2
Integração do algoritmo CC-TSB-Biclustering
No final do primeiro semestre, o BiGGEsTS tinha integrados dois algoritmos de biclustering que podiam ser aplicados apenas a matrizes de valores
discretos (CCC-Biclustering e e-CCC-Biclustering). Com a introdução do
algoritmo CC-TSB-Biclustering, a ferramenta passou a poder extrair biclusters a partir de matrizes de valores reais (originais ou pré-processadas, sem
valores em falta). Dada a modularidade da aplicação, esta integração não
implicou alterações profundas, apenas extensões do trabalho que já havia
sido realizado, especialmente na visualização dos gráficos de expressão e
das matrizes de expressão dos biclusters.
5.2.3
Download de ficheiros da Gene Ontology
Os ficheiros com a ontologia dos genes e as anotações para os diferentes
organismos podem agora ser descarregados do site da Gene Ontology.
Esta funcionalidade está disponível no painel de biclustering e no painel de
análise de funções biológicas relevantes. É permitido ao utilizador realizar
o download do ficheiro de ontologia ou do ficheiro de anotações para o
organismo em causa, de forma independente. O ficheiro com a ontologia
dos genes é sempre o mesmo para todos os organismos, apenas o ficheiro
de anotações varia. Na operação de download, o sistema identifica o ficheiro
que deve descarregar, faz a ligação ao site da Gene Ontology através do
URL do respectivo ficheiro e descarrega-o para a directoria de ficheiros da
Gene Ontology no sistema de ficheiros local, descompactando-o.
Nos casos em que o ficheiro alvo da operação de download já existe
na directoria mencionada, a aplicação substituirá a versão existente pela
5.2 Implementação
73
nova, mais actualizada. Se o descarregamento falhar, por qualquer motivo,
os ficheiros que já existiam são repostos e a aplicação poderá continuar a
utilizá-los.
5.2.4
Threads e barras de progresso
O download de ficheiros da Gene Ontology, a aplicação dos algoritmos de
biclustering e a análise de funções biológicas relevantes são operações que
consomem bastante tempo, deixando o utilizador sem qualquer feedback
ou possibilidade de interacção / controlo sobre a aplicação. Como solução,
o BiGGEsTS passou a realizar estas tarefas através de threads de execução
independente, apresentando, simultaneamente, uma barra de progresso
com informação sobre as fases intermédias concluídas.
Para cada tarefa de longo curso é criada uma nova thread, que executa
de forma independente da thread de execução principal, impedindo assim
a paralisação da aplicação. À medida que a tarefa vai sendo realizada, a
thread vai actualizando a informação na barra de progresso. Para um maior
controlo do utilizador sobre a aplicação, incluímos também a possibilidade
de abortar a tarefa de longo curso, através de um botão para o efeito na
janela da barra de progresso.
5.2.5
Pós-processamento
A implementação da filtragem e ordenação de biclusters, designadas em
geral como operações de pós-processamento, introduziu dois novos conceitos em relação aos definidos no relatório do primeiro semestre: biclusters
pós-processados e grupos de biclusters pós-processados. Na realidade, as
classes destes tipos de objectos são exactamente as mesmas que as que definem os biclusters e os grupos de biclusters extraídos pelos algoritmos. No
entanto, o conceito em si é diferente, pois os homónimos pós-processados
não resultam da extracção directa de um algoritmo de biclustering, mas
de uma operação de pós-processamento sobre os biclusters originais (que
poderão ter sido directamente extraídos por um algoritmo de biclustering
ou constituir, eles mesmos, biclusters pós-processados).
O pós-processamento aplica-se a grupos de biclusters, não operando
qualquer modificação sobre os biclusters individuais em si, mas apenas sobre a estrutura do grupo. Isto significa que o grupo pós-processado poderá
74
A Ferramenta BiGGEsTS
ter um menor número de biclusters ou os biclusters ordenados de forma distinta, sendo que cada um dos biclusters finais corresponde exactamente a
um dos biclusters originais. No grupo de biclusters resultante cada bicluster
mantém o identificador do bicluster original, entre parêntesis. No entanto,
para uma melhor navegação na árvore de dados e resultados, bem como
nos gráficos de expressão e nas tabelas de funções biológicas relevantes,
os nodos dos biclusters pós-processados apresentam uma nova numeração
automática atribuída de forma sequencial, mantendo o identificador dos
biclusters originais entre parêntesis. A numeração sequencial torna a tarefa
de pesquisa mais fácil e rápida, sobretudo nos casos em que a ordem dos biclusters foi alterada. O identificador entre parêntesis possibilita um rápido
relacionamento do bicluster pós-processado com o bicluster que lhe deu
origem, tornando-se particularmente útil no caso em que um determinado
grupo de biclusters sofre pós-processamentos sucessivos. Nesta situação,
qualquer bicluster pós-processado da cadeia mencionada que apresente,
por exemplo, o identificador 24 entre parêntesis é exactamente o mesmo
que o bicluster original com o identificador 24.
5.2.6
Gestão de sessões
O BiGGEsTS permite ao utilizador gravar a sua sessão para, posteriormente, restaurar e continuar o seu trabalho a partir do ponto em que se
encontrava. A sessão é gravada da seguinte forma: o sistema cria um ficheiro binário designado tree.big em que guarda a árvore de dados (todos
os objectos são serializados e escritos no ficheiro como sequências de bytes)
e o caminho na árvore para o nodo seleccionado no momento da gravação
da sessão. Finalmente, cria um arquivo ZIP com o nome e caminho indicados pelo utilizador. Este arquivo inclui o ficheiro tree.big e a directoria
Function_Results (bem como o seu conteúdo), onde a aplicação mantém
os ficheiros no formato DOT com a estrutura dos grafos de resultantes da
análise de funções relevantes. Finalmente, ficheiro tree.big é eliminado do
sistema de ficheiros local.
Para restaurar uma sessão o sistema acede ao respectivo arquivo, descompacta a directoria Function_Results para o caminho associado à aplicação e lê a árvore de dados do ficheiro tree.big desserializando-a e construindo assim a árvore na aplicação. Lê também o caminho para o nodo
seleccionado no momento da gravação e instancia-o na árvore.
5.2 Implementação
75
A implementação da gestão de sessões implicou que todas as classes
cujos objectos fossem escritos/lidos para ficheiros tivessem que passar a
implementar a interface Serializable. A preferência sobre o formato de ficheiros a utilizar recaiu sobre o binário, em detrimento do formato de texto,
pois o número de dados a escrever/ler pode ser considerável e o formato
binário permite maior eficiência em todo o processo, dado que os ficheiros de texto requerem sempre uma interpretação/parsing dos dados (entre
outros processos morosos).
5.2.7
Informação
Quando o utilizador selecciona um determinado nodo da árvore de dados,
o sistema apresenta um sumário informativo do conteúdo desse nodo, isto
é, todos os detalhes relevantes sobre a matriz, bicluster ou grupo de biclusters
em causa. Das informações constam, por exemplo, o número de genes e o
número de condições, o nome do nodo que contém a matriz/bicluster/grupo
de biclusters que lhe deu origem, tipos de pré-processamento, biclustering
e/ou análise de funções efectuados sobre os dados, etc.
A introdução deste resumo informativo originou a inclusão de dois atributos adicionais na classe NodeInfo, utilizada para armazenar a informação
sobre o objecto (matriz, bicluster, grupo de biclusters) contido em cada nodo.
O primeiro contém um conjunto de strings com as próprias informações.
O segundo engloba o conjunto de formatações para as strings incluídas no
primeiro, de modo a que a caixa de texto (da classe JTextPane) que as recebe
possa saber qual a formatação adequada para cada informação.
5.2.8
Gráficos de expressão e padrão de expressão
Os métodos que constroem os gráficos de expressão e de padrão de expressão foram reformulados, de forma a suportar os novos tipos de biclusters:
biclusters com padrões de expressão simétricos (sign changes) e biclusters
com atrasos (time-lags).
Nos primeiros, apenas os gráficos do padrão de expressão sofreram
alterações, uma vez que é necessário agora incluir dois padrões: o original
e o simétrico. Na legenda dos gráficos aparecem, para cada padrão, os
respectivos nomes dos genes que lhe estão associados.
Nos gráficos dos biclusters com atrasos, tanto os gráficos de expressão
76
A Ferramenta BiGGEsTS
como os de padrão são agora construídos de modo distinto, pois apesar
de todos os genes apresentarem uma evolução de expressão coerente ou
o mesmo padrão de expressão, a condição inicial (e, consequentemente,
todas as outras condições) pode(m) variar de gene para gene, o que implica
a sua verificação e desenho correspondente.
Existe também a possibilidade de combinação de biclusters com padrões
de expressão simétricos e atrasos, o que implica a satisfação em simultâneo
de todas as condições acima descritas.
5.2.9
Clustering hierárquico e dendrogramas
A implementação do clustering hierárquico foi referida no Capítulo 4, Secção 4.2, e consistiu numa reprogramação em Java dos algoritmos integrados no software Cluster 3.0 [6] e na biblioteca de clustering [5], cujo código
fonte se encontrava em linguagem C. Na adaptação dos algoritmos procurámos minimizar as alterações introduzidas, de modo a que a execução
global se assemelhasse, não esquecendo no entanto a diferente estrutura do
Java e o aproveitamento das suas potencialidades (classes, objectos, atributos de classe - estáticos - e de instância, métodos de classe e de instância,
polimorfismo, entre outras).
Na definição final subsistiram três classes distintas: HierarchicalClustering, ClusterTreeNode e ClusterTreeNodeComparator.
A primeira consiste na classe principal, que recebe e armazena os dados
de expressão genética a processar, produz dados auxiliares e permite aplicar os algoritmos de clustering hierárquico, devolvendo a árvore com a hierarquia de clusters resultante ou escrevendo a sua estrutura para ficheiros
CDT 1 , ATR 2 e GTR 3 . A classe HierarchicalClustering pode receber os dados
tanto de forma individualizada (número de genes, número de condições,
nomes dos genes, nomes das condições, matriz com os dados de expressão, matriz com a máscara de valores em falta, ordem dos genes, ordem
das condições, índices dos genes, índices das condições, pesos dos genes,
1
Ficheiro gerado pelo algoritmo de clustering hierárquico. Contém os nomes dos genes
e das condições, bem como os respectivos pesos e os valores de expressão genética
2
Tipo de ficheiro gerado pelo algoritmo de clustering hierárquico quando aplicado sobre
as condições da matriz de dados de expressão genética. Contém a estrutura hierárquica
dos nodos resultantes.
3
Tipo de ficheiro gerado pelo algoritmo de clustering hierárquico quando aplicado sobre
os genes da matriz de dados. Contém a estrutura hierárquica dos nodos resultantes.
5.3 Finalização e Divulgação
77
pesos das condições), como através de objectos de tipo ExpressionMatrix
(matrizes originais na aplicação BiGGEsTS), PreProcessedExpressionMatrix
(pré-processadas) ou DiscretizedExpressionMatrix (matrizes discretas).
O tipo ClusterTreeNode define um nodo da árvore de clusters, caracterizado por um filho esquerdo, um filho direito e uma distância (medida de
similaridade) entre os dois.
Finalmente, a classe ClusterTreeNodeComparator implementa a interface
Comparator para o tipo de dados ClusterTreeNode, fornecendo métodos para
comparação de objectos deste tipo e definindo assim uma ordem sobre os
elementos desse conjunto.
5.3
Finalização e Divulgação
A fase de finalização consistiu essencialmente na preparação do BiGGEsTS
para a sua distribuição e divulgação e incluiu tarefas como a produção
de executáveis nativos para Windows, Linux e Mac OS X, a criação de
instaladores para automatizar o processo de instalação nesses mesmos
sistemas operativos, a selecção de uma licença de utilização e distribuição
para a aplicação e do seu código-fonte, bem como a criação de uma imagem
e de um site para divulgação e a respectiva documentação.
5.3.1
Executáveis
A criação dos executáveis foi assistida pelo JBuilder. Num primeiro passo
criámos um arquivo executável JAR com a seguinte configuração:
• Inclusão de todas as classes e recursos para todas as dependências.
• Indicação da classe com o método main.
• Parametrização da máquina virtual, com os seguintes valores.
• Compressão do arquivo.
Com as configurações descritas produzimos os executáveis nativos para
Windows, Linux e Mac OS X, a partir do executável JAR.
A parametrização da máquina virtual constituiu um processo cuidadoso, com vários testes ao comportamento da aplicação sobre várias configurações distintas. Antes de apresentarmos e justificarmos a selecção dos
78
A Ferramenta BiGGEsTS
parâmetros para a máquina virtual de Java, faremos uma breve referência aos conceitos de pilha (stack), heap, geração jovem e geração estável,
imprescindíveis à compreensão do funcionamento básico de um garbage
collector.
Pilha (stack)
Alocação linear de memória: a memória é alocada em fila ou em pilha.
Não permite a remoção de objectos fora da ordem de criação. O Java usa
alocação linear para procedimentos sequenciais. Cada thread tem associada uma pilha para armazenar variáveis locais e resultados parciais. A
memória usada pela pilha pode ser alocada na heap, não precisa de ser
contígua e é libertada automaticamente depois de utilizada. Pode ter um
tamanho fixo ou expandir-se e reduzir-se na medida do necessário.
Heap
Alocação dinâmica de memória: permite liberdade de criação e remoção
em ordem arbitrária. Requer uma gestão complexa do espaço ocupado. O
Java usa alocação dinâmica para objectos. Heap é a área de dados onde
todas as instâncias e vectores são alocados. É criada quando a máquina
virtual inicia a sua execução e compartilhada por todas as threads. O espaço
de objectos é reciclado por um sistema de gestão de memória (garbage
collector). No caso do BiGGEsTS, a heap tem um tamanho variável limitado
por valores máximo e mínimo.
Gerações
As gerações são áreas da heap que se baseiam na classificação dos objectos
segundo o seu ciclo de vida e nas seguintes observações:
• Se um objecto se mantém alcançável por um longo período de tempo,
é provável que continue assim.
• A maior parte dos objectos "morre"pouco tempo depois da sua criação.
• Referências de objectos antigos para objectos novos são pouco frequentes.
5.3 Finalização e Divulgação
79
Estas permitem concluir que um garbage collector será mais eficiente se
analisar os objectos mais jovens com mais frequência do que os objectos
mais antigos/estáveis. Praticamente todas as implementações actuais de
garbage collection usam a abordagem geracional para a gestão da memória.
Geração jovem (Young generation)
Área menor da heap, em que é inicialmente alocada a memória para novos
objectos, excepto nos casos em que o espaço não é suficiente.
Geração estável (Tenured generation)
Área maior da heap para onde são copiados objectos que sobrevivem a uma
ou mais garbage collections na área menor.
Parametrização
Em Java a gestão de memória é fundamentalmente automática e realizada pelo garbage collector. O programador não tem a responsabilidade ou
possibilidade de gerir a memória do sistema explicitamente, dado que a
alocação e libertação são realizadas segundo algoritmos previamente definidos. No entanto, é possível ajustar o comportamento ou seleccionar
quais os algoritmos a utilizar para adaptar a gestão de memória à especificidade da aplicação desenvolvida. No BiGGEsTS procurámos optimizar
a combinação de parâmetros para obter um equilíbrio entre a utilização
da memória e o tempo dispensado para garbage collection. A configuração
final foi a seguinte:
Xss5M (tamanho da pilha para cada thread: 5 MB)
Xms100M (tamanho mínimo da heap: 100 MB)
Xmx800M (tamanho máximo da heap: 800 MB)
Dado que a utilização de memória é considerável, particularmente na
aplicação de algoritmos de biclustering, decidimos manter o tamanho máximo da heap bastante superior ao seu tamanho mínimo. Esta técnica
permite aumentar o número de chamadas ao garbage collector, já que é a diferença entre os valores máximo e mínimo que define o espaço disponível
para a geração estável de objectos (tenured generation). Se o valor mínimo
80
A Ferramenta BiGGEsTS
for semelhante ao máximo, o garbage collector não terá que executar tantas
vezes, pois o valor mínimo é atingido com alguma facilidade. O tamanho
máximo estipulado para a heap varia consoante a versão (existem versões
distintas para máquinas com memórias de diferentes capacidades).
O valor elevado para o tamanho da pilha de cada thread (5 MB) é
justificado pelas particularidades da implementação dos algoritmos de
biclustering: engloba vários métodos recursivos que envolvem a criação de
muitas variáveis locais ou resultados intermédios e, consequentemente,
provocam uma utilização extremamente intensiva da pilha.
Finalmente, optámos pela utilização do serial garbage collector que usa,
para a geração jovem, um colector de cópia em série, e para a geração
estável, o algoritmo mark-compact em série.
O primeiro, colector de cópia, divide a heap em duas áreas iguais, designadas origem e destino. Os objectos são alocados na área de origem e
quando o colector é executado, navega pelo conjunto de referências e copia
os objectos alcançáveis para a área de destino. Quando a cópia termina, os
espaços destino e origem trocam de função. Este algoritmo permite uma
cópia rápida, principalmente se a quantidade de objectos for reduzida, o
que é comum no caso da geração jovem. Para além disso não precisa de
percorrer a heap inteira, apenas os objectos alcançáveis, e não fragmenta
a memória. Entre as suas desvantagens contam-se: a necessidade de paragem da aplicação durante a execução do algoritmo (comum a todos os
algoritmos de garbage collection em série); a duplicação de memória necessária na heap, o que constitui um problema se a heap tiver um tamanho
elevado; e a utilização ineficiente da memória, uma vez que metade está
sempre vazia.
O algoritmo mark-compact rastreia os objectos da heap, marca os objectos
alcançáveis e remove os restantes, libertando memória e mantendo a heap
desfragmentada através de um algoritmo de compactação. Não causa
fragmentação da memória, a alocação é rápida e a performance não se
degrada com o tempo devido ao aumento das colectas. Por outro lado, o
algoritmo de compactação representa algum overhead, uma vez que requer
várias visitas.
5.3 Finalização e Divulgação
5.3.2
81
Instaladores
Os instaladores foram construídos com a aplicação BitRock InstallBuilder. Existem duas versões de instaladores. A única diferença entre ambas
reside no facto de uma incluir os ficheiros da Gene Ontology com a ontologia genética e as anotações para todos os organismos suportados pela
aplicação e a outra não. A decisão de oferecer dois instaladores distintos
foi motivada pelo espaço de armazenamento considerável requerido pelos ficheiros da Gene Ontology, dado que estes não são indispensáveis à
utilização do BiGGEsTS. Isto porque apenas são utilizados na análise de
funções biológicas relevantes e, mesmo nesse caso, se existir uma ligação
à Internet é possível realizar o seu download.
O instalador para Windows permite instalar todos os componentes
necessários à utilização imediata da ferramenta. A instalação processa-se
da seguinte forma:
• O instalador verifica a instalação prévia do BiGGEsTS no sistema
(caso exista outra versão, o utilizador é aconselhado a removê-la).
• O utilizador selecciona a linguagem de instalação.
• O instalador apresenta a licença de utilização e distribuição da aplicação.
• O utilizador indica o caminho para a directoria de instalação.
• O instalador extrai e dispõe os seguintes itens na directoria de instalação: executável da aplicação, directoria para os ficheiros da Gene
Ontology, directoria para os resultados da análise de funções biológicas relevantes, directoria para as sessões, directoria com o programa
dot do Graphviz e um ícone do BiGGEsTS; finalmente, cria um desinstalador e os atalhos do BiGGEsTS no menu Iniciar e no Ambiente
de Trabalho.
O instalador para Linux funciona de modo semelhante. As excepções
são a instalação do programa Graphviz-dot e a criação de atalhos. O código
fonte do Graphviz deverá ser descarregado a partir do respectivo site e
compilado para que possa, posteriormente, ser utilizado pelo BiGGEsTS
na apresentação dos grafos de funções biológicas relevantes. Existem no
mesmo site RPMs para algumas distribuições de Linux, que fornecem uma
82
A Ferramenta BiGGEsTS
instalação mais automatizada. O instalador realiza ainda uma operação
adicional, alterando as permissões de execução do BiGGEsTS, para que
este possa ser executado por todos.
Em Mac OS X, o instalador comporta-se de forma em tudo semelhante
ao instalador para Windows.
5.3.3
Licença
O BiGGEsTS utiliza diversas bibliotecas, pacotes ou programas de utilização gratuita e open source. Estes componentes de software são distribuídos
segundo os termos das licenças de utilização e distribuição que passamos
a citar:
Graphviz - Common Public License Version 1.0
TrueZip - Apache License Version 2.0, January 2004
HTTPUnit - Russel Gold License
Commons-Cli - Apache License Version 2.0, January 2004
Batik - Apache License Version 2.0, January 2004
JFreeChart - GNU Lesser General Public License Version 2.1, February
1999
Java Treeview - GNU General Public License
Após a leitura de todos os termos das licenças mencionadas, optámos por
distribuir o BiGGEsTS com a licença GNU General Public License (GNU
GPL), uma vez que nos permite abranger e verificar todos os termos das
outras licenças, protegendo simultaneamente os nossos direitos e os das
entidades distribuidoras daqueles componentes.
5.3.4
Imagem e logótipo
A imagem que produzimos para o BiGGEsTS pretende ser simultaneamente forte e simples (logótipo do BiGGEsTS na Figura 5.12). De certo
modo, caracteriza a aplicação desenvolvida pela sua robustez e eficiência,
aliada à utilização agradável e intuitiva. As cores seleccionadas foram o
5.3 Finalização e Divulgação
83
Figura 5.12: Logótipo do BiGGEsTS.
verde, o vermelho e o branco, sugestionadas pelas cores utilizadas nas
matrizes de valores de expressão utilizadas na análise de expressão genética. As formas foram também inspiradas nas mencionadas matrizes e são,
sobretudo, quadrangulares e rectangulares.
5.3.5
Documentação
A documentação do BiGGEsTS inclui um manual de utilizador e a documentação Javadoc para o programador no formato HTML, produzida
directamente a partir dos comentários no código.
5.3.6
Site
O site desenvolvido tem como objectivo a distribuição e divulgação do
BiGGEsTS à comunidade, funcionando também como o meio de interacção principal entre a equipa de desenvolvimento e os utilizadores ou
programadores interessados na ferramenta.
O layout do site foi inspirado na imagem que desenvolvemos previamente, de acordo com as cores e formas estipuladas (ver Figura 5.13).
Utilizámos XHTML para a definição do conteúdo geral, CSS para a sua
apresentação e também JavaScript para a implementação de alguns comportamentos dinâmicos. O site respeita ambas as normas XHTML e CSS e
suporta uma larga variedade de resoluções e browsers, incluindo navegação em dispositivos móveis (telemóveis e PDAs).
Quanto ao conteúdo, a página oferece oito áreas distintas:
Overview - apresenta uma introdução sobre a extracção de padrões em
séries temporais de expressão genética, algoritmos de biclustering e
sobre o próprio BiGGEsTS.
News - mantém um conjunto de notícias acerca da aplicação; é nesta área
que aparecem os anúncios sobre novas versões do software ou novos
84
A Ferramenta BiGGEsTS
Figura 5.13: Site do BiGGEsTS.
manuais disponibilizados, entre outros.
License - contém os detalhes e termos da licença de utilização e distribuição.
Download - consiste no repositório do software para download, com todas
as versões do BiGGEsTS, incluindo binários e código fonte, versões
para Windows, Linux e Mac OS X e versões com e sem ficheiros de
anotações da Gene Ontology.
Known Issues - divulga os problemas e bugs conhecidos do BiGGEsTS.
Documentation - disponibiliza a documentação das várias versões do
software, incluindo manuais de utilização, documentação Javadoc no
formato HTML, apresentações sobre o BiGGEsTS e artigos científicos,
entre outros.
People - apresenta a equipa de desenvolvimento do BiGGEsTS.
Contacts - divulga os meios de contacto da equipa de desenvolvimento e
suporte para utilizadores e programadores.
Capítulo 6
Estudo de Caso
Este capítulo apresenta uma demonstração de utilização da ferramenta
BiGGEsTS para manipulação, visualização e análise de séries temporais
de expressão genética. Os dados apresentados são provenientes de experiências biológicas reais com genes do organismo yeast (levedura).
6.1
Carregamento de Dados
Figura 6.1: Painel de carregamento de dados.
85
86
Estudo de Caso
O primeiro passo consiste no carregamento dos dados de expressão
genética para a aplicação (ver Figura 6.1). É necessário indicar o caminho
para o ficheiro de texto que contém os dados, o organismo a que correspondem, o tipo de ADN utilizado na experiência e o identificador dos genes.
Neste caso, o ficheiro de texto contém 1171 genes e 7 condições, pertence
ao organismo yeast, o ADN utilizado na experiência foi cDNA, os genes
estão identificados por gene IDs e os dados são delimitados por tabulações.
O ficheiro contém alguns valores em falta, que serão alvo de tratamento
posterior.
Após o carregamento dos dados, e dado que possuímos os ficheiros
de anotações necessários para o organismo yeast, o BiGGEsTS procede à
análise de funções sobre os genes da matriz original, pelo nos será possível
consultar também a tabela de funções.
6.2
Visualização de Matrizes
Após o carregamento bem sucedido, a aplicação comuta para a aba Analyzing e apresenta a matriz de valores colorida (ver Figura 6.2).
Figura 6.2: Matriz de valores original colorida.
A sua observação revela facilmente que os valores mais baixos da matriz apresentam uma coloração verde (de maior ou menor intensidade,
6.2 Visualização de Matrizes
87
consoante o valor real da célula), os valores mais elevados apresentam
uma coloração vermelha e os valores em falta são destacados a amarelo.
Figura 6.3: Matriz de valores original colorida e ordenada por ordem crescente da condição
t2 .
Figura 6.4: Matriz de valores original colorida e ordenada por ordem decrescente da
condição t2 .
88
Estudo de Caso
É possível ordenar a tabela segundo uma determinada coluna, pressionandoa. Os resultados das ordenações crescente e decrescente são ilustrados nas
Figuras 6.3 e 6.4, respectivamente.
O BiGGEsTS apresenta a matriz colorida como resultado do carregamento, pois este tipo de visualização permite, geralmente, uma observação
mais global dos dados. No entanto, é sempre possível aceder à matriz de
valores (original), através da aba Values acessível no extremo inferior da
janela (ver Figura 6.5).
Figura 6.5: Matriz original de valores. As células que cujos valores estão em falta são
coloridas a azul-escuro. A navegação com o rato por cima das células permite identificar
a linha, a coluna e o valor de cada célula em particular.
6.3
Dendrograma
Ainda no mesmo contexto, com a matriz original e as abas Analyzing e
Matrix seleccionadas, acedemos à aba Dendrogram. Aparecerá o painel que
permite seleccionar as opções para a aplicação do algoritmo de clustering
hierárquico sobre os dados. No nosso caso, seleccionámos como medida
de similaridade a correlação de Spearman e optámos pelo método completelinkage clustering (ver Figura 6.6).
6.3 Dendrograma
89
Figura 6.6: Painel de opções para o algoritmo de clustering hierárquico.
Figura 6.7: Janela do BiGGEsTS com a janela do Java TreeView sobreposta. O Java
TreeView apresenta o dendrograma resultante do algoritmo de clustering hierárquico
aplicado aos dados da matriz de expressão original.
Premindo o botão View Dendrogram, surge a janela do Java TreeView
com o dendrograma resultante do clustering hierárquico aplicado sobre os
dados (ver Figura 6.7). Se seleccionarmos um determinado cluster, através
90
Estudo de Caso
das linhas hierárquicas do painel mais à esquerda surge, no painel central,
o cluster correspondente em grande plano. Os nomes das condições do
cluster aparecem no painel central superior e os nomes dos genes no painel
da direita (Figura 6.7).
6.4
Tabela de Funções
Figura 6.8: Tabela de funções biológicas para os genes da matriz original.
A tabela de funções está disponível através das abas Analyzing, Function
e apresenta os termos para o organismo yeast, neste caso, bem como o
número de genes utilizados na experiência e anotados com esse termo. A
Figura 6.8 apresenta a visualização típica de uma tabela de funções para
uma matriz original, pré-processada ou discreta. Neste caso, a Figura 6.8
mostra a tabela de funções para a matriz de expressão original.
6.5
Pré-Processamento
O passo seguinte será o pré-processamento da matriz, demonstrado na
Figura 6.9.
6.5 Pré-Processamento
91
Figura 6.9: Painel com as opções de pré-processamento.
A filtragem de genes é obrigatória, uma vez que a matriz possui valores
em falta, que terão que ser eliminados ou preenchidos. Para tal, optámos
por seleccionar a opção de filtrar apenas os genes com mais de uma determinada percentagem de valores em falta, à qual atribuímos o valor 20 (%).
A selecção desta opção torna obrigatório o preenchimento dos restantes
valores em falta, os quais decidimos preencher com a média da linha em
que se encontram. Escolhemos não aplicar aos dados qualquer técnica de
normalização ou smoothing. Para a discretização seleccionámos a técnica
variations between time-points com 3 símbolos e um threshold igual a 1. (ver
Figura 6.9).
Da aplicação das técnicas de pré-processamento resultam duas novas
matrizes: uma pré-processada e outra discreta. A matriz pré-processada
corresponde à matriz original sem quaisquer valores em falta, enquanto a
discreta resulta da aplicação da discretização variations between time-points
de 3 símbolos sobre a matriz pré-processada. O BiGGEsTS apresenta-nos a
matriz discreta, na forma de uma matriz de símbolos colorida (ver Figura
6.10).
92
Estudo de Caso
Figura 6.10: Matriz discreta sob a forma de uma tabela de símbolos colorida. A navegação
do rato sobre as células permite identificar a linha, a coluna e o símbolo de cada célula em
particular.
6.6
Biclustering
Passemos então à aplicação de um algoritmo de biclustering sobre a matriz
discreta (ver Figura 6.11). As opções disponíveis, neste caso, correspondem aos algoritmos CCC-Biclustering e e-CCC-Biclustering. Optámos pelo
primeiro, sem utilização de gene shifts ou time-lags, mas activando a opção
sign changes para biclusters com padrões de expressão simétricos. Para
a respectiva análise de funções, o BiGGEsTS detectou automaticamente
a existência dos ficheiros da Gene Ontology necessários no sistema local,
que decidimos aproveitar. Aceitámos também o p-value a considerar por
omissão, com o valor de 0.01, e aplicámos então as opções aos dados.
O algoritmo CCC-Biclustering permitiu extrair 262 biclusters, que aparecem na árvore de dados (à esquerda na Figura 6.12). Na análise de
matrizes, temos acesso às matrizes de valores, matrizes de valores coloridas e matrizes de símbolos coloridas, tal como para a matriz discreta, uma
vez que cada bicluster não é mais do que uma submatriz da matriz discreta. Para o grupo de biclusters são apresentados os vários biclusters que o
compõem (por omissão apenas os primeiros 5, mas é possível alterar este
valor, seleccionando outro na caixa de selecção), como se pode observar
6.6 Biclustering
93
Figura 6.11: Painel com as opções para aplicação de algoritmos de biclustering e de análise
de funções biológicas.
na Figura 6.12.
Figura 6.12: Matriz de valores colorida para os cinco primeiros biclusters do grupo de
biclusters extraído pelo algoritmo CCC-Biclustering sobre a matriz discreta. Na Figura
vemos apenas o primeiro bicluster. Para ter acesso aos restantes é necessário mover a barra
de deslocação (à direita) para baixo.
94
6.7
Estudo de Caso
Gráficos de Expressão
Ainda para o grupo de biclusters, é possível visualizar as miniaturas dos
gráficos de expressão genética (Figura 6.13) ou do padrão de expressão
(Figura 6.14) de todos os biclusters do grupo. Os gráficos de expressão
genética permitem analisar a co-regulação ou co-expressão dos genes num
bicluster, isto é, verificar que os genes exibem uma sequência de actividade
semelhante ao longo dos instantes temporais em que se pensa poderem
estar a participar em conjunto num determinado processo biológico. Os
gráficos do padrão de expressão mostram, por sua vez, o padrão de expressão de um bicluster, ou seja, a sequência de símbolos partilhada por
todos os seus genes nos instantes temporais que lhe pertencem. De facto,
o padrão de expressão representa também a co-regulação dos genes do bicluster de uma forma relativa (neste caso específico, através de um alfabeto
de três símbolos - D, N e U - o alfabeto utilizado na discretização) e não
através de valores reais, como os gráficos de expressão genética.
Figura 6.13: Miniaturas dos gráficos de expressão dos 24 primeiros biclusters do grupo
de biclusters extraído pelo algoritmo CCC-Biclustering aplicado à matriz discreta.
Após a visualização global dos gráficos de expressão, considerámos
que o bicluster 10 teria um gráfico de expressão interessante, pelo que decidimos visualizá-lo em mais pormenor. Para tal, é necessário seleccionar
o bicluster pretendido e a respectiva aba Expression (ver Figura 6.15). O
6.7 Gráficos de Expressão
95
Figura 6.14: Miniaturas do padrão de expressão dos primeiros 96 biclusters do grupo
de biclusters extraído pelo algoritmo CCC-Biclustering aplicado à matriz discreta. Na
imagem são visíveis os biclusters com números entre o 45 e o 60.
primeiro gráfico a aparecer será o que representa os valores de expressão do bicluster para os genes e as condições que o integram (ver Figura
6.15). No gráfico é possível visualizar a coerência na evolução da expressão
dos genes. Salienta-se também o facto de um grupo de genes apresentar
uma evolução da expressão exactamente simétrica à dos restantes genes
(evoluções coerentes, mas simétricas). Nos casos em que a co-regulação
dos genes não é clara, é possível solicitar um novo gráfico com os valores
normalizados por gene (ver Figura 6.16).
A visualização do gráfico dos valores de expressão dos genes nas condições do bicluster origina algum interesse em visualizar o gráfico de expressão dos genes do bicluster em todas as condições da experiência e não
apenas nas condições do bicluster (Figura 6.17). O objectivo é permitir
a comparação da co-regulação dos genes nas condições do bicluster com
a não co-regulação dos mesmos genes nos instantes temporais que não
integram o bicluster. No gráfico do bicluster 10 (Figura 6.17) é visível a
sintonia da evolução do nível de expressão dos genes (co-regulação) entre
as condições t4 e t7 , exactamente o intervalo de tempo do bicluster, e a não
co-regulação dos genes entre os instantes temporais t1 e t4 .
O gráfico do padrão de expressão do bicluster 10 é concordante com o
96
Estudo de Caso
Figura 6.15: Gráfico de expressão do bicluster 10. Representa a expressão de todos os
seus genes nas suas condições.
Figura 6.16: Gráfico de expressão do bicluster 10 com os valores de expressão normalizados
por gene para média 0 e desvio padrão 1.
gráfico do seu padrão de expressão (ver Figura 6.18), permitindo uma visualização menos confusa e mais discreta da evolução do nível de expressão
dos genes ao longo dos instantes temporais.
6.8 Análise de Funções Biológicas
97
Figura 6.17: Gráfico de expressão dos genes do bicluster 10 em todas as condições da
experiência.
Figura 6.18: Gráfico do padrão de expressão do bicluster 10.
6.8
Análise de Funções Biológicas
Finalmente, veremos os resultados da análise de funções biológicas, consideradas estatisticamente significativas, efectuada em simultâneo com a
98
Estudo de Caso
aplicação do algoritmo CCC-Biclustering. Para uma observação global
dos p-values calculados para cada bicluster e do número de funções estatisticamente significativas correspondente, acedemos novamente ao grupo
de biclusters extraído pelo algoritmo CCC-Biclustering aplicado à matriz
discreta e seleccionamos a aba Function.
Figura 6.19: Tabela de funções biológicas para o grupo de biclusters calculadas usando
um theshold de 0.01 para o p-value corrigido pela correcção de Bonferroni. Os biclusters
com funções biológicas estatisticamente significativas são assinalados a verde.
A tabela apresentada pelo BiGGEsTS encontra-se na Figura 6.19 e apresenta, para cada bicluster: o número que o identifica, os números de genes
e condições que o compõem, o melhor p-value calculado (best p-value),
correspondente à função biológica atribuída ao bicluster que foi considerada como sendo a estatisticamente mais significativa, o melhor p-value
corrigido (best corrected p-value), depois de aplicada a correcção de Bonferroni para testes múltiplos, e o número de funções biológicas consideradas
estatisticamente significativas (significant functions), isto é, o número de
funções biológicas atribuídas ao bicluster que passaram o teste estatístico
depois da correcção de Bonferroni, pois têm um p-value corrigido inferior
a 0.01 (threshold abaixo do qual as funções biológicas são consideradas
estatisticamente significativas). Esta tabela pode depois ser recalculada
usando outro threshold para o p-value (ver Figura 6.19). As colunas desta
tabela podem ser também ordenadas por ordem crescente ou decrescente
6.8 Análise de Funções Biológicas
99
do valor de qualquer uma das suas colunas. É possível, por exemplo,
ordenar as linhas da tabela por ordem decrescente do número de funções
biológicas estatisticamente significativas e, assim, identificar os melhores
biclusters segundo este critério.
Vejamos, por exemplo, o bicluster 95, com 55 funções biológicas significativas encontradas para os seus 486 genes agrupados em 4 instantes
de tempo consecutivos. A visualização da tabela de funções biológicas
atribuídas a este bicluster, em particular, requer apenas a sua selecção na
árvore de dados e um click sobre a aba Function (ver Figura 6.20).
Figura 6.20: Tabela de funções biológicas para o bicluster 95. Estão assinaladas três
funções estatisticamente significativas: manutenção e assemblagem de subunidades ribossómicas de grandes dimensões, assemblagem de complexos proteína-ARN, processos
metabólicos primários.
A tabela de funções de um bicluster apresenta os seguintes dados para
cada função biológica: o identificador e a descrição da Gene Ontology,
o número de genes na população (experiência) e o número de genes no
bicluster anotados pela Gene Ontology com essa função, o p-value calculado
usando uma distribuição hipergeométrica em função dos valores anteriores
e do número total de genes na população e no bicluster e, por último, o
p-value corrigido pela correcção de Bonferroni para testes múltiplos (ver
Figura 6.20).
Entre as várias funções biológicas apresentadas e que podem ser atri-
100
Estudo de Caso
buídas aos genes deste bicluster (95), verificamos que apenas algumas são
consideradas estatisticamente significativas (ver Figura 6.20), por apresentarem um p-value corrigido inferior ao threshold que introduzimos aquando
da selecção das opções para a análise de funções (neste caso 0.01).
Para uma apresentação gráfica mais interessante destes dados, recorreremos à visualização das funções significativas segundo a hierarquia de
funções anotadas pela Gene Ontology representada num grafo dirigido. A
selecção da aba Significance Graph produz o resultado ilustrado na Figura
6.21.
Figura 6.21: Grafo de funções biológicas significativas do bicluster 95.
A classificação de funções da Gene Ontology considera três funções essenciais: componente celular, função molecular e processo biológico. Estas
funções englobam, por sua vez, outras funções mais específicas e assim sucessivamente. No grafo é apresentada a classificação de todas as funções
gerais que levam às funções significativas do bicluster em análise (bicluster
95). A coloração das funções significativas tem como objectivo realçá-las
em relação às restantes e pode ser interpretada da seguinte forma: as funções significativas que derivam da função geral de componente celular são
coloridas a roxo, as que têm origem na função molecular a amarelo e as
funções específicas de processos biológicos a verde. A intensidade da cor
roxa, amarela ou verde depende do valor de significância estatística encontrado para a função correspondente (ver Figura 6.21). Podemos depois
6.9 Pós-Processamento
101
exportar o gráfico nos formatos SVG e PNG.
Se considerarmos, por exemplo, que a análise apresenta demasiados
biclusters com funções significativas e que, de um modo geral, o número de
funções significativas para cada bicluster é demasiado elevado e queremos
que a análise de significância estatística seja mais restritiva, podemos voltar
a efectuar a análise de funções, utilizando desta vez um threshold para o
p-value inferior ao da primeira análise. Esta funcionalidade está acessível
a partir do painel da tabela de funções do grupo de biclusters, através de
um click no botão Recalculate (ver Figura 6.19).
6.9
Pós-Processamento
Para terminar, decidimos pós-processar o nosso grupo de biclusters. Com
o grupo seleccionado, pressionamos a aba Post-Processing e acedemos ao
respectivo painel de pós-processamento, no qual seleccionamos as opções:
filtragem de biclusters com menos de 5 genes e menos de 5 condições e
ordenação pelo p-value do padrão de expressão (ver Figura 6.22).
Figura 6.22: Painel de pós-processamento.
Após o pós-processamento, o grupo de biclusters ficou com apenas 124
biclusters, ordenados pelo p-value do padrão de expressão. Os identifica-
102
Estudo de Caso
dores dos biclusters originais são visíveis entre parêntesis, sempre que o
bicluster aparece (Figura 6.23).
Figura 6.23: Gráficos de expressão do grupo de biclusters pós-processado.
Capítulo 7
Conclusões e Trabalho Futuro
Pretende-se, através da ferramenta BiGGEsTS, disponibilizar à comunidade científica um conjunto de algoritmos de biclustering especialmente
desenvolvidos para análise de séries temporais de expressão genética.
Esta ferramenta deve permitir não só a execução dos algoritmos de
forma eficiente, mas também uma forma intuitiva de visualizar as matrizes de expressão, pré-processar os dados de entrada de acordo com
as características dos dados relativos ao problema, estudar os resultados
tendo em conta várias dimensões de análise e processá-los de acordo com
o tipo de conclusões biológicas que se pretendem inferir.
Uma ferramenta deste tipo será certamente útil a todos aqueles que trabalham com expressão genética e tentam encontrar mecanismos de regulação genética que possam posteriormente ser usados na difícil e importante
tarefa de inferência de redes de regulação genética.
Como trabalho futuro, seria interessante promover a implementação
de um módulo que permitisse a comparação de resultados obtidos por
aplicações de algoritmos distintos ou semelhantes com parametrizações
diferentes sobre os mesmos dados de expressão genética. A compatibilidade da entrada e saída de dados com o formato MAGE-ML (linguagem
XML para a definição de dados de expressão genética) é também um objectivo a atingir.
No seu estado actual, a ferramenta BiGGEsTS cumpre todos os requisitos propostos para os projectos do primeiro e segundo semestre. Após a
fase de testes, a ferramenta será disponibilizada à comunidade científica,
juntamente com a respectiva documentação, através do site desenvolvido
para o efeito. Será escrito e submetido para publicação na revista Bioinfor103
104
Conclusões e Trabalho Futuro
matics um artigo (application note) que apresente a aplicação e promova a
sua utilização e desenvolvimento.
Bibliografia
[1] P. Baldi and G. W. Hatfield. DNA Microarrays and Gene Expression. From
Experiments to Data Analysis and Modelling. Cambridge University
Press, 2002.
[2] A. Ben-Dor, B. Chor, R. Karp, and Z. Yakhini. Discovering local
structure in gene expression data: The order–preserving submatrix
problem. In Proc. of the 6th International Conference on Computacional
Biology, pages 49–57, 2002.
[3] Y. Cheng and G. M. Church. Biclustering of expression data. In Proc.
of the 8th International Conference on Intelligent Systems for Molecular
Biology, pages 93–103, 2000.
[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction
to Algorithms. The MIT Electrical Engineering and Computer Science
Series. The MIT Press, 2nd edition, 2001.
[5] M.J.L. de Hoon, S. Imoto, J. Nolan, and S. Miyano. Open source
clustering software. Bioinformatics, 20(9):1453–1454, 2004.
[6] M. de Hooon.
Cluster 3.0.
http://bonsai.ims.utokyo.ac.jp/ mdehoon/software/cluster/software.htm, [July 9, 2007].
[7] J. P. Gonçalves. Relatório no 28-2007: BiGGEsTS, Biclustering Gene
Expression Time-Series. Technical report, Departamento de Informática, Universidade da Beira Interior, 2007.
[8] J. A. Hartigan. Direct clustering of a data matrix. Journal of the American
Statistical Association (JASA), 67(337):123–129, 1972.
105
106
BIBLIOGRAFIA
[9] L. Ji and K. Tan. Identifying time-lagged gene clusters using gene
expression data. Bioinformatics, 21(4):509–516, 2005.
[10] L. Lazzeroni and A. Owen. Plaid models for gene expression data.
Technical report, Stanford University, 2000.
[11] Y. Luan and H. Li. Clustering of time-course gene expression data
using a mixed-effects model with B-splines. Bioinformatics, 19(4):474–
482, 2003.
[12] S. C. Madeira and A. L. Oliveira. Biclustering algorithms for biological data analysis: a survey. IEEE/ACM Transactions on Computational
Biology and Bioinformatics, 1(1):24–45, January–March 2004.
[13] S. C. Madeira and A. L. Oliveira. CCC-Biclustering: A linear time algorithm for biclustering time series expression data. IEEE/ACM Transactions on Computational Biology and Bioinformatics (submitted), 2007.
[14] S. C. Madeira and A. L. Oliveira. An efficient biclustering algorithm
for finding genes with similar patterns in time-series expression data.
In Proc. of the 5th Asia Pacific Bioinformatics Conference (to appear), 2007.
[15] B. Mirkin. Mathematical Classification and Clustering. Nonconvex Optimization and its Applications. Kluwer Academic Publishers, 1996.
[16] R. Peeters. The maximum edge biclique problem is NP-complete.
Discrete Applied Mathematics, 131(3):651–654, 2003.
[17] R. G. Pensa, C. Leschi, J. Besson, and J. Boulicaut. Assessment of
discretization techniques for relevant pattern discovery from gene
expression data. In 4th Workshop on Data Mining in Bioinformatics,
2004.
[18] R. G. Pensa, C. Robardet, and J. F. Bolicaut. A Bi-clustering Framework
for Categorical Data. Technical report, INSA Lyon - LIRIS CNRS UMS
5205, INSA Lyon - PRISMa EA INSA UCBL 2058, 2005.
[19] R. G. Pensa, C. Robardet, and J.F. Boulicaut. Towards Constrained Coclustering in Ordered 0/1 Data Sets. In Foundations of Intelligent Systems
- Proceedings of the 16th International Symposium on Methodologies for
Intelligent Systems (ISMIS’06), pages 425–434, 2006.
BIBLIOGRAFIA
107
[20] A. J. Saldanha. Java Treeview: extensible visualization of microarray
data. Bioinformatics, 20(17):3246–3248, 2004.
[21] L. Shi. Design of a DNA Microarray System. http://www.genechips.com, [January 31, 2007].
[22] R. Stears, T. Martinsky, and M. Schena. Trends in Microarray Analysis.
Nature Medicine, 9(1):140–145, 2003.
[23] Y. Zhang, H. Zha, and C. H. Chu. A time-series biclustering algorithm
for revealing co-regulated genes. In Proc. of the 5th IEEE International
Conference on Information Technology: Coding and Computing, pages 32–
37, 2005.