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.

Taula de l'algoritme Smith-Waterman.

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

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.