# Alineamiento múltiple de secuencias

Un alineamiento múltiple de secuencias (Multiple sequence alignment MSA, por sus siglas en inglés) es un alineamiento de tres o más secuencias biológicas, generalmente proteínas, ADN o ARN. En general, se asume que el conjunto de secuencias de consulta que se ingresa como entrada (conjunto problema) tienen una relación evolutiva por la cual comparten un linaje y descienden de un ancestro común. Del MSA resultante, se puede inferir la homología, y puede llevarse a cabo el análisis filogenético para evaluar los orígenes evolutivos compartidos por las secuencias. Las representaciones visuales del alineamiento ilustran mutaciones tales como mutaciones puntuales (un solo cambio de aminoácidos o nucleótidos) que aparecen como diferentes caracteres en una sola columna del alineamiento, y las inserciones o supresiones de fragmentos (o indels), que aparecen como huecos en una o varias de las secuencias en la alineación. El alineamiento múltiple de secuencias a menudo se utiliza para evaluar la conservación de los dominios proteicos, las estructuras terciarias y secundarias, e incluso aminoácidos o nucleótidos individuales.
Los alineamientos múltiples de secuencias también se refieren al proceso de alinearlas como un conjunto de secuencias. Como puede ser difícil alinear a mano tres o más secuencias de longitud biológicamente relevante, y casi siempre consume mucho tiempo, se utilizan algoritmos computacionales para producir y analizar los alineamientos. Los MSA requieren metodologías más sofisticadas que los alineamiento de pares porque son computacionalmente más complejos de producir. La mayor parte de los programas de alineamiento múltiple de secuencias usan métodos heurísticos en lugar de optimización global, porque identificar el alineamiento óptimo entre más de unas pocas secuencias de longitud moderada es prohibitivamente costoso computacionalmente.

## Programación dinámica y complejidad computacional

El método más directo para producir alineamientos múltiples de secuencias utiliza la técnica de programación dinámica para identificar la solución de alineamiento globalmente óptima. Para las proteínas, este método supone normalmente dos conjuntos de parámetros: una penalización por gap (o hueco) y una matriz de sustitución que asigna puntuaciones o probabilidades al alineamiento de cada posible par de aminoácidos basadas en la similitud de las propiedades químicas de los mismos o en la probabilidad evolutiva de la mutación. Para secuencias de nucleótidos puede usarse una matriz de sustitución, pero dado que solo hay cuatro caracteres estándar posibles por secuencia, y que los nucleótidos individuales no difieren mucho en su probabilidad de sustitución, los parámetros para secuencias de ADN y ARN consisten, normalmente, en una penalización por gap, una puntuación positiva para coincidencias de caracteres, y una puntuación negativa para desigualdades.
Para n secuencias individuales, el método requiere construir el equivalente n-dimensional de la matriz formada en el alineamiento estándar de pares de secuencias de la programación dinámica. De esta forma, el espacio de búsqueda se incrementa exponencialmente conforme se incrementa n, dependiendo también fuertemente de la longitud de la secuencia. Encontrar de esta forma el óptimo global para n secuencias ha mostrado ser un problema NP-completo. Los métodos para reducir el espacio de búsqueda efectuando inicialmente alineamientos de pares mediante programación dinámica sobre cada par de secuencias en el conjunto problema, y buscando solo el espacio solución cerca de estos resultados (encontrando de forma efectiva la intersección entre trayectorias locales en los alrededores inmediatos de cada solución óptima de alineamiento por pares) representan la técnica de programación dinámica más eficiente. El método denominado "suma de pares" se ha implementado en el software MSA, pero no es todavía práctico para la mayoría de aplicaciones de alineamiento múltiple de secuencias que requieren el alineamiento simultáneo de docenas (y aun de varios centenares) de secuencias. Los métodos de programación dinámica solo se usan ahora cuando se necesita un alineamiento de muy alta calidad entre un pequeño número de secuencias, así como benchmark estándar en la evaluación de nuevas o mejoradas técnicas heurísticas.

## Construcción progresiva del alineamiento

