Bioinformática

El algoritmo de Needleman-Wunsch sirve para realizar alineamientos globales de dos secuencias. Se suele utilizar en el ámbito de labioinformática para alinear secuencias de proteínas o de ácidos nucleicos. Fue propuesto por primera vez en 1970, por Saul Needlemany Christian Wunsch. Se trata de un ejemplo típico de programación dinámica. El algoritmo funciona del mismo modo independientemente de la complejidad o longitud de las secuencias y garantiza la obtención del mejor alineamiento.¹

Las dos secuencias a alinear, llamadas A y B en los ejemplos, de longitud ${\displaystyle |A|=m}$ y ${\displaystyle |B|=n}$, están formadas por elementos de un alfabeto finito de símbolos. El algoritmo necesita saber qué símbolos son diferentes entre sí y cuáles son iguales. Podemos utilizar una matriz cuadrada (S) para este propósito, en la que cada elemento ${\displaystyle S_{ij}}$ indique la similitud entre los elementos i y j del alfabeto usado. Si nuestro alfabeto de símbolos no fuese finito, en vez de una matriz podríamos usar una función ${\displaystyle R^{2}\rightarrow R}$ que tuviese como parámetros ambos símbolos a comparar y cuya salida fuese la similitud entre ambos. También se necesita otro parámetro (d) que nos indique cómo vamos a valorar que un símbolo no quede alineado con otro y que en su lugar se utilice un hueco.

Por ejemplo podemos definir la siguiente matriz:

${\displaystyle {\begin{array}{ccccc}-&A&G&C&T\\A&10&-1&-3&-4\\G&-1&7&-5&-3\\C&-3&-5&9&0\\T&-4&-3&0&8\end{array}}}$

Y entonces el siguiente alineamiento:

AGACTAGTTAC
CGA---GACGT

con una penalización por hueco de ${\displaystyle d=-5}$ nos devolvería como solución óptima:

${\displaystyle S(A,C)+S(G,G)+S(A,A)+3\times d+S(G,G)+S(T,A)+S(T,C)+S(A,G)+S(C,T)=-3+7+10-3\times 5+7+-4+0+-1+0=1}$

Para determinar la puntuación óptima y poder reconstruir el alineamiento que devolvería esa puntuación se necesita otra matriz, F, que almacena los resultados parciales de cada posible alineamiento. Las dimensiones de la matriz F son el número de elementos en la secuencia A y el de B (${\displaystyle |A|\times |B|}$).

En cada iteración del algoritmo recibe valor un elemento de la matriz F. El valor que recibe el elemento ${\displaystyle F_{ij}}$ representa la puntuación obtenida al alinear de forma óptima los primeros i elementos de A y los primeros j de B. Cuando el algoritmo termine, el último elemento de F (${\displaystyle F_{mn}}$, con ${\displaystyle m=|A|}$ y ${\displaystyle n=|B|}$) contendrá la puntuación para el alineamiento óptimo de ambas secuencias.

  Inicio del algoritmo:
  ${\displaystyle F_{0j}=d*j}$
  ${\displaystyle F_{i0}=d*i}$
  Recursión para obtener el siguiente elemento de forma óptima:
  ${\displaystyle F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),F_{i,j-1}+d,F_{i-1,j}+d)}$

La matriz F se calcula con el siguiente algoritmo:

   for i=0 to length(A)-1
     F(i,0) <- span=""> d*i
   for j=0 to length(B)-1
     F(0,j) <- span=""> d*j
   for i=1 to length(A)
     for j = 1 to length(B)
     {
       Choice1 <- span=""> F(i-1,j-1) + S(A(i), B(j))
       Choice2 <- span=""> F(i-1, j) + d
       Choice3 <- span=""> F(i, j-1) + d
       F(i,j) <- span=""> max(Choice1, Choice2, Choice3)
     }

Cuando el algoritmo acaba tenemos calculada la matriz F; el resultado es la puntuación devuelta por el mejor alineamiento posible, de acuerdo a los parámetros que hemos definido. Para obtener la secuencia se necesita ejecutar el siguiente algoritmo, que hace uso de la matriz F. Este algoritmo comienza por el último elemento, ${\displaystyle F_{mn}}$, y va retrocediendo hasta llegar a un elemento de la primera fila o la primera columna de F. En cada paso se comparan 3 elementos de F para ver cuál de ellos es el que se ha seguido en la solución óptima. Para cada ${\displaystyle F_{ij}}$ debemos comparar ${\displaystyle F_{i-1,j},F_{i,j-1}}$ y ${\displaystyle F_{i-1,j-1}}$. Si el elemento usado es ${\displaystyle F_{i-1,j}}$, entonces ${\displaystyle A_{i}}$ se ha alineado con un hueco; si es ${\displaystyle F_{i,j-1}}$, entonces ${\displaystyle B_{i}}$ se ha alineado con un hueco; y si no, si el elemento elegido es ${\displaystyle F_{i-1,j-1}}$, los elementos ${\displaystyle A_{i}}$ y ${\displaystyle B_{i}}$ han sido alineados. Es importante destacar que el que dos elementos sean alineados no implica necesariamente que sean iguales; significa que entre esa posibilidad, alinear con huecos o alinear símbolos diferentes, esa era la mejor opción. El pseudo-algoritmo que permite obtener el alineamiento correcto es el siguiente:

   AlignmentA <- span=""> ""
   AlignmentB <- span=""> ""
   i <- span=""> length(A) 
   j <- span=""> length(B)
   while (i > 0 AND j > 0)
   {
     Score <- span=""> F(i,j)
     ScoreDiag <- span=""> F(i - 1, j - 1)
     ScoreUp <- span=""> F(i, j - 1)
     ScoreLeft <- span=""> F(i - 1, j)
     if (Score == ScoreDiag + S(A(i), B(j)))
     {
       AlignmentA <- span=""> A(i-1) + AlignmentA
       AlignmentB <- span=""> B(j-1) + AlignmentB
       i <- span=""> i - 1
       j <- span=""> j - 1
     }
     else if (Score == ScoreLeft + d)
     {
       AlignmentA <- span=""> A(i-1) + AlignmentA
       AlignmentB <- span=""> "-" + AlignmentB
       i <- span=""> i - 1
     }
     otherwise (Score == ScoreUp + d)
     {
       AlignmentA <- span=""> "-" + AlignmentA
       AlignmentB <- span=""> B(j-1) + AlignmentB
       j <- span=""> j - 1
     }
   }
   while (i > 0)
   {
     AlignmentA <- span=""> A(i-1) + AlignmentA
     AlignmentB <- span=""> "-" + AlignmentB
     i <- span=""> i - 1
   }
   while (j > 0)
   {
     AlignmentA <- span=""> "-" + AlignmentA
     AlignmentB <- span=""> B(j-1) + AlignmentB
     j <- span=""> j - 1
   }

Se puede demostrar formalmente que tanto el tiempo de ejecución como el espacio necesario para ejecutar el algoritmo son de ordenO(nm). Para alguna aplicaciones, sobre todo en bioinformática, el requerimiento de espacio es prohibitivo, puesto que se alinean secuencias muy largas. Existe una optimización de este algoritmo, denominada algoritmo de Hirschberg, que sólo necesita espacio del orden O(m+n), pero a costa de incrementar el tiempo de computación.

El algoritmo de Smith-Waterman es una reconocida estrategia para realizar alineamiento local de secuencias biológicas (ADN, ARN oproteí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.