Allineamenti e Misure
di Similarità
Evoluzione  diversità
•A livello molecolare le diversità si creano a causa di
errori avvenuti in fase replicativa del DNA e non corretti
dai sistemi di riparo
•Ciò implica che frammenti di DNA aventi la stessa
funzione in organismi differenti, o funzioni correlate
nello stesso organismo, non hanno esattamente la stessa
sequenza in quanto sono avvenute delle sostituzioni
puntiformi, delle delezioni e delle inserzioni.
L'ALFABETO delle biosequenze.
Un testo biologico è costituito da stringhe il cui
alfabeto, indicato con X, ha dimensione D.
Nel caso degli acidi nucleici l'alfabeto è costituito da 4
caratteri :
A(denina), C(itosina), G(uanina) e T(imina nel DNA) o
U(racile nel RNA))  (D=4),
mentre per le proteine l'alfabeto ha dimensione D=20.
Codice Ambiguità Nucleotidi
Codice IUB
A
C
G
T
M
R
W
S
Y
K
V
H
D
B
N
Nucleotidi
A
C
G
T/U
A or C
A or G
A or T
C or G
C or T
G or T
A or C or G
A or C or T
A or G orT
C or G or T
G or A or T or C
Gli Alfabeti degli Aminoacidi
Alfabeto Classico
(D = 20)
Alfabeto Chimico
(D=8)
Alfabeto funzionale
(D=4)
Alfabeto Idrofobicità
(D=2)
AA
SI
SC
Significato
SF
Significato
SH
Significato
Ala
Arg
Asn
Asp
Cys
Gln
Glu
Gly
His
Ile
Leu
Lys
Met
Phe
Pro
Ser
Thr
Trp
Tyr
Val
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
Y
V
L
B
M
A
S
M
A
L
B
L
L
B
S
R
I
H
H
R
R
L
alifatico
basico
amidico
acido
sulfureo
amidico
acido
alifatico
basico
alifatico
alifatico
basico
sulfureo
aromatico
iminico
idrossilico
idrossilico
aromatico
aromatico
alifatico
H
P
O
M
O
O
M
O
P
H
H
P
H
H
H
O
O
H
O
H
idrofobico non polare
positivo
polare non carico
negativo
polare non carico
polare non carico
negativo
polare non carico
positivo
idrofobico non polare
idrofobico non polare
Positivo
idrofobico non polare
idrofobico non polare
idrofobico non polare
polare non carico
polare non carico
idrofobico non polare
polare non carico
idrofobico non polare
O
I
I
I
I
I
I
I
I
O
O
I
O
O
O
I
I
O
I
O
idrofobico
idrofilico
idrofilico
idrofilico
idrofilico
idrofilico
idrofilico
idrofilico
idrofilico
idrofobico
idrofobico
idrofilico
idrofobico
idrofobico
idrofobico
idrofilico
idrofilico
idrofobico
idrofilico
idrofobico
ALFABETO CHIMICO
L B M A S R I H (dimension=8)
ALFABETO FUNZIONALE
H P 0 M (dimension=4)
ALFABETO IDROFOBICO
0 I (dimension=2)
ALFABETO CHARGE
0 + – (dimension=3)
ALFABETO CHIMICO/FUNZIONALE
A H D C I F (dimension=6)
Symbol
3-letter
Aminoacido
Codone
A
B
Ala
Asp,Asn
Alanine
Aspartic,
Asparagine
Cysteine
Aspartic
Glutamic
Phenylalanine
Glycine
Histidine
Isoleucine
Lysine
Leucine
Methionine
Asparagine
Proline
Glutamine
Arginine
GCT, GCC, GCA, GCG
!GCX
GAT, GAC, AAT, AAC
TGT, TGC
GAT, GAC
GAA, GAG
TTT,TTC
GGT,GGC,GGA,GGG
CAT,CAC
ATT, ATC, ATA
AAA, AAG
!AAR
TTG, TTA, CTT, CTC, CTA, CTG
ATG
AAT,AAC
CCT,CCC,CCA,CCG
CAA,CAG
CGT,CGC,CGA,CGG,AGA,AGG
!RAY
!TGY
!GAY
!GAR
!TTY
!GGX
!CAY
!ATH
TCT,TCC,TCA,TCG,AGT,AGC
ACT,ACC,ACA,ACG
GTT,GTC,GTA,GTG
TGG
TAT, TAC
!TCX,AGY;WSX
!ACZ
!GTX
!TGG
!XXX
!TAY
GAA,GAG,CAA,CAG
TAA, TAG, TGA
!SAR
!TAR,TRA;TRR
C
D
E
F
G
H
I
K
L
M
N
P
Q
R
Cys
Asp
Glu
Phe
Gly
His
Ile
Lys
Leu
Met
Asn
Pro
Gln
Arg
Codifica IUB del Codone
!TTR,CTX,YTR;YTX
!ATG
!AAY
!CCX
!CAR
!CGX,AGR,MGR;MGX
S
T
V
W
X
Y
Z
*
Ser
Thr
Val
Trp
Xxz
Tyr
Glu, Gln
End
Serine
Threonine
Valine
Tryptophan
Unknown
Tyrosine
Glutamic,
Glutamine
Terminator
Misura della SIMILARITA’
Anche se dal punto di vista biologico la similarità
tra due sequenze esprime una relazione di
omologia, i termini “similarità” e “omologia”
hanno significati distinti
SIMILARITA' E OMOLOGIA
Due sequenze si definiscono omologhe se derivano
da una comune sequenza ancestrale in seguito ad
un
processo
speciazione.
di
duplicazione
genica
o
di
SIMILARITA' E OMOLOGIA
L’omologia é dunque un carattere qualitativo che fa
riferimento ad una relazione evolutiva presente o assente e
non é corretto quindi riferirsi a valori di “percentuale di
omologia”.
La similarità, invece, può essere espressa in termini
quantitativi, in quanto fa riferimento al grado di
similitudine che viene misurato tra due sequenze
precedentemente allineate.
La determinazione del grado di similarità tra due o
più sequenze richiede, dunque, che le sequenze in esame
vengano previamente allineate.
Allineamento:
Determinazione di una relazione tra i residui della prima
sequenza con quelli della seconda in modo da rendere
massimo il grado di similarità o analogamente rendere
minimo il numero di differenze.
Stabilisce una relazione biunivoca tra due sequenze (o parti
di esse) in modo da minimizzare il numero di operazioni
necessarie per la trasformazione di una nell’altra.
SA= E V D Q K I S K W D
SB= E V K K I T R P K W D
allineamento
match
E V D Q K I - - S K W D
| |
| |
| | |
E V - K K I T R P K W D
gap
mismatch
Fra due sequenze di lunghezza n e m il numero possibile di
differenti allineamenti e’ pari a n+m-1 quando si esclude
l’inserimento di gaps.
Allineamento ottenuto facendo scorrere una sequenza
sull’altra. Vince l’allineamento con il max n. di match.
Fra tutti i possibili allineamenti con o senza gaps vince
quello che in base all’algoritmo scelto e in base ai
parametri impostati corrisponde al più alto grado di
similarità
Se si volesse lavorare in modo rigoroso, bisognerebbe
provare fra gli n+m-1 allineamenti e scegliere il migliore,
ma ciò implicherebbe tempi lunghi in quanto si dovrebbero
eseguire n × m confronti; si seguono quindi vie alternative.
Le vie alternative all’allineamento esatto
•Utilizzo di algoritmi basati sulla programmazione
dinamica.
•Utilizzo di algoritmi euristici (approssimati)
La scelta dell’algoritmo dipende anche dalle
finalità che l’allineamento si propone:
allineamento globale
allineamento locale
Programmazione dinamica
• Utilizzo di algoritmi basati sulla programmazione
dinamica implementati
 nel metodo di Needleman e Wunsch per la
