Bakgrund: Ett standardförfarande inom många områden av bioinformatik är att använda en enda multipel sekvens anpassning (MSA) som grund för olika typer av analys. Resultaten i senare led kan dock vara mycket känsliga för den anpassning som används, och om man bortser från osäkerheten i anpassningen kan det leda till betydande partiskhet i den resulterande slutsatsen. Under de senaste åren har ett antal metoder utvecklats för probabilistisk provtagning av anpassningar, snarare än att bara generera en enda optimal. Denna typ av probabilistisk information används dock för närvarande inte i någon större utsträckning i samband med slutsatsen i senare led, eftersom de flesta befintliga algoritmer har inrättats för att använda sig av en enda anpassning. Resultat: I detta arbete presenterar vi en ram för att representera en uppsättning av prover justeringar som en riktad acyklisk graf (DAG) vars noder är justering kolumner; varje väg genom denna DAG representerar sedan en giltig justering. Eftersom sannolikheten för enskilda kolumner kan uppskattas från empiriska frekvenser, möjliggör detta tillvägagångssätt en urvalsbaserad uppskattning av sannolikheterna för bakåtjustering. På grund av det villkorade oberoendet mellan kolumnerna kodar grafstrukturen dessutom en mycket större uppsättning justeringar än den ursprungliga uppsättningen provtagna MSA, så att den effektiva urvalsstorleken ökas avsevärt. Anpassningen DAG ger ett naturligt sätt att representera en distribution i utrymmet för MSA, och gör det möjligt för befintliga algoritmer att effektivt skalas upp för att fungera på stora uppsättningar av anpassningar. Som exempel visar vi hur detta kan användas för att beräkna marginell sannolikhet för trädtopologier, i genomsnitt över ett mycket stort antal MSA. Denna ram kan också användas för att generera en statistiskt meningsfull sammanfattande anpassning. Exempel på tillämpningar visar att denna sammanfattande anpassning konsekvent är mer exakt än majoriteten av anpassningsproven, vilket leder till förbättringar i efterföljande trädslutsatser. Genomförandet av de metoder som beskrivs i denna artikel finns på http://statalign.github.io/WeaveAlign. Sekvensjustering är ett av de mest intensivt studerade problemen inom bioinformatik, och är ett viktigt steg i ett brett spektrum av olika analyser, inklusive identifiering av bevarade motiv [1], analys av molekylär koevolution [2] [3] [4], uppskattning av fylogenier [5], och homologi-baserad proteinstruktur förutsägelse [6, 7].
Detta tillvägagångssätt ger en naturlig rymdfördelning av MSA för att göra den befintliga algoritmen för anpassning effektivare REF.
Efficient representation of uncertainty in multiple sequence alignments using directed acyclic graphs