Algoritmo Smith-Waterman

El algoritmo de Smith-Waterman es una reconocida estrategia para realizar alineamiento local de secuencias biológicas (ADN, ARN o proteínas); es decir que determina regiones similares entre un par de secuencias.

Ejemplo del algoritmo de Smith-Waterman. Las flechas azules indican el camino en la matriz, las rojas el alineamiento óptimo

El algoritmo SW fue propuesto por Temple Smith y Michael Waterman en 1981.^[1] Está basado en el uso de algoritmos de programación dinámica, de tal forma que tiene la deseable propiedad de garantizar que el alineamiento local encontrado es óptimo con respecto a un determinado sistema de puntajes que se use (tales como matrices de substitución).

Las alternativas básicas para realizar el alineamiento de un par de secuencias son: el alineamiento local y el alineamiento global.

Los alineamientos globales pretenden alinear cada símbolo (o residuo) en cada secuencia. Esta estrategia es especialmente útil cuando las secuencias a alinear son altamente similares y aproximadamente del mismo tamaño. En contraste, los alineamientos locales son más útiles cuando las secuencias a alinear poseen grandes diferencias, pero se sospecha que existen regiones de similitud.

Algoritmo

Sean $A=a_{1}a_{2}...a_{n}$ y $B=b_{1}b_{2}...b_{m}$ las dos secuencias biológicas a alinear, cuyas longitudes son $n$ y $m$ respectivamente. La puntuación de similitud entre dos elementos $a$ y $b$ está dada por $s(a,b)$ . A cada eliminación de longitud $k$ se le asigna una penalización $W_{k}$ .

Para encontrar un par de segmentos con una gran similitud, se construye una matriz $H$ de $(n+1)$ × $(m+1)$ , inicializando la primera columna y primer fila con valores de $0$ .
$H_{k0}=H_{0l}=0\quad para\quad 0\leq k\leq n\quad y\quad 0\leq l\leq m$ .
Cada valor $H_{ij}$ representa la máxima similitud entre dos segmentos que terminan en $a_{i}$ y $b_{j}$ respectivamente. Dichos valores se obtienen de la siguiente relación de recurrencia:
$H_{ij}=\max {\begin{cases}H_{i-1,j-1}+s(a_{i},b_{j}),\\\max _{k\geq 1}\{H_{i-k,j}-W_{k}\},\\\max _{l\geq 1}\{H_{i,j-l}-W_{l}\},\\0\end{cases}}\qquad (1\leq i\leq n,1\leq j\leq m)$

donde

$H_{i-1,j-1}+s(a_{i},b_{j})$ es la puntuación de alinear $a_{i}$ y $b_{j}$ ,

$H_{i-k,j}-W_{k}$ es la puntuación si $a_{i}$ se encuentra al final de una eliminación de longitud $k$ ,

$H_{i,j-l}-W_{l}$ es la puntuación si $b_{j}$ se encuentra al final de una eliminación de longitud $l$ ,

$0$ indica que no existe alguna similitud entre $a_{i}$ y $b_{j}$ , se añade este valor para evitar valores negativos.
Para recuperar el par de segmentos con máxima similitud, se lleva a cabo un rastreo reverso a partir del máximo elemento de $H$ hasta terminar en un elemento cuyo valor sea igual a $0$ , siendo este el inicio de la alineación local óptima.

Complejidad algorítmica

El algoritmo de Smith-Waterman tiene una complejidad temporal de $O(nm^{2})$ y una complejidad espacial de $O(nm)$ . Esto representa una disminución considerable del costo computacional con respecto al enfoque de fuerza bruta, que tiene un tiempo de ejecución de $O(n^{3}m^{3})$ debido a que existen ${\binom {n}{2}}$ y ${\binom {m}{2}}$ subsecuencias de $A$ y $B$ respectivamente. No obstante, su complejidad representa una desventaja en comparación a la del algoritmo de Needleman-Wunsch,^[2] que tiene una complejidad lineal. Especialmente cuando el valor de $m$ es muy grande. Es por ello que se desarrollaron alternativas con un tiempo de ejecución lineal^[3]^[4] y otros con complejidad espacial lineal con respecto a $n$ .^[5]

