stringtranslate.com

Alineación estadística rápida

El alineamiento estadístico rápido o FSA es un programa de alineamiento de secuencias múltiples para alinear muchas proteínas, ARN o secuencias largas de ADN genómico . Junto con MUSCLE y MAFFT , FSA es uno de los pocos programas de alineamiento de secuencias que puede alinear conjuntos de datos de cientos o miles de secuencias. FSA utiliza un criterio de optimización diferente que le permite identificar secuencias no homólogas de manera más confiable que estos otros programas, aunque esta mayor precisión se produce a costa de una menor velocidad.

Actualmente, FSA se está utilizando para múltiples proyectos, incluida la secuenciación de nuevos genomas de gusanos y el análisis de la unión de factores de transcripción in vivo en moscas.

Entrada/Salida

Este programa acepta secuencias en formato FASTA y genera alineaciones en formato FASTA o formato Estocolmo .

Algoritmo

El algoritmo para la alineación de las secuencias de entrada tiene 4 componentes principales.

Modelo de Markov oculto por pares para generar probabilidades posteriores

El algoritmo comienza determinando las probabilidades posteriores de alineación 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 estar alineadas de manera poco confiable. Estas probabilidades también permiten la predicción y estimación de la homología entre cualquier par de secuencias. Se utiliza un modelo de Markov oculto de cinco estados estándar (Pair HMM) para determinar estas probabilidades posteriores de alineación para dos secuencias de entrada cualesquiera. El modelo Pair HMM 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 la cantidad de comparaciones por pares necesarias para determinar las distribuciones de probabilidad posterior de dos pares de secuencias es computacionalmente costosa y cuadrática en la cantidad de secuencias que se están alineando, se reduce mediante el uso de un enfoque aleatorio inspirado en la teoría de gráficos aleatorios de Erdos-Renyi. Esto reduce significativamente los tiempos de ejecución de los conjuntos de datos y el costo computacional de ejecutar las alineaciones múltiples.

Fusión de probabilidades

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

Recocido de secuencias

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

FSA utiliza la técnica de recocido de secuencias para superar este problema. Las probabilidades posteriores ordenadas se utilizan con la técnica de recocido de secuencias para generar una alineación múltiple. La técnica encuentra la alineación entre dos secuencias que minimiza la distancia esperada a la verdad. 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 verdad, encuentra a la inversa la alineación con la precisión máxima 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 luego como una función objetivo que comienza con las secuencias no alineadas (alineación nula) y alinea caracteres en diferentes columnas en función de la precisión creciente de una alineación.

Ordenación de la alineación

FSA alinea múltiples secuencias basándose en la homología dentro de las columnas en lugar de considerar estrictamente las indels y las sustituciones. Como tal, FSA considera que las alineaciones son equivalentes si para cada posición a lo largo de las secuencias en ambas alineaciones, se puede hacer la misma afirmación sobre la homología. Por ejemplo, al considerar comparaciones por pares, si hay un espacio en una posición específica en dos alineaciones, entonces se puede decir que las dos secuencias que se comparan no son homólogas en dicha posición. Esto puede dar como resultado alineaciones en las que los eventos de apertura de espacios pueden diferir y, aun así, considerarse equivalentes. Como tal, FSA elige generar la alineación en la que hay una cantidad mínima de "aperturas de espacios".

Paralelización

Para manejar conjuntos de datos demasiado grandes, FSA puede dividir el trabajo de ejecutar todas las comparaciones y alineaciones por pares necesarias en diferentes procesadores. Esto se maneja mediante el uso de una estrategia de "fragmentación de tamaño fijo" que distribuye las comparaciones por pares en fragmentos a cada procesador disponible. Por lo tanto, cada procesador puede ejecutar el cálculo de probabilidad posterior en un fragmento de comparaciones por pares antes de fusionar los datos recopilados nuevamente en un solo procesador para la recocción de secuencias.

Visualización

Los resultados de la alineación de secuencias múltiples con FSA se pueden visualizar en la propia interfaz gráfica de usuario de FSA. La interfaz gráfica de usuario puede mostrar y etiquetar con colores diferentes medidas de calidad de alineación en las columnas de caracteres dentro de la propia alineación. Las cinco medidas diferentes que se pueden observar y que se aproximan con el modelo FSA incluyen precisión, sensibilidad, certeza, especificidad y consistencia.

Comparaciones con otros programas

FSA ha sido evaluada en comparación con múltiples bases de datos de alineamiento para proteínas (SABmark 1.65 y BAliBASE 3), ARN (BRAliBase 2.1 y Consanmix80) y secuencias de ADN. Estas evaluaciones comparativas se llevaron a cabo junto con otros programas de alineamiento populares como ClustalW, MAFFT, MUSCLE, T-Coffee, etc. En general, en el momento en que se recibió el resumen y el artículo de investigación de FSA para su revisión, FSA superó a la mayoría de los programas de alineamiento en precisión y valores predictivos positivos, con sensibilidades a la par con los programas de mejor desempeño como MAFFT y ProbConsRNA. También se realizaron comparaciones de tiempo de ejecución comparando los tiempos para alinear las secuencias ribosomales 16S. MAFFT realizó el alineamiento más rápido que los otros programas de alineamiento, mientras que MUSCLE y FSA (usando un HMM de 3 estados y con refinamiento iterativo deshabilitado) fueron los siguientes programas más rápidos.

Referencias

Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L (2009). "Alineación estadística rápida". PLOS Computational Biology . 5 (5): e1000392. Bibcode :2009PLSCB...5E0392B. doi : 10.1371/journal.pcbi.1000392 . PMC  2684580 . PMID  19478997.

Schwartz AS, Pachter L (2007) Alineamiento múltiple mediante recocido de secuencias. Bioinformática 23: e24-9.

Eddy SR. Alineamiento múltiple utilizando modelos ocultos de Markov. Proc Int Conf Intell Syst Mol Biol. 1995;3:114-20. PMID 7584426.

Enlaces externos