Algoritmo de Needleman-Wunsha

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de julio de 2016; las comprobaciones requieren 10 ediciones .

El algoritmo de Needleman-Wunsch es un algoritmo para realizar una alineación de dos secuencias (llamémoslas y ) que se utiliza en bioinformática para construir alineaciones de secuencias de aminoácidos o nucleótidos . El algoritmo fue propuesto en 1970 por Saul Needleman y Christian Wunsch [1] . $A$ $B$

El algoritmo de Needleman-Wunsch es un ejemplo de programación dinámica y resultó ser el primer ejemplo de la aplicación de la programación dinámica a la comparación de secuencias biológicas.

Vista moderna

La correspondencia de los caracteres alineados viene dada por la matriz de similitud . Aquí está la similitud de los símbolos y . También se utiliza una penalización de espacio lineal , aquí llamada . $S(a,\;b)$ $a$ $b$ $d$

Por ejemplo, si la matriz de similitud viene dada por la tabla

-	A	GRAMO	C	T
A	diez	-una	-3	-cuatro
GRAMO	-una	7	-5	-3
C	-3	-5	9	0
T	-cuatro	-3	0	ocho

luego alineación:

GTTAC‒‒ G‒‒ACGT

con una penalización de hueco tendrá la siguiente puntuación: $d=-5$

S(G,\;G)+2\times d+S(A,\;A)+S(C,\;C)+2\times d

=7+(2\times -5)+10+9+(2\times -5)=6.

Para encontrar la alineación con la puntuación más alta, se asigna una matriz (o matriz ) bidimensional que contiene tantas filas como caracteres en la secuencia y tantas columnas como caracteres en la secuencia . Una entrada en una fila y columna se denota como . Por lo tanto, si alineamos las secuencias de tamaños y , entonces la cantidad de memoria requerida será . ( El algoritmo de Hirschberg calcula la alineación óptima utilizando la cantidad de memoria pero aproximadamente el doble del tiempo de cálculo ) . $F$ $A$ $B$ $i$ $j$ $F_{{ij}}$ $norte$ $metro$ $En M)$ $O(n+m)$

Durante la operación del algoritmo, el valor tomará los valores de la estimación óptima para alinear los primeros caracteres en y los primeros caracteres en . Entonces, el principio de optimalidad de Bellman se puede formular de la siguiente manera: $F_{{ij}}$ $i=0,\;\ldots,\;n$ $A$ $j=0,\;\ldots,\;m$ $B$

Base:

F_{{0j}}=d\cdot j

F_{{i0}}=d\cdot i

Recursividad basada en el principio de optimalidad:

F_{{ij}}=\max(F_{{i-1,\;j-1}}+S(A_{i},\;B_{j}),\;F_{{i,\;j -1}}+d,\;F_{{i-1,\;j}}+d).

Por lo tanto, el pseudocódigo del algoritmo para calcular la matriz F se verá así:

para i=0 a la longitud (A) F(i,0) ← d*i para j=0 a la longitud (B) F(0,j) ← d*j para i=1 a la longitud (A) para j = 1 a la longitud (B) { Partido ← F(i-1,j-1) + S(A i , B j ) Eliminar ← F(i-1, j) + d Insertar ← F(i, j-1) + d F(i,j) ← max (Coincidir, Insertar, Eliminar) }

Cuando se calcula una matriz , su elemento otorga la máxima puntuación entre todas las alineaciones posibles. Para calcular la alineación real que puntúa como esta, debe comenzar en la celda inferior derecha y comparar los valores en esa celda con las tres fuentes posibles (coincidencia, inserción o eliminación) para ver de dónde proviene. Si coinciden , y están alineados, si se eliminan, se alinean con una ruptura y, si se insertan, con una ruptura, ya están alineados . (En general, puede haber más de una opción con el mismo valor que dará como resultado alineaciones óptimas alternativas). $F$ $F_{{ij}}$ $Ai}$ $b_j$ $Ai}$ $b_j$

AlineaciónA ← "" AlineaciónB ← "" i ← longitud (A) j ← longitud (B) mientras que (i > 0 o j > 0) { Puntuación ← F(i,j) ScoreDiag ← F(i - 1, j - 1) Puntuación arriba ← F(i, j - 1) ScoreLeft ← F(i - 1, j) si (Puntaje == ScoreDiag + S(A i , B j )) { AlineaciónA ← A i + AlineaciónA AlineaciónB ← B j + AlineaciónB yo ← yo - 1 j ← j - 1 } de lo contrario si (Puntuación == ScoreLeft + d) { AlineaciónA ← A i + AlineaciónA AlineaciónB ← "-" + AlineaciónB yo ← yo - 1 } de lo contrario (Puntuación == ScoreUp + d) { AlineaciónA ← "-" + AlineaciónA AlineaciónB ← B j + AlineaciónB j ← j - 1 } } mientras (yo > 0) { AlineaciónA ← A i + AlineaciónA AlineaciónB ← "-" + AlineaciónB yo ← yo - 1 } mientras (j > 0) { AlineaciónA ← "-" + AlineaciónA AlineaciónB ← B j + AlineaciónB j ← j - 1 }

