7.3: Programación dinámica

Dos secuencias de tamaño razonable no pueden alinearse por la fuerza bruta. Por suerte, hay otro algoritmo prestado de la informática, la programación dinámica, que hace uso de una matriz dinámica.

Lo que se necesita es un sistema de puntuación para juzgar la calidad de una alineación. El objetivo es encontrar la alineación que tenga la máxima puntuación. Suponemos que la alineación de carácter\(a_{i}\) con carácter\(b_{j}\) tiene la puntuación\(S\left(a_{i}, b_{j}\right) .\) Por ejemplo, al alinear dos secuencias de ADN, se puede puntuar una coincidencia (A-A, C-C, T-T, G-G) como\(+2\), y un desajuste\((\mathrm{A}-\mathrm{C}, \mathrm{A}-\mathrm{T}, \mathrm{A}-\mathrm{G}\), etc. \()\)anotó como\(-1\). También asumimos que un indel (un nucleótido alineado con un hueco) es puntuado como\(g\), siendo un valor típico para el alineamiento del ADN\(g=-2\). En la siguiente sección, desarrollamos un modelo mejor y más ampliamente utilizado para la puntuación de indel que distingue las aberturas de brecha de las extensiones de brecha.

Ahora, vamos a\(T(i, j)\) denotar la puntuación máxima para alinear una secuencia de longitud\(i\) con una secuencia de longitud\(j .\) Podemos calcular\(T(i, j)\) siempre que sepamos\(T(i-\)\(1, j-1), T(i-1, j)\) y\(T(i, j-1)\). En efecto, nuestra lógica es similar a la utilizada al contar el número total de alineaciones. De nuevo, hay tres formas de calcular los\(T(i, j):(1) i-1\) caracteres de la primera secuencia que se alinean con los\(j-1\) caracteres de la segunda secuencia con puntuación máxima\(T(i-1, j-1)\), y el carácter\(i\) th de la primera secuencia se alinea con el \(j\)el carácter de la segunda secuencia con puntuación máxima actualizada\(T(i-1, j-1)+S\left(a_{i}, b_{j}\right) ;(2) i-1\) los caracteres de la primera secuencia se alinean con los\(j\) caracteres de la segunda secuencia con puntuación máxima\(T(i-\)\(1, j)\), y \(i\)el carácter de la primera secuencia se alinea con un hueco en la segunda secuencia con puntuación máxima actualizada\(T(i-1, j)+g\), o; (3) los\(i\) caracteres de la primera secuencia se alinean con los\(j-1\) caracteres de la segunda secuencia con el máximo y un hueco en la primera secuencia se alinea con el carácter\(j\) th de la segunda secuencia con la puntuación máxima actualizada\(T(i, j-1)+g\).\(T(i, j-1)\) Luego comparamos estos tres puntajes y asignamos\(T(i, j)\) para ser el máximo; es decir,

