Alineación de secuencias múltiples

Las primeras 90 posiciones de una proteína alineación de secuencias múltiples de instancias del ácido proteína ribosomal P0 (L10E) de varios organismos. Generado con ClustalW.

Una alineación de secuencias múltiples (MSA) es una alineación de secuencias de tres o más secuencias biológicas, generalmente proteínas , ADN , o RNA. En general, se supone que el conjunto de entrada de secuencias de consulta para tener una evolutiva relación por la que comparten un linaje y descienden de un ancestro común. Desde el resultante MSA, la secuencia homología se puede inferir y análisis filogenético puede llevarse a cabo para evaluar los orígenes evolutivos compartidos las secuencias. Representaciones visuales de la alineación como en la imagen a la derecha ilustrar eventos de mutación, como mutaciones puntuales (solo aminoácido o cambios de nucleótidos) que aparecen como diferentes personajes en una sola columna de la alineación y mutaciones inserción o supresión (o indeles) que aparecen como huecos en una o más de las secuencias en la alineación. Alineación de secuencias múltiples a menudo se utiliza para evaluar la secuencia conservación de dominios de la proteína, terciaria y estructuras secundarias, y ácidos o nucleótidos amino incluso individuales.

Alineación de secuencias múltiples también se refiere al proceso de alineación de un conjunto de tales secuencias. Debido a que tres o más secuencias de longitud biológicamente relevante puede ser difícil y casi siempre son mucho tiempo para alinear a mano, computacionales algoritmos se utilizan para producir y analizar los alineamientos. MSA requieren metodologías más sofisticadas que pairwise alineación porque son más computacionalmente complejo para producir. La mayoría de los programas de alineamiento de secuencias múltiples utilizan métodos heurísticos en lugar de optimización global porque la identificación de la mejor alineación entre más de unas pocas secuencias de longitud moderada es prohibitivamente costoso computacionalmente.

La programación dinámica y la complejidad computacional

El método más directo para producir un MSA utiliza el técnica de programación dinámica para identificar la solución alineación óptima a nivel mundial. Para las proteínas, este método implica generalmente dos conjuntos de parámetros: una penalización de espacio y un matriz de sustitución de la asignación de puntajes o probabilidades a la alineación de cada posible par de aminoácidos basados en la similitud de las propiedades químicas de los aminoácidos "y la probabilidad de la evolución de la mutación. Para secuencias de nucleótidos de una matriz de sustitución se puede utilizar, pero como sólo hay cuatro posibles caracteres estándar por secuencia y los nucleótidos individuales no suelen difieren mucho en la probabilidad de sustitución, los parámetros de ADN y ARN secuencias generalmente consisten en una penalización por hueco, un positivo puntuación de caracteres detecta, y una puntuación negativa para desajustes.

Para n secuencias individuales, el método requiere la construcción de la n-dimensional equivalente de la matriz formada en la programación dinámica pairwise estándar. Así pues, el espacio de búsqueda aumenta exponencialmente con el aumento de n, y también es fuertemente dependiente de la secuencia de longitud. Para encontrar el óptimo global para n secuencias de esta manera se ha demostrado ser una Problema NP-completo. Los métodos para reducir el espacio de búsqueda mediante la realización de primera programación dinámica por parejas en cada par de secuencias en el conjunto de consulta y buscar sólo el espacio de la solución cerca de estos resultados (efectivamente encontrar la intersección entre las trayectorias locales que rodea inmediatamente a cada solución óptima pairwise) hacer que la técnica de programación dinámica más eficiente. El llamado "suma de pares" método ha sido implementado en el paquete de software MSA, pero todavía es poco práctico para muchas aplicaciones de MSA que requieren la alineación simultánea de decenas o incluso unos pocos cientos de secuencias. Métodos de programación dinámica ahora sólo se utilizan cuando se necesita un alineamiento de muy alta calidad de un pequeño número de secuencias, y como evaluación comparativa estándar en la evaluación de nuevos o refinados técnicas heurísticas.

Construcción alineación progresiva

