Reconhecimento de Genes
Marcílio C. P. de Souto
DIMAp/UFRN
Reconhecimento de genes (1/2)

Análise em laboratório: difícil e cara


Alternativa: uso de técnicas computacionais
Variação, complexidade e natureza ainda
desconhecida dos genes

Dificuldade de codificar algoritmos específicos
Aprendizado de Máquina: gera
descrições próprias dos conceitos genéticos
Reconhecimento de genes (2/2)

Abordagens para localização de genes:

Busca por sinal: localiza indiretamente, por sinais
associados à expressão gênica



Promotores
Sítios de início de tradução
Busca por conteúdo: identifica segmentos do DNA
com propriedades (padrões) de regiões codificadoras
Busca por Sinal (1/4)

Localiza sinais associados à presença de genes

Mais próximo do modo biológico

Muitos sinais realizam funções regulatórias

Ex.: velocidade de Expressão
Busca por Sinal (2/4)

Alternativas:

Achar seqüência consenso


Matriz de Posições Ponderadas



Muito simples
Modelo para o sinal
Dependência estatística entre nucleotídeos vizinhos
Classificação

Aprendizado de Máquina
Busca por Sinal (3/4)
Sinal na posição 3?

Classificação: dada
janela de tamanho fixo,
determinar se há sinal
em uma posição
particular

Tamanho da janela

Instâncias alinhadas
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
...ATCCTTACGCGTA...
...ATCCTTACGCGTA...
janela
Busca por Sinal (4/4)

Problemas:

Identificação de sítios de início de tradução

Identificação de promotores

Identificação de sítios de splicing
Busca por Sinal – Splicing (1/8)
Identificação de sítios de splicing
Dado: conjunto de seqüências de DNA de tamanho
fixo
Faça: gerar classificador para identificar se uma
janela possui uma fronteira intron-exon,
exon-intron, ou nenhuma delas
Busca por Sinal – Splicing (2/8)

Eucariotos

Nomenclatura bordas:



Exon/intron: doadoras (GT)
Intron/exon: receptoras (AG)
Importância: necessário demarcar precisamente
segmentos de DNA traduzidos
Busca por Sinal – Splicing (3/8)


Lapedes et al. (1989): ADs, RNs e kNN
Janelas: 11, 21 e 41
Entrada: Cadeia de nucleotídeos
Regiões Doadoras
Posição 8 = ?
C
A
Posição 3 = ?
A
Negativo
C
Negativo
G
Positivo
G
Negativo
Posição 9 = ?
A
T
Positivo
T
Negativo
C
Positivo
G
Negativo
T
Negativo
Busca por Sinal – Splicing (4/8)
Lapedes et al. (1989)

Instâncias alinhadas segundo AG/GT



Inclusive negativas
RNs melhor: 91% precisão receptoras e 95%
doadoras
ADs: regras interpretáveis biologicamente
Busca por Sinal – Splicing (5/8)

Para RNs (e também SVMs): necessária conversão dos
nucleotídeos para valores numéricos

Converter cada símbolo para valores entre 0 e 1


A = 0, B = 0.33, C = 0.66 e T = 1.0
Favorece algumas substituições de bases




Algumas bases podem ser interpretadas como mais próximas
Não é biologicamente comprovado
Não é claro
Codificação ortogonal


A = 0001, C = 0010, G = 0100 e T = 1000
Considera distâncias entre bases iguais

Abordagem empregada usualmente
Busca por Sinal – Splicing (6/8)

Rampone (1998): abordagem híbrida envolvendo
o uso de regras e de uma RN




Algoritmo BRAIN (Batch Relevance-based Artificial
INtelligence)
Infere fórmulas Booleanas dos exemplos (regras
disjuntivas)
Regras são refinadas por uma RN
Combinadas com um procedimento discriminante
estatístico
Busca por Sinal – Splicing (7/8)
Rampone (1998)

Comparou seus resultados aos do projeto StatLog






