3 Algoritmi dinamici

Algoritmi dinamici

Si possono produrre due tipologie di allineamento: allineamento globale (che prevede l'allineamento delle sequenze secondo la loro intera lunghezza), ed un allineamento locale (che non richiede che il confronto delle due sequenze sia svolto per l'intera lunghezza delle sequenze). L’allineamento locale torna utile quando si vogliono confrontare due geni, ad esempio, che sebbene appartengano a specie diverse potrebbero essere simili in corte regioni conservate e diversi nel resto della sequenza.

Un esempio sono i geni Homeobox (chiaramente omologhi) che hanno corte regioni chiamate omeodomini altamente conservate tra le diverse specie. Un allineamento globale non troverebbe gli omeodomini perché cercherebbe di allineare l’intera sequenza. È importante precisare che non necessariamente l’allineamento locale è un sottoinsieme di un allineamento globale. Spesso i due differiscono e il motivo per considerarli entrambi risiede proprio nella differente informazione che possono dare.

In generale, si considera in prima istanza l’allineamento locale, che poi viene confrontato con quello globale per cercare eventuali differenze. Un algoritmo che fa allineamenti globali è l’algoritmo di Needleman e Wunsch.

Di Needleman e Wunsch

Algoritmo

Needleman e Wunsch hanno proposto nel 1970 un metodo per poter effettuare allineamenti tra sequenze attraverso l’uso di algoritmi matematici. Il loro metodo originale ha subito delle modifiche nel corso degli anni, ma vediamo in cosa consisteva. Innanzitutto, essi disponevano le sequenze in una matrice, analogamente a quanto fatto per le matrici a punti. Quindi, in questa matrice, una sequenza viene disposta sulla prima riga, e l’altra viene disposta sulla prima colonna.

Utilizzavano poi un punteggio molto semplice: questo metodo di punteggio prevede di assegnare il valore “1” laddove i caratteri coincidono; laddove i caratteri non coincidono viene assegnato il valore “0”. Questa è la unitary scoring matrix, che si rivelò poco efficace nel mostrare similarità tra eventuali aminoacidi interscambiabili. Pertanto, questa matrice venne inizialmente utilizzata da Needleman e Wunsch, ma poi tale metodo venne rivisitato (vedi dopo). In questo modo si dice che inizializziamo la matrice.

Inizializzata la matrice, si dovrà calcolare il percorso che identificherà l’allineamento. Vediamo come si procede: si parte dal quadratino in alto a sinistra (indice 1,1); si considera poi la casella con indice (2,2). A questa casella si può arrivare solo in diagonale dalla casella (1,1). La regola che si applica è: sommare al valore presente nella casella con indice (2,2) il valore della casella di partenza con indice (1,1).

Si prende poi in considerazione la casella successiva, quella con indice (2,3). (RICORDA: il numero di sinistra dell’indice indica l’asse delle X, quindi la prima riga della matrice; mentre il numero di destra dell’indice indica l’asse delle Y, quindi la prima colonna della matrice.) I percorsi possibili per arrivare alla casella con indice (2,3) sono due: o partire dalla casella con indice (1,1) o p...