Un método para realizar una búsqueda heurística de alineación es la técnica progresiva (también conocido como el método jerárquico o árbol) que se acumula una MSA final por primera realización de una serie de alineamientos por pares en las secuencias sucesivamente menos estrechamente relacionadas. Tales métodos comienzan alineando las dos secuencias más estrechamente relacionados primero y luego alinear sucesivamente la siguiente secuencia más estrechamente relacionados en la consulta se establece en la alineación producido en el paso anterior. La pareja inicial "más relacionadas" se determina mediante un eficiente método de agrupación tales como vecino a participar sobre la base de una simple búsqueda heurística de la consulta establecido con una herramienta como FASTA. Por lo tanto, las técnicas progresivos construyen automáticamente un árbol filogenético, así como una alineación.

Una de las principales limitaciones de los métodos progresivos es su gran dependencia de la asignación inicial de la relación y en la calidad de la alineación inicial. Los métodos son por lo tanto sensibles, y también a la distribución de secuencias en el conjunto de consulta; rendimiento mejora cuando la relación entre secuencias de consulta es un gradiente relativamente suave en lugar de racimos separado a distancia. El desempeño también se degrada significativamente cuando todas las secuencias en el conjunto son bastante alejadas, debido a imprecisiones en la alineación inicial son entonces más probable. La mayoría de los métodos progresistas modernas modifican su función de puntuación con una función de ponderación secundaria que asigna factores de escala a los miembros individuales de la consulta establecido de manera no lineal en función de su distancia filogenética de sus vecinos más cercanos. La elección juiciosa de ponderación puede ayudar en la evaluación de la relación y mitigar los efectos de la relativamente pobres alineaciones iniciales temprano en la progresión.

Métodos de alineación progresivos son lo suficientemente eficaz para aplicar a gran escala para muchas secuencias y son a menudo se ejecutan en servidores web accesibles públicamente para que los usuarios no necesitan instalar localmente las aplicaciones de interés. Un método de alineación progresiva muy popular es el Clustal familia, especialmente la variante ponderada ClustalW cuyo acceso es proporcionado por un gran número de portales web que incluye GenomeNet, EBI, y EMBNet. Diferentes portales o implementaciones pueden variar en interfaz de usuario y hacer diferentes parámetros accesible para el usuario. Clustal se utiliza ampliamente para la construcción del árbol filogenético y como insumo para proteína de predicción de estructura por modelado por homología.

Otro método de alineación progresiva común llamada T-Café es más lento que Clustal y sus derivados, pero generalmente produce alineaciones precisa de conjuntos de secuencias alejadas. T-Café calcula alineamientos por pares mediante la combinación de la alineación directa del par con alineaciones indirectos que se alinea cada secuencia de la pareja a una tercera secuencia. Se utiliza la salida de Clustal así como otro programa de alineamiento local LALIGN, que encuentra múltiples regiones de la alineación local entre dos secuencias. La alineación resultante y el árbol filogenético se utilizan como una guía para producir factores de ponderación nuevas y más precisas.

Dado que los métodos progresivos son heurísticas que no están garantizados para converger a un óptimo global, la calidad de alineación puede ser difícil de evaluar y su verdadero significado biológico puede ser oscuro. Un método semi-progresivo muy reciente que mejora la calidad de la alineación y no utiliza una heurística con pérdidas, mientras que todavía está en activo tiempo polinomial se ha implementado en el programa PSAlign.

Los métodos iterativos

Un conjunto de métodos para producir MSA al tiempo que reduce los errores inherentes a los métodos progresistas se clasifican como "iterativo" porque funcionan de manera similar a los métodos progresivos pero realinear repetidamente las secuencias iniciales, así como la adición de nuevas secuencias a la creciente MSA. Una de las razones métodos progresivos son tan fuertemente dependiente de una alineación inicial de alta calidad es el hecho de que estas alineaciones siempre se incorporan en el resultado final - es decir, una vez que una secuencia ha sido alineado en el MSA, su alineación no se considera aún más. Esta aproximación mejora la eficiencia en el costo de precisión. Por el contrario, los métodos iterativos pueden volver a alineamientos de pares previamente calculadas o sub-MSA incorporan subconjuntos de la secuencia de consulta como un medio de la optimización de un general función objetivo como la búsqueda de una puntuación de alineamiento de alta calidad.