RN do tipo RBF (Radial Basis Function)
Classificador Bayesiano
RN do tipo MLP
Algoritmo C4.5, indutor de ADs
Algoritmo k-NN
Verificou de forma geral maior acurácia dos
modelos baseados em RNs
Busca por Sinal – Splicing (8/8)

Lorena et al. (2002): SVMs e ADs


Melhores resultados obtidos pelas SVMs (95%
confidência)
Pré-processamento visando eliminar ruídos



Levou a simplificações nos modelos induzidos
SVMs: em alguns casos houve também melhora de
desempenho
ADs: diminuições no tamanho das árvores induzidas  ganhos
em termos de compreensibilidade
Busca por Sinal – SITs (1/6)
Identificação de sítios de início de tradução
Dado: conjunto de seqüências de DNA (ou mRNA)
de tamanho fixo
Faça: gerar classificador para identificar sítios de
início de tradução (SITs) em uma janela
Busca por Sinal – SITs (2/6)

Tradução não se inicia com primeira tripla de
nucleotídeos do mRNA



Geralmente códon AUG (metionina)
Procariotos: precedendo códon inicial  seqüências
Shine–Dalgarno
Stormo et al. (1982): RN Perceptron (SITs de E.
coli)

Gerar MPP
Busca por Sinal – SITs (3/6)


Stormo et al. (1982)
Janelas: 51, 71, 101 (melhor)
Codificação canônica
...
...
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 C C A ...
Busca por Sinal - SITs (4/6)
Stormo et al. (1982)




MPP obtida foi mais precisa que diversos métodos
de consenso
Pesos mais significativos corresponderam àqueles
conectados ao SIT e à região Shine-Dalgarno
Deficiência: Perceptron  padrões linearmente
separáveis
Futschik et al. (1999): redes multicamadas
Busca por Sinal – SITs (5/6)


Zien et al. (2000): SVMs no reconhecimento de
SITs de vertebrados
Desempenho comparado ao de RNs e a um
método Markoviano

Janelas de mRNA de 200 nucleotídeos

Codificação canônica (cinco bits)
Busca por Sinal – SITs (6/6)
Zien et al. (2000)

Desempenho melhor das SVMs

Informações a priori



Privilegiar correlações locais entre nucleotídeos
Melhorou resultados
Reformulação da função Kernel considerando
informações providas pela técnica estatística

Melhores resultados na aplicação
Busca por Sinal – Promotores (1/8)
Identificação de promotores
Dado: conjunto de seqüências de DNA de tamanho
fixo
Faça: gerar classificador para identificar promotores em uma janela
Busca por Sinal – Promotores (2/8)


Transcrição se inicia com RNA polimerase se ligando ao
promotor
Towell et al. (1990): KBANN  RNAs + regras
simbólicas em promotores de E. coli
Promotor procarioto
-35
-10
gene
TTGACA
TAATTA
TAC
RNA polimerase
+1 RNAm
Busca por Sinal – Promotores (3/8)
Towell et al. (1990)

Regras proposicionais para inicializar topologia e
pesos de uma RN



Janela: 57 nucleotídeos


Identificavam TATAbox, TTGACA e regiões controversas
Regras falharam no reconhecimento de instâncias com
promotores
Promotor alinhado sete nucleotídeos à direita da janela
Codificação canônica (quatro bits)
Busca por Sinal – Promotores (4/8)
Towell et al. (1990)

Redução no tempo de treinamento das RNs

Melhora na generalização das redes

RNs aprenderam a descartar as regras que correspondiam
a regiões controversas

Indicação que não correspondiam a características relevantes
Busca por Sinal – Promotores (5/8)
Towell et al. (1990)

Resultados obtidos foram comparados





RNs se sobressaíram em relação à técnica biológica


Rede MLP
AD induzida pelo algoritmo ID3
Algoritmo k-vizinhos mais próximos
Técnica referenciada na literatura biológica
Eficácia de técnicas de AM
Algoritmos k-NN e ID3 foram inferiores  pode ser
conseqüência da dificuldade em lidar com muitos atributos
Busca por Sinal – Promotores (6/8)