Observaciones históricas

Needleman y Wunsch describieron explícitamente su algoritmo para el caso en que solo se evalúa la coincidencia o la falta de coincidencia de caracteres, pero no la brecha ( ). La publicación original [1] de 1970 propone una recursión $re=0$

F_{ij}=\max _{h<i,\;k<j}\{F_{h,\;j-1}+S(A_{i},\;B_{j}), \;F_{i-1,\;k}+S(A_{i},\;B_{j})\}.

El algoritmo de programación dinámica correspondiente requiere tiempo cúbico para calcular. El artículo también señala que la recursividad se puede adaptar a cualquier fórmula de penalización por brecha:

La penalización por espacios (el número que se resta por cada espacio) puede considerarse como una forma de evitar que aparezcan espacios en la alineación. La cantidad de la penalización del hueco puede ser una función del tamaño y/o la dirección del hueco. [pags. 444]

David Sankoff propuso por primera vez [2] un algoritmo de programación dinámica en tiempo cuadrático más rápido para el mismo problema (sin penalización por brecha) en 1972. TK Vintsyuk [3] descubrió de forma independiente un algoritmo cuadrático en el tiempo similar en 1968 para procesar el habla ( pre-énfasis de escala dinámica) y por Robert A. Wagner y Michael J. Fisher [4] en 1974 para emparejar cadenas.

Needleman y Wunsch formularon su problema en términos de maximizar la similitud. Otra posibilidad es minimizar la distancia de edición entre secuencias propuesta por V. Levenshtein , sin embargo, se demostró [5] que estos dos problemas son equivalentes.

En la terminología moderna, Needleman-Wunsch se refiere a un algoritmo de alineación de secuencia de tiempo cuadrático para una penalización de brecha lineal o afín.

Véase también

Notas

↑ 1 2 Needleman, Saúl B.; y Wunsch, Christian D. Un método general aplicable a la búsqueda de similitudes en la secuencia de aminoácidos de dos proteínas // Journal of Molecular Biology : diario. - 1970. - vol. 48 , núm. 3 . - Pág. 443-453 . - doi : 10.1016/0022-2836(70)90057-4 . —PMID 5420325 .
↑ Sankoff, D. Coincidencia de secuencias bajo restricciones de eliminación / inserción // Actas de la Academia Nacional de Ciencias de los Estados Unidos de América : revista. - 1972. - vol. 69 , núm. 1 . - Pág. 4-6 .
↑ Vintsyuk, TK Discriminación del habla por programación dinámica (neopr.) // Kibernetika. - 1968. - T. 4 . - S. 81-88 .
↑ Wagner, RA y Fischer, MJ El problema de corrección de cadena a cadena // Journal of the ACM : journal. - 1974. - vol. 21 . - pág. 168-173 . -doi : 10.1145/ 321796.321811 .
↑ Sellers, PH Sobre la teoría y el cálculo de distancias evolutivas // SIAM Journal on Applied Mathematics : diario. - 1974. - vol. 26 , núm. 4 . - Pág. 787-793 .

Enlaces

Algoritmo de Needleman-Wunsch como código Ruby
Implementación en Java del Algoritmo de Needleman-Wunsch
BABA : un subprograma (con fuente) que explica visualmente el algoritmo.
Una explicación clara de NW y sus aplicaciones para la alineación de secuencias
Técnicas de alineación de secuencias en el blog de tecnología

Instrumentos de cuerda
Medidas de similitud de cadenas	Distancia de Damerau a Loewenstein distancia Levenstein distancia de hamming Similitudes Jaro-Winkler
Búsqueda de subcadena	Algoritmo de Boyer-Moore Algoritmo de Boyer-Moore-Horspool Algoritmo de Knuth-Morris-Pratt Algoritmo de Rabin-Karp función de prefijo Función Z Algoritmo Aho - Korasik
palíndromos	árbol palíndromo Algoritmo del administrador
Alineación de secuencia	Algoritmo de Needleman-Wunsha Algoritmo de Smith-Waterman
Estructuras de sufijos	Matriz de sufijos sufijo autómata árbol de sufijos árbol de prefijos
Otro	analizando La coincidencia de patrones Mayor subsecuencia común Mayor subcadena común

diccionarios y enciclopedias	Britannica (en línea)