Articulo de referencia

Alineamiento de secuencias múltiples

Las primeras 90 posiciones de una alineación de secuencias múltiples de proteínas de instancias de la proteína ribosómica ácida P0 (L10E) de varios organismos. Generado con Clus...

Las primeras 90 posiciones de una alineación de secuencias múltiples de proteínas de instancias de la proteína ribosómica ácida P0 (L10E) de varios organismos. Generado con Clustal X.

El alineamiento de secuencias múltiples ( MSA ) es el proceso o el resultado del alineamiento de tres o más secuencias biológicas , generalmente de proteínas , ADN o ARN . Estos alineamientos se utilizan para inferir relaciones evolutivas mediante análisis filogenético y pueden resaltar características homólogas entre secuencias. Los alineamientos resaltan eventos de mutación como mutaciones puntuales ( cambios de un solo aminoácido o nucleótido ), mutaciones por inserción y mutaciones por deleción , y se utilizan para evaluar la conservación de secuencias e inferir la presencia y actividad de dominios proteicos , estructuras terciarias , estructuras secundarias y aminoácidos o nucleótidos individuales.

Los alineamientos de secuencias múltiples requieren metodologías más sofisticadas que los alineamientos por pares , ya que son computacionalmente más complejos . La mayoría de los programas de alineamiento de secuencias múltiples utilizan métodos heurísticos en lugar de optimización global, dado que identificar el alineamiento óptimo entre más de unas pocas secuencias de longitud moderada resulta prohibitivamente costoso desde el punto de vista computacional. Sin embargo, los métodos heurísticos generalmente no garantizan soluciones de alta calidad y se ha demostrado que no logran producir soluciones casi óptimas en casos de prueba de referencia. [ 1 ] [ 2 ] [ 3 ]

Planteamiento del problema

Dadometro{\displaystyle m}secuenciasSi{\displaystyle S_{i}},i=1,,metro{\displaystyle i=1,\cdots ,m}similar al formulario que aparece a continuación:

