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.