( PDF ) Extração de regras simbólicas de agrupamentos de dados de expressão gênica

Download PDF

ads:

EXTRAÇÃO DE REGRAS SIMBÓLICAS DE

AGRUPAMENTOS DE DADOS DE EXPRESSÃO GÊNICA

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

Universidade Federal do Rio Grande do Norte

Centro de Ciências Exatas e da Terra

Departamento de Informática e Matemática Aplicada

Programa de pós-graduação em Sistemas e Computação

Dissertação de Mestrado

Extração de Regras Simbólicas de Agrupamentos de Dados

de Expressão Gênica

por

Welbson Siqueira Costa

Sob orientação do

Prof. Dr. Marcílio Carlos Pereira de Souto

Natal, 2006

ads:

iii

Universidade Federal do Rio Grande do Norte

Centro de Ciências Exatas e da Terra

Departamento de Informática e Matemática Aplicada

Programa de pós-graduação em Sistemas e Computação

Dissertação de Mestrado

Welbson Siqueira Costa

Extração de Regras Simbólicas de Agrupamentos de Dados

de Expressão Gênica

Este trabalho foi apresentado ao programa de Pós-graduação em Sistemas e Computação

do Departamento de Informática e Matemática Aplicada da Universidade Federal do Rio

Grande do Norte como um dos requisitos para a obtenção do título de Mestre em Sistemas

e Computação.

_______________________________

Prof. Dr. Marcílio Carlos Pereira de Souto

Orientador

_______________________________

Profa. Dra. Thaís Vasconcelos Batista

Coordenadora do Programa

Banca Examinadora:

_______________________________

Profa. Dra. Anne Magály de Paula Canuto

Universidade Federal do Rio Grande do Norte

_______________________________

Prof. Dr. Francisco de Assis Tenório de Carvalho

Universidade Federal de Pernambuco

_______________________________

Prof. Dr. Marcílio Carlos Pereira de Souto

Universidade Federal do Rio Grande do Norte

Natal, 2006

Agradecimentos

Primeiramente ofereço meus sinceros agradecimentos ou meu orientador,

Profº Marcílio Carlos Pereira de Souto, que me conduziu na elaboração desta

dissertação e me permitiu conciliar estes estudos com as minhas várias viagens a

motivo de trabalho. Agradecimento semelhante devo aos professores Benjamín

René Callejas Bedregal, Regivan Hugo Nunes Santiago e jair Cavalcanti Leite, os

quais também permitiram minha ausência, por várias vezes, em suas salas de aula.

Também não poderei esquecer dos professores João Maria Filgueira e José

Antônio da Cunha, do CEFET-RN, os quais me incentivaram bastante em busca

desta empreitada. Por fim, também agradeço a todos aqueles colegas que direta ou

indiretamente me ajudaram.

Sumário

Capítulo 1 ......................................................................................................................... 1

Introdução......................................................................................................................... 1

1.1. Contextualização ................................................................................................... 1

1.2. Motivação.............................................................................................................. 3

1.3. Objetivos e Abordagens......................................................................................... 5

1.4. Trabalhos Relacionados......................................................................................... 7

1.4.1. Discussões........................................................................................................... 10

1.5. Estrutura da Proposta........................................................................................... 11

Capítulo 2 ....................................................................................................................... 12

Biologia molecular.......................................................................................................... 12

2.1. Replicação do DNA............................................................................................. 12

2.2. Síntese de RNA – Transcrição ............................................................................. 16

2.3. A Síntese de Proteínas - Tradução........................................................................ 18

2.4. Análise de Dados de Expressão Gênica................................................................ 23

2.5. Análise Computacional de Dados de Expressão Gênica ....................................... 27

Capítulo 3 ....................................................................................................................... 29

Aprendizado de Máquina ................................................................................................ 29

3.1. Aprendizado de Máquina Supervisionado............................................................ 31

3.1.1. Rough Sets .......................................................................................................... 31

3.1.2. Árvores de Decisão.............................................................................................. 37

3.1.3. Top Scoring Pairs ................................................................................................ 39

3.1.4. Avaliação de Regras ............................................................................................ 41

3.2. Aprendizado de Máquina Não Supervisionado..................................................... 42

3.2.1. Algoritmo de Agrupamento Hierárquico.............................................................. 43

3.2.2. Algoritmo de Agrupamento k-means.................................................................... 47

3.2.3. Avaliação de Agrupamentos com Índices de Validação ....................................... 48

Capítulo 4 ....................................................................................................................... 52

Métodos, Experimentos e Resultados .............................................................................. 52

4.1. Bases de Dados.................................................................................................... 52

4.2. Experimentos....................................................................................................... 54

4.3. Avaliação dos Resultados Obtidos ....................................................................... 57

4.3.1. Avaliação de Agrupamentos ................................................................................ 57

4.3.2. Avaliação de Regras ............................................................................................ 58

4.3.3. Avaliação Fim a Fim ........................................................................................... 60

4.4. Resultados ........................................................................................................... 61

4.4.1. Avaliação de Agrupamentos ................................................................................ 61

4.4.2. Avaliação de Regras ............................................................................................ 62

4.4.3. Avaliação Fim a Fim ........................................................................................... 65

Capítulo 5 ....................................................................................................................... 69

Análise dos Resultados.................................................................................................... 69

5.1. Análise com Gaussian3 ....................................................................................... 69

5.1.1. Árvore de Decisão ............................................................................................... 70

5.1.2. TSP ..................................................................................................................... 72

5.1.3. Rough Sets........................................................................................................... 72

5.2. Análise com Simulated6 ...................................................................................... 73

5.2.1. Árvore de Decisão ............................................................................................... 73

5.2.2. TSP ..................................................................................................................... 76

5.2.3. Rough Sets........................................................................................................... 77

5.3. Análise com St. Jude Leukemia............................................................................ 77

5.3.1. Árvore de Decisão ............................................................................................... 79

5.3.2. TSP ..................................................................................................................... 82

5.3.3. Rough Sets........................................................................................................... 83

5.4. Considerações Finais ........................................................................................... 84

Capítulo 6 ....................................................................................................................... 86

Conclusão e Trabalhos Futuros........................................................................................ 86

6.1. Trabalhos Futuros................................................................................................ 88

Referências Bibliográficas............................................................................................... 90

Anexo A.......................................................................................................................... 97

Anotações dos genes segundo o FatiGO .......................................................................... 97

vii

Lista de Figuras

Figura 1.1 – Representação do Pipeline............................................................................. 6

Figura 2.1 – Exemplos de células eucariótica (A) e procariótica (B). ............................... 13

Figura 2.2 – Representação da molécula de DNA............................................................ 13

Figura 2.3 – Representação esquemática da molécula de DNA. ....................................... 14

Figura 2.4 – Representação esquemática de uma molécula de DNA. ............................... 15

Figura 2.5 – Representação do processo de replicação de DNA. ...................................... 16

Figura 2.6 – Representação da molécula de RNA. ........................................................... 17

Figura 2.7 – Representação do processo de Transcrição................................................... 17

Figura 2.8 – Representação genérica de um aminoácido. ................................................. 19

Figura 2.9 – Aminoácido Glicina..................................................................................... 19

Figura 2.10 – Representação do processo de Tradução (parte1). ...................................... 21

Figura 2.11 – Representação do processo de Tradução (parte2). ...................................... 21

Figura 2.12 – Representação do processo de Tradução (parte3). ...................................... 22

Figura 2.13 – Representação do processo de Tradução (parte4). ...................................... 22

Figura 2.14 – Representação do Princípio básico da Biologia. ......................................... 23

Figura 2.15 – Representação de microarray..................................................................... 25

Figura 2.16 – Representação de amostra derramada sobre o microarray para hibridiza.... 25

Figura 2.17 – Imagens sobrepostas de análise de dados de microarray. ........................... 26

Figura 3.1 – Todas as classes de equivalência para o SI da Tabela 3.2............................. 34

Figura 3.2 – Exemplo de Árvore de Decisão.................................................................... 38

Figura 3.3 – Regras extraídas da Árvore de Decisão. ....................................................... 38

Figura 3.4 – Exemplo de cálculo de distâncias................................................................. 43

Figura 3.5 – Representação das etapas de agrupamento hierárquico................................. 44

Figura 3.6 – Exemplo de Dendrograma. .......................................................................... 45

Figura 3.7 – Exemplo de Dendrograma com cortes.......................................................... 46

Figura 4.1 – Representação do Pipeline........................................................................... 55

Figura 4.2 – Ilustração da seleção de agrupamento para a fase de geração de regras. ....... 57

Figura 4.3 – Ilustração de avaliação de regras.................................................................. 58

Figura 4.4 – Avaliação fim a fim. .................................................................................... 60

viii

Figura 5.1 – Árvore de Decisão obtida da base de dados Gaussian3 agrupada com k-...... 71

Figura 5.2 – Regras geradas com TSP a partir da base de dados Gausian3 agrupada c..... 72

Figura 5.3 – Regras geradas com Rough Sets a partir da base de dados Gausian3 agru .... 73

Figura 5.4 – Árvore de Decisão obtida da base de dados Simulated6 agrupada com k-..... 75

Figura 5.5 – Regras geradas com TSP a partir da base de dados Simulated6 agrupada .... 76

Figura 5.6 – Regras geradas com Rough Sets a partir da base de dados Simulated6 agr.... 77

Figura 5.7 – Árvore de Decisão gerada da base de dados St. Jude Leukemia agrupada .... 81

Figura 5.8 – Regras geradas com TSP a partir da base de dados St. Jude Leukemia agr.... 82

Figura 5.9 – Regras geradas com Rough Sets a partir da base de dados St. Jude Leuke..... 84

Lista de Tabelas

Tabela 2.1 – Código Genético. ........................................................................................ 20

Tabela 2.2 – Exemplo de matriz de dados de expressão gênica sem informação a priori. . 27

Tabela 2.3 – Exemplo de matriz de dados de expressão gênica com informação a priori.. 27

Tabela 3.1 – Exemplo de base de dados para AM............................................................ 30

Tabela 3.2 – Exemplo de Sistema de Informação............................................................. 32

Tabela 3.3 – Exemplo de Sistema de Decisão.................................................................. 33

Tabela 3.4 – Classes de equivalências para B = {Dor de Cabeça, Dor muscular, Temp.... 34

Tabela 3.5 – Matriz de Discernimento. ............................................................................ 35

Tabela 3.6 – Sistema de Decisão Reduzido...................................................................... 37

Tabela 3.7 – Exemplo de distribuição de freqüências de par de genes.............................. 40

Tabela 3.8 – Exemplo de Matriz de Confusão.................................................................. 41

Tabela 3.9 – Exemplo de base de dados para agrupamento. ............................................. 48

Tabela 3.10 – Exemplo de base de dados agrupada.......................................................... 48

Tabela 3.11 – Comparação de Classe com Grupo para avaliação de agrupamento. .......... 49

Tabela 3.12 – Matriz de confusão para as partições Grupo e Classe. ............................... 51

Tabela 4.1 – Características das bases de dados............................................................... 53

Tabela 4.2 – Exemplo de Base de Dados Agrupada......................................................... 60

Tabela 4.3 – Avaliação de Agrupamentos........................................................................ 61

Tabela 4.4 – Avaliação de Regras – Rand Corrigido, Precisão e Cobertura...................... 62

Tabela 4.5 – Avaliação de Regras – Quantidade de Regras e Elementos Antecedentes. ... 64

Tabela 4.6 – Avaliação Fim a Fim................................................................................... 66

Resumo

Nos últimos anos, a crescente automação aplicada a processos da biologia

vem possibilitando a obtenção e acúmulo de dados biológicos importantes a taxas

muito elevadas. A vasta implicação biológica existente nesses dados torna inviável

sua análise por meios computacionais convencionais. Nesse sentido, as técnicas de

Aprendizado de Máquina (AM) mostram-se bastante promissoras. Em muitos

casos, deseja-se explorar os dados para adquirir algum conhecimento que está

implícito. Por exemplo, os dados produzidos através de processos de análise de

expressão gênica, como os dados de microarray, despertam bastante interesse nos

biólogos. Um dos recursos de AM para análise desses dados pode ser a formação de

grupos, através da aplicação de técnicas de agrupamento. Estudos experimentais

demonstram que, em geral, esses grupos são biologicamente significativos. No

entanto, na maioria das vezes, a interpretação do significado biológico dos vários

grupos formados é uma tarefa bastante complexa. Assim, a análise manual, por

parte de especialistas da área em questão, passa a ser necessária para a

interpretação. Porém, isso pode ser uma tarefa extremamente custosa envolvendo

vários desafios técnicos e científicos. Este trabalho investe, portanto, seus esforços

no estudo de técnicas que facilitem a interpretação dos grupos formados por

técnicas de agrupamento. Desse modo serão associadas técnicas de AM não

supervisionadas (técnicas de agrupamento) com técnicas supervisionadas, técnicas

que objetivam a criação de estruturas simbólicas, regras do tipo SE-ENTÃO, que

sejam compreensíveis por humanos.

Palavras chaves: Aprendizado de Máquina, Dados de Expressão Gênica, Regras

Simbólicas, Facilidade de Interpretação.

Abstract

In the last few years, the increasing automation applied to Biology processes

has led to a fast accumulation of important biological data. The wide biological

implication present in these data makes its analysis unsuitable via conventional

computing. In this context, Machine Learning (ML) techniques have been shown

very promising. In many cases, we want to explore the data to acquire some

implicit knowledge. For example, the data produced by means of gene expression

analysis, such as microarray data, have been drawing a lot of attention from the

biologists. One of the ML techniques for analyzing these data is the clustering

methods. Experimental studies have shown that, often, clusters generated via such

methods are biologically meaningful. However, in general, the interpretation of the

biological meaning of the clusters formed is a very complex task. Thus, the manual

analysis, performed by the experts in the area, is needed for the interpretation. In

fact, this can be an extremely expensive task which involves several technical and

scientific challenges. Thus, this work invests its efforts in the study of techniques

that make the interpretation of clusters formed by clustering techniques more

straightforward. In order to do so, unsupervised ML techniques (clustering

techniques) will be associated with supervised ML techniques (rule generation).

The goal is to generate symbolic structures, such as IF-THEN rules, which are more

comprehensible for humans.

Key words: Machine Learning, Gene Expression Data, Symbolic Rules, Easy

Interpretation.

Capítulo 1

1. Introdução

Introdução

Neste capítulo é apresentada uma visão geral sobre o trabalho. Assim, a

Seção 1.1 faz uma contextualização sobre informática aplicada à biologia

molecular. A Seção 1.2 apresenta os motivos que nos estimulou a realizar este

trabalho. Em seguida, a Seção 1.3 expõe os nossos objetivos e abordagens. Depois,

a Seção 1.4 apresenta alguns trabalhos relacionados com nossa proposta. Logo em

seguida, a Seção 1.4.1 organiza algumas discussões sobre os trabalhos relacionados

e apresenta as diferenças entre eles e esta dissertação. Por último, a Seção 1.5

apresenta a forma como esta proposta está organizada.

1.1. Contextualização

Os estudos genéticos iniciados por Mendel em meados do século XIX

sofreram um grande impulso há 50 anos atrás. Em fevereiro de 1953 espalhara-se a

notícia: "pesquisadores de Cambridge haviam descoberto o segredo da vida" (Ortiz,

2004). No dia sete daquele mês, no laboratório Cavendish, na Inglaterra, Francis

Crick e James Watson haviam concluído que a estrutura da molécula de Ácido

Desoxirribonucléico (DNA – do inglês Deoxyribonucleic Acid) era uma dupla

hélice. Desde então a biologia molecular, após cerca de meio século de avanços,

exibe suas façanhas permitindo que o homem penetre no íntimo de organismos

vivos e interaja diretamente com aquilo que coordena todo o seu estado de vida, ou

seja, o DNA (Pereira, 2001; Ortiz, 2004; Pierotti, 2001).

Apesar da estrutura do DNA ter sido desvendada, em 1953, as informações

contidas nele eram desconhecidas. Assim “a descoberta do segredo da vida” não

estava completa. Segundo Setubal (2004) havia sido descoberto o alfabeto utilizado

para escrever o “livro” da vida, mas as letras eram tão pequenas que não se podia

“lê-las”. Por volta de 1980 surgem as tecnologias de seqüenciamento e montagem

de DNA, as quais possibilitam determinar a ordem correta das bases nitrogenadas

do DNA (A - Adenina, T - Timina, C – Citosina e G - Guanina). Essas tecnologias

emergem em conjunto com o avanço dos computadores e são auxiliadas por eles e

pela Ciência da Computação, tornando-se dependente de ambos. Nesse contexto

surge o termo Bioinformática, o qual, segundo Setubal (2004) passou a ser

reconhecido como importante pelo mundo científico por volta de 1995, data em que

foi publicado o primeiro genoma de uma bactéria. A partir de então a

Bioinformática vem, cada vez mais, ocupando um lugar de destaque no auxílio à

resolução de diversos problemas da biologia molecular.

Os seqüenciamentos de genomas de organismos continuaram e culminaram

com o projeto Genoma Humano. Em 2000 pesquisadores do consórcio público

Projeto Genoma Humano e da empresa privada norte-americana Celera anunciam o

rascunho do genoma humano, o qual teve sua publicação definitiva em fevereiro de

2001 (Linha do Tempo do DNA, 2005). Mais uma vez a mídia “explode” com as

notícias de uma grande descoberta. De fato houve um enorme avanço que

representou o sucesso da mais formidável empreitada biológica jamais empreendida

pelo homem, concebida a partir de 1985, iniciada em 1990 e hoje realizada

(Pierotti, 2001). No entanto, o genoma apenas determina a ordem correta de todas

as bases do DNA. Mas o que fazer com elas? O que são os genes

? Os próximos

desafios são identificar os genes, suas funções e seus relacionamentos de

dependências. Esses desafios são hoje motivos de concentração de esforços da

Bioinformática, pois apenas de posse desse conhecimento é possível manipular os

genes corretamente em nosso benefício. Segundo Setubal (2004) essa interpretação

requer métodos, técnicas e algoritmos que vem principalmente da informática.

Ainda segundo Setubal (2004), sem o uso dessas técnicas as seqüências de DNA

produzidas pelas máquinas seqüenciadoras e montadas pelos programas de

computadores são uma inútil “sopa de letrinhas”.

O gene é a menor unidade de informação de um genoma. Ele é composto por um determinado número de

bases (A, T, C, G), que pode variar de gene para gene. O genoma humano é o maior já seqüenciado. Ele tem

cerca de três bilhões de bases (Pierotti, 2001). Estima-se que apenas 5% dele seja constituído de genes, ou

seja, apenas 5% é informação, o resto não se tem conhecimento do que possa ser (Napoli, 2003).

1.2. Motivação

A crescente automação da biologia molecular experimental e o auxílio da

informática estão modificando a maneira como as pesquisas biológicas são

realizadas. Atualmente é possível aumentar a velocidade das descobertas. Muitos

processos que eram realizados bioquimicamente podem agora ser simulados em

softwares. Os bancos de dados permitem o armazenamento e organização de muitas

informações biológicas preciosas. Dessa maneira, em vez de fazer pesquisas

preliminares em laboratório, os cientistas podem explorar um banco de dados

público e ganhar tempo na busca de uma informação.

Essa crescente automação e informatização dos processos e dados

biológicos vêm causando a disponibilidade de dados a taxas muito elevadas. Na

maioria das vezes as informações que se desejam obter requerem um estudo

bastante complexo devido à vasta implicação biológica e riqueza dos dados (Souto

et al., 2003). Por isso técnicas convencionais da Ciência da Computação mostram-

se, muitas vezes, insuficientes para análise. Um recurso que vem se destacando

nesse sentido são as técnicas de Aprendizado de Máquina (AM), as quais têm a

capacidade de aprender automaticamente a partir de dados disponíveis e produzir

hipóteses úteis (Mitchell, 1997).

Em muitos casos deseja-se explorar os dados para adquirir algum

conhecimento que está implícito, ou seja, escondido em meio a tanta complexidade

e riqueza. Nesse sentido as técnicas de AM utilizadas são, geralmente, as não

supervisionadas. Essas técnicas agrupam os dados em aglomerados (grupos)

distintos, em que cada grupo apresenta maior grau de semelhanças entre os

elementos que o compõe e menor grau de semelhança entre os elementos de

diferentes grupos (Jain e Dubes, 1988). Em geral os aglomerados formados

refletem algum novo conhecimento intrínseco aos dados examinados.

Uma das fontes de dados biológicos que tem destaque na investigação de

genes são os dados obtidos dos processos de expressão gênica, como os dados de

microarray de DNA (Eisen, 1998; Golub et al., 1999; Slonim, 2002). A

miniaturização e automação possibilitaram a fixação, em alguns poucos centímetros

quadrados de lâmina de vidro, de milhares de genes, os quais podem agora ter seus

níveis de expressão analisados, ou seja, é possível verificar o quanto eles estão

ativos ou trabalhando para produzir proteínas. Essas informações são de grande

importância para a biologia molecular. Os milhares de genes podem ser

investigados de uma só vez, sob determinadas condições específicas, por exemplo,

analisando-se os níveis de expressão de um determinado conjunto de genes de uma

célula sob efeito de uma droga, pode-se descobrir quais deles estão mais ou menos

relacionados ao efeito da droga; outras vezes é interessante para os biólogos

comparar os níveis de expressão de alguns genes de uma célula normal com os de

outra doente, com câncer, por exemplo.

Os dados gerados a partir dos experimentos de expressão gênica são

organizados como tabelas em bancos de dados e, como já sabemos, necessitam de

análise para o seu entendimento. Esses dados podem então ser submetidos a alguma

técnica de AM não supervisionado, a qual irá tentar formar grupos que reflitam

novos conhecimentos. Estudos experimentais mostram que grupos formados dessa

maneira são, em geral, biologicamente significativos. Por exemplo, em Golub et al.

(1999) foi usado como técnica de AM não supervisionado, Mapa Auto-Organizável

(SOM - do inglês Self-Organizing Map) para agrupar 38 amostras de dados de

expressão gênica, contendo cada uma 6817 genes, de dois tipos de leucemia já

conhecidos, Leucemia Mielóide Aguda (AML – do inglês Acute Myeloid

Leukemia) e Leucemia Linfóide Aguda (ALL – do inglês Acute Lynphoblastic

Leukemia). O conjunto de dados era formado por 27 amostras do tipo ALL e 11 do

tipo AML. Os resultados evidenciaram que a técnica foi eficiente em descobrir

automaticamente os dois tipos de leucemia (Golub et al., 1999).

De fato, na maioria das vezes, a interpretação do significado biológico dos

vários grupos formados pelas técnicas de AM não supervisionadas é uma tarefa

bastante complexa. Uma das razões para isso é que, em geral, essas técnicas apenas

fornecem como resultados os grupos, sem representação alguma de como eles

foram formados; ou, ainda, desenvolvem uma representação interna própria que não

é facilmente interpretada por humanos. Assim a análise manual, por parte de

especialistas da área em questão, passa a ser necessária para a interpretação dos

grupos (Jain e Dubes, 1988; Dopazo et al., 2001). Evidentemente, isso pode ser

uma tarefa excessivamente custosa envolvendo vários desafios técnicos e

científicos. Nesse sentido verifica-se um esforço ainda modesto, porém crescente,

na produção de técnicas que forneçam resultados que sejam facilmente

interpretáveis por humanos e, conseqüentemente, facilitem a aquisição de novos

conhecimentos antes desconhecidos (Geman, 2004; Tan, 2005; Hellem e Inge,

2002; Liu et al., 2000; Karthigasoo, Cheach e Manickam, 2005; Abidi, Hoe e Goh,

2001).

Este trabalho, então, será mais um esforço no desenvolvimento de técnicas

que auxiliem a interpretação dos grupos formados por técnicas de AM não

supervisionadas (técnicas de Agrupamento). Para isso serão associadas técnicas de

Agrupamento com técnicas de AM supervisionadas orientadas a conhecimento,

técnicas que objetivam a criação de estruturas simbólicas, regras do tipo SE-

ENTÃO, que sejam compreensíveis por humanos.

1.3. Objetivos e Abordagens

Devido à necessidade de interpretação, conforme visto anteriormente,

objetivamos fazer um estudo envolvendo técnicas de AM e dados de níveis de

expressão gênica com o intuito de produzir resultados que sejam facilmente

interpretáveis por humanos. Assim, foram abordadas propostas de técnicas de AM

relativamente novas, como também técnicas bastante difundidas na literatura. Nesse

contexto, foi seguida uma abordagem que resultou na geração de regras a partir de

grupos formados por técnicas de agrupamento.

Mais especificamente foram utilizadas técnicas de AM não supervisionadas

em conjunto com técnicas supervisionadas, estas últimas para geração de regras. As

técnicas não supervisionadas utilizadas foram Agrupamento Hierárquico e k-means,

pois elas representam diferentes paradigmas de AM não supervisionado e são

amplamente utilizadas no contexto de dados de expressão gênica (Monti et al.,

2003; Quackenbush, 2001; Eisen, 1998; Golub et al., 1999). Já as técnicas para

geração de regras serão Rough Sets (Pila, 2001), Árvores de decisão (AD) (Quinlan,

1993) e Top Scoring Pairs (TSP) (Geman, 2004).

Quanto às técnicas de geração de regras, Rough Sets foi escolhida pela sua

capacidade de reduzir a quantidade de atributos do conjunto de dados

possibilitando, então, a produção de regras mais simples e, também, por ter sido

utilizada em (Abidi, Hoe e Goh, 2001), com um propósito semelhante ao deste

trabalho. A opção por algoritmos de indução de Árvores de Decisão se deve ao fato

desse algoritmo, além de produzir representações simbólicas de fácil entendimento

por humanos é, também, uma das técnicas de AM supervisionada mais tradicionais

(Mitchell, 1997). A técnica TSP também foi escolhida por apresentar características

importantes do ponto de vista da facilidade de interpretação dos resultados por

humanos, pois ela gera poucas regras com poucos elementos em seu corpo (Geman

et al., 2004), além de ter sido desenvolvida para classificação de dados de expressão

gênica.

Para essa abordagem híbrida adotamos o nome de Pipeline, mesmo nome

adotado por (Karthigasoo, Cheach e Manickam, 2005). O Pipeline consiste em

agrupar dados com as técnicas não supervisionadas, mencionadas anteriormente, e

usar o resultado fornecido (agrupamentos) como entrada para técnicas

supervisionadas que geram regras. Com isso são construídos classificadores para

base de dados de microarray considerando cada grupo como sendo uma classe. A

Figura 1.1 representa, simplificadamente, as etapas de processamento do Pipeline.

Figura 1.1 – Representação do Pipeline.

Figura adaptada de (Abidi, Hoe e Goh, 2001).

Assim, teremos seis combinações de experimentos para o Pipeline da Figura

1.1, pois cada uma das técnicas de agrupamento é combinada com cada uma das

técnicas de geração de regras. Em Karthigasoo, Cheach e Manickam (2005) é usado

apenas SOM para agrupar os dados e as regras geradas com Rough Sets são usadas

para treinamento de redes neurais. Já Abidi, Hoe e Goh (2001) fazem o uso apenas

de k-means para agrupamento e Rough Sets para geração de regras.

Para os experimentos com o Pipeline desta dissertação foram usadas três

bases de dados. Duas delas, “Gaussian3” e “Simuilated6” são bases de dados

sintéticas, que simulam dados de expressão gênica, criadas para testar algoritmos de

AM no contexto de análise de expressão gênica (Monti et al., 2003). A última, St.

Jude Leukemia, é uma base obtida a partir de dados de expressão gênica de células

com leucemia (Yeoh et al., 2002; Monti et al., 2003). Todas essas bases de dados

possuem informação a priori, ou seja, é conhecida a classe a que cada objeto

pertence. No entanto, inicialmente ignoramos a informação a priori e trabalhamos

como se não conhecêssemos a classe a que cada objeto pertence, por isso

agrupamos os dados, com o intuito de descobrir as classes, para só então gerar

regras. Isto é feito, porque objetivamos simular um processo exploratório, o qual é

bastante freqüente com dados biológicos reais. Assim as informações a priori são

utilizadas apenas quando da avaliação do desempenho dos algoritmos de

agrupamento e geração de regras.

Devido ao caráter híbrido do Pipeline a avaliação dos resultados é um tanto

complexa e específica. Por isso, na Seção 4, onde são explorados os experimentos

realizados, a avaliação dos resultados é exposta com mais detalhes.

1.4. Trabalhos Relacionados

Em Abidi, Hoe e Goh (2001) foi proposta uma estratégia híbrida,

constituída de técnica de agrupamento k-means e da teoria Rough Sets para

produção de regras a partir de dados sem informação a priori. A técnica foi

denominada de SREW (Symbolic Rule Extraction Workbench).

Para os experimentos realizados com SREW foram utilizadas duas bases de

dados com informações de câncer: 1) New Thyroid Gland, a qual tem 699

