GenScan
Katia Guimarães
Topologia de um Gene
Gene
Intron 0
Exon1
Intron1
Exon2
3’
{
{
{
{
{
5’
Exon 0
DNA
2
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.
3
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. 4
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.
5
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.
6
Diferentes Regiões em um Gene
Gene
Exon 0
Exon1
Intron1
Exon2
3’
{
{
{
{
{
5’
Intron 0
DNA
Região
Promotora
Região
de Corte 5’
Região
de Cort e 3’
Regiã o
de Corte 5’
Região
de Cort e 3’
Regiã o
PolyA
7
O Modelo do GenScan
O GENSCAN é baseado num modelo denominado
Generalized 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 ,qQ.
 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.
8
Modelo HMM Linear
9
Exemplo de HMM
10
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)
11
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.
12
HMM Gene Model
13
Como Utilizar GenScan
Pedaço contíguo de uma fita de DNA:
ACGAAGGTTCATATC...
Matriz de Parâmetros (três opções):
1.
2.
3.
Vertebrados
Arabidopsis
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
Estrutura de Genes
estimada pelo
GENSCAN
para o DNA
dado como
entrada.
14
Resultado do GeneScan
GENSCAN 1.0 Date run: 15-Jun-101 Time: 07:51:52Sequence X66401 : 66
: 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 +
2.01 Init +
2.02 Intr +
2.03 Intr +
2.04 Intr +
24834
25024
26158
26421
27511
24873
25621
26272
26551
27716
40
598
115
131
206
0
2
0
2
1
1
2
2
57 87
122 41
83 9
123 91
-14.22
371 0.621 27.34
76 0.997 5.81
151 0.979 7.04
98 0.826 12.52
15
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)
16
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)
17
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.
18
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.smat
Predicted 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
1.02 Intr +
1535 1678 144 1 0 92 42 198 0.991
1.03 Intr +
1794 1853 60 2 0 30 105 73 0.899
1.04 Intr +
2425 2628 204 0 0 100 56 389 0.993
1.05 Intr +
4131 4244 114 2 0 139 94 223 0.999
1.06 Intr +
4448 4700 253 1 1 96 21 508 0.900
1.07 Intr +
4990 5258 269 2 2 97 79 536 0.568
1.08 Intr +
5871 6069 199 2 1 105 64 273 0.992
........
1.21 Intr + 14136 14227 92 0 2 90 64 177 0.994
1.22 Term + 14418 14446 29 1 2 124 44 13 0.700
1.23 PlyA + 14835 14840 6
3.44
17.26
3.27
37.51
29.81
43.15
52.10
26.74
16.30
-0.38
1.05
19
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.
20
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.
21
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.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
22
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
23
(ver tabela - coluna P).
Dados da Tabela
…….
2.00 Prom + 24834 24873 40
2.01 Init + 25024 25621 598 0
2.02 Intr + 26158 26272 115 2
2.03 Intr + 26421 26551 131 0
2.04 Intr + 27511 27716 206 2
2.05 Intr + 28143 28340 198 2
2.06 Intr + 29542 29670 129 0
2.07 Intr + 29820 30008 189 2
2.08 Intr + 30568 30741 174 0
2.09 Intr + 30985 31147 163 0
2.10 Intr + 31456 31592 137 2
2.11 Intr + 32875 33051 177 0
2.12 Intr + 35571 35718 148 2
2.13 Intr + 35877 35988 112 1
1
1
2
2
0
0
0
0
1
2
0
1
1
57 87
122 41
83 9
123 91
69 39
89 78
137 87
101 80
103 78
101 94
113 16
98 64
103 115
371
76
151
98
276
131
125
233
108
127
188
116
134
0.621
0.997
0.979
0.826
0.998
0.992
0.999
0.966
0.999
0.999
0.043
0.984
0.999
-14.22
27.34
5.81
7.04
12.52
20.35
13.09
17.08
23.94
10.85
14.89
14.22
10.01
17.04
24
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).
25
Dados da Tabela – Gene 3
3.00 Prom +
3.01 Init +
3.02 Intr +
3.03 Intr +
3.04 Intr +
3.05 Intr +
3.06 Intr +
3.07 Intr +
3.08 Intr +
3.09 Intr +
3.10 Intr +
3.11 Intr +
3.12 Term +
3.13 PlyA +
38257
40428
41010
42888
43302
45837
46200
47480
47855
48221
48572
49125
49627
51307
38296
40920
41124
43018
43507
46034
46328
47512
48043
48394
48731
49261
49755
51312
40
493
115
131
206
198
129
33
189
174
160
137
129
6
2
1
0
1
2
2
1
1
1
1
1
0
1
1
2
2
0
0
0
0
0
1
2
0
83
95
106
99
91
145
45
112
107
83
41
69
92
96
75
99
90
99
113
46
94
70
78
49
260 0.911
66 0.999
150 0.992
201 0.649
187 0.706
101 0.999
41 0.622
97 0.992
232 0.722
178 0.960
206 0.775
157 0.771
-7.86
19.22
7.61
15.84
21.22
18.75
17.79
0.72
7.68
25.84
15.06
15.19
8.08
1.05
26
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.
27
Dados da Tabela – Gene 4
4.00 Prom +
4.01 Init +
4.02 Intr +
4.03 Term +
4.04 PlyA +
60709
61706
63341
64049
65861
60748
61796
63610
64341
65866
40
-5.76
91 1 1 67 110 68 0.655 5.66
270 0 0 54 105 242 0.988 20.01
293 0 2 107 29 199 0.650 11.41
6
1.05
28
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.
29
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
30
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.
31
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.
32
Resultados de Precisão (Burset & Guigó ´96)
Nucleotídeo
Method
Exon
(SN+SP)
SN
SP
AC
SN SP
0.93
0.93
0.91
0.78
0.81
0.80
0.09
0.05
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
GeneParser
2
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
GENSCAN
FGENEH
/2
ME WE
33
Resultados de Precisão
Nucleotídeo
Exon
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
0.66
0.79
0.66
0.35
0.39
0.37
0.29
0.17
GeneParser
2
34