# Algorisme de Smith-Waterman

L'algorisme de Smith-Waterman és un dels algorismes més emprats per a l'alineament local de seqüències proteiques o nucleotídiques, i en permet determinar les regions de major similitud. La primera versió d'aquest algorisme va ser proposada per Temple Smith i Michael Waterman el 1981 i, de forma similar a l'algorisme de Needleman-Wunsch, es tracta d'un algorisme de programació dinàmica que garanteix que l'alineament trobat és òptim.
Una implementació de l'algorisme de Smith-Waterman, SSEARCH, es troba disponible en el programa d'anàlisi de seqüències FASTA.

## Funcionament de l'algorisme

Inicialment es construeix una matriu $H$ de la manera següent:
$H(i,0)=0,\;0\leq i\leq m$
$H(0,j)=0,\;0\leq j\leq n$
$H(i,j)=\max {\begin{Bmatrix}0&\\H(i-1,j-1)+\ w(a_{i},b_{j})&{\text{Coincidència/No-coincidència}}\\H(i-1,j)+\ w(a_{i},-)&{\text{Delecio}}\\H(i,j-1)+\ w(-,b_{j})&{\text{Insercio}}\end{Bmatrix}},\;1\leq i\leq m,1\leq j\leq n$
On:
* a, b = Mots de l'alfabet $\Sigma$
* m = longitud(a)
* n = longitud(b)
* $H(i,j)$ - és el màxim Similitud-Puntuació entre un submot de a amb una longitud i, i un submot de b amb una longitud j
* $w(c,d),\;c,d\in \Sigma \cup \{'-'\}$, '–' correspon a buit en la seqüència

## Exemple

* Seqüència 1 = ACACACTA
* Seqüència 2 = AGCACACA
* w(coincidència) = +2
* w(a,-) = w(-,b) = w(no-coincidència) = -1
$Matrix={\begin{pmatrix}&-&A&C&A&C&A&C&T&A\\-&0&0&0&0&0&0&0&0&0\\A&0&2&1&2&1&2&1&0&2\\G&0&1&1&1&1&1&1&0&1\\C&0&0&3&2&3&2&3&2&1\\A&0&2&2&5&4&5&4&3&4\\C&0&1&4&4&7&6&7&6&5\\A&0&2&3&6&6&9&8&7&8\\C&0&1&4&5&8&8&11&10&9\\A&0&2&3&6&7&10&10&10&12\\\end{pmatrix}}$
Per obtenir l'alineament local òptim, es parteix de la posició (i,j) que conté el valor més gran elevat. A continuació, es passa d'aquest valor al valor més gran entre les posicions veïnes (i-1,j), (i,j-1), i (i-1,j-1). (En cas d'empat, el moviment diagonal és el prioritari). Aquest procés continua iterativament fins que s'arriba a la posició (0,0). A l'exemple anterior, el valor més gran de la matriu correspon a la posició (8,8) i a partir d'aquí es mou per les posicions (8,8), (7,7), (7,6), (6,5), (5,4), (4,3), (3,2), (2,1), (1,1), i (0,0),
Un cop finalitzat el recorregut per la matriu, l'alineament es reconstrueix a partir de l'últim valor seguint el camí definit anteriorment fins a assolir la posició inicial (i,j). Un salt en diagonal implica un alineament ja sigui una coincidència (match) o una no-coincidència (mismatch), mentre que un salt vertical implica una deleció, i un salt horitzontal implica una inserció.
Seguint l'exemple anterior, s'obté el següent alineament:
* Seqüència 1 = A-CACACTA
* Seqüència 2 = AGCACAC-A

## Vegeu també

* BLAST

## Referències

* ↑ Smith TF, Waterman MS «Identification of Common Molecular Subsequences». Journal of Molecular Biology, 147, 1981, pàg. 195–197. DOI: 10.1016/0022-2836(81)90087-5.
* ↑ «UVa FASTA Downloads». virginia.edu. [Consulta: 2 gener 2017].

## Enllaços externs

* JAligner — Implementació de l'algorisme de Smith-Waterman en Java.
* B.A.B.A. — Explicació del funcionament de l'algorisme de Smith-Waterman.
* FASTA/SSEARCH at the Pàgina web amb els serveis FASTA i SSEARCH de l'EBI.
* UGENE Smith-Waterman plugin Arxivat 2009-04-19 a Wayback Machine. — Implementació de SSEARCH amb una interfície gràfica.