exemplos, cinco atributos e três classes; e 2) Wisconsin Breast Cancer

, com 215

exemplos, nove atributos e duas classes. Maiores detalhes sobre as bases como, por

exemplo, o que significa cada atributo, não foram fornecidos por Abidi, Hoe e Goh

(2001).

O SREW é constituído de quatro fases. Na primeira fase é realizado um pré-

processamento nos dados. Na segunda fase, os dados são agrupados com k-means.

Cada grupo formado é, então, considerado como uma classe. Assim, os elementos

A base de dados Wisconsin Breast Câncer possui originalmente 699 exemplos, no entanto, no trabalho de

Abidi, Hoe e Goh (2001) ela é apresentada com apenas 215 exemplos. Mas os autores deste trabalho não

informam que tipo de pré-processamento foi realizado para exclusão de exemplos. Também não informam a

fonte da qual foi adquirida esta base dedados.

pertencentes a um mesmo grupo são rotulados com a mesma classe. Na terceira fase

os dados já rotulados são discretizados para poder ser trabalhados com Rough Sets.

Para discretização são usados os métodos Chip2 (Liu e Setiono, 1995) e MDL

(Kohavi e Sahami, 1996). Na quarta fase são calculados os redutos

, com algoritmo

genético (Bazan, Skowron e Synak, 1994; Bazan, 1996; Wróblewski, 1995;

Komorowski e Bjorvand, 1997), extraídas as regras e aplicado um filtro a elas.

Os critérios de filtro das regras são RHD (Right Hand Side), o qual

representa o número de exemplos dos dados de treinamento que são cobertos pelo

conseqüente das regras; LHS (Left Hand Side), que representa o número de

exemplos dos dados de treinamento que são cobertos pelo antecedente das regras; e,

precisão (“acurácia”) das regras geradas.

Em Karthigasoo, Cheach e Manickam (2005) foi realizada uma estratégia

semelhante à encontrada em Abidi, Hoe e Goh (2001). No entanto, o objetivo final

de Karthigasoo, Cheach e Manickam (2005) não foi gerar regras, mas sim

classificadores baseados em redes neurais. Assim, as regras produzidas foram

usadas para treinamento de redes neurais. Esse processo foi denominado de

Pipeline.

Para os experimentos com o Pipeline de Karthigasoo, Cheach e Manickam

(2005) foi utilizada apenas a base de dados Wisconsin Breast Cancer, com as suas

699 amostras (exemplos) de células, nove características (atributos) e duas classes

(possui câncer ou não possui câncer).

O Pipeline de Karthigasoo, Cheach e Manickam (2005) é constituído de seis

fases. Na primeira há o pré-processamento dos dados. Na segunda é feito o

agrupamento com SOM, mais especificamente é realizado um ensemble de quatro

redes SOM. Na terceira fase os dados resultantes do agrupamento são discretizados.

Para discretização são utilizados os algoritmos Boolean Reasoning (Nguyen e

Skowron, 1995) e MDL (Dougherty, Kohavi e Sahami, 1995). Na quarta fase são

calculados os redutos e definidas as regras. Os redutos são calculados por meio de

algoritmo Johnson e genético. Na quinta fase as regras produzidas são submetidas a

um filtro. A seleção das regras pelo filtro se baseia em uma técnica de avaliação

quantitativa definida em Karthigasoo, Cheach e Manickam (2005). Na sexta e

O termo reduto é definido pela Teoria Rough Sets como sendo um conjunto mínimo de atributos que

permite diferenciação entre os vários objetos da base de dados. Para uma determinada base de dados podem

existir um ou mais redutos.

última fase as regras geradas pelas etapas anteriores são usadas como base de dados

para treinamento de um ensemble de redes neurais. Esta última fase não é muito

bem explicada no trabalho de Karthigasoo, Cheach e Manickam (2005), mas os

autores escrevem dizendo que as regras filtradas na fase cinco são usadas como

uma nova base de dados, agora com uma menor quantidade de atributos, para o

treinamento de redes neurais. Isto nos faz inferir que sendo as regras compostas por

atributos em seus termos antecedentes e classes em seus temos conseqüentes elas

foram tratadas como uma tabela e usadas como base de dados.

Em Geman et al. (2004) foi proposto um algoritmo de classificação

denominado de TSP (Top Scoring Pair). O TSP nasceu da necessidade de gerar

classificadores a partir de dados de expressão gênica que além de precisos fossem,

também, de fácil interpretação por humanos. Assim a técnica consiste na geração de

regras com poucos elementos em seu termo antecedente, ou melhor, apenas um par

de genes.

Os experimentos realizados por Geman et al. (2004) com TSP incluíam três

bases de dados de níveis de expressão gênica: 1) Breast é uma base de dados de

níveis de expressão de genes de 49 amostras de células de mama. Os níveis de

expressão foram obtidos pela técnica Affymetrix HuGeneFL array. A base possui

7.129 genes (atributos) e foram consideradas duas classes (ter câncer e não ter

câncer) (West et al., 2001). 2) Leukemia é uma base de dados de níveis de

expressão com 72 amostras de células com leucemia, também obtidas pela técnica

Affymetrix HuGeneFL array. Possui 7.129 atributos e são consideradas duas classes

de leucemia (ALL e AML) (Golub et al., 1999). 3) Prostate é uma base de dados

constituída de 102 amostras de células da próstata, das quais 52 há câncer e 50 não.

Ela possui 12.600 genes (atributos) e foi obtida pela técnica de Affymetrix Hu95Av2

microarray chip (Singh et al., 2002).

Em Tan et al. (2005) foi proposta uma modificação, um refinamento, no

algoritmo TSP proposto por Geman et al. (2004), o qual passou a ser denominado

de K-TSP. Nessa nova versão do TSP há a possibilidade de configuração do

parâmetro k com um número que varia de um a dez. Quando K = 1 a técnica

corresponde ao seu antecessor TSP. Nos experimentos realizados com K-TSP em

Tan et al. (2005) foram utilizadas diversas bases de dados de níveis de expressão

gênica com o número de classes variando de dois a catorze. As bases de dados

foram obtidas pelos processos de microarray de cDNA e Affymetrix.

1.4.1. Discussões

Todas as propostas apresentadas na seção anterior objetivam, de certa

maneira, produzir hipóteses que possibilitem uma melhor compreensão por parte de

humanos. No entanto, além de fácil entendimento eles objetivam também uma boa

precisão no desempenho dos modelos gerados.

A Estratégia adotada por Abidi, Hoe e Goh (2001) gera regras a partir de

dados sem informação a priori, no entanto, esse trabalho realiza experimentos com

dados de pequena dimensão com relação ao número de atributos, isto é, a maior

quantidade de atributos utilizada foi nove. Eles apenas utilizam o algoritmo k-

means para agrupamento dos dados e Rough Sets para gerar as regras. Já no

Pipeline de Karthigasoo, Cheach e Manickam (2005) o agrupamento dos dados é

realizado através de SOM e as regras geradas com Rough Sets são utilizadas para

treinamento de redes neurais. A única base de dados utilizada nos experimentos

com o Pipeline de Karthigasoo, Cheach e Manickam (2005) possui apenas nove

atributos, mesma quantidade máxima de atributos encontrada em uma das bases de

dados dos experimentos realizados no trabalho de Abidi, Hoe e Goh (2001).

Diferentemente dos experimentos de Abidi, Hoe e Goh (2001) e

Karthigasoo, Cheach e Manickam (2005). O Pipeline implementado nesta

dissertação utiliza k-means e Agrupamento Hierárquico, como técnica de

agrupamento; e, Rough Sets, Árvores de Decisão e TSP para produção das regras a

partir dos agrupamentos, objetivando, dessa maneira, um melhor desempenho

relativo à interpretação dos dados.

Em todos os trabalhos apresentados na seção anterior apenas a proposta do

algoritmo TSP (Geman et al., 2004) realiza experimentos com dados de nível de

expressão gênica. Para todos os experimentos realizados nesta dissertação são

utilizadas bases de dados de níveis de expressão gênica obtidas pelo processo de

microarray de cDNA. Essas bases são caracterizadas por possuírem grandes

quantidades de atributos, geralmente mais de seis centenas de atributos.

A técnica K-TSP de Tan et al. (2005), a qual é um refinamento do TSP, não

foi escolhida para ser utilizada nos experimentos desta dissertação, pois sua

implementação é relativamente mais complexa que a TSP. Ela também é bastante

dispendiosa computacionalmente. Segundo os experimentos realizados por Tan et

al. (2005), o qual fez, entre outras, uma comparação entre TSP e K-TSP, esta última

não apresentou desempenho consideravelmente maior que a técnica TSP, sendo,

ainda, que a TSP gera sempre uma menor quantidade de regras, o que facilita a

interpretação de resultados quando se trabalha com exploração de dados.

1.5. Estrutura da Proposta

Os próximos capítulos desse trabalho são:

• Capítulo 2 (Biologia Molecular). É exposta a fundamentação teórica

biológica necessária para o entendimento deste trabalho.

• Capítulo 3 (Aprendizado de Máquina). Esse capítulo apresenta uma

breve revisão sobre Aprendizado de Máquina e expõe as técnicas

utilizadas nos experimentos.

• Capítulo 4 (Métodos, Experimentos e Resultados). Esse capítulo

apresenta as bases de dados utilizadas nos experimentos; explica

detalhadamente a abordagem empregada em cada experimento,

incluindo os métodos utilizados na avaliação, e mostra os resultados

obtidos.

• Capítulo 5 (Análise dos Resultados). Nesse capítulo são analisados os

resultados obtidos nos experimentos.

• Capítulo 6 (Conclusão e Trabalhos Futuros). Nesse capítulo é

apresentada a conclusão e os prováveis trabalhos futuros.

Capítulo 2

2. Biologia Molecular

Biologia molecular

A biologia molecular é uma área ligada à genética e a bioquímica. Ela atua

no estudo dos processos bioquímicos celulares que envolvem o material genético e

as proteínas (Lopes, 1997). Mais especificamente ela estuda o DNA, o RNA, as

proteínas e os processos dos quais participam essas moléculas, ou seja, a replicação,

a transcrição e a tradução.

Neste capítulo são apresentados conceitos da biologia molecular essenciais

para o entendimento do que são dados de expressão gênica, os quais são as fontes

de dados biológicas analisadas neste trabalho. Deste modo, as Seções 2.1 até 2.3

esclarecem conceitos importantes para o entendimento do conceito expressão

gênica. É explicado o que é DNA, RNA e proteínas e, ainda, os processos nos quais

essas moléculas participam nas células. A Seção 2.4 explica o que é expressão

gênica e aborda os dados de expressão gênica utilizados como entrada para as

técnicas de AM.

2.1. Replicação do DNA

A terra é habitada por uma infinidade de espécies. Estima-se que existam

cerca de dez ou até cem milhões de espécies diferentes (Alberts, 2004). Esses seres

são capazes de produzir cópias fiéis de si mesmo reproduzindo características

específicas minuciosamente. Esse fato é denominado de hereditariedade e é parte

central da definição de vida. A hereditariedade tem suas informações armazenadas

em moléculas de DNA. Essas informações, denominadas de informações genéticas,

também são responsáveis pela realização de atividades vitais (Lopes, 1997), ou

seja, elas determinam como os organismos devem funcionar. O material genético é

encontrado no interior do núcleo de células eucarióticas

ou disposto no citoplasma

de células procarióticas

(Figura 2.1).

Em 1953 os pesquisadores Francis Crick e James Watson publicaram que

haviam desvendado a estrutura da molécula de DNA, a qual é aceita até os dias

atuais. Segundo os pesquisadores o DNA é uma longa molécula, constituída por

duas fitas enroladas em torno de seu próprio eixo, semelhante a uma escada do tipo

caracol (Ortiz, 2004) (Figura 2.2).

Figura 2.1 – Exemplos de células eucariótica (A) e procariótica (B).

(A) Figura adaptada de http://www.invivo.fiocruz.br/celula/imagens/celula_animal.gif.

(B) Figura adaptada de www.colegiosaofrancisco.com.br/procariotica.jpg.

Figura 2.2 – Representação da molécula de DNA.

Cada molécula de DNA é formada pela união de grupos menores

denominados de nucleotídeos. Cada nucleotídeo é constituído de uma molécula de

ácido fosfórico (fosfato), uma molécula de açúcar (sempre uma pentose chamada de

desoxirribose) e uma base nitrogenada. A base nitrogenada pode ser de quatro tipos

distintos: A (Adenina), T (Timina), C (Citosina) ou G (Guanina). A presença de um

As células eucarióticas são aquelas que possuem núcleo e as procarióticas são as que não possuem núcleo.

tipo específico de base nitrogenada determina o tipo do nucleotídeo, já que o

fosfato e a pentose são comuns a todos os nucleotídeos do DNA. Bases

nitrogenadas de fitas opostas são unidas por ligações do tipo pontes de hidrogênio.

Verifica-se que em cada molécula de DNA a proporção de Timina e Adenina é de

um para um (1:1), ou seja, elas ocorrem em mesma quantidade. Situação análoga

ocorre com as proporções de Citosina e Guanina. Essas informações levam a

proposição de que as bases A e T são complementares entre si, sendo C e G

também complementares entre si. Assim se em um trecho de DNA uma das fitas

apresenta a seqüência ACTT a fita oposta apresentará TGAA. A Figura 2.3 e a

Figura 2.4 ilustram o que foi explicado.

Figura 2.3 – Representação esquemática da molécula de DNA.

Figura 2.4 – Representação esquemática de uma molécula de DNA.

Figura adaptada de http://upoad.wikimedia.org/wikipedia/en/b/b8/DNA-structure-and-

bases.gif.

As moléculas de DNA diferem umas das outras pela ordem de suas bases

nitrogenadas. A ordem correta de todos os nucleotídeos de todo o DNA de um

determinado organismo é denominada de seqüência do genoma

. Assim quando em

2001 foi apresentado ao mundo o seqüenciamento do genoma humano, na verdade

foi apresentada a seqüência correta de todos os nucleotídeos de nosso material

genético.

Todas as entidades vivas têm a capacidade de criar novas cópias delas

mesmas. Para que isso seja possível o material genético deve ser duplicado para ser

transferido ao novo organismo. A essa duplicação do material genético dá-se o

nome de replicação. Em células a replicação é realizada quando da ocorrência do

processo da divisão celular.

Cada molécula de DNA, ao final do processo de replicação, se transforma

em duas novas moléculas. Uma delas permanece com a célula existente e a outra é

transferida para a nova célula. A replicação ocorre com o auxílio da enzima DNA

polimerase. A DNA polimerase quebra as pontes de hidrogênio que une as bases

complementares de fitas opostas. As fitas, então, se separam e novos nucleotídeos

se unem aos seus respectivos complementares (esse processo de união de

nucleotídeos complementares é denominado de hibridização) formando a fita que

estava faltando. Após o processo têm-se duas moléculas totalmente idênticas a

original. A Figura 2.5 ilustra o processo de replicação.

Um genoma é o conjunto completo de todos os nucleotídeos do DNA de uma célula de um determinado

organismo (Lopes, 1997).

Figura 2.5 – Representação do processo de replicação de DNA.

Figura adaptado de http://www.genelex.com/paternitytesting/images/dna-molecule.jpg.

2.2. Síntese de RNA – Transcrição