S:={S1=(S11,S12,,S1norte1)S2=(S21,S22,,S2norte2)Smetro=(Smetro1,Smetro2,,Smetronortemetro){\displaystyle S:={\begin{cases}S_{1}=(S_{11},S_{12},\ldots ,S_{1n_{1}})\\S_{2}=(S_{21},S_{22},\cdots ,S_{2n_{2}})\\\,\,\,\,\,\,\,\,\,\,\vdots \\S_{m}=(S_{m1},S_{m2},\ldots ,S_{mn_{m}})\end{cases}}}

Se realiza un alineamiento de secuencias múltiples de este conjunto de secuencias.S{\displaystyle S}insertando la cantidad de huecos necesarios en cada uno de losSi{\displaystyle S_{i}}secuencias deS{\displaystyle S}hasta las secuencias modificadas,Si{\displaystyle S'_{i}}, todos se ajustan a la longitudLmáximo{norteii=1,,metro}{\displaystyle L\geq \max\{n_{i}\mid i=1,\ldots ,m\}}y ningún valor en las secuencias deS{\displaystyle S}La misma columna consta únicamente de huecos. La forma matemática de un MSA del conjunto de secuencias anterior se muestra a continuación:

S:={S1=(S11,S12,,S1L)S2=(S21,S22,,S2L)Smetro=(Smetro1,Smetro2,,SmetroL){\displaystyle S':={\begin{cases}S'_{1}=(S'_{11},S'_{12},\ldots ,S'_{1L})\\S'_{2}=(S'_{21},S'_{22},\ldots ,S'_{2L})\\\,\,\,\,\,\,\,\,\,\,\vdots \\S'_{m}=(S'_{m1},S'_{m2},\ldots ,S'_{mL})\end{cases}}}

Para regresar de cada secuencia en particularSi{\displaystyle S'_{i}}aSi{\displaystyle S_{i}}, elimina todos los huecos.

Enfoque gráfico

Un método habitual para calcular alineamientos de secuencias múltiples consiste en utilizar grafos para identificar todos los alineamientos posibles. Al encontrar alineamientos mediante grafos, se crea un alineamiento completo en un grafo ponderado que contiene un conjunto de vértices y un conjunto de aristas. Cada arista del grafo tiene un peso basado en una heurística que ayuda a puntuar cada alineamiento o subconjunto del grafo original.

Alineaciones de seguimiento

Para determinar las alineaciones más adecuadas para cada MSA, generalmente se genera una traza . Una traza es un conjunto de vértices realizados , es decir, correspondientes y alineados, que tiene un peso específico basado en las aristas seleccionadas entre dichos vértices. Al elegir trazas para un conjunto de secuencias, es necesario seleccionar la traza con el peso máximo para obtener la mejor alineación de las secuencias.

Métodos de alineación

Existen diversos métodos de alineación que se utilizan en secuencias múltiples para maximizar la precisión y la exactitud de las alineaciones. Cada uno suele basarse en una heurística específica que considera el proceso evolutivo. La mayoría intenta replicar la evolución para obtener la alineación más realista posible y predecir con mayor precisión las relaciones entre secuencias.

Programación dinámica

Un método directo para generar un MSA utiliza la técnica de programación dinámica para identificar la solución de alineación óptima global. Para las proteínas, este método suele implicar dos conjuntos de parámetros: una penalización por hueco y una matriz de sustitución que asigna puntuaciones o probabilidades a la alineación de cada par posible de aminoácidos en función de la similitud de las propiedades químicas de los aminoácidos y la probabilidad evolutiva de la mutación. Para las secuencias de nucleótidos, se utiliza una penalización por hueco similar, pero es habitual una matriz de sustitución mucho más simple, en la que solo se consideran coincidencias y discrepancias idénticas. Las puntuaciones en la matriz de sustitución pueden ser todas positivas o una combinación de positivas y negativas en el caso de una alineación global, pero deben ser tanto positivas como negativas en el caso de una alineación local. [ 4 ]

Para n secuencias individuales, el método ingenuo requiere construir el equivalente n -dimensional de la matriz formada en el alineamiento de secuencias por pares estándar . El espacio de búsqueda, por lo tanto, aumenta exponencialmente con el aumento de n y también depende fuertemente de la longitud de la secuencia. Expresado con la notación O grande comúnmente utilizada para medir la complejidad computacional , un MSA ingenuo toma O(Length Nseqs ) tiempo para producir. Encontrar el óptimo global para n secuencias de esta manera ha demostrado ser un problema NP-completo . [ 5 ] [ 6 ] [ 7 ] En 1989, basándose en el algoritmo de Carrillo-Lipman, [ 8 ] Altschul introdujo un método práctico que utiliza alineamientos por pares para restringir el espacio de búsqueda n-dimensional. [ 9 ] En este enfoque, se realizan alineamientos de programación dinámica por pares en cada par de secuencias en el conjunto de consulta, y solo se busca el alineamiento de n vías en el espacio cercano a la intersección n-dimensional de estos alineamientos. El programa MSA optimiza la suma de todos los pares de caracteres en cada posición del alineamiento (la llamada suma de puntuaciones de pares) y se ha implementado en un programa de software para la construcción de alineamientos de secuencias múltiples. [ 10 ] En 2019, Hosseininasab y van Hoeve demostraron que, mediante el uso de diagramas de decisión, MSA puede modelarse con una complejidad espacial polinomial. [ 3 ]

Construcción de alineación progresiva

El método más utilizado para alineamientos de secuencias múltiples emplea una búsqueda heurística conocida como técnica progresiva (también llamada método jerárquico o de árbol), desarrollada por Da-Fei Feng y Doolittle en 1987. [ 11 ] El alineamiento progresivo construye un MSA final combinando alineamientos por pares, comenzando con el par más similar y avanzando hacia el más distante. Todos los métodos de alineamiento progresivo requieren dos etapas: una primera etapa en la que las relaciones entre las secuencias se representan como un árbol filogenético , denominado árbol guía , y una segunda etapa en la que el MSA se construye añadiendo secuencialmente las secuencias al MSA en crecimiento según el árbol guía. El árbol guía inicial se determina mediante un método de agrupamiento eficiente , como el de unión de vecinos o el método de agrupamiento de pares no ponderados con media aritmética ( UPGMA ), y puede utilizar distancias basadas en el número de subsecuencias idénticas de dos letras (como en FASTA en lugar de un alineamiento de programación dinámica). [ 12 ]

No se garantiza que los alineamientos progresivos sean globalmente óptimos. El principal problema es que, cuando se cometen errores en cualquier etapa del crecimiento del alineamiento múltiple de secuencias (AMS), estos se propagan hasta el resultado final. El rendimiento también es particularmente deficiente cuando todas las secuencias del conjunto están bastante distantemente relacionadas. La mayoría de los métodos progresivos modernos modifican su función de puntuación con una función de ponderación secundaria que asigna factores de escala a los miembros individuales del conjunto de consulta de forma no lineal, basándose en su distancia filogenética con respecto a sus vecinos más cercanos. Esto corrige la selección no aleatoria de las secuencias proporcionadas al programa de alineamiento. [ 12 ]

Los métodos de alineación progresiva son lo suficientemente eficientes como para implementarse a gran escala para muchas (cientos a miles) de secuencias. Un método popular de alineación progresiva ha sido la familia Clustal . [ 13 ] [ 14 ] Clustal W se utiliza ampliamente para la construcción de árboles filogenéticos, a pesar de las advertencias explícitas del autor de que las alineaciones sin editar no deben usarse en tales estudios y como entrada para la predicción de la estructura de proteínas mediante modelado por homología. El Instituto Europeo de Bioinformática (EMBL-EBI) anunció que CLustalW2 expirará en agosto de 2015. Recomiendan Clustal Omega, que funciona basándose en árboles guía con semillas y técnicas de perfil-perfil HMM para alineaciones de proteínas. Una herramienta alternativa para alineaciones progresivas de ADN es la alineación múltiple mediante la transformada rápida de Fourier ( MAFFT ). [ 15 ]

Otro método común de alineación progresiva, denominado T-Coffee [ 16 ] , es más lento que Clustal y sus derivados, pero generalmente produce alineaciones más precisas para conjuntos de secuencias distantemente relacionadas. T-Coffee calcula alineaciones por pares combinando la alineación directa del par con alineaciones indirectas que alinean cada secuencia del par con una tercera secuencia. Utiliza la salida de Clustal, así como otro programa de alineación local, LALIGN, que encuentra múltiples regiones de alineación local entre dos secuencias. La alineación y el árbol filogenético resultantes se utilizan como guía para generar factores de ponderación nuevos y más precisos.

Debido a que los métodos progresivos son heurísticas que no garantizan la convergencia a un óptimo global, la calidad de la alineación puede ser difícil de evaluar y su verdadero significado biológico puede resultar confuso. En el programa PSAlign se ha implementado un método semiprogresivo que mejora la calidad de la alineación y no utiliza una heurística con pérdida, con una ejecución en tiempo polinomial . [ 17 ]

Métodos iterativos

Un conjunto de métodos para producir alineamientos múltiples de secuencias (MSA) que reducen los errores inherentes a los métodos progresivos se clasifican como "iterativos" porque funcionan de manera similar a estos, pero realinean repetidamente las secuencias iniciales y añaden nuevas secuencias al MSA en crecimiento. Una razón por la que los métodos progresivos dependen tanto de un alineamiento inicial de alta calidad es que estos alineamientos siempre se incorporan al resultado final; es decir, una vez que una secuencia se ha alineado en el MSA, su alineamiento no se considera posteriormente. Esta aproximación mejora la eficiencia a costa de la precisión. Por el contrario, los métodos iterativos pueden volver a alineamientos por pares calculados previamente o a sub-MSA que incorporan subconjuntos de la secuencia de consulta como medio para optimizar una función objetivo general , como encontrar una puntuación de alineamiento de alta calidad. [ 12 ]

Se han implementado y puesto a disposición en paquetes de software diversos métodos de iteración sutilmente diferentes; las revisiones y comparaciones han sido útiles, pero generalmente se abstienen de elegir una técnica "mejor". [ 18 ] El paquete de software PRRN/PRRP utiliza un algoritmo de ascenso de colina para optimizar su puntuación de alineación MSA [ 19 ] y corrige iterativamente tanto los pesos de alineación como las regiones localmente divergentes o "con huecos" de la MSA en crecimiento. [ 12 ] PRRP funciona mejor cuando refina una alineación previamente construida por un método más rápido. [ 12 ]

Otro programa iterativo, DIALIGN, adopta un enfoque inusual al centrarse exclusivamente en alineamientos locales entre subsegmentos o motivos de secuencia sin introducir una penalización por huecos. [ 20 ] El alineamiento de motivos individuales se logra mediante una representación matricial similar a un diagrama de puntos en un alineamiento por pares. En el conjunto de programas CHAOS/DIALIGN se implementa un método alternativo que utiliza alineamientos locales rápidos como puntos de anclaje o semillas para un procedimiento de alineamiento global más lento. [ 20 ]

Un tercer método popular basado en iteraciones, denominado MUSCLE (alineamiento de secuencias múltiples mediante expectativa logarítmica), mejora los métodos progresivos con una medida de distancia más precisa para evaluar la relación entre dos secuencias. [ 21 ] La medida de distancia se actualiza entre las etapas de iteración (aunque, en su forma original, MUSCLE contenía solo 2-3 iteraciones dependiendo de si el refinamiento estaba habilitado).

Métodos de consenso

Los métodos de consenso intentan encontrar el alineamiento múltiple de secuencias óptimo a partir de múltiples alineamientos diferentes del mismo conjunto de secuencias. Existen dos métodos de consenso de uso común: M-COFFEE y MergeAlign. [ 22 ] M-COFFEE utiliza alineamientos múltiples de secuencias generados por siete métodos diferentes para generar alineamientos de consenso. MergeAlign es capaz de generar alineamientos de consenso a partir de cualquier número de alineamientos de entrada generados mediante diferentes modelos de evolución de secuencias o diferentes métodos de alineamiento múltiple de secuencias. La opción predeterminada de MergeAlign es inferir un alineamiento de consenso utilizando alineamientos generados mediante 91 modelos diferentes de evolución de secuencias de proteínas .

modelos ocultos de Markov

Un modelo oculto de Markov (HMM) de perfil que modela una alineación de secuencias múltiples

Un modelo oculto de Markov (HMM) es un modelo probabilístico que puede asignar probabilidades a todas las combinaciones posibles de huecos, coincidencias y discrepancias, para determinar el alineamiento múltiple de secuencias (MSA) más probable o un conjunto de MSA posibles. Los HMM pueden producir una única salida con la puntuación más alta, pero también pueden generar una familia de alineamientos posibles que luego se pueden evaluar para determinar su relevancia biológica. Los HMM pueden producir alineamientos tanto globales como locales. Aunque los métodos basados ​​en HMM se han desarrollado relativamente hace poco, ofrecen mejoras significativas en la velocidad de cálculo, especialmente para secuencias que contienen regiones superpuestas. [ 12 ]

Los métodos típicos basados ​​en HMM funcionan representando un MSA como un grafo dirigido acíclico conocido como grafo de orden parcial, que consiste en una serie de nodos que representan posibles entradas en las columnas de un MSA. En esta representación, una columna que se conserva absolutamente (es decir, que todas las secuencias en el MSA comparten un carácter particular en una posición particular) se codifica como un solo nodo con tantas conexiones salientes como caracteres posibles haya en la siguiente columna del alineamiento. En términos de un modelo oculto de Markov típico, los estados observados son las columnas individuales del alineamiento y los estados "ocultos" representan la supuesta secuencia ancestral de la que se hipotetiza que descienden las secuencias en el conjunto de consulta. Una variante de búsqueda eficiente del método de programación dinámica, denominada algoritmo de Viterbi , se utiliza generalmente para alinear sucesivamente el MSA en crecimiento con la siguiente secuencia en el conjunto de consulta para producir un nuevo MSA. [ 23 ] Esto es distinto de los métodos de alineamiento progresivo porque el alineamiento de secuencias anteriores se actualiza con cada nueva adición de secuencia. Sin embargo, al igual que los métodos progresivos, esta técnica puede verse influenciada por el orden en que las secuencias del conjunto de consulta se integran en la alineación, especialmente cuando las secuencias están distantemente relacionadas. [ 12 ]

Hay varios programas de software disponibles en los que se han implementado variantes de métodos basados ​​en HMM y que se destacan por su escalabilidad y eficiencia, aunque el uso adecuado de un método HMM es más complejo que el uso de métodos progresivos más comunes. El más simple es Alineamiento de Orden Parcial (POA), [ 24 ] y un método similar más general está implementado en el paquete de software Sequence Alignment and Modeling System (SAM). [ 25 ] y HMMER . [ 26 ] SAM se ha utilizado como fuente de alineamientos para la predicción de la estructura de proteínas para participar en el experimento de predicción de estructura Critical Assessment of Structure Prediction ( CASP ) y para desarrollar una base de datos de proteínas predichas en la especie de levadura S. cerevisiae . HHsearch [ 27 ] es un paquete de software para la detección de secuencias de proteínas remotamente relacionadas basadas en la comparación por pares de HMM. Un servidor que ejecuta HHsearch ( HHpred ) fue el más rápido de 10 servidores automáticos de predicción de estructura en las competiciones de predicción de estructura CASP7 y CASP8. [ 28 ]

Métodos que tienen en cuenta la filogenia

Alineación de exones no homólogos mediante un método iterativo (a) y mediante un método que tiene en cuenta la filogenia (b).

La mayoría de los métodos de alineación de secuencias múltiples intentan minimizar el número de inserciones/deleciones (huecos) y, como consecuencia, producen alineaciones compactas. Esto causa varios problemas si las secuencias a alinear contienen regiones no homólogas , si los huecos son informativos en un análisis filogenético . Estos problemas son comunes en secuencias recién producidas que están mal anotadas y pueden contener cambios de marco , dominios incorrectos o exones empalmados no homólogos . El primer método de este tipo fue desarrollado en 2005 por Löytynoja y Goldman. [ 29 ] Los mismos autores lanzaron un paquete de software llamado PRANK en 2008. [ 30 ] PRANK mejora las alineaciones cuando hay inserciones presentes. Sin embargo, se ejecuta lentamente en comparación con los métodos progresivos y/o iterativos que se han desarrollado durante varios años.

En 2012, aparecieron dos nuevas herramientas basadas en filogenia. Una se llama PAGAN y fue desarrollada por el mismo equipo que PRANK. [ 31 ] La otra es ProGraphMSA, desarrollada por Szalkowski. [ 32 ] Ambos paquetes de software se desarrollaron de forma independiente, pero comparten características comunes, en particular el uso de algoritmos de grafos para mejorar el reconocimiento de regiones no homólogas y una mejora en el código que hace que estos programas sean más rápidos que PRANK.

Búsqueda de motivos

Alineación de las siete caspasas de Drosophila coloreadas según los motivos identificados por MEME. Cuando las posiciones de los motivos y las alineaciones de secuencias se generan de forma independiente, suelen correlacionarse bien, pero no a la perfección, como en este ejemplo.

La búsqueda de motivos, también conocida como análisis de perfiles, es un método para localizar motivos de secuencia en alineamientos múltiples de secuencias (MSA) globales. Este método permite tanto mejorar el MSA como generar una matriz de puntuación para la búsqueda de motivos similares en otras secuencias. Se han desarrollado diversos métodos para aislar los motivos, pero todos se basan en la identificación de patrones cortos y altamente conservados dentro del alineamiento general y en la construcción de una matriz similar a una matriz de sustitución que refleja la composición de aminoácidos o nucleótidos de cada posición en el supuesto motivo. El alineamiento se puede refinar utilizando estas matrices. En el análisis de perfiles estándar, la matriz incluye entradas para cada carácter posible, así como entradas para huecos. [ 12 ] Alternativamente, los algoritmos estadísticos de búsqueda de patrones pueden identificar motivos como precursores de un MSA, en lugar de como derivaciones. En muchos casos, cuando el conjunto de consulta contiene solo un pequeño número de secuencias o solo secuencias altamente relacionadas, se añaden pseudocuentas para normalizar la distribución reflejada en la matriz de puntuación. En particular, esto corrige las entradas de probabilidad cero en la matriz, asignándoles valores pequeños pero distintos de cero.

El análisis de bloques es un método de búsqueda de motivos que los restringe a regiones sin huecos en el alineamiento. Los bloques pueden generarse a partir de un alineamiento múltiple de secuencias (MSA) o extraerse de secuencias no alineadas utilizando un conjunto precalculado de motivos comunes generados previamente a partir de familias de genes conocidas. [ 33 ] La puntuación de bloques generalmente se basa en el espaciamiento de caracteres de alta frecuencia en lugar del cálculo de una matriz de sustitución explícita .

La coincidencia de patrones estadísticos se ha implementado utilizando tanto el algoritmo de maximización de la expectativa como el muestreador de Gibbs . Una de las herramientas más comunes para la búsqueda de motivos, denominada Multiple EM for Motif Elicitation (MEME), utiliza métodos de maximización de la expectativa y de Markov ocultos para generar motivos que luego son utilizados como herramientas de búsqueda por su complemento MAST en el conjunto combinado MEME/MAST. [ 34 ] [ 35 ]

Alineamiento de secuencias múltiples no codificantes

Las regiones de ADN no codificante , especialmente los sitios de unión de factores de transcripción (TFBS), están conservadas, pero no necesariamente relacionadas evolutivamente, y pueden haber convergido a partir de ancestros no comunes. Por lo tanto, las suposiciones utilizadas para alinear secuencias de proteínas y regiones codificantes de ADN son inherentemente diferentes de las que se aplican a las secuencias de TFBS. Si bien es útil alinear regiones codificantes de ADN para secuencias homólogas mediante operadores de mutación, la alineación de secuencias de sitios de unión para el mismo factor de transcripción no puede basarse en operaciones de mutación relacionadas evolutivamente. De manera similar, el operador evolutivo de mutaciones puntuales puede usarse para definir una distancia de edición para secuencias codificantes, pero esto tiene poco sentido para las secuencias de TFBS, ya que cualquier variación de secuencia debe mantener un cierto nivel de especificidad para que el sitio de unión funcione. Esto cobra especial importancia al intentar alinear secuencias de TFBS conocidas para construir modelos supervisados ​​que predigan ubicaciones desconocidas del mismo TFBS. Por lo tanto, los métodos de alineación de secuencias múltiples necesitan ajustar la hipótesis evolutiva subyacente y los operadores utilizados como en el trabajo publicado que incorpora información termodinámica de bases vecinas [ 36 ] para alinear los sitios de unión buscando la alineación termodinámica más baja que conserve la especificidad del sitio de unión.

Mejoramiento

Algoritmos genéticos y recocido simulado

Las técnicas de optimización estándar en informática —ambas inspiradas en procesos físicos, pero que no los reproducen directamente— también se han utilizado para intentar producir alineamientos múltiples de secuencias (AMS) de mayor calidad de forma más eficiente. Una de estas técnicas, los algoritmos genéticos , se ha utilizado para la producción de AMS con el fin de simular de forma general el proceso evolutivo hipotético que dio origen a la divergencia en el conjunto de consulta. El método funciona dividiendo una serie de posibles AMS en fragmentos y reordenándolos repetidamente mediante la introducción de huecos en diferentes posiciones. Durante la simulación, se optimiza una función objetivo general , generalmente la función de maximización de la "suma de pares" introducida en los métodos de AMS basados ​​en programación dinámica. Se ha implementado una técnica para secuencias de proteínas en el programa SAGA (Sequence Alignment by Genetic Algorithm) [ 37 ] y su equivalente en ARN se denomina RAGA [ 38 ] .

La técnica de recocido simulado , mediante la cual un alineamiento múltiple de secuencias (AMS) existente, producido por otro método, se refina mediante una serie de reordenamientos diseñados para encontrar mejores regiones del espacio de alineación que la que ya ocupa el alineamiento de entrada. Al igual que el método del algoritmo genético, el recocido simulado maximiza una función objetivo, como la función suma de pares. El recocido simulado utiliza un "factor de temperatura" metafórico que determina la velocidad a la que se producen los reordenamientos y la probabilidad de cada uno; su uso típico alterna períodos de altas tasas de reordenamiento con una probabilidad relativamente baja (para explorar regiones más distantes del espacio de alineación) con períodos de tasas más bajas y probabilidades más altas para explorar con mayor profundidad los mínimos locales cerca de las regiones recién "colonizadas". Este enfoque se ha implementado en el programa MSASA (Alineamiento Múltiple de Secuencias mediante Recocido Simulado). [ 39 ]

Programación matemática y algoritmos de solución exacta

La programación matemática , y en particular los modelos de programación entera mixta, constituyen otro enfoque para resolver problemas MSA. La ventaja de estos modelos de optimización radica en que permiten encontrar la solución óptima de MSA de forma más eficiente que el enfoque tradicional de programación dinámica. Esto se debe, en parte, a la aplicabilidad de las técnicas de descomposición para programas matemáticos, donde el modelo MSA se descompone en partes más pequeñas y se resuelve iterativamente hasta encontrar la solución óptima. Algunos ejemplos de algoritmos utilizados para resolver modelos de programación entera mixta de MSA incluyen el método de ramificación y precio [ 40 ] y la descomposición de Benders [ 3 ] . Si bien los enfoques exactos son computacionalmente lentos en comparación con los algoritmos heurísticos para MSA, garantizan alcanzar la solución óptima, incluso para problemas de gran tamaño.

Computación cuántica simulada

En enero de 2017, D-Wave Systems anunció que su software de computación cuántica de código abierto qbsolv se había utilizado con éxito para encontrar una solución más rápida al problema MSA. [ 41 ]

Visualización de la alineación y control de calidad

El uso necesario de heurísticas para el alineamiento múltiple implica que, para un conjunto arbitrario de proteínas, siempre existe una alta probabilidad de que un alineamiento contenga errores. Por ejemplo, una evaluación de varios programas de alineamiento líderes utilizando el conjunto de datos BAliBase reveló que al menos el 24 % de todos los pares de aminoácidos alineados estaban incorrectamente alineados. [ 2 ] Estos errores pueden surgir debido a inserciones únicas en una o más regiones de las secuencias, o a través de algún proceso evolutivo más complejo que da lugar a proteínas que no se alinean fácilmente solo por su secuencia. A medida que aumenta el número de secuencias y su divergencia, se producirán muchos más errores simplemente debido a la naturaleza heurística de los algoritmos de alineamiento múltiple de secuencias (MSA). Los visualizadores de alineamiento múltiple de secuencias permiten revisar visualmente los alineamientos, a menudo inspeccionando la calidad del alineamiento para los sitios funcionales anotados en dos o más secuencias. Muchos también permiten editar el alineamiento para corregir estos errores (generalmente menores), con el fin de obtener un alineamiento óptimo y "curado" adecuado para su uso en análisis filogenéticos o modelado comparativo. [ 42 ]

Sin embargo, a medida que aumenta el número de secuencias y especialmente en estudios de todo el genoma que involucran muchos MSA, es imposible curar manualmente todos los alineamientos. Además, la curación manual es subjetiva. Y finalmente, incluso el mejor experto no puede alinear con confianza los casos más ambiguos de secuencias altamente divergentes. En tales casos, es práctica común utilizar procedimientos automáticos para excluir regiones alineadas de forma poco fiable del MSA. Para el propósito de reconstrucción filogenética (ver más adelante), el programa Gblocks se utiliza ampliamente para eliminar bloques de alineamiento sospechosos de baja calidad, según varios umbrales en el número de secuencias con huecos en las columnas de alineamiento. [ 43 ] Sin embargo, estos criterios pueden filtrar excesivamente regiones con eventos de inserción/deleción que aún pueden estar alineadas de forma fiable, y estas regiones podrían ser deseables para otros propósitos, como la detección de selección positiva. Algunos algoritmos de alineamiento generan puntuaciones específicas del sitio que permiten la selección de regiones de alta confianza. Este servicio fue ofrecido inicialmente por el programa SOAP, [ 44 ] que prueba la robustez de cada columna ante perturbaciones en los parámetros del popular programa de alineación CLUSTALW. El programa T-Coffee [ 45 ] utiliza una biblioteca de alineaciones en la construcción del MSA final, y su MSA de salida se colorea según puntuaciones de confianza que reflejan la concordancia entre diferentes alineaciones en la biblioteca con respecto a cada residuo alineado. Su extensión, la Puntuación de Consistencia Transitiva (TCS), utiliza bibliotecas de alineaciones por pares de T-Coffee para evaluar cualquier MSA de terceros. Las proyecciones por pares se pueden producir utilizando métodos rápidos o lentos, lo que permite un equilibrio entre velocidad y precisión. [ 46 ] [ 47 ] Otro programa de alineación que puede generar un MSA con puntuaciones de confianza es FSA, [ 48 ] que utiliza un modelo estadístico que permite calcular la incertidumbre en la alineación. La puntuación HoT (Cara o Cruz) se puede utilizar como medida de la incertidumbre de alineación específica del sitio debido a la existencia de múltiples soluciones coóptimas. [ 49 ] El programa GUIDANCE [ 50 ]Calcula una medida de confianza similar específica para cada sitio, basada en la robustez del alineamiento ante la incertidumbre en el árbol guía que se utiliza en los programas de alineamiento progresivo. Un enfoque alternativo, con mayor justificación estadística, para evaluar la incertidumbre del alineamiento es el uso de modelos evolutivos probabilísticos para la estimación conjunta de la filogenia y el alineamiento. Un enfoque bayesiano permite calcular las probabilidades posteriores de la filogenia y el alineamiento estimados, lo que constituye una medida de la confianza en estas estimaciones. En este caso, se puede calcular una probabilidad posterior para cada sitio del alineamiento. Este enfoque se implementó en el programa BAli-Phy. [ 51 ]

Existen programas gratuitos para la visualización de alineamientos de secuencias múltiples, como por ejemplo Jalview y UGENE .

Uso filogenético

Los alineamientos de secuencias múltiples se pueden utilizar para crear un árbol filogenético . [ 52 ] Esto es posible por dos razones. La primera es que los dominios funcionales conocidos en secuencias anotadas se pueden utilizar para el alineamiento en secuencias no anotadas. La segunda es que se pueden encontrar regiones conservadas que se sabe que son funcionalmente importantes. Esto permite que los alineamientos de secuencias múltiples se utilicen para analizar y encontrar relaciones evolutivas a través de la homología entre secuencias. Se pueden detectar mutaciones puntuales y eventos de inserción o deleción (llamados indels).

Los alineamientos de secuencias múltiples también pueden utilizarse para identificar sitios funcionalmente importantes, como sitios de unión, sitios activos o sitios correspondientes a otras funciones clave, mediante la localización de dominios conservados. Al analizar alineamientos de secuencias múltiples, es útil considerar diferentes aspectos de las secuencias al compararlas. Estos aspectos incluyen identidad, similitud y homología. La identidad significa que las secuencias tienen residuos idénticos en sus posiciones respectivas. Por otro lado, la similitud se refiere a que las secuencias que se comparan tengan residuos cuantitativamente similares. Por ejemplo, en términos de secuencias de nucleótidos, las pirimidinas se consideran similares entre sí, al igual que las purinas. La similitud conduce finalmente a la homología, ya que cuanto más similares sean las secuencias, más cerca estarán de ser homólogas. Esta similitud en las secuencias puede ayudar a encontrar un ancestro común. [ 52 ]

Véase también

Referencias

  1. Thompson JD, Linard B, Lecompte O, Poch O (2011). "Un estudio comparativo exhaustivo de métodos de alineación de secuencias múltiples: desafíos actuales y perspectivas futuras" . PLOS One . 6 (3) e18093. Bibcode : 2011PLoSO...618093T . doi : 10.1371/journal.pone.0018093 . PMC 3069049. PMID 21483869 .  
  2. 1 2 Nuin PA, Wang Z, Tillier ER (2006). "La precisión de varios programas de alineación de secuencias múltiples para proteínas" . BMC Bioinformatics . 7 (1) 471. Bibcode : 2006BMCBi...7..471N . doi : 10.1186/1471-2105-7-471 . PMC 1633746. PMID 17062146 .  
  3. 1 2 3 Hosseininasab A, van Hoeve WJ (2019). "Alineación exacta de secuencias múltiples mediante diagramas de decisión sincronizados". INFORMS Journal on Computing ijoc.2019.0937. doi : 10.1287/ijoc.2019.0937 . S2CID 109937203 . 
  4. "Ayuda con matrices utilizadas en herramientas de comparación de secuencias" . Instituto Europeo de Bioinformática. Archivado del original el 11 de marzo de 2010. Recuperado el 3 de marzo de 2010 .
  5. Wang L, Jiang T (1994). "Sobre la complejidad del alineamiento de secuencias múltiples". J Comput Biol . 1 (4): 337– 348. Bibcode : 1994JCoB....1..337W . CiteSeerX 10.1.1.408.894 . doi : 10.1089/cmb.1994.1.337 . PMID 8790475 .  
  6. Just W (2001). "Complejidad computacional del alineamiento de secuencias múltiples con SP-score". J Comput Biol . 8 (6): 615–23 . CiteSeerX 10.1.1.31.6382 . doi : 10.1089/106652701753307511 . PMID 11747615 .  
  7. Elias, Isaac (2006). "Resolviendo la intratabilidad del alineamiento múltiple". J Comput Biol . 13 (7): 1323– 1339. CiteSeerX 10.1.1.6.256 . doi : 10.1089/cmb.2006.13.1323 . PMID 17037961 .  
  8. Carrillo H, Lipman DJ (1988). "El problema de la alineación de secuencias múltiples en biología" . SIAM Journal on Applied Mathematics . 48 (5): 1073– 1082. doi : 10.1137/0148063 .
  9. Lipman DJ, Altschul SF, Kececioglu JD (1989). "Una herramienta para el alineamiento de secuencias múltiples" . Proc Natl Acad Sci USA . 86 (12): 4412– 4415. Bibcode : 1989PNAS...86.4412L . doi : 10.1073 / pnas.86.12.4412 . PMC 287279. PMID 2734293 .  
  10. "Software de análisis genético" . Centro Nacional de Información Biotecnológica. Archivado del original el 19 de enero de 2000. Consultado el 3 de marzo de 2010 .
  11. Feng DF, Doolittle RF (1987) . "Alineación progresiva de secuencias como requisito previo para árboles filogenéticos correctos". J Mol Evol . 25 (4): 351– 360. Bibcode : 1987JMolE..25..351F . doi : 10.1007/BF02603120 . PMID 3118049. S2CID 6345432 .  
  12. 1 2 3 4 5 6 7 8 Mount DM. (2004). Bioinformática: Análisis de secuencias y genomas, 2.ª ed. Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY.
  13. Higgins DG , Sharp PM (1988). "CLUSTAL: un paquete para realizar alineamiento de secuencias múltiples en un microordenador". Gene . 73 (1): 237–244 . doi : 10.1016/0378-1119(88)90330-7 . PMID 3243435 . 
  14. Thompson JD, Higgins DG, Gibson TJ (noviembre de 1994). "CLUSTAL W: mejora de la sensibilidad del alineamiento progresivo de secuencias múltiples mediante ponderación de secuencias, penalizaciones de huecos específicas de posición y elección de matriz de ponderación" . Nucleic Acids Res . 22 (22): 4673–80 . doi : 10.1093/nar/22.22.4673 . PMC 308517. PMID 7984417 .  
  15. "EMBL-EBI-ClustalW2-Alineamiento de secuencias múltiples" . CLUSTALW2 .
  16. Notredame C, Higgins DG, Heringa J (septiembre de 2000). "T-Coffee: un nuevo método para el alineamiento múltiple de secuencias rápido y preciso". J. Mol. Biol . 302 (1): 205–17 . doi : 10.1006/jmbi.2000.4042 . PMID 10964570. S2CID 10189971 .  
  17. Sze SH, Lu Y, Yang Q (2006). "Una formulación de alineación de secuencias múltiples resoluble en tiempo polinomial". J Comput Biol . 13 (2): 309– 319. doi : 10.1089/cmb.2006.13.309 . PMID 16597242 . 
  18. Hirosawa M, Totoki Y, Hoshida M, Ishikawa M (1995). "Estudio exhaustivo sobre algoritmos iterativos de alineación de secuencias múltiples". Aplicaciones informáticas en las biociencias . 11 (1): 13– 18. doi : 10.1093/bioinformatics/11.1.13 . PMID 7796270 . 
  19. Gotoh O (1996). "Mejora significativa en la precisión de los alineamientos de secuencias de proteínas múltiples mediante refinamiento iterativo, evaluada con referencia a alineamientos estructurales". J Mol Biol . 264 (4): 823–38 . doi : 10.1006/jmbi.1996.0679 . PMID 8980688 . 
  20. 1 2 Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B (diciembre de 2003). " Alineamiento múltiple rápido y sensible de secuencias genómicas grandes" . BMC Bioinformatics . 4 66. doi : 10.1186/1471-2105-4-66 . PMC 521198. PMID 14693042 .  
  21. Edgar RC (2004). "MUSCLE: alineación de secuencias múltiples con alta precisión y alto rendimiento" . Nucleic Acids Research . 32 (5): 1792– 97. doi : 10.1093/nar/gkh340 . PMC 390337. PMID 15034147 .  
  22. Collingridge PW, Kelly S (2012). "MergeAlign: mejora del rendimiento de la alineación de secuencias múltiples mediante la reconstrucción dinámica de alineaciones de secuencias múltiples de consenso" . BMC Bioinformatics . 13 (117) 117. Bibcode : 2012BMCBi..13..117C . doi : 10.1186/1471-2105-13-117 . PMC 3413523. PMID 22646090 .  
  23. Hughey R, Krogh A (1996). "Modelos ocultos de Markov para el análisis de secuencias: extensión y análisis del método básico". CABIOS . 12 (2): 95– 107. CiteSeerX 10.1.1.44.3365 . doi : 10.1093/bioinformatics/12.2.95 . PMID 8744772 .  
  24. Grasso C, Lee C (2004). "La combinación de alineación de orden parcial y alineación progresiva de secuencias múltiples aumenta la velocidad de alineación y la escalabilidad a problemas de alineación muy grandes" . Bioinformatics . 20 (10): 1546– 56. doi : 10.1093/bioinformatics/bth126 . PMID 14962922 . 
  25. Hughey R, Krogh A. SAM: Sistema de software para alineación y modelado de secuencias. Informe técnico UCSC-CRL-96-22, Universidad de California, Santa Cruz, CA, septiembre de 1996.
  26. Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Análisis de secuencias biológicas: modelos probabilísticos de proteínas y ácidos nucleicos, Cambridge University Press, 1998.
  27. Söding J (2005). "Detección de homología de proteínas mediante comparación HMM-HMM". Bioinformatics . 21 (7): 951– 960. CiteSeerX 10.1.1.519.1257 . doi : 10.1093/bioinformatics/bti125 . PMID 15531603 .  
  28. Battey JN, Kopp J, Bordoli L, Read RJ, Clarke ND, Schwede T (2007). "Predicciones automatizadas del servidor en CASP7" . Proteins . 69 ( Supl. 8): 68–82 . doi : 10.1002/prot.21761 . PMID 17894354. S2CID 29879391 .  
  29. Loytynoja, A. (2005). "Un algoritmo para el alineamiento múltiple progresivo de secuencias con inserciones" . Actas de la Academia Nacional de Ciencias . 102 (30): 10557– 10562. Bibcode : 2005PNAS..10210557L . doi : 10.1073 / pnas.0409137102 . PMC 1180752. PMID 16000407 .  
  30. Löytynoja A, Goldman N (junio de 2008). "La colocación de huecos con conocimiento de la filogenia previene errores en la alineación de secuencias y el análisis evolutivo". Science . 320 ( 5883): 1632– 5. Bibcode : 2008Sci...320.1632L . doi : 10.1126/science.1158395 . PMID 18566285. S2CID 5211928 .  
  31. Löytynoja A, Vilella AJ, Goldman N (julio de 2012). "Extensión precisa de alineamientos de secuencias múltiples mediante un algoritmo gráfico que considera la filogenia" . Bioinformatics . 28 ( 13): 1684–91 . doi : 10.1093/bioinformatics/bts198 . PMC 3381962. PMID 22531217 .  
  32. Szalkowski AM (junio de 2012). "Alineamiento múltiple de secuencias rápido y robusto con colocación de huecos consciente de la filogenia" . BMC Bioinformatics . 13 129. doi : 10.1186/1471-2105-13-129 . PMC 3495709. PMID 22694311 .  
  33. Henikoff S, Henikoff JG (diciembre de 1991). "Ensamblaje automatizado de bloques de proteínas para búsqueda en bases de datos" . Nucleic Acids Res . 19 (23): 6565–72 . doi : 10.1093/nar/19.23.6565 . PMC 329220. PMID 1754394 .  
  34. Bailey TL, Elkan C (1994). "Ajuste de un modelo de mezcla mediante maximización de expectativas para descubrir motivos en biopolímeros" (PDF) . Actas de la Segunda Conferencia Internacional sobre Sistemas Inteligentes para la Biología Molecular . Menlo Park, California: AAAI Press. págs. 28–36 . 
  35. Bailey TL, Gribskov M (1998). "Combinación de evidencia mediante valores p: aplicación a búsquedas de homología de secuencias" . Bioinformatics . 14 (1): 48– 54. doi : 10.1093/bioinformatics/14.1.48 . PMID 9520501 . 
  36. Salama RA, Stekel DJ (noviembre de 2013). "Un alineamiento de secuencias múltiples basado en energía no independiente mejora la predicción de sitios de unión de factores de transcripción" . Bioinformatics . 29 (21): 2699–704 . doi : 10.1093/bioinformatics/btt463 . PMID 23990411 . 
  37. ^ Notredame C, Higgins DG (abril de 1996). "SAGA: alineación de secuencias por algoritmo genético" . Ácidos nucleicos Res . 24 (8): 1515– 24. doi : 10.1093/nar/24.8.1515 . PMC 145823 . PMID 8628686 .  
  38. ^ Notredame C, O'Brien EA, Higgins DG (1997). "RAGA: alineación de secuencias de ARN mediante algoritmo genético" . Ácidos nucleicos Res . 25 (22): 4570–80.doi : 10.1093 / nar /25.22.4570 . PMC 147093 . PMID 9358168 .  
  39. Kim J, Pramanik S, Chung MJ (1994). "Alineamiento de secuencias múltiples mediante recocido simulado". Aplicaciones informáticas en las biociencias . 10 (4): 419– 26. doi : 10.1093/bioinformatics/10.4.419 . PMID 7804875 . 
  40. Althaus E, Caprara A, Lenhof HP, Reinert K (2006). "Un algoritmo de ramificación y corte para el alineamiento de secuencias múltiples". Mathematical Programming . 105 ( 2– 3): 387– 425. doi : 10.1007/s10107-005-0659-3 . S2CID 17715172 . 
  41. "D-Wave inicia un entorno de software cuántico abierto el 11 de enero de 2017" . Archivado del original el 8 de marzo de 2021. Consultado el 20 de enero de 2017 .
  42. "Edición y ajuste manual de MSA" . Laboratorio Europeo de Biología Molecular. 2007. Archivado del original el 24 de septiembre de 2015. Recuperado el 7 de marzo de 2010 .
  43. Castresana J (abril de 2000). "Selección de bloques conservados de alineamientos múltiples para su uso en análisis filogenéticos" . Biología Molecular y Evolución . 17 (4): 540– 52. doi : 10.1093/oxfordjournals.molbev.a026334 . PMID 10742046 . 
  44. Löytynoja A, Milinkovitch MC (junio de 2001). "SOAP, limpieza de alineamientos múltiples de bloques inestables" . Bioinformatics . 17 (6): 573–4 . doi : 10.1093/bioinformatics/17.6.573 . PMID 11395440 . 
  45. Poirot O, O'Toole E, Notredame C (julio de 2003). "Tcoffee@igs: un servidor web para calcular, evaluar y combinar alineamientos de secuencias múltiples" . Nucleic Acids Res . 31 (13): 3503–6 . doi : 10.1093/nar/gkg522 . PMC 168929. PMID 12824354 .  
  46. Chang, JM; Di Tommaso, P; Notredame, C (junio de 2014). "TCS: una nueva medida de confiabilidad de alineación de secuencias múltiples para estimar la precisión de la alineación y mejorar la reconstrucción del árbol filogenético" . Biología molecular y evolución . 31 (6): 1625–37 . doi : 10.1093/molbev/msu117 . PMID 24694831 . 
  47. Chang JM, Di Tommaso P, Lefort V, Gascuel O, Notredame C (julio de 2015). "TCS: un servidor web para la evaluación de alineamientos de secuencias múltiples y reconstrucción filogenética" . Nucleic Acids Res . 43 (W1): W3–6. doi : 10.1093/nar/gkv310 . PMC 4489230. PMID 25855806 .  
  48. Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L (mayo de 2009). "Alineación estadística rápida" . PLOS Comput. Biol . 5 (5) e1000392. Bibcode : 2009PLSCB ... 5E0392B . doi : 10.1371/journal.pcbi.1000392 . PMC 2684580. PMID 19478997 .  
  49. Landan G, Graur D (2008). "Medidas de fiabilidad local a partir de conjuntos de alineamientos de secuencias múltiples coóptimos". Biocomputing 2008. págs. 15–24 . doi : 10.1142/9789812776136_0003 . ISBN  978-981-277-608-2. PMID 18229673 . {{cite book}}: |journal=ignorado ( ayuda )
  50. Penn O, Privman E, Landan G, Graur D, Pupko T (agosto de 2010). "Una puntuación de confianza de alineación que captura la robustez para guiar la incertidumbre del árbol" . Biología molecular y evolución . 27 (8): 1759– 67. doi : 10.1093/molbev/msq066 . PMC 2908709. PMID 20207713 .  
  51. Redelings BD, Suchard MA (junio de 2005). "Estimación bayesiana conjunta de alineación y filogenia" . Syst. Biol . 54 (3): 401–18 . doi : 10.1080/10635150590947041 . PMID 16012107 . 
  52. 1 2 Budd, Aidan (10 de febrero de 2009). "Ejercicios y demostraciones de alineación de secuencias múltiples" . Laboratorio Europeo de Biología Molecular. Archivado del original el 5 de marzo de 2012. Recuperado el 30 de junio de 2010 .

Artículos de encuesta

  • Duret, L.; S. Abdeddaim (2000). "Alineamiento múltiple para análisis estructurales, funcionales o filogenéticos de secuencias homólogas". En D. Higgins y W. Taylor (eds.). Estructura de secuencias bioinformáticas y bases de datos . Oxford: Oxford University Press.
  • Notredame, C. (2002). "Avances recientes en el alineamiento de secuencias múltiples: una revisión". Farmacogenómica . 3 (1): 131– 144. doi : 10.1517/14622416.3.1.131 . PMID 11966409 . 
  • Thompson, JD; Plewniak, F.; Poch, O. (1999). "Una comparación exhaustiva de programas de alineación de secuencias múltiples" . Nucleic Acids Research . 27 (13): 12682– 2690. doi : 10.1093/nar/27.13.2682 . PMC 148477. PMID 10373585 .  
  • Wallace, IM; Blackshields, G.; Higgins, DG (2005). "Alineamientos de secuencias múltiples". Curr Opin Struct Biol . 15 (3): 261– 266. doi : 10.1016/j.sbi.2005.04.002 . PMID 15963889 . 
  • Notredame, C (2007). "Recent Evolutions of Multiple Sequence Alignment Algorithms" . PLOS Computational Biology . 3 (8) e123. Bibcode : 2007PLSCB...3..123N . doi : 10.1371/journal.pcbi.0030123 . PMC 1963500. PMID 17784778 .  
  • Herramientas de alineación de secuencias ExPASy. Archivado el 13 de abril de 2010 en Wayback Machine.
  • Página de recursos archivada sobre alineación múltiple – de la Escuela Virtual de Ciencias Naturales
  • Herramientas para múltiples alineamientos : de Pôle Bioinformatique Lyonnais
  • Un punto de entrada a los servidores e información de Clúster
  • Un punto de acceso a los servidores principales de T-Coffee.
  • Un punto de entrada al servidor principal de MergeAlign e información
  • Servidores del Instituto Europeo de Bioinformática:
    • ClustalW2 : programa de alineación de secuencias múltiples de propósito general para ADN o proteínas.
    • Músculo : comparación de secuencias múltiples mediante la expectativa logarítmica
    • T-coffee – alineación de secuencias múltiples.
    • MAFFT – Alineación múltiple mediante transformada rápida de Fourier
    • KALIGN : un algoritmo de alineación de secuencias múltiples rápido y preciso.

Apuntes de clase, tutoriales y cursos

  • Conferencias sobre alineación de secuencias múltiples – del Instituto Max Planck de Genética Molecular
  • Apuntes de clase y ejercicios prácticos sobre alineamientos de secuencias múltiples en el Laboratorio Europeo de Biología Molecular (EMBL).
  • Apuntes de clase de Bioinformática Molecular
  • Apuntes de clase sobre Evolución Molecular y Bioinformática