BWA-backtrack je založen na backtrackingu. Tento přístup je vhodný pouze v případě, že rozdílnost mezi čtením a odkazem je nízký, nebo pokud chcete najít všechny nejlepší zásahy nebo vyjmenovat všechna možná zarovnání až na zadaný počet chyb.
Ve všech ostatních situacích je BWA-MEM díky své propracované strategii výhodnější, jak může. na základě maximálních přesných shod řešit chyby lépe a také automaticky přepínat mezi režimy místního a globálního zarovnání.
Dlouhý popis:
Chtěl bych poskytnout některé algoritmický vhled, protože se domnívám, že to v tomto případě může být velmi užitečné. BWA-backtrack i BWA-MEM používají stejnou strategii indexování (silně se spoléhající na BWT-index), ale skutečné algoritmy jsou zcela odlišné.
BWT-index (a také další fulltextové indexy, například pole přípon nebo stromy přípon) mohou snadno najít přesné shody (představte si Ctrl + F-like search in a text editor), but any d Pokud rozdíly mezi čtením a odkazem, jako jsou chyby sekvenování nebo genomické varianty, situaci komplikují. Jeden pak musí nějakým způsobem transformovat nepřesnou shodu na přesnou shodu a všechny tři mapovače BWA (všimněte si, že existuje také BWA-SW, ale je zastaralý) používají zcela odlišné strategie.
BWA-backtrack hledá podřetězce odkazu, které by byly podobné celému čtení (end-to-end) pomocí algoritmu backtracking. Nejprve vyhledává výskyty čtení bez jakýchkoli „oprav“. Pokud se nic nenašlo, zohlední se všechny možné jednotlivé úpravy; pak dvě úpravy atd. Aby bylo mapování efektivní, jeden obvykle chce skončit s prvním nalezeným zarovnáním, protože by to bylo nejlepší. V případě potřeby je také možné najít další stejně dobré zarovnání nebo vyjmenovat všechna zarovnání až po nějakou úpravu vzdálenost nebo přesáhne určitou odchylku (viz volba -N u BWA-backtrack).
Ukázalo se, že
čas potřebný k nalezení zarovnání může být v počtu chyb exponenciální, což je pravděpodobně hlavní problém přístupů založených na zpětném sledování. Aby se zabránilo velkým režijním nákladům v důsledku odlišných čtení, je třeba omezit počet povolených chyb na nějaký rozumný počet (viz maxDiff na BWA man page) a zvažte, že ostatní čte nezarovnané. V případě BWA-backtrack je minimální požadovaná úroveň identity ~ 97% s výchozími možnostmi (viz možnost -n).
Algoritmus je ve skutečnosti komplikovanější a používá různé heuristiky, jako je seed-and-extend nebo Z-dropoff, aby byl výpočet dostatečně rychlý (za cenu nižší přesnosti). Pokud vás zajímá více podrobností, všechny tyto triky jsou dobře popsány v příspěvku.
BWA-MEM používá zcela jinou strategii. Detekuje dlouhé přesné shody mezi čtením a odkazem a poté je zřetězí do místního nebo globálního zarovnání na základě toho, co je v konkrétním případě vhodnější.Takové automatické přepínání mezi místními a globálními může být velmi silné a BWA-MEM funguje dobře s různými typy dat (krátká čtení, dlouhá čtení, nízká chybovost, vysoká chybovost atd.).