Una variedad de sutilmente diferentes métodos de iteración se han implementado y puesto a disposición en paquetes de software; comentarios y comparaciones han sido útiles, pero en general abstenerse de elegir un "mejor" técnica. El paquete de software Utiliza PRRN / PRRP un algoritmo de escalada para optimizar su puntuación de alineamiento MSA y corrige de forma iterativa ambos pesos alineación y o regiones "Cappy" localmente divergentes de la creciente MSA. PRRP funciona mejor cuando se refina un alineamiento previamente construido por un método más rápido.

Otro programa iterativo, DIALIGN, toma un enfoque inusual de centrarse estrictamente en las alineaciones locales entre los sub-segmentos o motivos de secuencia sin introducir una penalización por hueco. La alineación de motivos individuales se consigue entonces con una representación de la matriz similar a una parcela de matriz de puntos en un alineamiento por pares. Un método alternativo que utiliza alineamientos locales rápidas como puntos de anclaje o "semillas" para un procedimiento de alineamiento global más lento se implementa en el Suite CAOS / DIALIGN.

Un tercer método basado en la iteración popular llamado MÚSCULO (alineación de secuencias múltiples por log-expectativa) mejora en los métodos progresivos con una medida de la distancia más precisa para evaluar la relación de las dos secuencias. La medida de la distancia se actualiza entre las etapas de iteración (aunque, en su forma original, MÚSCULO contenía sólo 2-3 iteraciones en función de si el refinamiento se ha habilitado).

Los modelos ocultos de Markov

Los modelos ocultos de Markov son modelos probabilísticos que pueden asignar probabilidades a todas las combinaciones posibles de las lagunas de los partidos, y los desajustes para determinar la más probable MSA o conjunto de posibles acuerdos de servicios administrativos. HMM pueden producir una sola salida más alta puntuación, pero también pueden generar una familia de posibles alineaciones que luego pueden ser evaluados por su importancia biológica. Debido HMMs son probabilística, no producen la misma solución cada vez que se ejecutan en el mismo conjunto de datos; por lo que no se puede garantizar a converger a una alineación óptima. HMM pueden producir alineamientos globales y locales. Aunque los métodos basados en HMM se han desarrollado relativamente recientemente, que ofrecen mejoras significativas en la velocidad de cálculo, especialmente para secuencias que contienen regiones que se superponen.

Típico Hmm basada en métodos de trabajo por lo que representa un MSA como una forma de grafo dirigido acíclico conocido como un gráfico de orden parcial, que consiste en una serie de nodos que representan posibles entradas en las columnas de una MSA. En esta representación una columna que se absolutamente conservadas (es decir, que todas las secuencias en el MSA comparten un carácter particular en una posición particular) se codifica como un único nodo con el mayor número de conexiones de salida, ya que hay posibles caracteres en la siguiente columna de la alineación. En los términos de un modelo típico ocultos de Markov, los estados observados son las columnas de alineación individuales y los estados "ocultos" representan la secuencia ancestral de la que se presume son la hipótesis de las secuencias en el conjunto de consultas que han descendido. Una variante de búsqueda eficiente del método de programación dinámica, conocido como el Algoritmo de Viterbi, se utiliza generalmente para alinear sucesivamente la creciente MSA a la siguiente secuencia en la consulta establecido para producir un nuevo MSA. Esto es distinto de los métodos de alineación progresivos porque la alineación de las secuencias anteriores se actualiza con cada nueva adición secuencia. Sin embargo, como métodos progresivos, esta técnica puede ser influenciado por el orden en que las secuencias en el conjunto de consultas se integran en la alineación, especialmente cuando las secuencias están lejanamente relacionados.

Varios programas de software están disponibles en los que las variantes de los métodos basados en HMM se han aplicado y que se destaca por su escalabilidad y eficiencia, aunque adecuadamente usando un método HMM es más complejo que el uso de métodos progresivos más comunes. El más simple es POA (Parcial-Order Alignment); un método similar pero más generalizado se implementa en el paquete SAM (Secuencia de alineación y Modeling System). SAM se ha utilizado como una fuente de alineaciones para estructura de la proteína de predicción para participar en el CASP predicción de estructura experimento y desarrollar una base de datos de proteínas previsto en las levaduras especies S. cerevisiae. HMM métodos también se pueden utilizar para la búsqueda de base de datos con HMMER.

Algoritmos genéticos y recocido simulado

