Utilizando Inteligência Artificial em Bioinformática

1André de Carvalho

LABIC

Utilizando Inteligência Artificial em

Bioinformática

Prof. André de CarvalhoLABIC - Universidade de São Paulo

2André de Carvalho

LABIC Principais tópicos

Introdução Bioinformática Biologia Molecular Reconhecimento de Genes Utilizando Inteligência Artificial Conclusão

3André de Carvalho

LABIC IA e Bioinformática

BIOLOGIA

Redes Neurais, Algorítmos genéticos

COMPUTAÇÃO

Bioinformática

4André de Carvalho

LABIC Definições

Bioinformática Pesquisa e desenvolvimento de ferramentas

computacionais, matemáticas e estatísticas para a resolução de problemas da BiologiaBiologia molecular

A Computação está para a Biologia da mesmaforma que a Matemática está para a Física.

Harold Morowitz

5André de Carvalho

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 áreasMedicina - Farmácia - Agricultura

6André de Carvalho

LABIC Crescimento do GenBank

0

2000000

4000000

6000000

8000000

10000000

12000000

1990 1992 1994 1996 1998 2000

Ano

Número de sequências armazenadas no banco de dados GenBank

7André de Carvalho

LABIC Andamento de projetos genoma

73 genomas completos publicados Humano Camundongo Drosophila Arabidopsis Levedura

212 de procariotos em andamento 157 de eucariotos em andamento

8André de Carvalho

LABIC Fração do genoma da levedura

