Giovanni Paolella » 10.Algoritmi dinamici di allineamento

Matrici di punti e allineamenti

L’allineamento mediante matrice di punti descritto precedentemente permette l’identificazione del path ottimale unendo segmenti di diagonale corrispondenti alle regioni di maggiore similarità (figura A). Bisogna notare però che l’algoritmo non produce direttamente l’allineamento ma piuttosto una rappresentazione grafica delle similarità tra due sequenze che viene poi di fatto processata dal ricercatore; un vero algoritmo di allineamento dovrebbe invece calcolare l’allineamento migliore. Questo risulta tanto più importante quando la dimensione delle matrici cresce al crescere delle sequenze. Inoltre non è sempre immediatamente evidente quale sia la o le diagonali corrispondenti all’allineamento migliore. Prova a cercarlo in figura B, noterai che non è tanto facile trovarlo.

Un path è un allineamento

L’allineamento ha la forma di un tratto di diagonale quando esiste similarità per un numero consistente di residui consecutivi. Se però i tratti di similarità sono piuttosto corti, l’allineamento assume un aspetto piu’ tortuoso, come quello rappresentato nella figura A.

Più generalmente, quindi, un allineamento ha la forma di un percorso (path) più o meno tortuoso, che, partendo da un punto del margine sinistro o di quello superiore, raggiunge un punto del margine inferiore o destro della matrice.

Lungo questo percorso, i tratti in diagonale rappresentano zone di allineamento, mentre i salti di diagonale, rappresentano inserzioni o delezioni in una delle sequenze (gap).

E’ sempre possibile rappresentare un percorso di questo tipo sotto forma di allineamento. Prova a convertire in un allineamento il path indicato nella matrice e confronta il tuo risultato con quello di figura B.

Come trovare l’allineamento ottimale

Nella precedente lezione sugli allineamenti, è stato proposto che il modo più semplice di trovare l’allineamento ottimale consiste nel calcolare un punteggio per tutti gli allineamenti possibili e scegliere quello che ha il punteggio più elevato.

Nella matrice riportata in figura, in aggiunta all’allineamento indicato nella pagina precedente, esistono naturalmente molti altri allineamenti possibili, in figura sono indicati quattro di questi e non è immediatamente evidente quale di questi sia il migliore.

Il primo problema è infatti quello di trovare un modo per calcolare il punteggio; finora abbiamo utilizzato un metodo piuttosto semplice che consiste nel contare il numero di residui identici. Applicando questo metodo, l’allineamento in alto a destra (p=6) in figura risulta migliore di quello in basso a sinistra (p=4), ma, se sottraiamo 1 punto per ogni gap (-1), i due punteggi diventano uguali, e l’allineamento di sinistra diventa addirittura migliore se si stabilisce che un gap vale -2. Prova a verificare questi punteggi nella figura e a calcolare quelli degli altri due allineamenti indicati attribuendo ai gap il valore -1. Quale sia il migliore allineamento dipende quindi fortemente dai criteri utilizzati per calcolare il punteggio, ed è quindi molto importante fare attenzione alla scelta di questi criteri.

Quanti sono i path?

In maniera indipendente dalla scelta dei criteri utilizzati per il calcolo del punteggio, è però necessario definire la lista degli allineamenti possibili.

In figura A sono rappresentati gli allineamenti già analizzati in precedenza, ma quelli possibili sono in realtà molti di più. In figura B ne sono indicati ad esempio altri due. Nota che uno stesso residuo può essere parte di allineamenti alternativi: in figura, due allineamenti condividono i primi due residui, altri due solo il primo.

Alla luce di queste considerazioni, appare chiaro che il numero degli allineamenti possibili è molto più alto del numero di diagonali, e che cresce molto velocemente al crescere delle dimensioni della matrice.

Non tutti i path però costituiscono allineamenti possibili: i due allineamenti tratteggiati in figura C non vanno considerati, perchè prevedono il riutilizzo degli stessi residui in posizioni diverse. Prova a convertirli in allineamenti per capire il problema.

Path da un punto

Per una qualsiasi casella della matrice, ad esempio quella cerchiata in figura A, passano molti path; tuttavia, se ci limitiamo a pensare a quelli che proseguono a partire da quella indicata, ci rendiamo conto che essi devono tutti proseguire entrando all’interno del rettangolo indicato.

In pratica il path può continuare nella casella immediatamente in basso a destra (senza introdurre gap), oppure in una di quelle alla destra di quest’ultima, introducendo così uno o più gap nella sequenza posta in verticale, oppure ancora in una di quelle sotto di essa introducendo gap nella sequenza orizzontale.

Questo è vero per qualsiasi altra casella della matrice, come ad esempio l’altra casella cerchiata in figura B che, in maniera simile, può continuare solo nel rettangolo posto in basso a destra di essa.

