Algoritmo di Smith-Waterman

L'algoritmo di Smith–Waterman è un algoritmo di bioinformatica pensato per l'allineamento di sequenze, cioè la determinazione del grado di similarità (detta anche omologia) di sequenze nucleotidiche o proteiche.

Descrizione

L'algoritmo è stato proposto nel 1981 da Temple F. Smith e Michael S. Waterman^[1]. L'algoritmo si basa sulla programmazione dinamica ed è una variazione dell'algoritmo di Needleman-Wunsch (proposto qualche anno prima).

L'algoritmo calcola la distanza di edit fra due sequenze nel caso di allineamento locale. Nel caso generale le operazioni disponibili sono:

• corrispondenza (match) di due caratteri uguali
• sostituzione (substitution) di un carattere in un carattere diverso
• inserimento (insertion) di un carattere;
• cancellazione (deletion) di un carattere;

Per calcolare la distanza di edit si deve fornire un opportuno schema di costi. Uno schema di costi diffuso è la distanza di Levenshtein (in cui le operazioni di sostituzione, inserimento e cancellazione hanno costo 1). Si può usare uno schema più generale fornendo una matrice dei costi delle sostituzioni e delle penalità per i gap (che sono la diretta conseguenza di inserimenti e cancellazioni).

L'algoritmo utilizza una matrice come struttura dati ed opera in due fasi. Nella prima fase si compila la matrice ottenendo il punteggio del migliore allineamento. Nella seconda fase si opera un backtracking per recuperare la trasformazione (edit string) che permette di fare l'allineamento.

L'algoritmo

La matrice ${\displaystyle H}$ si costruisce nel seguente modo:

${\displaystyle H(i,0)=0,\;0\leq i\leq m}$

${\displaystyle H(0,j)=0,\;0\leq j\leq n}$

${\displaystyle {\text{ Se }}a_{i}=b_{j}}$ ${\displaystyle w(a_{i},b_{j})=w{\text{(Match)}}}$ ${\displaystyle {\text{ o se }}a_{i}!=b_{j}}$ ${\displaystyle w(a_{i},b_{j})=w{\text{(Substitution)}}}$

${\displaystyle H(i,j)=\max {\begin{Bmatrix}0\\H(i-1,j-1)+\ w(a_{i},b_{j})&{\text{Match/Substitution}}\\H(i-1,j)+\ w(a_{i},-)&{\text{Deletion}}\\H(i,j-1)+\ w(-,b_{j})&{\text{Insertion}}\end{Bmatrix}},\;1\leq i\leq m,1\leq j\leq n}$

Dove:

• ${\displaystyle a,b}$ = Sono le due stringhe nell'alfabeto ${\displaystyle \Sigma }$
• ${\displaystyle m={\text{length}}(a)}$
• ${\displaystyle n={\text{length}}(b)}$
• ${\displaystyle H(i,j)}$ - è il massimo punteggio di similarità fra il suffisso di a[1...i] e il suffisso di b[1...j]
• ${\displaystyle w(c,d),\;c,d\in \Sigma \cup \{'-'\}}$, '-' è lo schema delle penalità/punteggi dei gap