bestämningen av homologa regioner av molekylära sekvenser används ofta för vidare inferens av deras funktion och utveckling, och därför är noggrann multipel sekvensinriktning (MSA) av nukleinsyra och proteinsekvenser avgörande., Följaktligen har det gjorts enorma ansträngningar i utvecklingen och genomförandet av olika MSA algoritmer, med hjälp av olika metoder för att förbättra den resulterande inriktningsnoggrannheten.

noggrannhetsbedömningen av MSA-program görs ofta genom att använda manuellt (eller semi automatiskt) kurerade sekvensdatabaser som BAliBASE , PREFAB och SABmark . Hittills har BAliBASE varit den oftast använda justeringsdatabasen för att utvärdera prestanda för olika MSA-program. Det konstruerades med hjälp av proteinsekvenser eller modeller med kända tredimensionella strukturer., Den sista starten, version 3.0, hade en ökning av antalet tillgängliga sekvenser och anpassningar. Sådana förbättringar har uppenbarligen tagit itu med Karplus och Hu: s stora farhågor när det gäller användningen av BAliBASE för att jämföra MSA-algoritmer.

Justeringsdatabaser ger en källa till exakta anpassningar för att mäta noggrannheten och hastigheten hos olika program, men de uppvisar också flera nackdelar. Även om databasernas anpassningar är manuellt kurerade finns det fortfarande möjlighet till feljusteringar som skulle leda till problem med noggrannhetsbedömningen., Uppsättningarna av anpassningar förblir fortfarande ganska små och kanske inte representerar det fullständiga utbudet av scenarier för proteinutveckling. Dessutom är en stor nackdel med användningen av justeringsdatabaser att algoritmer potentiellt kan utvecklas och anpassas till de anpassningar som endast finns i dessa datamängder.

nyligen har det funnits flera DNA-sekvenssimuleringspaket som innehåller Indel, såsom MySSP och DAWG . MySSP har använts i stor utsträckning i olika studier av fylogenetisk inferens och evolutionär avståndsuppskattning i kombination med DNA-inriktningsnoggrannhet ., För proteiner, Lassmann och Sonnhammer i en tidigare jämförelse av MSA algoritmer som används artificiellt skapade sekvensuppsättningar som genereras av simuleringsprogrammet Rose . Rose simulerar sekvenser av proteiner som möjliggör förekomst av Indel. Datauppsättningar som genereras av Rose presenterar sina egna begränsningar för studien av inriktningsnoggrannheten. I Rose representerar indelstorlek och antal inte tillräckligt empiriska data för proteiner som har divergerat för olika evolutionära tider. Programmet förutsätter också lika evolutionära hastigheter för alla platser i proteinet.,

i denna studie introducerar vi ett förbättrat tillvägagångssätt för att bedöma inriktningsnoggrannheten genom att använda simulerade proteinsekvenser som genereras av Simprot . Simprot är ett avancerat simuleringsprogram som använder en parametriserad version av Qian och Goldstein insertion and deletion (indel) distribution. Även om den ursprungliga fördelningen var empiriskt härledd från en delmängd av anpassningar av mycket divergerade proteinsekvenser, tillåter den parametriserade versionen en mycket flexibel simulering av Indel i sekvenser för alla nivåer av sekvensdivergens., Simprot tillåter också variabel substitution och indel priser på olika platser genom att genomföra gamma distribuerade platser priser . Tre modeller av aminosyror substitution (PMB, PAM och JTT) är också tillgängliga. Vi har använt Simprot för att generera kända anpassningar med ett brett utbud av evolutionära parametrar, liksom den senaste balibasdatabasen av kurerade anpassningar, för att undersöka noggrannheten och hastigheten hos populära och offentligt tillgängliga program för flera sekvenser för proteininriktning.,

anpassningsprogram

det finns många tillgängliga datorpaket som genererar MSAs av proteinsekvenser. Vi valde nio av de för närvarande mest använda program (för offentliggörande datum): Clustal W, Dialign2.2, T-Kaffe, POA, Muskler, Mafft, ProbCons, Dialign-T och Kalign.

