Nelle pagine precedenti sono stati affrontati alcuni problemi relativi all'analisi di similarità di sequenze e sono state sollevate diverse domande sugli algoritmi di allineamento a cui non è ancora stata data una risposta. In questo paragrafo inizieremo ad analizzare gli algoritmi esatti di allineamento che determinano il migliore allineamento possibile tra due sequenze in base a una determinata matrice di sostituzione e a un criterio di penalità da attribuire ad ogni gap inserito.
Needleman e Wunsch nel 1970 furono i primi a risolvere il problema con un algoritmo in grado di trovare similarità globali in un tempo proporzionale al prodotto delle lunghezze delle due sequenze. Successivamente, nel 1981, Smith e Waterman svilupparono un nuovo algoritmo in grado di individuare anche similarità locali (paragrafo successivo). Il processo dell'algoritmo di Needleman e Wunsch verrà diviso schematicamente in tre fasi successive per illustrarne la logica:
- PRIMA FASE: Invece che colorare le caselle con intensità diverse di grigio, si dovranno porre all'interno di ogni casella i valori ottenuti da una matrice di sostituzione, come illustrato nell'esempio 1 sottostante in cui questi valori (score) sono riportati in colore, nell'angolo in alto a sinistra di ogni casella. La matrice di sostituzione usata nell'esempio è una matrice normalizzata in modo da contenere solo score positivi, che consentirà di trovare il migliore allineamento globale.
- SECONDA FASE: Viene cercato il miglior allineamento considerando la possibilità di inserimento di gap. L'obiettivo è quello di trovare il percorso tra le caselle della matrice di allineamento che totalizza il massimo punteggio in base alle regole stabilite. I salti tra una diagonale e la diagonale contigua corrispondono all'inserzione di un gap e dovranno essere penalizzati di conseguenza.
- TERZA FASE: Viene cercata la casella con il punteggio massimo (cerchiato nell'esempio) e si procede a ritroso per ricavare i singoli appaiamenti (valori evidenziati su sfondo grigio nell'esempio).
Esempio 1:
Allineamento globale. Le due sequenze da allineare sono poste ai margini superiore e sinistro della matrice e scritte rispettivamente da sinistra a destra e dall'alto in basso. I numeri colorati posti in alto a sinistra in ogni casella indicano gli score dei singoli appaiamenti. I numeri scritti in nero indicano il punteggio massimo ottenibile fino a quella casella, attribuendo 5 punti di penalità sia all'apertura sia all'estensione dei gap. Il migliore allineamento può essere trovato partendo dalla casella col punteggio massimo (66) e procedendo a ritroso seguendo il percorso indicato dalle frecce Gli appaiamenti corrispondenti al migliore allineamento globale sono evidenziati in grigio.
E' stato già discusso il fatto che i modi in cui è possibile inserire un gap sono troppi per potere considerare indipendente tutti i percorsi ipotizzabili.
La soluzione a questo problema deriva da alcune semplici considerazioni che hanno permesso di applicare una strategia di programmazione dinamica. La prima considerazione è che se una sequenza è scritta da sinistra a destra sul lato superiore della matrice e l'altra dall'alto in basso sul lato sinistro, allora qualsiasi percorso valido deve mantenere sempre una direzione tendenziale che va dall'angolo in alto a sinistra a quello in basso a destra. Nonostante una casella sia circondata da 8 caselle, un percorso valido potrà proseguire soltanto verso 3 delle 8 caselle contigue, come illustrato nell'esempio 2 sottostante (le frecce nere indicano le direzioni consentite). Per arrivare al punto colorato nel riquadro destro della figura, un percorso valido potrà essere originato solo da una delle 3 caselle con il punto di domanda.
Conoscendo il valore delle tre possibili caselle a monte di una posizione è possibile calcolare da quale delle 3 sia più vantaggioso far provenire il percorso.
Esempio 2. Il percorso all’interno di una matrice di allineamento deve seguire delle regole. Le direzioni indicate dalle frecce colorate nel riquadro di sinistra non hanno senso e quindi non sono consentite. Allo stesso modo, nel pannello di destra, per raggiungere la casella con il punto in colore il percorso può provenire solo da una delle tre caselle con il punto di domanda.
Un'ulteriore considerazione consente di semplificare enormemente il problema: il migliore percorso a monte resta comunque lo stesso, qualunque sia il percorso a valle di una determinata casella. Quindi, partendo dalla prima casella in alto a sinistra è possibile procedere una casella alla volta verso destra fino all'ultima colonna, poi nella riga successiva, come se si leggesse una pagina di un libro. A ogni casella conosceremo sempre il punteggio delle tre caselle da cui può provenire un percorso valido. Procedendo fino alla fine determineremo la casella con il punteggio massimo. Questa strategia algoritmica di calcolare i valori man mano che si procede, e di utilizzarli poi per le fasi successive, viene chiamata "programmazione dinamica".