UNIVERSITA’ DI MILANO-BICOCCA
LAUREA MAGISTRALE IN
BIOINFORMATICA
Corso di
BIOINFORMATICA: TECNICHE DI BASE
Prof. Giancarlo Mauri
Lezione 7
Allineamento di sequenze
Allineamento globale di sequenze
Cos’è un allineamento globale?
Date due sequenze S = s1s2…sn e T = t1t2…tm sull’alfabeto
S, un allineamento (globale) di S e T consiste in una coppia
di sequenze S’ = s’1s’2…s’l e T’ = t’1t’2…t’l sull’alfabeto SU{}
(con  carattere di spazio), che godono delle seguenti
proprietà:
S’ = T’ = l (max(n,m) ≤ l ≤ (m+n))
 Eliminando gli spazi da S’ si ottiene S


Eliminando gli spazi da T’ si ottiene T

Se s’i = , allora t’i ≠ e viceversa
2
Allineamento globale: esempio
S
T
S’
T’
ttcgagccttagcgta
ttatagcgtagtcgta
ttc-gagccttag-cgta
ttat-agcg-tagtcgta
Mismatch
Match
in T
Cancellazione
S o inserzione in S
T
3
Allineamento globale
 Rispetto alla distanza di edit, massimizza la similarità
anziché minimizzare la differenza
 La distanza di edit è riconducibile ad esso
 Tecniche utilizzate:
 Analisi di dot matrix (dotplot)
 Algoritmi di Programmazione Dinamica
 Metodi euristici (FASTA, BLAST)
4
Esempio
Senza gap: punteggio 10
IPLMTRWDQEQESDFGHKLPIYTREWCTRG
CHKIPLMTRWDQQESDFGHKLPVIYTREW
Con gap: punteggio 25
IPLMTRWDQEQESDFGHKLP IYTREWCTRG
CHKIPLMTRWDQ QESDFGHKLPVIYTREW
5
Allineamento pesato
Cos’è una matrice di punteggio?
Matrice che assegna ad ogni coppia di caratteri
(a,b)(S{-})2 un punteggio d che esprime il costo (o il
beneficio) della sostituzione del simbolo a col simbolo b.
Punteggio A
dell’allineamento S’, T’
l
A   d(S'(i), T' (i))
i1
6
Allineamento globale : il problema
INPUT:
due sequenze S e T definite su un alfabeto S e una
matrice di punteggio d: (S{-})2  R
OUTPUT:
un allineamento (S’, T’) tra S e T il cui punteggio A sia
minimo (o massimo)
NB: Se d(a,b) esprime un costo, A è da minimizzare.
Se d(a,b) esprime un beneficio, A è da massimizzare
7
Allineamento globale con indels
 Inserimenti e cancellazioni (indels) sono necessari per
allineare accuratamente sequenze anche molto simili
come le  e  globine
 L’approccio ingenuo per trovare l’allineamento ottimo
di due sequenze con indels consiste nel generare tutti
i possibili allineamenti, sommare i punteggi per ogni
coppia di simboli corrispondenti in ogni allineamento e
scegliere quello di punteggio massimo.
 Questa idea è praticamente irrealizzabile anche per
sequenze corte (anche solo di 100 caratteri).
8
Algoritmo di Needleman-Wunsch (1970)
Si
le sequenze
S=s1s2S
…s=
n esT=t
1t2…te
Si considerino
considerino
le sequenze
1s2…s
n m T = t1t2…tm
Sia A(i,j) il costo dell’allineamento tra il prefisso s1s2…si e il prefisso
Sia
A(i,j)
il costo
dell’allineamento
tra il prefisso s1s2…si e il
t1t2…t
.
Si
hanno
tre
possibilità:
j
d(spossibilità:
i,tj)=0 se si uguale a tj,
prefisso t t …t . Si hanno tre
1 2
j
il carattere si si allinea con il carattere tj e quindi:
 il carattere
si si
allinea contra
il carattere
A(i,j) = costo
allineamento
i prefissi s1tsj2e
…squindi:
i-1 e t1t2…tj-1 + d(si,tj)

A(i,j) = A(i-1,j-1) + d(si,tj)
il carattere si si allinea con uno spazio e quindi:
A(i,j) = costo
allineamento
s2…si-1 e t1t2…tj + d(si,-)
 il carattere
