bestemmelse af homologe regioner i molekylær sekvenser bruges ofte til yderligere antagelser om deres funktion og evolution, og derfor nøjagtig flere sekvens alignment (MSA) af nukleinsyre-og protein-sekvenser er afgørende., Derfor har der været en enorm indsats i udviklingen og implementeringen af forskellige MSA-algoritmer ved hjælp af forskellige tilgange til at forbedre den resulterende justeringsnøjagtighed.

nøjagtighedsvurderingen af MSA-programmer udføres ofte ved at anvende manuelt (eller semi automatisk) kuraterede sekvensdatabaser som BAliBASE , PREFAB og SABmark . Indtil videre har BAliBASE været den mest anvendte justeringsdatabase til evaluering af ydeevnen for forskellige MSA-programmer. Det blev konstrueret ved hjælp af proteinsekvenser eller modeller med kendte tredimensionelle strukturer., Den sidste start, version 3.0, havde en stigning i antallet af tilgængelige sekvenser og justeringer. Sådanne forbedringer har tilsyneladende behandlet Karplus og Hu ‘ s største bekymringer vedrørende brugen af BAliBASE til at benchmarke MSA-algoritmer.

Justeringsdatabaser giver en kilde til nøjagtige justeringer for at måle nøjagtigheden og hastigheden af forskellige programmer, men de har også flere ulemper. Selvom databasernes justeringer er manuelt kurateret, er der stadig mulighed for fejljusteringer, hvilket ville resultere i nøjagtighedsvurderingsproblemer., Sætene med justeringer forbliver stadig ret små og repræsenterer muligvis ikke det komplette udvalg af scenarier for proteinudvikling. Desuden er en stor ulempe ved brugen af justeringsdatabaser, at algoritmer potentielt kan udvikles og indstilles til de tilpasninger, der udelukkende findes i disse datasæt.

for nylig har der været flere DNA-sekvenssimuleringspakker, der indeholder indels, såsom MySSP og da .g . MySSP har været meget anvendt i forskellige undersøgelser af fylogenetisk inferens og evolutionær afstandsstimering kombineret med DNA-justeringsnøjagtighed ., For proteiner steg Lassmann og sonnhammer i en tidligere sammenligning af MSA-algoritmer kunstigt oprettede sekvenssæt genereret af simuleringsprogrammet . Rose simulerer sekvenser af proteiner, der giver mulighed for forekomst af indels. Datasæt genereret af Rose præsenterer deres egne begrænsninger for undersøgelsen af justeringsnøjagtigheden. I Rose repræsenterer indel størrelse og antal ikke tilstrækkeligt empiriske data for proteiner, der har divergeret i forskellige evolutionære tider. Programmet antager også lige evolutionære satser for alle steder i proteinet.,

i denne undersøgelse introducerer vi en forbedret tilgang til vurdering af justeringsnøjagtighed ved hjælp af simulerede proteinsekvenser genereret af Simprot . Simprot er et avanceret simuleringsprogram, der anvender en parametreret version af distributionian og Goldstein insertion and deletion (indel) distribution. Selvom den oprindelige distribution empirisk blev afledt af en undergruppe af justeringer af stærkt divergerede proteinsekvenser, den parametriserede version tillader en meget fleksibel simulering af indels i sekvenser for alle niveauer af sekvensdivergens., Simprot tillader også variabel substitution og indel satser på forskellige steder ved at gennemføre gamma distribuerede steder satser . Tre modeller af aminosyresubstitution (PMB, PAM og JTT) er også tilgængelige. Vi har brugt Simprot til at generere kendt linjeføringer med en bred vifte af evolutionære parametre, samt det nyeste BAliBASE database kurateret af linjeføringer, at undersøge den nøjagtighed og hastighed populære og offentligt tilgængelige protein flere sekvens alignment programmer.,

justeringsprogrammer

Der er mange tilgængelige computerpakker, der genererer MSA ‘ er af proteinsekvenser. Vi valgte ni af de aktuelt mest anvendte programmer (i rækkefølge efter udgivelsesdato): Clustal., Dialign2.2, t-Coffee, POA, Muscle, Mafft, ProbCons, Dialign-t og Kalign.