CCACACCACACCCACACACCCACACACCACACCACACACCACACCACACCCACACACACACATCCTAACACTACCCTAACACAGCCCTAATCTAACCCTGGCCAACCTGTCTCTCAACTTACCCTCCATTACCCTGCCTCCACTCGTTACCCTGTCCCATTCAACCATACCACTCCGAACCACCATCCATCCCTCTACTTACTACCACTCACCCACCGTTACCCTCCAATTACCCATATCCAACCCACTGCCACTTACCCTACCATTACCCTACCATCCACCATGACCTACTCACCATACTGTTCTTCTACCCACCATATTGAAACGCTAACAAATGATCGTAAATAACACACACGTGCTTACCCTACCACTTTATACCACCACCACATGCCATACTCACCCTCACTTGTATACTGATTTTACGTACGCACACGGATGCTACAGTATATACCATCTCAAACTTACCCTACTCTCAGATTCCACTTCACTCCATGGCCCATCTCTCACTGAATCAGTACCAAATGCACTCACATCATTATGCACGGCACTTGCCTCAGCGGTCTATACCCTGTGCCATTTACCCATAACGCCCATCATTATCCACATTTTGATATCTATATCTCATTCGGCGGTCCCAAATATTGTATAACTGCCCTTAATACATACGTTATACCACTTTTGCACCATATACTTACCACTCCATTTATATACACTTATGTCAATATTACAGAAAAATCCCCACAAAAATCACCTAAACATAAAAATATTCTACTTTTCAACAATAATACATAAACATATTGGCTTGTGGTAGCAACACTATCATGGTATCACTAACGTAAAAGTTCCTCAATATTGCAATTTGCTTGAACGGATGCTATTTCAGAATATTTCGTACTTACACAGGCCATACATTAGAATAATATGTCACATCACTGTCGTAACACTCTTTATTCACCGAGCAATAATACGGTAGTGGCTCAAACTCATGCGGGTGCTATGATACAATTATATCTTATTTCCATTCCCATATGCTAACCGCAATATCCTAAAAGCATAACTGATGCATCTTTAATCTTGTATGTGACACTACTCATACGAAGGGACTATATCTAGTCAAGACGATACTGTGATAGGTACGTTATTTAATAGGATCTATAACGAAATGTCAAATAATTTTACGGTAATATAACTTATCAGCGGCGTATACTAAAACGGACGTTACGATATTGTCTCACTTCATCTTACCACCCTCTATCTTATTGCTGATAGAACACTAACCCCTCAGCTTTATTTCTAGTTACAGTTACACAAAAAACTATGCCAACCCAGAAATCTTGATATTTTACGTGTCAAAAAATGAGGGTCTCTAAATGAGAGTTTGGTACCATGACTTGTAACTCGCACTGCCCTGATCTGCAATCTTGTTCTTAGAAGTGACGCATATTCTATACGGCCCGACGCGACGCGCCAAAAAATGAAAAACGAAGCAGCGACTCATTTTTATTTAAGGACAAAGGTTGCGAAGCCGCACATTTCCAATTTCATTGTTGTTTATTGGACATACACTGTTAGCTTTATTACCGTCCACGTTTTTTCTACAATAGTGTAGAAGTTTCTTTCTTATGTTCATCGTATTCATAAAATGCTTCACGAACACCGTCATTGATCAAATAGGTCTATAATATTAATATACATTTATATAATCTACGGTATTTATATCATCAAAAAAAAGTAGTTTTTTTATTTTATTTTGTTCGTTAATTTTCAATTTCTATGGAAACCCGTTCGTAAAATTGGCGTTTGTCTCTAGTTTGCGATAGTGTAGATACCGTCCTTGGATAGAGCACTGGAGATGGCTGGCTTTAATCTGCTGGAGTACCATGGAACACCGGTGATCATTCTGGTCACTTGGTCTGGAGCAATACCGGTCAACATGGTGGTGAAGTCACCGTAGTTGAAAACGGCTTCAGCAACTTCGACTGGGTAGGTTTCAGTTGGGTGGGCGGCTTGGAACATGTAGTATTGGGCTAAGTGAGCTCTGATATCAGAGACGTAGACACCCAATTCCACCAAGTTGACTCTTTCGTCAGATTGAGCTAGAGTGGTGGTTGCAGAAGCAGTAGCAGCGATGGCAGCGACACCAGCGGCGATTGAAGTTAATTTGACCATTGTATTTGTTTTGTTTGTTAGTGCTGATATAAGCTTAACAGGAAAGGAAAGAATAAAGACATATTCTCAAAGGCATATAGTTGAAGCAGCTCTATTTATACCCATTCCCTCATGGGTTGTTGCTATTTAAACGATCGCTGACTGGCACCAGTTCCTCATCAAATATTCTCTATATCTCATCTTTCACACAATCTCATTATCTCTATGGAGATGCTCTTGTTTCTGAACGAATCATAAATCTTTCATAGGTTTCGTATGTGGAGTACTGTTTTATGGCGCTTATGTGTATTCGTATGCGCAGAATGTGGGAATGCCAATTATAGGGGTGCCGAGGTGCCTTATAAAACCCTTTTCTGTGCCTGTGACATTTCCTTTTTCGGTCAAAAAGAATATCCGAATTTTAGATTTGGACCCTCGTACAGAAGCTTATTGTCTAAGCCTGAATTCAGTCTGCTTTAAACGGCTTCCGCGGAGGAAATATTTCCATCTCTTGAATTCGTACAACATTAAACGTGTGTTGGGAGTCGTATACTGTTAGGGTCTGTAAACTTGTGAACTCTCGGCAAATGCCTTGGTGCAATTACGTAATTTTAGCCGCTGAGAAGCGGATGGTAATGAGACAAGTTGATATCAAACAGATACATATTTAAAAGAGGGTACCGCTAATTTAGCAGGGCAGTATTATTGTAGTTTGATATGTACGGCTAACTGAACCTAAGTAGGGATATGAGAGTAAGAACGTTCGGCTACTCTTCTTTCTAAGTGGGATTTTTCTTAATCCTTGGATTCTTAAAAGGTTATTAAAGTTCCGCACAAAGAACGCTTGGAAATCGCATTCATCAAAGAACAACTCTTCGTTTTCCAAACAATCTTCCCGAAAAAGTAGCCGTTCATTTCCCTTCCGATTTCATTCCTAGACTGCCAAATTTTTCTTGCTCATTTATAATGATTGATAAGAATTGTATTTGTGTCCCATTCTCGTAGATAAAATTCTTGGATGTTAAAAAATTATTATTTTCTTCATAAAGAAGCTTTCAAGATATAAGATACGAAATAGGGGTTGATAATTGCATGACAGTAGCTTTAGATCAAAAAGGAAAGCATGGAGGGAAACAGTAAACAGTGAAAATTCTCTTGAGAACCAAAGTAAACCTTCATTGAAGAGCTTCCTTAAAAAATTTAGAATCTCCCATGTCAACGGGTTTCCATACCTCCCCAGCATCATACATCTTTTTTCAAAGAAACTTCAAATGCCTCTTTTATGCAAGGGGCAAAATCCTGAAATGACTTAAACTTAGCAGTTTCGTCTTTTTTCAAAGAGAATGGTTGAAGAAGAATTGTTTTGGACGCTTATTGACAATCTGTTGCATTGATAAAGTACCTACTATCCCAGACTATATTTGTATACAAGTACAAAATTAGGTTTGTTGAAACAACTTTCCGATCATTGGTGCCCGTATCTGATGTTTTTTTAGTAATTTCTTTGTAAATACAGGGAGTTGTTTCGAAAGCTTATGAGAAAAATACATGAATGACAGGTAAAAATATTGGCTCGAAAAAGAGGACAAAAAGAGAAATCATAAATGAGTAAACCCACTTGCTGGACATTATCCAGTAAAGGCTTGGTAGTAACCATAATATTACCCAGGTACGAAACGCTAAGAACCTTGAAAGACTCATAAAACTTCCAGGTTAAGCTATTTTTGAAAATATTCTGAGGTAAAAGCCATTAAGGTCCAGATAACCAAGGGACAATAAACCTATGCTTTTCTTGTCTTCAATTTCAGTATCTTTCCATTTTGATAATGAGCATGTGATCCGGAAAGCTACTTTATGATGTTTCAAGGCCTGAAGTTTGAATATTTATGTAGTTCAACATCAAATGTGTCTATTTTGTGATGAGGCAACCGTCGACAACCTTATTATCGAAAAAGAACAACAAGTTCACATGCTTGTTACTCTCTATAACTAGAGAGTACTTTTTTTGGAAGCAAGTAAGAATAAGTCAATTTCTACTTACCTCATTAGGGAAAAATTTAATAGCAGTTGTTATAACGACAAATACAGGCCCTAAAAAATTCACTGTATTCAATGGTCTACGAATCGTCAATCGCTTGCGGTTATGGCACGAAGAACAATGCAATAGCTCTTACAAGCCACTACATGACAAGCAACTCATAATTTAA

