Multipel sekvens alignment ( engelsk multiple sequence alignment, MSA ) - alignment af tre eller flere biologiske sekvenser, normalt proteiner , DNA eller RNA . I de fleste tilfælde antages det, at inputsættet af sekvenser har et evolutionært forhold. Ved hjælp af flere justeringer kan den evolutionære oprindelse af sekvenser vurderes gennem fylogenetisk analyse.
Den visuelle repræsentation af alignment illustrerer mutationshændelser som punktmutationer (ændringer i en aminosyre eller et nukleotid ) som distinkte karakterer i en alignment-søjle, såvel som deres indsættelser og deletioner (repræsenteret med en bindestreg , huller).
Multiple sekvensjusteringer bruges ofte til at vurdere bevarelsen af proteindomæner , tertiære og sekundære strukturer og endda enkelte aminosyrerester eller nukleotider .
På grund af den større beregningsmæssige kompleksitet sammenlignet med parvis justering, kræver multipel justering mere komplekse algoritmer. Mange relaterede programmer bruger heuristiske algoritmer, fordi det kan være meget tidskrævende at finde en global optimal justering for mange sekvenser.
For at konstruere en global optimal justering bruges dynamisk programmering direkte . For proteinsekvenser er der to sæt parametre: gap penalty og substitutionsmatrixen, som indeholder sandsynligheden for at matche et par aminosyrerester baseret på ligheden mellem deres kemiske egenskaber og den evolutionære sandsynlighed for mutation. For nukleotidsekvenser bruges gap penalty også, men substitutionsmatricen er meget enklere, den tager kun højde for fuldstændige matchninger af nukleotider eller mismatches, dvs. fuldstændige mismatches [1] .
For n individuelle sekvenser kræver den naive metode at konstruere den n-dimensionelle ækvivalent af den matrix, der bruges til parvis alignment. Efterhånden som n vokser, vokser søgerummet eksponentielt . Den naive algoritme har således beregningsmæssig kompleksitet O(Længde af sekvenser Nsequences ). At finde det globale optimum for n sekvenser er et NP-komplet problem [2] [3] [4] .
I 1989, baseret på Carrillo-Lipman-algoritmen [5] , introducerede Altschul en praktisk tilgang, der brugte parvise justeringer til at begrænse det n-dimensionelle søgerum [6] . Med denne tilgang udføres dynamisk programmering på hvert par af sekvenser fra inputsættet, og der søges kun i området, der er placeret nær den n-dimensionelle skæring af disse stier. Programmet optimerer summen af alle tegnpar på hver position i justeringen (summen af parvægte) [7]
En meget brugt tilgang er progressiv alignment ved hjælp af en heuristisk algoritme udviklet af Paulien Hogeweg og Ben Hesper i 1984 [8] . Alle progressive justeringsmetoder har to vigtige trin: opbygning af et binært træ (stitræ), hvor bladene er sekvenser, og opbygning af en multipel justering ved at tilføje sekvenser til den voksende justering i henhold til stitræet. Selve stitræet kan bygges ved klyngemetoder såsom UPGMA og nabosammenføjning [9] .
Progressiv justering garanterer ikke en global optimal justering. Problemet er, at fejl genereret på et hvilket som helst trin af den voksende multiple justering ender i den endelige justering. Derudover kan justeringen være særlig dårlig i tilfælde af et sæt sekvenser, der er meget fjernt fra hinanden. De fleste moderne progressive metoder har en modificeret vægtningsfunktion med en sekundær vægtningsfunktion, der tildeler koefficienter til individuelle elementer i datasættet på en ikke-lineær måde baseret på deres fylogenetiske afstand fra nærmeste naboer [9] .
De progressive alignment-metoder er effektive nok til at blive anvendt på et stort antal (100-1000) sekvenser. Den mest populære progressive tilpasningsmetode tilhører Clustal [10] -familien , især den vægtede ClustalW [11] -variant , som kan tilgås gennem portaler såsom GenomeNet , EBI , EMBNet Arkiveret 1. maj 2011 på Wayback Machine . ClustalW bruges aktivt til at bygge fylogenetiske træer på trods af forfatterens advarsler om, at ukontrollerede håndjusteringer ikke bør bruges hverken i træbygning eller som input til forudsigelse af proteinstruktur . Den nuværende version af Clustal er Clustal Omega, som arbejder baseret på stitræer og HMM profil-profilmetoder til proteinjusteringer. Forskellige værktøjer er også foreslået til at konstruere progressive justeringer af DNA-sekvenser. En af dem er MAFFT ( Multiple Alignment using Fast Fourier Transform ) [12] .
En anden almindelig progressiv alignment-metode, T-Coffee [13] , er langsommere end Clustal og dets derivater, men producerer generelt mere nøjagtige alignments for fjernt beslægtede sekvenser. T-Coffee bygger et bibliotek af parrede justeringer, som den derefter bruger til at bygge flere justeringer.
Fordi progressive metoder er heuristiske, er de ikke garanteret at konvergere til et globalt optimum; linjeføringens kvalitet og dens biologiske betydning kan være svær at vurdere. En semi-progressiv metode, der forbedrer alignment-kvaliteten og ikke bruger tabsgivende heuristik, udføres i polynomiel tid ( PSAlign Archived 18 July 2011 at the Wayback Machine ) [14] .
Et sæt metoder til at konstruere flere justeringer, der reducerer de fejl, der nedarves i progressive metoder, er klassificeret som " iterativ ". De fungerer på samme måde som progressive metoder, men de omarrangerer gentagne gange de originale justeringer, efterhånden som nye sekvenser tilføjes. Progressive metoder er meget afhængige af kvaliteten af de indledende justeringer, da de vil ende i det endelige resultat uændret og derfor med fejl. Med andre ord, hvis sekvensen allerede er på linje, vil dens yderligere position ikke ændre sig. Denne tilnærmelse forbedrer effektiviteten, men påvirker resultatets nøjagtighed negativt. I modsætning til progressive metoder kan iterative metoder vende tilbage til oprindeligt beregnede parvise justeringer og sub-alignments, der indeholder undersæt af sekvenser fra forespørgslen, og dermed optimere den overordnede objektivfunktion og forbedre kvaliteten [9] .
Der er en bred vifte af iterative metoder. For eksempel bruger PRRN/PRRP en toppunktklatringsalgoritme til at optimere vægten af flere justeringer [15] og justerer iterativt justeringsvægtene og multi-gap-området [9] . PRRP fungerer mere effektivt, når det forbedrer justeringen, der tidligere er bygget med den hurtige metode [9] .
Et andet iterativt program, DIALIGN, tager en usædvanlig tilgang ved at fokusere på lokale justeringer af undersegmenter eller sekvensmotiver uden at indføre en gap penalty [16] . Justering af individuelle motiver præsenteres i en matrixform, svarende til et prikplot i parret justering. En alternativ metode, der bruger hurtige lokale justeringer som ankerpunkter for en langsommere global justering konstruktionsprocedure, er tilvejebragt i CHAOS/DIALIGN softwaren [16] .
Den tredje populære iterative metode kaldes MUSKEL. Det er en forbedring i forhold til progressive metoder, fordi det bruger mere nøjagtige afstande til at estimere forholdet mellem to sekvenser [17] . Afstande opdateres mellem iterationer (selvom MUSKEL oprindeligt kun indeholdt 2-3 iterationer).
Konsensusmetoder forsøger at vælge den optimale multiple justering fra forskellige multiple justeringer af det samme sæt inputdata. Der er to mest almindelige konsensusmetoder: M-COFFEE og MergeAlign [18] . M-COFFEE bruger flere justeringer genereret af 7 forskellige metoder til at opnå konsensus justeringer. MergeAlign er i stand til at generere konsensusjusteringer fra et vilkårligt antal inputjusteringer afledt af forskellige sekvensudviklingsmodeller og konstruktionsmetoder. Standardindstillingen for MergeAlign er at udlede en konsensusjustering ved hjælp af justeringer afledt af 91 forskellige modeller for proteinsekvensudvikling.
Skjulte Markov-modeller (HMM'er) er probabilistiske modeller, der kan evaluere sandsynligheden for alle mulige kombinationer af huller, matchninger eller uoverensstemmelser for at bestemme den mest sandsynlige multiple justering eller sæt af dem. HMM'er kan producere en enkelt højtvægtet justering, men kan også generere en familie af mulige justeringer, som derefter kan evalueres for deres biologiske betydning. HMM'er kan bruges til at opnå både globale og lokale justeringer. Selvom HMM-baserede metoder er relativt nye, har de vist sig at være metoder med betydelige forbedringer i beregningskompleksitet, især for sekvenser, der indeholder overlappende regioner [9] .
Standardmetoder baseret på HMM repræsenterer multipel justering i form af en rettet acyklisk graf , kendt som en partiel ordensgraf, som består af en række knudepunkter, der repræsenterer de mulige tilstande i justeringskolonnerne. I denne repræsentation er en perfekt konservativ søjle (dvs. sekvenser i en multipel justering har et bestemt tegn i den position) kodet som en enkelt knude med mange udgående forbindelser med tegn mulige i den næste alignment-position. Med hensyn til standard Hidden Markov Model er de observerede tilstande individuelle justeringssøjler, og de "skjulte" tilstande repræsenterer en antaget forfædres sekvens, hvorfra sekvenser i inputsættet kunne være nedstammet. En effektiv dynamisk programmeringsteknik, Viterbi-algoritmen , er meget brugt til at opnå god justering [19] . Den adskiller sig fra progressive metoder ved, at justeringen af de første sekvenser omarrangeres, efterhånden som hver ny sekvens tilføjes. Men ligesom progressive metoder kan denne algoritme blive påvirket af den rækkefølge, hvori sekvenser fra inputsættet kommer ind i alignment, især i tilfælde af evolutionært løst koblede sekvenser [9] .
Selvom HMM-metoder er mere komplekse end almindeligt anvendte progressive metoder, er der flere programmer til at opnå justeringer, såsom POA [20] såvel som en lignende, men mere generel metode i SAM [21] og HMMER [22] -pakkerne . SAM bruges til at opnå justeringer til forudsigelse af proteinstruktur i CASP-eksperimentet for gærproteiner . HHsearch, baseret på parvis sammenligning af HMM'er, bruges til at søge efter fjernt beslægtede sekvenser. Serveren, der kørte HHsearch (HHpred) var den hurtigste af de 10 bedste automatiske servere til forudsigelse af proteinstruktur i CASP7 og CASP8 [23] .
Standard optimeringsteknikker inden for datalogi, som tillader modellering, men ikke direkte gengivelse af den fysiske proces, bruges også til at bygge flere justeringer mere effektivt. En sådan teknik, den genetiske algoritme , er blevet brugt til at konstruere en multipel sekvensjustering baseret på en hypotetisk evolutionær proces, der gav sekvensdivergens. Denne metode fungerer ved at opdele en række mulige MSA'er i bidder og omarrangere disse bidder igen, hvilket introducerer pauser på forskellige positioner. Hovedmålfunktionen optimeres under denne proces, normalt ved at maksimere "parsummer" ved hjælp af dynamiske programmeringsmetoder. Denne metode er implementeret for proteinsekvenser i SAGA ( Sequence Alignment by Genetic Algorithm ) [ 24] -software og for RNA-sekvenser i RAGA [25] .
Ved hjælp af simuleringsudglødningsmetoden raffineres en eksisterende multipel justering bygget af en anden metode i en række omarrangeringer for at finde bedre justeringsområde, end det var før. Som i tilfældet med den genetiske algoritme, maksimerer annealingssimuleringen den objektive funktion som en funktion af summen af parrene. Udglødningssimuleringen bruger en betinget "temperaturfaktor", der bestemmer niveauet af omlejringer, der forekommer, og sandsynlighedsniveauet for hver omlejring. Det er typisk at bruge skiftende perioder med høj realignment og lav sandsynlighed (for at finde de yderste regioner i alignment) med perioder med lav realignment og høj sandsynlighed for nærmere at undersøge lokale minima nær nye alignment kolonner. Denne tilgang blev implementeret i MSASA-programmet ( Multiple Sequence Alignment by Simulated Annealing ) [26] .
De fleste multiple justeringsmetoder forsøger at minimere antallet af indsættelser/deletioner (huller), hvilket resulterer i kompakte justeringer. Denne tilgang kan føre til tilpasningsfejl, hvis de justerede sekvenser indeholdt ikke-homologe regioner, og hvis hullerne er informative i fylogenetisk analyse. Disse problemer er almindelige i nye sekvenser, der er dårligt kommenterede og kan indeholde frameshifts , fejldomæner eller ikke-homologe splejsede exoner .
Den første metode baseret på fylogenianalyse blev udviklet af Loitinoge og Goldman i 2005 [27] . I 2008 udgav de samme forfattere den tilsvarende software - PRANK [28] . PRANK forbedrer justeringer, når der er skær. Det er dog langsommere end de progressive og/eller iterative metoder [29] , der blev udviklet år før.
I 2012 dukkede to nye metoder baseret på fylogenetisk analyse op. Den første, kaldet PAGAN, blev udviklet af PRANK-holdet, og den anden, kaldet ProGraphMSA, blev udviklet af Zhalkovsky [30] . Deres software blev udviklet uafhængigt, men deler fælles træk: begge bruger grafalgoritmer til at forbedre genkendelsen af ikke-homologe områder, og forbedringer i koden gør dem hurtigere end PRANK .
Motivsøgning, eller på anden måde profilering, er en metode til at finde placeringen af et motiv i en global multiple alignment som et middel til at opnå den bedste MSA og den gennemsnitlige vægt af den resulterende matrix for at bruge den til at søge efter andre sekvenser med lignende motiver. Mange metoder er blevet udviklet til at bestemme motiver, men de er alle afhængige af at finde korte, meget konserverede mønstre i et større alignmentmønster og konstruere en matrix svarende til en substitutionsmatrix. Denne matrix afspejler nukleotid- eller aminosyresammensætningen for hver position i det formodede motiv. Justeringen kan derefter forfines ved hjælp af disse matricer. I standardprofilanalyse inkluderer denne matrix indgange for både hvert muligt symbol og mellemrummet [9] . I modsætning hertil søger den statistiske mønstersøgningsalgoritme først efter motiver og bruger derefter de fundne motiver til at bygge en multipel justering. I mange tilfælde, når det oprindelige sæt af sekvenser indeholder et lille antal sekvenser eller kun meget relaterede sekvenser, tilføjes pseudo -tællinger for at normalisere fordelingen afspejlet i vægtmatricen. Det hjælper især at undgå nuller i sandsynlighedsmatricen for ikke at få værdien af uendelighed i positionsvægtmatricen .
Blokanalyse er en motivsøgningsmetode udført i mellemrumsfri alignment-regioner. Blokke kan genereres fra flere justeringer eller afledes fra fejljusterede sekvenser ved at forudberegne flere fælles motiver fra kendte genfamilier [31] . Blokstimering er normalt baseret på et rum af højfrekvente symboler snarere end en eksplicit beregning af erstatningsmatricer. BLOCKS - serveren giver en alternativ metode til at lokalisere sådanne motiver i ikke-justerede sekvenser.
Statistisk mønstermatching udføres ved hjælp af forventningsmaksimering og Gibbs samplingsalgoritme . For at søge efter motiver er den mest brugte server MEME , som bruger forventningsmaksimeringsalgoritmen og metoden for skjulte Markov-modeller, samt MEME/MAST [32] [33] , som desuden bruger MAST-algoritmen.
Nogle ikke-proteinkodende regioner af DNA, især transkriptionsfaktorbindingssteder (TFBS), er mere konserverede og ikke nødvendigvis evolutionært beslægtede, da disse steder kan forekomme i ikke-homologe sekvenser. Således er de antagelser, der anvendes til at tilpasse proteinsekvenser og DNA-kodende regioner, ikke passende for sekvenser af transkriptionsfaktorbindingssteder. Selvom det giver mening at tilpasse proteinkodende DNA-regioner til homologe sekvenser ved hjælp af mutationsoperatorer, kan tilpasning af bindingsstedsekvenser for den samme transkriptionsfaktor ikke være baseret på evolutionært relaterede mutationsoperationer. Tilsvarende kan den evolutionære punktmutationsoperator bruges til at bestemme redigeringsafstand for kodende sekvenser, men er til ringe nytte for transkriptionsfaktorbindingsstedsekvenser på grund af det faktum, at enhver sekvensændring skal bevare et vist niveau af specificitet for at udføre bindingsfunktionen. Dette bliver især vigtigt, når sekvensjustering af transkriptionsfaktorbindingssteder er nødvendig for at bygge observerbare modeller til at forudsige ukendte loci af den samme TFBS. Derfor skal flere justeringsmetoder justeres for at tage højde for de vigtigste evolutionære hypoteser og bruge visse operatører, som i den termodynamisk følsomme EDNA- metode til at justere bindingssteder [34] .
Behovet for at bruge heuristiske tilgange til multiple alignment fører til det faktum, at et vilkårligt udvalgt sæt af proteiner kan være fejljusteret med stor sandsynlighed. For eksempel viste evaluering af nogle førende tilpasningsprogrammer ved brug af BAliBase benchmark [35] , at mindst 24% af alle justerede aminosyrepar er forkert justeret [36] . Disse fejl kan opstå på grund af unikke indsættelser i en eller flere sektioner af sekvenserne. De kan også skyldes en mere kompleks evolutionær proces, der resulterer i proteiner, der er svære at aligne i sekvens alene, og for en god alignment skal du vide noget andet, såsom struktur. Efterhånden som antallet af alignede sekvenser stiger, og deres divergens stiger, stiger fejlen på grund af den heuristiske natur af multiple alignment-algoritmer. Multiple alignment visualizers giver dig mulighed for visuelt at evaluere alignment ofte ved at kontrollere kvaliteten af alignment for kommenterede funktionelle regioner i to eller flere sekvenser. Mange visualizere giver dig også mulighed for at redigere justeringen ved at rette fejl (normalt af mindre karakter) for at opnå en optimal kureret justering, der er egnet til brug i fylogenetisk analyse eller sammenlignende modellering [37] .
Men da antallet af sekvenser stiger, især i genom-dækkende undersøgelser, der involverer mange multiple justeringer, bliver det umuligt manuelt at kurere alle justeringer. Også manuel kuration er subjektiv. Og endelig kan selv den bedste ekspert ikke med sikkerhed bringe mange tvetydige sager på linje i stærkt divergerende sekvenser. I sådanne tilfælde er det almindelig praksis at bruge automatiske procedurer til at eliminere upålideligt justerede områder med flere justeringer. For at opnå fylogenetiske rekonstruktioner bruges Gblocks-programmet i vid udstrækning til at fjerne alignment-blokke med angiveligt lav kvalitet i overensstemmelse med forskellige cutoffs af antallet af sekvenser med huller i alignment-kolonner [38] . Samtidig kan disse kriterier overdrevent bortfiltrere regioner med insertioner/deletioner, der kunne justeres pålideligt, og disse regioner kan være nyttige til at identificere positiv selektion. Få alignment-algoritmer producerer en stedspecifik alignmentvægt, der kunne tillade udvælgelse af meget konserverede regioner. Denne mulighed blev først givet af SOAP -programmet [39] , som tester modstanden af hver kolonne over for parameterudsving i det populære ClustalW-justeringsprogram. T - Coffee [39] -programmet bruger et alignment-bibliotek til at generere den endelige multiple alignment og producerer en multiple alignment farvet i overensstemmelse med en konfidensscore, der afspejler overensstemmelsen mellem de forskellige alignmenter i biblioteket for hver af de justerede residualer. TCS ( Transitive Consistency Score ) er en udvidelse, der bruger T-Coffee parvise alignment-bibliotek til at score hver tredje multiple alignment . Parvise projektioner kan skabes ved hjælp af hurtige eller langsomme metoder, så der kan findes et kompromis mellem beregningshastighed og nøjagtighed [40] [41] . Et andet justeringsprogram, FSA ( eng. Fast statistical alignment ), bruger statistiske modeller til at beregne alignment-fejlen og kan producere multiple alignment med et estimat af niveauet af dets pålidelighed. HoT-scoren ( Heads -Or-Tails ) kan bruges til at måle fejlene ved stedspecifikke justeringer, hvor der kan opstå fejl på grund af eksistensen af flere co-optimale løsninger. GUIDANCE [42] -programmet beregner et lignende stedspecifikt konfidensmål baseret på stabiliteten af justeringen til usikkerhed i styretræet, som bruges, som nævnt ovenfor, i progressive alignment-programmer . Samtidig er en mere statistisk forsvarlig tilgang til at estimere tilpasningsusikkerheder at bruge probabilistiske evolutionære modeller til i fællesskab at estimere fylogeni og tilpasning. Den Bayesianske tilgang beregner posteriore sandsynligheder for fylogeni og tilpasningsestimater, som måler tillidsniveauet i disse estimater. I dette tilfælde kan den posteriore sandsynlighed beregnes for hvert sted i linjeføringen. Denne tilgang er implementeret i Bali-Phy-programmet [43] .
Multipel sekvensjustering kan bruges til at konstruere et fylogenetisk træ [44] . Dette er muligt af to årsager. For det første kan funktionelle domæner, der er kendt for annoterede sekvenser, anvendes til at aligne uannoterede sekvenser. For det andet kan konservative regioner have funktionel betydning. På grund af dette kan flere justeringer bruges til at analysere og finde evolutionære forhold gennem sekvenshomologi. Punktmutationer og indsættelser/delinger kan også påvises [45] .
Lokalisering af bevarede domæner ved multiple alignment kan også bruges til at identificere funktionelt vigtige steder, såsom bindingssteder , regulatoriske steder eller steder, der er ansvarlige for andre nøglefunktioner. Når du analyserer flere justeringer, er det nyttigt at overveje forskellige karakteristika. Sådanne nyttige alignmentkarakteristika indbefatter sekvensidentitet , lighed og homologi . Identitet bestemmer, at sekvenserne har de samme rester på de tilsvarende positioner. Lighed bestemmes af lignende rester i et kvantitativt forhold. For eksempel, hvad angår nukleotidsekvenser, anses pyrimidiner for at ligne hinanden, ligesom puriner . Lighed fører til sidst til homologi, så jo mere ens sekvenser er, jo tættere er de homologer. Også sekvenslighed kan hjælpe med at finde en fælles oprindelse [46] .