Clustal version version 1.8

Dette er sandsynligvis det mest anvendte justeringsprogram og ældste blandt de testede pakker. Soft .aren udfører en progressiv justering, først anvender en parvis sekvens sammenligning ved at beregne en afstand Matri., der gemmer sekvens divergens., Efter denne Matri.er opnået, en træ guide er bygget ved hjælp af nabo sammenføjning, efterfulgt af det tredje og sidste trin, hvor sekvenser er justeret i henhold til grenrækkefølgen i guide træet. Programmet anvender to gap sanktioner i sin justering procedure: gap åbning og gap udvidelse, og i tilfælde af polypeptider, en fuld aminosyre scoring vægt Matri.. Disse gap sanktioner er hovedsageligt afhængige af faktorer såsom vægt Matri., sekvens længde og lighed., I enkle tilfælde kan Clustal might nøjagtigt justere tilsvarende domæner og sekvenser af kendt sekundær eller tertiær struktur, mens det i mere komplekse tilfælde kan bruges som et godt udgangspunkt for yderligere forfining.

Dialign2.2 version 2.2.1

dette program bruger en diagonal metode til at justere sekvenser lokalt og globalt. Dialign2. 2 sammenligner ikke enkelte rester, men hele uafbrudt (ingen huller, uoverensstemmelser tilladt) strækninger af rester, der ville danne diagonaler i en dot-Matri.sammenligning af to sekvenser., Derfor straffer den ikke indsættelsen og udvidelsen af huller og kan lade uafhængige segmenter være uændrede. Det første trin i proceduren skaber alle mulige parvise justeringer, opbevaring af en samling af diagonaler, der opfylder visse konsistenskriterier uden modstridende dobbelt-eller crossover-opgaver af rester . Alle gemte diagonaler vægtes for at definere poster med maksimal sum af vægte, og derefter sorteret for at bestemme graden af overlapning, understreger eksistensen af diagonaler til stede i flere sekvenser., En grådig-lignende algoritme gør en endelig behandling, kontrol diagonaler scoringer fra top til bund skaber en endelig flere justering. Huller indsættes i slutningen af MSA-oprettelsen, indtil alle nuværende rester er forbundet.

t-kaffe (træbaseret konsistensmålfunktion til justeringsevaluering) version 3.27

T-kaffe anvender en progressiv strategi til justering af sekvenser. Programmet opretter først et bibliotek fra to forskellige kilder: globale justeringer fra Clustal and og lokale justeringer fra Lalign ., For hvert par sekvenser oprettes globale justeringer og de parvise lokale justeringer fra de ti topscorende ikke-skærende segmenter. Programmet behandler de globale og lokale oplysninger, tildele vægte til alle parvise justeringer i forhold til sekvens identitet . Dette efterfølges af kombinationen af grupper, der fusioneres til et enkelt bibliotek. Der er en forlængelsesfase for dette kombinerede bibliotek, hvilket får den endelige vægt af ethvert par rester til at afspejle en del af informationen indeholdt i hele biblioteket., Et sidste trin kræver en beregning af en afstandsmatri.og et nabo Sammenføjningstræ, da justeringen genereres med en progressiv strategi ved at justere de to nærmeste sekvenser på træet i henhold til den vægt, der er gemt i det udvidede bibliotek. Det oprindelige par fastgøres derefter, og eventuelle eksisterende huller kan ikke forskydes senere. Den progressive justering fortsætter, indtil hver sekvens er justeret.

POA (Partial Order Alignment) version 2.0