Reese e Eeckman (1995): combinação de RNs no
reconhecimento de promotores vertebrados

Identificação de promotores eucariotos pode ser considerada mais
custosa e complexa
Promotor eucarioto
URS
+
UAS
TATA
Holoenzima Pol II
gene
IRN ATG
RNAm
Busca por Sinal – Promotores (7/8)
Reese e Eeckman. (1995)



RNs individuais para a identificação de duas
regiões

TATA-box

Cadeia denominada Iniciadora (IRN)
RNs foram treinadas com um procedimento de
poda de conexões
Na combinação das RNs  rede do tipo Time
Delay Neural Network (TDNN)
Busca por Sinal – Promotores (8/8)
Reese e Eeckman. (1995)


Janela de 51 nucleotídeos
Resultados das TDNNs foram comparados aos das
RNs individuais


RNs se mostraram pouco acuradas individualmente
Combinação pela TDNNs gerou ganhos significativos


Acurácia
Redução da taxa de falsos positivos
Busca por Conteúdo (1/3)


Reconhece genes por padrões gerais que ocorrem
em regiões codificadoras
Objetivo: identificar regiões traduzidas em proteínas
(janela fixa)


Procariotos: distinguir genes das regiões não-codificadoras entre
eles
Eucariotos: também distinguir introns de exons
Busca por Conteúdo (2/3)

Questões:


Que regiões são codificadoras
Qual fase de leitura codifica proteína  Open Reading
Frame (ORF)

Como agrupar nucleotídeos consecutivos em triplas
... A T G C C T A A T ...
Met.
Pro.
Asp.
... A T G C C T A A T ...
Cis.
Leu.
... A T G C C T A A T ...
Ala. Parada
Busca por Conteúdo (3/3)

Propriedades que podem ser exploradas:

Alguns aminoácidos são mais usados

Preferência de códon de um organismo

Alguns aminoácidos têm maior ‘afinidade’
Regiões codificadoras (1/8)
Identificação de regiões codificadoras
Dado: conjunto de seqüências de DNA de tamanho fixo
Faça: gerar classificador para identificar se uma
janela é codificadora ou não
Se for codificadora, identificar sua ORF
Regiões codificadoras (2/8)

Farber et al. (1992): Perceptron com ativação
Sigmoidal para distinguir introns de exons


64 entradas: freqüência de cada codon
Janelas de 5 a 90 codons


Maiores levaram em geral a melhores predições
4096 entradas: freqüência de cada dicodon

Melhores resultados
Regiões codificadoras (3/8)
Farber et al. (1992)

Resultados comparados a um classificador
Bayesiano baseado em preferências de códons


Maior precisão das RNs
Resultado atribuído ao fato do classificador Bayesiano
assumir independência entre códons vizinhos
Regiões codificadoras (4/8)
Farber et al. (1992)

Representação por dicódons melhorou a
generalização




Desempenho com o uso da representação de apenas
um códon foi inferior mesmo adicionando à rede uma
camada intermediária
Habilidade de um sistema de aprendizado é dependente
da representação dos atributos
Craven e Shavlik (1993b): resultados e discussões
semelhantes
Verificação das ORFs após identificação dos exons
Regiões codificadoras (5/8)

Uberbacher e Mural (1991): reconhecimento
exons e introns


Módulo do servidor GRAIL
Atributos de entrada: calculados por algoritmos que
avaliam 7 diferentes características da seqüência





Freqüência que cada nucleotídeo ocupa cada posição
Preferências em tuplas de seis nucleotídeos
RN  combinacão das informações (pesos)
Janelas de 99 nucleotídeos
19 genes humanos: 90 % de precisão
Regiões codificadoras (6/8)

Craven e Shavlik (1993a): previsão de ORFs em bactérias
E. coli