Un método para realizar una búsqueda heurística del alineamiento es la técnica progresiva (también conocido como método jerárquico o de árbol) que construye un alineamiento múltiple final realizando primero una serie de alineamientos de pares sobre secuencias sucesivamente menos emparentadas. Tales métodos comienzan alineando en primer lugar las dos secuencias más cercanamente relacionadas, para seguir alineando sucesivamente la siguiente secuencia del conjunto problema más emparentada con el alineamiento producido en el paso previo. El par inicial "más relacionado", o emparentado, se determina mediante un método eficiente de categorización (o clustering) tal como el neighbour-joining, basado en una simple búsqueda heurística del conjunto problema con una herramienta como FASTA. Las técnicas progresivas, por tanto, construyen automáticamente tanto un árbol filogenético como un alineamiento.
Una limitación importante de los métodos progresivos es su fuerte dependencia de la asignación inicial del parentesco entre las secuencias, así como de la calidad del alineamiento inicial. De este modo, los métodos son sensibles también a la distribución de las secuencias en el conjunto problema: el rendimiento mejora cuando la cuantificación de la estructura del parentesco entre las secuencias problema compone un gradiente relativamente suave en lugar de encontrarse en categorías distantes. También se degrada significativamente el rendimiento cuando todas las secuencias del conjunto están bastante lejanamente relacionadas, ya que entonces son más probables las imprecisiones en el alineamiento inicial. Los métodos progresivos más modernos modifican su función de puntuación con una función de ponderación secundaria que asigna individualmente factores de escala a miembros del conjunto problema de forma no lineal, basada en su distancia filogenética a sus vecinos más próximos. Una elección juiciosa de los pesos puede ayudar en la evaluación de las relaciones y mitigar los efectos de alineamientos iniciales relativamente pobres en instantes tempranos de la progresión.
Los métodos de alineamiento progresivo son lo bastante eficientes como para implementarlos a gran escala para muchas secuencias, y se ejecutan a menudo en servidores web públicamente accesibles, por lo que los usuarios no necesitan instalar localmente las aplicaciones de interés. Un método de alineamiento progresivo muy popular es la familia Clustal, especialmente la variante ponderada ClustalW, cuyo acceso se proporciona en un buen número de portales web, incluyendo GenomeNet, EBI y EMBNet Archivado el 1 de mayo de 2011 en Wayback Machine.. Diferentes portales o implementaciones pueden variar la interfaz con el usuario y hacer accesibles a éste diferentes parámetros. Se usa Clustal extensivamente en la construcción de árboles filogenéticos y como input para la predicción de la estructura de proteínas mediante modelado por homología.
Otro método común de alineamiento progresivo denominado T-Coffee es más lento que Clustal y sus derivados, pero generalmente produce alineamientos más precisos para conjuntos de secuencias lejanamente emparentadas. T-Coffee calcula alineamientos de pares combinando el alineamiento directo del par con alineamientos indirectos que alinean cada secuencia del par con una tercera. Usa la salida de Clustal así como otro programa de alineamiento local, LALIGN, que encuentra regiones múltiples de alineamiento local entre dos secuencias. Los alineamientos y el árbol filogenético resultantes se usan como guía para producir nuevos y más precisos factores de ponderación.
Puesto que los métodos progresivos son heurísticos y, por lo tanto, no garantizan la convergencia a un óptimo global, la calidad del alineamiento puede ser difícil de evaluar, y su verdadera significación biológica puede ser oscura. Un muy reciente método semiprogresivo que mejora la calidad del alineamiento y que no utiliza una heurística "con pérdidas" a la vez que se ejecuta en tiempo polinómico se ha implementado en el programa PSAlign Archivado el 2 de agosto de 2020 en Wayback Machine..

## Métodos iterativos

