la determinación de regiones homólogas de secuencias moleculares se utiliza a menudo para la inferencia posterior de su función y evolución, y por lo tanto la alineación precisa de secuencias múltiples (MSA) de secuencias de ácidos nucleicos y proteínas es crucial., En consecuencia, ha habido un tremendo esfuerzo en el desarrollo e implementación de diferentes algoritmos de MSA, utilizando distintos enfoques para mejorar la precisión de alineación resultante.

la evaluación de la precisión de los programas de MSA a menudo se realiza mediante el empleo manual (o semiautomático) curado de bases de datos de secuencias como BAliBASE , PREFAB y SABmark . Hasta ahora, BAliBASE ha sido la base de datos de alineación más utilizada en la evaluación del rendimiento de diferentes programas de MSA. Se construyó utilizando secuencias de proteínas o modelos con estructuras tridimensionales conocidas., El último inicio, la versión 3.0, tuvo un aumento en el número de secuencias y alineaciones disponibles. Estas mejoras aparentemente han abordado las principales preocupaciones de Karplus y Hu con respecto al uso de BAliBASE para comparar algoritmos de MSA.

Las bases de datos de alineación proporcionan una fuente de alineaciones precisas para medir la precisión y velocidad de diferentes programas, pero también presentan varias desventajas. A pesar de que las alineaciones de las bases de datos se curan manualmente, todavía existe la posibilidad de desalineaciones que darían lugar a problemas de evaluación de la precisión., Los conjuntos de alineaciones siguen siendo bastante pequeños y pueden no representar la gama completa de escenarios de la evolución de las proteínas. Además, un inconveniente importante del uso de bases de datos de alineación es que los algoritmos pueden desarrollarse y ajustarse a las alineaciones presentes únicamente en estos conjuntos de datos.

recientemente ha habido varios paquetes de simulación de secuencias de ADN que incorporan indels, como MySSP y DAWG . MySSP ha sido ampliamente utilizado en diferentes estudios de inferencia filogenética y estimación de distancia evolutiva junto con precisión de alineación de ADN ., Para las proteínas, Lassmann y Sonnhammer en una comparación previa de Algoritmos de MSA utilizaron conjuntos de secuencias creados artificialmente generados por el programa de simulación Rose . Rose simula secuencias de proteínas permitiendo la aparición de indels. Los conjuntos de datos generados por Rose presentan sus propias limitaciones para el estudio de la precisión de la alineación. En Rose, el tamaño y el número de indel no representan adecuadamente los datos empíricos de las proteínas que han divergido para diferentes tiempos evolutivos. También el programa asume tasas evolutivas iguales de todos los sitios en la proteína.,

en este estudio presentamos un enfoque mejorado para evaluar la precisión de la alineación mediante el uso de secuencias de proteínas simuladas generadas por Simprot . Simprot es un programa de simulación avanzado que emplea una versión parametrizada de la distribución de inserción y eliminación de Qian y Goldstein (indel). Aunque la distribución original se derivó empíricamente de un subconjunto de alineaciones de secuencias de proteínas altamente divergentes, la versión parametrizada permite una simulación muy flexible de indels en secuencias para todos los niveles de divergencia de secuencias., Simprot también permite la sustitución variable y las tasas de indel en diferentes sitios mediante la implementación de tasas de sitios distribuidos gamma . Tres modelos de sustitución de aminoácidos (PMB, PAM y JTT) también están disponibles. Hemos utilizado Simprot para generar alineaciones conocidas con una amplia variedad de parámetros evolutivos, así como la última Base de datos BAliBASE de alineaciones curadas, para investigar la precisión y velocidad de los programas de software de alineación de secuencias múltiples de proteínas populares y disponibles públicamente.,

programas de alineación

hay muchos paquetes de computadoras disponibles que generan MSAs de secuencias de proteínas. Seleccionamos nueve de los programas más utilizados actualmente( por orden de fecha de publicación): Clustal W, Dialign2.2, T-Coffee, POA, Muscle, Mafft, ProbCons, Dialign-T y Kalign.

