Programmazione Dinamica PDF

PROGRAMMAZIONE DINAMICA L’allineamento globale sfrutta la programmazione dinamica per cercare di ridurre il tempo di calcolo, perché le sequenze più sono lunghe e più tempo ci vorrà. La programmazione dinamica viene usata per rendere i tempi di calcolo più brevi e utilizza le matrici. Quindi divide...

PROGRAMMAZIONE DINAMICA L’allineamento globale sfrutta la programmazione dinamica per cercare di ridurre il tempo di calcolo, perché le sequenze più sono lunghe e più tempo ci vorrà. La programmazione dinamica viene usata per rendere i tempi di calcolo più brevi e utilizza le matrici. Quindi divide un problema in sottoproblemi in modo tale che l’algoritmo ricordi la soluzione di ogni sottoproblema fino ad arrivare allo scopo finale. La programmazione dinamica prende un problema più complesso e grande, lo spezzetta in sottoproblemi più piccoli e affrontabili dal punto di vista computazionale e memorizza ogni volta la soluzione al sottoproblema in modo che ogni volta che l’algoritmo incontra quel sottoproblema non deve ricalcolare il sottoproblema ma ce l’ha già memorizzato, accorciando i tempi. La memorizzazione dei sottoproblemi avviene sottoforma di MATRICI. Una matrice non è altro che una tabella in cui sono riportate delle informazioni. Dato che, nel nostro caso, le informazioni sono riportate sottoforma di numeri, creiamo una matrice di numeri casuali. Possiamo associare alle righe un indice (generalmente indicato dalla lettera ‘’i’’) che indica il numero della riga, allo stesso modo possiamo creare un indice (generalmente indicato dalla lettera ‘’j’’) per le colonne. L’elemento che si trova nell’intersezione tra la riga i e la colonna j è indicato con A(i,j), dove ‘’A’’ è il ‘’nome’’ che diamo alla matrice. La matrice viene utilizzata dalla programmazione dinamica per memorizzare tutti i possibili allineamenti tra due sequenze. Dopo aver creato la matrice bisogna calcolare il punteggio di similarità per ogni cella. Per calcolare quello della cella azzurra dobbiamo vedere le celle adiacenti. Questi punteggi vengono calcolati dai punteggi già presenti in matrice. Si prende quasi sempre in considerazione la cella in diagonale, riquadro viola; se nel riquadro azzurro c’è lo stesso nucleotide tra le righe e le colonne viene dato il bonus identità +1 (se non fossero stati uguali bisognava sommare 0). La prima riga e la prima colonna va riempita con gli zeri. Per l’1 più a destra della cella celeste si mette 1 perché si è preso il punteggio più alto (si prende in considerazione solo il maggiore dei tre) della cella adiacente (quella celeste) aggiungendo 0 perché la A e la G non sono uguali. Questa è la regola del massimo, con questo si vedono tutti i possibili allineamenti di due sequenze. Nel caso di allineamento globale di una sequenza il punteggio migliore sarà sempre nell’ultima cella in basso a destra. Per capire come si fa ad ottenere il punteggio massimo bisogna effettuare la procedura del TRACEBACK, questo ci permette di tracciare a ritroso il percorso. Si parte dal 7 e si applica di nuovo la legge del massimo nelle cellule adiacenti, quindi ci si muove in su. Poi si riparte ricercando il valore massimo. A parità di valore si predilige sempre la diagonale. Facendo questo percorso capiamo qual è il migliore allineamento tra le due sequenze. Dopodiché il risultato bisogna scriverlo sottoforma di stringhe. Il movimento in diagonale corrisponde a match, un movimento in orizzontale corrisponde a un gap sulle righe, mentre quando mi sposto in verticale c’è un gap nelle colonne. Così si riproduce l’allineamento migliore.  ALLINEAMENTO GLOBALE Il globale si usa quando si vuole sapere se due sequenze sono molto simili. Per pagare il costo della gap penalty bisogna inizializzare le righe e le colonne con i numeri da 0-9/10/11… La colonna e la riga relative ai gap vengono inserite nell’eventualità che l’allineamento delle sequenze inizi con un gap. Inserendo una riga di gap e inizializzandola a 0 possiamo assicurarci che questa opzione possa essere valutata dall’algoritmo. In questo caso le cose si complicano perché la procedura del traceback non è ovvia come prima perché potrebbero esserci più caselle che hanno il punteggio migliore. Facciamo sempre il traceback partendo dalla cella in basso a destra per arrivare, grazie al percorso a ritroso, alla cella in alto a sinistra. La * indica un mismatch: due simboli diversi allineati. Il discorso del missmatch/match è facile per le basi perché o avviene o meno, nel caso degli amminoacidi è un po’ più complicato. Per questo motivo si utilizzano le matrici di sostituzione inventate dalla Dayhoff. L’allineamento globale per le sequenze amminoacidiche utilizza le MATRICI DI SOSTITUZIONE, queste servono per vedere le posizioni in cui gli amminoacidi sono conservai o sostituiti. La Dayhoff e il suo team hanno identificato sequenze proteiche omologhe, ovvero sequenze che condividono una comune origine filogenetica. L'allineamento di queste sequenze omologhe è stato eseguito per evidenziare le posizioni in cui gli amminoacidi sono conservati (simili) o sostituiti (diversi). Osservando le sequenze allineate, hanno calcolato le frequenze di sostituzione tra gli amminoacidi. Dai dati raccolti dalla Dayhoff venne calcolata la probabilità di trovare un amminoacido sostituito da un altro ogni 100 amminoacidi. Dati due amminoacidi ‘’a’’ e ‘’b’’ calcolarono: M(a, b) = la probabilità di trovare ‘’a’’ e ‘’b’’ allineati ogni 100 amminoacidi nelle sequenze studiate. Si tratta della frequenza osservata degli allineamenti di ‘’a’’ e ‘’b’’. C(a, b) = la probabilità di trovare ‘’a’’ e ‘’b’’ ogni 100 amminoacidi per semplice effetto del caso. Si tratta di una stima che può essere calcolata moltiplicando le frequenze dell’amminoacido ‘’a’’ e dell’amminoacido ‘’b’’ (fa * fb) Il punteggio di sostituzione, dato dalla formula per calcolare una probabilità di un amminoacido sostituito ogni 100 amminoacidi: Quando M è tanto maggiore di C, stando al numeratore, si otterrà che il punteggio>1, se, invece C>M il punteggio sarà