Além da capacidade de duplicação o DNA é responsável pela síntese de um

outro ácido muito importante para a célula, o Ácido Ribonucléico (RNA – do inglês

Ribonucleic Acid). Semelhante ao DNA o RNA também é uma molécula formada

por nucleotídeos, mas em vez da base Timina há a presença de uma outra base a

Uracila (U). Os nucleotídeos do RNA possuem os mesmos componentes dos

nucleotídeos do DNA; uma molécula de ácido fosfórico, uma de açúcar (nesse caso

uma ribose) e uma base nitrogenada.

Mas o RNA não possui a configuração de fita dupla como ocorre no DNA.

Ele é uma fita simples, uma única cadeia de nucleotídeos. Por esse motivo o RNA é

bastante reativo, pois suas bases (nucleotídeos) ficam expostas podendo se ligar

(hibridizar) a bases complementares da própria molécula ou de outra molécula de

RNA (Alberts, 2004).

Figura 2.6 – Representação da molécula de RNA.

A síntese ou produção de RNA ocorre a partir das moléculas de DNA. Estas

funcionam como molde para a formação daquelas. O processo inicia-se quando a

enzima RNA polimerase quebra as pontes de hidrogênio que une determinados

nucleotídeos do DNA. Inicia-se, então, a hibridização de novos nucleotídeos

complementares aos do DNA. Concluída a hibridização a cadeia formada é o RNA

que possui as informações correspondentes aquele trecho de DNA. O RNA se

desprende do DNA e este volta a se fechar unindo suas bases complementares que

haviam tido sua ligações rompidas pela RNA polimerase.

Figura 2.7 – Representação do processo de Transcrição.

Figura adaptado de http://www.genelex.com/paternitytesting/images/dna-molecule.jpg.

Há três tipos distintos de RNA classificados conforme suas funções e

estruturas: RNA ribossômico (RNAr), RNA mensageiro (RNAm) e RNA

transportador (RNAt). O RNAr é o que ocorre em maior quantidade nas células. No

citoplasma ele é encontrado associado a proteínas formando os ribossomos (Lopes,

1997).

Já o RNAm é um dos principais atores no processo de formação de

proteínas. Cada conjunto de três bases do RNAm é denominado de códon e codifica

um determinado aminoácido (molécula formadora das proteínas). Assim uma

proteína específica é formada conforme as seqüências de códons existentes em uma

molécula de RNAm. Por exemplo, supondo a existência de uma proteína com a

seguinte seqüência de aminoácidos: Serina, Prolina, Treonina e Alanina, nessa

ordem. Teremos os códons UCU, CCA, ACC e GCC, codificando os respectivos

aminoácidos anteriores. Uma molécula de RNAm necessária para sintetizar essa

proteína teria a seguinte seqüência de bases: UCUCCAACCGCC.

O RNAt é o menor de todos, ele tem cerca de 75 a 100 nucleotídeos. Ele é

importante no processo de formação de proteínas porque possui uma característica

especial de se combinar, de modo reversível, a específicos aminoácidos que serão

transportados para o processo de formação de proteínas (Lopes, 1997). Em uma de

suas extremidades o RNAt se une a uma determinada proteína. Na sua outra

extremidade ele possui um anticódon, o qual possui a seqüência de três bases

complementares ao códon do RNAm que codifica aquele determinado aminoácido

transportado pelo RNAt.

2.3. A Síntese de Proteínas - Tradução

As proteínas são moléculas formadas pela união de outras moléculas

denominadas de aminoácidos. Já os aminoácidos são formados por um grupamento

amina (NH

) e um grupamento carboxila ou ácido (COOH), por isso o nome

aminoácido (Lopes, 1997). Esses grupamentos são ligados a um átomo de carbono

(C), o qual, por sua vez, é ligado a um átomo de hidrogênio e a um radical (R). Esse

radical é quem determina o tipo do aminoácido.

Figura 2.8 – Representação genérica de um aminoácido.

Figura 2.9 – Aminoácido Glicina.

As proteínas desempenham um papel fundamental na vida das células e dos

seres vivos. Por exemplos, elas são os principais componentes estruturais dos

organismos. Participam da constituição de membranas celulares; constituem as

fibras que ocorrem entre os espaços formados pela união das células de

determinados tecidos, como tendões e cartilagens do nariz e orelhas; participam da

composição de unhas, cascos e pelos de mamíferos; entre outros. Elas também são

responsáveis pelo mecanismo de defesa dos organismos (anticorpos) (Lopes, 1997).

Um tipo bastante importante de proteína são as enzimas, as quais atuam

aumentando a velocidade de reações químicas e são responsáveis, por exemplo,

pela digestão dos alimentos no nosso estômago (Lopes, 1997; Alberts, 2004;

Pereira, 2001).

As funções das proteínas são determinadas pela sua estrutura tridimensional,

a qual é definida pela seqüência de aminoácidos que constitui cada uma delas. Há

apenas 20 tipos de aminoácidos diferentes, que podem ser combinados para formar

uma infinidade de proteínas. A combinação de aminoácidos para formação de uma

proteína é denominada síntese de proteínas ou tradução e ocorre no citoplasma da

célula.

A tradução é comandada por um complexo formado principalmente por

RNAm, RNAt e ribossomo (RNAr associado a proteínas). Cada conjunto de três

nucleotídeos (códon) seqüenciais do RNAm determina um aminoácido. Esse

mapeamento de códons para aminoácidos caracteriza o código genético. Assim a

tradução é o resultado da interpretação do código genético estabelecido pelos

códons dos RNAm, em que cada códon especifica um determinado aminoácido.

O código genético é constituído por 64 códons diferentes e seus

aminoácidos correspondentes (Tabela 2.1). Mas como existem apenas 20 tipos de

aminoácidos diferentes há mais de um códon para um mesmo aminoácido. Esse

fenômeno é reconhecido como degeneração do código genético.

UUU UCU UAU UGU

UUC UCC UAC UGC

UUA UCA UAA UGA Parada

UUG UCG UAG UGG Triptofano

CUU CCU CAU CGU

CUC CCC CAC CGC

CUA CCA CAA CGA

CUG CCG CAG CGG

AUU ACU AAU AGU

AUC ACC AAC AGC

AUA ACA AAA AGA

AUG Metionina ACG AAG AGG

GUU GCU GAU Ácido GGU

GUC GCC GAC aspático GGC

GUA GCA GAA Ácido GGA

GUG GCG GAG glutâmico GGG

Alanina Glicina

Asparagina Serina

Lisina Arginina

Tirosina Cisteína

Terceira Letra

Leucina Parada

Leucina Prolina

Histidina

Arginina

Glutamina

Segunda Letra

Fenilalanina

Serina

Isoleucina

Treonina

Valina

Primeira Letra

UCA G

Tabela 2.1 – Código Genético.

Dos 64 códons, três não determinam aminoácidos. Eles representam sinais

de parada que determinam o final do processo de tradução.

A seguir é ilustrado o processo de produção de uma proteína hipotética

constituída pelos aminoácidos Metionina, Leucina e Alanina, nessa ordem. O

ribossomo “caminha” sobre o RNAm ao passo de um códon de cada vez. A cada

passo dado um RNAt traz um aminoácido. Os aminoácidos adjacentes são então

unidos por ligações peptídicas. A ordem correta das associações de aminoácidos é

conduzida pelo casamento do anticódon do RNAt com o códon do RNAm. A

Figura 2.10 mostra um RNAt transportando uma Metionina que irá se ligar a uma

Leucina.

Figura 2.10 – Representação do processo de Tradução (parte1).

Figura adaptada de http://www.math.tamu.edu/~rahe/Math664/fig37.jpg.

Após a ligação dos aminoácidos Leucina e Metionina o RNAt mais a

esquerda é descartado (Figura 2.11). O RNAt mais a direita ocupa o lugar do

anterior (Figura 2.12). Um novo aminoácido chega ao ribossomo através de um

outro RNAt (Figura 2.12) e, da mesma maneira anterior, se une à corrente de

aminoácidos existente para formar a proteína representada na Figura 2.13.

Figura 2.11 – Representação do processo de Tradução (parte2).

Figura adaptada de http://www.math.tamu.edu/~rahe/Math664/fig37.jpg.

Figura 2.12 – Representação do processo de Tradução (parte3).

Figura adaptada de http://www.math.tamu.edu/~rahe/Math664/fig37.jpg.

Figura 2.13 – Representação do processo de Tradução (parte4).

Nas células eucarióticas a transcrição e a tradução são realizadas em

períodos distintos. A primeira ocorre no núcleo e a segunda no citoplasma. O

RNAm sintetizado no núcleo migra para o citoplasma e só então é traduzido em

proteínas. Já em células procarióticas, que não possuem núcleo, a transcrição e

tradução podem ocorrer ao mesmo tempo, ou melhor, à medida que um RNAm é

transcrito a sua parte já formada pode ser traduzida.

Os três processos: replicação de DNA, transcrição de RNAm e tradução de

RNAm em proteínas ocorre em todos os organismos e constituem o princípio

básico da biologia.

Figura 2.14 – Representação do Princípio básico da Biologia.

2.4. Análise de Dados de Expressão Gênica

Os seres humanos, como outros organismos multicelulares, são compostos

por uma enorme quantidade de células distintas, por exemplo, as células da parede

intestinal, os neurônios cerebrais, as células da pele (melanócitos), têm formas e

funções bastante diferentes. As primeiras são especializadas na absorção, as

segundas na transmissão de impulsos nervosos, já as terceiras produzem a

melanina, pigmento responsável pela cor da pele. No entanto, apesar de diferentes,

todas essas células possuem o mesmo material genético. Mas, sendo os genes desse

material genético os responsáveis pelas características das células como elas podem

ser diferentes? Esse fenômeno bastante intrigante é denominado de diferenciação

celular ou especialização celular (Lopes, 1997). Ele tem sua origem em outro

fenômeno, a expressão gênica.

Apesar de todas as células de um organismo apresentarem o mesmo DNA,

apenas alguns de seus genes mostram-se ativos, ou melhor, são expressos. Assim os

genes que são expressos na célula do estômago, por exemplo, permanecem inativos

nos neurônios. Essa diferenciação na atividade dos genes caracteriza a

especialização celular e é denominada de expressão gênica. A expressão gênica

corresponde aos processos de trasncrição de DNA em RNAm e tradução de RNAm

em proteínas.

A análise de expressão de genes é uma tarefa de bastante interesse e

importância para a biologia, pois ela fornece informações que podem permitir

identificar genes que participam de um mesmo processo biológico (Eisen, 1998);

verificar a resposta de uma célula ao tratamento com uma droga específica (Dopazo

et al., 2001); descobrir redes regulatórias de genes (Haeseleer, Liang e Somogyi,

1999); diagnosticar doenças como o câncer, que muitas vezes são de difícil

diagnóstico por meios histológicos convencionais (Brown et al., 2000; Brown e

Bostein, 1999); entre outras.

Para cada propósito há um tipo específico de análise. Por exemplo, na

identificação de redes regulatórias de genes ou na análise do comportamento de

uma célula sob ação de uma droga, é interessante observar a expressão dos genes

em alguns intervalos de tempo. Em outros tipos de análises, como o diagnóstico de

câncer, deseja-se comparar a expressão dos genes de uma célula normal com uma

outra célula, possivelmente doente. Este último também é usado para comparação

de células normais com células que sofreram mutações.

Existem diversas técnicas propostas para a obtenção de expressão de genes:

MPSS (Massively Parallel Signature Sequence Technology), SAGE (Serial

Analysis of Gene Expression), RT-PCR (Reverse-Transcription Polymerase Chain

Reaction) e microarray de cDNA

(microarray de Complementary DNA) (Brenner

et al., 2000; Velculescu et al., 1995; Freeman, Walker e Vrana, 1999; Harrington,

Rosenow e Retief, 2000). Nesse trabalho serão utilizados dados de microarray de

cDNA.

O microarray de cDNA é uma técnica de domínio público desenvolvida

pela universidade de Stanford e bastante difundida na comunidade científica. Há

uma grande quantidade de dados de expressão gênica disponíveis em bancos de

dados públicos obtidos a partir dessa técnica. Uma de suas maiores vantagens é a

possibilidade de analise de milhares de genes de uma só vez em alguns poucos

centímetros de lâmina de vidro.

O surgimento da técnica de microarray foi possível devido a alguns fatores.

Primeiramente, o desenvolvimento da automação possibilitou construir lâminas de

vidro com alguns poucos centímetros quadrados contendo milhares de pequenos

pontos, denominados de spot, nos quais são depositados milhares de genes. Em

segundo lugar, o surgimento das tecnologias de seqüenciamento de DNA e a

descoberta de genes foram necessários para produzir genes a serem analisados por

microarray.

A técnica consiste em afixar milhares de moléculas de cDNA de maneira

ordenada e específica numa matriz de spots sob uma lâmina de vidro. Essa lâmina

adquire a denominação de microarray de cDNA (Figura 2.15). A operação de

fixação dos pontos é realizada por robôs.

cDNA são moléculas de DNA produzidas a partir de moléculas de RNAm. Elas são usadas em substituição

ao RNAm, porque são mais estáveis que aquelas.

Figura 2.15 – Representação de microarray.

As moléculas de cDNA afixadas são escolhidas de maneira que possam

hibridizar com RNAm que corresponda aos genes cuja expressão se deseja analisar.

São então extraídos RNAm de uma célula que se deseja analisar e de uma célula de

controle. Esses RNAm são também transcritos para moléculas de cDNA, pois

RNAm são muito reativos e podem se degradar antes do experimento ser concluído.

Os cDNA são então marcados com corantes fluorescentes. Os da célula de controle

geralmente são marcados com vermelho (CY5) e os da célula que se está

analisando são marcados com verde (CY3).

Após isso as moléculas são misturadas e despejadas sobre o microarray

(Figura 2.16). Assim materiais genéticos complementares irão hibridizar. Depois

disso a lâmina é lavada e as moléculas que não hibridizaram são removidas.

Figura 2.16 – Representação de amostra derramada sobre o microarray para hibridização.

O microarray é escaneado sob a presença da luz vermelha e depois de luz

verde. Isso produz duas imagens cada uma delas identificando os pontos verdes e

vermelhos. Essas imagens são sobrepostas e analisadas por computador que calcula

os níveis de intensidade (IN) de cada ponto, ou seja, de cada gene, e produz uma

matriz com valores de intensidade relativa. Cada valor da matriz representa, então,

o nível de expressão de cada gene de cada spot em relação à célula de controle. A

equação 2.1 apresenta o cálculo do nível de expressão relativo em uma análise de

dados de microarray.

IN = log (intensidade(CY5)/intensidade(CY3)

2.1

Assim, se um ponto apresenta a cor negra significa que aquele gene não foi

expresso em nenhuma das células. Se o ponto é verde o gene foi expresso na célula

que se estava analisando. Quando ele é vermelho o gene estava sendo expresso na

célula de controle. Tendo uma cor entre verde e vermelho (amarelo) significa que

ele foi expresso em ambas as células. As intensidades das cores medidas pelo

computador irão refletir a atividade de cada gene sob a condição em que foi

realizado o experimento.

Figura 2.17 – Imagens sobrepostas de análise de dados de microarray.

2.5. Análise Computacional de Dados de Expressão Gênica

À medida que se acumulam resultados de experimentos com dados de

expressão gênica cresce a necessidade da aplicação de técnicas que possam dar

significado biológico a esses resultados. A grande quantidade de dados torna

inviável a análise por meios convencionais (Quackenbush, 2001; Slonim, 2002;

Souto et al., 2003). Nesse sentido, técnicas de AM destacam-se como um recurso

computacional viável para essa atividade (Baldi e Brunak, 2001; Haeseleer, Liang e

Somogyi, 1999).

Em experimentos com microarray, geralmente são medidos os níveis de

expressão de vários genes em diversas circunstâncias, por exemplo, podem ser

analisados os genes de uma célula normal e outra doente (com câncer); ou, de uma

única célula após a administração de uma droga.

Para serem analisados com técnicas de AM, os valores de expressão

medidos podem ser organizados em forma de uma matriz, conforme apresentado

nas tabelas abaixo, nas quais os experimentos (objetos) são considerados como as

linhas da matriz e os genes (atributos) como as colunas, assim cada valor isolado da

matriz representa o nível de expressão do gene coluna no experimento linha.

Gene 1 Gene 2 ... Gene M

Experimento 1

-0,1542 0,472 ... 0,0784

Experimento 2

0,0154 0,2655 ... 0,2098

...

... ... ... ...

Experimento N

-0,0405 0,0124 ... 0,0265

Objetos

Atributos

Tabela 2.2 – Exemplo de matriz de dados de expressão gênica sem informação a priori.

Gene 1 Gene 2 ... Gene M Classe

Experimento 1

-0,1542 0,472 ... 0,0784 B

Experimento 2

0,0154 0,2655 ... 0,2098 A

...

... ... ... ... ...

Experimento N

-0,0405 0,0124 ... 0,0265 B

Objetos

Atributos

Tabela 2.3 – Exemplo de matriz de dados de expressão gênica com informação a priori.

Quando se trabalha com técnicas de AM supervisionadas é necessário ter

conhecimento a priori, ou seja, saber a que classe pertence cada objeto, pois assim é

possível a construção de classificadores capazes de predizer a classe de um novo

objeto que não estava no conjunto de treinamento original. Nesse contexto a base

de dados deve ser representada conforme Tabela 2.3.

Em abordagens denominadas de exploratórias, nas quais não se tem

informação a priori, o objetivo é descobrir a que classe pertence cada objeto. Para

isso são aplicadas técnicas de AM não supervisionadas, essas técnicas formam

grupos de objetos que, em sua maioria, possuem objetos pertencentes a uma mesma

classe. Assim cada grupo formado é denominado de uma nova classe (Eisen, 1998;

Heyer, Kruglyak e Yooseph, 1999; Tamayo et al., 1999; Golub et al., 1999). Nesse

contexto a base de dados é representada como na Tabela 2.2.

Neste trabalho realizamos experimentos com bases de dados de níveis de

expressão gênica, obtidas através do processo de microarray de amostras de células

com câncer. Para todas as bases de dados são conhecidas as informações a priori,

no entanto, como o objetivo desta dissertação é a execução de experimentos em

abordagens exploratórias os dados de entrada para as técnicas de agrupamento são

semelhantes aos da Tabela 2.2. As informações a priori são, então, utilizadas apenas

para avaliar os resultados obtidos dos experimentos.

Capítulo 3

3. Aprendizado de Máquina

Aprendizado de Máquina

Neste capítulo são abordados conceitos de Aprendizado de Máquina (AM)

supervisionado e não supervisionado necessários para o entendimento das

abordagens aplicadas aos experimentos desta dissertação. Na Seção 3.1 são

apresentadas as técnicas de geração de regras utilizadas na execução dos

experimentos. Na Seção 3.2 são apresentadas as técnicas de agrupamento. É

importante observar que a técnica Rough Sets não é classificada na literatura como

sendo uma técnica de AM, dessa maneira, apenas a inserimos na Seção 3.1 para

organizá-la junto às outras técnicas de geração de regras.

O termo aprender abrange uma quantidade relativamente grande de

processos que se torna difícil fornecer uma definição precisa (Resende et al., 2003).

Porém, a maioria das definições converge para um mesmo significado. Vejamos

algumas encontradas em (Fernandes, 2000):

“1) tomar conhecimento de algo; 2) tornar-se apto ou capaz de alguma coisa, em

conseqüência de estudo, observação, experiência, advertência, etc; 3) tomar

conhecimento de algo, retê-lo na memória, em conseqüência de estudo,

observação, experiência, advertência, etc.”

Em Ciências da Computação, AM é uma subárea da Inteligência Artificial

que tem como objetivo estudar e produzir técnicas ou sistemas computacionais

capazes de adquirir conhecimento de forma automática (Resende et al., 2003 p.89).

Assim um Sistema de Aprendizado é um programa de computador que apresenta

resultados baseando-se no conhecimento adquirido automaticamente. No caso de

sistemas de AM supervisionado os resultados são obtidos através de experiências

adquiridas por meio da solução bem sucedida de problemas anteriores (Souto et al.,

2003).

Grande parte dos sistemas computacionais existentes funciona mapeando

entradas previamente determinadas para saídas também previamente determinadas.

Assim, para construir programas que trabalham dessa maneira é necessário ter o

completo conhecimento do mapeamento de todas as entradas possíveis com suas

respectivas saídas, ou seja, é necessário ter o domínio sobre o conhecimento. Mas

nem sempre há domínio completo sobre o conhecimento. Nesse sentido as técnicas

de AM são bem sucedidas, pois elas apresentam a capacidade de generalização

através da realização de processos indutivos, ou seja, a técnica extrai o

conhecimento diretamente dos dados de entrada e computa as devidas saídas sem a

necessidade da intervenção humana. Isso possibilita o tratamento de assuntos ainda

desconhecidos.

A indução é a forma de raciocínio lógico que permite obter conclusões

genéricas a partir de um conjunto restrito de exemplos. Essa é uma das formas mais

usadas pelo cérebro humano para derivar conhecimento novo (Resende et al.,

2003). Nos sistemas de AM a indução é realizada por técnicas computacionais,

algoritmos, que recebem como entrada informações ou exemplos referentes àquilo

que se deseja aprender. O Aprendizado de Máquina Indutivo pode ser dividido em

supervisionado e não supervisionado.

No aprendizado supervisionado os dados de entrada (objetos, exemplos,

instâncias, casos, experimentos, padrões) são constituídos de atributos e classes,

este último também denominado de informação a priori. Cada exemplo,

individualmente, é formado por uma determinada quantidade de atributos e apenas

uma classe. Por exemplo, considere a Tabela 3.1 como um conjunto de dados de

entrada para uma técnica de AM. Observe que o primeiro valor do “ATRIBUTO2“

na primeira linha é indefinido. Isso significa que ele é desconhecido. Técnicas de

AM podem lidar com dificuldades dessa natureza.

TRIBUTO

CLASSE

está chovendo indefinido não vou à praia

não chovendo não tenho dinheiro não vou à praia

não chovendo tenho dinheiro vou à praia