Ejemplo

Sean $A$ :AAGGCT y $B$ :AACCCG las dos secuencias a alinear con una puntuación de similitud está dada por la siguiente relación:

$s(a_{i},b_{j})={\begin{cases}+1,\quad a_{i}=b_{j}\\-1,\quad a_{i}\neq b_{j}\end{cases}}$ .

La matriz de puntuación se inicializa con $0$ para todos los elementos de la primera columna y la primera fila. Después se calculan todas las puntuaciónes entre $a_{i}$ y $b_{j}$ , comenzando por $a_{1}$ y $b_{1}$ , denotado con amarillo en la siguiente matriz.

	A	A	C	C	C	G
	0	0	0	0	0	0
A	1
A
G
G
C
T

Una vez calculados todos los valores se busca el elemento con la máxima puntuación, denotado con verde.

	A	A	C	C	C	G
	0	0	0	0	0	0
A	1	1	0	0	0	0
A	1	2	1	0	0	0
G	0	1	1	0	0	1
G	0	0	0	0	0	1
C	0	0	1	1	1	0
T	0	0	0	0	0	0

Finalmente, para recuperar la alineación local óptima de $A$ y $B$ se lleva a cabo un rastreo a partir de ese elemento hasta llegar a un elemento con valor de $0$ .

	A	A	C	C	C	G
	0	0	0	0	0	0
A	1	1	0	0	0	0
A	1	2	1	0	0	0
G	0	1	1	0	0	1
G	0	0	0	0	0	1
C	0	0	1	1	1	0
T	0	0	0	0	0	0

La alineación resultante de este ejemplo consiste en alinear únicamente los primeros dos elementos de cada secuencia.

AA
||
AA

Penalización por huecos

Penalización lineal

La penalización por huecos sirve para determinar la puntuación de un indel, es decir, una inserción o una eliminación. El algoritmo de Smith-Waterman emplea una penalización lineal por extender la longitud de un hueco, donde la penalizacion $W_{k}$ depende únicamente de la longitud $k$ del hueco y del costo $w_{1}$ de un hueco de un solo espacio : $W_{k}=kw_{1}$ .

Huecos afines

Gotoh propuso un modelo de huecos afines, que consiste en modificar la penalizacion $W_{k}$ para que esta sea función de dos parámetros: $W_{k}=uk+v$ , donde $u$ es la penalización por extender un hueco, $v$ es la penalización por iniciar un hueco y $k$ es la longitud del hueco. Este esquema se reduce a la penalización lineal cuando $u=0$ . Este modelo ofrece dos ventajas: reducir el número de operaciones a $O(mn)$ y permitir que se asigne un costo más alto por iniciar un hueco que por extenderlo. La última propiedad tiene importantes implicaciónes biológicas ya que una simple mutación puede ocasionar varios cambios en un segmento de una secuencia, por lo tanto la creación de un hueco suele tener mayor impacto que su longitud. La disminución en el costo computacional del algoritmo de Gotoh se debe a que este intenta encontrar solo una de las alineaciónes locales óptimas y no garantiza encontrar alguna, a diferencia de Smith-Waterman que busca encontrar todas por lo que siempre encuentra la alineación óptima.

El algoritmo de Gotoh emplea tres matrices de $n\times m$ :

$D_{i,j}$ : puntuación por alinear $a_{i}$ y $b_{j}$ ,
$P_{i,j}$ : puntuación por alinear $a_{i}$ con un hueco,
$Q_{i,j}$ : puntuación por alinear $b_{j}$ con un hueco

Estas matrices tienen la siguiente inicialización:

$D_{0,j}=W_{j}$ ,
$D_{i,0}=W_{i}$ ,
$P_{0,j}=\infty$ ,
$Q_{j,0}=\infty$

Los valores de estas matrices se obtienen de las siguientes relaciones de recurrencia:

$D_{i,j}=\min {\begin{cases}D_{i-1,j-1}+s(a_{i},b_{j}),\\P_{i,j},\\Q_{i,j}\\\end{cases}}$

$P_{i,j}=\min {\begin{cases}D_{i-1,j}+W_{1},\\P_{i-1,j}+u\\\end{cases}}$

$Q_{i,j}=\min {\begin{cases}D_{i,j-1}+W_{1},\\Q_{i,j-1}+u\\\end{cases}}$

Huecos convexos

Waterman^[6] propuso otro sistema de penalización aún más flexible. A diferencia del modelo de huecos afines donde los costos de iniciar y extender un hueco son constantes, $u$ y $v$ respectivamente, en la penalización de huecos convexos el costo de extender el hueco disminuye a medida que aumenta su longitud: $W_{k+1}-W_{k}\leq W_{k}-W_{k-1}$ .

Véase también

Referencias

↑ Smith TF, Waterman MS (1981). «Identification of common molecular subsequences.». J Mol Biol. 147 (1): 195-7. PMID 7265238. [1]
↑ Saul B. Needleman; Christian D. Wunsch (1970). «A general method applicable to the search for similarities in the amino acid sequence of two proteins». Journal of Molecular Biology 48 (3): 443-453. PMID 5420325. doi:10.1016/0022-2836(70)90057-4.
↑ Osamu Gotoh (1982). «An improved algorithm for matching biological sequences». Journal of Molecular Biology 162 (3): 705-708. PMID 7166760. doi:10.1016/0022-2836(82)90398-9. «10.1.1.204.203».
↑ Stephen F. Altschul & Bruce W. Erickson (1986). «Optimal sequence alignment using affine gap costs». Bulletin of Mathematical Biology 48 (5–6): 603-616. PMID 3580642. S2CID 189889143. doi:10.1007/BF02462326.
↑ Miller, Webb; Myers, Eugene (1988). «Optimal alignments in linear space». Bioinformatics 4 (1): 11-17. PMID 3382986. doi:10.1093/bioinformatics/4.1.11. «10.1.1.107.6989».
↑ Michael S. Waterman (1984). «Efficient Sequence Alignment Algorithms». Journal of Theoretical Biology 108: 333-337. doi:10.1016/s0022-5193(84)80037-5.

Enlaces externos

Una implementación en Java

Datos: Q1683352
Multimedia: Smith–Waterman algorithm / Q1683352

[1] Smith TF, Waterman MS (1981). «Identification of common molecular subsequences.». J Mol Biol. 147 (1): 195-7. PMID 7265238. [1]

[Needleman1970-2] Saul B. Needleman; Christian D. Wunsch (1970). «A general method applicable to the search for similarities in the amino acid sequence of two proteins». Journal of Molecular Biology 48 (3): 443-453. PMID 5420325. doi:10.1016/0022-2836(70)90057-4.

[Gotoh1982-3] Osamu Gotoh (1982). «An improved algorithm for matching biological sequences». Journal of Molecular Biology 162 (3): 705-708. PMID 7166760. doi:10.1016/0022-2836(82)90398-9. «10.1.1.204.203».

[Altschul1986-4] Stephen F. Altschul & Bruce W. Erickson (1986). «Optimal sequence alignment using affine gap costs». Bulletin of Mathematical Biology 48 (5–6): 603-616. PMID 3580642. S2CID 189889143. doi:10.1007/BF02462326.

[Myers1988-5] Miller, Webb; Myers, Eugene (1988). «Optimal alignments in linear space». Bioinformatics 4 (1): 11-17. PMID 3382986. doi:10.1093/bioinformatics/4.1.11. «10.1.1.107.6989».

[Waterman1984-6] Michael S. Waterman (1984). «Efficient Sequence Alignment Algorithms». Journal of Theoretical Biology 108: 333-337. doi:10.1016/s0022-5193(84)80037-5.

[1]

[2]

[3]

[4]

[5]

[6]