Bioinformatics Course Notes (Ming LI)



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

ESEMPIO

  • GATTO
  • GETTO
  • BARDO
  • BRRDO
  • BRODO
  • due sostituzioni o un’inversione e una sostituzione
  • COLORE
  • TOLORE
  • TILORE
  • TINORE
  • TINTRE
  • TINTAE
  • TINTA
  • AGACCC
  • complemento inverso
  • TGACCC
  • TCACCC
  • TCTCCC
  • TCTGCC
  • TCTGGC
  • TCTGGG
  • GGGTCT

Edit transcript

  • Rappresenta una particolare trasformazione di una stringa in un’altra

Distanza di edit: il problema

  • INPUT:
  • due sequenze S1 e S2 definite su un alfabeto 
  • 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)

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

Calcolo della distanza di edit

  • Si hanno tre possibilità per calcolare D(i,j), noto D(k,l) per k
  • il carattere ai va sostituito con il bj 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
  • il carattere bj va inserito e quindi:
  • Si hanno tre possibilità per calcolare D(i,j), noto D(k,l) per k
  • il carattere ai va sostituito con il carattere bj e quindi:
    • D(i,j) = D(i-1,j-1)+t(ai,bj)
  • il carattere ai va cancellato e quindi:
          • D(i,j) = D(i-1,j)+1
  • il carattere bj va inserito e quindi:
          • D(i,j) = D(i,j-1)+1
  • t(ai,bj)=1 se ai diverso da bj,
  • altrimenti t(ai,bj)=0


Condividi con i tuoi amici:
1   2   3   4   5


©astratto.info 2019
invia messaggio

    Pagina principale