Algoritmo de Needleman-Wunsch

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 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 esencialmente divide un problema grande (por ejemplo, la secuencia completa) en una serie de problemas más pequeños y utiliza las soluciones de los problemas más pequeños. problemas para encontrar una solución óptima al problema mayor. ^[2]^[3] A veces también se lo denomina algoritmo de coincidencia óptima y técnica de alineación global . El algoritmo Needleman-Wunsch todavía se usa ampliamente para una 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.

Introducción

Este algoritmo se puede utilizar para dos cadenas cualesquiera . Esta guía utilizará dos pequeñas secuencias de ADN como ejemplos, como se muestra en la Figura 1:

GCATGCGGATACA

Construyendo la grilla

Primero construya una cuadrícula como la que se muestra en la Figura 1 arriba. Comience la primera cadena en la parte superior de la tercera columna y comience la otra cadena al comienzo de la tercera fila. Complete el resto de los encabezados de columnas y filas como en la Figura 1. Aún no debería haber números en la cuadrícula.

Elegir un sistema de puntuación

A continuación, decide cómo puntuar cada par individual de letras. Usando el ejemplo anterior, un posible candidato a alineación podría ser:12345678 GCATG-CG G-ATTACALas letras pueden coincidir, no coincidir o coincidir con un espacio (una eliminación o inserción ( indel )):

Coincidencia: Las dos letras del índice actual son iguales.
Falta de coincidencia: las dos letras del índice actual son diferentes.
Indel (inserción o eliminación): la mejor alineación implica que una letra se alinee con un espacio en la otra cadena.

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 de todo el candidato de alineación. 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] :}

Coincidencia: +1
Falta de coincidencia o Indel: −1

Para el ejemplo anterior, la puntuación de la alineación sería 0:GCATG-CG G-ATTACA

+−++−−+− −> 1*4 + (−1)*4 = 0

Llenando la tabla

Comience con un cero en la primera fila, primera columna (sin incluir las celdas que contienen nucleótidos). Muévete 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 apropiada para coincidencia, falta de coincidencia o indel. Tome el máximo de puntuaciones de los candidatos para cada una de las tres posibilidades:

El camino desde la celda superior o izquierda representa un emparejamiento indel, así que tome las puntuaciones de las celdas izquierda y superior y agregue la puntuación de indel a cada una de ellas.
La ruta diagonal representa una coincidencia/no coincidencia, así que tome la puntuación de la celda diagonal superior izquierda y agregue la puntuación de coincidencia si las bases (letras) correspondientes en la fila y columna coinciden o la puntuación de no coincidencia si no lo hacen.

La puntuación resultante para la celda es la más alta de las tres puntuaciones candidatas.

Dado que no hay celdas 'arriba' o 'arriba izquierda' para la primera fila, solo se puede usar 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 un indel 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 encima de cada celda. Así 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 están a continuación:

Esta celda tiene tres posibles sumas candidatas:

El vecino diagonal superior izquierdo tiene una puntuación de 0. El emparejamiento de G y G es una coincidencia, así que suma la puntuación de la coincidencia: 0+1 = 1
El vecino superior tiene una puntuación −1 y moverse desde allí representa un indel, así que sume la puntuación para el indel: (−1) + (−1) = (−2)
El vecino izquierdo también tiene puntuación −1, representa un indel y también produce (−2).

El candidato más alto es 1 y se ingresa en la celda:

También se debe registrar la celda que dio la puntuación más alta al candidato. En el diagrama completo de la figura 1 anterior, esto se representa como una flecha desde la celda de la fila y columna 2 a la celda de la fila y columna 1.

En el siguiente ejemplo, el paso diagonal para X e Y representa una falta de coincidencia:

Arriba: (−2)+(−1) = (−3)
Izquierda: (+1)+(−1) = (0)
Arriba a la izquierda: (−1)+(−1) = (−2)

Arriba: (1)+(−1) = (0)
Izquierda: (−2)+(−1) = (−3)
Arriba a la izquierda: (−1)+(−1) = (−2)

Tanto para X como para Y, la puntuación más alta es cero:

La puntuación más alta del candidato la pueden alcanzar dos de las celdas vecinas:

Arriba: (1)+(−1) = (0)
Arriba a la izquierda: (1)+(−1) = (0)
Izquierda: (0)+(−1) = (−1)

En este caso, todas las direcciones que alcanzan la puntuación más alta del candidato 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 las puntuaciones de todos los posibles candidatos a alineación; la puntuación en la celda de la parte inferior derecha representa la puntuación de alineación para la mejor alineación.

Trazando flechas de regreso al origen

Marque un camino desde la celda en la parte inferior derecha hasta la celda en la parte superior izquierda siguiendo la dirección de las flechas. A partir de este camino, la secuencia se construye mediante estas reglas:

Una flecha diagonal representa una coincidencia o no coincidencia, por lo que la letra de la columna y la letra de la fila de la celda de origen se alinearán.
Una flecha horizontal o vertical representa un indel. Las flechas verticales alinearán un espacio ("-") con la letra de la fila (la secuencia "lateral"), las flechas horizontales alinearán un espacio con la letra de la columna (la secuencia "superior").
Si hay varias flechas para elegir, representan una ramificación de las alineaciones. Si dos o más ramas pertenecen a rutas desde la celda inferior derecha hasta la celda superior izquierda, son alineaciones igualmente viables. En este caso, tenga en cuenta las rutas como candidatos de alineación separados.

Siguiendo estas reglas, los pasos para un posible candidato de 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 ↓ (sucursal) → TGCG → -TGCG → ... → TACA → TTACA → ...

Sistemas de puntuación

Esquemas básicos de puntuación

Los esquemas de puntuación más simples simplemente dan un valor para cada coincidencia, desajuste e indel. La guía paso a paso anterior utiliza coincidencia = 1, falta de coincidencia = −1, indel = −1. Por lo tanto, cuanto menor sea la puntuación 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:

Partido = 1
Indel = -2
Falta de coincidencia = -1

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 las brechas se consideran muy malas para su alineación, puede utilizar un sistema de puntuación que penalice fuertemente las brechas, como por ejemplo:

Partido = 1
Falta de coincidencia = -1
Indel = -2

Matriz de similitud

Los sistemas de puntuación más complicados atribuyen valores no sólo al tipo de alteración, sino también a las letras involucradas. Por ejemplo, a una coincidencia entre A y A se le puede dar 1, pero a una coincidencia entre T y T se le puede dar 4. Aquí (asumiendo el primer sistema de puntuación) se le da más importancia a la coincidencia de Ts que a las As, es decir, a las coincidencias de Ts. Se supone que es más significativo para la alineación. Esta ponderación basada en letras también se aplica a las discrepancias.

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 discrepancias (para un alfabeto de ACGT). Tenga en cuenta que todas las coincidencias van a lo largo de la diagonal, además no es necesario llenar 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 desde arriba, se produce la siguiente matriz de similitud:

Se han construido estadísticamente diferentes matrices de puntuación que dan peso a diferentes acciones apropiadas para un escenario particular. Tener matrices de puntuación ponderadas es particularmente importante en el alineamiento de secuencias de proteínas debido a la frecuencia variable de los diferentes aminoácidos. Hay dos familias amplias de matrices de puntuación, cada una con modificaciones adicionales para escenarios específicos:

PAM
FLOR

Penalización por brecha

Al alinear secuencias, a menudo hay espacios (es decir, indeles), a veces grandes. Biológicamente, es más probable que se produzca una gran brecha como una eliminación grande en lugar de múltiples eliminaciones únicas. Por lo tanto, dos indeles pequeños deberían tener peor puntuación que uno grande. La forma más sencilla y común de hacerlo es mediante una puntuación de inicio de intervalo grande para un nuevo indel y una puntuación de extensión de intervalo más pequeña para cada letra que amplía el indel. Por ejemplo, un nuevo indel puede costar -5 y un indel extendido puede costar -1. De esta manera se logra 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 de 4 largos con preferencia sobre múltiples espacios pequeños.

Presentación avanzada del algoritmo.