ATRIBUTO 1 ATRIBUTO 2

Tabela 3.1 – Exemplo de base de dados para AM.

Cada linha da Tabela 3.1 representa um objeto. Cada objeto é um vetor de

atributos e o atributo classe. O processo de indução é denominado de treinamento e

o algoritmo que o realiza e chamado de indutor. Após o treinamento o sistema de

AM produz um modelo que é uma representação generalizada do conhecimento

adquirido. Esse modelo pode ser usado para tomar decisões ou classificar novos

objetos que não pertenceram ao conjunto de dados usado no treinamento e que

ainda não têm classe definida. O modelo generalizado que classifica novos

exemplos ainda desconhecidos é denominado de classificador ou hipótese. Um

exemplo de hipótese poderia ser um conjunto de regras.

As técnicas de AM não supervisionadas diferem das supervisionadas por

receberem como entrada objetos sem informação a priori, ou seja, sem o atributo

classe. Assim o dever dessas técnicas é agrupar os objetos em aglomerados

(grupos) distintos. Em geral, os objetos dentro de um mesmo grupo têm maior

semelhança entre si que os objetos em grupos diferentes. Assim, deseja-se que cada

grupo formado represente uma classe que o sistema descobriu automaticamente, já

que todos ou maior parte dos objetos pertencentes a um mesmo grupo são

semelhantes e geralmente possuem a mesma classe. Normalmente, após a obtenção

dos grupos é necessário analisá-los para determinar o que cada um deles significa

no contexto do problema que se está explorando.

3.1. Aprendizado de Máquina Supervisionado

3.1.1. Rough Sets

A teoria de Rough Sets foi desenvolvida por Pawlak (1982). Segundo Pila

(2001) essa teoria é uma abordagem matemática para manipular imprecisão e

ambigüidade. Ela baseia-se na filosofia de que o conhecimento consiste na

habilidade de classificar objetos (Slowinski, 1995).

Rough Sets apresenta conceitos bastante úteis para a manipulação de dados e

geração de regras, por exemplo, o conceito de Reduto permite reduzir a “largura”

das bases de dados através da eliminação de atributos irrelevantes. A remoção de

atributos resulta, também, na redução da largura das regras induzidas. Outros

conceitos importantes são os de aproximação superior e inferior, os quais

possibilitam o tratamento de conflitos existentes nos dados.

Rough Sets foi desenvolvida para trabalhar apenas com atributos discretos,

sejam eles nominais ou numéricos, mas pode ser estendida para manipular atributos

reais. Para isso faz-se necessário discretizar os atributos reais transformando-os em

intervalos de valores. Por exemplo, um atributo que assume valores que variam de -

