El algoritmo Needleman-Wunsch es un algoritmo utilizado en bioinformática para alinear secuencias de proteínas o nucleótidos . Fue una de las primeras aplicaciones de la programación dinámica para comparar secuencias biológicas. El algoritmo fue desarrollado por Saul B. Needleman y Christian D. Wunsch y publicado en 1970. [1] El algoritmo divide esencialmente un problema grande (por ejemplo, la secuencia completa) en una serie de problemas más pequeños, y utiliza las soluciones a los problemas más pequeños para encontrar una solución óptima al problema más grande. [2] También se lo conoce a veces como el algoritmo de coincidencia óptima y la técnica de alineación global . El algoritmo Needleman-Wunsch todavía se usa ampliamente para la alineación global óptima, particularmente cuando la calidad de la alineación global es de suma importancia. El algoritmo asigna una puntuación a cada alineación posible, y el propósito del algoritmo es encontrar todas las alineaciones posibles que tengan la puntuación más alta.
Este algoritmo se puede utilizar para dos cadenas cualesquiera . En esta guía se utilizarán dos pequeñas secuencias de ADN como ejemplos, como se muestra en la Figura 1:
GCATGCGGATACA
Primero, construya una cuadrícula como la que se muestra en la Figura 1. Comience la primera cadena en la parte superior de la tercera columna y comience la otra cadena al principio de la tercera fila. Complete el resto de los encabezados de columnas y filas como se muestra en la Figura 1. Aún no debería haber números en la cuadrícula.
A continuación, decida cómo puntuar cada par de letras. Con el ejemplo anterior, un posible candidato para la alineación podría ser:
12345678GCATG-CGG-ATACA
Las letras pueden coincidir, no coincidir o coincidir con un espacio (una eliminación o inserción ( indel )):
A cada uno de estos escenarios se le asigna una puntuación y la suma de las puntuaciones de todos los emparejamientos es la puntuación del candidato de alineación completo. Existen diferentes sistemas para asignar puntuaciones; algunos se describen en la sección Sistemas de puntuación a continuación. Por ahora, se utilizará el sistema utilizado por Needleman y Wunsch [1] :
Para el ejemplo anterior, la puntuación de la alineación sería 0:
GCATG-CGG-ATACA+−++−−+− −> 1*4 + (−1)*4 = 0
Comience con un cero en la primera fila, primera columna (sin incluir las celdas que contienen nucleótidos). Desplácese por las celdas fila por fila, calculando la puntuación de cada celda. La puntuación se calcula comparando las puntuaciones de las celdas vecinas a la izquierda, arriba o arriba a la izquierda (diagonal) de la celda y sumando la puntuación correspondiente para coincidencia, desajuste o indel. Tome el máximo de las puntuaciones de los candidatos para cada una de las tres posibilidades:
La puntuación resultante para la celda es la más alta de las tres puntuaciones candidatas.
Dado que no hay celdas 'superiores' o 'superiores izquierdas' para la primera fila, solo se puede utilizar la celda existente a la izquierda para calcular la puntuación de cada celda. Por lo tanto, se agrega −1 por cada desplazamiento hacia la derecha, ya que esto representa una inserción o deleción de la puntuación anterior. Esto da como resultado que la primera fila sea 0, −1, −2, −3, −4, −5, −6, −7. Lo mismo se aplica a la primera columna, ya que solo se puede utilizar la puntuación existente sobre cada celda. Por lo tanto, la tabla resultante es:
El primer caso con puntuaciones existentes en las 3 direcciones es la intersección de nuestras primeras letras (en este caso G y G). Las celdas circundantes se muestran a continuación:
Esta celda tiene tres posibles sumas candidatas:
El candidato más alto es 1 y se ingresa en la celda:
También se debe registrar la celda que haya dado la puntuación más alta al candidato. En el diagrama completo de la figura 1 anterior, esto se representa como una flecha que va desde la celda de la fila y columna 2 hasta la celda de la fila y columna 1.
En el siguiente ejemplo, el paso diagonal tanto para X como para Y representa un desajuste:
INCÓGNITA:
Y:
Tanto para X como para Y, la puntuación más alta es cero:
La puntuación más alta del candidato puede ser alcanzada por dos de las celdas vecinas:
En este caso, todas las direcciones que alcanzan la puntuación candidata más alta deben anotarse como posibles celdas de origen en el diagrama terminado en la figura 1, por ejemplo en la celda de la fila y columna 6.
Al completar la tabla de esta manera se obtienen los puntajes de todos los posibles candidatos de alineación; el puntaje en la celda de la parte inferior derecha representa el puntaje de alineación para la mejor alineación.
Marcar una ruta desde la celda de la parte inferior derecha hasta la celda de la parte superior izquierda siguiendo la dirección de las flechas. A partir de esta ruta, la secuencia se construye según estas reglas:
Siguiendo estas reglas, los pasos para un posible candidato a alineación en la figura 1 son:
G → CG → GCG → -GCG → T-GCG → AT-GCG → CAT-GCG → GCAT-GCG A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA ↓ (rama) → TGCG → -TGCG → ... → TACA → TTACA → ...
Los esquemas de puntuación más simples simplemente dan un valor para cada coincidencia, desajuste e inserción/extracción. La guía paso a paso anterior utiliza coincidencia = 1, desajuste = −1, inserción/extracción = −1. Por lo tanto, cuanto menor sea el puntaje de alineación, mayor será la distancia de edición ; para este sistema de puntuación, se desea una puntuación alta. Otro sistema de puntuación podría ser:
Para este sistema, la puntuación de alineación representará la distancia de edición entre las dos cadenas. Se pueden idear diferentes sistemas de puntuación para diferentes situaciones; por ejemplo, si se considera que los espacios son muy perjudiciales para la alineación, se puede utilizar un sistema de puntuación que penalice considerablemente los espacios, como:
Los sistemas de puntuación más complejos no sólo atribuyen valores al tipo de alteración, sino también a las letras implicadas. Por ejemplo, una coincidencia entre A y A puede recibir un 1, pero una coincidencia entre T y T puede recibir un 4. Aquí (asumiendo el primer sistema de puntuación) se da más importancia a la coincidencia de Ts que a la de As, es decir, se supone que la coincidencia de Ts es más significativa para la alineación. Esta ponderación basada en letras también se aplica a las discordancias.
Para representar todas las combinaciones posibles de letras y sus puntuaciones resultantes se utiliza una matriz de similitud. La matriz de similitud para el sistema más básico se representa como:
Cada puntuación representa un cambio de una de las letras que coincide con la celda a la otra. Por lo tanto, esto representa todas las posibles coincidencias y desajustes (para un alfabeto de ACGT). Tenga en cuenta que todas las coincidencias van a lo largo de la diagonal; además, no es necesario completar toda la tabla, solo este triángulo porque las puntuaciones son recíprocas. = (Puntuación para A → C = Puntuación para C → A). Si se implementa la regla TT = 4 de arriba, se produce la siguiente matriz de similitud:
Se han construido estadísticamente distintas matrices de puntuación que ponderan distintas acciones adecuadas para un escenario en particular. Disponer de matrices de puntuación ponderadas es particularmente importante en la alineación de secuencias de proteínas debido a la frecuencia variable de los distintos aminoácidos. Existen dos grandes familias de matrices de puntuación, cada una con modificaciones adicionales para escenarios específicos:
Al alinear secuencias, a menudo hay huecos (es decir, indels), a veces grandes. Biológicamente, es más probable que un hueco grande se produzca como una gran deleción en lugar de múltiples deleciones individuales. Por lo tanto, dos indels pequeños deberían tener una puntuación peor que una grande. La forma sencilla y común de hacer esto es mediante una puntuación de inicio de hueco grande para un nuevo indel y una puntuación de extensión de hueco más pequeña para cada letra que extienda el indel. Por ejemplo, new-indel puede costar -5 y extend-indel puede costar -1. De esta manera, una alineación como:
GAAAAAATG--AAT
que tiene múltiples alineaciones iguales, algunas con múltiples alineaciones pequeñas ahora se alinearán como:
GAAAAAATGAA----T
o cualquier alineación con un espacio largo de 4 en preferencia a múltiples espacios pequeños.
Las puntuaciones de los caracteres alineados se especifican mediante una matriz de similitud . Aquí, S ( a , b ) es la similitud de los caracteres a y b . Utiliza una penalización de espacio lineal , aquí denominada d .
Por ejemplo, si la matriz de similitud fuera
Luego la alineación:
AGACTAGTTACCGA---GACGT
con una penalización de gap de −5, tendría la siguiente puntuación:
Para encontrar la alineación con la puntuación más alta, se asigna una matriz bidimensional (o matriz ) F. La entrada en la fila i y la columna j se denota aquí por . Hay una fila para cada carácter en la secuencia A y una columna para cada carácter en la secuencia B. Por lo tanto, si se alinean secuencias de tamaños n y m , la cantidad de memoria utilizada está en . El algoritmo de Hirschberg solo mantiene un subconjunto de la matriz en la memoria y usa espacio, pero por lo demás es similar a Needleman-Wunsch (y aún requiere tiempo).
A medida que avanza el algoritmo, se asignará la puntuación óptima para la alineación de los primeros caracteres de A y los primeros caracteres de B. El principio de optimalidad se aplica entonces de la siguiente manera:
El pseudocódigo del algoritmo para calcular la matriz F se ve así:
d ← Puntuación de penalización por brecha para i = 0 a longitud (A) F(i,0) ← d * ipara j = 0 a longitud (B) F(0,j) ← d * jpara i = 1 a la longitud (A) para j = 1 a la longitud (B) { Coincidencia ← 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) ← máx. (Coincidir, Insertar, Eliminar) }Una vez calculada la matriz F , la entrada da la puntuación máxima entre todas las alineaciones posibles. Para calcular una alineación que realmente dé esta puntuación, se comienza desde la celda inferior derecha y se compara el valor con las tres fuentes posibles (Coincidir, Insertar y Eliminar mencionadas anteriormente) para ver de cuál proviene. Si es Coincidir, entonces y están alineados, si es Eliminar, entonces está alineado con un espacio, y si es Insertar, entonces está alineado con un espacio. (En general, más de una opción puede tener el mismo valor, lo que lleva a alineaciones óptimas alternativas).
AlineaciónA ← ""AlineaciónB ← ""i ← longitud (A)j ← longitud (B) mientras (i > 0 o j > 0){ si (i > 0 y j > 0 y F(i, j) == F(i−1, j−1) + 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 (i > 0 y F(i, j) == F(i−1, j) + d) { AlineaciónA ← A i + AlineaciónA AlineaciónB ← "−" + AlineaciónB yo ← yo − 1 } demás { AlineaciónA ← "−" + AlineaciónA AlineaciónB ← B j + AlineaciónB j ← j − 1 }}Calcular la puntuación de cada celda de la tabla es una operación. Por lo tanto, la complejidad temporal del algoritmo para dos secuencias de longitud y es . [3] Se ha demostrado que es posible mejorar el tiempo de ejecución de utilizando el método de los cuatro rusos . [3] [4] Dado que el algoritmo llena una tabla, la complejidad espacial es [3]
El propósito original del algoritmo descrito por Needleman y Wunsch era encontrar similitudes en las secuencias de aminoácidos de dos proteínas. [1]
Needleman y Wunsch describen su algoritmo explícitamente para el caso en el que la alineación se ve penalizada únicamente por las coincidencias y desajustes, y los huecos no tienen penalización ( d = 0). La publicación original de 1970 sugiere la recursión .
El algoritmo de programación dinámica correspondiente toma tiempo cúbico. El artículo también señala que la recursión puede adaptarse a fórmulas arbitrarias de penalización por brecha:
Se puede aplicar un factor de penalización, un número que se resta por cada espacio que se crea, como barrera para permitir el espacio. El factor de penalización podría ser una función del tamaño y/o la dirección del espacio. [página 444]
Un mejor algoritmo de programación dinámica con tiempo de ejecución cuadrático para el mismo problema (sin penalización por espacio) fue introducido más tarde [5] por David Sankoff en 1972. Algoritmos de tiempo cuadrático similares fueron descubiertos independientemente por TK Vintsyuk [6] en 1968 para el procesamiento del habla ( "deformación del tiempo" ), y por Robert A. Wagner y Michael J. Fischer [7] en 1974 para la coincidencia de 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 Vladimir Levenshtein . Peter H. Sellers demostró [8] en 1974 que los dos problemas son equivalentes.
El algoritmo Needleman–Wunsch todavía se utiliza ampliamente para lograr una alineación global óptima , en particular cuando la calidad de la alineación global es de suma importancia. Sin embargo, el algoritmo es costoso en términos de tiempo y espacio, proporcional al producto de la longitud de dos secuencias y, por lo tanto, no es adecuado para secuencias largas.
Los últimos avances se han centrado en mejorar el tiempo y el coste espacial del algoritmo manteniendo la calidad. Por ejemplo, en 2013, un algoritmo de alineación global de secuencias óptimas rápidas (FOGSAA, por sus siglas en inglés) [9] sugirió una alineación de secuencias de nucleótidos/proteínas más rápida que otros métodos de alineación global óptima, incluido el algoritmo Needleman-Wunsch. El artículo afirma que, en comparación con el algoritmo Needleman-Wunsch, FOGSAA logra una ganancia de tiempo del 70-90 % para secuencias de nucleótidos altamente similares (con una similitud > 80 %) y del 54-70 % para secuencias que tienen una similitud del 30-80 %.
La correspondencia estereoscópica es un paso esencial en el proceso de reconstrucción 3D a partir de un par de imágenes estereoscópicas. Una vez rectificadas las imágenes, se puede establecer una analogía entre la alineación de secuencias de nucleótidos y proteínas y la correspondencia de píxeles pertenecientes a líneas de escaneo , ya que ambas tareas tienen como objetivo establecer una correspondencia óptima entre dos cadenas de caracteres.
Aunque en muchas aplicaciones se puede realizar la rectificación de imágenes, por ejemplo, mediante la resección o calibración de la cámara, a veces es imposible o poco práctico ya que el costo computacional de los modelos de rectificación precisos prohíbe su uso en aplicaciones en tiempo real . Además, ninguno de estos modelos es adecuado cuando una lente de cámara muestra distorsiones inesperadas , como las generadas por gotas de lluvia, cubiertas impermeables o polvo. Al extender el algoritmo Needleman-Wunsch, una línea en la imagen "izquierda" se puede asociar a una curva en la imagen "derecha" al encontrar la alineación con la puntuación más alta en una matriz tridimensional (o matriz). Los experimentos demostraron que dicha extensión permite una coincidencia densa de píxeles entre imágenes no rectificadas o distorsionadas. [10]