Needlemann e Wunsch

Per calcolare il punteggio è utile sostituire gli asterischi con dei valori numerici, ad esempio inserendo il numero 1 al loro posto e zero o nulla negli altri (figura A).

Nell’algoritmo di Needlemann e Wunsch, in ciascuna casella, questo numero viene sostituito da valori che corrispondono al punteggio del miglior path, tra quelli che, passando per quella casella, proseguono fino alla fine della matrice concludendosi sul suo margine destro o inferiore. Ricordando che i path possibili continuano solo all’interno del rettangolo posto in basso e a destra della casella stessa, basta trovare, nel rettangolo, il valore più alto, che si troverà lungo i margini alto e sinistro, e sommarlo al valore contenuto nella casella in esame, come indicato nella figura B. In questo modo questi valori possono essere calcolati per tutta le caselle della matrice, partendo dall’angolo in basso a destra e proseguendo fino ai margini superiore e sinistro. Si ottiene così la matrice in figura C.

Needle

Dal path ottimale all’allineamento

Per determinare il path ottimale, si procede a partire dai margini superiore e sinistro della matrice, selezionando la casella con il punteggio maggiore che sarà quella dove termina il miglior path. A partire da questa, si procede entrando nei rettangoli via via più piccoli scegliendo sempre il valore più elevato e terminando in una delle caselle al margine inferiore o destro. Il path così determinato corrisponde all’allineamento ottimale. Nota che in qualche rettangolo potrebbero esserci più caselle contenenti il valore più elevato, in questo caso il path si ramifica ed è poi possibile seguire i diversi rami; tutti questi path avranno però lo stesso punteggio che corrisponde al quello più elevato.

Un approccio alternativo

Un modo alternativo di procedere consiste nel rappresentare i gap come un passo in verticale o in orizzontale, piuttosto che come un salto. Così facendo il calcolo risulta notevolmente semplificato, perchè basta considerare tre sole caselle, quella adiacente lungo la stessa riga, quella adiacente lungo la stessa colonna e quella ad una riga e ad una colonna di distanza. Nell’esempio riportato in figura, il calcolo è effettuato in maniera inversa a quella precedente, partendo dall’angolo in alto a sinistra. In pratica, ogni casella può essere raggiunta camminando in verticale o in orizzontale, con l’introduzione di un gap, o in diagonale, allungando l’allineamento. Solo in quest’ultimo caso il valore della casella potrà essere sommato al punteggio accumulato finora. Dei tre punteggi ottenibili in questo modo, viene scelto quello più elevato (vedi figura A a sinistra). Se al gap non si associa un punteggio, il risultato è funzionalmente identico a quello ottenuto con il metodo precedente, figura B. Se invece si da un valore negativo all’introduzione dei gap, si sfavorisce la loro introduzione, come indicato in precedenza in questa lezione. In figura C, le stesse sequenze producono un allineamento meno tortuoso perchè l’aggiunta del gap è stata associata ad un valore di -5.

Smith e Watermann

L’introduzione di valori negativi pone il problema di come gestire tratti relativamente lunghi privi di identità significativa. Usando i metodi descritti finora, il punteggio può diventare anche molto inferiore allo zero. Smith e Watermann hanno introdotto un ulteriore confronto, inserendo il valore zero tra quelli da confrontare, per cercare il valore da inserire nella casella. Se gli altri punteggi sono inferiori allo zero, questo significa che la casella assumerà il valore zero e non un valore negativo, in questo modo, il valore di ogni casella non dipenderà più dal punteggio accumulato lungo tutto il percorso, ma solo da quello accumulato a partire da quando il punteggio ha superato lo zero. In sostanza punteggi elevati indicheranno regioni di similarità locale, piuttosto che l’allineamento globale delle due sequenze.

Allineamento locale

La ricerca di allineamenti locali è importante quando si cerca di identificare delle piccole regioni di similarità tra due sequenze.

Se si osserva l’allineamento indicato in alto in figura A, si nota che la similarità è piuttosto elevata, ma è limitata alla sola regione centrale. Essendo la similarità piuttosto estesa rispetto alla sequenza totale, questo allineamento sara’ comunque il migliore e quindi facilmente identificato.

Diversamente, nel caso dei due allineamenti indicati in basso, quello superiore contiene una regione di similarità interessante, ma piuttosto piccola, che non è in grado di contribuire significativamente all’allineamento globale. Un algoritmo di allineamento globale preferirebbe il secondo allineamento, che ha 17 match, e perderebbe quello superiore che ne ha 14. Un algoritmo di allineamento locale, invece, identifica correttamente la regione di identità. Infatti, come si vede in figura B in basso, l’azzeramento del punteggio ogni volta che questo scende sotto lo zero, permette alla regione di similarita’ di diventare visibile come valori positivi.