1,58 a 10 pode ser discretizado para os intervalos [-1,58; 4[, [4; 6[ e [6; 10[.

Neste trabalho a teoria de Rough Sets foi usada para geração de regras,

assim foi explorado o conceito de Reduto para redução da quantidade de atributos

da base de dados. Por isso esta seção limita-se a explicação dos conceitos

necessários ao cálculo dos Redutos. Maiores detalhes sobre a teoria de Rough Sets

podem ser encontrados em (Pawlak, 1982; Pila, 2001).

Em Rough Sets as informações sobre o mundo real são representadas na

forma de uma tabela denominada de Sistema de Informação (SI)

Definição 1: um SI é um par ordenado S = (U, A), no qual U é um conjunto finito e

não vazio denominado de universo e A é um conjunto finito e não vazio de

elementos denominados de atributos (Pila, 2001). A Tabela 3.2 representa um SI.

Atributos

Objetos

Dor de

Cabeça

Dor

Muscular

Temperatura

e1 sim sim normal

e2 sim sim alta

e3 sim sim muito alta

e4 não sim normal

e5 não não alta

e6 não sim muito alta

e7 não não alta

e8 não sim muito alta

Tabela 3.2 – Exemplo de Sistema de Informação.

Rough Sets é uma teoria que trabalha segundo o conceito de aprendizado

supervisionado, assim ela necessita de uma classe para cada objeto do SI. A adição

dessa classe caracteriza um Sistema de Decisão (SD).

Definição 2: um Sistema de Decisão (SD) é um SI da forma S = (U, A ∪ {d}), em

que d ∉ A é o atributo de decisão. A Tabela 3.3 mostra um SD.

Atributos Decisão

Objetos

Dor de

Cabeça

Dor

Muscular

Temperatura Gripe

e1 sim sim normal não

e2 sim sim alta sim

e3 sim sim muito alta sim

e4 não sim normal não

e5 não não alta não

e6 não sim muito alta sim

e7 não não alta sim

e8 não sim muito alta não

Tabela 3.3 – Exemplo de Sistema de Decisão.

Um dos principais conceitos envolvidos na teoria de Rough Sets é a relação

de não-discernimento, isto é, considera-se que dois ou mais objetos de um SD são

indiscerníveis, levando-se em consideração um determinado conjunto de atributos,

quando não é possível verificar a que classe eles pertencem olhando apenas para os

atributos. Isso significa dizer que todos os atributos considerados para aqueles

objetos têm o mesmo valor. Por exemplo, tomando o SD da Tabela 3.3 e

considerando os atributos “Dor de Cabeça” e “Dor Muscular” pode-se dizer que os

objetos e1, e2 e e3 são indiscerníveis. O cálculo das relações de não-discernimento

é importante, pois permite descobrir quais atributos são irrelevantes e podem ser

removidos do SD.

Definição 3: para cada subconjunto de atributos B

⊆

A no SI S = (U, A), é

associada uma relação de não-discernimento definida por IND

(B) = {(x,y)∈U

∀a ∈ B, a(x) = a(y)}, em que a(x) corresponde ao valor do atributo a no objeto x e

a(y) corresponde ao valor do atributo a no objeto y. O conjunto de objetos

pertencente a uma mesma relação de não-discernimento é denominado de classe de

equivalência. O conjunto de todas as classes de equivalência é denotado por

U/IND

(B) ou simplesmente U/IND (B)

Considerando todos os possíveis subconjuntos, não-vazios, de atributos do

sistema de informação da Tabela 3.2 tem-se as seguintes classes de equivalência

(Figura 3.1).

Quando não há dúvidas sobre qual SI se está referenciando o subscrito S é normalmente omitido na relação

de não discernimento. Assim IND

(B) e U/IND

(B) podem ser escritas, respectivamente, como IND (B) e

U/IND(B).

Figura 3.1 – Todas as classes de equivalência para o SI da Tabela 3.2.

Para o exemplo da Figura 3.1 quando é verificada a relação de não

discernimento para todos os atributos são encontradas as seguintes classes de

equivalência:

E1 = {e1}, E2 = {e2}, E3 = {e3}, E4 = {e4}, E5 = {e5,e7} e E6 = {e6,e8}

Verifica-se que a classe E5 contém os objetos e5 e e7, os quais são

indiscerníveis entre si. Raciocínio análogo segue para a classe de equivalência E6.

Atributos

Exemplos

Dor de

Cabeça

Dor

Muscular

Temperatura

E1 sim sim normal

E2 sim sim alta

E3 sim sim muito alta

E4 não sim normal

E5 não não alta

E6 não sim muito alta

Tabela 3.4 – Classes de equivalências para B = {Dor de Cabeça, Dor muscular, Temperatura}.

Os próximos conceitos (Matriz de Discernimento, Função de Discernimento

e Redutos) fundamentam a remoção de atributos irrelevantes do SD.

Em uma matriz de discernimento os índices são as classes de equivalência e

cada elemento é composto pelos atributos que permitem a distinção entre as classes,

por exemplo, o elemento [E1, E2] = Temperatura, significa que o atributo

Temperatura permite a distinção entre as classes E1 e E2. De fato, verificando na

Tabela 3.4 apenas esse atributo possui valor diferente quando comparadas as

classes E1 e E2. A Matriz de Discernimento é sempre simétrica como pode ser

visto na Tabela 3.5 onde a região triangular mais escura é idêntica a mais clara.

U/IND ({Dor de Cabeça}) = {{e1, e2, e3}, {e4, e5, e6, e7, e8}}

U/IND ({Dor Muscular}) = {{e1, e2, e3, e6, e8},{e5, e7}}

U/IND ({Temperatura}) = {{e1, e4}, {e2, e5, e7}, {e3, e6, e8}}

U/IND ({Dor de Cabeça, Dor Muscular}) = {{e1, e2, e3}, {e4, e6, e8}, {e5, e7}}

U/IND ({Dor de Cabeça, Temperatura}) = {{e1},{e2},{e3},{e4},{e5,e7},{e6,e8}}

U/IND ({Dor Muscular, Temperatura}) = {{e1, e4},{e2},{e3, e6, e8},{e5, e7}}

U/IND ({Dor de Cabeça, Dor Muscular, Temperatura}) = {{e1},{e2},{e3},{e4},{e5,e7},{e6,e8}}

Definição 4: para um conjunto de atributos B ⊆A em S = (U, A), uma matriz de

discernimento é dada por:

(B) = {m

(i, j)}

n x n

, onde 1

≤

i, j

≤

n, com n = |U/IND(B)|,

e m

(i, j) = {a ∈B | a(E

) ≠ a(E

)} para i, j = 1, 2, ..., n

Classes E1 E2 E3 E4 E5 E6

Dor de Cabeça Dor de Cabeça

---------- Temperatura Temperatura Dor de Cabeça Dor Muscular

Temperatura Temperatura

Dor de Cabeça Dor de Cabeça Dor de Cabeça

Temperatura ---------- Temperatura

Temperatura Dor Muscular Temperatura

Dor de Cabeça Dor de Cabeça

Temperatura Temperatura ---------- Dor Muscular Dor de Cabeça

Temperatura Temperatura

Dor de Cabeça Dor de Cabeça Dor Muscular

Dor de Cabeça ---------- Temperatura

Temperatura Temperatura

Temperatura

Dor de Cabeça Dor de Cabeça Dor de Cabeça Dor Muscular Dor Muscular

Dor Muscular Dor Muscular ----------

Temperatura Dor Muscular Temperatura Temperatura

Temperatura

Dor de Cabeça Dor de Cabeça Dor Muscular

Dor de Cabeça Temperatura ----------

Temperatura Temperatura Temperatura

Tabela 3.5 – Matriz de Discernimento.

A Função de Discernimento define conjunções de disjunções dos elementos

da Matriz de Discernimento. Assim o conjunto de variáveis booleanas (atributos do

SD original) é, então, simplificado e resulta em um ou mais conjuntos mínimos de

atributos denominados de Redutos. Assim, aos Redutos pertencem apenas aqueles

atributos que são indispensáveis para distinguir os elementos do SD.

Definição 5: uma função de discernimento é dada por

),()(

jiD

EEmBf ∨∧=

onde i, j

∈

{1, 2, ..., n}, n = |U/IND(B)| e

),(

jiD

EEm∨

é a disjunção sobre o

conjunto de variáveis booleanas

),(

jiD

EEm que corresponde ao elemento

),( jim

da Matriz de Discernimento.

Segundo Pila (2001), a função de discernimento computa o conjunto

mínimo de atributos necessários para distinguir qualquer classe de equivalência das

demais.

A equação 3.1 mostra o cálculo da função de discernimento referente à

Matriz de Discernimento da Tabela 3.5 em função das Classes de Equivalência.

Fazendo todas as substituições e as simplificações necessárias encontra-se um dos

possíveis Redutos representado na equação 3.2.

O reduto encontrado {Temperatura, Dor de Cabeça} significa que esses

atributos são suficientes para distinção dos elementos do SD. Assim o atributo Dor

Muscular pode ser removido sem mais problemas.

),(),(),(),(),(),(

)(

665646362616

655545352515

645444342414

635343332313

625242322212

615141312111

EEmEEmEEmEEmEEmEEm

DDDDDD

∨∧∨∧∨∧∨∧∨∧∨

∧∨∧∨∧∨∧∨∧∨∧∨

3.1

CabeçadeDoraTemperaturBf __)( ∧=

3.2

Definição 6 (Redutos): um reduto de um conjunto de atributos B é um conjunto de

atributos B

⊆ B tal que todos os atributos a ∈ B - B

são dispensáveis e IND(B

)

= IND(B). O termo RED(B) denota a família de redutos de B.

Após a remoção do atributo dispensável o sistema de decisão é reduzido ao

exposto na Tabela 3.6. Por fim o exemplo de regras geradas para esta tabela seriam

as seguintes:

SE (Dor de Cabeça = sim) E (Temperatura = normal) ENTÃO (Gripe = não)

SE (Dor de Cabeça = sim) E (Temperatura = alta) ENTÃO (Gripe = sim)

SE (Dor de Cabeça = sim) E (Temperatura = muito alta) ENTÃO (Gripe = sim)

SE (Dor de Cabeça = não) E (Temperatura = normal) ENTÃO (Gripe = não)

SE (Dor de Cabeça = não) E (Temperatura = muito alta) ENTÃO (Gripe = sim) OU (Gripe = não)

SE (Dor de Cabeça = não) E (Temperatura = alta) ENTÃO (Gripe = sim) OU (Gripe = não)

Atributos Decisão

Exemplos

Dor de

Cabeça

Temperatura Gripe

e1 sim normal não

e2 sim alta sim

e3 sim muito alta sim

e4 não normal não

e5 não alta não

e6 não muito alta sim

e7 não alta sim

e8 não muito alta não

Tabela 3.6 – Sistema de Decisão Reduzido.

É importante evidenciar que neste trabalho não foram usados os conceitos

de aproximação superior e inferior (Pawlak, 1982) existentes na teoria Rough Sets,

assim a teoria foi utilizada apenas para redução do conjunto de atributos a fim de

gerar regras com poucos elementos em seus termos antecedentes.

Nos experimentos realizados com Rough Sets, a discretização dos dados foi

feita com o algoritmo Entropy/MDL, pois ele obteve melhor desempenho nos

experimentos executados por Karthigasoo, Cheach e Manickam (2005) e Abidi,

Hoe e Goh (2001). Os redutos foram gerados com Johnson Algoritmo, uma vez que

esse algoritmo é bastante utilizado pela comunidade científica e foi o que

possibilitou a geração de menor quantidade de regras nos trabalhos de Karthigasoo,

Cheach e Manickam (2005).

3.1.2. Árvores de Decisão

Técnicas que produzem Árvores de Decisão (AD) são amplamente

utilizadas pela comunidade científica no Aprendizado de Máquina indutivo

(Mitchell, 1997). Segundo Breiman et al. (1984) esses algoritmos utilizam a

estratégia de dividir um problema complexo em subproblemas mais simples. Assim

um conjunto de dados de treinamento é dividido recursivamente até que cada

subconjunto obtido pelas sucessivas divisões contenha apenas elementos

pertencentes à mesma classe. Uma vez construída a árvore ela poderá ser usada

para classificar novos exemplos que não pertenciam à base de dados original. A

classificação de novos exemplos é processada computacionalmente através de

regras extraídas da árvore. As regras são obtidas percorrendo-se todos os possíveis

caminhos da Árvore, desde a raiz até as folhas (classes).

As Árvores de Decisão possuem dois tipos de nós: 1) nós de decisão, que

fazem o teste de um único atributo; e 2) nós folhas, que especificam a classe. O

caminho percorrido desde o nó raiz até uma folha determina uma regra do tipo SE-

ENTÃO.

Segundo (Liu et al., 2000), do ponto de vista geométrico uma AD representa

segmentações do espaço de dados. Como exemplo tomemos a Figura 3.2. O gráfico

à esquerda mostra um espaço bi-dimensional com vários objetos distribuídos. Há

duas classes: classe C1 (quadrado) e classe C2 (círculo). À direita é mostrada a AD

gerada a partir dos dados. Todas as possíveis regras que podem ser extraídas da

Árvore são representadas na Figura 3.3.

Figura 3.2 – Exemplo de Árvore de Decisão.

Extraído de (Liu et al., 2000).

Figura 3.3 – Regras extraídas da Árvore de Decisão.

As estruturas de árvores são facilmente interpretáveis por humanos e

também apresentam fácil manipulação. Essas são características proveitosas desse

tipo de modelo, pois especialistas podem facilmente analisar os resultados e obter

conclusões sobre o domínio do problema que se está explorando.

E (X <= 3,5)

NTÃO C

SE (X > 3,5) E (Y <= 4) E (X <= 8,5) ENTÃO C

SE (X > 3,5) E (Y <= 4) E (X > 8,5) ENTÃO C

SE (X > 3,5) E (Y > 4) ENTÃO C

Esse tipo de algoritmo também apresenta algumas características

indesejáveis. Algoritmos que geram árvores são pouco robustos a dados de grandes

dimensões; apresentam uma certa dificuldade de lidar com atributos contínuos; e,

ainda apresentam grande sensibilidade aos dados de treinamento, isso significa

dizer que pequenos erros nos dados de treinamento podem afetar em maiores

proporções o classificador (árvore) gerado (Mitchell, 1997). Neste trabalho

lidaremos diretamente com esses problemas, pois os dados que usaremos como

entrada para o algoritmo de AD serão dados de expressão gênica, os quais têm a

característica de apresentar ruídos

e, também, grande quantidade de atributos

(Slonim, 2002).

Um dos primeiros algoritmos desenvolvidos para geração de Árvores de

Decisão foi o ID3 (Quinlan, 1986) e seu sucessor C4.5 (Quinlan, 1993). Muitos dos

algoritmos que têm sido desenvolvidos para geração de Árvores de Decisão, são

variações desses primeiros. O ID3 apenas trabalha com dados que possuem

atributos com valores discretos, ou seja, atributos que assumem um determinado

número de valores. Já o C4.5 tem a capacidade de lidar com atributos que

armazenam valores contínuos. O C4.5 também pode combater o problema de

overfitting

, utilizando a estratégia de “poda da árvore”.

3.1.3. Top Scoring Pairs

O TSP (Top Scoring Pairs) nasceu da necessidade de gerar classificadores a

partir de dados de expressão gênica que além de precisos fossem, também, de fácil

interpretação por humanos (Geman, 2004). Assim a técnica consiste na geração de

regras com poucos elementos em seu corpo, ou melhor, apenas um par de genes no

corpo de cada regra.

De maneira geral o TSP trabalha para descobrir a diferença entre duas

classes através da procura por par de genes que invertem os seus níveis de

expressão de uma classe para outra (Geman, 2004). A idéia de avaliar genes aos

Os ruídos são erros nos dados. Eles podem ser derivados do próprio processo que gerou os dados, do

processo de aquisição de dados ou do processo de transformação (Slonim, 2002).

Overfitting é a característica que um indutor tem de gerar um classificador super ajustado aos dados de

treinamento, ou seja, ele é tão específico para aquele conjunto de treinamento que perde a capacidade de

generalização desejada nos processos de AM. Um classificador assim não obtém sucesso quando da

classificação de novos dados.

pares para classificação de dados de microarray foi inicialmente empregada em BØ

e Jonassen (2002).

Consideremos, a título de exemplo, uma matriz M

m x n

, de níveis de

expressão de genes. Em que m corresponde ao número de amostras (objetos) e n-1

ao número de genes para os quais foram medidos os níveis de expressão. Assim

cada elemento da matriz, com exceção da última coluna (coluna n) que representa a

classe, corresponde ao nível de expressão do gene coluna no experimento linha.

Cada objeto é, então, um vetor de genes X = {X

, X

, ..., X

n-1

}. Para cada X há uma

classe associada C

∈

{1, 2, ..., c}.

Por simplicidade consideraremos C = 2. O objetivo é encontrar a um par de

genes (i, j) para o qual há uma significante diferença na probabilidade de X

< X

classe 1 para a classe 2. A classificação dos experimentos é, então, baseada na

probabilidade p

< X

| C), ou seja, a probabilidade de encontrar X

< X

em cada classe.

A diferença de probabilidades de X

< X

da classe 1 para a classe 2 é

denominada de score em (Geman, 2004; Tan et al., 2005). O score é calculado

como ∆

= |p

(1) - p

(2)|. A técnica procura por par de genes que possuam o maior

score.

Vejamos um exemplo mostrado em (Geman, 2004). A Tabela 3.7 apresenta

a distribuição de freqüência para os pares (X

< X

)

e (X

> X

) de 102 exemplos, dos

quais 52 são classificados como pertencentes à classe 1 (tecido com câncer) e 50

pertencentes a classe 2 (tecido normal). As probabilidades são calculadas como

(1) = 50/52 e p

(2) = 3/50. Isso resulta no score ∆

= | (50/52) – (3/50) | = 0,902.

Como p

(1) > p

(2) a regra para esse par de genes seria definida da seguinte

maneira:

SE (X

< X

) ENTÃO classe 1, SENÃO classe 2. Os scores são calculados

para todas as combinações de genes X

, X

, mas só os scores com o maior valor

definem regras. Em alguns casos há apenas um score (Geman, 2004).

< X

> X

Classe 1 50 2 52

Classe 2 3 47 50

Tabela 3.7 – Exemplo de distribuição de freqüências de par de genes.

Extraído de (Geman, 2004).

Apesar de o exemplo ter mostrado como são geradas regras para apenas

duas classe; o TSP pode ser usados para gerar regras para uma quantidade de

classes C > 2. Por exemplo, consideremos três classes (classe1, classe2 e classe3),

C = 3. A técnica é, primeiramente, aplicada aos dados considerando apenas duas

classes (classe1) e (classe2

OU classe3). As regras geradas seriam do tipo SE (X

< X

) ENTÃO (classe1) SENÃO (classe2 OU classe3). Após isso os objetos

correspondentes a classe1 são eliminados dos dados e o processo é repetido, mas

agora considerando apenas as classes classe2 e classe3. Por fim as regras geradas

são do tipo

SE (X

< X

) ENTÃO (classe2) SENÃO (classe3). Os dois conjuntos de

regras geradas se completam.

3.1.4. Avaliação de Regras

Regras podem ser avaliadas em conjunto ou individualmente. Quando em

conjunto (todo o conjunto de regras é considerado como uma hipótese) as medidas

são baseadas em uma matriz de confusão. Uma matriz de confusão mostra o

número de classificações corretas em relação ao número de classificações preditas

para cada classe (Resende et al., 2003). Os resultados são, então, organizados em

duas dimensões, classes verdadeiras e classes preditas para k classes diferentes

(Tabela 3.8).

Classes PreditaC1 PreditaC2

...

PreditaCk

verdadeiraC1 m(C1,C1) m(C1,C2) ... m(C1,Ck)

verdadeiraC2 m(C2,C1) m(C2,C2) ... m(C2,Ck)

... ... ... ... ...

verdadeiraCk m(Ck,C1) m(Ck,C2) ... m(Ck,Ck)

Tabela 3.8 – Exemplo de Matriz de Confusão.

Cada elemento m(i,j) da matriz, com i,j= 1, 2, ..., k e i ≠ j, representa o

número de elementos que pertencem a classe i, mas foram classificados com

pertencentes a classe j. O número de acertos para cada classe encontra-se na

diagonal principal, ou seja, quando i = j. Assim a precisão “acurácia” de todo o

conjunto de regras é determinado por

jiM

kji

∑

},...,2,1{,

),(

, onde i = j e n é o

número de regras avaliadas.

Neste trabalho, além da medida de precisão, são utilizadas outras medidas

para a avaliação de regras. Algumas dessas medidas são bastante específicas e são

explicadas na Seção 4.3.2 (Avaliação de Regras).

3.2. Aprendizado de Máquina Não Supervisionado

A grande maioria dos algoritmos de agrupamento faz o uso de alguma

medida de distância para calcular a semelhança entre dois objetos ou dois grupos de

objetos. As medidas de distâncias podem trabalhar com atributos nominais

(categóricos) ou lineares (números reais). Assim para cada caso há alguns tipos de

medidas de distâncias na literatura. As equações 3.3, 3.4 e 3.5 mostram algumas das

medidas mais comuns (Jain e Dubes, 1988). Para exemplificação consideremos a

distância entre dois objetos

x = {x

, x

} e y = {y

, y

}. Cada objeto possui dois

atributos x

, x

e y

, y

. Observe na Figura 3.4, que a distância Euclidiana coincide

com a distância vetorial entre os dois objetos.

Euclidiana:

∑

−

yxd

)(

),(

3.3

Manhattan, Hamming ou city block:

∑

−=

yxyxd

||),(

3.4

Tchebyschev: ||max),(

...2,1

yxyxd −=

3.5

Figura 3.4 – Exemplo de cálculo de distâncias.

Adaptado de (Pedrycz, 2005).

Neste trabalho foi escolhido o uso da distância Euclidiana como um dos

parâmetros de configuração dos algoritmos k-means e Agrupamento Hierárquico. O

motivo da escolha se deve ao fato dessa medida ser amplamente explorada pela

comunidade científica em experimentos com dados de expressão gênica (Slonim,

2002; Quackenbush, 2001).

3.2.1. Algoritmo de Agrupamento Hierárquico

As técnicas de agrupamento hierárquico consistem em sucessivas divisões

(métodos divisivos) ou agrupamentos (métodos aglomerativos) de elementos de um

espaço n-dimensional. Nos métodos divisivos, inicialmente, os objetos estão juntos

em um único grupo, que é dividido formando dois ou mais grupos. Cada um dos

grupos formados é novamente dividido em um ou mais grupos. As divisões

continuam até cada grupo possuir apenas um objeto. As técnicas aglomerativas

trabalham de maneira inversa às anteriores. Nas aglomerativas, inicialmente é

considerado a existências de tantos grupos quantos forem os objetos. Esses grupos

unitários são então unidos uns com os outros através do critério da medida da

menor distância. Assim cada grupo tem sua distância medida entre todos os outros

grupos. Aqueles que apresentarem menor distância serão fundidos. O processo

continua até existir apenas um único grupo constituído de todos os objetos (Eisen,

1998).

As técnicas divisivas têm um custo computacional bastante elevado quando

comparadas as aglomerativas, por isso elas são pouco mencionadas na literatura.

Sendo então as técnicas aglomerativas as mais utilizadas (Kaufman e Rousseeuw,

1990; Doni, 2004).

O resultado dos agrupamentos hierárquicos são mais bem representados na

forma de uma árvore de hierarquia denominada de dendrograma (Jain, Murty e

Flynn, 1999). A título de exemplo, considere um espaço bidimensional constituído

pelos seguintes objetos:

Objeto 1: (1,0; 2,0)

Objeto 2: (2,5; 4,5)

Objeto 3: (2,0; 2,0)

Objeto 4: (4,0; 1,5)

Objeto 5: (4,0; 2,5)

Cada objeto pode ser visto como um vetor de dois atributos, por exemplo, o

“Objeto 1” possui os atributos 1,0 e 2,0. As sucessíveis etapas do processo do

algoritmo estão representadas na Figura 3.5. O dendrograma para o processo

aglomerativo pode ser visto na Figura 3.6.

Figura 3.5 – Representação das etapas de agrupamento hierárquico.

Figura 3.6 – Exemplo de Dendrograma.

A partir do conhecimento prévio sobre o domínio do problema que se está

analisando deve-se escolher uma distância de corte no dendrograma para definição

dos grupos (Doni, 2004). A Figura 3.7 mostra o dendrograma do exemplo anterior

com três possíveis cortes. O “Corte 1” determina três grupos {1, 3}, {4, 5} e {2}. O

“Corte 2” determina dois grupos {1, 3, 4, 5} e {2} e o “Corte 3” determina o grupo

raiz constituído por todos os elementos {1, 2, 3, 4, 5}.

Figura 3.7 – Exemplo de Dendrograma com cortes.

Existem algumas diferenças no processamento desses algoritmos quanto ao

cálculo das distâncias entre os grupos. As mais difundidas são: ligação média (em

inglês, average linkage), ligação simples (em inglês, single linkage) e ligação

completa (em inglês, complete linkage) (Hair et al., 2005). Os algoritmos

hierárquicos com ligação completa consideram como distância entre dois grupos a

maior distância encontrada entre um objeto de um grupo e um objeto do outro

grupo. No algoritmo de agrupamento hierárquico com distância simples a distância

entre dois grupos é a menor encontrada entre um elemento de um grupo e um do

outro grupo. Já no agrupamento hierárquico com ligação média calcula-se a

distância entre dois grupos pela proximidade média entre os objetos de um grupo

com os de um outro grupo. As técnicas que usam ligação completa formam grupos

mais compactos e mais distantes entre si; já as técnicas que fazem o uso da ligação

simples formam grupos mais próximos com formatos alongados; e, por último as

técnicas que usam ligação média formam grupos compactos com tendência a exibir

formas esféricas.

Neste trabalho foi escolhida a ligação média por ser extensivamente usada

na literatura de expressão gênica (Eisen, 1998; Alizadeh et al., 2000).

3.2.2. Algoritmo de Agrupamento k-means

O k-means trabalha agrupando objetos em k número de grupos, em que k >

1. O número k deve ser definido previamente pelo usuário. Essa dependência

caracteriza uma deficiência do algoritmo para certos contextos de problemas, pois

na maioria das vezes não há conhecimento da quantidade de grupos ou classes

existentes no conjunto de dados. Mesmo assim k-means é uma técnica bastante

difundida em AM. É um algoritmo clássico e de implementação relativamente

simples, por isso é bastante usado pela comunidade científica (Jain, Murty e Flynn,

1999). Muitas vezes ele faz parte de sistemas de AM mais complexos sendo, por

exemplo, usado como referência para comparação com outras técnicas ou novas

técnicas propostas.

O k-means trabalha tentando minimizar a soma dos quadrados das distâncias

entre os objetos e seus respectivos centros de grupo (centróides). Inicialmente

podem ser escolhidos k objetos aleatórios para serem os centros dos k grupos. São

então calculadas as distâncias de cada objeto para cada centro de grupo. Cada

objeto será considerado pertencente ao grupo do centróide que ele ficou mais

próximo, ou seja, teve menor distância calculada. Após a etapa anterior estão

formados k grupos. É calculado o centro geométrico de cada novo grupo (o novo

centróide de cada grupo). O processo continua até que se chegue a um determinado

número de iterações configurado inicialmente como ponto de parada, ou não haja

mais mudanças significativas, isto é, os objetos não mudem de grupos a cada etapa.

O k-means se comporta melhor com dados que contenham grupos esféricos. Assim,

grupos com outra geometria podem não ser encontrados (Jain, Murty e Flynn,

1999).

3.2.3. Avaliação de Agrupamentos com Índices de Validação

Consideremos a base de dados da Tabela 3.9 como sendo um exemplo de

base de dados de microarray para agrupamento. Consideremos também que estes

dados foram agrupados através de algum algoritmo de agrupamento e que foram

gerados dois grupos rotulados com os símbolos “0” e “1”. Assumindo que a técnica

alcançou uma porcentagem de acerto de 100%, ou seja, todos os objetos de classes

distintas ficaram em grupos distintos e todos os objetos de mesma classe ficaram no

mesmo grupo. Têm-se, então, os grupos:

Grupo 0 = {Paciente 1, Paciente 4}

Grupo 1 = {Paciente 2, Paciente 3}

Objetos Gene 1 ... Gene N Classe

Paciente 1 0,2548 ... 0,3254 2

Paciente 2 0,9856 ... 0,9989 1

Paciente 3 0,9985 ... 0,9896 1

Paciente 4 0,2049 ... 0,3352 2

Tabela 3.9 – Exemplo de base de dados para agrupamento.

Organizando os grupos em uma tabela no formato de uma base de dados

obtém-se a Tabela 3.10, na qual é facilmente observável que o Grupo 0 corresponde

aos objetos da Classe 2 e que o Grupo 1 aos da Classe 1. No entanto, nos problemas

do mundo real nem sempre os agrupamentos são perfeitos. Também, no mundo real

nem sempre é possível fazer essa análise visual e determinar a que classe

corresponde cada grupo, como foi feita neste exemplo, pois geralmente são

agrupadas grandes quantidades de dados com muitos atributos. Em muitos casos os

grupos também não são homogêneos nem perfeitos.

Objetos Gene 1 ... Gene N Grupo

Paciente 1 0,2548 ... 0,3254 0

Paciente 2 0,9856 ... 0,9989 1

Paciente 3 0,9985 ... 0,9896 1

Paciente 4 0,2049 ... 0,3352 0

Tabela 3.10 – Exemplo de base de dados agrupada.

A maneira mais racional para se fazer uma avaliação dos resultados do

agrupamento seria uma comparação da coluna “Classe” da base de dados original

com a coluna “Grupo” da base de dados agrupada (Tabela 3.11). Mas como os

símbolos que representam as classes e os grupos são diferentes não é possível fazer

essa comparação. Os símbolos para a representação dos grupos são determinados

pelo algoritmo da técnica de agrupamento e podem ser qualquer um, ou seja, pode-

se dar qualquer nome a grupos de dados independentemente da classe a que seus

elementos pertencem, pois a única certeza que se tem de agrupamentos é que seus

elementos apresentam características semelhantes.

Classe Grupo

2 0

1 1

2 0

Tabela 3.11 – Comparação de Classe com Grupo para avaliação de agrupamento.

Os resultados de técnicas de agrupamento podem, então, ser avaliados por

índices de validação. O objetivo da avaliação é verificar o quanto os grupos

formados representam as reais características dos dados. Segundo Jain e Dubes

(1988) esses índices deverão verificar se os grupos formados capturam

características intrínsecas dos dados.

Os principais índices de validação encontrados na literatura são os índices

externos e internos (Handl, Knowles e Kell, 2005). Os índices externos avaliam os

agrupamentos através de sua comparação com as classes originais contidas na base

de dados, que foi usada como entrada para as técnicas de agrupamento. Já os

índices internos usam estratégias que permitem verificar a qualidade dos grupos

formados através da comparação apenas com os dados de entrada, ou seja, nenhuma

informação sobre as classes dos objetos da base de dados é necessária (Jain e

Dubes, 1988).

Os índices internos, em geral, realizam suas medidas baseados na

homogeneidade e compactação dos grupos formados. Sendo assim, eles fornecem

uma medida teórica de quanto bom é um determinado grupo. Já os índices externos

apresentam um resultado que provém da comparação com a informação a priori, ou

seja, com a real estrutura dos grupos existente nos dados. Assim, sempre que

possível (sempre que existir informação a priori), será mais significativo utilizar

uma medida de avaliação de agrupamentos baseada em índices externos.

Consideremos as duas colunas da Tabela 3.11 como partições, ou melhor,

partição A sendo a coluna “Classe” e a partição B sendo a coluna “Grupo”. Dessa

maneira índices externos como Hubbert, Jaccard, Rand e Rand Corrigido

(Corrected Rand) fornecem um valor que mede o grau de concordância que há

entre duas partições A e B.

Alguns desses índices são sensíveis à quantidade de classes nas partições ou

distribuição de objetos por classe (Dubes, 1987). Por exemplo, os índices Hubbert e

Rand têm a característica de apresentar valores elevados para partições com muitas

classes. Já o Jaccard tende a fornecer valores elevados para partições com poucas

classes. O índice Rand Corrigido não apresenta tais características indesejáveis

(Milligan e Cooper, 1986).

O Rand Corrigido fornece valores no intervalo [-1, 1], onde 1 significa que

as partições são perfeitamente concordantes e valores próximos de 0 ou negativos

correspondem a concordâncias encontradas ao acaso. De fato análises realizadas

por (Milligan e Cooper, 1986) indicam que índices próximos de 0,05 ainda não

representam grupos encontrados ao acaso.

Para o cálculo do Corrected Rand formulemos a matriz de confusão

representada na Tabela 3.12, na qual as linhas correspondem a objetos da partição A

e as colunas a objetos da partição B. Denominando de N

o elemento pertencente à

linha i e coluna j da matriz, onde N

é o número de ocorrências do casamento do

objeto linha da partição A e coluna da partição B da matriz de confusão encontrados

nas partições A e B quando elas são dispostas lado a lado (Tabela 3.11), por

exemplo, o elemento N

corresponde ao casamento do valor 2 (dois) da partição A

com 0 (zero) da partição B, quando estas partições são dispostas lado a lado (Tabela

3.11) encontra-se esse casamento duas vezes, portanto N

= 2. Denominando,

também, N

como sendo a soma de todos os elementos da matriz de confusão em

cada linha i; N

a soma de todos os elementos da matriz em cada coluna j; e, por

último, N como sendo a soma de todos os N

ou a soma de todos os N

0 1

Total

0 2 2

2 0 2

Total

2 2 4

Tabela 3.12 – Matriz de confusão para as partições Grupo e Classe.

Finalmente, após definida a matriz de confusão e todos os seus elementos o

cálculo do Corrected Rand é realizado através das seguintes equações (Kuncheva,

2004).

∑













3.6

∑













3.7

)1(

−

3.8

321

)(

),(

ttt

BACR

−+

−













∑∑

−=

3.9

Nas equações são considerados C

como sendo o número de classes

encontrados na partição A e C

o número de classes na partição B. Por convenção

assumi-se que quando N

< 2 o binômio de Newton













Aplicando as equações às partições A e B tem-se:

= 2; C

= 2; e

)22(

),(

−+

−

=BACR

O resultado igual a 1 confirma a concordância perfeita entre as partições A e

B. Isso demonstra que o Rand Corrigido pode ser utilizado como um índice de

avaliação de resultados de agrupamentos.

Capítulo 4

4. Métodos, Experimentos e Resultados

Métodos, Experimentos e Resultados

Este capítulo descreve a forma como os experimentos foram realizados e

apresenta os resultados obtidos.

A Seção 4.1 mostra as bases de dados utilizadas nos experimentos; a Seção

4.2 descreve os experimentos; a Seção 4.3 mostra a forma como os resultados

foram avaliados; e, por último, a Seção 4.4 apresenta os resultados obtidos.

4.1. Bases de Dados

Foram utilizadas três bases de dados para execução dos experimentos,

Gaussian3, Simulated6 e St. Jude Leukemia. As duas primeiras são bases de dados

sintéticas, que simulam dados de microarray, criadas para testar algoritmos de AM

no contexto de análise de expressão gênica (Monti et al., 2003). A terceira, St. Jude

Leukemia, é uma base de dados obtida a partir de dados de expressão gênica de

células com leucemia (Monti et al., 2003; Yeoh et al., 2002). A Tabela 4.1 resume

algumas características das bases de dados.

Base de Dados

Quantidade

Atributos

Quantidade

de Objetos

Quantidade

de Objetos

or Classe

Classes

BCR-ABL

E2A-PBX1

Hyp>50

MLL

T-ALL

248St. Jude Leukemia 985

Gaussian3 600

Simulated6 600

Tabela 4.1 – Características das bases de dados.

As duas bases de dados sintéticas possuem atributos relacionados a cada

uma de suas classes. Assim na Gaussian3 há um conjunto de 200 atributos que

determinam cada classe, essa relação de atributo com classe é exclusiva, ou seja, os

200 atributos que determinam a classe 2, por exemplo, não determinam a classe 0

nem a classe 1. Semelhante a Gaussian3 a Simulated6 apresenta conjuntos de 50

atributos exclusivamente relacionados a cada classe. Tendo seis classes na

Simulated6 e conjuntos de 50 atributos exclusivamente relacionados a cada classe

totaliza-se 300 atributos. Como a Simulated6 tem 600 atributos, os 300 restantes

são ruídos (Monti et al., 2003).

A relação de atributos com classes, nas bases de dados sintéticas, se da

seguinte maneira: os atributos que determinam ou se relacionam com determinada

classe têm maiores valores e maior variância destes valores quando comparados

com os outros atributos da mesma base de dados.

Sobre a St.

Jude Leukemia considerando ela como uma matriz M(i,j)

n x m

suas n linhas (exemplos, objetos, instâncias) são amostras de células com leucemia

e suas m colunas (atributos) são genes. Assim cada elemento m(i,j) da matriz é um

número que mede o nível de expressão do gene j encontrado na amostra de célula i.

Foram realizadas as seguintes etapas de pré-processamento das bases de

dados:

Remoção do atributo classe: todas essas bases de dados originalmente

possuem informação a priori, assim o atributo classe foi removido para

que elas pudessem ser usadas em técnicas de agrupamento.

Normalização: os valores dos atributos apresentam escalas bastante

distantes, como isso pode atrapalhar o desempenho de técnicas de

agrupamento que trabalham com alguma medida de distância, todos os

atributos foram convertidos para o intervalo de [0,1]. Para todos os

valores foi aplicada a função de normalização mostrada na equação 4.1.

Na qual v é o valor atual do atributo, min(v) o menor valor de atributo

encontrado em toda a base de dados, max(v) o maior valor de atributo

encontrado na base de dados e v

o novo valor do atributo normalizado.

))min()(max(

))min((

−

4.1

4.2. Experimentos

Como o objetivo principal deste trabalho é desenvolver ou estimular o

desenvolvimento de técnicas para análise de dados de microarray que sejam mais

facilmente interpretadas, os experimentos não fizeram uso de nenhuma técnica de

amostragem de dados, ou seja, toda a base de dados foi usada para treinamento das

técnicas apresentadas aqui e os resultados testados com os próprios dados de

treinamento.

Conforme exposto na Seção 1.3 este trabalho realiza experimentos em uma

abordagem híbrida denominada de Pipeline, a qual consiste em agrupar dados com

as técnicas de AM não supervisionado e usar o resultado fornecido (agrupamentos)

como entrada para técnicas supervisionadas que geram regras. Com isso são

construídos classificadores para a base de dados de microarray considerando cada

grupo como sendo uma classe. A Figura 4.1 representa, simplificadamente, as

etapas de processamento do Pipeline.

Figura 4.1 – Representação do Pipeline.

Figura adaptada de (Abidi, Hoe e Goh, 2001).

Os experimentos foram, então, realizados utilizando técnicas de

agrupamento em conjunto com técnicas de geração de regras. Para agrupamento

foram utilizados Agrupamento Hierárquico (com ligação média) e k-means, pois

eles representam diferentes paradigmas de AM e são amplamente utilizados no

contexto de dados de expressão gênica (Monti et al., 2003; Quackenbush, 2001;

Eisen, 1998; Golub et al., 1999). Para geração de regras foram utilizados Rough

Sets (Pila, 2001), AD (Árvores de Decisão) (Quinlan, 1993) e TSP (Top Scoring

Pairs) (Geman, 2004).

Rough Sets foi escolhido pela sua capacidade de reduzir a quantidade de

atributos do conjunto de dados possibilitando, então, a produção de regras mais

simples e, também, por ter sido utilizado em (Abidi, Hoe e Goh, 2001) com um

propósito semelhante ao deste trabalho. A opção por Árvores de Decisão se deve ao

fato desse algoritmo produzir representações simbólicas de fácil entendimento por

humanos. A técnica TSP também foi escolhida por apresentar características

importantes do ponto de vista da facilidade de interpretação dos resultados por

humanos, pois ela gera poucas regras com poucos elementos em seus termos

antecedentes (Germam 2004). O TSP foi desenvolvido para classificação de dados

de expressão gênica. Assim o nosso interesse por essa técnica também provem

desse fato, pois neste trabalho analisamos dados de expressão gênica.

Cada um dos algoritmos de agrupamento foi combinado com cada uma das

técnicas de geração de regras produzindo as seis combinações a seguir:

Agrupamento Hierárquico com Rough Sets;

Agrupamento Hierárquico com Arvores de Decisão;

Agrupamento Hierárquico com TSP.

k-means com Rough Sets;

k-means com Arvores de Decisão; e

k-means com TSP;

As seis combinações acima foram aplicadas a cada uma das bases de dados

(Gaussian3, Simulated6 e St. Jude Leukemia). Dessa maneira foram então

realizados 18 experimentos.

No agrupamento com k-means foram realizadas dez replicações (repetições)

com inicializações de centros de grupos diferentes e aleatórias. Assim foram

obtidos dez resultados de agrupamentos para casa base de dados. Cada

agrupamento gerado foi comparado com sua respectiva base de dados de

treinamento e avaliado com o índice externo Rand Corrigido. Das 10 replicações

foi escolhido o melhor agrupamento, conforme índice Rand Corrigido, ou seja, foi

escolhido o agrupamento que apresentou maior índice Rand Corrigido, para fazer

parte da etapa de geração de regras.

A Figura 4.2 ilustra estratégia usada para selecionar os grupos para a fase de

geração de regras. O algoritmo de Agrupamento Hierárquico, por ser

determinístico, não foi submetido às dez replicações. É importante lembrar que o

atributo classe das bases de dados de treinamento foi removido na etapa de pré-

processamento. Mas, para usar o Rand Corrigido, faz-se necessário a presença das

classes. A adição das classes a base de dados para comparação e cálculo do Rand

Corrigido não é representada na Figura 4.2.

Figura 4.2 – Ilustração da seleção de agrupamento para a fase de geração de regras.

4.3. Avaliação dos Resultados Obtidos

A avaliação dos resultados foi dividida em Avaliação de Agrupamento,

Avaliação de Regras e Avaliação Fim a Fim, as quais são apresentadas,

respectivamente, nas seguintes Seções 4.3.1, 4.3.2 e 4.3.3.

4.3.1. Avaliação de Agrupamentos

Essa avaliação foi realizada conforme a Figura 4.2, ou seja, da mesma

maneira que foi feita a seleção do melhor agrupamento nas replicações com k-

means. Assim para os experimentos realizados com k-means o valor da Avaliação

de Agrupamento corresponde ao valor do índice Rand Corrigido do melhor

agrupamento encontrado na seleção de agrupamento como descrita anteriormente.

4.3.2. Avaliação de Regras

A avaliação de regras se dividiu nos seguintes procedimentos:

Rand Corrigido das Regras: nesta avaliação os agrupamentos obtidos das

técnicas de agrupamento (Base de Dados Agrupada) e usados como entrada para as

técnicas de geração de regras foram classificados pelas regras geradas. Isso deu

origem a um novo conjunto de dados (Base de Dados Agrupada Classificada). Esse

novo conjunto de dados foi, então, comparado com a base de dados de entrada para

a técnica de geração de regras e o índice Rand Corrigido foi calculado. Esse índice

mede, então, a precisão das regras geradas. A Figura 4.3 ilustra o processo.

Figura 4.3 – Ilustração de avaliação de regras.

Precisão (“Acurácia”): nesta avaliação as regras geradas foram testadas com a

própria base de dados usada para treinamento (Base de Dados Agrupada) a fim de

encontrar a porcentagem de acertos (precisão) das regras.

Quantidade de Regras: nessa avaliação foi contada a quantidade de regras

geradas em cada experimento.

Quantidade de Elementos Antecedentes: dada uma regra do tipo SE

(elemento1 = valor1) E (elemento2 = valor2) ENTÃO (elemento3 = valor3),

consideraremos como elementos antecedentes as variáveis elemento1 e elemento2,

assim diz-se que esta regra possui dois elementos em seu termo antecedente.

Foram, então, contadas as quantidades de elementos existentes no termo

antecedente de cada regra gerada em cada experimento. Os resultados são

apresentados como a média de quantidade para cada conjunto de regra em cada

experimento.

Cobertura: nesse procedimento foi observado a porcentagem média da

quantidade de objetos da base de dados utilizada para geração das regras (Base de

Dados Agrupada) que teve os valores de seus atributos coincidindo com os valores

dos termos antecedentes das regras geradas. Por exemplo, consideremos o conjunto

de regras abaixo geradas a partir da base de dados exemplificada na Tabela 4.2. Se

removermos a coluna “Classe” da tabela e usarmos as duas regras geradas para

classificar esses dados verificaremos que os objetos 2 e 3 não poderão ser

classificados, pois seus valores de atributos não coincidem completamente com os

valores dos termos antecedentes de nenhuma das duas regras. Assim de quatro

exemplos apenas dois foram cobertos. Nesse caso dizemos que houve uma

cobertura de 50 %

SE (Atributo1 = 2) E (Atributo2 = 3) ENTÃO (Classe = 1)

SE (Atributo1 > 2) ENTÃO (Classe = 2)

Objetos

tributo1

tributo2 Classe

1231

22501

31252

4372

Tabela 4.2 – Exemplo de Base de Dados Agrupada.

4.3.3. Avaliação Fim a Fim

Nesta avaliação a base de dados de entrada para todo o Pipeline foi

classificada pelas regras geradas. Isso deu origem a um novo conjunto de dados

(Base de Dados Classificada). Essa nova base de dados foi então comparada com a

base de dados de entrada para o Pipeline, e o índice Rand Corrigido foi calculado.

Esse índice mede, portanto, a precisão fim a fim de todo o processo do Pipeline. Ele

irá, dessa maneira, acumular os valores de erros obtidos nos processos de

agrupamento e geração de regras. Ver Figura 4.4.

Figura 4.4 – Avaliação fim a fim.

4.4. Resultados

4.4.1. Avaliação de Agrupamentos

A Tabela 4.3 apresenta a avaliação conforme descrito na Seção 4.3.1. Os

valores de Rand Corrigido (RC) para a técnica k-means são os valores dos melhores

agrupamentos selecionados das dez replicações que foram realizadas para esta

técnica. Observa-se que com a base de dados Gaussian3 obteve-se uma

concordância perfeita dos grupos gerados com as classes originais da base de

dados, ou seja, atingiu-se o índice RC igual a um. Para as outras duas bases de

dados a perfeição não é atingida, no entanto os valores ainda são muito bons,

próximos de um. O desempenho ótimo encontrado nos agrupamentos com

Gaussian3 é facilmente explicado pela simplicidade desta base de dados em relação

a maior complexidade da Simulated6 e St. Jude Leukemia. De maneira geral

também é observado que a técnica de agrupamento k-means apresentou os melhores

índices RC.

Esta análise é importante, pois as regras obtidas na fase de geração de regras

são derivadas dos agrupamentos obtidos na fase de agrupamento, assim erros na

primeira fase contribuirão para formação de regras “defeituosas”, ou seja, que

refletirão os grupos errôneos e não a verdadeira complexidade existente dentro da

base de dados. Esta verificação, do erro que se propaga da fase de agrupamento

para a fase de geração de regras e se acumula com os erros obtidos nesta última fase

é observado na Avaliação Fim a Fim.

Hierárquico 1,0000

k-means 1,0000

Hierárquico 0,7346

k-means 0,9620

Hierárquico 0,4945

k-means 0,8223

Gaussian3

Simulated6

St. Jude Leukemia

RCBase de Dados

Algoritmo de

Agrupamento

Tabela 4.3 – Avaliação de Agrupamentos.

4.4.2. Avaliação de Regras

2.1.

Rand Corrigido das Regras, Precisão e Cobertura: a Tabela 4.4 apresenta a

avaliação das regras geradas conforme itens 1, 2 e 5 Seção 4.3.2. A coluna RC é o

Rand Corrigido calculado como exposto na Figura 4.3.

Rough Sets 1,0000 100,00 100,00

AD 0,7588 96,67 100,00

TSP 0,6364 86,67 100,00

Rough Sets 1,0000 100,00 100,00

AD 0,7588 96,67 100,00

TSP 0,6364 86,67 100,00

Rough Sets 0,9475 97,62 96,67

AD 0,8835 96,67 100,00

TSP 0,5498 81,67 100,00

Rough Sets 0,3588 56,36 49,90

AD 1,0000 100,00 100,00

TSP 0,6236 80,00 100,00

Rough Sets 0,9986 99,26 100,00

AD 0,9681 98,79 100,00

TSP 0,6136 71,60 100,00

Rough Sets 0,9857 99,25 100,00

AD 0,9656 98,79 100,00

TSP 0,6407 76,21 100,00

Cobertura

(%)

St. Jude

Leukemia

Hierárquico

k-means

Gaussian3

Hierárquico

k-means

Simulated6

Hierárquico

k-means

Precisão

(%)

Base de

Dados

Algoritmo de

Agrupamento

Técnica de

Geração de

Regras

Tabela 4.4 – Avaliação de Regras – Rand Corrigido, Precisão e Cobertura.

O Gráfico 4.1 mostra as médias e os desvios padrões dos valores de Rand

Corrigido da Tabela 4.4 para cada técnica de geração de regra, por exemplo, para a

técnica Rough Sets o valor de média 0,88 mostrado no gráfico é a média dos valores

circulados na tabela Tabela 4.4. Observando o gráfico é verificado que os

experimentos realizados com Rough Sets e AD apresentam melhores valores de

índice Rand Corrigido, os quais são bastante próximos de um. No entanto, fazendo

uma análise mais apurada e observando os valores na Tabela 4.4 é claramente

visível que Rough Sets tem os melhores índices RC, exceto pelo valor encontrado

com o experimento realizado com a base de dados Simulated6 e algoritmo de

agrupamento k-means, o qual foi de aproximadamente 0,36. Este valor contribuiu

para reduzir a média dos valores dos experimentos realizados com Rough Sets

exposto no Gráfico 4.1, mas ele é um caso isolado, portanto, podemos dizer que os

experimentos com Rough Sets produzem os melhores resultados de RC. A técnica

TSP também apresentou um bom valor de RC, não tanto quanto os obtidos com

Rough Sets e AD, mas um valor de índice satisfatório. É importante lembrar que a

técnica TSP tem características bastante proveitosas do ponto de vista da

interpretação de grupos em análises exploratórias, pois ela produz poucas regras

extremamente simples, as quais apresentam apenas a comparação entre dois

atributos em seus termos antecedentes.

A análise baseada na precisão “acurácia” das regras segue um raciocínio

idêntico ao realizado com o índice RC, pois técnicas que produziram regras que

apresentaram índices RC próximos de um apresentaram, também, precisões

próximas de 100%, ou seja, os valores da precisão e RC são correlacionais

positivamente.

Quanto à cobertura, a Tabela 4.4 mostra que quase todas as regras

conseguiram cobrir todos ou quase todos os exemplos do conjunto de treinamento,

quando usadas para classificá-los. Uma exceção é para a técnica Rough Sets com a

base de dados Simulated6 e agrupamento com k-means, a qual conseguiu cobrir

aproximadamente apenas 50 % do conjunto de treinamento. Essa baixa cobertura

explica o baixo índice RC encontrado.

Média

Desvio

Pad r ão

0,89

0,88

0,26

0,00

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

Média de Rand Corrigido

Comparação entre Técnicas de Geração de

Regras

Rough Sets

TSP

Gráfico 4.1 – Média e desvio padrão dos valores de RC para cada técnica de geração de

regras.

3.1.

Quantidade de Regras e Elementos Antecedentes: a Tabela 4.5 mostra a

quantidades de regras e quantidade média de elementos antecedentes nas regras

obtidos nos experimentos.

Rough Sets 51,00 4,00

AD 6,00 3,00

TSP 2,00 2,00

Rough Sets 51,00 4,00

AD 6,00 3,00

TSP 2,00 2,00

Rough Sets 50,00 2,00

AD 5,00 2,80

TSP 5,00 2,00

Rough Sets 60,00 2,00

AD 6,00 3,33

TSP 5,00 2,00

Rough Sets 210,00 3,00

AD 3,00 1,67

TSP 5,00 2,00

Rough Sets 209,00 2,00

AD 10,00 4,50

TSP 5,00 2,00

Quant.

Elementos

Antecedente

das Regras

Média

Base de

Dados

Algoritmo de

Agrupamento

Técnica de

Geração de

Regras

Quant. de

Regras

St. Jude

Leukemia

Hierárquico

k-means

Gaussian3

Hierárquico

k-means

Simulated6

Hierárquico

k-means

Tabela 4.5 – Avaliação de Regras – Quantidade de Regras e Elementos Antecedentes.

Analisando a Tabela 4.5 verifica-se que TSP e AD foram as técnicas que

obtiveram as menores quantidades de regras. TSP apresentou uma média de quatro

regras, a qual variou de dois a cinco; AD uma média de seis regras, variando de três

a dez. Rough sets gerou uma maior quantidade de regras, mas isso se deve ou fato

de esta teoria ter sido usada apenas para reduzir a quantidade de atributos e assim

gerar regras com uma pequena quantidade de elementos em seus termos

antecedentes (ver Seção 3.1.1). A quantidade de regras geradas com Rough Sets é

diretamente relacionada à quantidade de objetos nas bases de dados. Como a base

de dados St. Jude Leukemia tem a maior quantidade de objetos as regras geradas

com Rough Sets a partir desta base de dados também são em maiores quantidades.

Quanto à quantidade de elementos antecedentes, observa-se claramente que

todas as técnicas geraram regras com poucos elementos em seus termos

antecedentes, sendo TSP a que apresentou menor quantidade, apenas dois. Mas isso

já era esperado uma vez que é característica natural desta técnica a geração de

regras com apenas dois elementos em seus termos antecedentes.

4.4.3. Avaliação Fim a Fim

A Tabela 4.6 apresenta a avaliação das regras geradas conforme Seção

4.3.3. A coluna RC é o Rand Corrigido calculado como exposto na Figura 4.4.

Nesta avaliação é possível analisar o quanto a soma dos erros obtidos na fase de

agrupamento com os obtidos na fase de geração de regras contribui para a precisão

de todo o processo do Pipeline. Assim os valores de RC desta avaliação dão uma

idéia da qualidade de todo o processo em produzir regras que refletem as estruturas

originais das bases de dados.

Rough Sets 1,0000

AD 0,7588

TSP 0,6364

Rough Sets 1,0000

AD 0,7588

TSP 0,6364

Rough Sets 0,7178

AD 0,6581

TSP 0,5287

Rough Sets 0,3588

AD 0,9620

TSP 0,5838

Rough Sets 0,3879

AD 0,4104

TSP 0,5569

Rough Sets 0,8867

AD 0,8128

TSP 0,5922

St. Jude

Leukemia

Hierárquico

k-means

Base de

Dados

Algoritmo de

Agrupamento

Gaussian3

Hierárquico

k-means

Simulated6

Hierárquico

k-means

Técnica de

Geração de

Regras

Tabela 4.6 – Avaliação Fim a Fim.

O Gráfico 4.2 apresenta a comparação entre todos os valores de Rand

Corrigido obtidos na fase de geração de regras (Avaliação de Regras, valores da

coluna RC da Tabela 4.4) e os valores de Rand Corrigido obtidos na Avaliação Fim

a Fim (Tabela 4.6). Observa-se que para os experimentos realizados com a base de

dados Gaussian3 a linha do gráfico que representa os valores de RC da Avaliação

de Regras (linha azul) e a linha que representa os valores de RC da Avaliação Fim a

Fim (linha rosa) seguem juntas, ou seja, os valores de RC na Avaliação de Regras

coincidem com os valores de RC na Avaliação Fim a Fim. Isso se deve ao fato de

os agrupamentos realizados com a Gaussian3 terem apresentado RC igual a um

(Gráfico 4.3), ou seja, não houve erro na fase de agrupamento para esta base de

dados, portanto, os erros acumulados pelo Pipeline foram apenas os da fase de

geração de regras.

Ainda observando o Gráfico 4.2 na região dos experimentos realizados com

agrupamento hierárquico, base de dados Simulated6 e as técnicas Rough Sets e AD

verifica-se que os valores de RC da Avaliação Fim a Fim são consideravelmente

menores que os da Avaliação de Regra, mas isso é explicado pelo baixo valor de

RC obtido para os agrupamentos com Simulated6 e algoritmo hierárquico,

conforme pode ser visualizado no Gráfico 4.3. Mas quando se observa o valor de

RC da Avaliação Fim a Fim para o experimento realizado com Simulated6,

agrupamento hierárquico e TSP ela não fica tão abaixo do RC da Avaliação de

Regras, talvez a técnica TSP tenha gerado regras bastante generalistas que não se

super-ajustaram aos grupos formados pelo algoritmo hierárquico. Isso garantiu,

portanto, uma certa estabilidade no valor do RC. Fato semelhante ocorre com os

experimentos realizados com St. Jude Leukemia, agrupamento hierárquico e,

novamente, TSP.

0,3000

0,4000

0,5000

0,6000

0,7000

0,8000

0,9000

1,0000

ian3

rá

h S

3 -

rá

3 -

rá

3 -

-me

s -

3 -

-me

s -

ussi

K-

s -

ulate

6 -

ierá

Set

ulate

6 -

ierá

ula

6 -

ierá

ula

6 -

-me

Sim

ted6 -

K-means

- A

ulated6 -

-me

TSP

t. Jud

rárq

ico

Rough

ets

emia -

ierá

. Ju

emia -

ierárqu

co -

. Ju

emia -

-means

St. Ju

emia - K-means

Jud

K-means

Rand Corrigido

Rand Corrigido da

Avaliação de Regras

Rand Corrigido da

Avaliação Fim a Fim

Gráfico 4.2 – Comparação entre valores de Rand Corrigido obtidos na Avaliação de Regra e

Avaliação Fim a Fim.

0,0000

0,2000

0,4000

0,6000

0,8000

1,0000

1,2000

Gausian3 - H

erá

quico

ans

Simul

ted6 - Hierár

uico

ula

ed6 - K-

eans

St. Ju

Leuk

mia

Hierár

Jud

K-

Rand Corrigido

Gráfico 4.3 – Rand Corrigido obtido na Avaliação de Agrupamentos.

Capítulo 5

5. Análise das Regras Geradas

Análise dos Resultados

Neste capítulo são realizadas análises das regras geradas a partir dos

agrupamentos realizados com o algoritmo k-means, pois como observado nas

avaliações dos resultados na Seção 4.4 os experimentos realizados com esse

algoritmo obtiveram melhores resultados de índice RC que os realizados com

algoritmo hierárquico.

As Seções 5.1 e 5.2 fazem, respectivamente, uma análise da

correspondência dos atributos das bases de dados Gaussian3 e Simulated6, que

estão relacionados a cada classe, com os atributos encontrados nas regras e a classe

definida por elas. Em seguida a Seção 5.3 analisa as regras geradas no contexto da

base de dados St. Jude Leukemia.

5.1. Análise com Gaussian3

As duas bases de dados sintéticas possuem atributos relacionados a cada

uma de suas classes. Assim na Gaussian3 há um conjunto de 200 atributos que

determinam cada classe, essa relação de atributo com classe é exclusiva, ou seja, os

200 atributos que determinam a classe um, por exemplo, não determinam a classe

dois nem a classe três (Monti et al., 2003).

Abaixo são apresentadas as correspondências grupo-classe, as quais foram

obtidas após o agrupamento da Gaussian3 com o algoritmo k-means. É observado

que o agrupamento foi perfeito apresentando grupos totalmente homogêneos, ou

seja, cada grupo só possui elementos pertencentes a uma única classe.

•

Grupo1 = {Classe2 (20)}: vinte objetos pertencentes a Classe2 da base de

dados Gaussian3 foram os únicos objetos a fazer parte deste grupo. Assim

caracterizamos o Grupo1 como sendo o grupo da Classe2.

•

Grupo2 = {Classe1 (20)}: da mesma maneira que o anterior, neste grupo

todos os seus 20 objetos pertencem a Classe1. Por isso dizemos que ele é o grupo

da Classe1.

•

Grupo3 = {Classe0 (20)}: neste grupo seus 20 objetos são pertencentes a

Classe0. Então o Grupo3 é o grupo da Classe0.

5.1.1. Árvore de Decisão

A Figura 5.1 apresenta a árvore de decisão gerada a partir da base de dados

Gaussian3 agrupada com o algoritmo k-means. A primeira vantagem que se pode

observar é que dos 600 atributos da Gaussian3 apenas cinco (nós da árvore) foram

considerados necessários para diferenciação entre os três grupos. Observemos,

então, a correspondência dos atributos existentes nos nós desta árvore com o grupo

(classe) que eles definem. Na base de dados Gaussian3 os atributos 95 e 2 definem

a classe 0; os atributos 242 e 291 definem a classe 2; e, por último, o atributo 133

define a classe 1.

Observando a árvore verifica-se que o atributo 95 é o nó raiz que diferencia

a classe 0 das demais. O nó 2 faz a distinção das classes 1 e 2 das classes 0 e 1, mas

no nó 133 a classe 0 é distinguida da classe 1. No nó 242 é feita a discriminação

entre a classe 2 e as classes 1 e, novamente, 2. Por fim, no nó 291 é finalmente feita

a diferenciação entre as classes 1 e 2.

A partir da análise feita acima é possível dizer que os atributos que estão

relacionados com determinada classe na base de dados estão assumindo posições

estratégicas dentro da estrutura da árvore gerada e servem para decisão entre as

classes que eles determinam. Ou seja, a árvore gerada é uma estrutura de decisão

representativa dos dados.

Figura 5.1 – Árvore de Decisão obtida da base de dados Gaussian3 agrupada com k-means.

5.1.2. TSP

O uso do algoritmo TSP gerou as duas regras ilustradas na Figura 5.2. De

acordo com essas regras, pode ser observado que dos 600 atributos originais,

apenas quatro foram considerados relevantes como discriminantes entre os

diferentes grupos. Mas isso já era esperado, uma vez que a técnica TSP gera regras

com apenas dois elementos em seu termo antecedente. Assim, como no caso da

árvore de decisão, pode ser dito que o TSP além de proporcionar regras mais

simples funcionou como um filtro de atributos. Originalmente, na base de dados

Gaussian3, os atributos 2 e 18 definem a classe 0, já os atributos 178 e 268

definem, respectivamente, as classes 1 e 2.

Analisando as regras é possível verificar que os atributos, nos antecedentes

das regras, que originalmente têm relação com determinada classe na base de dados

servem, nas regras, para a distinção entre estas mesmas classes. Por exemplo, na

Regra 1 o atributo 2 e o atributo 268 distinguem a classe 2 das classes 0 e 1. Já na

Regra 2 os atributos 18 e 178 diferenciam entre as classes 0 e 1.

Figura 5.2 – Regras geradas com TSP a partir da base de dados Gausian3 agrupada com k-

means.

5.1.3. Rough Sets

Conforme foi mostrado na Seção 3.1.1 Rough Sets foi utilizado apenas para

reduzir a quantidade de atributos da base de dados para geração de regras, ou seja,

desta teoria foi explorado apenas o conceito de reduto, o qual é um conjunto

mínimo de atributos que permite diferenciação entre os vários objetos da base de

dados. O reduto encontrado possui os atributos 1, 111, 119 e 239. Originalmente, na

base de dados Gaussian3, o atributo 1 está relacionado a classe 0; os atributos 111 e

Regra 1:

IF (atributo 2 < atributo 268) THEN (classe 2)

ELSE (classe 1 OR classe 0)

Regra 2:

IF (atributo 18 < atributo 178) THEN (classe 1)

ELSE (classe 0)

119 estão relacionados a classe 1; e, o 239 está relacionado a classe 2. Como era

esperado, uma vez definido o reduto, todas as regras geradas tiveram apenas os

atributos do reduto como termos antecedentes. Elas se diferenciam umas das outras

apenas pelos valores de cada atributo. Assim não é possível fazer uma análise sobre

a correspondência dos atributos com suas classes, apenas podemos verificar que o

reduto apresentou atributos que definem as três classes. Na Figura 5.3 são

apresentadas duas das 51 regras geradas.

Figura 5.3 – Regras geradas com Rough Sets a partir da base de dados Gausian3 agrupada

com k-means.

5.2. Análise com Simulated6

A correspondência de atributos com classes, semelhante à existente na

Gaussian3 é também encontrada na Simulated6. Esta base de dados apresenta

conjuntos de 50 atributos exclusivamente relacionados a cada classe. Da mesma

maneira que na Gaussian3 a exclusividade significa que os 50 atributos que se

relacionam a uma das seis classes da Simulated6 não determinam nenhuma outra

classe desta base de dados.

5.2.1. Árvore de Decisão

Da mesma maneira que foi feito com a base de dados Gaussian3 façamos a

análise da correspondência dos atributos (nós da árvore) com suas classes. A Figura

5.4 apresenta a AD obtida a partir da base de dados Simulated6 agrupados com k-

means. Originalmente, na base de dados Simulated6, o atributo 188 define a classe

Regra1:

IF (atributo 1 = [*, 0.4795))

AND (atributo 111 = [0.6048, 0.6118))

AND (atributo 119 = [0.6763, 0.7363))

AND (atributo 239 = [0.6302, 0.6378))

THEN (classe 0)

Regra2:

IF (atributo 1 = [*, 0.4795))

AND (atributo 111 = [0.7350, 0.7424))

AND (atributo 119 = [*, 0.4763))

AND (atributo 239 = [*, 0.4798))

THEN (classe 1)

3; o 69 definem a classe 1; o 103 define a classe 2; o 6 a classe 0; e, finalmente, o

atributo 207 define a classe 4.

Visualizando-se a árvore verifica-se que cada atributo ocupa um nó de

decisão pela classe que ele originalmente determina na base de dados, por exemplo,

o nó 188 (raiz da árvore) é determinante, na base de dados, da classe 3. Na árvore

ele ocupa a posição de decisão que distingue a classe 3 das demais. Esse raciocínio

segue por toda a árvore mais uma vez mostrando que a estrutura gerada é bastante

representativa dos dados originais.

Figura 5.4 – Árvore de Decisão obtida da base de dados Simulated6 agrupada com k-means.

5.2.2. TSP

Dos 600 atributos da Simulated6 o algoritmo TSP realizou uma filtragem

gerando as cinco regras apresentadas na Figura 5.5 com o uso de apenas nove

atributos. Na base de dados Simulated6 o atributo 2 define a classe 0; os atributos

51, 52, 61 e 90 definem a classe 1; o atributo 135 define a classe 2; o 186 a classe 3;

o 242 a classe 4; e o 252 a classe 5.

Da mesma maneira que foi feito para a base de dados Gaussian3 analisando

as regras é possível verificar que os atributos, nos antecedentes delas, que

originalmente têm relação com determinada classe na base de dados servem, nas

regras, para a distinção entre estas mesmas classes. Por exemplo, na Regra 1 o

atributo 52 e o atributo 242 distinguem a classe 4 das demais. O raciocínio segue

até a última regras, Regra 5, na qual os atributos 51 e 252 distinguem entre as

classes 5 e 1.

Figura 5.5 – Regras geradas com TSP a partir da base de dados Simulated6 agrupada com k-

means.

Regra1:

IF (atributo 52 < atributo 242) THEN (classe = 4)

ELSE (classe=2ORclasse=3ORclasse=0ORclasse=1OR

classe = 5)

Regra2:

IF (atributo 52 < atributo 135) THEN (classe = 2)

ELSE (classe=3ORclasse=0ORclasse=1ORclasse = 5)

Regra3:

IF (atributo 61 < atributo 186) THEN (classe = 3)

ELSE (classe=0ORclasse=1ORclasse = 5)

Regra4:

IF (atributo 2 < atributo 90) THEN (classe=1ORclasse = 5)

ELSE (classe = 0)

Regra5:

IF (atributo 51 < atributo 252) THEN (classe = 5)

ELSE (classe = 1)

5.2.3. Rough Sets

O reduto encontrado quando aplicado Rough Sets aos agrupamentos obtidos

com k-means a partir da base e dados Simulated6 possui apenas dois atributos

(atributos 1 e 492). Originalmente o atributo 1 está relacionado a classe 0; já o

atributo 492 não define classe alguma, pois ele faz parte do conjunto de atributos

com ruídos existente nesta base de dados. Assim, mais uma vez não é possível fazer

uma análise sobre a correspondência dos atributos com suas classes, apenas pode

ser dito que o reduto gerado não apresentou atributos relevantes que pudessem

definir as seis classes da base de dados Simulated6. Na Figura 5.6 são apresentadas

apenas duas das 60 regras geradas.

Figura 5.6 – Regras geradas com Rough Sets a partir da base de dados Simulated6 agrupada

com k-means.

5.3. Análise com St. Jude Leukemia

A Leucemia Linfóide Aguda (ALL – do inglês Acute Lynphoblastic

Leukemia) infantil é uma enfermidade, na qual os glóbulos brancos (linfócitos

responsáveis por combater as infecções, encontram-se imaturos, em grande

quantidade no sangue e na medula óssea do paciente. A ALL é a forma mais

comum de câncer infantil (Pui e Evans, 1998). Nas últimas décadas grandes

avanços têm sido conseguidos no tratamento da ALL infantil (Silverman et al.,

2001; Pui e Evans, 1998; Yeon et al., 2002). Em parte, esses avanços se devem ao

uso de uma terapia adaptada ao risco de recaída de cada paciente.

Células do sistema imune, uma dos dois tipos gerais: linfócitos B, da medula óssea, e o linfócito T,

derivados do Timo (Passarge, 2003).

Regra1:

IF (atributo 1 = [0.7318, *))

AND (atributo 492 = 0.5302)

THEN (classe 0)

Regra2:

IF (atributo 1 = [0.4420, 0.4425))

AND (atributo 492 = 0.2293)

THEN (classe 2)

A abordagem das terapias adaptadas foi desenvolvida baseada no fato de

que a ALL infantil é uma enfermidade que consiste de vários subtipos, que diferem

bastante em suas respostas à quimioterapia (prognóstico) (Pui e Evans, 1998; Yeon

et al., 2002). Os subtipos incluem as leucemias das linhagens B e T (Silverman et

al., 2001; Pui e Evans, 1998; Yeon et al., 2002). A linhagem B ainda pode ser

classificada naquelas em que há algum tipo de 1) translocação

: a) t(9;22) em

relação aos genes BCR e ABL; b) t(1;19) em relação aos genes E2A e PBX1; e c)

