# Alineament múltiple de seqüències

L'alineament múltiple de seqüències (MSA, per les sigles en anglès) es refereix al procés o resultat d’un alineament de seqüències de tres o més seqüències biològiques, generalment proteïnes, ADN o ARN. En alguns casos, es poden trobar relacions evolutives i inclús l'avantpassat comú. En cas que es vulgui inferir homologia s'ha de recórrer a l'anàlisi filogenètic.
Podríem considerar que un MSA és una organització matricial d’un grup de seqüències, en la qual cada fila correspon a una seqüència diferent (per exemple, d’espècies diferents) i cada columna correspon a una posició equivalent en les seqüències. Les representacions visuals de l’alineament mostren les mutacions puntuals (un únic canvi d’aminoàcid o de nucleòtid) que apareixen com diferents caràcters en una mateixa columna, així com les insercions o delecions de fragments, conegudes com a indels, que apareixen com buits a les seqüències.
Per dur a terme aquest procés s'usen algorismes computacionals per produir i analitzar els alineaments. La major part dels programes utilitzen mètodes heurístics en canvi d'optimitzacions globals, ja que trobar un alineament global per moltes seqüències és costós a nivell computacional. Per altra banda, les solucions heurístiques no et donen garanties sobre la qualitat de les mateixes i solen estar per sota de la solució òptima.

## Mètodes d'alineament

Hi ha diversos mètodes d’alineament que s'utilitzen dintre dels alineaments de seqüències múltiples per maximitzar les puntuacions i la correcció dels alineaments.

### Programació dinàmica

Un mètode directe per produir MSA és l’ús de tècniques de programació dinàmica amb l’objectiu d’identificar la solució d’alineament òptim. Per proteïnes aquest mètode implica dos paràmetres: una penalització per gap (indel) i una matriu de substitució, que consistiria a alinear cada parell d’aminoàcids basant-se en les propietats químiques i la probabilitat evolutiva que ocorri la mutació. Per les seqüències nucleotídiques s'utilitza una penalització semblant, però les matrius de substitució són més simples, ja que només hi ha quatre caràcters possibles, només es consideren puntuacions positives en casos de coincidencia (match) i puntuació negativa en els casos de desigualtat (mismatches). Les puntuacions de les matrius de substitució poden ser positives o una combinació de positives i negatives en el cas dels alineaments globals, però en el cas d’un alineament local s'han de tenir en compte les positives i les negatives.
Per n seqüències individuals, el mètode requereix reconstruir l'equivalent n-dimensional de la matriu formada a l’alineament estàndard dels parells de seqüències. D’aquesta forma hi ha un increment exponencial de l'espai de cerca a mesura que va augmentant n, fet que també dependrà de la longitud de la seqüència. La troballa de l’òptim global per n seqüències mitjançant aquest mètode es considera com un problema NP-complet. El 1989, basat en l'algorisme Carrillo-Lipman, Altschul va introduir un mètode pràctic que utilitzava els alineaments parells per restringir l'espai de cerca n-dimensional. En aquest enfocament els alineaments de programació dinàmica per parells es realitzen a cada parell de seqüències del conjunt de consultes, i només es busca l’alineament a l'espai n-dimensional (es troba de forma efectiva la intersecció entre les trajectòries locals dels voltants immediats de cada solució òptima de l’alineament per parells). Actualment els mètodes de programació dinàmica només s'utilitzen quan es necessita un alineament d’alta qualitat entre un petit nombre de seqüències, així com benchmark estàndard en l'avaluació de tècniques heurístiques noves o millorades.

### Construcció progressiva de l’alineament

És el mètode més utilitzat per dur a terme l’alineament múltiple de seqüències. Utilitza una recerca heurística coneguda com a tècnica progressiva (també conegut com a mètode jeràrquic o arbre) desenvolupat per Da-Fei Feng i Doolittle el 1987. L’alineament progressiu crea un MSA combinant alineaments de parelles començant per les parelles més similars i progressant cap a les més llunyanes. Tots els alineaments progressius requereixen dues passes: el primer pas on les relacions entre seqüències són representades com un arbre filogenètic, anomenat arbre guia, i un segon pas on es construeix el MSA afegint progressivament les seqüències per construir l’alineament d’acord amb l’arbre guia. L'arbre guia inicial està determinat per un algorisme d'agrupament (clustering en anglès), com podrien ser els mètodes de neighbor-joining (o "unió de veïns") o UPGMA (de l’anglès Unweighted Pair Group Method with Arithmetic mean). A més, utilitza distàncies basades en el nombre de subseqüències idèntiques de dues lletres (ús de FASTA en lloc d’una alineació de programació dinàmica).
El principal problema dels alineaments progressius és que si es produeix en qualsevol etapa del creixement del MSA, s'afectarà el resultat final, per tant és important una bona assignació inicial del parentesc entre les seqüències. El rendiment és baix quan totes les seqüències del conjunt estan relacionades de manera llunyana. Alguns mètodes progressius més moderns modifiquen la seva funció de puntuació amb una funció de ponderació secundària, que assigna factors d’escala als membres individuals de la consulta establerts de manera no lineal, en funció de la seva distància filogenètica, respecte als seus veïns més propers. Això corregeix la selecció no aleatòria de les seqüències donades al programa.
Aquests mètodes són suficientment eficients per a poder ser implementats a gran escala per a moltes seqüències, i s'executen sovint a servidors web d'accés públic, de manera que els usuaris no necessiten instal·lar localment les aplicacions. El mètode d’alineament progressiu més conegut és la família Clustal, especialment la seva variant ponderada ClustalW, al qual es pot accedir a través d'un gran nombre de portals web, com ara GenomeNet, EBI i EMBNet Arxivat 2011-05-01 a Wayback Machine.. Clustal s'utilitza principalment en la creació d’arbres filogenètics i com a base per a la predicció d’estructura de proteïnes mitjançant models d'homologia. La darrera versió de la família Clustal i recomanada per l'EMBL-EBI és Clustal Omega, el qual es basa en arbres guia arrelats i tècniques de models de Màrkov ocults per fer alineament de proteïnes. Un altre programa habitual és T-Coffee que no ofereix la rapidesa de Clustal, però produeix alineaments més precisos per a conjunts de seqüències emparentades de forma llunyana.
Al basar-se en l’heurística pot ser difícil avaluar la qualitat de l’alineament i la seva significació biològica. El programa PSAlign Arxivat 2020-08-02 a Wayback Machine. és un mètode semiprogressiu que té com a objectiu la millora de la qualitat de l’alineament, ja que no utilitza una heurística “amb pèrdues” i s'executa en temps polinòmic.

