LABIC
Utilizando Inteligência
Artificial em
Bioinformática
Prof. André de Carvalho
LABIC - Universidade de São Paulo
André de Carvalho
1
Principais tópicos
LABIC
Introdução
 Bioinformática
 Biologia Molecular
 Reconhecimento de Genes
 Utilizando Inteligência Artificial
 Conclusão

André de Carvalho
2
LABIC
IA e Bioinformática
Redes Neurais, Algorítmos genéticos
BIOLOGIA
COMPUTAÇÃO
Bioinformática
André de Carvalho
3
LABIC
Definições

Bioinformática
 Pesquisa e desenvolvimento de ferramentas
computacionais, matemáticas e estatísticas para
a resolução de problemas da Biologia
 Biologia molecular
A Computação está para a Biologia da mesma
forma que a Matemática está para a Física.
Harold Morowitz
André de Carvalho
4
LABIC

Bioinformática
Nos últimos anos, diversos laboratórios têm
trabalhado no seqüenciamento de vários genomas
 Até o ano 2000:
 Mais que 30 organismos tinham sido seqüenciados
 Cerca de 150 organismos estavam sendo seqüenciados
 Determinação da seqüência de nucleotídeos em uma
molécula é o primeiro passo para entender seu
funcionamento
 Beneficia várias áreas
 Medicina - Farmácia - Agricultura
André de Carvalho
5
LABIC
Crescimento do GenBank
Número de sequências armazenadas no banco de
dados GenBank
12000000
10000000
8000000
6000000
4000000
2000000
0
1990
1992
1994
1996
1998
2000
Ano
André de Carvalho
6
LABIC
Andamento de projetos genoma

73 genomas completos publicados
 Humano
 Camundongo
 Drosophila
 Arabidopsis
 Levedura
212 de procariotos em andamento
 157 de eucariotos em andamento

