Alinierea secvenței multiple ( în engleză alinierea secvenței multiple, MSA ) - alinierea a trei sau mai multe secvențe biologice, de obicei proteine , ADN sau ARN . În cele mai multe cazuri, se presupune că setul de secvențe de intrare are o relație evolutivă . Folosind aliniamente multiple, originea evolutivă a secvențelor poate fi evaluată prin analiză filogenetică .
Reprezentarea vizuală a alinierii ilustrează evenimentele de mutație ca mutații punctuale (modificări într-un aminoacid sau o nucleotidă ) ca caractere distincte într-o coloană de aliniere, precum și inserțiile și ștergerile acestora (reprezentate printr-o cratimă , goluri).
Aliniamentele de secvențe multiple sunt adesea folosite pentru a evalua conservarea domeniilor proteice , a structurilor terțiare și secundare și chiar a resturilor individuale de aminoacizi sau a nucleotidelor.
Datorită complexității computaționale mai mari în comparație cu alinierea pe perechi, alinierea multiplă necesită algoritmi mai complexi. Multe programe înrudite folosesc algoritmi euristici , deoarece găsirea unei alinieri optime globale pentru multe secvențe poate consuma foarte mult timp.
Pentru a construi o aliniere globală optimă, programarea dinamică este utilizată direct . Pentru secvențele de proteine, există două seturi de parametri: penalizarea decalajului și matricea de substituție, care conține probabilitățile de potrivire a unei perechi de resturi de aminoacizi pe baza similitudinii proprietăților lor chimice și a probabilității evolutive de mutație. Pentru secvențele de nucleotide, se folosește și penalizarea gap-ului, dar matricea de substituție este mult mai simplă, ia în considerare doar potriviri complete de nucleotide sau nepotriviri, adică nepotriviri complete [1] .
Pentru n secvențe individuale, metoda naivă necesită construirea echivalentului n-dimensional al matricei care este utilizată pentru alinierea pe perechi. Pe măsură ce n crește, spațiul de căutare crește exponențial . Astfel, algoritmul naiv are complexitate de calcul O(Lungimea secvenţelor Nsecvenţe ). Găsirea optimului global pentru n secvențe este o problemă NP-completă [2] [3] [4] .
În 1989, pe baza algoritmului Carrillo-Lipman [5] , Altschul a introdus o abordare practică care folosea aliniamente perechi pentru a limita spațiul de căutare n-dimensional [6] . Cu această abordare, programarea dinamică este efectuată pe fiecare pereche de secvențe din setul de intrare și este căutată doar regiunea situată în apropierea intersecției n-dimensionale a acestor căi. Programul optimizează suma tuturor perechilor de caractere la fiecare poziție din aliniament (suma greutăților perechilor) [7]
O abordare larg utilizată este alinierea progresivă folosind un algoritm euristic dezvoltat de Paulien Hogeweg și Ben Hesper în 1984 [8] . Toate metodele de aliniere progresivă au doi pași importanți: construirea unui arbore binar (arborele de cale) în care frunzele sunt secvențe și construirea unui aliniament multiplu prin adăugarea de secvențe la alinierea în creștere conform arborelui de cale. Arborele de căi în sine poate fi construit prin metode de grupare precum UPGMA și îmbinarea vecinilor [9] .
Alinierea progresivă nu garantează o aliniere optimă globală. Problema este că erorile generate în orice etapă a alinierii multiple în creștere ajung în alinierea finală. În plus, alinierea poate fi deosebit de proastă în cazul unui set de secvențe care sunt foarte îndepărtate unele de altele. Majoritatea metodelor moderne progresive au o funcție de ponderare modificată cu o funcție de ponderare secundară care atribuie coeficienți elementelor individuale ale setului de date într-un mod neliniar pe baza distanței lor filogenetice față de cei mai apropiați vecini [9] .
Metodele de aliniere progresivă sunt suficient de eficiente pentru a fi aplicate unui număr mare (100-1000) de secvențe. Cea mai populară metodă de aliniere progresivă aparține familiei Clustal [10] , în special, varianta ponderată ClustalW [11] , care poate fi accesată prin portaluri precum GenomeNet , EBI , EMBNet Arhivat 1 mai 2011 la Wayback Machine . ClustalW este utilizat în mod activ pentru construirea arborilor filogenetici, în ciuda avertismentelor autorului că aliniamentele necontrolate de mână nu ar trebui utilizate nici în construirea arborilor, nici ca intrare pentru predicția structurii proteinelor . Versiunea actuală a Clustal este Clustal Omega, care funcționează pe baza arborilor de cale și a metodelor de profil HMM pentru alinierea proteinelor. Sunt propuse, de asemenea, diverse instrumente pentru construirea de aliniamente progresive ale secvențelor de ADN. Unul dintre ele este MAFFT ( Multiple Alignment using Fast Fourier Transform ) [12] .
O altă metodă comună de aliniere progresivă, T-Coffee [13] , este mai lentă decât Clustal și derivații săi, dar în general produce aliniamente mai precise pentru secvențele înrudite la distanță. T-Coffee construiește o bibliotecă de aliniamente pereche, pe care apoi le folosește pentru a construi mai multe aliniamente.
Deoarece metodele progresive sunt euristice, nu se garantează că vor converge către un optim global; calitatea alinierii și semnificația sa biologică pot fi dificil de evaluat. O metodă semi-progresivă care îmbunătățește calitatea alinierii și nu utilizează euristica cu pierderi este realizată în timp polinomial ( PSAlign Arhivat la 18 iulie 2011 la Wayback Machine ) [14] .
Un set de metode pentru construirea de aliniamente multiple care reduc erorile moștenite în metodele progresive sunt clasificate drept „ iterative ”. Ele funcționează în mod similar cu metodele progresive, dar rearanjează în mod repetat aliniamentele originale pe măsură ce se adaugă secvențe noi. Metodele progresive depind în mare măsură de calitatea aliniamentelor inițiale, deoarece acestea vor ajunge în rezultatul final neschimbate și, prin urmare, cu erori. Cu alte cuvinte, dacă secvența este deja aliniată, poziția sa ulterioară nu se va schimba. Această aproximare îmbunătățește eficiența, dar afectează negativ acuratețea rezultatului. Spre deosebire de metodele progresive, metodele iterative pot reveni la aliniamentele perechi calculate inițial și sub-aliniamentele care conțin subseturi de secvențe din interogare și, astfel, optimizează funcția obiectivă generală și îmbunătățesc calitatea [9] .
Există o mare varietate de metode iterative. De exemplu, PRRN/PRRP utilizează un algoritm de urcare a vârfurilor pentru a optimiza greutatea aliniamentelor multiple [15] și ajustează în mod iterativ greutățile de aliniere și aria multi-gap [9] . PRRP funcționează mai eficient atunci când îmbunătățește alinierea construită anterior prin metoda rapidă [9] .
Un alt program iterativ, DIALIGN, adoptă o abordare neobișnuită, concentrându-se pe aliniamentele locale ale subsegmentelor sau motivelor secvenței fără a introduce o penalizare de decalaj [16] . Alinierea motivelor individuale este prezentată într-o formă de matrice, similară cu un dot-plot în aliniere pereche. O metodă alternativă care utilizează aliniamente locale rapide ca puncte de ancorare pentru o procedură de construcție a aliniamentului global mai lentă este furnizată în software-ul CHAOS/DIALIGN [16] .
A treia metodă iterativă populară se numește MUSCLE. Este o îmbunătățire față de metodele progresive deoarece utilizează distanțe mai precise pentru a estima relația dintre două secvențe [17] . Distanțele sunt actualizate între iterații (deși MUSCLE conținea inițial doar 2-3 iterații).
Metodele de consens încearcă să selecteze alinierea multiplă optimă din diferite aliniamente multiple ale aceluiași set de date de intrare. Există două cele mai comune metode de consens: M-COFFEE și MergeAlign [18] . M-COFFEE folosește aliniamente multiple generate de 7 metode diferite pentru a obține aliniamente de consens. MergeAlign este capabil să genereze aliniamente de consens din orice număr de aliniamente de intrare derivate din diferite modele de evoluție a secvenței și metode de construcție. Opțiunea implicită pentru MergeAlign este de a obține o aliniere de consens folosind aliniamente derivate din 91 de modele diferite de evoluție a secvenței proteinelor.
Modelele Markov ascunse (HMM) sunt modele probabilistice care pot evalua probabilitatea pentru toate combinațiile posibile de lacune, potriviri sau nepotriviri pentru a determina cea mai probabilă aliniere multiplă sau setul acestora. HMM-urile pot produce o singură aliniere cu pondere mare, dar pot genera și o familie de aliniamente posibile, care pot fi apoi evaluate pentru semnificația lor biologică. HMM-urile pot fi folosite pentru a obține atât aliniamente globale, cât și locale. Deși metodele bazate pe HMM sunt relativ recente, ele s-au dovedit a fi metode cu îmbunătățiri semnificative în complexitatea computațională, în special pentru secvențele care conțin regiuni suprapuse [9] .
Metodele standard bazate pe HMM reprezintă alinierea multiplă sub forma unui graf aciclic direcționat , cunoscut sub numele de graf de ordine parțială, care constă dintr-o serie de noduri reprezentând stările posibile în coloanele de aliniere. În această reprezentare, o coloană perfect conservatoare (adică secvențele dintr-o aliniere multiplă au un caracter particular în acea poziție) este codificată ca un singur nod cu multe conexiuni de ieșire cu caractere posibile în următoarea poziție de aliniere. În ceea ce privește modelul standard Hidden Markov, stările observate sunt coloane individuale de aliniere, iar stările „ascunse” reprezintă o secvență ancestrală presupusă din care secvențele din setul de intrare ar fi putut coborî. O tehnică eficientă de programare dinamică, algoritmul Viterbi , este utilizată pe scară largă pentru a obține o aliniere bună [19] . Diferă de metodele progresive prin faptul că alinierea primelor secvențe este rearanjată pe măsură ce se adaugă fiecare nouă secvență. Totuși, ca și metodele progresive, acest algoritm poate fi afectat de ordinea în care secvențele din setul de intrare intră în aliniament, mai ales în cazul secvențelor cuplate lax din punct de vedere evolutiv [9] .
Deși metodele HMM sunt mai complexe decât metodele progresive utilizate în mod obișnuit, există mai multe programe pentru obținerea aliniamentelor, cum ar fi POA [20] , precum și o metodă similară, dar mai generală în pachetele SAM [21] și HMMER [22] . SAM este utilizat pentru a obține aliniamente pentru predicția structurii proteinelor în experimentul CASP pentru proteinele de drojdie . Căutarea HH, bazată pe compararea perechi a HMM-urilor, este utilizată pentru a căuta secvențe înrudite la distanță. Serverul care rulează HHsearch (HHpred) a fost cel mai rapid dintre primele 10 servere automate pentru predicția structurii proteinelor în CASP7 și CASP8 [23] .
Tehnicile standard de optimizare în informatică, care permit modelarea, dar nu reproducerea directă a procesului fizic, sunt, de asemenea, utilizate pentru a construi mai multe aliniamente mai eficient. O astfel de tehnică, algoritmul genetic , a fost folosită pentru a construi o aliniere a secvenței multiple bazată pe un proces evolutiv ipotetic care a furnizat divergența secvenței. Această metodă funcționează prin împărțirea unei serii de posibile MSA-uri în bucăți și rearanjarea acelor bucăți din nou, introducând pauze în diferite poziții. Funcția principală a obiectivului este optimizată în timpul acestui proces, de obicei prin maximizarea „sumelor de perechi” folosind metode de programare dinamică. Această metodă este implementată pentru secvențele de proteine în software-ul SAGA ( Sequence Alignment by Genetic Algorithm ) [ 24] și pentru secvențele de ARN din RAGA [25] .
Folosind metoda de recoacere prin simulare , un aliniament multiplu existent construit printr-o metodă diferită este rafinat într-o serie de rearanjamente pentru a găsi zone de aliniere mai bune decât era înainte. Ca și în cazul algoritmului genetic, simularea de recoacere maximizează funcția obiectiv în funcție de sumele perechilor. Simularea de recoacere folosește un „factor de temperatură” condiționat care determină nivelul de rearanjare care apar și nivelul de probabilitate al fiecărei rearanjamente. Este tipic să se utilizeze perioade alternante de realiniere mare și probabilitate scăzută (pentru a găsi regiunile cele mai exterioare din aliniament) cu perioade de realiniere scăzută și probabilitate mare pentru a examina mai atent minimele locale în apropierea coloanelor noi de aliniere. Această abordare a fost implementată în programul MSASA ( Multiple Sequence Alignment by Simulated Annealing ) [26] .
Majoritatea metodelor de aliniere multiple încearcă să minimizeze numărul de inserții/ștergeri (goluri), ceea ce are ca rezultat aliniamente compacte. Această abordare poate duce la erori de aliniere dacă secvențele aliniate au conținut regiuni non-omolog și dacă golurile sunt informative în analiza filogenetică. Aceste probleme sunt frecvente în secvențele noi care sunt prost adnotate și pot conține deplasări de cadre , domenii greșite sau exoni îmbinați neomologi .
Prima metodă bazată pe analiza filogeniei a fost dezvoltată de Loitinoge și Goldman în 2005 [27] . În 2008, aceiași autori au lansat software-ul corespunzător - PRANK [28] . PRANK îmbunătățește aliniamentele atunci când există inserții. Cu toate acestea, este mai lent decât metodele progresive și/sau iterative [29] care au fost dezvoltate cu ani înainte.
În 2012 au apărut două noi metode bazate pe analiză filogenetică. Primul, numit PAGAN, a fost dezvoltat de echipa PRANK, iar al doilea, numit ProGraphMSA, a fost dezvoltat de Zhalkovsky [30] . Software-urile lor au fost dezvoltate independent, dar au caracteristici comune: ambele folosesc algoritmi grafici pentru a îmbunătăți recunoașterea regiunilor neomologe, iar îmbunătățirile codului le fac mai rapide decât PRANK .
Căutarea de motive, sau altfel profilarea, este o metodă de găsire a locației unui motiv într-o aliniere multiplă globală ca mijloc de obținere a celui mai bun MSA și a greutății medii a matricei rezultate pentru a o utiliza pentru a căuta alte secvențe cu similare. motive. Au fost dezvoltate multe metode pentru a determina motive, dar toate se bazează pe găsirea de modele scurte, foarte conservate, într-un model de aliniere mai mare și construirea unei matrice similare cu o matrice de substituție. Această matrice reflectă compoziția de nucleotide sau aminoacizi pentru fiecare poziție din motivul presupus. Alinierea poate fi apoi rafinată folosind aceste matrici. În analiza profilului standard, această matrice include intrări atât pentru fiecare simbol posibil, cât și pentru decalajul [9] . În schimb, algoritmul de căutare a modelelor statistice caută mai întâi motivele și apoi folosește motivele găsite pentru a construi un aliniament multiplu. În multe cazuri, atunci când setul inițial de secvențe conține un număr mic de secvențe sau numai secvențe foarte înrudite, pseudo -contoare sunt adăugate pentru a normaliza distribuția reflectată în matricea de ponderi. În special, ajută la evitarea zerourilor în matricea probabilităților pentru a nu obține valoarea infinitului în matricea ponderii poziționale .
Analiza blocurilor este o metodă de căutare a motivelor efectuată în regiuni de aliniere fără goluri. Blocurile pot fi generate din aliniamente multiple sau derivate din secvențe nealiniate prin precalcularea mai multor motive comune din familii de gene cunoscute [31] . Estimarea blocurilor se bazează de obicei pe un spațiu de simboluri de înaltă frecvență, mai degrabă decât pe un calcul explicit al matricelor de înlocuire. Serverul BLOCKS oferă o metodă alternativă pentru localizarea unor astfel de motive în secvențe nealiniate.
Potrivirea modelelor statistice este realizată utilizând maximizarea așteptărilor și algoritmul de eșantionare Gibbs . Pentru a căuta motive, serverul cel mai des folosit este MEME , care folosește algoritmul de maximizare a așteptărilor și metoda modelelor Markov ascunse, precum și MEME/MAST [32] [33] , care folosește suplimentar algoritmul MAST.
Unele regiuni ale ADN-ului care nu codifică proteine, în special situsurile de legare a factorului de transcripție (TFBS), sunt mai conservate și nu neapărat legate evolutiv, deoarece aceste situsuri pot apărea în secvențe non-omolog. Astfel, ipotezele utilizate pentru a alinia secvențele de proteine și regiunile care codifică ADN nu sunt adecvate pentru secvențele de situsuri de legare a factorului de transcripție. Deși are sens să se alinieze regiunile de ADN care codifică proteine pentru secvențe omoloage folosind operatori de mutație, alinierea secvențelor site-ului de legare pentru același factor de transcripție nu se poate baza pe operațiuni de mutație legate evolutiv. În mod similar, operatorul de mutație punctuală evolutivă poate fi utilizat pentru a determina distanța de editare pentru secvențele de codificare, dar este de puțin folos pentru secvențele site-ului de legare a factorului de transcripție datorită faptului că orice modificare a secvenței trebuie să păstreze un anumit nivel de specificitate pentru a îndeplini funcția de legare. Acest lucru devine deosebit de important atunci când alinierea secvenței site-urilor de legare a factorului de transcripție este necesară pentru a construi modele observabile pentru prezicerea loci necunoscuți ai aceluiași TFBS. Prin urmare, metodele de aliniere multiple trebuie ajustate pentru a ține cont de principalele ipoteze evolutive și de a utiliza anumiți operatori, ca în metoda EDNA sensibilă termodinamic pentru a alinia site-urile de legare [34] .
Necesitatea de a utiliza abordări euristice pentru aliniere multiplă duce la faptul că un set de proteine alese în mod arbitrar poate fi aliniat greșit cu o mare probabilitate. De exemplu, evaluarea unor programe de aliniere de vârf folosind benchmark-ul BAliBase [35] a arătat că cel puțin 24% din toate perechile de aminoacizi aliniate sunt nealiniate [36] . Aceste erori pot apărea din cauza inserțiilor unice în una sau mai multe secțiuni ale secvențelor. Ele se pot datora, de asemenea, unui proces evolutiv mai complex, care are ca rezultat proteine care sunt greu de aliniat în secvență, iar pentru o aliniere bună, trebuie să știți altceva, cum ar fi structura. Pe măsură ce numărul de secvențe aliniate crește și divergența lor crește, eroarea crește datorită naturii euristice a algoritmilor de aliniere multiple. Vizualizatoarele de aliniere multiple vă permit să evaluați vizual alinierea des prin verificarea calității alinierii pentru regiunile funcționale adnotate în două sau mai multe secvențe. Multe vizualizatoare vă permit, de asemenea, să editați alinierea prin corectarea erorilor (de obicei de natură minoră) pentru a obține o aliniere curată optimă potrivită pentru utilizarea în analiza filogenetică sau modelarea comparativă [37] .
Cu toate acestea, pe măsură ce numărul de secvențe crește, în special în studiile la nivelul genomului care implică multe aliniamente multiple, devine imposibil să se efectueze manual toate aliniamentele. De asemenea, curatarea manuală este subiectivă. Și, în sfârșit, chiar și cel mai bun expert nu poate alinia cu siguranță multe cazuri ambigue în secvențe extrem de divergente. În astfel de cazuri, este o practică obișnuită să folosiți proceduri automate pentru a elimina regiunile aliniate nesigur de aliniere multiplă. Pentru a obține reconstrucții filogenetice, programul Gblocks este utilizat pe scară largă pentru a elimina blocurile de aliniere cu o calitate presupusă scăzută, în conformitate cu diferitele tăieturi după numărul de secvențe cu goluri în coloanele de aliniere [38] . În același timp, aceste criterii pot filtra excesiv regiunile cu inserții/ștergeri care ar putea fi aliniate în mod fiabil, iar aceste regiuni ar putea fi utile în identificarea selecției pozitive. Puțini algoritmi de aliniere produc o greutate de aliniere specifică locului care ar putea permite selectarea regiunilor foarte conservate. Această posibilitate a fost oferită mai întâi de programul SOAP [39] , care testează rezistența fiecărei coloane la fluctuațiile parametrilor în popularul program de aliniere ClustalW. Programul T-Coffee [39] folosește o bibliotecă de aliniere pentru a genera alinierea multiplă finală și produce o aliniere multiplă colorată conform unui scor de încredere care reflectă corespondența dintre diferitele aliniamente din bibliotecă pentru fiecare dintre reziduurile aliniate. TCS ( Scor de coerență tranzitorie ) este o extensie care utilizează biblioteca de aliniere în perechi T-Coffee pentru a nota fiecare a treia aliniere multiplă . Proiecțiile în perechi pot fi create folosind metode rapide sau lente, astfel încât se poate găsi un compromis între viteza de calcul și precizie [40] [41] . Un alt program de aliniere, FSA ( eng. Fast statistical alignment ), folosește modele statistice pentru a calcula eroarea de aliniere și poate produce o aliniere multiplă cu o estimare a nivelului de fiabilitate a acestuia. Scorul HoT ( Heads-Or-Tails ) poate fi folosit pentru a măsura erorile aliniamentelor specifice site-ului, în care erori pot apărea datorită existenței mai multor soluții co-optime. Programul GUIDANCE [42] calculează o măsură similară de încredere specifică locului pe baza stabilității alinierii la incertitudine în arborele de direcție, care este utilizată, așa cum sa menționat mai sus, în programele de aliniere progresivă. În același timp, o abordare mai solidă din punct de vedere statistic pentru estimarea incertitudinilor de aliniere este utilizarea modelelor evolutive probabilistice pentru a estima în comun filogenia și alinierea. Abordarea bayesiană calculează probabilitățile posterioare ale estimărilor de filogenie și aliniere, care măsoară nivelul de încredere în acele estimări. În acest caz, probabilitatea posterioară poate fi calculată pentru fiecare loc din aliniament. Această abordare este implementată în programul Bali-Phy [43] .
Alinierea secvenței multiple poate fi utilizată pentru a construi un arbore filogenetic [44] . Acest lucru este posibil din două motive. În primul rând, domeniile funcționale cunoscute pentru secvențele adnotate pot fi utilizate pentru a alinia secvențele neadnotate. În al doilea rând, regiunile conservatoare pot avea o semnificație funcțională. Din această cauză, aliniamentele multiple pot fi utilizate pentru a analiza și găsi relații evolutive prin omologie de secvență. Mutațiile punctuale și inserțiile/diviziunile pot fi de asemenea detectate [45] .
Localizarea domeniilor conservate prin aliniere multiplă poate fi utilizată și pentru a identifica site-uri importante din punct de vedere funcțional, cum ar fi site-uri de legare, site-uri de reglementare sau site-uri responsabile pentru alte funcții cheie. Când se analizează mai multe aliniamente, este util să se ia în considerare diferite caracteristici. Astfel de caracteristici utile de aliniere includ identitatea secvenței , asemănarea și omologia . Identitatea determină că secvențele au aceleași reziduuri în pozițiile corespunzătoare. Asemănarea este determinată de reziduuri similare într-un raport cantitativ. De exemplu, în ceea ce privește secvențele de nucleotide, pirimidinele sunt considerate similare între ele, ca și purinele . Asemănarea duce în cele din urmă la omologie, deci cu cât secvențele sunt mai asemănătoare, cu atât sunt mai apropiate de omologi. De asemenea, asemănarea secvenței poate ajuta la găsirea unei origini comune [46] .