### Mètodes iteratius

Es tracta d’uns mètodes per produir MSA que redueixen els errors inherents en els mètodes progressius. S'anomenen “iteratius” perquè treballen d’una manera semblant als mètodes progressius, però realineen de manera repetida les seqüències inicials i afegeixen de noves al MSA en construcció. Un dels motius pels quals els mètodes progressius depenen en gran manera d’una alta qualitat de l’alineament inicial és perquè aquests alineaments sempre s'inclouran al resultat final, ja que un cop la seqüència s'introdueix al MSA no es tornarà a fer l’alineament. Aquesta aproximació millora l'eficiència a costa de la precisió. En canvi, com ja hem vist, els mètodes iteratius poden tornar als alineaments parells calculats prèviament (o sub-MSAs) incorporant subconjunts de la seqüència problema com a mesura per optimitzar una funció objectiu general, així com buscar l’alineament amb la puntuació més alta.
S'han implementat diversos mètodes subtilment diferents i estan disponibles en paquets de programari; els articles de revisió i les comparacions són útils, però normalment s'abstenen d’escollir quina és la “millor” tècnica. El paquet de programari PRRN/PRRP utilitza un algorisme hill climbing (o "algorisme d'escalada") per optimitzar la puntuació del MSA. PRRP té un millor rendiment quan refina un alineament construït prèviament per un mètode més ràpid.
Un altre programa iteratiu, DIALIGN, adopta un enfocament inusual centrant-se en els alineaments locals entre subsegments o motius de seqüència sense introduir un penalització per gap. L’alineament de motius individuals s'aconsegueix amb una representació en forma de matriu semblant a les matrius de punts (dot-matrix en anglès) en els alineaments parells. Hi ha un mètode alternatiu que utilitza alineaments locals ràpids com a punts d’ancoratge per a un procediment d’alineament global més lent, el qual s'implementa a CHAOS/DIALIGN.
El tercer mètode iteratiu conegut es coneix com a MUSCLE (de les sigles en anglès, MUltiple Sequence Comparison by Log-Expectation) i millora els mètodes progressius. El que fa és mesurar una distància més acurada per avaluar la relació entre dues seqüències. La mesura de la distància s'actualitza entre les etapes d’iteració (tot i que originàriament, MUSCLE contenia només 2-3 iteracions depenent si el refinament estava habilitat o no).

### Mètodes consens

Els mètodes consens pretenen trobar el MSA òptim d’entre els diferents alineaments del mateix grup de seqüències. Hi ha dos mètodes comuns utilitzats: M-COFFEE Arxivat 2020-08-02 a Wayback Machine. i MergeAlign. M-COFFEE utilitza MSA generats de set formes diferents, ja que combina els outputs de diferents alineadors. MergeAlign és capaç de generar alineaments consens a partir de qualsevol nombre d’alineaments introduïts utilitzant models d’evolució de seqüències entre d'altres. L'opció per defecte de MergeAlign és inferir l’alineament consens utilitzant alineaments generats utilitzant 91 models diferents d’evolució de la seqüència proteica, això és possible per l’ús de diferents matrius de substitució d’aminoàcids, que és més acurat que no pas l’ús d’una única matriu.

### Models de Màrkov ocults