André de Carvalho
7
LABIC
Fração do genoma da levedura
CCACACCACACCCACACACCCACACACCACACCACACACCACACCACACCCACACACACACATCCTAACACTACCCTAACACAGCCCTAATCTAACCCTGGCCAACCTGTCTCTCAACTTACCC
TCCATTACCCTGCCTCCACTCGTTACCCTGTCCCATTCAACCATACCACTCCGAACCACCATCCATCCCTCTACTTACTACCACTCACCCACCGTTACCCTCCAATTACCCATATCCAACCCAC
TGCCACTTACCCTACCATTACCCTACCATCCACCATGACCTACTCACCATACTGTTCTTCTACCCACCATATTGAAACGCTAACAAATGATCGTAAATAACACACACGTGCTTACCCTACCACT
TTATACCACCACCACATGCCATACTCACCCTCACTTGTATACTGATTTTACGTACGCACACGGATGCTACAGTATATACCATCTCAAACTTACCCTACTCTCAGATTCCACTTCACTCCATGGC
CCATCTCTCACTGAATCAGTACCAAATGCACTCACATCATTATGCACGGCACTTGCCTCAGCGGTCTATACCCTGTGCCATTTACCCATAACGCCCATCATTATCCACATTTTGATATCTATAT
CTCATTCGGCGGTCCCAAATATTGTATAACTGCCCTTAATACATACGTTATACCACTTTTGCACCATATACTTACCACTCCATTTATATACACTTATGTCAATATTACAGAAAAATCCCCACAA
AAATCACCTAAACATAAAAATATTCTACTTTTCAACAATAATACATAAACATATTGGCTTGTGGTAGCAACACTATCATGGTATCACTAACGTAAAAGTTCCTCAATATTGCAATTTGCTTGAA
CGGATGCTATTTCAGAATATTTCGTACTTACACAGGCCATACATTAGAATAATATGTCACATCACTGTCGTAACACTCTTTATTCACCGAGCAATAATACGGTAGTGGCTCAAACTCATGCGGG
TGCTATGATACAATTATATCTTATTTCCATTCCCATATGCTAACCGCAATATCCTAAAAGCATAACTGATGCATCTTTAATCTTGTATGTGACACTACTCATACGAAGGGACTATATCTAGTCA
AGACGATACTGTGATAGGTACGTTATTTAATAGGATCTATAACGAAATGTCAAATAATTTTACGGTAATATAACTTATCAGCGGCGTATACTAAAACGGACGTTACGATATTGTCTCACTTCAT
CTTACCACCCTCTATCTTATTGCTGATAGAACACTAACCCCTCAGCTTTATTTCTAGTTACAGTTACACAAAAAACTATGCCAACCCAGAAATCTTGATATTTTACGTGTCAAAAAATGAGGGT
CTCTAAATGAGAGTTTGGTACCATGACTTGTAACTCGCACTGCCCTGATCTGCAATCTTGTTCTTAGAAGTGACGCATATTCTATACGGCCCGACGCGACGCGCCAAAAAATGAAAAACGAAGC
AGCGACTCATTTTTATTTAAGGACAAAGGTTGCGAAGCCGCACATTTCCAATTTCATTGTTGTTTATTGGACATACACTGTTAGCTTTATTACCGTCCACGTTTTTTCTACAATAGTGTAGAAG
TTTCTTTCTTATGTTCATCGTATTCATAAAATGCTTCACGAACACCGTCATTGATCAAATAGGTCTATAATATTAATATACATTTATATAATCTACGGTATTTATATCATCAAAAAAAAGTAGT
TTTTTTATTTTATTTTGTTCGTTAATTTTCAATTTCTATGGAAACCCGTTCGTAAAATTGGCGTTTGTCTCTAGTTTGCGATAGTGTAGATACCGTCCTTGGATAGAGCACTGGAGATGGCTGG
CTTTAATCTGCTGGAGTACCATGGAACACCGGTGATCATTCTGGTCACTTGGTCTGGAGCAATACCGGTCAACATGGTGGTGAAGTCACCGTAGTTGAAAACGGCTTCAGCAACTTCGACTGGG
TAGGTTTCAGTTGGGTGGGCGGCTTGGAACATGTAGTATTGGGCTAAGTGAGCTCTGATATCAGAGACGTAGACACCCAATTCCACCAAGTTGACTCTTTCGTCAGATTGAGCTAGAGTGGTGG
TTGCAGAAGCAGTAGCAGCGATGGCAGCGACACCAGCGGCGATTGAAGTTAATTTGACCATTGTATTTGTTTTGTTTGTTAGTGCTGATATAAGCTTAACAGGAAAGGAAAGAATAAAGACATA
TTCTCAAAGGCATATAGTTGAAGCAGCTCTATTTATACCCATTCCCTCATGGGTTGTTGCTATTTAAACGATCGCTGACTGGCACCAGTTCCTCATCAAATATTCTCTATATCTCATCTTTCAC
ACAATCTCATTATCTCTATGGAGATGCTCTTGTTTCTGAACGAATCATAAATCTTTCATAGGTTTCGTATGTGGAGTACTGTTTTATGGCGCTTATGTGTATTCGTATGCGCAGAATGTGGGAA
TGCCAATTATAGGGGTGCCGAGGTGCCTTATAAAACCCTTTTCTGTGCCTGTGACATTTCCTTTTTCGGTCAAAAAGAATATCCGAATTTTAGATTTGGACCCTCGTACAGAAGCTTATTGTCT
AAGCCTGAATTCAGTCTGCTTTAAACGGCTTCCGCGGAGGAAATATTTCCATCTCTTGAATTCGTACAACATTAAACGTGTGTTGGGAGTCGTATACTGTTAGGGTCTGTAAACTTGTGAACTC
TCGGCAAATGCCTTGGTGCAATTACGTAATTTTAGCCGCTGAGAAGCGGATGGTAATGAGACAAGTTGATATCAAACAGATACATATTTAAAAGAGGGTACCGCTAATTTAGCAGGGCAGTATT
ATTGTAGTTTGATATGTACGGCTAACTGAACCTAAGTAGGGATATGAGAGTAAGAACGTTCGGCTACTCTTCTTTCTAAGTGGGATTTTTCTTAATCCTTGGATTCTTAAAAGGTTATTAAAGT
TCCGCACAAAGAACGCTTGGAAATCGCATTCATCAAAGAACAACTCTTCGTTTTCCAAACAATCTTCCCGAAAAAGTAGCCGTTCATTTCCCTTCCGATTTCATTCCTAGACTGCCAAATTTTT
CTTGCTCATTTATAATGATTGATAAGAATTGTATTTGTGTCCCATTCTCGTAGATAAAATTCTTGGATGTTAAAAAATTATTATTTTCTTCATAAAGAAGCTTTCAAGATATAAGATACGAAAT
AGGGGTTGATAATTGCATGACAGTAGCTTTAGATCAAAAAGGAAAGCATGGAGGGAAACAGTAAACAGTGAAAATTCTCTTGAGAACCAAAGTAAACCTTCATTGAAGAGCTTCCTTAAAAAAT
TTAGAATCTCCCATGTCAACGGGTTTCCATACCTCCCCAGCATCATACATCTTTTTTCAAAGAAACTTCAAATGCCTCTTTTATGCAAGGGGCAAAATCCTGAAATGACTTAAACTTAGCAGTT
TCGTCTTTTTTCAAAGAGAATGGTTGAAGAAGAATTGTTTTGGACGCTTATTGACAATCTGTTGCATTGATAAAGTACCTACTATCCCAGACTATATTTGTATACAAGTACAAAATTAGGTTTG
TTGAAACAACTTTCCGATCATTGGTGCCCGTATCTGATGTTTTTTTAGTAATTTCTTTGTAAATACAGGGAGTTGTTTCGAAAGCTTATGAGAAAAATACATGAATGACAGGTAAAAATATTGG
CTCGAAAAAGAGGACAAAAAGAGAAATCATAAATGAGTAAACCCACTTGCTGGACATTATCCAGTAAAGGCTTGGTAGTAACCATAATATTACCCAGGTACGAAACGCTAAGAACCTTGAAAGA
CTCATAAAACTTCCAGGTTAAGCTATTTTTGAAAATATTCTGAGGTAAAAGCCATTAAGGTCCAGATAACCAAGGGACAATAAACCTATGCTTTTCTTGTCTTCAATTTCAGTATCTTTCCATT
TTGATAATGAGCATGTGATCCGGAAAGCTACTTTATGATGTTTCAAGGCCTGAAGTTTGAATATTTATGTAGTTCAACATCAAATGTGTCTATTTTGTGATGAGGCAACCGTCGACAACCTTAT
TATCGAAAAAGAACAACAAGTTCACATGCTTGTTACTCTCTATAACTAGAGAGTACTTTTTTTGGAAGCAAGTAAGAATAAGTCAATTTCTACTTACCTCATTAGGGAAAAATTTAATAGCAGT
TGTTATAACGACAAATACAGGCCCTAAAAAATTCACTGTATTCAATGGTCTACGAATCGTCAATCGCTTGCGGTTATGGCACGAAGAACAATGCAATAGCTCTTACAAGCCACTACATGACAAG
CAACTCATAATTTAA
André de Carvalho
8
Bioinformática
LABIC

