UNIVERSITA’ DI MILANO-BICOCCA
CdL IN INFORMATICA
Corso di
ALGORITMI COMPLEMENTI
Prof. Giancarlo Mauri
Distanza di edit e programmazione dinamica
Confronto di sequenze
Il confronto tra sequenze è fondamentale in campi come la
biologia computazionale, l’analisi dei testi e molti altri.
Possibili obiettivi:

misurare la “similarità” tra le sequenze


misurare la “diversità” tra le sequenze


allineamento
distanza di edit
trovare parti comuni alle sequenze
pattern discovery
 allineamento locale

2
Distanza tra due sequenze
Come si misura la similarità ?
Bisogna capire da dove possono nascere le differenze: errori di
trascrizione, mutazioni, inserimento, cancellazione o sostituzione
di basi ...
Misuriamo la diversità
Distanza di edit tra due sequenze S1 e S2 (Levenshtein 66):
numero minimo di operazioni di “modifica” necessarie per
trasformare S1 in S2
3
ESEMPIO
GETTO
GATTO
una sostituzione
BARDO
BRODO
BRRDO
TINTA
TINTAE
TINTRE
TINORE
TILORE
TOLORE
COLORE
due sostituzioni o un’inversione e una sostituzione
cinque sostituzioni e una cancellazione
AGACCC
GGGTCT
TCTGGG
TCTGGC
TCTGCC
TCTCCC
TCACCC
TGACCC
complemento inverso
4
Edit transcript
I = inserisci
C = cancella
S = sostituisci
N = lascia invariato
SINCNCNNI
v intner
wri t ers
Rappresenta una particolare trasformazione di una stringa in un’altra
5
Distanza di edit: il problema
INPUT:
due sequenze S1 e S2 definite su un alfabeto S
OUTPUT:
distanza di edit tra S1 e S2 e edit transcript ottimale
che fornisce la trasformazione da S1 a S2
TECNICA UTILIZZATA: Programmazione Dinamica (PD)
6
Calcolo della distanza di edit
Si considerino le sequenze :
S1 =
S2 =
a1 a2 ... ai-1 ai ai+1 ... an
b1 b2 ...... bj-1 bj bj+1... bm
Costruiamo l’array:
D(i,j) = distanza tra il prefisso a1a2…ai e il prefisso
b1b2…bj
Il risultato cercato sarà:
D(n,m) = distanza tra a1 a2 ... an e b1 b2 ...bm
7
Calcolo della distanza di edit
SiSihanno
hannotre
trepossibilità
possibilitàper
percalcolare
calcolareD(i,j),
D(i,j),noto
notoD(k,l)
D(k,l)
per per
k<i k<i
e l<j:
e l<j:
t(ai,bj)=1 se ai diverso da bj,
ililcarattere
carattereaa
vasostituito
sostituito
con
conililbt(a
carattere
quindi: bj e
altrimenti
i iva
j e
i,bj)=0
quindi:
D(i,j) = distanza di edit tra i prefissi a1a2…ai-1 e b1b2…bj-1
+ una operazione
di sostituzione
D(i,j)
= D(i-1,j-1)+t(ai,bj)
 il

carattere
ai avava
cancellato
e e
quindi:
il
carattere
cancellato
quindi:
i
D(i,j) = distanza di edit tra i prefissi a1a2…ai-1 e b1b2…bj +
D(i,j) = D(i-1,j)+1
una operazione di cancellazione
il
il
carattere
inserito
quindi:
j va
carattere
bj bva
inserito
e e
quindi:
D(i,j)
D(i,j-1)+1
D(i,j) = distanza di edit
tra=i prefissi
a1a2…ai e b1b2…bj-1 +
una operazione di inserimento
8
Calcolo della distanza di edit

Si richiama quindi il calcolo di:
D(i-1,j-1)
D(i-1,j)
D(i,j-1)
a1 a2 ... ai-1 ai ai+1 ... an
b1 b2 ...... bj-1 bj ... bm
a1 a2 ... ai-1 ai ai+1 ... an
b1 b2 ...... bj-1 bj ... bm
a1 a2 ... ai-1 ai ai+1 ... an
b1 b2 ...... bj-1 bj ... bm
9
Calcolo della distanza di edit
Dal momento che si vuole un valore minimo, si ottiene la
ricorrenza
D(i-1,j-1)+t(ai,bj)
D(i,j) = MIN
D(i-1,j)+1
D(i,j-1)+1
che stabilisce un legame tra il generico sottoproblema
D(i,j) e i sottoproblemi D(i-1,j-1), D(i-1,j) e D(i,j-1)
10
Calcolo della distanza di edit
Ricorrenza:
stabilisce un legame ricorsivo tra il valore di D(i,j) e
i valori per indici più piccoli, fino a un valore base.
BASE:
D(i,0) = i
D(0,j) = j
PASSO:
D(i,j) = min{D(i-1,j)+1; D(i,j-1)+1; D(i-1,j-1)+t(i,j)}
con t(i,j) = 1 se ai ≠ bj
0 altrimenti
11
Calcolo della distanza di edit
In particolare:

per i=n e j=m, si ottiene la distanza di edit
D(n,m) tra le sequenze S1 e S2

per i=0 e j>0, si ottiene la distanza di edit
D(0,j) tra la sequenza nulla e e il prefisso
b1b2…bj (D(0,j)=j)

per i>0 e j=0, si ottiene la distanza di edit
D(i,0) tra il prefisso a1a2…ai e la sequenza nulla e
(D(i,0)=i)
12
Calcolo della distanza di edit
I casi base, per i quali il valore di D è calcolabile
immediatamente, sono:

D(0,0) = 0

D(i,0) = i
(i cancellazioni)

D(0,j) = j
(j cancellazioni)
13
Calcolo della distanza di edit
Correttezza
1.
D(i,j) = D(i-1,j)+1, D(i,j-1)+1 oppure D(i-1,j-1)+t(ai,bj)
Non ci sono altre possibilità
1.1 - Sia I l’ultima operazione per ottenere S2 da S1
Allora D(i,j) = D(i,j-1)+1
1.2 - Sia C l’ultima operazione per ottenere S2 da S1
Allora D(i,j) = D(i-1,j)+1
……
2. D(i,j) ≤ min {D(i-1,j)+1, D(i,j-1)+1, D(i-1,j-1)+t(i,j)}
14
Calcolo della distanza di edit
Esempio: calcolo della distanza di edit per S1=“winter” (n=6) e
S2=“writers” (m=7)
e w r
La cella (1,2)
(1,1) avrà
valore D(1,2)
D(1,1) dato
dal minimo
Nella
cella D(6,7)
tra:
Si riempiano le
costruisca la
-SiD(0,1)+t(w,r)=2
è
D(0,0)+t(w,w)=0
memorizzata
cellecosì
…e
D(0,j)
di e
seguito
D(i,0)
D didin+1
-matrice
la
D(0,1)+1=2
D(0,2)+1=3
distanza
edit
con i rispettivi
-(6+1)
tra
D(1,0)+1=2
D(1,1)+1=1
S righe
e S e m+1
valori1 dei2casi base
(7+1) colonne
Quindi:
jei
D(1,1)=0
D(1,2)=1
i
t
e
r
s
e 0 1 2 3 4 5 6 7
w
1 0 1 2 3 4 5 6
i
2 1 1 1 2 3 4 5
n
3 2 2 2 2 3 4 5
t
4 3 3 3 2 3 4 5
e
5 4 4 4 3 2 3 4
r
6 5 4 5 4 3 2 3
15
Calcolo della distanza di edit
La trasformazione da S1 a S2 relativa alla cella (i,j) è
di
Se ai è uguale a bj, l’operazione
di sostituzione è nulla

sostituzione del carattere ai con il carattere bj se
D(i,j)=D(i-1,j-1)+t(ai,bj)

cancellazione del carattere ai se
D(i,j)=D(i-1,j)+1

inserimento del carattere bj se
D(i,j)=D(i,j-1)+1
NB: può esistere più di una trasformazione
relativa alla cella (i,j)
16
Calcolo della distanza di edit
Esempio: ricostruzione della trasformazione da S1=“winter” a
S2=“writers”
w
(6,6) è stata
La cella (6,7)
prodotta
…e
così di
a partire
seguito
(5,5)
dalla cella (6,6)
r
i
t
e
r
s
0 1 2 3 4 5 6 7
w
1 0 1 2 3 4 5 6
winters
wiiters
writers
winter
i
2 1 1 1 2 3 4 5
n
3 2 2 2 2 3 4 5
Operazioni: ?
t
- inserimento di s
e
4 3 3 3 2 3 4 5
5 4 4 4 3 2 3 4
r
6 5 4 5 4 3 2 3
- sostituzione n  i
- sostituzione i  r
17
Calcolo della distanza di edit
La complessità in tempo dell’algoritmo è

O(nm) per il riempimento della matrice di calcolo
della distanza di edit

O(n+m) per la ricostruzione della trasformazione
da S1 a S2
18