ricerca dell’allineamento globale
 nel metodo di Smith e Waterman per la
ricerca dell’allineamento locale.
Dot plot
DotPlot permette di individuare graficamente
regioni allineabili
A XX
X
X X
X
X
X
G
X
X X
XX
XX X
C
XXX
X
X
T X
X X
X
X X
X
G
X
X X
XX
XX X
T X
X X
X
X X
X
C
XXX
X
X
C
XXX
X
X
G
X
X X
XX
XX X
A XX
X
X X
X
X
X
A XX
X
X X
X
X
X
T X
X X
X
X X
X
TAAGCCCTEGTAGCTAGGTATCGGATG
TAAGCCCTAGTAGCTAGGTATCGGATG
Sequence Comparison
EMBnet www.embnet.org
Versione semplice: una
croce o un punto sono
collocati all’incrocio fra
due caratteri identici
Con solo 4 caratteri si
introduce molto rumore di
fondo
Dot plots
Versione “Window” o finestra, una stringa
corta interna alla sequenza.
A
X
G
X
C
X X
X
X
T
X
X
X X
G
X
X
X
T
X
X
X X
C
X
X
C
XX
X
G
X
X X
X
X
A
X
X X
X
X
A X
X X
X
X
T X
X X
X
X
TAAGCCCTAGTAGCTAGGTATCGGATG
Sequence Comparison
EMBnet www.embnet.org
Qui si utilizza una finestra
di 3 nucleotidi e poniamo
il punto se ci sono almeno
2 match nella finestra in
esame (analisi con
stringenza 2)
Regioni allineabili si
individuano sul grafico per
la presenza di diagonali
piu’ o meno estese
Caratteristiche di una matrice
dotplot
Diagonali
Diagonali appaiono quando 2
sequenze sono sufficientemente
simili
Interruzioni
Interruzioni di diagonali o
spostamenti di diagonali indicano
la presenza di delezioni o
inserzioni
Sequence Comparison
EMBnet www.embnet.org
Allineamento semplice
L’allineamento semplice si ottiene facendo
scorrere una sequenza sull’altra spostandosi di
un nucleotide per volta
CGCTTCGGACGAAATCGCATCAGCATACGATCGCATGCCGGGCGGGATAAC
||| |||
||
||||||||||||||||||||||||||||||
| ||
||
|||||
| |||||
||
| ||
|||||
|||||
|||||||
CGAAATCGCATCAGCATACGATCGCATGC
CGAAATCGCATCAGCATACGATCGCATGC
CGAAATCGCATCAGCATACGATCGCATGC
CGAAATCGCATCAGCATACGATCGCATGC
CGAAATCGCATCAGCATACGATCGCATGC
CGAAATCGCATCAGCATACGATCGCATGC
CGAAATCGCATCAGCATACGATCGCATGC
CGAAATCGCATCAGCATACGATCGCATGC
CGAAATCGCATCAGCATACGATCGCATGC
CGAAATCGCATCAGCATACGATCGCATGC
Sequence Comparison
EMBnet www.embnet.org
Allineamento semplice
L’allineamento semplice implica la ricerca
sulla matrice dot-plot della diagonale piu’
lunga corrispondente alla regione la cui
somma degli scores è massima.
Sequence Comparison
EMBnet www.embnet.org
Allineamento con Gaps
L’allineamento semplice non funziona
sempre bene
CGCTTCGGACGAAATCGCATCA-GCATACGATCGCATGCCGGGCGGGATAA
CGCTTCGGACGAAATCGCATCAGCATACGATCGCATGCCGGGCGGGATAAC
||| |||
||
||||||||||||||
| ||
||
|||||
| |
|||||
|| |
||
||
|||||||||||||||||
||
||||||||||||||||
|||||
|
|||||||
|
CGAAATCGCATCACGCATACGATCGCATGC
CGAAATCGCATCACGCATACGATCGCATGC
CGAAATCGCATCACGCATACGATCGCATGC
CGAAATCGCATCACGCATACGATCGCATGC
CGAAATCGCATCACGCATACGATCGCATGC
CGAAATCGCATCACGCATACGATCGCATGC
CGAAATCGCATCACGCATACGATCGCATGC
CGAAATCGCATCACGCATACGATCGCATGC
CGAAATCGCATCACGCATACGATCGCATGC
CGAAATCGCATCACGCATACGATCGCATGC
A meno che le sequenze non siano
perfettamente coincidenti conviene
introdurre I gaps
Sequence Comparison
EMBnet www.embnet.org
Allineamento con Gaps
I gaps nell’allieneamento appaiono come
“shifts” nella diagonale.
Gap
Uno shift orizzontale rappresenta
un’inserzione nella sequenza orizzontale.
Sequence Comparison
EMBnet www.embnet.org
Allineamento con Gaps
L’allineamento con Gaps ottimale (max
similarità) corrisponde al percorso sulla dotplot corrispondente alla max somma di scores.
Ci sono molti percorsi nella dot-plot.
Sequence Comparison
EMBnet www.embnet.org
Algoritmi euristici
•Utilizzo di algoritmi euristici (approssimati)
implementati nei metodi di Database Similarity
Searching (FASTA e BLAST)
GRADO DI SIMILARITA’
s(ai,bi) é il punteggio di similarità relativo al confronto tra i
residui ai e bi, e l’indice i individua una qualunque posizione
dell’allineamento in cui non siano presenti inserzioni o
delezioni (gaps).
L
NG
i 1
k 1
S AB   s (ai , bi )      (k )  1
La presenza di NG gaps decrementa il punteggio di similarità
in misura proporzionale ai valori che vengono imposti ai
parametri δ e γ che corrispondono rispettivamente alla
penalità costante δ attribuita alla creazione di un gap e alla
penalità variabile γ[l(k)-1)] attribuita alla estensione del kmo gap che incrementa la penalità costante delta in misura
proporzionale alla lunghezza del gap pari a l(k).
L
NG
i 1
k 1
S AB   s (ai , bi )      (k )  1
Per la determinazione del grado di similarità tra
sequenze di nucleotidi si utilizza essenzialmente il
criterio identità/non identità (match/mismatch)
nel calcolo di s(ai,bi)
Match: s(ai,bi) =1
Mismatch : s(ai,bi) =0
Per la determinazione del grado di similarità tra
sequenze di proteine possono essere applicati
diversi metodi basati essenzialmente sulle proprietà
chimico-fisiche degli aminoacidi omologhi
1. Criterio di identità/non-identità, secondo il quale si
attribuisce un punteggio costante alle coppie di residui
identici con la possibilità di usare alfabeti differenti
per la codifica degli aminoacidi.
Qui oltre al codice classico che per gli aminoacidi
utilizza un alfabeto di venti lettere, possono essere
utilizzati altri alfabeti che raggruppano gli aminoacidi
sulla base delle loro similarità chimico-funzionali.
2. Criterio del codice genetico, secondo il quale il
punteggio di similarità per una coppia di aminoacidi è
correlato al numero di sostituzioni nucleotidiche che
sulla base del codice genetico è necessario per la loro
interconversione.
Gli aminoacidi sono considerati tanto più simili quante
meno sono le sostituzioni necessarie per la loro
conversione.
T  W
ACN  UGG
s(T,W)=a
AV
GCN  GUN
a<b
s(A,V)=b
3. Criterio del codice genetico congiunto ad un peso legato
alla similarità strutturale degli aminoacidi.
Viene considerato congiuntamente il peso legato alla
facilità di conversione tra gli aminoacidi e quello legato
alle loro somiglianze strutturali (Feng et al., 1985).
T
W
ACN
UGG
s(T,W)=1
CH3
CHOH
NH2
C
COOH
H
NH
NH2
CH2
H
C
COOH
H
A V
GCN
s(A,V)=5
GUN
CH3
NH2
C
COOH
H
C2H5
NH2
C
H
COOH
scala arbitraria utilizzata per pesare la similarità tra i 20 aminoacidi
(rappresentati dal codice ad una lettera) basata sulla somiglianza
strutturale e sulla interconvertibilità genetica (Feng et al., 1985)
C S T
6 4 2
6 5
6
P
2
4
4
6
A
2
5
5
5
6
G
3
5
2
3
5
6
N
2
5
4
2
3
3
6
D
1
3
2
2
4
4
5
6
E
0
3
3
3
4
4
3
5
6
Q
1
3
3
3
3
2
3
4
4
6
H
2
3
2
3
2
1
4
3
2
4
6
R
2
3
3
3
2
3
2
2
2
3
4
6
K
0
3
4
2
3
2
4
3
4
4
3
5
6
M
2
1
3
2
2
1
1
0
1
2
1
2
2
6
I
2
2
3
2
2
2
2
1
1
1
1
2
2
4
6
L
2
2
2
3
2
2
1
1
1
2
3
2
2
5
5
6
V
2
2
3
3
5
4
2
3
4
2
1
2
3
4
5
5
6
F
3
3
1
2
2
1
1
1
0
1
2
1
0
2
4
4
4
6
Y
3
3
2
2
2
2
3
2
1
2
3
1
1
2
3
3
3
5
6
W
3
2
1
2
2
3
0
0
1
1
1
2
1
3
2
4
3
3
3
6
C
S
T
P
A
G
N
D
E
Q
H
R
K
M
I
L
V
F
Y
W
4. Criterio basato sui dati di interconvertibilità
degli
aminoacidi determinati dalla osservazione di insiemi di
proteine omologhe:
Matrici Dayhoff : PAM
Blocks Substitution Matrix : BLOSUM
MATRICE PAM
La matrice proposta da Dayhoff et al. (1978) si basa su una compilazione
di sostituzioni aminoacidiche osservate su una collezione di proteine
omologhe.
Sono state considerate 1572 sostituzioni aminoacidiche da 71 gruppi di
proteine omologhe con un grado di similarità superiore all’85%.
La DAYHOFF introducendo il concetto di ”mutazione puntiforme
accettata” (PAM, point accepted mutation) per indicare una sostituzione
aminoacidica accettata dalla selezione naturale, determina una serie di
matrici i cui elementi sono utilizzati come punteggio di similarità per
ciascuna coppia di aminoacidi. Le varie matrici corrispondono a differenti
valori di distanza evolutiva.
Calcolo Matrice PAM
s(a,b) = int(10 x log(M(a,b)/C(a,b)
dove int sta per intero del valore ottenuto
moltiplicando per 10 il logaritmo decimale del
rapporto fra M(a,b) e C(a,b).
• M(a,b) è la frequenza di sostituzione
dell’amminoacido a nell’amminoacido b osservata
nei 71 gruppi di proteine omologhe considerate
• C(a,b) è la frequenza di sostituzione attesa, stimata
come prodotto delle frequenze degli amminoacidi a
e b nei 71 gruppi di proteine omologhe considerate
PAM - 250
A 2
R -2 6
N 0 0
D 0 -1
C -2 -4
Q 0 1
2
2 4
-4 -5 12
1 2 -5 4
E
G
H
I
L
K
M
1
0
2
-2
-3
1
-2
0
1
-1
-1
-2
-1
-1
-1
-3
2
-2
-3
3
0
3
1
1
-2
-4
0
-3
-5
-3
-3
-2
-6
-5
-5
2
-1
3
-2
-2
1
-1
4
0
1
-2
-3
0
-2
5
-2
-3
-4
-2
-3
6
-2
-2
0
-2
5
2 6
-2 -3 5
2 4 0
6
F -3 -4 -3 -6 -4
P 1 0 0 -1 -3
S 1 0 1 0 0
T 1 -1 0 0 -2
W -6 2 -4 -7 -8
Y -3 -4 -2 -4 0
V 0 -2 -2 -2 -2
-5
0
-1
-1
-5
-4
-2
-5
-1
0
0
-7
-4
-2
-5
0
1
0
-7
-5
-1
-2
0
-1
-1
-3
0
-2
1
-2
-1
0
-5
-1
4
2
-3
-3
-2
-2
-1
2
-5
-1
0
0
-3
-4
-2
0
-2
-2
-1
-4
-2
2
9
-5
-3
-3
0
7
-1
6
1
0
-6
-5
-1
2
1
-2
-3
-1
3
-5 17
-3 0 10
0 -6 -2 4
I
L
K M F
P
S
T W Y
A R N D C Q E G H
V
MATRICI BLOSUM
Henikoff & Henikoff (1992) usano un approccio differente
basato sull’osservazione di circa 2000 blocchi di segmenti
di sequenze allineate corrispondenti a più di 50 gruppi di
proteine omologhe, producendo le cosiddette matrici
BLOSUM (Blocks Substitution Matrices) che test empirici
hanno mostrato essere più accurate per il calcolo del
grado di similarità tra due sequenze aminoacidiche.
Matrice BLOSUM
Al fine di ridurre il contributo di coppie di aminoacidi relative
a proteine strettamente correlate, le sequenze che mostrano
una percentuale di identità al di sopra di un valore soglia
predeterminato costituiscono un raggruppamento cui viene
attribuito il peso di una singola sequenza.
In questo modo, variando la percentuale di similarità usata
come soglia si possono ottenere matrici differenti. Ad esempio
la matrice BLOSUM-62, che è quella più comunemente
utilizzata, viene costruita raggruppando tutte le sequenze con
una percentuale di identità superiore al 62%.
Calcolo Matrice BLOSUM
s(a,b) = int(kxlog(M(a,b)/C(a,b)
dove int sta per intero del valore ottenuto moltiplicando
per k il logaritmo decimale del rapporto fra M(a,b) e C(a,b).
•M(a,b) è la frequenza di sostituzione dell’amminoacido a
nell’amminoacido b, osservata nei blocchi di proteine
omologhe considerate.
•C(a,b) è la frequenza di sostituzione attesa, stimata come
prodotto delle frequenze degli amminoacidi a e b nella
totalità dei blocchi di proteine omologhe considerate.
BLOSUM - 62
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
Y
V
4
-1
-2
-2
0
-1
-1
0
-2
-1
-1
-1
-1
-2
-1
1
0
-3
-2
0
A
5
0
-2
-3
1
0
-2
0
-3
-2
2
-1
-3
-2
-1
-1
-3
-2
-3
R
6
1
-3
0
0
0
1
-3
-3
0
-2
-3
-2
1
0
-4
-2
-3
N
6
-3
0
2
-1
-1
-3
-4
-1
-3
-3
-1
0
-1
-4
-3
-3
D
9
-3
-4
-3
-3
-1
-1
-3
-1
-2
-3
-1
-1
-2
-2
-1
C
5
2
-2
0
-3
-2
1
0
-3
-1
0
-1
-2
-1
-2
Q
5
-2
0
-3
-3
1
-2
-3
-1
0
-1
-3
-2
-2
E
6
-2
-4
-4
-2
-3
-3
-2
0
-2
-2
-3
-3
G
8
-3
-3
-1
-2
-1
-2
-1
-2
-2
2
-3
H
4
2
-3
1
0
-3
-2
-1
-3
-1
3
I
4
-2
2
0
-3
-2
-1
-2
-1
1
L
5
-1
-3
-1
0
-1
-3
-2
-2
K
5
0
-2
-1
-1
-1
-1
1
M
6
-4
-2
-2
1
3
-1
F
7
-1
-1
-4
-3
-2
P
4
1
-3
-2
-2
S
5
-2
-2
0
T
11
2 7
-3 -1 4
W Y V
La matrice Dotplot può essere generata
con gli scores al posto dei dots
In questo esempio, due proteine sono confrontate e per ogni coppia
di aa si inserisce lo score derivato dalla matrice BLOSUM-50.
P
A
W
H
E
A
E
H
-2
-2
-3
10
0
-2
0
Sequence Comparison
E
-1
-1
-3
0
6
-1
6
A
-1
5
-3
-2
-1
5
-1
G
-2
0
-3
-2
-3
0
-3
A
-1
5
-3
-2
-1
5
-1
W
-4
-3
15
-3
-3
-3
-3
G
-2
0
-3
-2
-3
0
-3
EMBnet www.embnet.org
H
-2
-2
-3
10
0
-2
0
E
-1
-1
-3
0
6
-1
6
E
-1
-1
-3
0
6
-1
6