Un conjunto de métodos para producir alineamientos múltiples de secuencias que reducen los errores inherentes en los métodos progresivos son los clasificados como “iterativos”, ya que trabajan de forma similar a los métodos progresivos, pero realinean repetidamente las secuencias iniciales además de añadir nuevas secuencias al MSA en crecimiento. Una razón por la que los métodos progresivos son tan fuertemente dependientes de la alta calidad del alineamiento inicial es el hecho de que estos alineamientos se incorporan siempre al resultado final; esto es, una vez que una secuencia ha sido alineada dentro del MSA, su alineamiento no vuelve a ser considerado. Este enfoque mejora la eficiencia a costa de la precisión. En contraste, los métodos iterativos pueden volver a alineamientos de pares previamente calculados (o sub-MSAs) incorporando subconjuntos de la secuencia problema como un medio de optimización de una función objetivo general, tal como encontrar una puntuación de alineamiento de alta calidad.
Se ha implementado una variedad de métodos de iteración sutilmente diferentes, que han sido dispuestos en diferentes paquetes de software. Existen revisiones y comparaciones útiles, pero evitan, generalmente, elegir la "mejor" técnica.
El paquete PRRN/PRRP utiliza un algoritmo hill climbing (ascenso a colina, en alguna literatura) para optimizar su puntuación de alineamiento del MSA y corregir iterativamente tanto las ponderaciones del alineamiento como las regiones localmente divergentes (con huecos) del alineamiento múltiple de secuencias en crecimiento. PRRP actúa mejor cuando refina un alineamiento previamente construido por un método más rápido.
Otro programa iterativo, DIALIGN, toma una inusual aproximación al concentrarse estrechamente sobre alineamientos locales entre subsegmentos o secuencias motivo sin introducir una penalización por hueco. Se consigue el alineamiento de motivos individuales con una representación matricial similar a una gráfica de matriz de puntos en un alineamientos de pares. Un método alternativo que utiliza alineamientos locales rápidos como puntos de referencia o "semillas" para un procedimiento más lento de alineamiento global se implementa en la suite CHAOS/DIALIGN.
Un tercer método popular basado en la iteración, llamado MUSCLE (de multiple sequence alignment by log-expectation, o alineamiento múltiple de secuencias por log-esperanza; este último término corresponde a una función de puntuación no común basada en la esperanza matemática, y resultado de modificar la función log-average o log-promedio), mejora en relación con los métodos progresivos con una medida más precisa de la distancia para valorar el parentesco de dos secuencias. La medición de la distancia se actualiza entre las etapas de la iteración (sin embargo, en su forma original, MUSCLE contenía solo dos o tres iteraciones, dependiendo de si se activaba o no el refinamiento).

## Modelos de Márkov ocultos

Los modelos de Márkov ocultos (o HMM, del inglés Hidden Márkov Models) son modelos probabilísticos que asignan probabilidades a todas las posibles combinaciones de huecos, coincidencias y diferencias para determinar el más probable alineamiento múltiple de secuencias o conjunto de posibles MSA. Los HMM pueden producir una salida única con la mayor puntuación, pero también pueden generar una familia de alineamientos posibles que puedan ser evaluados en su significación biológica. Dado que los modelos ocultos de Márkov son probabilísticos, no producen la misma solución cada vez que se ejecutan sobre el mismo conjunto de datos; de esta forma, no pueden garantizar converger al alineamiento óptimo. Los HMM pueden producir alineamientos tanto locales como globales. Aunque los métodos basados en estos modelos han sido desarrollados recientemente, ofrecen mejoras significativas en la velocidad computacional, especialmente para secuencias que contienen regiones solapadas.
Los métodos típicos basados en HMM trabajan representando un MSA bajo la forma de grafo dirigido acíclico, conocido como un grafo de orden parcial, y que consiste en una serie de nodos representando posibles entradas en las columnas de un alineamiento múltiple de secuencias. En esta representación, una columna que esté absolutamente conservada (esto es, que todas las secuencias en el MSA compartan un carácter determinado en esa posición en particular) se codifica como un único nodo con tantas conexiones salientes como posibles caracteres haya en la siguiente columna del alineamiento. En los términos de un típico modelo oculto de Márkov, los estados observados son las columnas individuales del alineamiento, y los estados "ocultos" representan la supuesta secuencia ancestral desde la cual las secuencias del conjunto problema se presume han descendido. Una variante de búsqueda eficiente del método de programación dinámica, conocida como algoritmo de Viterbi, se usa generalmente para alinear sucesivamente el MSA en crecimiento con la siguiente secuencia del conjunto problema para generar un nuevo MSA. Esto es diferente de los métodos de alineamiento progresivo puesto que el alineamiento de las secuencias previas se actualiza en cada adición de una nueva secuencia. Sin embargo, como en los métodos progresivos, esta técnica puede verse influenciada por el orden en el cual las secuencias del conjunto problema son integradas al alineamiento, especialmente cuando las secuencias están lejanamente relacionadas.
Pueden encontrarse bastantes programas de software en los cuales se han implementado variantes de los métodos basados en HMM, y que se caracterizan por su escalabilidad y eficiencia, aunque el uso correcto de un método HMM es más complejo que el de los métodos progresivos más comunes. El más sencillo es POA (Partial-Order Alignment, alineamiento de orden parcial). Un método similar, pero más general, se implementa en el paquete SAM (Sequence Alignment and Modeling System, sistema de alineamiento y modelado de secuencia). SAM se ha usado como una fuente de alineamientos para predicción de estructura de proteínas al participar en el experimento de predicción de estructura CASP (de Critical Assessment of Techniques for Protein Structure Prediction, valoración crítica de técnicas para predicción de la estructura de proteínas), y para desarrollar una base de datos de proteínas predichas en la especie de levadura S. cerevisiae. Los métodos HMM también pueden usarse para búsquedas en bases de datos con HMMer.