Las técnicas estándar de optimización en la informática - ambos de los cuales fueron inspirados por, pero no se reproducen directamente, procesos físicos - también se han utilizado en un intento de producir de manera más eficiente las MSA de calidad. Una de tales técnicas, los algoritmos genéticos, se ha utilizado para la producción de MSA en un intento de simular ampliamente el proceso evolutivo la hipótesis de que dio lugar a la divergencia en el conjunto de consulta. El método funciona mediante la ruptura de una serie de posibles MSA en fragmentos y reordenando esos fragmentos con la introducción de huecos en diferentes posiciones repetidamente. Un general función objetivo está optimizado durante la simulación, más en general, la función de la maximización de "suma de pares" introdujo en métodos dinámicos MSA basado en programación. Una técnica para las secuencias de proteínas se ha implementado en la SAGA programa de software (Secuencia de alineación por Algoritmo Genético) y su equivalente en el ARN se llama RAGA.

La técnica de recocido simulado, por el cual un MSA existente producida por otro método se refina por una serie de reordenamientos diseñados para encontrar regiones más óptimo del espacio de alineación que el de la alineación de entrada ya ocupa. Al igual que el método de algoritmo genético, recocido simulado maximiza una función objetivo como la función de suma de pares. El recocido simulado utiliza un "factor de temperatura" metafórica que determina la velocidad a la que reordenamientos proceder y la probabilidad de cada reordenación; típicos suplentes uso períodos de altas tasas de reordenación con relativamente baja probabilidad (para explorar las regiones más distantes del espacio de alineación) con períodos de tarifas más bajas y más altas probabilidades de explorar más a fondo los mínimos locales cerca de las regiones recientemente "colonizadas". Este enfoque se ha aplicado en el programa Msasa (alineación de secuencias múltiples por recocido simulado).

La búsqueda de motivos

La alineación de los siete Drosophila caspasas coloreadas por motivos señalados por MEME. Cuando motivo posiciones y alineaciones de secuencia se generan de forma independiente, a menudo se correlacionan bien pero no perfectamente, como en este ejemplo.

Hallazgo Motif, también conocida como análisis del perfil, es un método de localización secuencia de motivos en MSA globales que es a la vez un medio de producir una mejor MSA y un medio de producir una matriz de puntuación para su uso en la búsqueda de otras secuencias de motivos similares. Una variedad de métodos para aislar los motivos se han desarrollado, pero todos se basan en la identificación de patrones de corto altamente conservadas dentro de la alineación más grande y la construcción de una matriz similar a una matriz de sustitución que refleja la composición de aminoácidos o de nucleótidos de cada posición en el motivo putativo . La alineación puede ser refinado uso de estas matrices. En el análisis de perfil estándar, la matriz incluye entradas para cada personaje sea posible, así como entradas para las lagunas. Alternativamente, los algoritmos de búsqueda de patrones estadísticos pueden identificar motivos como un precursor a un MSA en lugar de como una derivación. En muchos casos, cuando el conjunto de consulta contiene sólo un pequeño número de secuencias o contiene sólo secuencias altamente relacionadas, se añaden pseudocounts para normalizar la distribución refleja en la matriz de puntuación. En particular, esto corrige las entradas de cero en la matriz de probabilidad a valores que son pequeño pero distinto de cero.

Análisis Blocks es un método de búsqueda de motivos motivos que restringe a las regiones sin huecos en la alineación. Los bloques pueden ser generados a partir de un MSA o pueden ser extraídos a partir de secuencias no alineadas utilizando un conjunto precalculada de motivos comunes previamente generados a partir de familias de genes conocidos. Bloque de puntuación general se basa en la separación de caracteres de alta frecuencia en lugar de en el cálculo de una matriz de sustitución explícito. La BLOQUES servidor proporciona un método interactivo para localizar tales motivos en secuencias sin alinear.

Estadística de coincidencia de patrones se ha implementado utilizando tanto el expectativa de maximización algoritmo y la Muestreador de Gibbs. Una de las herramientas motivo de la búsqueda más comunes, conocidas como MEME, utiliza expectativa de maximización y métodos ocultos de Markov para generar motivos que luego se utilizan como herramientas de búsqueda por su mástil compañero en la suite combinada MEME / MAST.