Ênfase está se deslocando progressivamente
da acumulação de dados para a sua
interpretação
 Com os seqüenciamentos realizados, uma grande
quantidade de dados tem sido gerada
 Estes dados precisam agora ser analisados
 Análise laboratorial destes dados é difícil e cara
 Ferramentas computacionais sofisticadas são
necessárias para a análise dos dados obtidos
André de Carvalho
9
Bioinformática
LABIC

Para muitas destas análises, as ferramentas
computacionais precisam lidar com dados
imprecisos e ruidosos
 Técnicas de laboratório de Biologia Molecular
quase sempre geram dados com erros ou
imprecisões
 Na medição dos valores ou definição das classes
 Inteligência Artificial fornecem técnicas
eficientes para lidar com problemas deste tipo
André de Carvalho
10
LABIC

Biologia Molecular
Estudo das células e moléculas
 Em particular: genoma dos organismos

Estruturas principais:
 Genes
 Cromossomos
 DNA
nucleotídeos
 RNA
 Proteínas
aminoácidos
André de Carvalho
Expressão
Gênica
11
LABIC

Biologia Molecular
Dogma central da Biologia Molecular
 Transferência de Informação
Replicação
DNA
Transcrição
RNA
Tradução
André de Carvalho
Proteínas
12
Biologia Molecular
LABIC

Algumas descobertas posteriores contradizem
este dogma:
 RNA pode sofrer replicação em alguns vírus e
plantas
 RNA viral, através de uma enzima denominada
transcriptase reversa, pode ser transcrito em DNA
 DNA pode traduzir diretamente proteínas
específicas
 Sem passar pelo processo de transcrição
André de Carvalho
13
Biologia Molecular
LABIC

DNA (Ácido Desoxirribonucleico)
 O DNA é uma molécula formada por duas fitas (dupla
fita) que se entrelaçam formando uma hélice dupla
 DNA é composto de quatro nucleotídeos diferentes
 Adenina, Citosina, Guanina e Timina
 Fitas são mantidas juntas por ligações
que conectam cada nucleotídeo de uma
fita ao seu complemento na outra
• A se liga com T e C se liga com G
André de Carvalho
14
Biologia Molecular
LABIC

Genes
 Subseqüências de DNA
 Localizados no cromossomo
 Servem como molde para a produção de
proteínas
 Encaixadas entre os genes estão segmentos
chamados de regiões não codificadoras
André de Carvalho
15
Biologia Molecular
LABIC

Proteínas
 Definem estrutura, função e mecanismos
regulatórios das células
 Exemplos de mecanismos regulatórios: controle do
ciclo celular, transcrição gênica
 Seqüências lineares
 Combinações de 20 aminoácidos diferentes
 Três nucleotídeos (codon) formam um aminoácido
André de Carvalho
16
LABIC
Biologia Molecular
André de Carvalho
17
Biologia Molecular
LABIC

Expressão gênica
 Processo pelo qual genes são usados para
produzir proteínas
 Mecanismos de expressão gênica são diferentes
para organismos:
 Eucariotos
• Material genético difuso nas células (Ex.: bactérias)
 Procariotos
• Material genético em um núcleo (Ex.: seres humanos)
André de Carvalho
18
Processo de expressão gênica
LABIC

Transcrição
 RNA polimerase é a molécula (enzima) que
transcreve DNA em RNA
 RNA polimerase começa a transcrição após se
ligar a um sinal regulatório no DNA chamado
promotor
 Gera molécula de RNA mensageiro (mRNA)
