Allineamento locale: algoritmo di Smith-Waterman

Quando si hanno parentele evolutive molto lontane, oppure quando una sequenza nasce come fusione di due altre sequenze, o ancora se si vogliono ricercare similaritá tra zone di interesse funzionale, gli algoritmi sopra esposti non sono adatti, in quanto sono stati svilippati per cercare l'insieme di operazioni che abbia costo minimo (o massimo punteggio) per trasformare una sequenza nell'altra.

Per poter quindi riuscire ad evidenziare soltanto le sottosequenze (se esistono) che abbiano un punteggio elevato, senza dover penalizzare questo risultato con i mismatch o i gap che possiamo avere con le altre parti delle due sequenze, occorre modificare il nostro modo di procedere.

Un esempio pratico è dato dalle sequenze "ALACVKTTTSV" e "LACV". Essendo la seconda totalmente contenuta nella prima, un algoritmo che cercasse di trasformare una nell'altra si troverebbe necessariamente a dover procedere con solo cancellazioni (o inserimenti). Questo potrebbe portare ad avere che la prima sequenza ("ALACVKTTTSV") sia considerata più simile alla sequenza "LGCTPSV", solo perché la differenza in lunghezza è minore tra queste ultime. Mentre se valutiamo gli allineamanti

Caso "ALACVKTTTSV" e "LACV"

s: LACVKTTTSV

m: ||||......

t: LACV---

Caso "ALACVKTTTSV" e "LGCTPSV"

s: LACVKTTTSV

m: |.|...|.||

t: LGC--TPSV

si nota che nel primo caso esiste una forte similarità locale.

Smith a Waterman (vedi per esempio [4], [11]), introdussero una modifica nell'algoritmo precedente che permette di calcolare la massima similarità locale. L'idea di base è di agire sia sulla parte di inizializzazione, che su quella del calcolo della ricorrenza. Più un dettaglio, si vuole ottenere di

1. non dare peso ai gap agli estremi (iniziali e finali)
2. poter ripartire da capo se trovo una regione di alta similarità preceduta da una regione a bassa similarità

Ricordandosi il significato del riempimento della prima riga e della prima colonna, diviene evidente, che per poter evitare di pesare negativamente i gap iniziali basta porre a zero tutti gli elementi di tali riga e colonna. Ossia

$$C[i][0]=C[0][j]=0 \quad \forall i=1,..len(s) \quad and \quad j=1,..len(t)$$ (8.3)

Per quanto riguarda il secondo punto, l'idea è quella di poter ripartire, nel caso il massimo valore sia comunque $<0$. Da cui

$$C[i][j]=max\{0, C[i-1][j-1]+M(i,j),C[i-1][j]+g,C[i][j-1]+g\}$$ (8.4)

Adesso abbiamo bisogno, secondo l'Equazione , di calcolare il massimo tra 4 valori, ed un esempio in Python è riportato in Figura

Figura: Esempio di funzione per il calcolo del massimo tra 4 valori (max4)

    
Score Matrix
    

Tabella: Le matrici di Score e backtrace per le sequenze "FKLARR" e "TTAAAFKSTLAR"

	0	T	T	A	A	A	F	K	S	T	L	A	R
0	0	0	0	0	0	0	0	0	0	0	0	0	0
F	0	0	0	0	0	0	1.0	0.0	0	0	0	0	0
K	0	0	0	0	0	0	0.0	2.0	1.0	0.0	0	0	0
L	0	0	0	0	0	0	0	1.0	1.0	0.0	1.0	0.0	0
A	0	0	0	1.0	1.0	1.0	0.0	0.0	0.0	0.0	0.0	2.0	1.0
R	0	0	0	0.0	0.0	0.0	0.0	0	0	0	0	1.0	3.0
R	0	0	0	0	0	0	0	0	0	0	0	0.0	2.0

    
    
    
Backtrace Matrix
    

	0	T	T	A	A	A	F	K	S	T	L	A	R
0	0	0	0	0	0	0	0	0	0	0	0	0	0
F	0	0	0	0	0	0	D	R	0	0	0	0	0
K	0	0	0	0	0	0	C	D	R	R	0	0	0
L	0	0	0	0	0	0	0	C	D	D	$\nwarrow$D	R	0
A	0	0	0	D	D	D	R	C	D	D	C	$\nwarrow$D	R
R	0	0	0	C	D	D	D	0	0	0	0	C	$\nwarrow$D
R	0	0	0	0	0	0	0	0	0	0	0	C	D

    
    
    
Best Local Alignment with score 3.0
    
    

s: LAR

t: LAR

Ovviamente esiste una differenza fondamentale, tra l'Algoritmo di Smith-Waterman e quello precedente, che è il fatto di considerare l'eventuale allineamento che parte dalla posizione del massimo trovato, e di farlo terminare quando si raggiunge la soglia assegnata (tipicamente posta =0). Come esempio del funzionamento dell'algoritmo in Tabella è riportato il calcolo delle sequenze "FKLARR" e "TTAAAFKSTLAR". In tale figura, il calcolo è stato ottenuto utilizzando le Equazioni e , con valore del gap=-1 e valore del match =+1 se i due simboli sono uguali oppure -1 per simboli differenti.

Per concludere questo paragrafo riportiamo in figura l'algoritmo per il calcolo della massima similarità locale e in il corrispondente algoritmo per estrarre un allineamento locale con la massima similarità.