Outline
□ Gene Finding:
□ Struttura ed identificazione di geni in procarioti ed eucarioti;
□ Hidden Markov Models;
□Genscan;
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Premessa
□ Dimensione del genoma umano: 3 x 109 coppie di nucleotidi
□ Numero di geni ≈ 25.000
□ Percentuale di DNA codificante ≈ 1.6%
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Cosa e’?
Data una sequenza di DNA non caratterizzata, trovare:
□ Quali regioni che codificano per proteine
□ Quale dei due filamenti della doppia elica di DNA è codificante
□ Quale schema di lettura è usata in quest’ultimo
□ Dove comincia e dove finisce il gene
□ Dove sono i confini tra esoni/introni negli eucarioti
□ Etc
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Struttura del gene
Schema di lettura: ogni segmento di DNA ha 6 schemi di lettura
Filamento sense:
ATGGCTTACGCTTGA
Reading frame #1
Reading frame #2
Reading frame #3
ATG
GCT
TAC
GCT
TGC
TGG
CTT
ACG
CTT
GA.
GGC
TTA
CGC
TTG
A..
Filamento
antisense:
TCAAGCGTAAGCCAT
Reading frame #4
Reading frame #5
Reading frame #6
TCA
AGC
GTA
AGC
CAT
CAA
GCG
TAA
GCC
AT.
AAG
CGT
AAG
CCA
T..
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Organizzazione del gene
Un gene continuo
Un gene discontinuo (esoni intervallati da introni)
Gene dentro un introne di un altro gene
Geni sovrapposti
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Struttura del gene procariotico
GENE
5’
ATGCTACGGATG……..TGA
Regione Promotore
Regolatrice
Segnale di
Start
Segnale di
Stop
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
3’
Gene Finding: Struttura del gene Eucariotico
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: ORF (Open Reading Frame)
Un ORF o schema di lettura aperto è una zona compresa tra 2
segnali, uno di start e uno di stop presenti nello stesso frame.
All’interno dell’ORF non sono presenti ulteriori segnali di Stop.
start
ATG
stop
ORF
segnali di stop:
TAA, TGA e TAG
Un ORF è una potenziale regione codificante per proteine.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Primo passo
□ La distanza media tra due segnali di stop in una sequenza
casuale di DNA è 64/3 ≈ 21
□ Una proteina è lunga mediamente 300 aminoacidi
□ Se individuiamo due segnali di stop sufficientemente distanti tra
loro potremmo essere in presenza di un potenziale gene
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: ORF in un gene procariotico
Frame 1
Frame 2
Frame 3
ORF ?
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Algoritmo
Per ogni frame bisogna:
1.
Calcolare la distanza tra ogni coppia di segnali
di stop consecutivi.
2.
Se sono sufficientemente distanti, si va a
ricercare il primo codone di start utile.
3.
Trovato un ORF di lunghezza sufficiente, è da
considerare un potenziale gene.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: ORF in un gene eucariotico

Quali delle finestre che vediamo sono esoni?

Quali invece sono assenze casuali di segnali di stop?
Frame 1
Frame 2
Frame 3
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Procarioti vs Eucarioti
Procarioti:
Eucarioti:
 Piccoli genomi 0.5 –
10·106 bp
 Alta densità basi
codificanti (>90%)
 No introni
 Grandi genomi 107 –
1010 bp
 Bassa densità basi
codificanti (<50%)
 Struttura introni/esoni
 Identificazione del gene
relativamente semplice.
Probabilità di successo
~ 99%
 Identificazione del
gene complessa,
livello di accuratezza
~ 50%
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Metodo statistico
□ Un metodo migliore per determinare regioni codificanti tiene
conto delle frequenze dei codoni
□ Un uso diverso dei codoni nella regione codificante è una
caratteristica universale dei genomi
□ Uso diseguale degli aminoacidi nelle proteine esistenti
□ Uso diseguale di codoni sinonimi
□ Possiamo usare queste caratteristiche per differenziare regioni
codificanti e non codificanti del genoma
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Segnali di codifica
Distribuzione delle frequenze di coppie di aminoacidi nelle sequenze delle
proteine (shewanella).
La frequenza media è
del 5%.
Ogni amminoacido ha
delle preferenze nel
precedere o seguire
un altro amminoacido.
Alcuni aminoacidi
sono molto più
frequenti di altri.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Segnali di codifica
La frequenza delle coppie di aminoacidi dipende dal genoma!!!
shewanella
bovino
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Segnali di codifica

Le preferenze degli aminoacidi si rispecchiano sulle coppie di
codoni (o esanucleotidi) presenti nelle zone codificanti.
Ad esempio Nel genoma umano la frequenza della sequenza “AAA
AAA” è ~1% nelle regioni codificanti contro ~5% delle
regioni non codificanti.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Segnali di codifica