André de Carvalho
19
Processo de expressão gênica
LABIC

Transcrição depende do organismo
 Organismos eucariotos
 Cada gene é transcrito independentemente
 Existe um promotor antes de todo gene
 Organismos procariotos
 Vários genes consecutivos podem ser transcritos em
uma única molécula de RNA
 Não existe necessariamente um promotor antes de
cada gene
André de Carvalho
20
LABIC

Processo de expressão gênica
Tradução
 Sintetiza uma proteína utilizando como forma mRNA
 Leitura do mRNA é feita por uma molécula chamada de
ribossomo
 Mensagem lida é utilizada para montar uma cadeia de proteína
• Tripla de nucleotídeos consecutivos (codon) codifica um
aminoácido
 Código genético: mapeamento de codons em
aminoácidos
André de Carvalho
21
LABIC
Processo de expressão gênica
DNA
RNA Polimerase
T G CAG C T C C G GAC TC CAT . . .
Transcrição
promotor
mRNA
A
André de Carvalho
22
LABIC
Processo de expressão gênica
DNA
RNA Polimerase
T G CAG C T C C G GAC TC CAT . . .
promotor
Transcrição
mRNA
AC GU C GAGG C C U GAGGUA. . .
André de Carvalho
23
LABIC
Processo de expressão gênica
DNA
RNA Polimerase
T G CAG C T C C G GAC TC CAT . . .
promotor
Transcrição
Ribossomo
mRNA
AC G U C GAGG C C U GAGGUA. . .
Tradução
Thr
André de Carvalho
24
LABIC
Processo de expressão gênica
DNA
RNA Polimerase
T G CAG C T C C G GAC TC CAT . . .
Transcrição
promotor
mRNA
AC GU C GAGG C C U GAGGUA. . .
Tradução
Ser
Cys
André de Carvalho
His
Ser
Gly
Ribossomo
Leu
25
Processo de expressão gênica
LABIC

Estrutura de leitura
 Para uma dada faixa de DNA, nucleotídeos podem
ser agrupados em triplas de três formas diferentes
 Um dos nucleotídeos pode ocupar a 1a, 2a ou 3a
posição em um codon
 Apenas um destes três possíveis agrupamentos é
realmente lido pelo ribossomo
 O agrupamento lido é chamado de estrutura de
leitura do gene
A T T AC G A A G
André de Carvalho
26
Processo de expressão gênica
LABIC

Em organismos eucariotos, existe um outro passo
importante durante o processo de expressão
gênica
 Após o DNA ser transcrito, certas partes da molécula
são eliminadas antes de sua transformação em
proteína

Genes em eucariotos são formados por segmentos
alternados de exons e introns
André de Carvalho
27
LABIC

Regiões de splice
Exons:
 Seqüências de nucleotídeos que são expressas
(traduzidas em proteínas)

Introns:
 Seqüências intercaladas que são eliminadas na tradução

Regiões de splice (splice-junctions):
 Pontos de fronteira onde ocorrem junções de exons e
introns
 Doadoras: bordas exon-intron
 Aceptoras: bordas intron-exon
André de Carvalho
28
LABIC
Splice-junctions
DNA
doador aceptor
exon
Transcrição
mRNA
intron
Splicing
mRNA
André de Carvalho
29
Biologia Molecular e IA
LABIC

Problemas da Biologia Molecular que podem ser
tratados por IA







André de Carvalho
Reconhecimento de genes
Construção de árvores filogenéticas
Análise de expressão gênica
Previsão de estruturas de proteínas
Análise de interação entre genes
Montagem de fragmentos
Alinhamento de seqüências
30
LABIC


Reconhecimento de genes
Um dos principais problemas em biologia
molecular é a identificação de genes em seqüências
de DNA não caracterizadas
Algoritmos convencionais não têm sido eficientes
 Variação natural dos genes
 Complexidade dos genes
 Natureza pouco compreendida dos genes

Abordagem promissora: Aprendizado de Máquina
André de Carvalho
31
LABIC
Reconhecimento de genes
 Duas
abordagens principais têm sido
seguidas:
 Busca por sinal
 Busca por conteúdo
André de Carvalho
32
Reconhecimento de genes
LABIC

Busca por sinal
 Localiza genes indiretamente
 Procura sinais particulares relacionados com a
expressão de genes
 Sinal
 Região localizada do DNA que realiza uma função
específica (exemplo: se liga a uma enzima)
André de Carvalho
33
Reconhecimento de genes
LABIC

Busca por conteúdo
 Reconhece genes diretamente
 Identifica segmentos de seqüências de DNA que
possuem as propriedades gerais de regiões
codificadoras
 Se baseia no conhecimento das diferentes
propriedades estatísticas de regiões codificadoras
e não codificadoras
André de Carvalho
34
Busca por sinal
LABIC

É importante não apenas entender a função
de cada gene
 Mas também os mecanismos que regulam a