Els models ocults de Màrkov o HMM (per les seves sigles de l'anglès Hidden Màrkov Models) són models probabilístics que assignen probabilitats a totes les possibles combinacions de buits (gap), coincidències (match) i diferències (mismatch) per determinar alineament múltiple de seqüències o el conjunt d'aliments més probables. Els HMM poden produir un resultat únic amb la puntuació més alta, o també poden generar una família de possible alineacions que després es poden avaluar segons la seva significació biològica. Els HMM poden produir tant alineaments globals com locals. Tot i que els mètodes basats en HMM s'han desenvolupat recentment, ofereixen millores significatives pel que fa a velocitat computacional, especialment per a seqüències que contenen regions superposades.
Els mètodes típics basats en HMM funcionen representant un MSA en forma de graf dirigit acíclic, conegut com un graf d'ordre parcial, i que consisteix en una sèrie de nodes que representen possibles entrades a les columnes d'un alineament múltiple de seqüències. En aquesta representació, una columna que estigui absolutament conservada (és a dir, que totes les seqüències del MSA comparteixen un caràcter concret en una posició determinada) es codifica com un únic node amb tantes connexions sortints com possibles caràcters hi hagi a la següent columna de l'alineament. En els termes d'un típic model ocult de Màrkov, els estats "observats" són les columnes individuals de l'alineament i els estats "ocults" representen la presumpta seqüència ancestral de la qual se suposa que han descendit les seqüències del conjunt problema. Una variant de cerca eficient del mètode de programació dinàmica, coneguda com l'algorisme de Viterbi, s'utilitza generalment per alinear successivament el MSA en creixement amb la següent seqüència del conjunt problema per tal de produir un nou MSA. Això és diferent dels mètodes d'alineament progressiu, ja que l'alineament de les seqüències prèvies s'actualitza en cada addició d'una nova seqüència. Tanmateix, igual que els mètodes progressius, aquesta tècnica pot veure's influenciada per l'ordre en què les seqüències del conjunt problema s'integren a l'alineament, especialment en el cas que les seqüències no estiguin estretament relacionades.
Hi ha diversos programes disponibles en els quals s'han implementat variants dels mètodes basats en HMM i que destaquen per la seva escalabilitat i eficiència, tot i que l’ús correcte d’un mètode HMM és més complex que no pas el dels mètodes progressius més comuns. El més senzill és POA (Partial-Order Alignment o "alineament d’ordre parcial"); Un mètode similar, però més general, és el que s'implementa als paquets SAM (Sequence Alignment and Modeling System o "sistema d’alineament de seqüència"). El SAM s'ha utilitzat com a font d’alineaments per a la predicció de l'estructura de proteïnes en participar en l'experiment de predicció d’estructures CASP (Critical Assessment of Techniques for Protein Structure Prediction o "Avaluació Crítica de les Tècniques per la Predicció de l'Estructural Proteica") i per desenvolupar una base de dades de proteïnes predites en l'espècie de llevat S. cerevisiae. D’altra banda, els mètodes del HMM també es poden fer servir per cerques a bases de dades amb HMMER.

### Mètodes filogenètics

La majoria dels mètodes d’alineament intenten reduir el nombre d'insercions/delecions i produir alineaments compactes. Això crea diversos problemes en el cas que les seqüències que vulguem alinear continguin regions que no siguin homòlogues. Aquests problemes són comuns a seqüències noves que no estan ben anotades i que poden contenir mutacions en el patró de lectura de la traducció, dominis que no li pertoquen o exons empalmats no homòlegs. El primer mètode d’aquest tipus va ser desenvolupat el 2005 per Löytynoja i Goldman. Els mateixos autors van publicar el 2008 un paquet de programa anomenat PRANK que millora els alineaments quan hi ha insercions. Per contra, funciona més lent comparat amb els mètodes progressius o iteratius que van ser desenvolupats uns anys abans.
El 2012 van aparèixer dues eines filogenètiques noves: PAGAN i ProGraphMSA. Els dos programes es van desenvolupar independentment però comparteixen algunes característiques, com per exemple l’ús de grafs per millorar el reconeixement de les regions no-homòlogues i millorant la velocitat respecte PRANK.

### Descobriment de motius

El descobriment de motius, també conegut com a cerca de patrons, és un mètode per localitzar motius de seqüència en MSA globals, i que representa un mitjà per produir millors alineaments de seqüències múltiples, així com per produir una matriu de puntuació per ser utilitzada en la cerca de motius similars a altres seqüències. S'han desenvolupat diversos mètodes per aïllar els motius, però tots es basen a identificar patrons curts molt conservats dins d’un l'alineament més gran i en la construcció d’una matriu, similar a una matriu de substitució que reflecteixi la composició d'aminoàcids o nucleòtids de cada posició en el suposat motiu. Els alineaments es poden refinar aleshores mitjançant aquestes matrius. En l'anàlisi estàndard de perfils, la matriu inclou entrades per a cada possible caràcter, així com entrades per a buits (gaps). D'altra banda, els algoritmes estadístics de cerca de patrons poden identificar motius com a precursors d’un MSA en lloc de com a derivats. En molts casos, quan el conjunt de seqüències problema només conté un nombre reduït de seqüències, o només conté seqüències molt relacionades, s'afegeixen pseudo-comptadors per a normalitzar la distribució reflectida a la matriu de puntuació. En particular, això corregeix les entrades a la matriu amb probabilitat zero mitjançant valors petits però no nuls.
L'anàlisi per blocs és un mètode de descobriment de motius que restringeix la seva localització a regions de l'alineament que no tinguin buits. Els blocs es poden generar des d'un MSA o bé poden ser extrets de seqüències sense alinear fent servir un conjunt precalculat de motius generat a partir de famílies conegudes de gens. La puntuació dels blocs depèn generalment de l'espaiat que hi ha entre caràcters amb una alta freqüència, més que en el càlcul d'una matriu de substitució explicita. Existeixen servidors com BLOCKS o InterPro els quals ofereixen un mètode interactiu per tal de localitzar motius en seqüències sense que aquestes estiguin alineades.
S'han implementat comparadors de patrons fent servir tant l'algorisme expectació-maximització com el mostreig de Gibbs. Una de les eines més habituals de cerca de motius, denominada MEME, utilitza expectació-maximizatció juntament amb models de Màrkov ocults per generar motius que després es fan servir com a eina de cerca amb MAST en la suite combinada MEME/MAST Arxivat 2010-08-22 a Wayback Machine..

### Alineament múltiple de seqüències no codificants

Les regions no codificants de l’ADN, sobretot els llocs d’unió de factors de transcripció (o TFBS de l’anglès transcription factor binding site), es troben més conservades i no necessàriament estan relacionades evolutivament. De fet, poden haver convergit sense tenir un avantpassat comú. Per tant, les assumpcions que fem per alinear seqüències de proteïnes i regions de l’ADN codificants són diferents respecte a les que fem en el cas dels TFBS. Tot i que té sentit fer servir operadors mutadors per alinear regions codificants de seqüències homòlogues, els alineaments de seqüències d’unió per a un mateix factor de transcripció no es poden basar en aquests operadors mutadors de relacions evolutives. De la mateixa manera, l’operador evolutiu de les mutacions puntuals es pot fer servir per a definir una distància d’edició per a seqüències codificants, però tindria poc sentit per als TFBS, perquè qualsevol variació en la seqüència ha de mantenir un cert nivell d’especificitat per tal que siguin funcionals. Aquest fet esdevé molt important quan s'intenten alinear seqüències d’unió conegudes per tal de construir models que permetin predir altres localitzacions desconegudes d’aquest mateix lloc d’unió. Tot plegat, els mètodes per realitzar alineaments de múltiples seqüències han d’ajustar la hipòtesi evolutiva subjacent i els operadors que es fan servir i així alinear els llocs d’unió buscant l'alineament menys termodinàmic alhora que es conserva l'especificitat pel lloc d’unió. Això es podria aconseguir mitjançant el programa EDNA.

### Comparació de metodologies i programes

TAULA COMPARATIVA ENTRE DIFERENTS PROGRAMES :
| Nom | Descripció | Tipus de seqüència | Mètode | Autors | Any |
| PRRN/PRRP | Refina els alineaments creats amb mètodes més ràpids mitjançant l'algorisme hill climbing. | Proteïnes | Iteratiu | Totoki Y. (basat en Gotoh O.) | 1991 |
| ClustalW | En primer lloc, alineament de les seqüències més similars fins a crear un alineament global. | Proteïnes Nucleòtids | Progressiu | Thompson JD. et al. | 1994 |
| T-Coffee | Genera una llibreria per tal de dur a terme el MSA. | Proteïnes Nucleòtids | Progressiu | Notredame C. et al. | 2000 |
| CHAOS/DIALIGN | Fa alineacions globals a partir d'alineacions per parells sense deixar gaps (forats a la seqüència). | Proteïnes Nucleòtids | Iteratiu | Brudno M. i Morgenstern B. | 2003 |
| MUSCLE | Té 3 etapes: esborrany progressiu, progressiu millorat i refinament. Mesura una distància més acurada. | Proteïnes Nucleòtids | Progressiu-iteratiu | Edgar R.C. | 2004 |
| BAli-Phy | Estima el MSA utilitzant informació de l'arbre filogenètic. | Proteïnes Nucleòtids Codons | Bayesià | Redelings B.D. i Suchard M.A. | 2005 |
| UGENE | Dona suport a diferents plataformes (MUSCLE, ClustalW...) | Proteïnes Nucleòtids | - | Fursov M. | 2008 |
| Clustal Omega | Darrera versió de la famíloia Clustal, es serveix d'un algorisme basat en Models de Màrkov ocults. | Proteïnes Nucleòtids | Model de Màrkov ocult | Sievers F. et al. | 2011 |

## Optimització
### Algoritmes genèrics i simulated annealing

Les tècniques d'optimització estàndard en informàtica també han estat usades per intentar produir MSA d'una certa qualitat i de manera eficient. Una de les tècniques són els algorismes genètics que s'utilitzen per produir MSA en un intent de simular de manera general l'hipotètic procés evolutiu que va donar lloc a la divergència en el conjunt de seqüències. El mètode consisteix en tallar possibles alineaments MSA en fragments i anar unint els fragments de manera repetida amb la introducció de gaps a diverses posicions. S'optimitza una funció objectiu durant la simulació, més generalment la funció de maximització de "suma de parells" introduïda en els MSA basats en la programació dinàmica. S'ha implementat una tècnica per seqüències proteiques al programa SAGA (Sequence Alignment by Genetic Algorithm), l'equivalent en RNA es coneix com a RAGA.
La tècnica de recuita simulada (més conegut pel seu nom anglès simulated annealing) s'encarrega de refinar i reordenar els alineaments determinats per algun altre mètode, ja que estan dissenyats per trobar les millors regions en l'espai d'alineació que la regió que ocupa l'input d'alineament. Aquest model també planteja que hi hagi una funció objectiu. Com a diferència s'utilitza un "factor de temperatura" (o factor Debye-Waller) virtual que determina la velocitat a la qual es duen a terme els reordenaments i la probabilitat de cadascun d'ells; típicament alterna períodes d'altes taxes de reordenaments amb probabilitats baixes (per explorar regions llunyanes de l'espai d'alineació) amb períodes de taxes baixes i probabilitats més altes per explorar els mínims locals a prop de les regions recentment "colonitzades". La implementació es fa a través del programa MSASA (Multiple Sequence Alignment by Simulated Annealing).

### Programació matemàtica i algorismes de solució exacta

La programació matemàtica, en particular la dels models de programació d'enters mixta, són un altre mètode de resolució de MSA. L'avantatge és que milloren l'eficiència respecte als mètodes de programació dinàmica degut a l'aplicabilitat de les tècniques de descomposició per a programes matemàtics, on els models MSA són descompostos en petites porcions i resolts de manera iterativa fins que es troba una solució. Alguns algorismes d'exemple que s'utilitzen per resoldre models de programació d'enters mixta inclouen el branch and price ("branca i preu") i la descomposició de Benders. Tot i que els mètodes exactes són més lents comparats amb els algorismes heurístics, garanteixen la troballa d'una solució final òptima, inclús per mostres de gran longitud.

### Computació quàntica simulada

El gener del 2017, D-Wave Systems va anunciar que el seu programari informàtic de codi obert Qbsolov s'havia utilitzat per trobar una solució més ràpida al MSA. L'objectiu de la seva creació va ser que fos més fàcil accedir al poder de la computació quàntica i a la creació de programari específic, però sense necessitat d'entendre la física complexa arrelada a aquest àmbit. Qsolov tracta de subdividir els problemes grans per poder resoldre'ls en processadors D-Wave, finalitzant amb la combinació de les respostes individuals en una global.

## Visualització dels alineaments i control de qualitat

La necessitat de l'ús de l'heurística per l'alineament múltiple vol dir que per a un grup de proteïnes hi ha sempre una possibilitat que l'alineament contingui errors. Per exemple, una avaluació de diversos programes d'alineaments guia mitjançant BAliBase benchmark va trobar aproximadament un 24% de les parelles d'aminoàcids alineats incorrectament. Aquests errors poden ocórrer perquè les insercions úniques en una o més seqüències, o a través de processos evolutius més complexos, porta a un difícil alineament de les proteïnes només per la seqüència. En cas que s'augmenti el nombre de la seqüència i incrementi la seva divergència es produiran molts més errors, simplement per la naturalesa heurística dels algorismes de MSA. Diversos visors d'alineaments múltiples de seqüència permeten una revisió visual dels alineaments, normalment inspeccionant la qualitat de l'alineament de llocs funcionals anotats en dues o més seqüències. Molts també permeten editar l'alineament per corregir aquests errors (generalment menors) amb l'objectiu d'obtenir un alineament òptim acurat, adequat per l'ús en anàlisis filogenètiques o models comparatius.
Malgrat això, a mesura que augmenta el nombre de seqüències i especialment en els estudis d'associació del genòma sencer (o en anglès, Genome-wide association study, GWAS) que inclouen diversos MSA és impossible polir els alineaments manualment (a més que és una tècnica subjectiva). Finalment, ni tan sols el millor expert podria alinear els casos més ambigus amb una mínima seguretat. En aquests casos és comú utilitzar procediments automàtics per excloure les regions que no s'alineen de manera fiable. En el cas de l'anàlisi filogenètic, el programa Gblocks és molt usat per eliminar blocs d'alineaments dels quals se sospita una qualitat baixa. Aquest criteri podria ser un filtre excessiu per regions que contenen esdeveniments d'insercions/delecions alineats adequadament, fet que ens evitaria la detecció d'aquestes zones amb selecció positiva. Uns quants algorismes d'alineament generen puntuacions específiques del lloc que permeten seleccionar regions d'alta confiança, servei ofert per primer cop pel programa SOAP, que avalua la robustesa de cada columna a la pertorbació amb els paràmetres del CLUSTALW. El programa T-Coffee utilitza una llibreria d'alineaments i la puntuació final està acolorida d'acord amb la confiança entre els diferents residus. TCS (Transitive Consistency Score) utilitza les llibreries dels alineaments parells de T-Coffee per avaluar qualsevol MSA. Les projeccions per parells poden produir-se utilitzant mètodes ràpids o lents, permetent així una compensació entre velocitat i precisió. Un altre programa que pot donar un alineament final amb puntuacions de confiança és FSA (Fast Statistical Alignment), que utilitza un model estadístic que permet calcular la incertesa de l'alineament. La puntuació HoT (Heads-Or-Tails o "caps i cues") pot fer-se servir com una mida d'incertesa d'un alineament específic de lloc degut a l'existència de diverses solucions co-òptimes. El programa GUIDANCE calcula una mesura de confiança similar específica de lloc, basada en la robustesa de l'alineament a la incertesa de l'arbre guia (alineaments progressius). Una alternativa amb més estadística per avaluar la incertesa és l'ús de models evolutius probabilístics per a l'estimació conjunta de filogènia i alineament. Una aproximació Bayesiana permet calcular les probabilitats posteriors de filogènia i alineació estimades, la qual és una mesura de la confiança d'aquestes estimacions. En aquest cas, la probabilitat posterior pot ser calculada per cada posició de l'alineament i que s'ha implementat al programa BAli-Phy. Hi ha diversos programes gratuïts per la visualització d'alineaments múltiples de seqüència, per exemple Jalview and UGENE.

## Usos en filogenètica

Els alineaments de múltiples seqüències es poden fer servir per a crear arbres filogenètics. Això ha estat possible per dos motius. El primer és el fet que els dominis funcionals que ja són coneguts i tenen les seves seqüències anotades es poden fer servir per fer alineaments de seqüències que encara no estan anotades. L'altra raó és que les regions conservades que se sap que són importants funcionalment es poden trobar. Això fa possible que els alineaments de múltiples seqüències es puguin utilitzar per analitzar i trobar relacions evolutives a través de l'homologia de les seqüències. D'aquesta manera tant mutacions puntuals, com delecions o insercions es poden detectar.
Els alineaments de múltiples seqüències també es poden fer servir per identificar posicions o llocs funcionals importants, com ara llocs d'unió, llocs actius, o corresponents a altres funcions importants, mitjançant la localització dels dominis conservats. Quan s'analitza un MSA i es comparen les seqüències, és important parar atenció i considerar diversos aspectes de les seqüències. Aquests aspectes inclouen el percentatge d'identitat, similitud, i homologia. La identitat implica que les seqüències tenen residus idèntics a la seva respectiva posició. D'altra banda, la similitud es refereix a la comparació de les seqüències en termes de contingut quantitatiu de residus similars. Per exemple, en el cas de les seqüències nucleotídiques, les pirimidines es consideren similars entre elles i el mateix succeeix amb les purines. La similitud s'acaba podent relacionar amb l'homologia, de manera que les seqüències més similars són les que tenen una major probabilitat de ser homòlogues. Per tant, l'anàlisi de la similitud pot servir per a trobar un avantpassat comú.

## Referències

* ↑ Guigó Serra, Roderic «Biologia i computació». Treballs de la Societat Catalana de Biologia, 63, 2012, pàg. 183–198. DOI: 10.2436/20.1501.02.118. ISSN: 2013-9802.
* ↑ Thompson, Julie D.; Linard, Benjamin; Lecompte, Odile; Poch, Olivier «A Comprehensive Benchmark Study of Multiple Sequence Alignment Methods: Current Challenges and Future Perspectives» (en anglès). PLoS ONE, 6, 3, 31-03-2011, pàg. e18093. DOI: 10.1371/journal.pone.0018093. ISSN: 1932-6203. PMC: PMC3069049. PMID: 21483869.
* 1 2 Pervez, Muhammad Tariq; Babar, Masroor Ellahi; Nadeem, Asif; Aslam, Muhammad; Awan, Ali Raza «Evaluating the Accuracy and Efficiency of Multiple Sequence Alignment Methods» (en anglès). Evolutionary Bioinformatics, 10, 1-2014, pàg. EBO.S19199. DOI: 10.4137/EBO.S19199. ISSN: 1176-9343. PMC: PMC4267518. PMID: 25574120.
* ↑ «Help With Matrices Used In Sequence Comparison Tools | Help | EBI», 11-03-2010. Arxivat de l'original el 2010-03-11. [Consulta: 19 desembre 2020].
* ↑ Wang, Lusheng; Jiang, Tao «On the Complexity of Multiple Sequence Alignment». Journal of Computational Biology, 1, 4, 01-01-1994, pàg. 337–348. DOI: 10.1089/cmb.1994.1.337.
* ↑ Just, Winfried «Computational Complexity of Multiple Sequence Alignment with SP-Score». Journal of Computational Biology, 8, 6, 01-11-2001, pàg. 615–623. DOI: 10.1089/106652701753307511.
* ↑ Elias, Isaac «Settling the Intractability of Multiple Alignment». Journal of Computational Biology, 13, 7, 01-09-2006, pàg. 1323–1339. DOI: 10.1089/cmb.2006.13.1323.
* ↑ Carrillo, Humberto; Lipman, David «The Multiple Sequence Alignment Problem in Biology». SIAM Journal on Applied Mathematics, 48, 5, 01-10-1988, pàg. 1073–1082. DOI: 10.1137/0148063. ISSN: 0036-1399.
* ↑ Lipman, D. J.; Altschul, S. F.; Kececioglu, J. D. «A tool for multiple sequence alignment» (en anglès). Proceedings of the National Academy of Sciences, 86, 12, 01-06-1989, pàg. 4412–4415. DOI: 10.1073/pnas.86.12.4412. ISSN: 0027-8424. PMC: PMC287279. PMID: 2734293.
* ↑ Feng, Da-Fei; Doolittle, Russell F. «Progressive sequence alignment as a prerequisitetto correct phylogenetic trees» (en anglès). Journal of Molecular Evolution, 25, 4, 01-08-1987, pàg. 351–360. DOI: 10.1007/BF02603120. ISSN: 1432-1432.
* 1 2 3 4 5 6 7 Gollery, Martin «Bioinformatics: Sequence and Genome Analysis, 2nd ed. David W. Mount. Cold Spring Harbor, NY: Cold Spring Harbor Laboratory Press, 2004, 692 pp., $75.00, paperback. ISBN 0-87969-712-1.». Clinical Chemistry, 51, 11, 01-11-2005, pàg. 2219–2219. DOI: 10.1373/clinchem.2005.053850. ISSN: 0009-9147.
* ↑ Higgins DG, Sharp PM. (1988). CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. Gene 73(1):237-44.
* 1 2 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.
* ↑ Sievers, Fabian; Higgins, Desmond G. «Clustal Omega for making accurate alignments of many protein sequences» (en anglès). Protein Science, 27, 1, 2018, pàg. 135–145. DOI: 10.1002/pro.3290. ISSN: 1469-896X. PMC: PMC5734385. PMID: 28884485.
* 1 2 Sievers, Fabian; Wilm, Andreas; Dineen, David; Gibson, Toby J; Karplus, Kevin «Fast, scalable generation of high‐quality protein multiple sequence alignments using Clustal Omega» (en anglès). Molecular Systems Biology, 7, 1, 1-2011, pàg. 539. DOI: 10.1038/msb.2011.75. ISSN: 1744-4292. PMC: PMC3261699. PMID: 21988835.
* 1 2 Notredame, Cédric; Higgins, Desmond G; Heringa, Jaap «T-coffee: a novel method for fast and accurate multiple sequence alignment11Edited by J. Thornton» (en anglès). Journal of Molecular Biology, 302, 1, 08-09-2000, pàg. 205–217. DOI: 10.1006/jmbi.2000.4042. ISSN: 0022-2836.
* ↑ Sze, Sing-Hoi; Lu, Yue; Yang, Qingwu «A Polynomial Time Solvable Formulation of Multiple Sequence Alignment». Journal of Computational Biology, 13, 2, 01-03-2006, pàg. 309–319. DOI: 10.1089/cmb.2006.13.309.
* 1 2 Gotoh, Osamu «Significant Improvement in Accuracy of Multiple Protein Sequence Alignments by Iterative Refinement as Assessed by Reference to Structural Alignments» (en anglès). Journal of Molecular Biology, 264, 4, 13-12-1996, pàg. 823–838. DOI: 10.1006/jmbi.1996.0679. ISSN: 0022-2836.
* 1 2 3 Brudno, Michael; Chapman, Michael; Göttgens, Berthold; Batzoglou, Serafim; Morgenstern, Burkhard «Fast and sensitive multiple alignment of large genomic sequences». BMC Bioinformatics, 4, 1, 23-12-2003, pàg. 66. DOI: 10.1186/1471-2105-4-66. ISSN: 1471-2105. PMC: PMC521198. PMID: 14693042.
* 1 2 Edgar, R. C. «MUSCLE: multiple sequence alignment with high accuracy and high throughput». Nucleic Acids Research, 32, 5, 08-03-2004, pàg. 1792–1797. DOI: 10.1093/nar/gkh340. ISSN: 1362-4962. PMC: PMC390337. PMID: 15034147.
* ↑ Collingridge, Peter W.; Kelly, Steven «MergeAlign: improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignments». BMC Bioinformatics, 13, 1, 30-05-2012, pàg. 117. DOI: 10.1186/1471-2105-13-117. ISSN: 1471-2105. PMC: PMC3413523. PMID: 22646090.
* ↑ Hughey, Richard; Krogh, Anders «Hidden Markov models for sequence analysis: extension and analysis of the basic method». Bioinformatics, 12, 2, 1996, pàg. 95–107. DOI: 10.1093/bioinformatics/12.2.95. ISSN: 1367-4803.
* ↑ Grasso, C.; Lee, C. «Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems». Bioinformatics, 20, 10, 12-02-2004, pàg. 1546–1556. DOI: 10.1093/bioinformatics/bth126. ISSN: 1367-4803.
* ↑ Hughey R, Krogh A. SAM: Sequence alignment and modeling software system. Technical Report UCSC-CRL-96-22, University of California, Santa Cruz, CA, September 1996
* ↑ Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.
* ↑ Loytynoja, A.; Goldman, N. «From The Cover: An algorithm for progressive multiple alignment of sequences with insertions» (en anglès). Proceedings of the National Academy of Sciences, 102, 30, 06-07-2005, pàg. 10557–10562. DOI: 10.1073/pnas.0409137102. ISSN: 0027-8424. PMC: PMC1180752. PMID: 16000407.
* ↑ Löytynoja, Ari; Goldman, Nick «Phylogeny-Aware Gap Placement Prevents Errors in Sequence Alignment and Evolutionary Analysis» (en anglès). Science, 320, 5883, 20-06-2008, pàg. 1632–1635. DOI: 10.1126/science.1158395. ISSN: 0036-8075. PMID: 18566285.
* ↑ Löytynoja, Ari; Vilella, Albert J.; Goldman, Nick «Accurate extension of multiple sequence alignments using a phylogeny-aware graph algorithm». Bioinformatics, 28, 13, 23-04-2012, pàg. 1684–1691. DOI: 10.1093/bioinformatics/bts198. ISSN: 1460-2059. PMC: PMC3381962. PMID: 22531217.
* ↑ Szalkowski, Adam M. «Fast and robust multiple sequence alignment with phylogeny-aware gap placement». BMC Bioinformatics, 13, 1, 13-06-2012, pàg. 129. DOI: 10.1186/1471-2105-13-129. ISSN: 1471-2105. PMC: PMC3495709. PMID: 22694311.
* ↑ Henikoff, Steven; Henikoff, Jorja G. «Automated assembly of protein blocks for database searching». Nucleic Acids Research, 19, 23, 1991, pàg. 6565–6572. DOI: 10.1093/nar/19.23.6565. ISSN: 0305-1048. PMC: PMC329220. PMID: 1754394.
* ↑ Bailey TL, Elkan C (1994). "Fitting a mixture model by expectation maximization to discover motifs in biopolymers". Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology. Menlo Park, California: AAAI Press. pp. 28–36.
* ↑ Bailey, T. L.; Gribskov, M. «Combining evidence using p-values: application to sequence homology searches». Bioinformatics, 14, 1, 01-02-1998, pàg. 48–54. DOI: 10.1093/bioinformatics/14.1.48. ISSN: 1367-4803.
* ↑ Salama, R. A.; Stekel, D. J. «A non-independent energy-based multiple sequence alignment improves prediction of transcription factor binding sites». Bioinformatics, 29, 21, 28-08-2013, pàg. 2699–2704. DOI: 10.1093/bioinformatics/btt463. ISSN: 1367-4803.
* 1 2 Redelings, Benjamin D.; Suchard, Marc A. «Joint Bayesian Estimation of Alignment and Phylogeny». Systematic Biology, 54, 3, 01-06-2005, pàg. 401–418. DOI: 10.1080/10635150590947041. ISSN: 1076-836X.
* 1 2 Okonechnikov, Konstantin; Golosova, Olga; Fursov, Mikhail «Unipro UGENE: a unified bioinformatics toolkit» (en anglès). Bioinformatics, 28, 8, 4-2012, pàg. 1166–1167. DOI: 10.1093/bioinformatics/bts091. ISSN: 1367-4803.
* ↑ Notredame, C «SAGA: sequence alignment by genetic algorithm». Nucleic Acids Research, 24, 8, 15-04-1996, pàg. 1515–1524. DOI: 10.1093/nar/24.8.1515. PMC: PMC145823. PMID: 8628686.
* ↑ Notredame, C «RAGA: RNA sequence alignment by genetic algorithm». Nucleic Acids Research, 25, 22, 15-11-1997, pàg. 4570–4580. DOI: 10.1093/nar/25.22.4570. PMC: PMC147093. PMID: 9358168.
* ↑ Kim, Jin; Pramanik, Sakti; Chung, Moon Jung «Multiple sequence alignment using simulated annealing» (en anglès). Bioinformatics, 10, 4, 1994, pàg. 419–426. DOI: 10.1093/bioinformatics/10.4.419. ISSN: 1367-4803.
* ↑ Althaus, Ernst; Caprara, Alberto; Lenhof, Hans-Peter; Reinert, Knut «A branch-and-cut algorithm for multiple sequence alignment» (en anglès). Mathematical Programming, 105, 2-3, 2-2006, pàg. 387–425. DOI: 10.1007/s10107-005-0659-3. ISSN: 0025-5610.
* ↑ Hosseininasab, Amin; van Hoeve, Willem-Jan «Exact Multiple Sequence Alignment by Synchronized Decision Diagrams» (en anglès). INFORMS Journal on Computing, 08-09-2020, pàg. ijoc.2019.0937. DOI: 10.1287/ijoc.2019.0937. ISSN: 1091-9856.
* ↑ «D-Wave Initiates Open Quantum Software Environment 11 January 201». Arxivat de l'original el 2021-01-21. [Consulta: 20 desembre 2020].
* ↑ Nuin, Paulo AS; Wang, Zhouzhi; Tillier, Elisabeth RM «The accuracy of several multiple sequence alignment programs for proteins». BMC Bioinformatics, 7, 1, 2006, pàg. 471. DOI: 10.1186/1471-2105-7-471. PMC: PMC1633746. PMID: 17062146.
* ↑ «Manual Editing and Adjustment of MSAs (Multiple Sequence Alignments)», 24-09-2015. Arxivat de l'original el 2015-09-24. [Consulta: 20 desembre 2020].
* ↑ Castresana, J. «Selection of Conserved Blocks from Multiple Alignments for Their Use in Phylogenetic Analysis» (en anglès). Molecular Biology and Evolution, 17, 4, 01-04-2000, pàg. 540–552. DOI: 10.1093/oxfordjournals.molbev.a026334. ISSN: 1537-1719.
* ↑ Loytynoja, A.; Milinkovitch, M. C. «SOAP, cleaning multiple alignments from unstable blocks» (en anglès). Bioinformatics, 17, 6, 01-06-2001, pàg. 573–574. DOI: 10.1093/bioinformatics/17.6.573. ISSN: 1367-4803.
* ↑ Poirot, O. «Tcoffee@igs: a web server for computing, evaluating and combining multiple sequence alignments» (en anglès). Nucleic Acids Research, 31, 13, 01-07-2003, pàg. 3503–3506. DOI: 10.1093/nar/gkg522. ISSN: 1362-4962.
* ↑ Chang, Jia-Ming; Di Tommaso, Paolo; Notredame, Cedric «TCS: A New Multiple Sequence Alignment Reliability Measure to Estimate Alignment Accuracy and Improve Phylogenetic Tree Reconstruction» (en anglès). Molecular Biology and Evolution, 31, 6, 6-2014, pàg. 1625–1637. DOI: 10.1093/molbev/msu117. ISSN: 1537-1719.
* ↑ Chang, Jia-Ming; Di Tommaso, Paolo; Lefort, Vincent; Gascuel, Olivier; Notredame, Cedric «TCS: a web server for multiple sequence alignment evaluation and phylogenetic reconstruction: Figure 1.» (en anglès). Nucleic Acids Research, 43, W1, 01-07-2015, pàg. W3–W6. DOI: 10.1093/nar/gkv310. ISSN: 0305-1048. PMC: PMC4489230. PMID: 25855806.
* ↑ Bradley, Robert K.; Roberts, Adam; Smoot, Michael; Juvekar, Sudeep; Do, Jaeyoung «Fast Statistical Alignment» (en anglès). PLoS Computational Biology, 5, 5, 29-05-2009, pàg. e1000392. DOI: 10.1371/journal.pcbi.1000392. ISSN: 1553-7358.
* ↑ Pacific Symposium on Biocomputing 2008 : Kohala Coast, Hawaii, USA, 4-8 January 2008. Hackensack, N.J.: World Scientific, 2008, p. 15-24. ISBN 978-981-277-613-6.
* ↑ «What is Jalview ? | jalview.org» (en anglès). [Consulta: 20 desembre 2020].
* 1 2 Kapli, Paschalia; Yang, Ziheng; Telford, Maximilian J. «Phylogenetic tree building in the genomic age» (en anglès). Nature Reviews Genetics, 21, 7, 7-2020, pàg. 428–444. DOI: 10.1038/s41576-020-0233-0. ISSN: 1471-0064.
* 1 2 Phillips, Aloysius; Janies, Daniel; Wheeler, Ward «Multiple Sequence Alignment in Phylogenetic Analysis» (en anglès). Molecular Phylogenetics and Evolution, 16, 3, 01-09-2000, pàg. 317–330. DOI: 10.1006/mpev.2000.0785. ISSN: 1055-7903.

## Vegeu també

* Alineament de seqüències
* Bioinformàtica
* Cladística
* Filogenetica computacional

### Artícles de consulta

* Duret, L.; S. Abdeddaim (2000). "Multiple alignment for structural functional or phylogenetic analyses of homologous sequences". In D. Higgins and W. Taylor (ed.). Bioinformatics sequence structure and databanks. Oxford: Oxford University Press.
* Notredame, C. (2002). "Recent progresses in multiple sequence alignment: a survey". Pharmacogenomics. 3 (1): 131–144. doi:10.1517/14622416.3.1.131. PMID 11966409.
* Thompson, J. D.; Plewniak, F.; Poch, O. (1999). "A comprehensive comparison of multiple sequence alignment programs". Nucleic Acids Research. 27 (13): 12682–2690. doi:10.1093/nar/27.13.2682. PMC 148477. PMID 10373585.
* Wallace, I.M.; Blackshields, G.; Higgins, D.G. (2005). "Multiple sequence alignments". 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.
* Blanchette M (2007). "Computation and analysis of genomic multi-sequence alignments". Annu Rev Genomics Hum Genet. 8: 193–213. PMID: 17489682 DOI: 10.1146/annurev.genom.8.080706.092300.
* Chowdhury B, Garai G (2017). "A review on multiple sequence alignment from the perspective of genetic algorithm". 109(5-6):419-431. doi::10.1016/j.ygeno.2017.06.007. PMID: 28669847.

## Enllaços externs

* Eines d'alineament de seqüències ExPASy Arxivat 2010-04-13 a Wayback Machine.
* Recursos per alineaments múltiples, de la Virtual School of Natural Science
* Eines per alineaments múltiples, de Pôle Bioinformatique Lyonnais
* Punt d'entrada als principals servidors T-Coffee
* Servidors de l'EBI (European Bioinformatics Institute)