Molti esanucleotidi mostrano grosse differenze di frequenza tra zone
codificanti e non codificanti.

Fondamenti per rilevare regioni codificanti
Regioni di DNA dove sono presenti moltissimi esanucleotidi che
sono risultati frequenti in regioni codificanti già appurate, sono
probabilmente regioni codificanti; al contrario sono regioni non
codificanti.

La frequenza delle coppie di codoni sono segnali chiave usati
per identificare regioni codificanti; Tutti i programmi di gene
prediction se ne avvalgono.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Modello preferenziale

Per ogni esanucleotide X (es: AAA AAA), calcolare la sua frequenza
in regioni codificanti (FC(X)) e non codificanti (FN(X))

Calcolare il valore della preferenza di X:
P(X) = log(FC(X)/FN(X))
Proprietà
P(X) vale 0 se X ha la stessa frequenza sia nelle regioni
codificanti, che in quelle non codificanti.
P(X) ha un valore positivo, se X compare più spesso in regioni
codificanti rispetto a quelle non codificanti; più grande è la
differenza più alto sarà il valore di P(X).
P(X) ha un valore negativo, se X ha frequenza maggiore in
regioni non codificanti; più grande è la differenza più piccolo
sarà il valore di P(X).
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Modello preferenziale
Esempi
AAA ATT e AAA GAC hanno le seguenti frequenze
•
•
FC(AAA ATT) = 1.4%,
FC(AAA GAC) = 1.9%,
FN(AAA ATT) = 5.2%
FN(AAA GAC) = 4.8%
Avremo


P(AAA ATT) = log (1.4/5.2) = -0.57
P(AAA GAC) = log (1.9/4.8) = -0.40
Una regione formata solo da esanucleotidi di questo
tipo, è probabilmente una regione non codificante.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Modello preferenziale

Perché usiamo un modello basato su coppie di codoni ?
 Modelli basati su singolo codone spesso non danno abbastanza
informazione per capire se siamo davvero in una regione
codificante o meno.
 Modelli basati su triple di codoni hanno bisogno di moltissimi
dati per rendere attendibile la statistica.
4*4*4 = 64 codoni
4*4*4*4*4*4 = 4,096 coppie di codoni
4*4*4*4*4*4*4*4*4= 262,144 triple di codoni
Nel caso di triple di codoni avremo quindi necessità di avere almeno
un numero elevatissimo di sequenze caratterizzate per popolare la
matrice delle frequenze
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Predizione di una regione codificante
Un semplice modello basato sulle frequenze dei codoni:


Sia fabc la frequenza con la quale il codone abc occorre in una regione
codificante.
Data la coding sequence
a1,b1,c1,a2,b2,c2,……,anbncn,an+1bn+1cn+1
la probabilità di osservare la sequenza di n codoni nei vari frame di lettura:
p1 = fa1,b1,c1 x fa2,b2,c2 x … x fan,bn,cn
p2 = fb1,c1,a2 x fb2,c2,a3 x … x fbn,cn,an+1
p3 = fc1,a2,b2 x fc2,a3,b3 x … x fcn,an+1,bn+1
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Predizione di una regione codificante
Denotiamo con Pi la probabilità dell’i-esimo frame di lettura come:

pi
Pi 
p1  p2  p3

E’ possibile utilizzare in un algoritmo per la ricerca di regioni
codificanti nel modo seguente:

Consideriamo finestre di size n e calcoliamo Pi per ogni punto di start;
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Predizione di una regione codificante

plot di log(p/(1-p)) per i tre frame di lettura:
In questo frame
di lettura il gene è
chiaramente
riconosciuto
gene
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Soglia minima
Regione
codificante?

Dove sono i confini ?
Decidiamo un valore di soglia per marcare una regione come
codificante. Tale valore deve essere scelto testandolo su un
training set. Deve essere tale da trovare il maggior numero
di regioni codificanti ed escludere il maggior numero di
regioni non codificanti.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Boundary Esoni/Introni
Usando come training set, sequenze di DNA la cui suddivisione
esoni/introni sia conosciuta, alliniamo tali sequenze rispetto ai
due siti di splicing.
Esone
Esone
Esone
Introne
Introne
Esone
--gaggcatcag|GTttgtagac-----------tgtgtttcAG|tgcacccact---gaggcatcag|gtttgtagac-----------tgtgtttcag|tgcacccact---ccgccgctga|GTgagccgtg-----------tctattctAG|gacgcgcggg---ccgccgctga|gtgagccgtg-----------tctattctag|gacgcgcggg---tgtgaattag|GTaagaggtt-----------atatctacAG|atggagatca---tgtgaattag|gtaagaggtt-----------atatctacag|atggagatca---ccatgaggag|GTgagtgcca-----------ttatttgcAG|gtatgagacg---ccatgaggag|gtgagtgcca-----------ttatttgcag|gtatgagacg--
Splicesite
site
Splice
Splice
Splice
site
site
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Segnali associati con gli estremi di una
regione codificante