Las puntuaciones de los personajes 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 brecha de −5, tendría la siguiente puntuación:

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 × 5) + 7 + (−4) + 0 + (−1) + 0 = 1

Para encontrar la alineación con la puntuación más alta, se asigna una matriz (o matriz ) bidimensional F. La entrada en la fila i y la columna j se indica 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 es de . 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). $F_{ij}$ $O(nm)$ $\Theta (\min\{n,m\})$ $O(nm)$

A medida que avanza el algoritmo, se asignará la puntuación óptima para la alineación de los primeros caracteres en A y los primeros caracteres en B. Luego se aplica el principio de optimización de la siguiente manera: $F_{ij}$ $i=0,\dotsc,n$ $j=0,\dotsc,m$

Base:

F_{0j}=d*j

F_{i0}=d*i

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

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 tiene el siguiente aspecto:

d ← Puntuación de penalización por espacio para i = 0 a  la longitud (A) F(yo,0) ← re * yopara j = 0 a la  longitud (B) F(0,j) ← re * 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) ← max (Coincidir, Insertar, Eliminar) }

Una vez calculada la matriz F , la entrada otorga la puntuación máxima entre todas las alineaciones posibles. Para calcular una alineación que realmente proporcione esta puntuación, comience desde la celda inferior derecha y compare el valor con las tres fuentes posibles (Coincidir, Insertar y Eliminar arriba) para ver de cuál proviene. Si Coincide, entonces y están alineados, si Eliminar, entonces se alinea con un espacio, y si Insertar, entonces se alinea con un espacio. (En general, más de una opción puede tener el mismo valor, lo que lleva a alineamientos óptimos alternativos). $F_{nm}$ ${\ Displaystyle A_ {i}}$ ${\ Displaystyle B_ {j}}$ ${\ Displaystyle A_ {i}}$ ${\ Displaystyle B_ {j}}$

AlineaciónA ← ""AlineaciónB ← ""yo ← 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 }}

Complejidad

Calcular la puntuación de cada celda de la tabla es una operación. Por tanto, la complejidad temporal del algoritmo para dos secuencias de longitud y es . ^[4] Se ha demostrado que es posible mejorar el tiempo de ejecución utilizando el Método de los Cuatro Rusos . ^[4]^[5] Dado que el algoritmo llena una tabla, la complejidad del espacio es ^[4] $F_{ij}$ $O(1)$ $n$ $m$ $O(mn)$ $O(mn/\log n)$ $n\times m$ $O(mn).$

Notas históricas y desarrollo de algoritmos.

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 penaliza únicamente por coincidencias y desajustes, y los espacios no tienen penalización ( d =0). La publicación original de 1970 sugiere la recursividad . $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. El artículo también señala que la recursividad puede acomodar fórmulas arbitrarias de penalización de brechas:

Un factor de penalización, un número que se resta por cada brecha realizada, puede evaluarse como una barrera para permitir la brecha. El factor de penalización podría ser una función del tamaño y/o dirección del espacio. [página 444]

^{Más tarde [6],} David Sankoff introdujo un mejor algoritmo de programación dinámica con tiempo de ejecución cuadrático para el mismo problema (sin penalización por espacio). TK Vintsyuk [7] descubrió de forma independiente algoritmos similares de tiempo cuadrático ^[7] en 1968 para el procesamiento del habla ( "time warping" ), y por Robert A. Wagner y Michael J. Fischer ^[8] 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, introducida por Vladimir Levenshtein . Peter H. Sellers demostró ^[9] en 1974 que los dos problemas son equivalentes.

El algoritmo Needleman-Wunsch todavía se usa ampliamente para una alineación global óptima , particularmente cuando la calidad de la alineación global es de suma importancia. Sin embargo, el algoritmo es caro con respecto al tiempo y al espacio, proporcional al producto de la longitud de dos secuencias y, por tanto, no es adecuado para secuencias largas.

El desarrollo reciente se ha centrado en mejorar el costo de tiempo y espacio del algoritmo manteniendo la calidad. Por ejemplo, en 2013, un algoritmo de alineación de secuencia global óptima rápida (FOGSAA) ^[10] 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 al 90 % para secuencias de nucleótidos muy similares (con > 80 % de similitud) y del 54 al 70 % para secuencias que tienen entre 30 y 80 % de similitud.

