2.6: Alineación múltiple

Alineación de tres secuencias

Ahora que hemos visto cómo alinear un par de secuencias, es natural extender esta idea a múltiples secuencias. Supongamos que nos gustaría encontrar el alineamiento óptimo de 3 secuencias. ¿Cómo podríamos proceder?

Recordemos que cuando alineamos dos secuencias S y T, elegimos el máximo de tres posibilidades para la posición final del alineamiento (secuencia T alineada contra un hueco, secuencia S alineada contra un hueco, o secuencia S alineada contra secuencia T):

\ [F_ {i, j} =\ max\ izquierda\ {\ begin {array} {l}
F_ {i, j-1} +d\\
F_ {i-1, j} +d\\
F_ {i-1, j-1} +s\ izquierda (S_ {i}, T_ {j}\ derecha)
\ end {array}\ derecha. \ nonumber\]

Para tres secuencias S, T y U, hay siete posibilidades para la posición final del alineamiento. Es decir, hay tres formas de tener dos huecos en la posición final, tres formas de tener un hueco, y una manera de tener las tres secuencias alineadas\ (\ left (\ left (\ begin {array} {l}
3\\
1
\ end {array}\ right) +\ left (\ begin {array} {l}
3\\
2
\ end {array}\ right) +\ left (\ begin {array} {l}
3\\
3
\ end {array}\ right) =7\ right)\). La regla de actualización es ahora:

\ [F_ {i, j, k} =\ max\ izquierda\ {\ begin {array} {l}
F_ {i-1, j, k} +s\ izquierda (S_ {i}, -, -\ derecha)\\
F_ {i, j-1, k} +s\ izquierda (-, T_ {j}, -\ derecha)\
F_ {i, j, k-1} +s\ izquierda (-, -, U_ {k}\ derecha)\
F_ {i-1, j-1, k} +s\ izquierda (S_ {i}, T_ {j}, -\ derecha)\\
F_ {i-1, j, k-1} +s\ izquierda ( S_ {i}, -, U_ {k}\ derecha)\
F_ {i, j-1, k-1} +s\ izquierda (-, T_ {j}, U_ {k}\ derecha)\
F_ {i-1, j-1, k-1} +s\ izquierda (S_ {i}, T_ {j}, U_ {k}\ derecha)
\ end {array}\ derecho. \ nonumber\]

donde s es la función que describe las puntuaciones de brecha, coincidencia y desajuste.

Este enfoque, sin embargo, es exponencial en el número de secuencias que estamos alineando. Si tenemos k secuencias de longitud\(n\), calcular la alineación óptima usando una matriz de programación dinámica k-dimensional lleva\(O\left((2 n)^{k}\right)\) tiempo (el factor de 2 resulta del hecho de que un k-cube tiene 2 ^k vértices, por lo que necesitamos tomar el máximo de 2 ^k − 1 celdas vecinas para cada entrada en la matriz de puntuación). Como puedes imaginar, este algoritmo rápidamente se vuelve poco práctico a medida que aumenta el número de secuencias.

Alineación múltiple heurística

Un enfoque comúnmente utilizado para el alineamiento de múltiples secuencias se llama alineación múltiple progresiva. Como- sume que conocemos el árbol evolutivo relacionando cada una de nuestras secuencias. Luego comenzamos realizando una alineación por pares de las dos secuencias más estrechamente relacionadas. Esta alineación inicial se llama alineación de semillas. Luego procedemos a alinear la siguiente secuencia más cercana a la semilla, y esta nueva alineación reemplaza a la semilla. Este proceso continúa hasta que se produce la alineación final.

En la práctica, generalmente no conocemos el árbol evolutivo (o árbol guía), esta técnica generalmente se empareja con algún tipo de algoritmo de agrupamiento que puede usar una medida de similitud de baja resolución para generar una estimación del árbol.

Si bien el tiempo de ejecución de este enfoque heurístico se mejora mucho con respecto al método anterior (polinomio en el número de secuencias en lugar de exponencial), ya no podemos garantizar que el alineamiento final sea óptimo.

Tenga en cuenta que aún no hemos explicado cómo alinear una secuencia contra una alineación existente. Un enfoque posible sería realizar alineaciones por pares de la nueva secuencia con cada secuencia ya en el alineamiento semilla (suponemos que cualquier posición en el alineamiento de semillas que ya sea un hueco seguirá siendo una). Luego podemos agregar la nueva secuencia al alineamiento de semillas basado en el mejor alineamiento por pares (este enfoque fue descrito previamente por Feng y Doolittle [4]). Alternativamente, podemos idear una función para puntuar la alineación de una secuencia con otra alineación (tales funciones de puntuación a menudo se basan en la suma por pares de las puntuaciones en cada posición).

El diseño de mejores herramientas de alineación de secuencias múltiples es un área activa de investigación. En la sección 2.7 se detallan algunos de los trabajos actuales en este campo.