Algorisme de Smith-Waterman

De Viquipèdia
Dreceres ràpides: navegació, cerca

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[modifica | modifica el codi]

Inicialment es construeix una matriu H de la manera següent:


H(i,0) = 0,\; 0\le i\le m


H(0,j) = 0,\; 0\le j\le n

H(i,j) = \max \begin{Bmatrix}
0 & \\
H(i-1,j-1) + \ w(a_i,b_j) & \text{Coincidencia/No-coincidencia} \\
H(i-1,j) + \ w(a_i,-) & \text{Delecio} \\
H(i,j-1) + \ w(-,b_j) & \text{Insercio}
\end{Bmatrix}
,\; 1\le i\le m, 1\le j\le 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[modifica | modifica el codi]

  • Seqüència 1 = ACACACTA
  • Seqüència 2 = AGCACACA
  • w(coincidència) = +2
  • w(a,-) = w(-,b) = w(no-coincidencia) = -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é[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. Smith TF, Waterman MS. «Identification of Common Molecular Subsequences». Journal of Molecular Biology, vol. 147, 1981, pàg. 195–197. DOI: 10.1016/0022-2836(81)90087-5.
  2. [enllaç sense format] http://fasta.bioch.virginia.edu/fasta_www2/fasta_down.shtml

Enllaços externs[modifica | modifica el codi]