Bioinformatics Course Notes (Ming LI)


Calcolo della distanza di edit



Scaricare 15.77 Kb.
Pagina5/5
26.10.2019
Dimensione del file15.77 Kb.
1   2   3   4   5

Calcolo della distanza di edit

  • Esempio: calcolo della distanza di edit per S1=“winter” (n=6) e S2=“writers” (m=7)
  • w
  • r
  • i
  • t
  • e
  • r
  • s
  • w
  • n
  • t
  • i
  • e
  • r
  • Si costruisca la
  • matrice D di n+1
  • (6+1) righe e m+1
  • (7+1) colonne
  • Si riempiano le
  • celle D(0,j) e D(i,0)
  • con i rispettivi
  • valori dei casi base
  • j e i
  • 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • La cella (1,1) avrà
  • valore D(1,1) dato
  • dal minimo tra:
  • - D(0,0)+t(w,w)=0
  • - D(0,1)+1=2
  • - D(1,0)+1=2
  • Quindi:
  • D(1,1)=0
  • 0
  • La cella (1,2) avrà
  • valore D(1,2) dato
  • dal minimo tra:
  • - D(0,1)+t(w,r)=2
  • - D(0,2)+1=3
  • - D(1,1)+1=1
  • Quindi:
  • D(1,2)=1
  • 1
  • …e così di seguito
  • 2
  • 3
  • 4
  • 5
  • 6
  • 1
  • 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 2
  • 2
  • 2
  • 2
  • 3
  • 4
  • 5
  • 3
  • 3
  • 3
  • 2
  • 3
  • 4
  • 5
  • 4
  • 4
  • 4
  • 3
  • 2
  • 3
  • 4
  • 5
  • 4
  • 5
  • 4
  • 3
  • 2
  • 3
  • Nella cella D(6,7)
  • è memorizzata
  • la distanza di edit
  • tra S1 e S2
  • 3

Calcolo della distanza di edit

  • La trasformazione da S1 a S2 relativa alla cella (i,j) è di
  • 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
  • Se ai è uguale a bj, l’operazione
  • di sostituzione è nulla
  • NB: può esistere più di una trasformazione
  • relativa alla cella (i,j)

Calcolo della distanza di edit

  • Esempio: ricostruzione della trasformazione da S1=“winter” a S2=“writers”
  • w
  • r
  • i
  • t
  • e
  • r
  • s
  • w
  • n
  • t
  • i
  • e
  • r
  • 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 1
  • 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 2
  • 2
  • 2
  • 2
  • 3
  • 4
  • 5
  • 3
  • 3
  • 3
  • 2
  • 3
  • 4
  • 5
  • 4
  • 4
  • 4
  • 3
  • 2
  • 3
  • 4
  • 5
  • 4
  • 5
  • 4
  • 3
  • 2
  • 3
  • 3
  • La cella (6,7) è stata
  • prodotta a partire
  • dalla cella (6,6)
  • winter
  • 2
  • winters
  • 2
  • La cella (6,6) è stata
  • prodotta a partire
  • dalla cella (5,5)
  • winters
  • 2
  • …e così di seguito
  • winters
  • 2
  • winters
  • 1
  • wiiters
  • 0
  • writers
  • 0
  • writers
  • Operazioni: ?
  • Operazioni:
  • - sostituzione n  i
  • - sostituzione i  r

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


Condividi con i tuoi amici:
1   2   3   4   5


©astratto.info 2019
invia messaggio

    Pagina principale