Entrambi i siti di splicing hanno particolari profili di distribuzione
nell’uso dei nucleotidi
Distribuzione dei nucleotidi attorno al Sito Accettore (Genoma Umano).
Y75
Y72
Y78
Y79
Y77
Y80
Y66
Y78
Y85
Y84
N
C68
A
G
G63
-14
-13
-12
-11
-10
-9
-8
-7
-6
-5
-4
-3
-2
-1
1
A
11,1
12,7
3,2
4,8
12,
7
8,7
16,
7
16,
7
12,
7
9,5
26,
2
6,3
100
0,0
21,
4
C
36,5
30,9
19,
1
23,
0
34,
9
39,
7
34,
9
40,
5
40,
5
36,
5
33,
3
68,
2
0,0
0,0
7,9
G
9,5
10,3
15,
1
12,
7
8,7
9,5
16,
7
4,8
2,4
6,3
13,
5
0,0
0,0
100
62,
7
T
38,9
41,3
58,
7
55,
6
42,
1
40,
5
30,
9
37,
3
44,
4
47,
6
27,
0
25,
4
0,0
0,0
0
7,9
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Segnali associati con gli estremi di una
regione codificante

Entrambi i siti di splicing hanno particolari profili di distribuzione
nell’uso dei nucleotidi
Distribuzione dei nucleotidi attorno al Sito Donatore (Genoma Umano).
-3
-2
-1
1
2
3
4
5
6
A
34,0
60,4
9,2
0,0
0,0
52,6
71,3
7,1
16,0
C
36,3
12,9
3,3
0,0
0,0
2,8
7,6
5,5
16,5
G
18,3
12,5
80,3
100
0,0
41,9
11,8
81,4
20,9
T
11,4
14,2
7,3
0,0
100
2,5
9,3
5,9
46,2
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Procedura per identificare i segnali


Creare le matrici pesate per i siti donatori e accettori.
-3
-2
-1
1
2
3
4
5
6
A
34,0
60,4
9,2
0,0
0,0
52,6
71,3
7,1
16,0
C
36,3
12,9
3,3
0,0
0,0
2,8
7,6
5,5
16,5
G
18,3
12,5
80,3
100
0,0
41,9
11,8
81,4
20,9
T
11,4
14,2
7,3
0,0
100
2,5
9,3
5,9
46,2
Sommiamo le frequenze delle lettere corrispondenti nelle posizioni
corrispondenti
…AAGGTAAGTGTCTCA…
AAGGTAAGT:(34.0+60.4+80.3+100+100+52.6+71.3+81.4+46.2)/100= 6.262
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Procedura per identificare i segnali


Creare le matrici pesate per i siti donatori e accettori.
-3
-2
-1
1
2
3
4
5
6
A
34,0
60,4
9,2
0,0
0,0
52,6
71,3
7,1
16,0
C
36,3
12,9
3,3
0,0
0,0
2,8
7,6
5,5
16,5
G
18,3
12,5
80,3
100
0,0
41,9
11,8
81,4
20,9
T
11,4
14,2
7,3
0,0
100
2,5
9,3
5,9
46,2
Sommiamo le frequenze delle lettere corrispondenti nelle posizioni
corrispondenti
…AAGGTAAGTGTCTCA…
AGTGTCTCA:(34.0+12.5+ 7.3+100+100+ 2.8+ 9.3+ 5.5+16.0)/100= 2.874
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Identificare i segnali

In corrispondenza di un sito di splicing, la corrispondente
funzione di score avrà un picco significativo.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Rappresentazione grafica della regione
codificante di un gene eucariotico

Vengono scelti tra gli esoni predetti un insieme che non
causa overlapping
Frame 1
Frame 2
Frame 3
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Ulteriori segnali

Segnali che identificano la trascrizione



TATA-Box (25-30 basi prima dello start)
presente nel 70% dei casi
sito di PolyA
(AATAAA oppure ATTAAA)
Segnali che identificano i promotori
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Ulteriori dati statistici
Distribuzione
lunghezza esoni
150 bp
Distribuzione
lunghezza introni
60 bp
Una regione ricca di G+C è indice della presenza di un gene (vale
solo per i genomi degli eucarioti superiori)
50%
G+C
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Modelli di Markov
La probabilità di un evento dipende dagli eventi precedenti
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Probabilità di una sequenza di eventi
 P(Sole, Pioggia, Pioggia, Pioggia, Neve, Neve) =
