dereita|miniatura|350px|As primeiras 90 posicións dun aliñamento múltiple de secuencias de exemplos da proteína ribosómica ácida P0 (L10E) de varios organismos. Xerado con ClustalX. miniatura|350px|Aliñamento múltiple de 27 secuencias da proteína hemaglutinina do virus da gripe aviaria, coloreado segundo a conservación de residuos (máis escuro canta maior conservación; arriba) e as súas propiedades químicas (abaixo). Un aliñamento múltiple de secuencias ou aliñamento de secuencias múltiples (MSA, nas súas siglas en inglés, de Multiple Sequence Alignment) é un aliñamento das secuencias de tres ou máis secuencias biolóxicas, xeralmente proteínas, ADN ou ARN (secuencias de aminoácidos ou de nucleótidos). En xeral, asúmese que as diversas secuencias a examinar que se introducen como entrada (conxunto problema) teñen unha relación evolutiva, comparten unha liñaxe e descenden dun antepasado común. Do MSA resultante, pode inferirse a homoloxía entre esas moléculas, e pode realizarse unha análise filoxenética para avaliar as orixes evolutivas compartidas polas secuencias. As representacións visuais do aliñamento poñen de manifesto mutacións tales como mutacións puntuais (un só cambio de aminoácidos ou nucleótidos) que aparecen como diferentes caracteres nunha soa columna do aliñamento, e a inserción ou supresión de mutacións (ou indeis) que aparecen como ocos nunha ou varias das secuencias da aliñación. O aliñamento múltiple de secuencias utilízase a miúdo para avaliar a conservación dos dominios proteicos, as estruturas terciarias e secundarias das moléculas, e mesmo aminoácidos ou nucleótidos individuais.
Co termo aliñamento múltiple de secuencias tamén se fai referencia ao proceso de aliñalas como un conxunto de secuencias. Como pode ser difícil aliñar a man tres ou máis secuencias de lonxitude bioloxicamente relevante, e case sempre leva moito tempo, utilízanse algoritmos computacionais para producir e analizar os aliñamentos. Os MSA requiren metodoloxías máis sofisticadas que os aliñamento de pares porque son computacionalmente máis complexos de producir. A maior parte dos programas de aliñamento múltiple de secuencias usan métodos heurísticos en lugar de optimización global, porque identificar o aliñamento óptimo entre máis dunhas poucas secuencias de lonxitude moderada é moi custoso computacionalmente.
Programación dinámica e complexidade computacional O método máis directo para producir aliñamentos múltiples de secuencias utiliza a técnica de programación dinámica para identificar a solución de aliñamento globalmente óptima. Para as proteínas, este método supón normalmente dous conxuntos de parámetros: unha penalización por oco (gap) e unha matriz de substitución que asigna puntuacións ou probabilidades ao aliñamento de cada posible par de aminoácidos baseadas na semellanza das propiedades químicas destes ou na probabilidade evolutiva da mutación. Para secuencias de nucleótidos pode usarse unha matriz de substitución, mais dado que só hai catro caracteres estándar posibles (A, T, G, C) por secuencia, e que os nucleótidos individuais non difiren moito na súa probabilidade de substitución, os parámetros para secuencias de ADN e ARN consisten, normalmente, nunha penalización por gap, unha puntuación positiva para coincidencias de caracteres, e unha puntuación negativa para as faltas de coincidencia. Os valores na matriz de substitución poden ser todos positivos ou unha mestura de positivos e negativos no caso dun aliñamento global, pero deben ser tanto positivos coma negativos no caso dun aliñamento local.
Para n secuencias individuais, o método require construír o equivalente n-dimensional da matriz formada no aliñamento estándar de pares de secuencias da programación dinámica. Desta forma, o espazo de busca increméntase exponencialmente conforme se incrementa n, dependendo tamén fortemente da lonxitude da secuencia. Atopar desta forma o óptimo global para n secuencias é un problema dos denominados NP-completos.Wang L, Jiang T. (1994) On the complexity of multiple sequence alignment. J Comput Biol 1:337-348.Just W. (2001). Computational complexity of multiple sequence alignment with SP-score. J Comput Biol 8(6):615-23. Os métodos para reducir o espazo de busca efectuando inicialmente aliñamentos de pares mediante programación dinámica sobre cada par de secuencias no conxunto problema, e buscando só o espazo solución preto destes resultados (encontrando de forma efectiva a intersección entre traxectorias locais nos arredores inmediatos de cada solución óptima de aliñamento por pares) representan a técnica de programación dinámica máis eficiente. O método denominado "suma de pares" utilízase co software MSA, pero non é aínda práctico para a maioría de aplicacións de aliñamento múltiple de secuencias que requiren o aliñamento simultáneo de ducias (e mesmo de varios centos) de secuencias. Os métodos de programación dinámica só se usan agora cando cómpre facer un aliñamento de moi alta calidade entre un pequeno número de secuencias, e como benchmark estándar (estándar de comparación) na avaliación de técnicas heurísticas novas ou melloradas.
Construción progresiva do aliñamento Un método para realizar unha busca heurística do aliñamento é a técnica progresiva (tamén coñecida como método xerárquico ou de árbore) que constrúe un aliñamento múltiple final realizando primeiro unha serie de aliñamentos de pares sobre secuencias sucesivamente menos emparentadas. Tales métodos comezan aliñando en primeiro lugar as dúas secuencias máis cercanamente relacionadas, para seguir aliñando sucesivamente a seguinte secuencia do conxunto problema máis emparentada co aliñamento producido no paso previo. O par inicial "máis relacionado", ou emparentado, determínase mediante un método eficiente de categorización (ou clustering) tal como UPGMA ou neighbour-joining, baseado nunha simple busca heurística do conxunto problema cunha ferramenta como FASTA. As técnicas progresivas, por tanto, constrúen automaticamente tanto unha árbore filoxenética coma un aliñamento.
Unha limitación importante dos métodos progresivos é a súa forte dependencia da asignación inicial do parentesco entre as secuencias, e da calidade do aliñamento inicial. Deste modo, os métodos son sensibles tamén á distribución das secuencias no conxunto problema: o rendemento mellora cando a cuantificación da estrutura do parentesco entre as secuencias problema compón un gradiente relativamente suave en lugar de encontrarse en categorías afastadas. Tamén se degrada significativamente o rendemento cando todas as secuencias do conxunto teñen unha relación bastante distante, xa que entón son máis probables as imprecisións no aliñamento inicial. Os métodos progresivos máis modernos modifican a súa función de puntuación cunha función de ponderación secundaria que asigna individualmente factores de escala a membros do conxunto problema de forma non lineal, baseada na súa distancia filoxenética aos seus veciños máis próximos. Unha elección asisada dos pesos pode axudar na avaliación das relacións e mitigar os efectos de aliñamentos iniciais relativamente pobres en instantes temperáns da progresión.
Os métodos de aliñamento progresivo son dabondo eficientes como para aplicalos a grande escala para moitas secuencias, e execútanse a miúdo en servidores web accesibles publicamente, polo que os usuarios non necesitan instalar localmente as aplicacións de interese. Uns métodos de aliñamento progresivo moi utilizados son os da familia Clustal,Higgins DG, Sharp PM. (1988). CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. Gene 73(1):237-44. especialmente a variante ponderada ClustalW,Thompson JD, Higgins DG, Gibson TJ. (1994). CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice. Nucleic Acids Res 22:4673-4680. cuxo acceso se proporciona nun bo número de portais web, entre os que están GenomeNet, EBI e EMBNet. Hai diferentes portais ou aplicacións que poden variar a interface co usuario e facer accesibles a este diferentes parámetros. O uso de Clustal está moi estendido para a construción de árbores filoxenéticas e como input para a predición da estrutura de proteínas por medio da modelaxe por homoloxía.
Outro método común de aliñamento progresivo denominado T-CoffeeNotredame C, Higgins DG, Heringa J. (2000). T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol 302(1):205-17. é máis lento que Clustal e os seus derivados, mais xeralmente produce aliñamentos máis precisos para conxuntos de secuencias distantemente emparentadas. T-Coffee calcula aliñamentos de pares combinando o aliñamento directo do par con aliñamentos indirectos que aliñan cada secuencia do par cunha terceira. Usa a saída de Clustal así como outro programa de aliñamento local, LALIGN, que encontra rexións múltiples de aliñamento local entre dúas secuencias. Os aliñamentos e a árbore filoxenética resultante úsanse como guía para producir factores de ponderación novos e máis precisos.
Como os métodos progresivos son heurísticos e, por tanto, non garanten a converxencia a un óptimo global, a calidade do aliñamento pode ser difícil de avaliar, e a súa verdadeira significación biolóxica pode ser escura. Un método semiprogresivo moi recente que mellora a calidade do aliñamento e que non utiliza unha heurística "con perdas" á vez que se executa en tempo polinómicoSze SH, Lu Y, Yang Q. (2006). A polynomial time solvable formulation of multiple sequence alignment. J Comput Biol 13(2):309-19. aplicouse no programa PSAlign.
Métodos iterativos Un conxunto de métodos para producir aliñamentos múltiples de secuencias que reducen os erros inherentes aos métodos progresivos son os clasificados como “iterativos”, xa que traballan de forma similar aos métodos progresivos, pero realiñan repetidamente as secuencias iniciais ademais de engadiren novas secuencias ao MSA en crecemento. Unha razón pola que os métodos progresivos son tan fortemente dependentes da alta calidade do aliñamento inicial é que estes aliñamentos se incorporan sempre ao resultado final; é dicir, unha vez que unha secuencia foi aliñada dentro do MSA, o seu aliñamento non volve a ser considerado. Este enfoque mellora a eficiencia a costa da precisión. En contraste, os métodos iterativos poden volver a aliñamentos de pares previamente calculados (ou sub-MSAs) incorporando subconxuntos da secuencia problema como un medio de optimización dunha función obxectivo xeral, tal como encontrar unha puntuación de aliñamento de alta calidade.
Aplicáronse unha variedade de métodos de iteración sutilmente diferentes, que se poden encontrar en diferentes paquetes de software. Existen revisións e comparacións útiles, pero evitan, xeralmente, elixir algunha das técnicas como a "mellor".Hirosawa M, Totoki Y, Hoshida M, Ishikawa M. (1995). Comprehensive study on iterative algorithms of multiple sequence alignment. Comput Appl Biosci 11:13-18.
O paquete PRRN/PRRP utiliza un algoritmo hill climbing (ascenso da colina) para optimizar a súa puntuación de aliñamento do MSAGotoh O. (1996). Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments. J Mol Biol 264(4):823-38. e corrixir iterativamente tanto as ponderacións do aliñamento como as rexións localmente diverxentes (con ocos) do aliñamento múltiple de secuencias en crecemento.Mount DM. (2004). Bioinformatics: Sequence and Genome Analysis 2nd ed. Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY. O PRRP actúa mellor cando refina un aliñamento previamente construído por un método máis rápido.