## Algoritmos genéticos y simulated annealing

En el intento de producir MSA de calidad de forma más eficiente también se han usado algunas técnicas de optimización estándar en ciencias de la computación inspiradas por procesos físicos (pero que no los reproducen directamente). Una de tales técnicas, los algoritmos genéticos, se han utilizado en la producción de MSA intentando simular, en líneas generales, el hipotético proceso evolutivo que da lugar a la divergencia en el conjunto problema. Este método trabaja rompiendo en fragmentos una serie de posibles MSA y reordenando repetidamente estos fragmentos con la introducción de huecos en diferentes posiciones. Una función objetivo general se optimiza durante la simulación, normalmente una función de maximización "suma de pares" introducida en los métodos de MSA de programación dinámica. Se ha implementado una técnica para secuencias de proteínas en el programa de software SAGA (Sequence Alignment by Genetic Algorithm, alineamiento de secuencias por algoritmo genético), denominándose RAGA su equivalente para ARN.
Mediante la técnica de simulated annealing (tienen relativamente poco éxito en la literatura en castellano traducciones como "temple" o "recocido" simulado), un alineamiento múltiple de secuencias existente, producido por otro método, se refina por una serie de reordenamientos diseñados para encontrar regiones más óptimas del espacio de alineamiento que la ya ocupada por el MSA previo. Al igual que en el método de algoritmos genéticos, en simulated annealing se maximiza una función objetivo como la suma de pares. Este método utiliza un "factor de temperatura" virtual que determina el ritmo al cual los reordenamientos avanzan, así como la probabilidad de cada uno de ellos. Un uso típico alterna periodos de altos ritmos de reorganización y relativamente baja probabilidad (para explorar regiones más distantes del espacio de alineamiento), con periodos de bajos ritmos y más altas probabilidades para explorar a fondo mínimos locales cerca de las regiones recientemente “colonizadas”. Este enfoque ha sido implementado en el programa MSASA (Multiple Sequence Alignment by Simulated Annealing, alineamiento múltiple de secuencias por simulated annealing).

## Descubrimiento de motivos

El descubrimiento de motivos, también conocido como análisis de perfiles, es un método de localización de motivos de secuencia en MSA globales, y que supone tanto un medio para producir mejores alineamientos múltiples de secuencias como para producir una matriz de puntuación para ser usada en la búsqueda de motivos similares en otras secuencias. Se han desarrollado varios métodos para aislar los motivos, pero todos están basados en la identificación de patrones cortos altamente conservados dentro de un alineamiento mayor, y en la construcción de una matriz, similar a una de sustitución, que refleje la composición de aminoácidos o nucleótidos de cada posición en el supuesto motivo. Los alineamientos se pueden refinar entonces usando estas matrices. En el análisis estándar de perfiles, la matriz incluye entradas para cada posible carácter, así como entradas para huecos. Alternativamente, los algoritmos estadísticos de descubrimiento de patrones pueden identificar motivos como precursores de MSA, en lugar de como derivados. En muchos casos, cuando el conjunto de secuencias problema contiene solo un pequeño número de secuencias, o contiene solo secuencias altamente relacionadas, se añaden seudocontadores para normalizar la distribución reflejada en la matriz de puntuación. Esto corrige, en particular, entradas en la matriz con probabilidad cero mediante valores pequeños, pero no nulos.
El análisis de bloques es un método de descubrimiento de motivos que los restringe a regiones sin huecos en el alineamiento. Los bloques se pueden generar desde un MSA o pueden ser extraídos de secuencias sin alinear usando un conjunto precalculado de motivos previamente generado desde familias conocidas de genes. La puntuación de los bloques depende generalmente del espaciado de los caracteres con altas frecuencias, en lugar de recaer sobre el cálculo de una matriz de sustitución explícita. El servidor BLOCKS proporciona un método interactivo para localizar tales motivos en secuencias sin alinear.
Se han implementado comparadores de patrones utilizando tanto el algoritmo expectación-maximización como el muestreo de Gibbs. Una de las más comunes herramientas de descubrimiento de motivos, denominada MEME, utiliza expectación-maximización y modelos ocultos de Márkov para generar motivos que luego se usan como herramientas de búsqueda por su compañero MAST en la suite combinada MEME/MAST.