Snabb statistisk justering
| Utvecklare | Robert Bradley ( UC Berkeley ), Colin Dewey ( UW Madison ), Lior Pachter ( UC Berkeley ) |
|---|---|
| Stabil frisättning | 1.5.2 |
| Operativ system | UNIX , Linux , Mac |
| Typ | Bioinformatikverktyg |
| Licens | Öppen källa |
FSA är ett program för multipelsekvensanpassning för att anpassa många proteiner eller RNA eller långa genomiska DNA-sekvenser. Tillsammans med MUSCLE och MAFFT är FSA ett av få sekvensanpassningsprogram som kan ställa in datauppsättningar med hundratals eller tusentals sekvenser. FSA använder ett annat optimeringskriterium som gör det möjligt att mer tillförlitligt identifiera icke-homologa sekvenser än dessa andra program, även om denna ökade noggrannhet kommer på bekostnad av minskad hastighet.
FSA används för närvarande för projekt inklusive sekvensering av nya maskgenom och analys av in vivo transkriptionsfaktorbindning i flugor.
Ingång/utgång
Detta program accepterar sekvenser i FASTA-format och matar ut justeringar i FASTA-format eller Stockholm-format .
Algoritm
Algoritmen för anpassningen av ingångssekvenserna har 4 kärnkomponenter.
Para Hidden Markov Model för att generera posteriora sannolikheter
Algoritmen börjar först med att bestämma posteriora sannolikheter för anpassning mellan två godtyckliga slumpmässiga sekvenser från poolen av sekvenser som ställs in. De bakre sannolikheterna för varje kolumn förstärker förutsägelsen av anpassningssannolikhet mellan ett sekvenspar och filtrerar även bort kolumner som kan vara otillförlitligt inriktade. Dessa sannolikheter tillåter också förutsägelse och uppskattning av homologi mellan vilket sekvenspar som helst. En standard fem-tillståndspar dold Markov-modell (Par HMM) används för att bestämma dessa posteriora sannolikheter för inriktning för två godtyckliga ingångssekvenser. Par-HMM-modellen använder två uppsättningar av tillstånden Delete (D) och Infoga (I) för att ta hänsyn till symbolborttagning och infogning mellan två inriktade sekvenser, men den kan också ha tre tillstånd utan en betydande förlust av noggrannhet.
Eftersom antalet parvisa jämförelser som behövs för att bestämma de bakre sannolikhetsfördelningarna för två sekvenspar är beräkningsmässigt dyrt och kvadratiskt i mängden sekvenser som justeras, minskas det genom att använda ett randomiserat tillvägagångssätt inspirerat av Erdos-Renyi-teorin om slumpmässiga grafer. Detta minskar avsevärt körtiderna för datamängder och beräkningskostnaden för att köra flera justeringar.
Sammanfogade sannolikheter
De bakre sannolikheterna för varje kolumn i sekvensparen sorteras med hjälp av en viktningsfunktion som använder en algoritm för den brantaste uppstigningen.
Sekvensglödgning
De flesta befintliga program som kör flera sekvensanpassningsalgoritmer är baserade på progressiv anpassning där processen börjar med en "nolljustering", ett tillstånd där ingen av sekvenserna har justerats. Poolen av sekvenser inpassas sedan antingen genom parvisa jämförelser eller genom en inriktning av ett par partiella inriktningar av undersekvenser. Denna process kan orsaka problem med anpassningen eftersom den resulterande multipelsekvensinriktningen kan och kommer att vara starkt beroende av sekvenserna som ställs in i början. Det finns ingen omanpassning av tidigare inriktade sekvenser som skulle kunna korrigera MSA.
FSA använder sekvensglödgningstekniken för att lösa detta problem. De sorterade posteriora sannolikheterna används med sekvensglödgningstekniken för att generera en multipel inriktning. Tekniken hittar anpassningen mellan två sekvenser som minimerar det förväntade avståndet till sanningen. I detta fall är avståndet mellan två sekvenser antalet kolumner där tecknet från en sekvens inte är homologt med tecknet i samma kolumn i den andra sekvensen.
Sekvensglödgningstekniken, genom att bestämma en inriktning med det minsta förväntade avståndet till sanningen, finner omvänt inriktningen med den maximala förväntade noggrannheten. Noggrannheten av en anpassning beror på en "sann" anpassning som referens och indikerar andelen kolumner där sekvenserna är homologa. Denna noggrannhet används sedan som en objektiv funktion som börjar med de ojusterade sekvenserna (nolljustering) och justerar tecken i olika kolumner baserat på den ökande noggrannheten hos en justering.
Beställning av uppriktningen
FSA ställer in flera sekvenser baserat på homologi inom kolumner istället för att strikt ta hänsyn till indelar och substitutioner. Som sådan anser FSA anpassningar vara ekvivalenta om för varje position längs sekvenserna i båda anpassningarna, samma uttalande om homologi kan göras. Till exempel när man överväger parvisa jämförelser, om det finns ett gap vid en specifik position i två anpassningar, så kan man säga att de två sekvenserna som jämförs inte är homologa vid nämnda position. Detta kan resultera i anpassningar där gap-open-händelser kan skilja sig åt och ändå anses vara likvärdiga. Som sådan väljer FSA att mata ut justeringen där det finns ett minimum av "gap-öppningar".
Parallellisering
För att hantera alltför stora datamängder kan FSA dela upp arbetet med att köra alla nödvändiga parvisa jämförelser och anpassningar till olika processorer. Detta hanteras genom att använda en "fast storlek chunking"-strategi som fördelar de parvisa jämförelserna till varje tillgänglig processor i bitar. Varje processor kan därför köra den bakre sannolikhetsberäkningen på en bit av parvisa jämförelser innan de sammanfogar den insamlade datan tillbaka till en enda processor för sekvensglödgning.
Visualisering
Resultaten av multipelsekvensanpassningen under FSA kan visas under FSA:s eget GUI. Det grafiska användargränssnittet kan visa och färgmärka olika mått på justeringens kvalitet på kolumnerna med tecken inom själva justeringen. De fem olika måtten som kan observeras och approximeras enligt FSA-modellen inkluderar noggrannhet, känslighet, säkerhet, specificitet och konsistens.
Jämförelser med andra anpassningsprogram
FSA har benchmarkats mot flera anpassningsdatabaser för protein (SABmark 1.65 och BAliBASE 3), RNA (BRAliBase 2.1 och Consanmix80) och DNA-sekvenser. Dessa riktmärken genomfördes tillsammans med andra populära anpassningsprogram som ClustalW, MAFFT, MUSCLE, T-Coffee, och så vidare. Sammantaget, vid den tidpunkt då FSA:s sammanfattning och forskningsdokument mottogs för granskning, överträffade FSA de flesta anpassningsprogram i noggrannhet och positiva prediktiva värden med känslighet i nivå med de bättre presterande programmen som MAFFT och ProbConsRNA. Körtidsjämförelser utfördes också genom att jämföra tidpunkterna för att anpassa 16S ribosomala sekvenser. MAFFT utförde anpassningen snabbare än de andra anpassningsprogrammen medan MUSCLE och FSA (med en 3-tillstånds HMM och med inaktiverad iterativ förfining) var de näst snabbaste programmen.
Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L (2009). "Snabb statistisk justering" . PLOS Computational Biology . 5 (5): e1000392. Bibcode : 2009PLSCB...5E0392B . doi : 10.1371/journal.pcbi.1000392 . PMC 2684580 . PMID 19478997 .
Schwartz AS, Pachter L (2007) Multipel anpassning genom sekvensglödgning. Bioinformatik 23: e24-9.
Eddy SR. Flera justeringar med dolda Markov-modeller. Proc Int Conf Intell Syst Mol Biol. 1995;3:114-20. PMID: 7584426.