Clustal w version 1.8

detta är förmodligen det mest använda anpassningsprogrammet och äldsta bland de testade paketen. Programvaran utför en progressiv inriktning, först använder en parvis sekvens jämförelse genom att beräkna en avståndsmatris som lagrar sekvens divergens., Efter denna matris erhålls, byggs en trädguide med hjälp av granne sammanfogning, följt av det tredje och sista steget där sekvenser är inriktade enligt grenordningen i styrträdet. Programmet använder två gap påföljder i sin anpassning förfarande: gap öppning och gap förlängning, och i fallet med polypeptider, en fullständig aminosyra scoring viktmatris. Dessa brister är huvudsakligen beroende av faktorer som viktmatrisen, sekvenslängden och likheten., I enkla fall kan Clustal W exakt anpassa motsvarande domäner och sekvenser av känd sekundär eller tertiär struktur medan den i mer komplexa fall kan användas som en bra utgångspunkt för ytterligare förfining.

Dialign2.2 version 2.2.1

det här programmet använder en diagonal metod för att anpassa sekvenser lokalt och globalt. Dialign2. 2 jämför inte enstaka rester, men hela oavbrutna (inga luckor, missmatchningar tillåtna) sträckor av rester som skulle bilda diagonaler i en punktmatrisjämförelse av två sekvenser., Följaktligen straffar det inte införandet och utvidgningen av luckor och kan lämna orelaterade segment oförändrade. Det första steget i förfarandet skapar alla möjliga parvis anpassningar, lagra en samling diagonaler som uppfyller vissa konsistenskriterier utan motstridiga dubbla eller crossover uppdrag av rester . Alla sparade diagonaler viktas för att definiera poster med maximal summa av vikter och sorteras sedan för att bestämma graden av överlappning, med betoning på förekomsten av diagonaler som finns i flera sekvenser., En girig-liknande algoritm gör en slutlig bearbetning, kontrollera diagonaler poäng från topp till botten skapa en slutlig flera justering. Luckor sätts in i slutet av MSA-skapandet tills alla nuvarande rester är anslutna.

t-kaffe (Trädbaserad konsistens målfunktion för justering utvärdering) version 3.27

t-kaffe använder en progressiv strategi för att anpassa sekvenser. Programmet skapar först ett bibliotek från två olika källor: globala anpassningar från Clustal W och lokala anpassningar från Lalign ., För varje par sekvenser skapas globala anpassningar och parvis lokala anpassningar från de tio toppbetyg som inte skär varandra. Programmet behandlar den globala och lokala informationen, tilldela vikter till alla parvis inriktningar i förhållande till sekvensidentitet . Detta följs av kombinationen av grupper som slås samman till ett enda bibliotek. Det finns en förlängningsfas för detta kombinerade bibliotek, vilket gör att den slutliga vikten av ett par rester återspeglar en del av informationen i hela biblioteket., Ett sista steg kräver en beräkning av en avståndsmatris och en granne som ansluter träd, eftersom inriktningen genereras med en progressiv strategi genom att anpassa de två närmaste sekvenserna på trädet enligt den vikt som lagras i det utökade biblioteket. Det ursprungliga paret är sedan fixat och eventuella befintliga luckor kan inte flyttas senare. Den progressiva inriktningen fortsätter tills varje sekvens är i linje.

POA (Partial Order Alignment) Version 2.0