s si
allinea contra
unoi prefissi
spazio es1quindi:

i


= A(i-1,j)
d(si,-)
il carattere tj si allineaA(i,j)
con uno
spazio e+ quindi:
A(i,j) = costo allineamento tra i prefissi s1s2…si e t1t2…tj-1 + d(-,tj)
il carattere tj si allinea con uno spazio e quindi:
A(i,j) = A(i,j-1) + d(-, tj)
9
Algoritmo di Needleman-Wunsch
Se si vuole un valore minimo, si ottiene la ricorrenza
A(i-1,j-1) + d(si,tj)
A(i,j) = min
A(i-1,j) + d(si,-)
A(i,j-1) + d(-,tj)
che stabilisce un legame tra il generico sottoproblema
A(i,j) e i sottoproblemi A(i-1,j-1), A(i-1,j) e A(i,j-1)
10
Algoritmo di Needleman-Wunsch
I casi base, per i quali il valore di A è immediatamente
calcolabile, sono:

A(0,0) = 0

A(i,0) = Sik=1d(sk,-) per 0<i<n

A(0,j) = Sik=1d(-,tk) per 0<j<m
Il costo dell’allineamento tra S e T è A(n,m)
11
Le matrici di punteggio
Esempi di matrice di punteggio
d(x,x) = 1, d(-,x) = d(x,-) = -a, d(x,y) = -u
 Se a = 0, u =   LCS (Longest Common
Subsequence)
PAM oppure BLOSUM per le proteine
12
Le matrici di punteggio
Matrice identità
Matrice BLAST
A
T
C
G
A
T
C
A
1
0
0
0
A
T
0
1
0
0
T -4
C
0
0
1
0
C -4 -4
G
0
0
0
1
G -4 -4 -4
Matrice transizione
trasversione
G
5 -4 -4 -4
5 -4 -4
5 -4
5
A
A
T
1
-5 -5 -1
T -5
1
C -5 -1
C
G
-1 -5
1
-5
G -1 -5 -5
1
13
Calcolo della distanza di edit
La distanza di edit può essere ricondotta ad un
problema di allineamento globale
D(i-1,j-1) + d(si,tj)
D(i,j) = min
D(i-1,j) + d(si,-)
D(i,j-1) + d(-,tj)
d(si,tj)=0 per si=tj
d(si,tj)=1 per sitj
d(si,-)=d(-,tj)=1j
14
Matrici PAM (Point Accepted
Mutations)
 Sono utilizzate per il confronto di sequenze proteiche
 Sono derivate dalla frequenza con cui un aminoacido
sostituisce un altro in sequenze evolutivamente
correlate
 Le mutazioni accettate non hanno causato
l’eliminazione dell’organismo
 Sono evidenziate allineando proteine omologhe in
specie diverse (es. emoglobina alfa in uomo e orango)
15
Matrici PAM (Point Accepted
Mutations)
 PAM1:
 Matrice corrispondente a distanza evolutiva 1 (1% di
mutazioni)
 PAMn:
 Matrice corrispondente a distanza evolutiva n, PAM1n
 La matrice di punteggio S è calcolata a partire da una
matrice di probabilità di transizione M
16
Il calcolo di PAM 1
 pa, probabilità di occorrenza dell’aminoacido a in un insieme
abbastanza ampio di sequenze proteiche
 fa,b = fb,a numero di mutazioni a  b accettate
 fa = S fa,b
 f = S fa (doppio del numero di mutazioni)
 Ma,b = prob. che a cambi in b (anche per a=b)
 Ma,a è calcolata partendo dalla mutabilità relativa di a:
 ma = fa/100fpa
 Ma,a = 1 - ma
 Ma,b = fa,b * ma/fa
