Bioinformatics Course Notes (Ming LI)


Calcolo della distanza di edit



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

Calcolo della distanza di edit

  • Si richiama quindi il calcolo di:
  • 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
  • D(i-1,j-1)
  • D(i-1,j)
  • D(i,j-1)

Calcolo della distanza di edit

  • D(i,j) = MIN
  • D(i-1,j-1)+t(ai,bj)
  • 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)

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


Condividi con i tuoi amici:
1   2   3   4   5


©astratto.info 2019
invia messaggio

    Pagina principale