POA är ett annat MSA-paket som använder en progressiv inriktningsalgoritm utan att använda generaliserade profiler., Detta program introducerar användningen av en partiell ordning-Multiple Sequence Alignment (PO-MSA) format för att representera sekvenser, och mer exakt återspeglar biologiskt innehåll. Detta format lagrar justeringen som en komprimerad graf för minimal nod och kanttal, fortfarande innehåller all information som finns i en traditionell MSA. Sekvenser lagras som en linjär serie noder vardera förbundna med två kanter. POA använder en traditionell dynamisk programmeringsalgoritm, där linjära sekvenser ersätts av Partial Order (PO) grafer., Dessa PO strukturer omvandlas i vanliga 2D matriser och varje kombination av celler görs bakåt som i en traditionell Smith-Waterman sekvens inriktningsförfarande . Dessa matriser förlängs sedan i vilken riktning som helst (diagonalt, horisontellt, vertikalt) vilket möjliggör produktion av parvis inriktning på knutpunkter. MSA erhålls från anpassningen av två sekvenser i början med tillägg av andra sekvenser successivt till det ursprungliga paret.

Muskel (Multipel sekvensjämförelse genom att logga förväntan) version 3.,6

Muscle använder en parvis profilinriktning. Programmet bygger först en progressiv anpassning som sedan förbättras och förfinas i två efterföljande steg. Den progressiva anpassningen skapas efter sekvensens likheter, en avståndsuppskattning och ett UPGMA-träd beräknas. Muscle använder två avståndsåtgärder: en k Mer avstånd för ojusterade sekvenspar och en Kimura avstånd för inriktade par . Den progressiva inriktningsförbättringssteget skapar ett nytt träd med den redan beräknade Kimura-avståndsmatrisen och bygger sedan en bättre inriktning baserat på detta förbättrade träd., Den sista förfining skede använder en variant av trädet beroende begränsad partitionering . Den här metoden tar bort en av trädkanterna, bi-partitionerar inriktningen och extraherar båda partitionernas profiler som sedan omformas med en profilprofiljustering. Varje trädkant besöks iterativt och anpassningen med en uppdaterad summerad parvis poäng för varje sekvens par behålls. Kanterna besöks för att minska avståndet från roten, med en omjustering av enskilda sekvenser, flyttar till närmare besläktade grupper av sekvenser .,

Mafft (Multiple sequence alignment based on Fast Fourier Transform) version 5.732

Mafft är ett program som kan användas med olika inriktningsmetoder, antingen progressiv inriktning ensam (med Fast Fourier Transform) eller progressiv följt av iterativ förfining. Maffts grundläggande körning kan ha upp till tre steg, men standardproceduren utför de första två stegen. För det första skapas en progressiv inriktning baserat på ett grovt avstånd mellan varje sekvenspar baserat på delade 6-tuples., Ett styrträd genereras också av UPGMA med modifierad koppling och sekvenser anpassas sedan efter grenens ordning (detta steg kallas enbart strategi FFT-NS-1). Det andra steget omberäknar en avståndsmatris, baserat på den information som samlats in på föregående steg, och den progressiva inriktningen görs på nytt med hjälp av ett träd som erhållits från den nya matrisen som utgångspunkt (fram till detta steg är strategin känd som FFT-NS-2 och det är standard som används av programvaran)., Den sista fasen är den iterativa förfiningen som optimerar Gotohs viktade summa av par (WSP)-poäng, med en grupp-till-gruppjustering och den trädberoende begränsningspartitionstekniken . Om alla tre stegen används kallas förfarandet FFT-NS-i, vilket innebär att det använder en FFT-metod för att snabbt identifiera homologa regioner som finns i sekvenserna som följs av en iterativ fas av förfining., FFT omvandlar varje enskild aminosyra som finns i en sekvens till en vektor som representerar volym och polaritet, vilket är viktiga faktorer på substitutionshändelser, vilket gör att programvaran kan förutsäga sådana händelser med precision.

Mafft innehåller också tre ytterligare förfiningsalgoritmer: l-ins-i, G-ins-i och E-ins-i . Dessa strategier ökar antalet steg som krävs för att skapa en MSA anpassning till fem. I dessa fall kräver det första steget också byggandet av en avståndsmatris, som inte använder 6-tuples., Annorlunda från FFT-NS – * tillvägagångssätt det finns ingen rekonstruktion av det beräknade UPGMA-trädet och programmet flyttar till det andra steget, delar de gapfria segmenten och lagrar poäng arrays för varje gapfritt segment från en sekvens till en annan. Mafft beräknar sedan ett” betydelse ” – värde från segmentets poäng och lagrar hur ofta rester visas på andra segment., Alla” betydelse ”- värden samlas sedan i en” betydelse ” – matris i steg tre som snabbt följs av en grupp-till-gruppjustering som erhålls från poängmatriserna och ett viktningssystem baserat på en Needleman-Wunsch-algoritm. Ett sista steg iterativt förfinar de erhållna justeringarna, optimerar en WSP-poäng och de” betydelse ” – värden som beräknats tidigare.

