UNIVERSITA’ DI MILANO-BICOCCA
LAUREA MAGISTRALE IN
BIOINFORMATICA
Corso di
BIOINFORMATICA: TECNICHE DI BASE
Prof. Giancarlo Mauri
Lezione 4
Distanza di edit e programmazione dinamica
Confronto di sequenze
Il confronto tra sequenze in biologia computazionale è la
base per:
 misurare la “similarità” tra le sequenze
 allineamento
 misurare la “diversità” tra le sequenze
 distanza di edit
 trovare parti comuni alle sequenze
 pattern discovery
 allineamento locale
2
Confronto di sequenze
Perché si confrontano sequenze in biologia?
Capire da dove possono nascere le differenze:
errori di trascrizione
mutazioni
inserimento
cancellazione
sostituzione di basi
3
Distanza tra due sequenze
Distanza tra due sequenze S1 e S2 (Levenshtein 66):
numero minimo di “operazioni di modifica” necessarie
per trasformare S1 in S2
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
Rappresenta una particolare trasformazione di una stringa in un’altra
v intner
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
Programmazione Dinamica
Perché si usa la Programmazione Dinamica?
Per rendere efficiente l’implementazione di procedure ricorsive
Esempio: procedura ricorsiva per il calcolo della somma dei
numeri da 1 a n
Procedura SOMMA(n)
Esempio di chiamata SOMMA(4)
SOMMA(4)
begin
if n=1 then
somma:=n;
else
SOMMA(3) +4
SOMMA(2) +3
SOMMA(1) +2
somma:=SOMMA(n-1)+n;
7
Programmazione Dinamica
Quali sono le procedure ricorsive da sostituire con un algoritmo
di PD?
Quelle in cui si presentano sottoproblemi ripetuti
Esempio: i numeri di Fibonacci
 Obiettivo
 dare un modello matematico della crescita di una popolazione di conigli
 Assunzioni:
 Si parte (tempo 0) con una coppia di conigli neonati
 Ogni coppia genera una nuova coppia ad ogni unità di tempo, a partire dalla seconda
unità dopo la nascita
 I conigli non muoiono mai
 Modello matematico per calcolare il numero di coppie al tempo n:
F(n) :=
se (n=0) o (n=1), allora 1
8
Programmazione Dinamica
Esempio di chiamata FIB(4)
Esempio: procedura ricorsiva per ilFIB(4)
calcolo dei numeri di
Fibonacci
FIB(3)
FIB(2)
Procedura FIB(n)
begin
FIB(1)
FIB(0)
if n=0 or n=1 then
return 1;
a:=n-1;b:=n-2;
f1:=FIBONACCI(a);
NB: nella
chiamata FIB(4), il numero di
f2:=FIBONACCI(b);
Fibonacci per n=2 viene calcolato 2 volte
FIB(1)
FIB(2)
FIB(1)
FIB(0)
return f1+f2;
9
Programmazione Dinamica
Algoritmo alternativo a FIB(n)
Procedura FIB2(n)
begin
F:=(); i:=0;
for i=0 to n do
begin
if i=0 then
F[i]:=0;
else
if i=1 NB:
thennella
chiamata FIB2(4), il valore F[2]
viene
sfruttato 2 volte ma calcolato 1 volta
F[i]:=1;
else
10
Programmazione Dinamica
Passi fondamentali della Programmazione Dinamica
 Riduzione del problema in sottoproblemi
 Risoluzione di tutti i sottoproblemi possibili
 Risoluzione del problema originale tramite l’utilizzo delle soluzioni dei
suoi sottoproblemi
11
Calcolo della distanza di edit
Si considerino le sequenze :
S1 =
a1 a2 ... ai-1 ai ai+1 ... an
S2 =
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
12
Calcolo della distanza di edit
SiSihanno
hannotre
trepossibilità
possibilitàper
percalcolare
calcolareD(i,j),
D(i,j),noto
notoD(k,l)
perD(k,l)
k<i e l<j:
per k<i e l<j:
t(ai,bj)=1 se ai diverso da bj,
ililcarattere
con
altrimenti
t(a
,bquindi:
j ie
j)=0
carattereaai iva
vasostituito
sostituito
conililb
carattere
bj e
D(i,j) = distanza di edit tra i prefissi a1a2…ai-1 e b1b2…bj-1
quindi:
+ una operazione di sostituzione
D(i,j) = D(i-1,j-1)+t(ai,bj)
 il carattere ai va cancellato e quindi:
 il
carattere
ai va
cancellato
e quindi:
D(i,j)
= distanza
di edit
tra i prefissi
a1a2…ai-1 e b1b2…bj +
una operazione di cancellazione
D(i,j) = D(i-1,j)+1
 il carattere bj va inserito e quindi:
 il carattere bj va inserito e quindi:
D(i,j) = distanza di edit tra i prefissi a1a2…ai e b1b2…bj-1 +
D(i,j) = D(i,j-1)+1
una operazione di inserimento
13
Calcolo della distanza di edit
 Si richiama quindi il calcolo di:
D(i-1,j-1)
a1 a2 ... ai-1 ai ai+1 ... an
b1 b2 ...... bj-1 bj ... bm
D(i-1,j)
a1 a2 ... ai-1 ai ai+1 ... an
b1 b2 ...... bj-1 bj ... bm
D(i,j-1)
a1 a2 ... ai-1 ai ai+1 ... an
b1 b2 ...... bj-1 bj ... bm
14
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)
15
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
16
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)
17
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)
18
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)}
19
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
20
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
NB: può esistere più di una trasformazione
relativa alla cella (i,j)
 inserimento del carattere bj se
D(i,j)=D(i,j-1)+1
21
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
- sostituzione n  i
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 i  r
22
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
23