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.

El algoritmo SW fue propuesto por Temple Smith y Michael Waterman en 1981.​ 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 ${\displaystyle A=a_{1}a_{2}...a_{n}}$ y ${\displaystyle B=b_{1}b_{2}...b_{m}}$ las dos secuencias biológicas a alinear, cuyas longitudes son ${\displaystyle n}$ y ${\displaystyle m}$ respectivamente. La puntuación de similitud entre dos elementos ${\displaystyle a}$ y ${\displaystyle b}$ esta dada por ${\displaystyle s(a,b)}$. A cada eliminación de longitud ${\displaystyle k}$ se le asigna una penalización ${\displaystyle W_{k}}$.

1. Para encontrar un par de segmentos con una gran similitud, se construye una matriz ${\displaystyle H}$ de ${\displaystyle (n+1)}$×${\displaystyle (m+1)}$, inicializando la primera columna y primer fila con valores de ${\displaystyle 0}$.

   ${\displaystyle H_{k0}=H_{0l}=0\quad para\quad 0\leq k\leq n\quad y\quad 0\leq l\leq m}$.

2. Cada valor ${\displaystyle H_{ij}}$ representa la máxima similitud entre dos segmentos que terminan en ${\displaystyle a_{i}}$ y ${\displaystyle b_{j}}$ respectivamente. Dichos valores se obtienen de la siguiente relación de recurrencia:

   ${\displaystyle 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

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

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

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

   ${\displaystyle 0}$ indica que no existe alguna similitud entre ${\displaystyle a_{i}}$ y ${\displaystyle b_{j}}$, se añade este valor para evitar valores negativos.

3. Para recuperar el par de segmentos con máxima similitud, se lleva a cabo un rastreo reverso a partir del máximo elemento de ${\displaystyle H}$ hasta terminar en un elemento cuyo valor sea igual a ${\displaystyle 0}$, siendo este el inicio de la alineación local óptima.

Complejidad algorítmica

El algoritmo de Smith-Waterman tiene una complejidad temporal de ${\displaystyle O(nm^{2})}$ y una complejidad espacial de ${\displaystyle 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 ${\displaystyle O(n^{3}m^{3})}$ debido a que existen ${\displaystyle {\binom {n}{2}}}$ y ${\displaystyle {\binom {m}{2}}}$subsecuencias de ${\displaystyle A}$ y ${\displaystyle B}$ respectivamente. No obstante, su complejidad representa una desventaja en comparación a la del algoritmo de Needleman-Wunsch,​ que tiene una complejidad lineal. Especialmente cuando el valor de ${\displaystyle m}$ es muy grande. Es por ello que se desarrollaron alternativas con un tiempo de ejecución lineal​​ y otros con complejidad espacial lineal con respecto a ${\displaystyle n}$ .​

Ejemplo

Sean ${\displaystyle A}$:AAGGCT y ${\displaystyle B}$:AACCCG las dos secuencias a alinear con una puntuación de similitud esta dada por la siguiente relación:

${\displaystyle 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 ${\displaystyle 0}$ para todos los elementos de la primera columna y la primera fila. Después se calculan todas las puntuaciónes entre ${\displaystyle a_{i}}$ y ${\displaystyle b_{j}}$ , comenzando por ${\displaystyle a_{1}}$ y ${\displaystyle b_{1}}$, denotado con amarillo en la siguiente matriz.

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

Finalmente, para recuperar la alineación local óptima de ${\displaystyle A}$ y ${\displaystyle B}$ se lleva a cabo un rastreo a partir de ese elemento hasta llegar a un elemento con valor de ${\displaystyle 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 ${\displaystyle W_{k}}$ depende únicamente de la longitud ${\displaystyle k}$ del hueco y del costo ${\displaystyle w_{1}}$de un hueco de un solo espacio : ${\displaystyle W_{k}=kw_{1}}$.

Huecos afines

Gotoh propuso un modelo de huecos afines, que consiste en modificar la penalizacion ${\displaystyle W_{k}}$ para que esta sea función de dos parámetros: ${\displaystyle W_{k}=uk+v}$, donde ${\displaystyle u}$ es la penalización por extender un hueco, ${\displaystyle v}$ es la penalización por iniciar un hueco y ${\displaystyle k}$ es la longitud del hueco. Este esquema se reduce a la penalización lineal cuando ${\displaystyle u=0}$. Este modelo ofrece dos ventajas: reducir el número de operaciones a ${\displaystyle 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 ${\displaystyle n\times m}$:

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

Estas matrices tienen la siguiente inicialización:

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

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

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

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

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

Huecos convexos

Waterman​ 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, ${\displaystyle u}$ y ${\displaystyle v}$ respectivamente, en la penalización de huecos convexos el costo de extender el hueco disminuye a medida que aumenta su longitud: ${\displaystyle W_{k+1}-W_{k}\leq W_{k}-W_{k-1}}$.

Véase también

• Alineamiento de secuencias
• Alineamiento local
• Alineamiento global
• Algoritmo-Needleman-Wunsch
• Bioinformática
• BLAST

Enlaces externos

• Una implementación en Java