ProbCons (Probabilistic consistence-based multiple sequence alignment) version 1.1

ProbCons är det enda program som använder en probabilistisk konsistensmetod för justering., Det är en modifiering av den traditionella summan av par poängsystem, och dessutom innehåller ett par dolda Markov modellbaserad progressiv inriktningsalgoritm. Inriktningsproceduren är uppdelad i fyra steg, som börjar med en beräkning av posterior-sannolikhetsmatriser för varje par sekvenser. Detta följs av en dynamisk programmeringsberäkning av den förväntade noggrannheten för varje parvis inriktning. Probabilistisk konsistenstransformation används sedan för att omvärdera matchens noggrannhetspoäng., Ett styrträd beräknas med hierarkisk kluster med likheten definierad av ett vägt genomsnitt av värden mellan sekvenser av varje kluster. Styrträdet används för att anpassa sekvenserna med ett progressivt tillvägagångssätt. En efterbehandlingsfas görs också, där slumpmässiga bi-partitioner av den genererade inriktningen omformas för att kontrollera bättre inriktningsregioner. ProbCons skiljer sig från andra anpassningsprogram eftersom det inte innehåller biologiska begrepp som positionsspecifik gap scoring, evolutionär trädkonstruktion och andra funktioner som vanligtvis används av andra paket.,

Dialign-t version 0.2.1

det här programmet är en ny implementering av proceduren som utvecklats i Dialign2. 2, men med en bättre lösning för att hantera inkonsekventa fragment, inklusive fragmentkedjning. Det genomför också ett nytt tillvägagångssätt för att uppskatta sannolikheter för den slumpmässiga förekomsten av varje fragment som finns i sekvensen som ska anpassas. Dialign-T använder inte förberäknade tabeller för att få viktpoäng: den beräknar sannolikhetstabeller från flera substitutionsmatriser. Dessutom, den giriga-liknande flera inriktningsalgoritmen från Dialign2.,2 ändrades för att undvika falska lokala likheter.

Kalign version 1.04

Kalign är ett annat program som använder en progressiv inriktning metod för att få bästa MSA möjligt. Den största skillnaden i denna algoritm till andra metoder är att den använder Wu-Manber ungefärlig strängmatchningsalgoritm vid beräkning av avståndet mellan sekvenser. Wu-Manber-algoritmen mäter avståndet mellan två strängar med hjälp av ett Levenshtein-redigeringsavstånd, vilket möjliggör en effektiv sökning efter felaktigheter (delade eller inte) och mönster som finns i sekvenserna., Enligt Kalign-utvecklarna möjliggör denna metod en avståndsuppskattning som är lika snabb som en k-tuple-algoritm men är mer exakt . Det första steget i justeringsproceduren är att beräkna de parvisa avstånden med hjälp av WU-Manber-metoden. Den parvisa avståndsuppskattningen följs av en konstruktion av ett styrträd genom att använda UPGMA, som används i en global dynamisk programmeringsmetod för att anpassa sekvenserna/profilerna., Dessutom utför programmet en konsistenskontroll för att definiera den största uppsättningen sekvensmatcher som kan införas i justeringen, med hjälp av en modifierad version av Needleman-Wunsch för att hitta den mest konsekventa vägen genom den dynamiska programmeringsmatrisen. Kalign uppdaterar också positionerna för mönstermatchningar, som justerar den absoluta positionen för matcher som finns inom sekvenser till deras relativa positioner inom genererade profiler .