Clustal w versión 1.8

Este es probablemente el programa de alineación más utilizado y el más antiguo entre los paquetes probados. El software realiza una alineación progresiva, primero empleando una comparación de secuencia en pares mediante el cálculo de una matriz de distancia que almacena la divergencia de la secuencia., Después de obtener esta matriz, se construye una guía de árbol utilizando la Unión de vecinos, seguida del tercer y último paso donde las secuencias se alinean de acuerdo con el orden de ramas en el árbol de guía. El programa emplea dos penalizaciones de brecha en su procedimiento de alineación: apertura de brecha y extensión de brecha, y en el caso de polipéptidos, una matriz de peso de puntuación de aminoácidos completa. Estas penalizaciones de separación dependen principalmente de factores como la matriz de peso, la longitud de la secuencia y la similitud., En casos simples, Clustal W podría alinear con precisión los dominios y secuencias correspondientes de la estructura secundaria o terciaria conocida, mientras que en casos más complejos puede ser utilizado como un buen punto de partida para un mayor refinamiento.

Dialign2.2 Versión 2.2.1

Este programa utiliza un método diagonal para alinear secuencias local y globalmente. Dialign2. 2 no compara residuos individuales, sino tramos enteros ininterrumpidos (sin huecos, desajustes permitidos) de residuos que formarían diagonales en una comparación de matriz de puntos de dos secuencias., En consecuencia, no penaliza la inserción y extensión de huecos, y puede dejar segmentos no relacionados sin alinear. El primer paso en el procedimiento crea todas las alineaciones posibles en pares, almacenando una colección de diagonales que cumplen con ciertos criterios de consistencia sin asignaciones dobles o cruzadas conflictivas de residuos . Todas las diagonales guardadas se ponderan para definir entradas con la suma máxima de pesos, y luego se ordenan para determinar el grado de superposición, enfatizando la existencia de diagonales presentes en múltiples secuencias., Un algoritmo codicioso hace un procesamiento final, verificando las puntuaciones diagonales de arriba a abajo creando una alineación múltiple final. Los huecos se insertan al final de la creación de MSA hasta que todos los residuos presentes estén conectados.

T-Coffee (Tree-based consistency objective function for alignment evaluation) versión 3.27

t-Coffee emplea una estrategia progresiva en la alineación de secuencias. El programa primero crea una biblioteca a partir de dos fuentes diferentes: alineaciones globales de Clustal W y alineaciones locales de Lalign ., Para cada par de secuencias se crean alineaciones globales y alineaciones locales por pares a partir de los diez segmentos no intersectantes de mayor puntuación. El programa procesa la información global y local, asignando pesos a todas las alineaciones en pares en relación con la identidad de la secuencia . Esto es seguido por la combinación de grupos que se fusionan en una sola biblioteca. Hay una fase de extensión para esta biblioteca combinada, haciendo que el peso final de cualquier par de residuos refleje parte de la información contenida en toda la biblioteca., Un paso final requiere un cálculo de una matriz de distancia y un árbol de unión vecino, ya que la alineación se genera con una estrategia progresiva mediante la alineación de las dos secuencias más cercanas en el árbol de acuerdo con el peso almacenado en la biblioteca extendida. El par inicial es entonces fijo y cualquier hueco existente no puede ser desplazado más tarde. La alineación progresiva continúa hasta que cada secuencia está alineada.

POA (Partial Order Alignment) versión 2.0