POA er en anden MSA-pakke, der bruger en progressiv justeringsalgoritme uden at bruge generaliserede profiler., Dette program introducerer brugen af en Delvis For-Flere Sekvens Alignment (PO-MSA) format til at repræsentere sekvenser, og mere præcist afspejler biologiske indhold. Dette format gemmer justeringen som en komprimeret graf for minimal node og kant tæller, stadig indeholder alle de tilgængelige oplysninger i en traditionel MSA. Sekvenser gemmes som en lineær serie af knuder, der hver er forbundet med to kanter. POA bruger en traditionel dynamisk programmeringsalgoritme, hvor lineære sekvenser erstattes af partielle orden (PO) grafer., Disse PO-strukturer transformeres i sædvanlige 2D-matricer, og hver kombination af celler scores baglæns som i en traditionel Smith-Wateraterman-sekvensindstillingsprocedure . Disse matricer udvides derefter i enhver retning (diagonal, vandret, lodret), hvilket muliggør produktion af parvis justering på knudepunkter. MSA opnås ved justering af to sekvenser i begyndelsen med tilføjelsen af andre sekvenser successivt til det oprindelige par.

muskel (Multiple se .uence comparison by log-e expectationpectation) version 3.,6

muskel bruger en parvis profiljusteringsmetode. Programmet bygger først en progressiv justering, som derefter forbedres og raffineres i to efterfølgende faser. Den progressive justering er skabt efter sekvensen ligheder, en afstand estimering og en UPGMA træ beregnes. Muscle bruger to afstandsmålinger: en k mer-afstand for ujævne sekvenspar og en Kimura-afstand for justerede par . Den progressive justeringsforbedringstrin skaber et nyt træ med den allerede beregnede Kimura-afstandsmatri.og bygger derefter en bedre justering baseret på dette forbedrede træ., Den sidste forfiningstrin anvender en variant af træafhængig begrænset partitionering . Denne metode sletter en af trækanterne, bi-partitionerer justeringen og ekstraherer begge partitioners profiler, som derefter justeres med en profilprofiljustering. Hvert træ kant er besøgt iterativt og tilpasningen med en opdateret summeres parvis score af hver sekvens par bevares. Kanterne besøges i rækkefølge af faldende afstand fra roden, med en justering af individuelle sekvenser, der bevæger sig til tættere beslægtede grupper af sekvenser .,

Mafft (Flere sekvens alignment baseret på Fast Fourier Transform) version 5.732

Mafft er et program, som kan bruges med forskellige alignment metoder, enten gradvis tilpasning alene (med Fast Fourier Transform), eller progressive efterfulgt af iterative raffinement. Maffts grundlæggende kørsel kan have op til tre trin, men standardproceduren udfører de første to trin. For det første oprettes en progressiv justering baseret på en grov afstand mellem hvert sekvenspar baseret på delte 6-tupler., En guide træ er også genereret af UPGMA med modificeret kobling og sekvenser derefter justeret efter gren rækkefølge af træet (dette trin alene kaldes strategi FFT-NS-1). Det andet trin beregner en distance matrix, der er baseret på de oplysninger, der er indsamlet på det foregående trin, og den progressive alignment er igen gjort brug af et træ, der opnås fra den nye matrix som udgangspunkt (op til dette trin, at den strategi er kendt som FFT-NS-2, og det er den standard, der anvendes af software)., Den sidste fase er den iterative forfining, der optimerer Gotohs vægtede sum af par (spsp) score, med en gruppe-til-gruppe justering og den træafhængige restriktionspartitionsteknik . Hvis alle tre trin anvendes, kaldes proceduren FFT-NS-i, hvilket betyder, at den bruger en FFT-metode til hurtigt at identificere homologe regioner, der er til stede i sekvenserne, som efterfølges af en iterativ fase af forfining., FFT konverterer hver enkelt aminosyre, der er til stede i en sekvens til en vektor, der repræsenterer volumen og polaritet, som er vigtige faktorer på substitution begivenheder, så softwaren til at forudsige disse hændelser med præcision.