17
PAM 240
18
BLOSUM 50
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
Y
V
A
5
-2
-1
-2
-1
-1
-1
0
-2
-1
-2
-1
-1
-3
-1
1
0
-3
-2
0
R
-2
7
-1
-2
-4
1
0
-3
0
-4
-3
3
-2
-3
-3
-1
-1
-3
-1
-3
N
-1
-1
7
2
-2
0
0
0
1
-3
-4
0
-2
-4
-2
1
0
-4
-2
-3
D
-2
-2
2
8
-4
0
2
-1
-1
-4
-4
-1
-4
-5
-1
0
-1
-5
-3
-4
C
-1
-4
-2
-4
13
-3
-3
-3
-3
-2
-2
-3
-2
-2
-4
-1
-1
-5
-3
-1
Q
-1
1
0
0
-3
7
2
-2
1
-3
-2
2
0
-4
-1
0
-1
-1
-1
-3
E
-1
0
0
2
-3
2
6
-3
0
-4
-3
1
-2
-3
-1
-1
-1
-3
-2
-3
G
0
-3
0
-1
-3
-2
-3
8
-2
-4
-4
-2
-3
-4
-2
0
-2
-3
-3
-4
H
-2
0
1
-1
-3
1
0
-2
10
-4
-3
0
-1
-1
-2
-1
-2
-3
2
-4
I
-1
-4
-3
-4
-2
-3
-4
-4
-4
5
2
-3
2
0
-3
-3
-1
-3
-1
4
L
-2
-3
-4
-4
-2
-2
-3
-4
-3
2
5
-3
3
1
-4
-3
-1
-2
-1
1
K
-1
3
0
-1
-3
2
1
-2
0
-3
-3
6
-2
-4
-1
0
-1
-3
-2
-3
M
-1
-2
-2
-4
-2
0
-2
-3
-1
2
3
-2
7
0
-3
-2
-1
-1
0
1
F
-3
-3
-4
-5
-2
-4
-3
-4
-1
0
1
-4
0
8
-4
-3
-2
1
4
-1
P
-1
-3
-2
-1
-4
-1
-1
-2
-2
-3
-4
-1
-3
-4
10
-1
-1
-4
-3
-3
S
1
-1
1
0
-1
0
-1
0
-1
-3
-3
0
-2
-3
-1
5
2
-4
-2
-2
T
0
-1
0
-1
-1
-1
-1
-2
-2
-1
-1
-1
-1
-2
-1
2
5
-3
-2
0
W
-3
-3
-4
-5
-5
-1
-3
-3
-3
-3
-2
-3
-1
1
-4
-4
-3
15
2
-3
Y
-2
-1
-2
-3
-3
-1
-2
-3
2
-1
-1
-2
0
4
-3
-2
-2
2
8
-1
V
0
-3
-3
-4
-1
-3
-3
-4
-4
4
1
-3
1
-1
-3
-2
0
-3
-1
5
19
Schemi di peso per i gap
 Linear score

f(g)= -gd con d gap-open penalty e g lunghezza del gap

Un peso dei gap dipendente dalla sola lunghezza comporta che due
gap isolati diano lo stesso costo di due consecutivi
 Affine score

f(g)= -d –(g-1)e con d gap-open penalty, e gap-extension penalty e g
lunghezza del gap

Modello di transizione da una sequenza all’altra biologicamente più
significativo, dal momento che inserzioni e cancellazioni di più di un
residuo non sono eventi poco comuni tra sequenze proteiche
omologhe
20
Allineamento globale vs locale
L’allineamento di due o più sequenze può essere globale o
locale
Globale: l’intera sequenza
viene allineata
Locale: solo frammenti della
sequenza vengono allineati
21
Allineamento locale: esempio
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK
TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKA
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK
TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKA
22
Allineamento locale
E’ meglio avere molte coincidenze sparse o averne
meno, ma concentrate?
Allineamento locale
Date S e T trovare due sottostringhe v e w di S e T
rispettivamente la cui similarità (allineamento ottimo)
sia massima su tutte le coppie di sottostringhe di S e
T.
23
Allineamento locale: esempio
S = pqraxabcstvq
T=
xyaxbacsll
axab-cs
ax-bacs
Con il seguente punteggio:
- d(x,x) = 2
- d(x,y) = -2
- d(x,-) = -1
si ottiene uno score pari a 8
24
Quando e perché l’allineamento
locale?
 Confronto sequenze DNA “anonimo”, per individuare
sottostringhe collegate
 Individuazione subunità strutturali comuni a proteine