t(12;21) com respeito aos genes TEL e AML1; 2) rearranjos no gene MLL do

cromossomo 11; e 3) um cariótipo hiperdiplóide, ou seja, mais de 50 cromossomos

(o cariótipo normal apresenta 46 cromossomos).

No contexto acima, a análise do perfil da expressão gênica vem se

mostrando uma abordagem promissora na identificação desses subtipos de ALL

infantil. Por exemplo, Yeoh et al. (2002) criou um conjunto de dados representando

a expressão gênica de pacientes com ALL infantil (base de dados St. Jude

Leukemia). Quando esses dados foram submetidos a algoritmos de agrupamento,

conseguiu-se gerar grupos que estavam diretamente relacionados com os seis

subtipos de ALL descritos anteriormente.

Nesta dissertação, conforme já foi explicado, agrupamos os dados para

depois extrair regras. Assim após o agrupamento da St. Jude Leukemia com o

algoritmo k-means foram obtidas as seguintes correspondências grupo-classe:

•

Grupo1 = {Hyp>50 (2), MLL (15), T-ALL (13)}: Como a classe majoritária é

MLL com 15 objetos (originalmente essa classe possui 20 objetos), associamos o

Grupo1 a ela. Este grupo também poderia ser visto como uma mistura de MLL

como T-ALL (13 objetos).