Mafft indeholder også tre yderligere raffinementalgoritmer: l-INS-i, G-INS-i og e-INS-i . Disse strategier øger antallet af trin, der kræves for at oprette en MSA-justering til fem. I disse tilfælde kræver det første trin også konstruktion af en afstandsmatri., der ikke bruger 6-tupler., Forskelligt fra FFT-NS-* tilgange der er ingen genopbygning af den beregnede UPGMA-træ og programmet flytter til det andet trin, dividere hul-fri segmenter og opbevaring af score arrays for hvert hul-fri segment fra en sekvens til en anden. Mafft beregner derefter en” betydning ” værdi fra scoren af segmentet og gemmer, hvor ofte rester vises på andre segmenter., Alle “Betydning” værdier er derefter samlet i en” betydning ” Matri.i trin tre, som hurtigt efterfølges af en gruppe-til-gruppe justering opnået fra score matricer og en vægtning ordning baseret på en Needleman-.unsch algoritme. Et sidste trin forbedrer iterativt de opnåede justeringer, optimerer en scoresp-score og de tidligere beregnede” betydning ” – værdier.

ProbCons (Probabilistisk Konsistens-baserede flere sekvens alignment) version 1.1

ProbCons er det eneste program, der bruger en probabilistisk konsistens metode til alignment., Det er en ændring af den traditionelle sum-of-Par pointsystem, og derudover inkorporerer et par-skjult Markov modelbaseret progressiv justering algoritme. Justeringsproceduren er opdelt i fire trin, begyndende med en beregning af posterior Sandsynlighed matricer for hvert par sekvenser. Dette efterfølges af en dynamisk programmering beregning af den forventede nøjagtighed af hver parvis justering. Probabilistisk konsistens transformation anvendes derefter for at re-estimere match nøjagtighed scoringer., Et guidetræ beregnes med hierarkisk klynge med ligheden defineret ved et vægtet gennemsnit af værdier mellem sekvenser af hver klynge. Guidetræet bruges til at justere sekvenserne ved hjælp af en progressiv tilgang. En efterbehandlingsfase udføres også, hvor tilfældige bi-partitioner af den genererede justering tilpasses for at kontrollere, om der er bedre justeringsregioner. ProbCons adskiller sig fra andre justeringsprogrammer, da det ikke indeholder biologiske begreber som positionsspecifik gap scoring, evolutionær trækonstruktion og andre funktioner, der ofte bruges af andre pakker.,

Dilign-t version 0.2.1

dette program er en reimplementering af proceduren udviklet i Dialign2.2, men med en bedre løsning til at håndtere inkonsekvente fragmenter, herunder fragment-kæde. Det implementerer også en ny tilgang til estimering af sandsynligheder for den tilfældige forekomst af hvert fragment, der er til stede i den rækkefølge, der skal justeres. Dialign – t bruger ikke forudberegnede tabeller for at opnå vægt score: det beregner sandsynlighedstabeller fra flere substitution matricer. Derudover er den grådige-lignende multiple alignment algoritme fra Dialign2.,2 blev ændret for at undgå falske lokale ligheder.

Kalign version 1.04

Kalign er et andet program, der bruger en progressiv justeringsmetode for at opnå den bedst mulige MSA. Den væsentligste forskel på denne algoritme til andre metoder er, at den anvender approximateu-manber omtrentlige streng matching algoritme ved beregning af afstanden mellem sekvenser. Algorithmu-manber-algoritmen måler afstanden mellem to strenge ved hjælp af en Levenshtein-redigeringsafstand, som giver mulighed for en effektiv søgning efter uoverensstemmelser (delt eller ej) og mønstre, der findes i sekvenserne., Ifølge Kalign-udviklerne giver denne metode mulighed for en afstandestimering, der er lige så hurtig som en k-tuple-algoritme, men er mere præcis . Det første trin i justeringsproceduren er at beregne de parvise afstande ved hjælp af approachu-manber-tilgangen. Den parvise afstandsstimering efterfølges af en konstruktion af et styretræ ved hjælp af UPGMA, som anvendes i en global dynamisk programmeringsmetode til at justere sekvenserne/profilerne., Desuden er, programmet udfører en sammenhæng ind for at definere de største sæt af sekvens kampe, der kan indsættes i den tilpasning, ved hjælp af en modificeret udgave af Needleman-Wunsch at finde den mest konsekvente vej gennem dynamisk programmering matrix. Også, Kalign opdaterer positionerne for mønster matchings, som justerer den absolutte position af kampe, der findes inden for sekvenser til deres relative positioner inden for genererede profiler .