9André de Carvalho

LABIC Bioinformática

Ê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

10André de Carvalho

LABIC Bioinformática

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õesNa medição dos valores ou definição das classes

Inteligência Artificial fornecem técnicas eficientes para lidar com problemas deste tipo

11André de Carvalho

LABIC Biologia Molecular

Estudo das células e moléculas Em particular: genoma dos organismos

Estruturas principais: Genes Cromossomos DNA RNA Proteínas

nucleotídeos

aminoácidos

Expressão

Gênica

12André de Carvalho

LABIC Biologia Molecular

Dogma central da Biologia Molecular Transferência de Informação

Transcrição

Tradução

DNA

RNA

Proteínas

Replicação

13André de Carvalho

LABIC Biologia Molecular

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

14André de Carvalho

LABIC Biologia Molecular

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

15André de Carvalho

LABIC Biologia Molecular

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

16André de Carvalho

LABIC Biologia Molecular

Proteínas Definem estrutura, função e mecanismos

regulatórios das célulasExemplos de mecanismos regulatórios: controle do

ciclo celular, transcrição gênica

Seqüências linearesCombinações de 20 aminoácidos diferentesTrês nucleotídeos (codon) formam um aminoácido

17André de Carvalho

LABIC Biologia Molecular

18André de Carvalho

LABIC Biologia Molecular

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)

19André de Carvalho

LABIC Processo de expressão gênica

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)

20André de Carvalho

LABIC Processo de expressão gênica

Transcrição depende do organismo Organismos eucariotos

Cada gene é transcrito independentementeExiste um promotor antes de todo gene

Organismos procariotosVários genes consecutivos podem ser transcritos em

uma única molécula de RNANão existe necessariamente um promotor antes de

cada gene

21André de Carvalho

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

22André de Carvalho

LABIC Processo de expressão gênica

G C A G C T C C G G A C T C C A T . . . RNA Polimerase

promotor Transcrição

DNA

mRNA

A

T

23André de Carvalho

LABIC Processo de expressão gênica

T G C A G C T C C G G A C T C C A T . . . RNA Polimerase

promotor Transcrição

A C G U C G A G G C C U G A G G U A . . .

DNA

mRNA

24André de Carvalho

LABIC Processo de expressão gênica

T G C A G C T C C G G A C T C C A T . . . RNA Polimerase

promotor Transcrição