POA es otro paquete MSA que utiliza un algoritmo de alineación progresiva sin utilizar perfiles generalizados., Este programa introduce el uso de un formato de alineación de secuencia múltiple de orden parcial (PO-MSA) para representar secuencias, y refleja con mayor precisión el contenido biológico. Este formato almacena la alineación como un gráfico compactado para recuentos mínimos de nodos y bordes, que aún contiene toda la información disponible en un MSA tradicional. Las secuencias se almacenan como una serie lineal de nodos conectados por dos aristas. POA utiliza un algoritmo de programación dinámica tradicional, donde las secuencias lineales son reemplazadas por gráficos de orden parcial (PO)., Estas estructuras PO se transforman en matrices 2D habituales y cada combinación de células se puntúan hacia atrás como en un procedimiento tradicional de alineación de secuencias Smith-Waterman . Estas matrices se extienden en cualquier dirección (diagonal, horizontal, vertical) permitiendo la producción de la alineación en pares en los puntos de unión. El MSA se obtiene de la alineación de dos secuencias al principio con la adición de otras secuencias sucesivamente al par inicial.

músculo (comparación de secuencia múltiple por log-expectativa) versión 3.,6

El músculo utiliza un enfoque de alineación de perfil en pares. El programa primero construye una alineación progresiva que luego se mejora y refina en dos etapas posteriores. La alineación progresiva se crea después de las similitudes de secuencia, se calcula una estimación de distancia y un árbol UPGMA. Muscle utiliza dos medidas de distancia: una distancia K mer para pares de secuencias no alineados y una distancia Kimura para pares alineados . La etapa de mejora de alineación progresiva crea un nuevo árbol con la matriz de distancia Kimura ya calculada y luego construye una mejor alineación basada en este árbol mejorado., La última etapa de refinamiento emplea una variante del particionamiento restringido dependiente del árbol . Este método elimina uno de los bordes del árbol, bi-particionando La alineación y extrayendo los perfiles de ambas particiones que luego se realinean con una alineación perfil-perfil. Cada borde del árbol se visita iterativamente y se mantiene la alineación con una puntuación de pares sumados actualizada de cada par de secuencias. Los bordes se visitan en orden de distancia decreciente desde la raíz, con un realineamiento de secuencias individuales, moviéndose a grupos de secuencias más estrechamente relacionados .,

Mafft (Multiple sequence alignment based on Fast Fourier Transform) versión 5.732

Mafft es un programa que se puede utilizar con diferentes enfoques de alineación, ya sea solo alineación progresiva (con transformada rápida de Fourier), o progresiva seguida de refinamiento iterativo. La ejecución básica de Mafft puede tener hasta tres pasos, pero el procedimiento predeterminado realiza los dos pasos iniciales. Primero, se crea una alineación progresiva basada en una distancia aproximada entre cada par de secuencias basada en 6 tuplas compartidas., UPGMA también genera un árbol guía con enlace modificado y las secuencias se alinean siguiendo el orden de ramas del árbol (este paso solo se llama estrategia FFT-NS-1). El segundo paso recalcula una matriz de distancias, basada en la información recopilada en el paso anterior, y la alineación progresiva se vuelve a hacer utilizando un árbol obtenido de la nueva matriz como punto de partida (hasta este paso, la estrategia se conoce como FFT-NS-2 y es la utilizada por defecto por el software)., La última fase es el refinamiento iterativo que optimiza la puntuación de la suma ponderada de pares (WSP) de Gotoh, con una alineación de grupo A grupo y la técnica de partición de restricción dependiente del árbol . Si se emplean los tres pasos, el procedimiento se llama FFT-NS-i, lo que significa que utiliza un método FFT para identificar rápidamente regiones homólogas presentes en las secuencias que es seguido por una fase iterativa de refinamiento., FFT convierte cada aminoácido presente en una secuencia en un vector que representa el volumen y la polaridad, que son factores importantes en los eventos de sustitución, lo que permite al software predecir tales ocurrencias con precisión.

