7.4: Brechas

La evidencia empírica sugiere que las brechas se agrupan, tanto en secuencias de nucleótidos como de proteínas. La agrupación generalmente se modela por diferentes penalizaciones por apertura de brecha\(\left(g_{o}\right)\) y extensión de brecha\(\left(g_{e}\right)\), con\(g_{o}<g_{e}<0\). Por ejemplo, el esquema de puntuación predeterminado para el software BLASTN ampliamente utilizado es\(+1\) para una coincidencia de nucleótidos,\(-3\) para un desajuste de nucleótidos,\(-5\) para una apertura de hueco y\(-2\) para una extensión de hueco.

Tener dos tipos de brechas (apertura y extensión) complica el algoritmo de programación dinámica. Cuando se agrega un indel a una alineación existente, el incremento de puntuación depende de si el indel es una abertura de hueco o una extensión de hueco. Por ejemplo, la alineación extendida

\[\begin{array}{ll} \mathrm{AB} & \mathrm{AB}- \\[4pt] 11 & \text { to } & 111 \\[4pt] \mathrm{ab} & & \mathrm{abc} \end{array} \nonumber \]

agrega una penalización por apertura de brecha\(g_{o}\) al marcador, mientras que

\[\begin{array}{ll} \text { A- } & \text { A- } \\[4pt] \text { II to } & \text { ||| } \\[4pt] \text { ab } & & \text { abc } \end{array} \nonumber \]

agrega una penalización por extensión de brecha\(g_{e}\) al marcador. El incremento de puntuación depende no sólo del par de alineación actual, sino también del par previamente alineado.

El par de alineación final de una secuencia de longitud\(i\) con una secuencia de longitud\(j\) puede ser una de tres posibilidades (arriba:abajo): (1)\(a_{i}: b_{j} ;\) (2)\(a_{i}:-;(3)-: b_{j}\). Solo para (1) es\(S\left(a_{i}, b_{j}\right)\) inequívoco el incremento de puntaje. Para (2) o (3), el incremento de puntaje depende de la presencia o ausencia de indels en los caracteres previamente alineados. Por ejemplo, para alineaciones que terminan con\(a_{i}:-\), el par de caracteres previamente alineado podría ser uno de (i)\(a_{i-1}: b_{j}\), (ii)\(-: b_{j}\), (iii)\(a_{i-1}:-\). Si el par de caracteres alineados anterior era (i) o (ii), el incremento de puntaje sería la penalización por apertura de hueco\(g_{o}\); si fuera (iii), el incremento de puntaje sería la penalización por extensión de hueco\(g_{e}\).

Para eliminar la ambigüedad que se produce con una sola matriz dinámica, necesitamos calcular tres matrices dinámicas simultáneamente, con elementos de matriz denotados por\(T(i, j), T_{-}(i, j)\) y\(T^{-}(i, j)\), correspondientes a los tres tipos de pares de alineación. Las relaciones de recursión son

\[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-1)+S\left(a_{i}, b_{j}\right) \\[4pt] T^{-}(i-1, j-1)+S\left(a_{i}, b_{j}\right) \end{array}\right. \nonumber \]

(2)\(a_{i}:-\)

\[T_{-}(i, j)=\max \left\{\begin{array}{l} T(i-1, j)+g_{o} \\[4pt] T_{-}(i-1, j)+g_{e} \\[4pt] T^{-}(i-1, j)+g_{o} \end{array}\right. \nonumber \]

(3)\(-: b_{j}\)

\[T^{-}(i, j)=\max \left\{\begin{array}{l} T(i, j-1)+g_{o} \\[4pt] T_{-}(i, j-1)+g_{o} \\[4pt] T^{-}(i, j-1)+g_{e} \end{array}\right. \nonumber \]

Para alinear una secuencia de longitud\(n\) con una secuencia de longitud\(m\), la mejor puntuación de alineación es la máxima de las puntuaciones obtenidas de las tres matrices dinámicas:

\[T_{\text {opt }}(n, m)=\max \left\{\begin{array}{l} T(n, m), \\[4pt] T_{-}(n, m), \\[4pt] T^{-}(n, m) . \end{array}\right. \nonumber \]

El algoritmo de rastreo para encontrar la mejor alineación procede como antes comenzando con el elemento de la matriz correspondiente a la mejor puntuación de alineación\(T_{\mathrm{opt}}(n, m)\), y trazando de nuevo al elemento de la matriz que determinó esta puntuación. La alineación óptima se construye de último a primero como antes, pero ahora puede ocurrir un cambio entre las tres matrices dinámicas.