\[T(i, j)=\max \left\{\begin{array}{l} T(i-1, j-1)+S\left(a_{i}, b_{j}\right) \\[4pt] T(i-1, j)+g \\[4pt] T(i, j-1)+g \end{array}\right. \nonumber \]

Las condiciones de contorno dan la puntuación de alinear una secuencia con una secuencia nula de huecos, de modo que

\[T(i, 0)=T(0, i)=i g, \quad i>0 \nonumber \]

con\(T(0,0)=0\).

La recursión\((7.2)\), junto con las condiciones de contorno (7.3), se puede utilizar para construir una matriz dinámica. La puntuación de la mejor alineación viene dada entonces por el último elemento rellenado de la matriz, que para alinear una secuencia de longitud\(n\) con una secuencia de longitud\(m\) es\(T(n, m)\). Además de esta puntuación, sin embargo, también queremos determinar la alineación en sí misma. La alineación se puede obtener trazando la ruta en la matriz dinámica que se siguió para calcular cada elemento de la matriz\(T(i, j)\). Podría haber más de un camino, para que el mejor alineamiento pueda ser degenerado.

La alineación de secuencias siempre se realiza computacionalmente, y hay excelentes herramientas de software disponibles gratuitamente en la web (ver $7.6). Solo para ilustrar el algoritmo de programación dinámica, calculamos a mano la matriz dinámica para alinear dos secuencias cortas de ADN GGAT y GAATT, puntuando una coincidencia como\(+2\), un desajuste como\(-1\) y un indel como\(-2\):

\(\begin{array}{ccccccc} & - & \mathrm{G} & \mathrm{A} & \mathrm{A} & \mathrm{T} & \mathrm{T} \\[4pt] - & 0 & -2 & -4 & -6 & -8 & -10 \\[4pt] \mathrm{G} & -2 & 2 & 0 & -2 & -4 & -6 \\[4pt] \mathrm{G} & -4 & 0 & 1 & -1 & -3 & -5 \\[4pt] \mathrm{~A} & -6 & -2 & 2 & 3 & 1 & -1 \\[4pt] \mathrm{~T} & -8 & -4 & 0 & 1 & 5 & 3\end{array}\)

En nuestro cálculo de la mano, las dos secuencias a alinear van hacia la izquierda y por encima de la matriz dinámica, liderando con un carácter de gap '\(^{\prime}\)'. A continuación, la fila 0 y la columna 0 se rellenan con las condiciones de contorno, comenzando con 0 en posición\((0,0)\) e incrementándose por la penalización por hueco\(-2\) a través de la fila 0 y la columna descendente 0. La relación de recursión (7.2) se utiliza entonces para rellenar la matriz dinámica una fila a la vez moviéndose de izquierda a derecha y de arriba a abajo. Para determinar el elemento de la\((i, j)\) matriz, se deben comparar tres números y tomar el máximo: (1) inspeccionar los nucleótidos a la izquierda de la fila\(i\) y arriba de la columna\(j\) y agregar\(+2\) para una coincidencia o\(-1\) para un desajuste al elemento de\((i-1, j-1)\) matriz;\((2)\) agregar\(-2\) al elemento de\((i-1, j)\) matriz;\((3)\) agregar\(-2\) al elemento de\((i, j-1)\) matriz. Por ejemplo, el primer elemento matricial calculado 2 en la posición\((1,1)\) se determinó tomando el máximo de\((1) 0+2=2\), ya que\(G-G\) es una coincidencia;\((2)-2-2=-4 ;(3)-2-2=-4\). Puede poner a prueba su comprensión de la programación dinámica computando los otros elementos de la matriz.

Después de construir la matriz, el algoritmo de traceback que encuentra la mejor alineación comienza en el elemento inferior derecho de la matriz, aquí el elemento\((4,5)\) matriz con entrada 3. El elemento matriz utilizado para calcular 3 fue en\((4,4)\) (movimiento horizontal) o en\((3,4)\) (movimiento diagonal). Tener dos posibilidades implica que el mejor alineamiento es degenerado. Por ahora, elegimos arbitrariamente el movimiento diagonal. Construimos la alineación de principio a fin con GGAT en la parte superior y GAATT en la parte inferior:

T

\(\mathrm{T}\)

Ilustramos nuestra posición actual en la matriz dinámica eliminando todos los elementos que no están en la ruta de rastreo y ya no son accesibles:

\(\begin{array}{ccccccc} & - & G & A & A & T & T \\[4pt] - & 0 & -2 & -4 & -6 & -8 & \\[4pt] G & -2 & 2 & 0 & -2 & -4 & \\[4pt] G & -4 & 0 & 1 & -1 & -3 & \\[4pt] A & -6 & -2 & 2 & 3 & 1 & \\[4pt] T & & & & & & 3\end{array}\)

Empezamos de nuevo desde la entrada 1 a las\((3,4)\). Este valor vino de la entrada 3 en\((3,3)\) por un movimiento horizontal. Por lo tanto, la alineación se extiende a

-T

||
TT

donde se inserta un hueco en la secuencia superior para un movimiento horizontal. (Se inserta un hueco en la secuencia inferior para un movimiento vertical). La matriz dinámica ahora parece

\(\begin{array}{lcccccc} & - & G & A & A & T & T \\[4pt] - & 0 & -2 & -4 & -6 & & \\[4pt] G & -2 & 2 & 0 & -2 & & \\[4pt] G & -4 & 0 & 1 & -1 & & \\[4pt] A & -6 & -2 & 2 & 3 & 1 & \\[4pt] T & & & & & & 3\end{array}\)

Comenzando de nuevo desde la entrada 3 en\((3,3)\), este valor vino de la entrada 1\((2,2)\) en un movimiento diagonal, extendiendo la alineación a

A-T

|||
ATT La matriz dinámica ahora parece

Continuando de esta manera (tratar de hacer esto), la alineación final es

donde se acostumbra representar un carácter coincidente con dos puntos '\(:\)'. La ruta de rastreo en la matriz dinámica es

Si inicialmente se tomara el otro camino degenerado, la alineación final sería

GAATT

y la ruta de rastreo sería

La puntuación de ambas alineaciones se recalcula fácilmente para que sea la misma, con\(2-1+2-\)\(2+2=3\) y\(2-1+2+2-2=3\)

El algoritmo para alinear dos proteínas es similar, excepto que las puntuaciones de coincidencia y desapareamientos dependen del par de aminoácidos de alineación. Con veinte aminoácidos diferentes encontrados en las proteínas, la puntuación está representada por una matriz de\(20 \times 20\) sustitución. Las matrices más utilizadas son las series PAM y las series BLOSUM de matrices, siendo BLOSUM62 la matriz por defecto de uso común.