Grande parte de seu genoma é codificante
Resultados comparados a métodos Bayesianos baseados
em preferências de códons
RN treinada de forma a predizer a posição do códon que o
nucleotídeo no centro da seqüência ocupa

Seis saídas:


Posições 1, 2 e 3 na fita submetida
Posições 4, 5 e 6 para a fita complementar
Regiões codificadoras (7/8)
Craven e Shavlik. (1993a)

Diferentes formas de codificação para as entradas





Nucleotídeos na forma canônica
Contagem de freqüência de códons na janela
Medidas similares às de Uberbacher e Mural (1991),
adaptadas para organismos procariotos
Combinação das probabilidades providas pelo método
Bayesiano com as medidas adaptadas
Janelas 61 nucleotídeos
Regiões codificadoras (8/8)
Craven e Shavlik. (1993a)


Resultados: porcentagem de janelas para as quais
gerou-se uma ORF correta
Maior poder preditivo das abordagens envolvendo
manipulações nos atributos

Confirma que a representação das entradas da RN tem
papel crucial no desempenho
Combinação de Métodos (1/9)


Sistemas de identificação de genes não se
baseiam em buscas de sinais ou de conteúdo
exclusivamente
Abordagens mais promissoras: combinação das
duas estratégias de busca



GRAIL II
GeneID
GeneParser2
Combinação de Métodos (2/9)

Alguns sistemas também utilizam buscas por
similiridade para confirmar suas previsões



GeneID+
GeneParser3
Estruturas gênicas identificadas são:



Traduzidas em cadeias de aminoácidos
Comparadas com seqüências em bases proteicas
Pontuadas de acordo com sua similaridade
Combinação de Métodos (3/9)


Técnicas de AM são empregadas em uma ou mais
etapas da predição gênica
Predição da estrutura gênica é complexa e
envolve a combinação de vários passos e técnicas

Exemplo: sistema GRAIL II
Combinação de Métodos (4/9)

GRAIL II:

Passo 1: Geração de exons candidatos



Identificação de sítios doadores e receptores
RN atribui pontuação indicando se a junção identificada é um
sítio verdadeiro
Pool de exons candidatos é gerado

Restrições: possuir fase de leitura e ser “intermediado” por um
par de junções receptoras e doadoras com pontuação acima de
um limiar
Combinação de Métodos (5/9)

GRAIL II:

Passo 2: Eliminação de candidatos improváveis


Série de medidas e regras heurísticas são aplicadas aos exons
candidatos
Aplicação leva à eliminação de grande parte dos exons
candidatos (aproximadamente 90%)
Combinação de Métodos (6/9)

GRAIL II:

Passo 3: Avaliação dos exons

Exons remanescentes são avaliados por uma RN
6-mer in-frame (Isochore)
6-mer in-frame (Candidato)
Composição GC (Isochore)
Pontuação
Composição GC do Exon
Exon
...
Doador
Receptor
Combinação de Métodos (7/9)

GRAIL II:

Passo 4: Geração do modelo do gene

Algoritmo de programação dinâmica é aplicado na montagem
do gene



Baseado em suas pontuações
Também são checadas se algumas restrições são satisfeitas
Outros sistemas diferem nas técnicas e passos
Combinação de Métodos (8/9)

Burset e Guigó (1996): compararam diversos
sistemas para predição da estrutura de genes
eucariotos

Deficiências comuns:




Não há metodologia padrão na obtenção das acurácias
Acurácias se mostraram menores que as reportadas
Acurácia dos programas está ligada aos conjuntos de
treinamento empregados em sua geração
Acurácia dos sistemas foi afetada presença de ruídos nos dados
Combinação de Métodos (9/9)


Burset e Guigó (1996) também apontaram que o
emprego de buscas por similaridade mostra-se
uma estratégia promissora
Combinação da saída de vários programas
também pode trazer benefícios

Todos programas predizem um mesmo exon  (quase
certamente) pode ser considerado correto