Algoritmo Needleman-Wunsch

Por Germán González

El algoritmo Needleman-Wunsch realiza un alineamiento global de dos secuencias (aquí llamadas A y B).

Es comúnmente usado en bioinformática para alinear secuencias de nucleótidos o proteínas. Fue propuesto en 1970 por Saul Needleman y Christian Wunsch en su paper A general method applicable to the search for similarities in the amino acid sequence of two proteins, J Mol Biol. 48(3):443-53.

El algoritmo Needleman–Wunsch es un ejemplo de programación dinámica, y está garantizado que encuentre el alineamiento con el puntaje máximo. Needleman–Wunsch fue la primera aplicación de programación dinámica para la comparación de secuencias biológicas.

Los puntajes para caracteres alineados son especificados por una matriz de similitud. Aquí, S(i,j) es la similitud de los caracteres i y j. Esta usa una penalidad por hueco (gap) lineal, aquí llamada d.

Por ejemplo, si la matriz de similitud era:

Entonces el alineamiento es:

AGACTAGTTAC

CGA—GACGT

Con una penalidad por hueco de -5, tendríamos el siguiente puntaje…

nw-eq1
nw-eq2

Para encontrar el alineamiento con el puntaje más alto, una matriz bidimensional es asignada. Esta matriz a menudo es llamada matriz F y su (i,j)ésima entrada frecuentemente es denotada Fij . Allí hay una columna para cada carácter de la secuencia A, y una fila para cada caracter de la secuencia B. Así si estamos alineando secuencias de tamaños n y m, el tiempo de ejecución del algoritmo es O(nm) y la cantidad de memoria utilizada es O(nm).

Sin embargo hay una versión modificada del algoritmo que usa solo O(n+m) espacio, al costo de un tiempo de ejecución más grande. Esta modificación es de hecho una técnica general que aplicamos a muchos algoritmos de programación dinámica; este método fue introducido en el algoritmo de Hirschberg para resolver el problema de la subcadena más larga en común.

Cuando el algoritmo progresa, Fij puede ser asignada para ser el puntaje óptimo para el alineamiento de los primeros i caracteres en A y los primeros j caracteres en B. El principio de optimización es entonces aplicado como sigue:

Base:

F0jdj

Fi0 = di

Recursión, basada en el principio de optimización:

Fij = max(Fi − 1,j − 1 + S(Ai − 1,Bj − 1),Fi,j − 1 + d,Fi − 1,jd)

El pseudo-código para el algoritmo que computa la matriz A por lo tanto luce algo así (los índices de arreglos y secuencias empiezan en 0):

for i=0 a largo(A)-1

F(i,0) <- d*i

for j=0 a largo(B)-1

F(0,j) <- d*j

for i=1 a largo(A)

for j = 1 a largo(B)

{

Elección1 <- F(i-1,j-1) + S(A(i-1), B(j-1))

Elección2 <- F(i-1, j) + d

Elección3 <- F(i, j-1) + d

F(i,j) <- max(Elección1, Elección2, Elección3)

}

Una vez que la matriz F es computada, note que la esquina inferior derecha de la matriz es el máximo puntaje para cualquier alineamiento. Para computar que alineamiento da actualmente ese puntaje, puedes empezar desde la celda que se encuentra al fondo a la derecha, y comparar el valor con las tres posibles fuentes (Elección1, Elección2, Elección3) para ver de donde proviene.

Si era Elección1, entonces A(i) y B(i) están alineadas, si era Elección2 entonces A(i) está alineado con un gap, y si era Elección3, entonces B(i) está alineada con un hueco (gap).

AlineamientoA <- “”

AlineamientoB <- “”

i <- largo(A)

j <- largo(B)

while (i > 0 AND j > 0)

{

Score <- F(i,j)

ScoreDiag <- F(i – 1, j – 1)

ScoreUp <- F(i, j – 1)

ScoreLeft <- F(i – 1, j)

if (Score == ScoreDiag + S(A(i-1), B(j-1)))

{

AlineamientoA <- A(i-1) + AlineamientoA

AlineamientoB <- B(j-1) + AlineamientoB

i <- i – 1

j <- j – 1

}

else if (Score == ScoreLeft + d)

{

AlineamientoA <- A(i-1) + AlineamientoA

AlineamientoB <- “-” + AlineamientoB

i <- i – 1

}

otherwise (Score == ScoreUp + d)

{

AlineamientoA <- “-” + AlineamientoA

AlineamientoB <- B(j-1) + AlineamientoB

j <- j – 1

}

}

while (i > 0)

{

AlineamientoA <- A(i-1) + AlineamientoA

AlineamientoB <- “-” + AlineamientoB

i <- i – 1

}

while (j > 0)

{

AlineamientoA <- “-” + AlineamientoA

AlineamientoB <- B(j-1) + AlineamientoB

j <- j – 1

}

 

Comentarios