Aplicaciones fuera de la bioinformática

Visión estéreo por computadora

La coincidencia estéreo es un paso esencial en el proceso de reconstrucción 3D a partir de un par de imágenes estéreo. Una vez rectificadas las imágenes, se puede establecer una analogía entre alinear secuencias de nucleótidos y proteínas y hacer coincidir 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 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 la lente de una cámara muestra distorsiones inesperadas , como las generadas por las gotas de lluvia, las cubiertas resistentes a la intemperie o el 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 (o matriz) tridimensional. Los experimentos demostraron que dicha extensión permite una coincidencia densa de píxeles entre imágenes no rectificadas o distorsionadas. ^[11]

Ver también

Referencias

^ abc Needleman, Saul B. y Wunsch, Christian D. (1970). "Un método general aplicable a la búsqueda de similitudes en la secuencia de aminoácidos de dos proteínas". Revista de biología molecular . 48 (3): 443–53. doi :10.1016/0022-2836(70)90057-4. PMID 5420325.
^ "bioinformática" . Consultado el 10 de septiembre de 2014 .
^ Gagniuc, Paul A. (2021). Algoritmos en bioinformática: teoría e implementación (1ª ed.). Hoboken, Nueva Jersey: John Wiley & Sons. ISBN 978-1-119-69800-5. OCLC 1240827446.{{cite book}}: Mantenimiento CS1: fecha y año ( enlace )
^ abc Wing-Kin., Sung (2010). Algoritmos en bioinformática: una introducción práctica . Boca Ratón: Chapman & Hall/CRC Press. págs. 34-35. ISBN 9781420070330. OCLC 429634761.
^ Masek, William; Paterson, Michael (febrero de 1980). "Un algoritmo más rápido que calcula las distancias de edición de cadenas". Revista de Ciencias de la Computación y de Sistemas . 20 : 18–31. doi : 10.1016/0022-0000(80)90002-1 .
^ Sankoff D (1972). "Secuencias coincidentes bajo restricciones de eliminación/inserción". Actas de la Academia Nacional de Ciencias de Estados Unidos . 69 (1): 4–6. Código bibliográfico : 1972PNAS...69....4S. doi : 10.1073/pnas.69.1.4 . PMC 427531 . PMID 4500555.
^ Vintsyuk TK (1968). "Discriminación del habla por programación dinámica". Kibernética . 4 : 81–88. doi :10.1007/BF01074755. S2CID 123081024.
^ Wagner RA, Fischer MJ (1974). "El problema de la corrección cadena a cadena". Revista de la ACM . 21 (1): 168-173. doi : 10.1145/321796.321811 . S2CID 13381535.
^ Vendedores PH (1974). "Sobre la teoría y cálculo de distancias evolutivas". Revista SIAM de Matemática Aplicada . 26 (4): 787–793. doi :10.1137/0126070.
^ Chakraborty, Angana; Bandyopadhyay, Sanghamitra (29 de abril de 2013). "FOGSAA: Algoritmo de alineación de secuencia global óptima y rápida". Informes científicos . 3 : 1746. Código bibliográfico : 2013NatSR...3E1746C. doi :10.1038/srep01746. PMC 3638164 . PMID 23624407.
^ Thevenon, J; Martínez-del-Rincón, J; Dieny, R; Nebel, JC (2012). Coincidencia densa de píxeles entre imágenes no rectificadas y distorsionadas mediante programación dinámica. Conferencia internacional sobre teoría y aplicaciones de la visión por computadora. Roma.

enlaces externos

NW-align: un programa de alineación de secuencia a secuencia de proteínas mediante el algoritmo Needleman-Wunsch (servidor en línea y código fuente)
Una demostración en vivo basada en Javascript de Needleman–Wunsch
Una explicación visual interactiva basada en Javascript del algoritmo Needleman-Wunsch
Técnicas de alineación de secuencias en el blog de tecnología
Paquete Biostrings R que implementa el algoritmo Needleman-Wunsch, entre otros