A C G U C G A G G C C U G A G G U A . . .

DNA

mRNA

Tradução

Thr

Ribossomo

A C G

25André de Carvalho

LABIC Processo de expressão gênica

T G C A G C T C C G G A C T C C A T . . . RNA Polimerase

promotor Transcrição

A C G U C G A G G C C U G A G G U A . . .

DNA

mRNA

Tradução RibossomoHis

LeuGlySer

Ser

Cys

26André de Carvalho

LABIC Processo de expressão gênica

Estrutura de leitura Para uma dada faixa de DNA, nucleotídeos podem

ser agrupados em triplas de três formas diferentesUm dos nucleotídeos pode ocupar a 1a, 2a ou 3a

posição em um codonApenas um destes três possíveis agrupamentos é

realmente lido pelo ribossomoO agrupamento lido é chamado de estrutura de

leitura do gene

A T T A C G A A G

27André de Carvalho

LABIC Processo de expressão gênica

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

28André de Carvalho

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 intronsDoadoras: bordas exon-intronAceptoras: bordas intron-exon

29André de Carvalho

LABIC Splice-junctions

mRNA

intronexon

Splicing

DNA

Transcrição

mRNA

doador aceptor

30André de Carvalho

LABIC Biologia Molecular e IA

Problemas da Biologia Molecular que podem ser tratados por IA 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

31André de Carvalho

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

32André de Carvalho

LABIC Reconhecimento de genes

Duas abordagens principais têm sido seguidas:

Busca por sinal

Busca por conteúdo

33André de Carvalho

LABIC Reconhecimento de genes

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)

34André de Carvalho

LABIC Reconhecimento de genes

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

35André de Carvalho

LABIC Busca por sinal

É 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 expressosTaxa com a qual a expressão ocorre

36André de Carvalho

LABIC Busca por sinal

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 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)

37André de Carvalho

LABIC Busca por sinal

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

38André de Carvalho

LABIC Busca por sinal

Promotor na posição 3?

Classificador

Posição 1 = ‘C’Posição 2 = ‘T’Posição 3 = ‘T’Posição 4 = ‘A’Posição 5 = ‘C’Posição 6 = ‘G’

Representação das características

Seqüência de DNA ... A T C G T G C T T A C G C G T C C A1 2 3 4 5 6

39André de Carvalho

LABIC Reconhecimento de início da tradução

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

40André de Carvalho

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

41André de Carvalho

LABIC Busca pelo conteúdo

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

42André de Carvalho

LABIC Busca pelo conteúdo

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

43André de Carvalho

LABIC Busca pelo conteúdo

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

44André de Carvalho

LABIC Reconhecimento de genes

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

45André de Carvalho

LABIC Redes Neurais Artificiais

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

46André de Carvalho

LABIC Redes Neurais Artificiais

camada de entrada

camadas intermediárias

camada de saída

conexões

47André de Carvalho

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 T C G T G C T T A C G C G C G T ...

A C G T A C G T A C G T

48André de Carvalho

LABIC

Reconhecimento de regiões de splicingRampone (1998)

Reconhecimento de promotoresMa e Wang (1999)

Bajic et al. (2002)

Previsão de estrutura de proteínasRiis et al (1995)

Polyac et al (1992)

Servidor GRAIL - identificação de genesUberbacher et al (1993)

Sítios de início de transcriçãoTowell et al (1990)

Problema abordadoTrabalho

Redes Neurais Artificiais

49André de Carvalho

LABICAlgoritmos 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

50André de Carvalho

LABICAlgoritmos Genéticos

População atual

Reprodução

Avaliação

Seleção

População inicial População final

51André de Carvalho

LABIC Algoritmos Genéticos

Alinhamento de seqüências: Uma a uma Uma com várias Identificar:

InserçõesRemoçõesSubstituições

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

52André de Carvalho

LABIC Algoritmos Genéticos

Alinhamento de sequênciasZhang e Wong (1997)

Previsão de estrutura de proteínas

Alander (1995)

Krasnogor et al. (1999)

Problema abordadoTrabalho

53André de Carvalho

LABIC Raciocínio Baseado em Casos

Resolve novos problemas adaptando soluções de problemas anteriores semelhantes

Nova solução

Novo problema1

2Solução

Problema

Solução

Problema

54André de Carvalho

LABIC Raciocínio Baseado em Casos

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