•

Grupo2 = {BCR-ABL (14), Hyp>50 (8)}: Atribuímos este grupo a classe BCR-

ABL. De um total de 15 objetos dessa classe, 14 foram associadas a este grupo.

•

Grupo3 = {T-ALL (30)}. Este grupo é totalmente homogêneo no sentido de que

possui objetos apenas da Classe T-ALL.

•

Grupo4 = {Hyp>50 (1), TEL-AML1 (79)}: Com exceção de um objeto da Classe

Hyp>50, todos os outros pertencem a Classe TEL-AML1.

Transferência de todo ou parte de um cromossomo para outro cromossomo (Passarge, 2003). Em geral se

usa a notação t(i;j) para indicar uma translocação entre os cromossomos i e j.

•

Grupo5 = {BCR-ABL (1), Hyp>50 (52)}: Com exceção de um objeto da Classe

BCR-ABL, todos os outros pertencem a Classe Hyp>50.

•

Grupo6 = {E2A-PBX1 (27), Hyp>50 (1), MLL (5)}. Como a classe majoritária é

claramente E2A-PBX1, associamos o Grupo6 a ela. De fato, todos os 27 objetos

dessa classe foram atribuídos a este grupo.

De acordo com a atribuição acima, cada grupo ficou associado a uma dada

classe. O próximo passo é uma interpretação biológica das regras geradas a partir

dos grupos acima. Um fator complicador para tal análise foi a falta de um

especialista (biólogo) para nos ajudar nessa tarefa. Diante disto, optamos pelo uso

da ferramenta FatiGO (Al-Shahrour, 2004; Al-Shahrour, 2005; Al-Shahrour, 2006;

Fatigo, 2006) que nos permitiu fazer uma anotação automática dos genes que fazem

parte dos antecedentes das regras.

Usamos também o trabalho de Yeoh et al. (2002), como guia, no qual foram

usados cinco diferentes testes estatísticos (por exemplo, t-teste e chi-quadrado) para

ordenar e selecionar os genes mais importantes para melhor discriminar os

diferentes subtipos de ALL infantil. O conjunto de genes selecionados foi usado

como entrada para o treinamento de classificadores como SVM e redes neurais. Ou

seja, no trabalho de Yeoh et al. (2002) a seleção de atributos foi feita no contexto

supervisionado. Em contraste, nesta dissertação a seleção dos genes mais

importantes que representam uma dada classe (grupo) é uma conseqüência direta

dos métodos usados para geração das regras a partir dos dados agrupados.

5.3.1. Árvore de Decisão

O uso do algoritmo de indução de árvores de decisão tendo como entrada a

base de dados St. Jude Leukemia agrupada com k-means, gerou a árvore ilustrada

na Figura 5.7. De acordo com essa figura, podemos observar que dos 985 atributos

(genes) originais, apenas nove atributos foram considerados relevantes como

discriminantes entre os diferentes grupos. Mais uma vez pode-se dizer que houve

uma filtragem de atributos. Esse tipo de filtro é muito importante no sentido de que

pode levar o especialista a focar sua análise em um subconjunto de genes que

realmente sejam importantes para se caracterizar os diferentes subtipos de ALL

infantil.

Observando-se, por exemplo, apenas o valor da expressão do gene U52682

(raiz da árvore), é possível discriminar a classe E2A-PBX1. Esse mesmo gene

aparece, no trabalho de Yeoh et al. (2002), como um dos principais discriminante

para essa classe. Da mesma forma, tanto no nosso trabalho quanto em Yeoh et al.

(2002), o valor da expressão do gene X00437

é fundamental para discriminação

da classe T-ALL das demais (MLL, TEL-AML1, Hyp>50 e BCR-ABL). O gene

U52682 está associado ao processo de resposta do sistema imune.

Em seguida, a fim de discriminar a classe MLL das classes TEL-AML1,

Hyp>50 e BCR-ABL, a árvore usa os genes AF070614 e AB002438

. No trabalho

de Yeoh et al. (2002), o primeiro gene aparece relacionado a todas as classes (com

diferentes níveis de correlação), enquanto o segundo gene aparece relacionado,

fracamente, a classe TEL-AML1. Ou seja, no contexto da classe MLL encontramos

genes diferentes daqueles do trabalho de Yeoh et al. (2002). Uma possível razão

para isso é o fato de que o Grupo1 seja bastante heterogêneo (aproximadamente

metade dos objetos são da classe MLL e a outra da classe T-ALL).

Por outro lado, como no trabalho em Yeoh et al. (2002), o gene U07223, no

ramo da árvore referente à classe TEL-AML1, aparece como discriminante para a

classe TEL-AML1. Ainda com relação a esse ramo, o gene U02493 não foi

encontrado em Yeoh et al. (2002), já o gene U07223 aparece associado também à

classe TEL-AML1. De acordo com os termos GO (Anexo A), o gene U02493 está

associado a processos de reparo do DNA durante a replicação, como também ao

processo de regulação da transcrição. Portanto, qualquer alteração do

funcionamento desse gene é um potencial risco para o desenvolvimento anormal da

célula como o câncer, por exemplo.

Nos nossos resultados, como também naqueles em Yeoh et al. (2002), o

gene U59151 (um dos responsáveis pelo processo de organização do cromossomo)

aparece como um discriminante para a classe Hyp>50. Na árvore gerada, o gene

utilizado para caracterizar a classe BCR-ABL é o M17886. Esse gene não aparece

Os genes X00437 e AB002438 são hipotéticos (ainda foi totalmente comprovado que eles representam

genes). O gene X00437 aparece em Yanagi et al. (1984) como gene hipotético associado a proteínas de

células tronco. Já em Ueno et al. (1998) o gene AB002438 aparece como um possível gene associado ao

câncer de pulmão.

em Yeoh et al. (2002). Mas como pode se visto no Anexo A, o gene M17886 está

envolvido no processo de tradução, ou seja, na síntese de proteína a partir do

RNAm. Portanto, problemas com esse gene podem afetar seriamente todo o

funcionamento da célula.

Figura 5.7 – Árvore de Decisão gerada da base de dados St. Jude Leukemia agrupada com k-

means.

5.3.2. TSP

O uso do algoritmo TSP gerou as cinco regras ilustradas na Figura 5.8. De

acordo com essas regras, podemos observar que dos 985 atributos (genes) originais,

apenas 10 atributos foram considerados relevantes como discriminantes entre os

diferentes grupos. Da mesma maneira que na árvore de decisão, pode ser dito que o

TSP além de proporcionar regras mais simples funcionou como um filtro.

Figura 5.8 – Regras geradas com TSP a partir da base de dados St. Jude Leukemia agrupada

com k-means.

A Regra1 discrimina a classe MLL das demais, usando os valores das

expressões dos genes Y18004 e AL050159. Mais claramente, essa regra estabelece

que se a expressão do gene AL050159 é maior do que a do gene Y18004, então a

amostra deve pertencer à classe MLL. Em Yeoh et al. (2002), ambos os genes

aparecem associados à classe Hyp>50. Esses genes, de acordo como o Anexo A,

estão envolvidos no processo de transcrição. Portanto, problemas com eles podem

levar, por exemplo, a um descontrole na produção das proteínas afetando a célula

como um todo.

A segunda regra discrimina a classe BCR-ABL das classes T-ALL, TEL-

AML1, E2A-PBX1 e Hyp>50. Para isso, são usados os valores da expressão dos

Regra1:

IF (Y18004 < AL050159) THEN (MLL)

ELSE (BCR-ABL OR T-ALL OR TEL-AML1 OR Hyp>50 OR E2A-PBX1)

Regra2:

IF (D73409 < D13640) THEN (BRC-ABL)

ELSE (T-ALL OR TEL-AML1 OR Hyp>50 OR E2A-PBX1)

Regra3:

IF (AB019392 < AA919102) THEN (T-ALL)

ELSE (TEL-AML1 OR Hyp>50 OR E2A-PBX1)

Regra4:

IF (AB010419 < U90878) THEN (Hyp>50 OR E2A-PBX1)

ELSE (TEL-AML1)

Regra5:

IF (U12255 < U52682) THEN (E2A-PBX1)

ELSE (Hyp>50)

genes D73409 e D13640. É interessante notar que essa regra associa um gene

(D74309) envolvido no processo de regulação do tamanho da célula com um gene

envolvido na apoptose (D13640) – veja Anexo A. O processo de apoptose (morte

celular programada) é caracterizado por uma série de eventos celulares regulados,

resultando na morte de uma célula para eliminar uma célula danificada (por

exemplo, uma célula cancerígena) ou uma célula normal não mais necessária

(Passarge, 2003). Com respeito aos resultados obtidos em Yeoh et al. (2002), o

gene D13640 não está presente. Por outro lado, nesse mesmo trabalho, o gene

D73409 aparece associado à classe BCR-ABL, como no caso desta dissertação.

Em seguida, a Regra3, que tem como antecedente os genes AB019392 e

AA919102, é usada para separar a classe T-ALL das classes TEL-AML1, E2A-

PBX1 e Hyp>50. Como pode ser visto no Anexo A, o gene AB019392 está

envolvido no processo de início de tradução (síntese de proteínas a partir do

RNAm), mas não há termos GO associados ao gene AA919102. No trabalho Yeoh

et al. (2002) o gene AB019392 aparece associado tanto à classe Hyp>50 quanto à

classe MLL. Já o gene AA91910 aparece sempre associado à classe T-ALL.

A classe TEL-AML1 é separada das restantes (E2A-PBX1 e Hyp>50) por

meio da Regra4. Essa regra relaciona os valores de expressão dos genes AB010419

e U90878. Em Yeoh et al. (2002) o gene AB010419 aparece sempre associada à

classe TEL-AML1. No caso do gene U90878, ele aparece, na maioria das vezes,

associados à classe TEL-AML1 (três de um total de cinco).

Por fim, a Regra5 separa as classes E2A-PBX1 e Hyp>50, por meio dos

genes U12255 e U52682. Esses dois genes estão envolvidos em processos relativos

a respostas do sistema imune. O primeiro deles, U12255, não aparece nos

resultados de Yeoh et al. (2002). Já o gene U52682 aparece três vezes associado à

classe E2A-PBX1, de um total de quatro.

5.3.3. Rough Sets

O reduto encontrado possui apenas dois genes (U12255 e U02493). Nenhum

destes dois genes aparece nos resultados de Yeoh et al. (2002). Como já

mencionado anteriormente, o gene U12255 está associado com processos de reparo

do DNA e o gene U02493 com respostas do sistema imune. Embora os processos

nos quais esses genes estejam envolvidos tenham relação com os diferentes

subtipos de leucemia é bastante difícil fazer alguma discriminação mais acurada das

diferentes classes com apenas estes dois genes, já que todas as regras geradas

apresentam apenas eles dois como atributos e diferem uma das outras apenas pelos

valores de nível de expressão que estes genes assumem em cada regra. A Figura 5.9

mostra duas das 209 regras obtidas com Rough Sets para os agrupamentos

realizados com k-means a pertir da base de dados St. Jude Leukemia.

Figura 5.9 – Regras geradas com Rough Sets a partir da base de dados St. Jude Leukemia

agrupada com k-means.

5.4. Considerações Finais

As análises anteriores permitiram fazer uma verificação da

representatividade das regras geradas em relação às bases de dados. De fato,

observou-se que elas não foram geradas ao acaso, pois de alguma maneira refletem

as bases de dados das quais foram criadas.

As investigações com as bases de dados sintéticas fizeram o uso de

características bastante especiais da Gausian3 e Simulated6. Ou seja, as

características que estas bases de dados têm de possuir conjuntos de atributos que

determinam exclusivamente cada uma de suas classes. A partir destas

características foi observado que as regras geradas apresentavam atributos em seus

termos antecedentes e classes em seus termos conseqüentes, em que as classes dos

conseqüentes são determinadas, na base de dados original, pelos mesmos atributos

encontrados nos termos antecedentes.

Na St. Jude Leukemia foi realizada uma comparação com o trabalho de

Yeoh et al. (2002), onde foi verificado que as regras geradas, em geral, também

fazem uma associação coerente de termos antecedentes (genes) com conseqüentes

Regra1:

IF (U12255 = [0.7318,*))

AND (U02493 = 0.5302)

THEN (T-ALLL)

Regra2:

IF (U12255 = [0.4613,0.4654))

AND (U02493 = 0.3828)

THEN (TEL)

(subtipos da leucemia ALL). Ou seja, as regras definem subtipos de leucemia a

partir de genes, os quais foram, em grande parte, encontrados associados aos

mesmos subtipos de ALL no trabalho de Yeoh et al. (2002). Mais uma vez é

demonstrado que as regras geradas refletem as características originais das bases de

dados.

A facilidade com a qual foi possível associar termos antecedentes de regras

(atributos) com seus termos conseqüentes (classes – subtipos de ALL) nas técnicas

AD e TSP não é alcançada em Rough Sets, pois esta última gera todas as regras

com o mesmo conjunto de atributos (o Reduto) em seus termos antecedentes. No

caso da St. Jude Leukemia o reduto possui apenas dois atributos (genes), quantidade

muito pequena para se fazer uma análise comparativa como os seis subtipos de

ALL. Assim mesmo tendo apresentado boa avaliação de índice Rand Corrigido,

conforme visto na Seção 4.4.2, ela não oferece grande facilidade de interpretação.

Capítulo 6

6. Conclusão e Trabalhos Futuros

Conclusão e Trabalhos Futuros

O objetivo deste trabalho foi desenvolver ou estimular o desenvolvimento

de técnicas para análise de dados de expressão gênica que sejam mais facilmente