expressão do gene
 Vários sinais exercem importantes funções
regulatórias definindo:
 Condições sob as quais os genes são expressos
 Taxa com a qual a expressão ocorre
André de Carvalho
35
Busca por sinal
LABIC

Detecção de sinal já é um problema em si
 Vários sinais que podem ser identificados em
seqüências de nucleotídeos são importantes para a
identificação de genes





André de Carvalho
Sítios de início de transcrição (promotores)
Sítios de término de transcrição (terminadores)
Sítios de splice-junction
Sítios de início da tradução (codons de iniciação)
Sítios de término da tradução (codons de parada ou stop
codons)
36
Busca por sinal
LABIC

Diferentes sinais têm diferentes dificuldades de
identificação
 Codons de parada são facilmente identificados
 Identificação de outros sinais é mais complicada

Busca por sinal é uma tarefa de classificação
 Dada uma janela de tamanho fixo de um DNA,
determinar se ela contém um sinal de interesse
 Se uma característica identificável do sinal ocupa
uma posição particular na janela
André de Carvalho
37
LABIC
Busca por sinal
Promotor na posição 3?
Classificador
Representação das
características
Posição 1 = ‘C’
Posição 2 = ‘T’
Posição 3 = ‘T’
Posição 4 = ‘A’
Posição 5 = ‘C’
Posição 6 = ‘G’
Seqüência de DNA ... A T C G T G C T T A C G C G T C C A
André de Carvalho
1 2 3 4 5 6
38
Reconhecimento de início da tradução
LABIC



Reconhece codons de iniciação
Tradução de mRNA em proteína não começa
com sua primeira tripla de nucleotídeos
Em organismos procariotos, uma simples
molécula de mRNA pode ter vários sítios de
início de tradução
 Genes consecutivos podem ser transcritos em uma
única cadeia de mRNA
André de Carvalho
39
LABIC

Reconhecimento de promotores
Sinal regulatório de uma molécula de DNA onde
RNA polimerase se liga para começar a transcrição
 RNA polimerase é uma molécula que transcreve DNA
em RNA
 Auxilia na localização de genes no DNA
 Existem sítios amplamente aceitos como sendo as
regiões que fornecem as carecterísticas definidoras de
promotores
 Regiões 10 e 35
André de Carvalho
40
Busca pelo conteúdo
LABIC

Identifica genes reconhecendo padrões que que
ocorrem na sua seqüência de nucleotídeos
 Regiões do DNA que serão traduzidas em proteínas
 Organismos procariotos: distinguir genes de regiões
não codificadoras
 Organismos eucariotos: distinguir também introns
de exons
 Janelas de tamanho fixo também são utilizadas para
esta previsão
André de Carvalho
41
Busca pelo conteúdo
LABIC

Busca por conteúdo procura responder as
seguintes perguntas:
 Quais são as regiões codificadoras
 Para uma dada região, que faixa e qual estrutura
de leitura codifica a proteína

Várias propriedades podem ser exploradas
para distinguir regiões codificadoras de não
codificadoras
André de Carvalho
42
Busca pelo conteúdo
LABIC

Propriedades que podem ser exploradas:
 Alguns aminoácidos são usados mais freqüentemente que
outros em regiões codificadoras
 A existência de diferentes números de codons para
aminoácidos diferentes
 Codons que mapeiam em um dado aminoácido não são
usados igualmente na maioria dos organismos
 Não podem conter codons de parada
 Alguns codons têm maior probabilidade de serem
vizinhos
André de Carvalho
43
Reconhecimento de genes
LABIC

Abordagens mais promissoras em
reconhecimento de genes:
 Combinam previsão de vários sinais diferentes
e regiões codificadoras

Reconhecimento de operons
 Genes consecutivos que são ativados ou
desativados em conjunto
André de Carvalho
44
Redes Neurais Artificiais
LABIC

Sistemas computacionais distribuídos
baseados na estrutura e funcionamento do
sistema nervoso
 Nodos simulam neurônios
 Conexões ponderadas simulam sinapses

Definidas por
 Arquitetura
 Aprendizado
André de Carvalho
45
LABIC
Redes Neurais Artificiais
camadas intermediárias
camada de
entrada
camada de
saída
conexões
André de Carvalho
46
LABIC

Redes Neurais Artificiais
Stormo et al (1982): reconhecimento de sítios de início
de tradução no DNA de bactérias E. Coli
 Primeira aplicação de Redes Neurais em Bioinformática
 Utilizou rede Perceptron
A C G T
A C G T A C G T
... A T C G T G C T T A C G C G C G T ...
André de Carvalho
47
LABIC
Redes Neurais Artificiais
Trabalho
Towell et al (1990)
Problema abordado
Sítios de início de transcrição
Uberbacher et al (1993) Servidor GRAIL - identificação de genes
Riis et al (1995)
Polyac et al (1992)
Ma e Wang (1999)
Bajic et al. (2002)
Rampone (1998)
André de Carvalho
Previsão de estrutura de proteínas
Reconhecimento de promotores
Reconhecimento de regiões de splicing
48
LABIC
Algoritmos Genéticos