55André de Carvalho

LABIC Raciocínio Baseado em Casos

Ciclo de um sistema de RBC

(Aamodt, 1993)

56André de Carvalho

LABIC Raciocínio Baseado em Casos

Alinhamento de seqüênciasHarris et al. (1993)

Reconhecimento de genesShavlik (1990, 1991)

Problema abordadoTrabalho

57André de Carvalho

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

58André de Carvalho

LABIC Classificadores de Margens Largas

Máquinas de Vetores Suporte Encontra um hiperplano ótimo que separa classes em um

espaço abstrato

margem

Classe 1Classe 2

59André de Carvalho

LABIC Classificadores de Margens Largas

Análise de expressão gênica

ExpressãoTecido normal Tecido com tumor

Gene T1 T2 T3 T1 T2 T3 1 128 100 30 20 10 9 2 20 10 18 104 210 47 3 29 130 7 37 310 40 4 21 12 15 92 123 84

60André de Carvalho

LABIC Classificadores de Margens Largas

Promotores, reg. codificadorasAB, RNsJackson (1995)

DNA microarraySVMs, ADsBrown et al. (1999)

Subfamílias proteínasSVMsKarchin et al. (2002)

Especificidade proteínasADs, ABHuss et al. (2001)

Bem-Hur et al. (2000)

Furey et al. (2001)

Zien et al. (2000)

Ding e Dubchak (2001)

Trabalho

DNA microarraySVMs, AB, clusterização

DNA microarraySVMs

Sítios de início de traduçãoSVMs

Estrutura proteínasSVMs, RNs

Problema abordadoTécnicas

61André de Carvalho

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

sorrisorri

segurasegura inimigoinimigo

nãosim

inimigoinimigo amigoamigo

espada balão oubandeira

62André de Carvalho

LABIC Árvores de Decisão

Lapedes et al (1989): detecção de regiões de splicing (regiões doadoras) Entrada: cadeia de nucleotídeos

PositivoPositivo

Posição 8 = ?Posição 8 = ?

Posição 3 = ?Posição 3 = ? NegativoNegativo Posição 9 = ?Posição 9 = ?

A C G T

A C G T

NegativoNegativo NegativoNegativo NegativoNegativoNegativoNegativoPositivoPositivo PositivoPositivo

A C G T

NegativoNegativo

63André de Carvalho

LABICOutras técnicas

Eddy (1998)Detecção de genesCadeias de Markov

Guan et al (1994)Estrutura de proteínas

RNAs, AGs e k-NN

Dond e Searls (1994)

Previsão da estrutura de genes

Lingüística computacional

Friedman et al (2000)

Detecção de genesRedes Baysianas

TrabalhoProblemaTécnica

64André de Carvalho

LABIC Projeto Fapesp Genoma Clínico

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

65André de Carvalho

LABIC Projeto CNPq - Bioinformática

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ídosSeleção de atributos

CNPq e FAPESP

66André de Carvalho

LABICProjeto CNPq - Bioinformática

Melhoramento genético Utiliza marcadores moleculares para avaliar

potencial genético10 marcadores (2 já foram avaliados)

Identificação de cruzamentos mais promissoresPrevisão de ganho de peso entre nascimento e

desmama

Utiliza SVMs e RNs CNPq e Embrapa

67André de Carvalho

LABIC Referências de IA e Bioinformática

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

68André de Carvalho

LABIC Conclusão

Introdução Bioinformática Biologia Molecular Reconhecimento de Genes Utilização de IA em Bioinformática

69André de Carvalho

LABIC Agradecimentos

Ana Carolina Lorena Cláudia Regina Milaré Humberto de Sousa Silvia Gorla Modonese da Silva Alexandre Delbem Katti Faceli Welington Martins

70André de Carvalho

LABIC Reconhecimento de regiões de splicing

DadosDados: regiões de splicing de primatas (UCI) Divisão do problemaDivisã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)

71André de Carvalho

LABIC Pré-processamento dos dados

Heurística Tomek linksHeurística Tomek links: identificar Dados classificados incorretamente Borderlines 5 - 6 % dados

72André de Carvalho

LABIC Resultados

ADs:ADs: diminuição do tamanho das árvores induzidas

(10 - 33 %) RNAs:RNAs:

menor tempo de treinamento (20 %) SVMs:SVMs:

menor tempo de treinamento (7 - 15 %) menor número de vetores suporte (6 - 10 %)

73André de Carvalho

LABIC

Experimento 2

Erros obtidos (%)

3.7 2.45.3 2.44.5 1.66.8 1.01.9 1.0 4.5 0.9Pré-proc.

3.3 2.85.3 2.34.3 1.56.7 0.91.9 0.6 4.4 0.6Originais

EIIETotalNIE+EITotalDados

3.0 2.84.3 2.33.7 1.7---- --Pré-proc.

3.3 2.33.6 1.73.5 1.7---- --Originais

0.9 0.51.2 1.22.1 1.22.0 0.41.0 0.8 2.9 0.8Pré-proc.

2.1 2.31.7 1.11.9 1.12.2 0.61.3 0.8 3.6 0.9Originais

Experimento 1

AD

RNA

SVM

74André de Carvalho

LABIC Teste de Significância

95 %95 %ADSVM

Pré-processadosOriginaisTécnica 2Técnica 1

80 %--ADRNA

95 %95 %ADSVM

95 %95 %RNASVM

Pré-processadosOriginaisTécnica 2Técnica 1

• Significância com que Técnica 1 é melhor que Técnica 2• Experimento 1:

• Experimento 2:

75André de Carvalho

LABIC Análise de expressão gênica

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)

76André de Carvalho

LABIC Experimentos

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

77André de Carvalho

LABIC Bibliotecas empregadas

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 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

78André de Carvalho

LABIC Resultados

Classificações incorretasFórmula

4 genes10 genes50 genesMedida

010B(Difference)

000A(Ratio)

010D(Difference)

000E

010F (correlação de Pearson)

210I(Distância Euclidiana)

010H(Baseado em C e D)

010G (Baseado em A e B)

000C(Ratio)

n

iii cg

n 1

2)(1

n

iiicg

n 1

1

15

5

DifferenceRatio

15

5

DifferenceRatio)min()max¨(

)min()max¨(

RatioRatio

differencedifference

dpNdpT

MediaNMediaTcgp

),(

MediaNMediaT

SomaNSomaT

SomaNSomaT

Se MediaNMediaT MediaN

MediaT

MediaT

MediaN

Se

senão

SomaN

SomaT

SomaT

SomaNsenão

)min()max¨(

)min()max¨(

RatioRatio

differencedifference

79André de Carvalho

LABIC Genes selecionados com as várias medidas

TAG UNIGENENo. de vezes que

foi selecionadoDescrição

AAGTTGCTAT 78575 1Prosaposin (variant Gaucher disease and variant metachromatic leukodystrophy)

AGGCTACGGA 119122 6 ribosomal protein L13a

ATGTGAAGAG 111779 1 secreted protein, acidic, cysteine-rich (osteonectin)

ATTTGAGAAG 178658 9 RAD23 homolog B (S. cerevisiae)

CACCTAATTG 334477 9 FLJ23277 protein

CCACTGCACT 107003 6 enhancer of invasion 10

CCTGTAATCC 138593 6 5'-nucleotidase (purine), cytosolic type B

CTGGGTTAAT 298262 5 ribosomal protein S19

GAGGGAGTTT 76064 8 ribosomal protein L27a

GGCAAGCCCC 334895 2 ribosomal protein L10a

GGCTGGGGGC 75721 3 profilin 1

GGGCTGGGGT 90436 2 sperm associated antigen 7

GTGAAACCCC 372737 6 hypothetical protein MGC3207

GTGAAACCCT 182476 1 hypothetical protein PP1226

GTGAAGGCAG 77039 3 ribosomal protein S3A

GTTGTGGTTA 75415 1 beta-2-microglobulin

TACCATCAAT 169476 1 glyceraldehyde-3-phosphate dehydrogenase

TACTAGTCCT 289088 8 heat shock 90kD protein 1, alpha

TAGGTTGTCT 279860 1 tumor protein, translationally-controlled 1

TGCACGTTTT 169793 3 ribosomal protein L32

TGCCTGCACC 135084 3 cystatin C (amyloid angiopathy and cerebral hemorrhage)

TGGAGTGGAG 3764 2 guanylate kinase 1

TGTACCTGTA 334842 2 tubulin, alpha, ubiquitous

TTGGGGTTTC 62954 1 ferritin, heavy polypeptide 1