Algorisme de Smith-Waterman

Taula de l'algoritme 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[1] 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.[2]

Funcionament de l'algorisme

Inicialment es construeix una matriu H {\displaystyle H} de la manera següent:

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

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

H ( i , j ) = max { 0 H ( i − 1 , j − 1 ) +   w ( a i , b j ) Coincidència/No-coincidència H ( i − 1 , j ) +   w ( a i , − ) Delecio H ( i , j − 1 ) +   w ( − , b j ) Insercio } , 1 ≤ i ≤ m , 1 ≤ j ≤ n {\displaystyle 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 Σ {\displaystyle \Sigma }
  • m = longitud(a)
  • n = longitud(b)
  • H ( i , j ) {\displaystyle 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 ∈ Σ ∪ { ′ − ′ } {\displaystyle 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

M a t r i x = ( − 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 ) {\displaystyle 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

  1. ↑ 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.
  2. ↑ «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.