GenScan

Katia Guimarães

2

Topologia de um Gene

Intron0 Intron1

DNA

Exon1 Exon2{ { { { {5’ 3’Exon0

Gene

3

O que é GenScan?

GenScan é um programa de computador capaz de identificar de maneira estatística os genes de uma cadeia de DNA.

Este programa foi construído em 1997, e é baseado num modelo probabilístico para a estrutura do gene descrito por Chris Burge e Samuel Karlin, do Dept. de Matemática da Universidade de Stanford.

4

Características do GenScan

  Identificação da estrutura completa de intron/exon de um Gene numa cadeia de DNA.  Capacidade de identificar múltiplos genes, genes parciais e genes completos.   Capacidade de identificar um conjunto de Genes ocorrendo em ambas as fitas do DNA.   Capacidade de identificar tanto exons optimais quanto exons sub-optimais (em relação ao modelo)  É mais adequado para DNA de organismos vertebrados (esta versão também funciona bem com DNA de Drosophila), milhos e Arabidopsis.)   Capacidade de associar probabilidades significativas as suas predições. Não aborda corte alternativo (alternative splicing).  Não modela genes nas duas fitas que se sobrepõem.

5

Regiões Características dos Genes

Próximo aos genes é possível notar a existência de regiões que obedecem a um certo padrão e que caracterizam a estrutura dos genes:

- Onde começam - Onde terminam - Onde alternam intron/exon ou exon/intron etc. - Região poli-A, rica no nucleotídeo tipo A (Adenina), após o gene.

6

Diferentes regiões em um Gene   

Região Promotora região que antecede o gene.

Região de Corte 5’ Fronteira entre um exon (esquerda) e um intron (direita). Também chamada de região de corte doadora (donor splice site).

Região de Corte 3’ Fronteira entre um intron (esquerda) e um exon (direita). Também chamada de região de corte aceitadora (acceptor splice site).

Região PolyA Sucede o gene; rica no nucleotídeo do tipo A. 

 

7

Diferentes Regiões em um Gene

Intron0 Intron1

DNA

Exon1 Exon2{ { { { {5’ 3’Exon0

Gene

RegiãoPromotora

Regiãode Corte 5’

Regiãode Corte 3’

Regiãode Corte 5’

Regiãode Corte 3’

RegiãoPolyA

8

O Modelo do GenScan

O GENSCAN é baseado num modelo denominadoGeneralized Hidden Markov Model (GHMM), que é definido por cinco parâmetros:   Um conjunto Q de estados.  Uma distribuição de probabilidade inicial para cada estado q ,qQ.

  Probabilidade de transição de estados Ti,j para i,j Q.

  Distribuição de probabilidades fq de tamanho,

onde q Q. Modelos Probabilísticos para a geração de símbolos Pq

para q Q.

9

Modelo HMM Linear

10

Exemplo de HMM

11

O Modelo do GenScan

Um parse de uma seqüência S de tamanho L é uma seqüência de estados (q1,q2,..., qt) cada um associado a

um tamanho di, i {1,2,...t} onde L = d1+d2+...+dt.

Seja um parse de um GHMM, com estados (q1,q2,..., qt),

tamanhos (d1,d2,...,dt). E sejam (S1,S2,...,St) seqüências de

símbolos gerados em cada estado correspondente com o tamanho S = S1S2S3...St.

A probabilidade de que o parse gere a seqüência S é dada por:

 P(,S) = q1 fq1(d1) P q1(S1|d1) × Tq1,q2 q2 fq2(d2) P q2(S2|d2)

× ... × Tq(t-1),qt qt fqt(dt) P qt(St|dt)

12

Achando o melhor parse de uma seqüência

Dada uma seqüência S de comprimento L, se quisermos saber qual probabilidade de que um determinado parse dentre todos os possíveis parses L de comprimento L

tenha gerado aquela seqüência temos (utilizando a regra de Bayes):

P(|S) = P(,S) / (P(1,S) + P(2,S) … P(n,S)),

L={1} {2} ... {2}.

Dados um GHMM e uma seqüência S, podemos saber qual o melhor parse opt do GHMM que gera aquela

seqüência S, utilizando um algoritmo de programação dinâmica chamado algoritmo de Viterbi.

13

HMM Gene Model

14

Como Utilizar GenScan

Pedaço contíguo de uma fita de DNA: ACGAAGGTTCATATC...

Matriz de Parâmetros (três opções): 1. Vertebrados 2. Arabidopsis 3. Milho

Sub - Optimal cutoff : {1.00, 0.50, 0.25, 0.10, 0.05, 0.02, 0.01} (se for 1.00 só gera á melhor saída do

modelo).

GENSCAN GENSCAN

Estrutura de Genes estimada pelo GENSCAN para o DNA dado como entrada.

Estrutura de Genes estimada pelo GENSCAN para o DNA dado como entrada.

15

Resultado do GeneScanGENSCAN 1.0 Date run: 15-Jun-101 Time: 07:51:52Sequence X66401 : 66109 bp : 43.63% C+G : Isochore 2 (43 - 51 C+G%)Parameter matrix: HumanIso.smat

 Predicted genes/exons: Gn.Ex Type S .Begin ...End .Len Fr Ph I/Ac Do/T CodRg P.... Tscr..----- ---- - ------ ------ ---- -- -- ---- ---- ----- ----- ------  1.07 PlyA - 541 536 6 1.05 1.06 Term - 19254 19127 128 1 2 77 46 180 0.998 11.14 1.05 Intr - 20295 20154 142 0 1 84 43 178 0.972 12.83 1.04 Intr - 20654 20525 130 1 1 94 109 64 0.995 9.80 1.03 Intr - 21396 21265 132 2 0 80 51 298 0.999 25.06 1.02 Intr - 22522 22455 68 1 2 119 96 80 0.172 9.60 1.01 Init - 24430 24371 60 1 0 71 47 69 0.152 0.42 1.00 Prom - 24811 24772 40 -11.53

2.00 Prom + 24834 24873 40 -14.22 2.01 Init + 25024 25621 598 0 1 57 87 371 0.621 27.34 2.02 Intr + 26158 26272 115 2 1 122 41 76 0.997 5.81 2.03 Intr + 26421 26551 131 0 2 83 9 151 0.979 7.04 2.04 Intr + 27511 27716 206 2 2 123 91 98 0.826 12.52

16

Saída do GenScan

Gn.Ex : número do gene, número do exon (para referencia)

Type :

Init = Exon Inicial(ATG até 5' splice site)

Intr = Exon Interno (3' splice site até 5' splice site)

Term = Exon Terminal (3' splice site até codon de parada)

Sngl = Gene com um único exon (ATG até códon de parada)

Prom = Região de Promoção (TATA box / initation site)

PlyA = Região poly-A (consenso: AATAAA)

S : Fita de DNA (+ = fita entrada; - = fita complementar)

Begin : posição inicial do exon ou do signal (referente a fita entrada)

End : posição final do exon ou do signal (referente a fita entrada)

Len : tamanho do exon ou do sinal(bp)

17

Saída do GenScan (continuação)

Fr : reading frame do exon

Ph : net phase do exon (tamanho do exon módulo 3)

I/Ac : score do sinal inicial ou do 3' splice site

Do/T : score do sinal terminal ou do 5' splice site

CodRg : score da região codificante

P : probabilidade do exon

(soma sobre todos os parses contendo exon)

Tscr : score do exon (depende do tamanho, I/Ac, Do/T e CodRg)  

18

Exemplo 1: J05451

 

A referência J05451 é de um trecho do DNA com 15067 pb.em que está contido o gene gástrico (H+ +K+)-ATPase, que já foi estudado e identificado.

Este gene é formado por 22 exons.

Utilizando o GENSCAN, foi possível recuperar exatamente a estrutura deste GENE como vemos na figura abaixo:

Em vermelho está o gene real Em azul está o gene previsto pelo GENSCAN.

19

Exemplo 1: J05451

GENSCAN 1.0 Date run: 22-Jun-101 Time: 14:39:18Sequence 14:39:04 : 15067 bp : 57.68% C+G : Isochore 4 (57 - 100 C+G%)Parameter matrix: HumanIso.smatPredicted genes/exons: Gn.Ex Type S .Begin ...End .Len Fr Ph I/Ac Do/T CodRg P.... Tscr..----- ---- - ------ ------ ---- -- -- ---- ---- ----- ----- ------  1.01 Init + 1433 1444 12 1 0 116 78 21 0.927 3.44 1.02 Intr + 1535 1678 144 1 0 92 42 198 0.991 17.26 1.03 Intr + 1794 1853 60 2 0 30 105 73 0.899 3.27 1.04 Intr + 2425 2628 204 0 0 100 56 389 0.993 37.51 1.05 Intr + 4131 4244 114 2 0 139 94 223 0.999 29.81 1.06 Intr + 4448 4700 253 1 1 96 21 508 0.900 43.15 1.07 Intr + 4990 5258 269 2 2 97 79 536 0.568 52.10 1.08 Intr + 5871 6069 199 2 1 105 64 273 0.992 26.74 ........1.21 Intr + 14136 14227 92 0 2 90 64 177 0.994 16.30 1.22 Term + 14418 14446 29 1 2 124 44 13 0.700 -0.38 1.23 PlyA + 14835 14840 6 1.05

20

Exemplo 2: X66401

A referência X66401 é de um trecho com 66109 pares de base do DNA do sexto cromossomo humano. Nele já se sabe que existem cinco genes (em ordem): LMP2, TAP1, LMP7, TAP2, DOB. O GENSCAN, neste caso, não foi capaz de prever corretamente todos os genes.

21

Exemplo 2: X66401

Em vermelho = genes reais; em azul = genes previstos.

No. genes previstos = quatro; no. genes reais é cinco.

O primeiro gene previsto, que se encontra na fita de DNA complementar (note a orientação da seta), casou exatamente com o gene LMP2 documentado.

22

Dados da Tabela

GENSCAN 1.0 Date run: 15-Jun-101 Time: 07:51:52Sequence X66401 : 66109 bp : 43.63% C+G : Isochore 2 (43 - 51 C+G%)Parameter matrix: HumanIso.smatPredicted genes/exons: Gn.Ex Type S .Begin ...End .Len Fr Ph I/Ac Do/T CodRg P.... Tscr..----- ---- - ------ ------ ---- -- -- ---- ---- ----- ----- ------  1.07 PlyA - 541 536 6 1.05 1.06 Term - 19254 19127 128 1 2 77 46 180 0.998 11.14 1.05 Intr - 20295 20154 142 0 1 84 43 178 0.972 12.83 1.04 Intr - 20654 20525 130 1 1 94 109 64 0.995 9.80 1.03 Intr - 21396 21265 132 2 0 80 51 298 0.999 25.06 1.02 Intr - 22522 22455 68 1 2 119 96 80 0.172 9.60 1.01 Init - 24430 24371 60 1 0 71 47 69 0.152 0.42 1.00 Prom - 24811 24772 40 -11.53 

23

Exemplo 2: X66401

O segundo gene previsto que está na fita de DNA entrada está englobando os genes reais TAP1 e LMP7.

Apesar de ter errado o GENSCAN dá uma indicação de que o décimo primeiro exon previsto no segundo gene não é um exon interno muito provável pois tem probabilidade 0.043 (ver tabela - coluna P).

24

Dados da Tabela …….2.00 Prom + 24834 24873 40 -14.22 2.01 Init + 25024 25621 598 0 1 57 87 371 0.621 27.34 2.02 Intr + 26158 26272 115 2 1 122 41 76 0.997 5.81 2.03 Intr + 26421 26551 131 0 2 83 9 151 0.979 7.04 2.04 Intr + 27511 27716 206 2 2 123 91 98 0.826 12.52 2.05 Intr + 28143 28340 198 2 0 69 39 276 0.998 20.35 2.06 Intr + 29542 29670 129 0 0 89 78 131 0.992 13.09 2.07 Intr + 29820 30008 189 2 0 137 87 125 0.999 17.08 2.08 Intr + 30568 30741 174 0 0 101 80 233 0.966 23.94 2.09 Intr + 30985 31147 163 0 1 103 78 108 0.999 10.85 2.10 Intr + 31456 31592 137 2 2 101 94 127 0.999 14.89 2.11 Intr + 32875 33051 177 0 0 113 16 188 0.043 14.22 2.12 Intr + 35571 35718 148 2 1 98 64 116 0.984 10.01 2.13 Intr + 35877 35988 112 1 1 103 115 134 0.999 17.04

25

Exemplo 2: X66401

O quarto gene TAP2 foi identificado corretamente a menos do sétimo exon que não existe no gene real

(Na tabela, o gene de mais baixa probabilidade 0.622).

26

Dados da Tabela – Gene 3

3.00 Prom + 38257 38296 40 -7.86 3.01 Init + 40428 40920 493 2 1 83 92 260 0.911 19.22 3.02 Intr + 41010 41124 115 1 1 95 96 66 0.999 7.61 3.03 Intr + 42888 43018 131 0 2 106 75 150 0.992 15.84 3.04 Intr + 43302 43507 206 1 2 99 99 201 0.649 21.22 3.05 Intr + 45837 46034 198 2 0 91 90 187 0.706 18.75 3.06 Intr + 46200 46328 129 2 0 145 99 101 0.999 17.79 3.07 Intr + 47480 47512 33 1 0 45 113 41 0.622 0.72 3.08 Intr + 47855 48043 189 1 0 112 46 97 0.992 7.68 3.09 Intr + 48221 48394 174 1 0 107 94 232 0.722 25.84 3.10 Intr + 48572 48731 160 1 1 83 70 178 0.960 15.06 3.11 Intr + 49125 49261 137 1 2 41 78 206 0.775 15.19 3.12 Term + 49627 49755 129 0 0 69 49 157 0.771 8.08 3.13 PlyA + 51307 51312 6 1.05

27

Exemplo 2: X66401

O quinto gene, DOB, apesar de estar correto no início, não termina corretamente e novamente a coluna P dá uma certa indicação do erro cometido pelo GENSCAN.

28

Dados da Tabela – Gene 4

4.00 Prom + 60709 60748 40 -5.76 4.01 Init + 61706 61796 91 1 1 67 110 68 0.655 5.66 4.02 Intr + 63341 63610 270 0 0 54 105 242 0.988 20.014.03 Term + 64049 64341 293 0 2 107 29 199 0.650 11.41 4.04 PlyA + 65861 65866 6 1.05  

29

GeneScan vs. Outros preditores

Medidas de Desempenho por Nucleotídeo

Cada nucleotídeo predito pode ser classificado como: - PP (Predicted Positive) ( pela perdição faz parte de um gene) - PN (Predicted Negative) ( pela predição não faz parte de um gene.

Cada nucleotídeo é, de acordo com os genes reais: - AP (Actual Positive) (pertence a um gene real) - AN (Actual Negative) (não pertence a um gene real)

Cada nucleotídeo é, de acordo com genes reais + a predição:  TP, True Positives = nucleotídeos PP e AP. FP, False Positives = nucleotídeos PP e AN. TP, True Negatives = nucleotídeos PN e AN. FN, False Negatives = nucleotídeos PN e AP.

30

Medidas de Desempenho por Nucleotídeo

• Sensibilidade (capacidade de capturar os verdadeiros +)

SN = #TP / #AP

• Especificidade (fração dos preditos + que são de fato +)

SP = #TP / #PP

• Correlação Aproximada: ( positivos certos sem chute e negativos certos e sem chutes)

 AC = (( (#TP / (#TP+#FN)) + (#TP / (#TP+#FP)) +

(#TN / (#TN+#FP)) + (#TN / (#TN+#FN)) ) / 2) -1

31

Medidas de Desempenho por Exon

 AE(annotated exon) é um exon anotado ou real.

PE(predicted exon) é um exon resultante de uma predição.

TE é o AE igual a um PE, ou seja, TRUE POSITIVE.

Sensibilidade: No. de identificados c/ relação aos anotados

SN = #TE / #AE

Especificidade: SP = #TE / #PE  

ME (missed exons): No. de AE não sobreposto por nenhum PE.

WE (wrong exons):No.de PE não sobreposto por nenhum AE.

32

Resultados

 AE(annotated exon) é um exon anotado ou real.

PE(predicted exon) é um exon resultante de uma predição.

TE é o AE igual a um PE, ou seja, TRUE POSITIVE.

Sensibilidade: No. de identificados c/ relação aos anotados

SN = #TE / #AE

Especificidade: SP = #TE / #PE  

ME (missed exons): No. de AE não sobreposto por nenhum PE.

WE (wrong exons):No.de PE não sobreposto por nenhum AE.

33

Resultados de Precisão (Burset & Guigó ´96)  Nucleotídeo Exon

MethodSN SP AC SN SP

(SN+SP) /2 ME WE

GENSCAN0.93 0.93 0.91 0.78 0.81 0.80 0.09 0.05

FGENEH0.77 0.85 0.78 0.61 0.61 0.61 0.15 0.11

GeneID0.63 0.81 0.67 0.44 0.45 0.45 0.28 0.24

GeneParser2 0.66 0.79 0.66 0.35 0.39

0.37 0.29 0.17

GenLang 0.72 0.75 0.69 0.50 0.49 0.50 0.21 0.21

GRAILII 0.72 0.84 0.75 0.36 0.41 0.38 0.25 0.10

SORFIND 0.71 0.85 0.73 0.42 0.47 0.45 0.24 0.14

34

Resultados de Precisão

  NucleotídeoExon

Method Sn Sp AC Sn Sp (Sn+Sp)/2 ME WE

GENSCAN 0.93 0.93 0.91 0.78 0.81 0.80 0.09 0.05

FGENEH 0.77 0.85 0.78 0.61 0.61 0.61 0.15 0.11

GeneID 0.63 0.81 0.67 0.44 0.45 0.45 0.28 0.24

GeneParser2 0.66 0.79 0.66 0.35 0.39 0.37 0.29 0.17