P(Sole) P(Pioggia | Sole) P(Pioggia | Pioggia)
P(Pioggia | Pioggia) P(Neve | Pioggia)
P(Neve | Neve)
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Modelli di Markov Nascosti (HMM)
Quale è la sequenza meteorologica più probabile che ha generato
questa sequenza di azioni?
Assunzione (First order Markov chains):
La probabilità di un evento dipende solo dal precedente.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Modelli di Markov Nascosti (HMM) ESEMPIO
Creiamo un modello per distinguere due regioni (per semplicità
supponiamo siano presenti solo due nucleotidi)
I
II
ATTA
TTAT
AAAT
TAAT
…
TTAA
TATA
ATTA
ATAT
ATTT
…
ATAT
Probabilità di transizione dalla
regione I alla II con la sequenza TT
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Modelli di Markov Nascosti (HMM) ESEMPIO
A quale regione appartiene la sequenza TTAT ?

Calcoliamo la probabilità di tutte le possibili sequenze di
nucleotidi appartenenti alle due regioni.
TITIAITI=1.1x10-1
TITIIAITI=1.8x10-3
TIITIAITI=6.0x10-3
TIITIIAITI=9.0x10-3
TITIAITII=8.8x10-3
TITIIAITII=1.4x10-4
TIITIAITII=4.8x10-4
TIITIIAITII=7.2x10-4
TITIAIITI=5.5x10-4
TITIIAIITI=1.0x10-3
TIITIAIITI=3.0x10-5
TIITIIAIITI=5.2x10-3
TITIAIITII=1.4x10-4
TITIIAIITII=8.4x10-3
TIITIAIITII=2.4x10-4
TIITIIAIITII=4.2x10-2
Risulta più probabile che la sequenza appartiene integralmente
alla regione I
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Genscan
http://genes.mit.edu/GENSCAN.html

Il tool di gene prediction più utilizzato

Presenta il miglior compromesso tra
Sensibilità e Specificità (sono due misure di accuratezza)

Largamente utilizzato dal Consorzio Internazionale durante il
Progetto Genoma Umano

Utilizza come algoritmo di base l’ Hidden Markov Model
(generalizzato)
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Genscan è basato su HMM
http://genes.mit.edu/GENSCAN.html
Le coppie di introni/esoni rappresentano i
differenti modi in cui un introne può
interrompere una coding sequence (dopo
la 1° base, dopo la 2° o dopo la 3°)
E0
E1
E2
I0
I1
I2
Einit
Esone iniziale e finale
Esngl
5’ UTR
Filamento sense
Eterm
3’ UTR
polyA
P
N
Filamento antisense
…………………..
…………………..
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Misura dell’accuratezza nella predizione

Scelta una caratteristica (es: identificazione esoni)
Possiamo definire i seguenti valori
1.
2.
3.
4.
TP (true positive) = Numero di esoni predetti, che sono risultati veri esoni.
FP (false positive) = Numero di esoni predetti che sono in realtà dei falsi.
TN (true negative) = Numero di esoni falsi, identificati come tali.
FN (false negative)= Numero di esoni reali, identificati come falsi.
Avremo le seguenti misure
TP
numero di esoni correttamente identificati
Sensibilità 

TP  FN
numero totale degli esoni reali
TP
numero di esoni correttamente identificati
Specificità 

TP  FP
numero di esoni predetti
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Confronto tra tool di gene predictioon
(Parametri calcolati a livello nucleotidico)
Coefficiente di correlazione
CC 
TP TN  FP  FN
(TP  FP)  (TP  FN)  (TN  FP)  (TN  FN)
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Interfaccia Genscan
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Output di Genscan
Probabilità
Inizio, Fine e
Score
del
sito
Score della
che Score
Filamento
suldell’
Frame del
lunghezza
Numerazione
Accettore
dieelemento
codinge sequence
l’elemento
quale
viene
fatta
primo codone
elemento
delTipo
Gene
dei
complessivo
Donatore
di
splicing
calcolata
sia un esone
la predizione
dell’elemento
calcolato
suoi riconosciuto
elementi
dell’esone
Proteina predetta sulla base della CDS calcolata
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007
Gene Finding: Esempio di uso di GenScan
Eseguire con Genscan la scansione del frammento di genoma di
Homo sapiens
>gi|2253431|gb|AF007546.1|AF007546
Utilizzare la proteina predetta da Genscan per fare un BLAST
proteico (BLASTP) per vedere a cosa corrisponde la predizione fatta
da Genscan.
Dept. of Mathematics and Computer Science - University of Catania – Corso di Bioinformatica – 2006/2007