Alineación estadística rápida

El algoritmo comienza determinando primero las probabilidades posteriores de alineación.${\displaystyle \mathbb {P} (A|X,Y)}$entre dos secuencias aleatorias cualesquiera del conjunto de secuencias que se están alineando. Las probabilidades posteriores para cada columna refuerzan la predicción de la probabilidad de alineación entre un par de secuencias y también filtran las columnas que pueden alinearse de forma poco fiable. Estas probabilidades también permiten predecir y estimar la homología entre cualquier par de secuencias. Se utiliza un modelo oculto de Markov de pares estándar de cinco estados (HMM de pares) para determinar estas probabilidades posteriores de alineación para cualquier par de secuencias de entrada. El modelo HMM de pares utiliza dos conjuntos de estados de eliminación (D) e inserción (I) para tener en cuenta la eliminación e inserción de símbolos entre dos secuencias alineadas, pero también puede tener tres estados sin una pérdida significativa de precisión.

Dado que el número de comparaciones por pares necesarias para determinar las distribuciones de probabilidad posterior de cualquier par de secuencias es computacionalmente costoso y cuadrático con respecto a la cantidad de secuencias que se alinean, se reduce mediante un enfoque aleatorio inspirado en la teoría de grafos aleatorios de Erdos-Renyi. Esto reduce significativamente los tiempos de ejecución de los conjuntos de datos y el costo computacional de realizar los alineamientos múltiples.

Las probabilidades posteriores para cada columna en los pares de secuencias se ordenan utilizando una función de ponderación que emplea un algoritmo de ascenso más pronunciado.

La mayoría de los programas existentes que ejecutan algoritmos de alineación de secuencias múltiples se basan en la alineación progresiva, donde el proceso comienza con una "alineación nula", un estado en el que ninguna de las secuencias se ha alineado. El conjunto de secuencias se alinea mediante comparaciones por pares o mediante la alineación de pares de alineaciones parciales de subsecuencias. Este proceso puede causar problemas en la alineación, ya que la alineación de secuencias múltiples resultante puede depender, y de hecho dependerá, en gran medida de las secuencias alineadas inicialmente. No se realiza ninguna realineación de las secuencias previamente alineadas que pueda corregir la alineación de secuencias múltiples.

FSA utiliza la técnica de recocido de secuencias para superar este problema. Las probabilidades posteriores ordenadas se emplean con la técnica de recocido de secuencias para generar un alineamiento múltiple. Esta técnica encuentra el alineamiento entre dos secuencias que minimiza la distancia esperada a la secuencia real. En este caso, la distancia entre dos secuencias es el número de columnas en las que el carácter de una secuencia no es homólogo al carácter de la misma columna en la segunda secuencia.

La técnica de recocido de secuencias, al determinar una alineación con la distancia mínima esperada a la alineación verdadera, encuentra a su vez la alineación con la máxima precisión esperada. La precisión de una alineación depende de una alineación "verdadera" como referencia e indica la fracción de columnas donde las secuencias son homólogas. Esta precisión se utiliza como función objetivo, partiendo de las secuencias no alineadas (alineación nula), y alinea los caracteres en diferentes columnas según la precisión creciente de la alineación.

FSA alinea múltiples secuencias basándose en la homología dentro de las columnas, en lugar de considerar únicamente inserciones, deleciones y sustituciones. Por lo tanto, FSA considera que dos alineamientos son equivalentes si, para cada posición de las secuencias en ambos alineamientos, se puede afirmar lo mismo sobre la homología. Por ejemplo, al considerar comparaciones por pares, si existe un hueco en una posición específica en dos alineamientos, se puede decir que las dos secuencias que se comparan no son homólogas en dicha posición. Esto puede dar lugar a alineamientos donde los eventos de apertura de huecos pueden diferir y aun así considerarse equivalentes. Por consiguiente, FSA elige generar el alineamiento con la menor cantidad de "aperturas de huecos".