7.2: Alineación de Fuerza Bruta

Un enfoque (malo) para la alineación de secuencias es alinear las dos secuencias de todas las formas posibles, puntuar las alineaciones con un sistema de puntuación supuesto y determinar la alineación de mayor puntuación. El problema con este enfoque de fuerza bruta es que el número de alineamientos posibles crece exponencialmente con la longitud de la secuencia; y para secuencias de longitud razonable, el cálculo ya es imposible. Por ejemplo, el número de formas de alinear dos secuencias de 50 caracteres cada una -un problema de alineación bastante pequeño- es aproximadamente\(1.5 \times 10^{37}\), ya un número asombrosamente grande. Es informativo contar el número de alineamientos posibles entre dos secuencias ya que se utiliza un algoritmo similar para el alineamiento de secuencias.

Supongamos que queremos alinear dos secuencias. Se permiten huecos en cualquiera de las secuencias, pero un hueco no se puede alinear con un hueco. A modo de ilustración, demostramos las tres formas en que el primer carácter del alfabeto en minúscula y el alfabeto en minúscula pueden alinearse:

y las cinco formas en que los dos primeros caracteres del alfabeto en minúscula pueden alinearse con el primer carácter del alfabeto minúscula:

Una relación de recursión para el número total de alineaciones posibles de una secuencia de\(i\) caracteres con una secuencia de\(j\) caracteres puede derivarse considerando la alineación del último carácter. Hay tres posibilidades que ilustramos asumiendo que el carácter\(i\) th es '\(\mathrm{F}\)' y el carácter\(j\) th es '\(\mathrm{d}\)':

(1) los\(i-1\) caracteres de la primera secuencia ya están alineados con los\(j-1\) caracteres de la segunda secuencia, y el carácter\(i\) th de la primera secuencia se alinea exactamente con el carácter\(j\) th de la segunda secuencia:

(2) los\(i-1\) caracteres de la primera secuencia se alinean con los\(j\) caracteres de la segunda secuencia y el carácter\(i\) th de la primera secuencia se alinea con un hueco en la segunda secuencia

(3) los\(i\) caracteres de la primera secuencia se alinean con los\(j-1\) caracteres de la segunda secuencia y un hueco en la primera secuencia se alinea con el carácter\(j\) th de la segunda secuencia iil

\(\cdots d\)

Si\(C(i, j)\) es el número de formas de alinear una secuencia de\(i\) caracteres con una secuencia de\(j\) caracteres, entonces, a partir de nuestro recuento,

\[C(i, j)=C(i-1, j-1)+C(i-1, j)+C(i, j-1) \nonumber \]

Esta relación de recursión requiere condiciones de contorno. Debido a que solo hay una manera de alinear una secuencia de\(i>0\) caracteres contra una secuencia de caracteres cero (es decir,\(i\) caracteres contra\(i\) huecos) las condiciones de contorno son\(C(0, j)=C(i, 0)=1\) para todos También\(i, j>0\) podemos agregar el adicional condición límite\(C(0,0)=1\), obtenida del resultado conocido\(C(1,1)=3\).

Usando la relación de recursión (7.1), podemos construir la siguiente matriz dinámica para contar el número de formas de alinear las dos secuencias de cinco caracteres\(a_{1} a_{2} a_{3} a_{4} a_{5}\) y\(b_{1} b_{2} b_{3} b_{4} b_{5}\):

\(\begin{array}{ccccccc} & - & b_{1} & b_{2} & b_{3} & b_{4} & b_{5} \\[4pt] - & 1 & 1 & 1 & 1 & 1 & 1 \\[4pt] a_{1} & 1 & 3 & 5 & 7 & 9 & 11 \\[4pt] a_{2} & 1 & 5 & 13 & 25 & 41 & 61 \\[4pt] a_{3} & 1 & 7 & 25 & 63 & 129 & 231 \\[4pt] a_{4} & 1 & 9 & 41 & 129 & 321 & 681 \\[4pt] a_{5} & 1 & 11 & 61 & 231 & 681 & 1683\end{array}\)

El tamaño de esta matriz dinámica es\(6 \times 6\), y por conveniencia etiquetamos las filas y columnas a partir de cero (es decir, fila 0, fila\(1, \ldots\), fila 5). Esta matriz se construyó escribiendo primero\(-a_{1} a_{2} a_{3} a_{4} a_{5}\) a la izquierda de la matriz y\(-b_{1} b_{2} b_{3} b_{4} b_{5}\) encima de la matriz, luego rellenando unos a través de la fila cero y abajo de la columna cero para satisfacer las condiciones de contorno, y finalmente aplicando la relación de recursión directamente yendo a través de la primera fila de izquierda a derecha, la segunda fila de izquierda a derecha, etc. Para demostrar el relleno de la matriz, tenemos a través de la primera fila:\(1+1+1=3,1+1+3=5,1+1+5=7\), etc, y a través de la segunda fila:\(1+3+1=5,3+5+5=13,5+7+13=25\), etc. Finalmente, el último elemento ingresado da el número de formas de alinear dos secuencias de cinco caracteres: 1683, ya un número notablemente grande.

Es posible resolver analíticamente la relación de recursión (7.1) para el\(C(i, j)\) uso de funciones generadoras. Aunque el método de solución es interesante -y de hecho me lo demostró un estudiante- el resultado analítico final es desordenado y lo omitimos aquí. En general, el cálculo de\(C(i, j)\) se realiza mejor numéricamente mediante la construcción de la matriz dinámica.