interpretáveis por humanos. Assim adotamos uma abordagem exploratória

denominada de Pipeline, a qual consistiu em gerar regras com as técnicas Rough

Sets, Árvores de Decisão (AD) e TSP, a partir de dados agrupados com as técnicas

de agrupamento k-means e algoritmo hierárquico (ver Seção 1.3 – Objetivos e

Abordagens). Dessa maneira, estamos tentando dar sentido aos dados de

microarray agrupados.

Uma das principais contribuições desta dissertação é o uso de bases de

dados de níveis de expressão gênica. Assim estamos aplicando as técnicas

computacionais para resolver problemas da biologia molecular, portanto estamos

trabalhando com Bioinformática. Diferentemente desta dissertação, na maioria dos

trabalhos pesquisados não foram realizados experimentos com bases de dados de

expressão gênica (ver Seções 1.4 – Trabalhos relacionados e Discussões). Sendo,

também, as bases de dados utilizadas nos outros trabalhos muito pequenas quando

comparadas com a quantidade de atributos encontrados nas bases de dados de

níveis de expressão gênica como, por exemplo, as que usamos Gaussian3 (600

atributos), Simulated6 (600 atributos) e St. Jude Leukemia (985 atributos - genes).

Duas das abordagens encontradas na literatura que mais se assemelham as

empregadas neste trabalho foram propostas, uma por Abidi, Hoe e Goh (2001) e a

outra por Karthigasoo, Cheach e Manickam (2005). A primeira consiste no

agrupamento de dados com k-means e posterior geração de regras com Rough Sets.

Diferentemente, nossas abordagens agruparam dados com k-means e agrupamento

hierárquico e geraram regras com Rough Sets, AD e TSP. Já no trabalho de

Karthigasoo, Cheach e Manickam (2005) os dados são agrupados com SOM e as

regras geradas com Rough Sets são utilizadas para treinamento de redes neurais. Ou

seja, este último gera regras a partir de agrupamentos, mas seu objetivo final não é

a produção de modelos mais facilmente interpretáveis e sim a produção de

classificadores baseados em redes neurais.

Um outro diferencial nos experimentos desta dissertação foi o uso da técnica

TSP (Geman et al., 2004), a qual foi desenvolvida para a classificação de dados de

expressão gênica. Ela possibilitou a obtenção de regras extremamente simples, ou

melhor, poucas regras com apenas dois elementos em seus termos antecedentes.

Em nossos experimentos não fizemos o uso de técnicas de amostragem de

dados, pois não desejamos verificar o quanto as regras geradas têm capacidade de

classificar dados que não estiveram presentes no conjunto de treinamento. Portanto,

a princípio, o objetivo não é gerar modelos de caráter generalistas e sim regras que

se ajustam aos dados agrupados e fornecem um modelo mais simples de ser

entendido. Nesse contexto, este trabalho é mais um dos esforços da comunidade

científica em fornecer modelos interpretativos, mas que difere dos outros trabalho

por apresentar uma abordagem de produção de regras que refletem as bases de

dados das quais foram geradas sem se preocupar com a capacidade de

generalização.

De fato, há um dilema entre a produção de modelos precisos e generalistas e

de fácil interpretação, conforme pode ser visto em Geman et al. (2004) onde é

ressaltado que técnicas que funcionam como “caixas pretas”, redes neurais, por

exemplo, são bastante precisas e generalistas, mais não permitem interpretação a

partir de análise visual. Assim enfatizamos que se queremos dar sentido aos grupos

gerados por técnicas de agrupamento não necessitamos gerar modelos generalistas.

Podemos, então, produzir algo que se ajuste aos grupos formados e forneça simples

interpretações.

Os resultados das avaliações dos experimentos, com índice de validação

Rand Corrigido e precisão das regras geradas, mostraram que os experimentos

realizados com k-means, Rough Sets e AD tiveram excelentes resultados e a técnica

TSP bons resultados. No que diz respeito a interpretação, as análises realizadas na

Seção 5 evidenciaram que as regras geradas realmente refletem os dados agrupados,

exceção esta feita aquelas geradas com a teoria Rough Sets, as quais não puderam,

apenas com estes experimentos, ser consideradas satisfatórias no contexto de

nossos objetivos de interpretação (ver comentários nas Seções 5.1.3, 5.2.3 e 5.3.3).

6.1. Trabalhos Futuros

Dando continuidade aos trabalhos iniciados nesta dissertação poderiam ser

realizados experimentos com outras bases de dados reais de níveis de expressão

gênica, obtidas tanto pela técnica de microarray como por outras técnicas. Nestes

novos experimentos poderiam ser abordadas diversas outras técnicas de

agrupamentos de dados e geração de regras como, por exemplo, Random Forest ou

Floresta Randômica, a qual consiste de classificadores baseados em muitas Árvores

de Decisões (Breiman, 2001; Breiman, 2006).

Em contrapartida a filosofia do Pipeline, mas seguindo o mesmo objetivo,

poderiam ser exploradas novas propostas de algoritmos que também trabalham de

forma exploratória e tentam produzir resultados mais facilmente interpretáveis,

como pode ser visto nas seguintes sugestões:

Em Liu et al. (2000) é proposto um algoritmo denominado de CLTree

(CLustering based on decision Trees). Esse algoritmo produz ADs a partir de

dados sem informação a priori. O seu princípio de funcionamento é derivado do

algoritmo C4.5 de Quinlan (1993). A idéia fundamental consiste em adicionar n

pontos virtuais ao espaço de dados, distribuídos uniformemente. Considera-se,

então, a existência de apenas duas classes e o problema passa a ser de

classificação. Dessa maneira as folhas das ADs geradas são consideradas

classes. O algoritmo é, portanto, uma versão modificada do C4.5 para trabalhar

de maneira exploratória. Nos experimentos realizados com CLTree em Liu et

al. (2000) não foram utilizadas bases de dados de níveis de expressão gênica,

nem biológicas de tipo algum. O número máximo de atributos não excedeu 20.

Em Basak e Krishnapuram (2005) também é apresentada uma proposta de

algoritmo para gerar AD a partir de dados sem informação a priori. O algoritmo

funciona segmentando o espaço de dados através de uma medida de

homogeneidade dos dados. Nos experimentos realizados em Basak e

Krishnapuram (2005) também não foram utilizadas bases de dados de níveis de

expressão gênica e a quantidade de atributos também foi pequena, variando de

4 a 57.

Referências Bibliográficas

Abidi, S. S. R., Hoe, K. M., Goh, A. (2001). Analyzing data cluster with Rough

Sets Approach to Extract Cluster-Defining Symbolic Rules.

Alberts, B. (2004). Biologia Molecular da Célula. Artmed.

Alizadeh, A. A., Eisen, M. B., Davis, R. E., Ma, C., Lossos, I. S., Rosenwald, A.,

Boldrick, J. C., Powell, T. et al. (2000) Distinct types of diffuse large B-cell

lyphoma identified by gene expression profiling. Nature 403:503 510.

Al-Shahrour, F., Minguez, P., Tárraga, J., Montaner, D., Alloza, E., Vaquerizas,

J.MM., Conde, L., Blaschke, C., Vera, J. e Dopazo, J. (2006), BABELOMICS:

a systems biology perspective in the functional annotation of genome-scale

experiments, Nucleic Acids Research, In Press.

Al-Shahrour, F., Minguez, P., Vaquerizas, J.M., Conde, L. e Dopazo, J. (2005),

Babelomics: a suite of web-tools for functional annotation and analysis of

group of genes in high-throughput experiments, Nucleic Acids Research,

33(Web Server issue), W460-W464.

Al-Shahrour, F., Díaz-Uriarte, R. e Dopazo, J. (2004), FatiGO: a web tool for

finding significant associations of Gene Ontology terms with groups of genes,

Bioinformatics, 20, 578-580.

Baldi, P. e Brunak, S. (2001). Bioinformatics: the Machine Learning approach.

MIT Press, segunda edição.

Basak, J. e Krishnapuram, R. (2005). Interpretable Hierarchical Clustering by

Cronstructing an Unsupervised Decision Tree. IEEE Transaction on knowledge

and data engineering, nº 1, Vol. 17.

Bazan, J. G, Skowron, A. J., Synak, P. (1994). Discovery of Decision Rules from

Experimental Data. Proc. 3 rd Int. Workshop on Rough Sets and Soft

Computing, San Jose CA pp. 526-533.

Bazan J. G. (1996). Dynamic reducts and statistical inference. Proc. 6 th Int. Conf.

on Information Procesing and Management of Uncertainty in Knowledge-Based

Systems (IPMIU'96). Vol. 3, Granada, Spain pp. 1147-1152.

Breiman, L. (2001). "Random Forests". Machine Learning 45 (1), 5-32

Breiman, L. Site de Leo Breiman, Disponível em:

<http://en.wikipedia.org/wiki/Random_forest>. Acesso em: 10 de junho de

2006.

Breiman, L., Friedman, H., Olshen, A. e Stone, J. (1984). Classification and

regression trees. In International Conference on Machine Learning, volume 10,

pages 57–78.

Brown, M.P. et al. (2000). Knowledge-based analysis of microarray gene

expression data by using support vector machines, Proc. of National Academy

of Sciences USE 97:262-267.

Brown, M. P., Bostein, D. (1999). Exploring the new world of genome with DNA

microarrays, Nature Genetics 21:33-37.

Brenner, S. et al. (2000). Gene expression analysis by Massive Parallel Signature

Sequencing (MPSS) on microbead array. Nat. Biotechnol., 18(6):630–640.

BØ, T. H. e Jonassen, I. (2002). New feature subset selection procedures for

classification of expression profiles. Genome Biology, 3(4):research0017.1-

0017.11.

Dopazo, J. et al. (2001). Methods and aproaches in the analysis of gene expression

data, Journal of Immunological Meth-ods. 250:93-112.

Dubes, R. (1987). How many clusters are best? An experiment. Pattern Recognition

20 (6): 645–663.

Doni, M. V. (2004). Análise de cluster: Métodos hierárquicos e de particionamento.

92 f. Trabalho final de graduação (Sistemas de Informação) – Faculdade de

Comunicação e Informática, Universidade Presbiteriana Mackenzie, São Paulo.

Dougherty, J., Kohavi, R. e Sahami, M. (1995). Supervised and Unsupervised

Discretization of Continuous Features. 12th International Conference on

Machine Learning, 194-202.

Eisen, M. B., Spellman, P. T., Brown, P. O. e Botstein, D. (1998). Cluster analysis

and display of genome-wide expression patterns. Proc. Of National Academy of

Sciences USA, Volume 95. 14863–14868.

FatiGo. Ferramenta na web para pesquisa de antologias de genes. Disponível em:

<http://www.fatigo.org>. Acesso em: 02 de junho de 2006.

Freeman, W. M., Walker, S. J. e Vrana, K. E. (1999). Quantitative RT-PCR: pitfalls

and pontential. Biotechniques, 26:112–122.

Fernandes, F. (2000). Dicionário Brasileiro Globo. 53. ed. São Paulo: Globo.

Golub, T.R., Slonim, D.K., Tamayo, P., Huard, C., Gaasenbeek, M., Mesirov, J.P.,

Coller, H., Loh, M.L., Downing, J.R., Caliguiri, M.A., Blo-omfield, C.D. e

Lander, E.S. (1999). Molecular classification of cancer: class discovery and

class prediction by gene expression monitoring. Science 5439 (286): 531–537.

Geman, D. et al. (2004). Classifying Gene Expression Profiles from Pairwise

mRNA Comparisons. Statistical Applications in Genetics and Molecular

Biology, v.3.

Haeseleer, P., Liang, S. e Somogyi, R. (1999). Gene Expression Data Analysis and

Modeling, Proc. of Pacific Symposium on Biocomputing.

Harrington, C. A., Rosenow, C. e Retief, J. (2000). Monitoring gene expression

using DNA microarrays. Curr. Opin. Microbol., 3:285–291.

Hair, J. F., Anderson, R. E., Tatham, R. L. e Black, W. C. (2005). Análise

multivariada dos dados. Porto alegre: Bookman.

Hellem, T. e Inge, J. (2002). New feature subset selection procedures for

classification of expression proles. Genome Biology.

Heyer, L. J., Kruglyak, S. e Yooseph, S. (1999). Exploring expression data:

identification and analysis of co-expressed genes. Genome Research 9 (11):

1106–1115.

Handl, J., Knowles, J. e Kell, D. B. (2005). Computational cluster validation in

post-genomic data analysis. Bioinformatics 21:3201–3212.

Jain, A. K., Murty, M. N. e Flynn, P. (1999). Data clustering: a review. ACM

Computing Surveys 3 (31): 264–323.

Jain A.K. e Dubes, R.C. (1988). Algorithms for clustering data, New Jersey:

Prentice Hall.

Kaufman, L. e Rousseeuw, P. J. (1990). Finding groups in data: an introduction to

cluster analysis. New York: Wiley.

Karthigasoo, S., Cheah, Y. e Manickam, S. (2005). Improving the Accuracy of

Medical Decision Support via a Knowledge Discovery Pipeline using Ensemble

Techniques. Journal of Advancing Information and Management Studies.

Kohavi, R. e Sahami, M. (1996). Error-based and Entropy-based Discretization of

Continuous Features. Proc. 2 nd Int. Conf. on Knowledge Discovery and Data

Mining. pp. 114-119.

Komorowski J. e Bjorvand A.T. (1997). Practical Applications of Genetic

Algorithms for Efficient Reduct Computation. Proc. of 15 th IMACS World

Congress on Scientific Computation, Modelling and Applied Mathematics,

Berlin.

Kuncheva, L. (2004). Combining Pattern Classifiers: Methods and Algorithms.

Wiley-Interscience.

Linha do tempo do DNA. Ciência online, Disponível em:

<http://www1.folha.uol.com.br/folha/especial/2003/dna/fe0703200312.shtml>.

Acesso em: 20 de outubro de 2005.

Liu, Bing et al. (2000). Clustering Through Decision Tree Construction. IBM

Research Report RC 21695 (97737).

Liu, H. e Setiono, R. (1995). Feature Selection and Discretization of Numeric

Attributes. Proc. 7 th Int. Conf. on Tools with Artificial Intelligence,

Washington D.C.

Lopes, Sônia. (1997). Bio. São Paulo: Saraiva.

Merck. Manual Merck para a família. Doenças Cardiovasculares. Seção 3, Cap. 25.

Disponível em: < http://www.manualmerck.net/>. Acesso em: 15 maio 2006.

Mitchell, T. M. (1997). Machine Learning. Mc Graw Hill.

Milligan, G. W., e Cooper, M. C. (1986) A study of the comparability of external

criteria for hierarchical cluster analysis. Multivariate Behavorial Research

21:441–458.

Monti, S., Tamayo, P., Mesirov, J., e Golub, T. (2003). Consensus clustering: a

resampling-based method for class discovery and visualization of gene

expression microarray data. Machine Learning 52:91–118.

Napoli, W. F. M de. (2003). Introdução A Bioinformática. 163 f. Trabalho final de

graduação (Engenharia elétrica) - Universidade Federal de Goiás, Gaiânia.

Nguyen, H.S. e Skowron A. (1995). Quantization of Real-Valued Attributes:

Rough Set and Boolean Reasoning Approach. In: Proceedings of the 2nd Joint

Annual Conference on Information Sciences, Wrightsville Beach, 34-37.

Ortiz, Lúcia. A descoberta da Estrutura do DNA. Patrimônio Genético, Disponível

em: <http://www.comciencia.br/reportagens/genetico/gen09.shtml>. Acesso

em: 15 de outubro de 2004.

Passarge, E. (2003). Genética - Texto e Atlas. Artmed.

Pedrycz, W. (2005). Knouledge-Based Clustering - From Data to Information

Granules. Wiley.

Pawlak, Z. (1982). Rough Sets. International Jornal of Computer and Information

Sciences, Pages 341-356.

Pila, Adriano Donizete. (2001). Seleção de atributos relevantes para aprendizado de

maquina utilizando Rough Sets. 144 f. Dissertação (Mestrado em Ciências –

Área de Computação e Matemática Computacional) – Instituto de Ciências

Matemáticas e de Computação, Universidade de São Paulo, São Carlos.

Pereira, Lygia da Veiga. (2001). Seqüenciaram o Genoma Humano... E agora?. São

Paulo: Moderna, 111 p.

Pierotti, Marco. Para além do genoma. Passos, n. 23, 2001. Disponível em:

<http://www.cl.org.br/genom23.htm>. Acesso em: 15 de outubro de 2004.

Pui, C.H. e Evans, W.E. (1998). Acute lymphoblastic leukemia. N. Engl. J. Med.

339, 605–615.

Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81 106.

Quinlan, J. R. (1993). C4.5 Programs for Machine Learning. San Mateo, CA:

Morgan Kaufmann.

Quackenbush, J. (2001) Computational analysis of cDNA microarray data. Nature

Reviews 6 (2): 418–428.

Resende, S., et al. (2003) Sistemas Inteligentes: fundamentos e aplicações. Manole.

Setubal, João Carlos. A origem e o sentido da bioinformática. Bioinformática,

Disponível em:

<http://www.comciencia.br/reportagens/bioinformatica/bio10.shtml>. Acesso

em: 17 de fevereiro de 2004.

Silverman, L.B., Gelber, R.D., Dalton, V.K., Asselin, B.L., Barr, R.D., Clavell,

L.A., Hurwitz, C.A., Moghrabi, A., Samson, Y., Schorin, M.A., et al. (2001).

Improved outcome or children with acute lymphoblastic leukemia: results of

Dana-Farber Consortium Protocol 91-01. Blood 97, 1211–1218.

Singh, D. et al. (2002). Gene expression correlates of clinical prostate cancer

behavior. Cancer Cell, 1(2):203-209.

Su, A. L., Cooke, M. P., Ching, K. A., Hakak, Y., Walker, J. R., Wiltishire, T.,

Orth, A. P., Vega, R. G., Sapinoso, L. M., Moqrich, A., Patapoutian, A.,

Hampton, G. M., Schultz, P. G. e Hogenesch, J. B. (2002). Large-scale analysis

of human and mouse transcriptomes. Proceedings of the National Academy of

Sciences, Volume 99. 4465–4470.

Slowinski, R. Rough Set approach to decision analysis. (1995). AI Expert, March:

19-25.

Slonim, D. (2002). From patterns to pathways: gene expression data analysis comes

of age. Nature Genetics 32:502–508.

Souto, M. C. P de., Lorena, A. C., Delbem, A. C. B. e Carvalho, A. C. P. L. F.

(2003). Pages 103–152 in Técnicas de Aprendizado de Máquina para

Problemas de Biologia Molecular 2003. Jornadas de Atualização em

Inteligência Artificial - JAIA. Editora SBC.

Tamayo, P., Slonim, D., Mesirov, J., Zhu, Q., Kitareewan, S., Dmitrovsky, E., Ler,

E. S. e Golub, T. R. (1999). Interpreting patterns of gene expression with self-

organizing maps: methods e application to hematopoietic differentiation. Proc.

of National Academy of Sciences USA, Volume 16:96. 2907–2912.

Tan, Aik Choon et al. (2005). Simple decision rules for classifying human cancers

from gene expression profiles.

Ueno, K., Kumagai, T., Kijima, T., Kishimoto, T. e Hosoe, S. (1998). Cloning and

tissue expression of cDNAs from chromosome 5q21-22 which is frequently

deleted in advanced lung cancer. Human Genetics - vol. 102, nr. 1, pp. 63-68.

Velculescu, V. E. et al. (1995). Serial analysis of gene expression. Science,

270:484–487.

Wróblewski, J. (1995). Finding Minimal Reducts using Genetic Algorithms. Proc.

2 nd Annual Joint Conf. on Information Sciences, Wrightsville Beach, NC.

USA pp.186-189.

West, M. et al. (2001). Predicting the clinical status of human breast cancer using

gene expression proles. Proc. Natl. Acad. Sci. USA, 98:11462-11467.

Yanagi Y., Yoshikai Y., Leggett K., Clark S. P., Aleksander I., Mak T. W. (1984).

A human T cell-specific cDNA clone encodes a protein having extensive

homology to immunoglobulin chains. Nature. Mar 8-14; 308(5955):145-9.

Yeoh, E. J., Ross, M. E., Shurtleff , S. A., Williams W. K., Patel, D. et al. (2002).

Classification, subtype discovery, and prediction of outcome in pediatric acute

lymphoblastic leukemia by gene expression profiling. Cancer Cell. 1 (2): 133–

143.

Anexos

Anexo A

Anotações dos genes segundo o FatiGO

(Biological Process)

Gene Termos GO

AA919102 Não há termos GO associados a esse gene.

AB002438

Gene hipotético. Não há termos GO associados a

esse gene.

AB010419

Cell proliferation; regulation of nucleobase,

nucleoside, nucleotide and nucleic acid metabolism.

AB019392 Translational initiation.

AF070614 Não há termos GO associados a esse gene.

AL050159 Não há termos GO associados a esse gene.

D13640 Cell death; programmed cell death.

D73409

Signal transduction; regulation of cell size; protein

kinase C activation.

M17886 Protein biosynthesis; translational elongation.

U02493

DNA repair; regulation of transcription; RNA

splicing, via transesterification reactions; nuclear

mRNA splicing, via spliceosome.

U07223 Signal transduction; intracellular signaling cascade.

U12255 Defense response; antigen presentation.

U52682

T-helper 1 type immune response; regulation of T-

helper cell differentiation; positive regulation of

cytokine biosynthesis.

U59151

Chromosome organization and biogenesis (sensu

Eukaryota); telomerase-dependent telomere

maintenance.

U68019

Transforming growth factor beta receptor signaling

pathway; regulation of transcription, DNA-

dependent.

U90878

Response to oxidative stress; response to abiotic

stimulus; response to chemical stimulus.

X00437

Gene hipotético. Não há termos GO associados a

esse gene.

Y18004

Cellular physiological process; regulation of cellular

process; metabolism; regulation of physiological

process.

Obtidos através da ferramenta FatiGo

(Al-Shahrour, 2004; Al-Shahrour, 2005; Al-Shahrour, 2006; Fatigo, 2006)

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 