diverse
…
25
Considerazioni di complessità
Ci sono (n2 m2) coppie di sottostringhe
L’allineamento locale può tuttavia essere
calcolato in tempo O(nm) come quello globale
26
Algoritmo di Smith-Waterman
Date due sequenze S e T (di lunghezza m e n):
 Si costruisce una matrice A di dimensione (m+1)x(n+1) in cui A(i,j)
è il costo di un allineamento tra il suffisso (eventualmente vuoto)
S[1,i] e il suffisso T[1,j]

Si inizializza la prima riga e la prima colonna di A a zero

La ricorrenza è derivata da quella dell’allineamento globale, con
l’aggiunta di 0 come valore minimo:
A(i,j) = max{0, A(i-1,j) + d(si,-); A(i,j-1)+d(-,tj); A(i-1,j-1)+d(si,tj)}
27
-41
28
One example of local dynamic
programming using a linear
score for gaps and Blosum50
29
30
Strategie euristiche
per l’allineamento di
sequenze in ricerche
in database: tempi a
confronto
31
Similarità di sequenze con FASTA
32
FASTA
33
BLAST (Basic Local Alignment Search Tool)
34
BLOSUM 62
35
Ricerca con Mega BLAST
Mega BLAST uses the greedy algorithm for nucleotide
sequence alignment search. This program is
optimized for aligning sequences that differ slightly as
a result of sequencing or other similar "errors". When
larger word size is used (see explanation below), it is
up to 10 times faster than more common sequence
similarity programs. Mega BLAST is also able to
efficiently handle much longer DNA sequences than
the blastn program of traditional BLAST algorithm.
36
Costruzione del profilo di una
sequenza
Allineamento Multiplo
1
2
3
4
5
6
7
8
9
10
Y
Y
Y
Y
Y
Y
Y
G
T
T
K
R
R
R
R
K
R
Y
K
K
D
D
D
D
D
D
D
G
G
G
Y
Y
Y
Y
Y
Y
Y
F
Y
Y
H
Q
Q
V
Q
N
Q
G
G
G
0
0
0
0
0
0
0
40
0
0
0
0
0
0
50
0
0
0
10
0
0
0
70
0
0
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
30
10
0
0
0
0
10
0
40
0
0
0
10
0
0
S
T
S
S
F
T
T
F
F
G
G
D
D
D
D
D
H
D
L
L
L
0
0
0
0
0
0
0
0
33
0
0 100
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33
0
33
0
0
0
0
0
0
0
0
0
60
0
0
0
10
0
0
30
0
0
0
0
0
0
0
0
0
0
K
Q
H
H
Q
Q
H
I
I
I
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
N
N
N
G
G
G
G
G
N
A
T
T
T
E
D
E
E
S
E
D
E
E
E
0
0
0
0
0
0
0
0
0
0
0
0
30
0
10 100
30
0
0
0
0
0
0
0
0
0
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
70
0
0
0
30
0
0
0
0
0
0
0
0
10
0
0
0
0
50
0
0
0
0
0
10
0
0
0
0
30
0
0
0
0
0
20
70
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
L
L
L
L
L
S
L
T
T
T
T
T
T
K
K
K
Position
A 0
C 0
D 0
E 0
F 0
G 10
H 0
K 0
I 0
L 0
M 0
N 0
P 0
Q 0
R 0
S 0
T 20
V 0
W 0
Y 70
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0 100
0
0
0
0
0
0
60
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
30 100
0
0
0
0
0
0
0
0
0
0
37
La struttura di PSI-BLAST
 PSI-BLAST takes as input a protein sequence and compares it to a
protein database, using the gapped BLAST program
 The program constructs a multiple alignment, and then a profile, from
any significant local alignment found. The original query sequence serves
as a template for the multiple alignment and profile, whose lengths are
identical to that of the query. Different numbers of sequences can be
aligned in different template positions
 The profile is compared to the protein database, again seeking local
alignments. After a few minor modifications, the BLAST algorithm can
be used for this directly.
 PSI-BLAST estimates the statistical significance of the local alignments
found. Because profile substitution scores are constructed to a fixed
scale, and gap scores remain independent of position, the statistical
theory and parameters for gapped BLAST alignments remain applicable
to profile alignments.
 Finally, PSI-BLAST iterates, by returning to step (2), an arbitrary
number of times or until convergence.
38