Técnica de busca e otimização
 Baseados na genética e teoria da seleção natural
 Utiliza uma população de soluções candidatas
(indivíduos)
 A cada indivíduo é associado um escore de aptidão, que
mede o quão boa é a solução que ele representa
 Otimização ocorre em várias gerações
 A cada geração
• Mecanismos de seleção selecionam os indivíduos mais aptos
• Operadores de reprodução geram novos indivíduos
André de Carvalho
49
LABIC
Algoritmos Genéticos
População inicial
População final
Avaliação
População atual
Seleção
Reprodução
André de Carvalho
50
LABIC

Algoritmos Genéticos
Alinhamento de seqüências:
 Uma a uma
 Uma com várias
 Identificar:
 Inserções
 Remoções
 Substituições
André de Carvalho
Seq1: A G C C A T A T
Seq2: A C G C T A T A
Seq1: A  G C C A T A T
Seq2: A C G C T A T A 
51
LABIC
Algoritmos Genéticos
Trabalho
Alander (1995)
Krasnogor et al. (1999)
Zhang e Wong (1997)
André de Carvalho
Problema abordado
Previsão de estrutura de
proteínas
Alinhamento de sequências
52
LABIC
Raciocínio Baseado em Casos

Resolve novos problemas adaptando soluções de
problemas anteriores semelhantes
Solução
Problema
André de Carvalho
2
1
Nova solução
Novo problema
53
Raciocínio Baseado em Casos
LABIC

RBC é mais que uma Base de Dados
 Não é uma tabela de busca

Sistemas de RBC procuram casos passados
semelhantes ao problema atual em uma base de
casos indexada
 Indexação e representação de casos facilitam
recuperação de casos relevantes e sua comparação
com o problema atual
 Permite adaptação de casos
André de Carvalho
54
LABIC
Raciocínio Baseado em Casos
Ciclo de um sistema de RBC
André de Carvalho
(Aamodt, 1993)
55
LABIC
Raciocínio Baseado em Casos
Trabalho
Problema abordado
Shavlik (1990, 1991)
Reconhecimento de genes
Harris et al. (1993)
Alinhamento de seqüências
André de Carvalho
56
LABIC
Classificadores de Margens Largas

Maximizam a margem de separação entre
classes presentes nos dados
 Máquinas de Vetores Suporte (SVMs)
 Boosting
 Maior capacidade de generalização
 Baseados na Teoria de Aprendizado
EstatísticoVapnik e Chervonenkis (1968)
 Embute conceitos probabilísticos e estatísticos
André de Carvalho
57
LABIC

Classificadores de Margens Largas
Máquinas de Vetores Suporte
 Encontra um hiperplano ótimo que separa classes em um
espaço abstrato
margem
Classe 1
Classe 2
André de Carvalho
58
LABIC
Classificadores de Margens Largas

Análise de expressão gênica
Gene
1
2
3
4
André de Carvalho
Expressão
Tecido normal
Tecido com tumor
T1 T2 T3
T1 T2 T3
128 100 30
20 10
9
20 10 18
104 210 47
29 130 7
37 310 40
21 12 15
92 123 84
59
LABIC
Classificadores de Margens Largas
Trabalho
Técnicas
Problema abordado
Ding e Dubchak (2001) SVMs, RNs
Estrutura proteínas
Zien et al. (2000)
SVMs
Sítios de início de tradução
Furey et al. (2001)
SVMs
DNA microarray
Bem-Hur et al. (2000)
SVMs, AB, DNA microarray
clusterização
Brown et al. (1999)
SVMs, ADs
DNA microarray
Karchin et al. (2002)
SVMs
Subfamílias proteínas
Jackson (1995)
AB, RNs
Promotores, reg. codificadoras
Huss et al. (2001)
ADs, AB
Especificidade proteínas
André de Carvalho
60
LABIC

Árvores de Decisão
Organizam informações em
estrutura composta de nós e
ramificações
 Nós: testes sobre atributos;
 Ramos: resultados dos testes
sorri
segura
espada
inimigo
André de Carvalho
não
sim
inimigo
balão ou
bandeira
amigo
61
Árvores de Decisão
LABIC

Lapedes et al (1989): detecção de regiões de
splicing (regiões doadoras)
 Entrada: cadeia de nucleotídeos
Posição 8 = ?
C
A
Posição 3 = ? Positivo
A
Negativo
André de Carvalho
C
Negativo
G
G
Negativo Posição 9 = ?
T
Positivo
T
A
Negativo
C
Positivo
G
Negativo
T
Negativo
62
LABIC
Outras técnicas
Técnica
Problema
Redes Baysianas
Detecção de genes Friedman et al
(2000)
Cadeias de
Markov
Detecção de genes Eddy (1998)
RNAs, AGs e kNN
Estrutura de
proteínas
Guan et al (1994)
Lingüística
computacional
Previsão da
estrutura de genes
Dond e Searls
(1994)
André de Carvalho
Trabalho
63
Projeto Fapesp Genoma Clínico
LABIC