Mafft también incluye tres algoritmos de refinamiento adicionales: L-INS-i, G-INS-I y E-INS-i . Estas estrategias aumentan el número de pasos necesarios para crear una alineación de MSA a cinco. En estos casos, el primer paso también requiere la construcción de una matriz de distancia, no utilizando 6 tuplas., A diferencia de los enfoques FFT-NS -*, no hay reconstrucción del árbol UPGMA calculado y el programa se mueve al segundo paso, dividiendo los segmentos libres de huecos y almacenando matrices de puntuación para cada segmento libre de huecos de una secuencia a otra. A continuación, Mafft calcula un valor de «importancia» a partir de la puntuación del segmento y almacena la frecuencia con la que aparecen los residuos en otros segmentos., Todos los valores de » importancia «se reúnen en una matriz de» importancia » en el paso tres, que es seguida rápidamente por una alineación grupo A grupo obtenida de las matrices de puntuación y un esquema de ponderación basado en un algoritmo Needleman-Wunsch. Un paso final refina iterativamente las alineaciones obtenidas, optimizando una puntuación WSP y los valores de» importancia » calculados previamente.

ProbCons (Probabilistic Consistency-based multiple sequence alignment) version 1.1

ProbCons es el único programa que utiliza un método de consistencia probabilística de alineación., Es una modificación del sistema tradicional de puntuación de suma de pares, y además incorpora un algoritmo de alineación progresiva basado en el modelo Markov oculto por pares. El procedimiento de alineación se divide en cuatro pasos, comenzando con un cálculo de matrices de probabilidad posterior para cada par de secuencias. Esto es seguido por un cálculo de programación dinámica de la precisión esperada de cada alineación en pares. La transformación de consistencia probabilística se emplea entonces para volver a estimar los puntajes de precisión de coincidencia., Un árbol guía se calcula con agrupamiento jerárquico con la similitud definida por un promedio ponderado de valores entre secuencias de cada clúster. El árbol guía se utiliza para alinear las secuencias utilizando un enfoque progresivo. También se realiza una fase de postprocesamiento, donde se realinean BI-particiones aleatorias de la alineación generada para verificar mejores regiones de alineación. ProbCons se diferencia de otros programas de alineación ya que no incorpora conceptos biológicos como la puntuación de huecos específicos de posición, la construcción de árboles evolutivos y otras características comúnmente utilizadas por otros paquetes.,

Dialign-T versión 0.2.1

Este programa es una re-implementación del procedimiento desarrollado en Dialign2.2, pero con una mejor solución para lidiar con fragmentos inconsistentes, incluyendo el encadenamiento de fragmentos. También implementa un nuevo enfoque para estimar las probabilidades de la ocurrencia aleatoria de cada fragmento presente en la secuencia a alinear. Dialign-T no utiliza tablas pre-calculadas para obtener puntuaciones de peso: calcula tablas de probabilidad a partir de varias matrices de sustitución. Además, el algoritmo de alineación múltiple codicioso de Dialign2.,2 fue cambiado para evitar similitudes locales espurias.

Kalign Versión 1.04

Kalign es otro programa que utiliza un enfoque de alineación progresiva para obtener el mejor MSA posible. La principal diferencia de este algoritmo con otros métodos es que emplea el algoritmo de coincidencia aproximada de cadenas de Wu-Manber al calcular la distancia entre secuencias. El algoritmo Wu-Manber mide la distancia entre dos cadenas usando una distancia de edición de Levenshtein, que permite una búsqueda eficiente de desajustes (compartidos o no) y patrones presentes en las secuencias., Según los desarrolladores de Kalign, esta metodología permite una estimación de distancia que es tan rápida como un algoritmo de K-tupla, pero es más precisa . El primer paso en el procedimiento de alineación es calcular las distancias en pares utilizando el enfoque Wu-Manber. La estimación de distancia en pares es seguida por una construcción de un árbol guía mediante el uso de UPGMA, que se emplea en un método de programación dinámica global para alinear las secuencias / perfiles., Además, el programa realiza una comprobación de consistencia para definir el conjunto más grande de coincidencias de secuencia que se pueden insertar en la alineación, utilizando una versión modificada del Needleman-Wunsch para encontrar la ruta más consistente a través de la matriz de programación dinámica. Además, Kalign actualiza las posiciones de las coincidencias de patrones, lo que ajusta la posición absoluta de las coincidencias encontradas dentro de las secuencias a sus posiciones relativas dentro de los perfiles generados .