Bioinformatics Course Notes (Ming LI)


Calcolo della distanza di edit



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

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 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  (D(i,0)=i)

Calcolo della distanza di edit

  • D(0,0) = 0
  • D(i,0) = i (i cancellazioni)
  • D(0,j) = j (j cancellazioni)

Calcolo della distanza di edit

  • Correttezza
  • 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)}


Condividi con i tuoi amici:
1   2   3   4   5


©astratto.info 2019
invia messaggio

    Pagina principale