Genoma do câncer humano
 Dados clínicos e de expressão gênica
 Sage, PCR, Microarray e MPSS
 9 tipos de câncer
 Análise de expressão gênica
 Data mining
 Utiliza técnicas de Aprendizado de Máquina
 FAPESP e Instituto Ludwig
André de Carvalho
64
Projeto CNPq - Bioinformática
LABIC

Reconhecimento de genes
 Identificação de promotores
 Reconhecimento de regiões de splicing
 Reconhecimento de regiões codificadoras
 Utiliza SVMs, AB e RNs
 Metodologias para melhorar desempenho
 Redução de ruídos
 Seleção de atributos
 CNPq e FAPESP
André de Carvalho
65
LABIC
Projeto CNPq - Bioinformática

Melhoramento genético
 Utiliza marcadores moleculares para avaliar
potencial genético
 10 marcadores (2 já foram avaliados)
 Identificação de cruzamentos mais promissores
 Previsão de ganho de peso entre nascimento e
desmama
 Utiliza SVMs e RNs
 CNPq e Embrapa
André de Carvalho
66
Referências de IA e Bioinformática
LABIC

Artificial Intelligence and Molecular Biology
 Editado por Lawrence Hunter, AAAI Press Book
 Disponível gratuitamente na internet

Bioinformatics (Adaptive Computation and Machine
Learning)
 Pierre Baldi, Soren Brunak, Sren Brunak, MIT Press

Neural Networks and Genome Informatics
 Cathy H. Wu, Jerry W. McLarty, Elssevier

Data Analysis and Classification for Bioinformatics
 Arun Jagota
André de Carvalho
67
LABIC
Conclusão
Introdução
 Bioinformática
 Biologia Molecular
 Reconhecimento de Genes
 Utilização de IA em Bioinformática

André de Carvalho
68
LABIC
Agradecimentos
Ana Carolina Lorena
 Cláudia Regina Milaré
 Humberto de Sousa
 Silvia Gorla Modonese da Silva
 Alexandre Delbem
 Katti Faceli
 Welington Martins

André de Carvalho
69
LABIC


Reconhecimento de regiões de splicing
Dados: regiões de splicing de primatas (UCI)
Divisão do problema:
 Identificação de presença da região (Experimento 1)
 Determinação do tipo da região (Experimento 2)
 intron-exon
 exon-intron

Técnicas:
 Árvores de Decisão (ADs)
 Redes Neurais Artificiais (RNAs)
 Máquinas de Vetores Suporte (SVMs)
André de Carvalho
70
Pré-processamento dos dados
LABIC

Heurística Tomek links: identificar
 Dados classificados incorretamente
5 - 6 % dados
 Borderlines
André de Carvalho
71
Resultados
LABIC

ADs:
 diminuição do tamanho das árvores induzidas
(10 - 33 %)

RNAs:
 menor tempo de treinamento (20 %)

SVMs:
 menor tempo de treinamento (7 - 15 %)
 menor número de vetores suporte (6 - 10 %)
André de Carvalho
72
LABIC
Erros obtidos (%)
Experimento 2
Experimento 1
Dados
Total
IE+EI
N
Total
IE
EI
Originais 4.4  0.6 1.9  0.6 6.7  0.9 4.3  1.5 5.3  2.3 3.3  2.8
A
D Pré-proc. 4.5  0.9 1.9  1.0 6.8  1.0 4.5  1.6 5.3  2.4 3.7  2.4
R
N
A
S
V
M
Originais
--
--
--
3.5  1.7 3.6  1.7 3.3  2.3
Pré-proc.
--
--
--
3.7  1.7 4.3  2.3 3.0  2.8
Originais 3.6  0.9 1.3  0.8 2.2  0.6 1.9  1.1 1.7  1.1 2.1  2.3
Pré-proc. 2.9  0.8 1.0  0.8 2.0  0.4 2.1  1.2 1.2  1.2 0.9  0.5
André de Carvalho
73
LABIC
Teste de Significância
• Significância com que Técnica 1 é melhor que Técnica 2
• Experimento 1:
Técnica 1
Técnica 2
Originais
Pré-processados
SVM
AD
95 %
95 %
• Experimento 2:
Técnica 1
Técnica 2
Originais
Pré-processados
RNA
AD
--
80 %
SVM
AD
95 %
95 %
SVM
RNA
95 %
95 %
André de Carvalho
74
Análise de expressão gênica
LABIC



Várias medidas foram testadas para a seleção de
genes
Para as várias medidas foram selecionados 50, 10
e 4 genes, sendo metade hipo e metade hiper
expressos
Para os casos 10 e 4 genes, os genes foram
selecionados dentre aqueles com expressão > 5
(apenas 84 genes)
André de Carvalho
75
Experimentos
LABIC

Os genes selecionados foram utilizados em um
algoritmo de Aprendizado de Máquina (AM)
 AM utilizado para classificar se uma amostra é de
tecido normal ou com tumor, a partir dos dados de
expressão desses genes
 Objetivo: verificar quais entre várias medidas para
seleção dos genes forneceu um conjunto de genes mais
apropriado para a distinção tumor/normal
André de Carvalho
76
Bibliotecas empregadas
LABIC

Normal







1 - SAGE_Brain_normal_cerebellum_B_1_FREQUENCY
2 - SAGE_Brain_normal_cerebellum_B_BB542_FREQUENCY
3 - SAGE_Brain_normal_cortex_B_BB542_FREQUENCY
4 - SAGE_Brain_normal_cortex_B_pool6_FREQUENCY
5 - SAGE_Brain_normal_peds_cortex_B_H1571_FREQUENCY
6 - SAGE_Brain_normal_thalamus_B_1_FREQUENCY
Tumor








André de Carvalho
7 - SAGE_Brain_astrocytoma_gradeIII_B_H1020_FREQUENCY
8 - SAGE_Brain_ependymoma_B_239_FREQUENCY
9 - SAGE_Brain_glioblastoma_B_GBM1062_FREQUENCY
10 - SAGE_Brain_glioblastoma_CL_H54+EGFRvIII_FREQUENCY
11 - SAGE_Brain_glioblastoma_CL_H54+LacZ_FREQUENCY
12 - SAGE_Brain_medulloblastoma_B_96-04-P019_FREQUENCY
13 - SAGE_Brain_medulloblastoma_B_98-04-P494_FREQUENCY
14 - SAGE_Brain_medulloblastoma_B_98-05-P608_FREQUENCY
77
LABIC
Resultados
Classificações incorretas
Medida
A
Fórmula
Se SomaT  SomaN
(Ratio)
B
SomaT
senão  SomaN
SomaN
SomaT
SomaT  SomaN
(Difference)
C
(Ratio)
D
Se MediaT  MediaN
MediaT  MediaN
(Difference)
E
F
(correlação de Pearson)
G
(Baseado em A e B)
H
(Baseado em C e D)
I
André de Carvalho
(Distância Euclidiana)
MediaT
MediaN
senão 
MediaN
MediaT
p( g , c) 
n
c g
i i
1 i
MediaT  MediaN
dpT  dpN
1
n
5Ratio  Difference
5  1
5Ratio  Difference
5  1
1 n
 ( g i  ci ) 2
n i 1
50 genes
10 genes
4 genes
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0

max¨(difference)  min(difference)
max¨(Ratio)  min(Ratio)
0
1
0

max¨(difference)  min(difference)
max¨(Ratio)  min(Ratio)
0
1
0
0
1
2
78
LABIC
Genes selecionados com as várias medidas
TAG
André
UNIGENE
No. de vezes que
foi selecionado
AAGTTGCTAT
78575
1
AGGCTACGGA
ATGTGAAGAG
ATTTGAGAAG
CACCTAATTG
CCACTGCACT
CCTGTAATCC
CTGGGTTAAT
GAGGGAGTTT
GGCAAGCCCC
GGCTGGGGGC
GGGCTGGGGT
GTGAAACCCC
GTGAAACCCT
GTGAAGGCAG
GTTGTGGTTA
TACCATCAAT
TACTAGTCCT
TAGGTTGTCT
TGCACGTTTT
TGCCTGCACC
TGGAGTGGAG
TGTACCTGTA
deTTGGGGTTTC
Carvalho
119122
111779
178658
334477
107003
138593
298262
76064
334895
75721
90436
372737
182476
77039
75415
169476
289088
279860
169793
135084
3764
334842
62954
6
1
9
9
6
6
5
8
2
3
2
6
1
3
1
1
8
1
3
3
2
2
1
Descrição
Prosaposin (variant Gaucher disease and variant metachromatic
leukodystrophy)
ribosomal protein L13a
secreted protein, acidic, cysteine-rich (osteonectin)
RAD23 homolog B (S. cerevisiae)
FLJ23277 protein
enhancer of invasion 10
5'-nucleotidase (purine), cytosolic type B
ribosomal protein S19
ribosomal protein L27a
ribosomal protein L10a
profilin 1
sperm associated antigen 7
hypothetical protein MGC3207
hypothetical protein PP1226
ribosomal protein S3A
beta-2-microglobulin
glyceraldehyde-3-phosphate dehydrogenase
heat shock 90kD protein 1, alpha
tumor protein, translationally-controlled 1
ribosomal protein L32
cystatin C (amyloid angiopathy and cerebral hemorrhage)
guanylate kinase 1
tubulin, alpha, ubiquitous
ferritin, heavy polypeptide 1
79