Bloomovy filtry v bioinformatice - Bloom filters in bioinformatics

Bloom filtry jsou prostorově efektivní pravděpodobnostní datové struktury slouží k otestování, zda je prvek součástí sady. Bloom filtry vyžadují mnohem méně prostoru než jiné datové struktury pro reprezentaci sad, avšak nevýhodou Bloomových filtrů je, že existuje míra falešně pozitivních výsledků při dotazování na datovou strukturu. Vzhledem k tomu, že několik prvků může mít stejné hodnoty hash pro řadu hash funkcí, je pravděpodobné, že dotazování na neexistující prvek může vrátit klad, pokud byl do filtru Bloom přidán jiný prvek se stejnými hodnotami hash. Za předpokladu, že hashovací funkce má stejnou pravděpodobnost výběru libovolného indexu Bloomova filtru, je falešná kladná rychlost dotazování Bloomova filtru funkcí počtu bitů, počtu hashovacích funkcí a počtu prvků Bloomova filtru. To umožňuje uživateli řídit riziko získání falešně pozitivního výsledku kompromitováním prostorových výhod filtru Bloom.

Bloom filtry se primárně používají v bioinformatice k testování existence a k-mer v sekvenci nebo sadě sekvencí. K-mery sekvence jsou indexovány v Bloom filtru a jakýkoli k-mer stejné velikosti lze dotazovat proti Bloom filtru. Toto je výhodnější alternativa k hashování k-mery sekvence s a hash tabulka, zvláště když je sekvence velmi dlouhá, protože je velmi náročné ukládat do paměti velké množství k-merů.

Aplikace

Charakterizace sekvence

Vizualizace dotazování Bloomova filtru k-merů sekvence DNA. Prvním krokem je uložení k-merů sekvence do Bloomova filtru. Dotazování se provádí podobně, když je sekvence dotazu rozdělena na odpovídající k-mery a k-mery se používají k dotazování Bloomova filtru.

Krok předzpracování v mnoha bioinformatických aplikacích zahrnuje klasifikaci sekvencí, primárně klasifikaci čtení z a Sekvenování DNA experiment. Například v metagenomické studie je důležité vědět, zda sekvenční čtení patří novému druhu.^[1] a v projektech klinického sekvenování je životně důležité odfiltrovat čtení z genomů kontaminujících organismů. Existuje mnoho nástrojů pro bioinformatiku, které používají Bloomovy filtry ke klasifikaci čtení dotazováním k-merů čtení na sadu Bloomových filtrů generovaných ze známých referenční genomy. Některé nástroje, které používají tuto metodu, jsou FACS^[2] a nástroje BioBloom.^[3] I když tyto metody nemusí překonat jiné nástroje pro klasifikaci bioinformatiky, jako je Kraken,^[4] nabízejí alternativu efektivní z hlediska paměti.

Nedávná oblast výzkumu s Bloomovými filtry v charakterizaci sekvence je ve vývoji způsobů dotazování surových čtení ze sekvenčních experimentů. Například, jak lze určit, která čtení obsahují konkrétní 30mer v celém NCBI Archiv čtení sekvence ? Tento úkol je podobný tomu, kterého je dosaženo pomocí VÝBUCH, nicméně zahrnuje dotazování mnohem větší datové sady; zatímco BLAST dotazy na databázi referenčních genomů, tento úkol vyžaduje vrácení konkrétních čtení, která obsahují k-mer. BLAST a podobné nástroje nemohou tento problém efektivně zvládnout, proto byly za tímto účelem implementovány datové struktury založené na Bloom filtru. Binární květinové stromy^[5] jsou binární stromy Bloomových filtrů, které usnadňují dotazování na přepisy ve velkém RNA sekvence experimenty. VELKÉ^[6] půjčuje si bitcovité podpisy z oblasti načítání dokumentů indexovat a dotazovat se na veškerá data o mikrobiálním a virovém sekvenování v souboru Evropský archiv nukleotidů. Podpis dané datové sady je zakódován jako sada Bloomových filtrů z této datové sady.

Sestavení genomu

Porovnání hashovací tabulky a Bloomova filtru pro uložení de Bruijnova grafu do paměti. Všimněte si, že zatímco informace o hraně mohou být zachovány v hašovací tabulce, nejsou uloženy ve filtru Bloom, což komplikuje procházení grafu. Filtr Bloom stejné velikosti jako hashovací tabulka bude i nadále využívat méně místa, protože neukládá hodnoty samotných k-merů.

Účinnost paměti filtrů Bloom byla použita v shromáždění genomu jako způsob, jak snížit prostorovou stopu k-merů ze sekvenování dat. Přínosem montážních metod založených na Bloomových filtrech je kombinace Bloomových filtrů a de Bruijn grafy do struktury zvané pravděpodobnostní de Bruijnův graf,^[7] který optimalizuje využití paměti za cenu falešně pozitivních hodnot inherentních filtrům Bloom. Namísto uložení de Bruijnova grafu v hašovací tabulce je uložen ve filtru Bloom.

Použití Bloomova filtru k uložení de Bruijnova grafu komplikuje krok přechodu grafu k sestavení sestavy, protože informace o okraji nejsou ve Bloomově filtru zakódovány. Traversal grafu se provádí dotazem na Bloomův filtr pro kterýkoli ze čtyř možných následných k-merů z aktuálního uzlu. Například pokud je aktuální uzel pro k-mer ACT, pak další uzel musí být pro jeden z k-mer CTA, CTG, CTC nebo CTT. Pokud ve filtru Bloom existuje k-mer dotazu, pak se k cestě přidá k-mer. Proto existují dva zdroje falešných poplachů při dotazování Bloomova filtru při procházení de Bruijnova grafu. Existuje pravděpodobnost, že jeden nebo více ze tří falešných k-merů existuje jinde v sadě sekvencování pro vrácení falešně pozitivního, a existuje výše uvedená inherentní míra falešných pozitivů samotného filtru Bloom. Montážní nástroje, které používají Bloomovy filtry, musí ve svých metodách tyto zdroje falešných poplachů zohledňovat. ABySS 2^[8] a Minia^[9] jsou příklady assemblerů, které tento přístup používají de novo shromáždění.

Oprava chyby sekvenování

Sekvenování nové generace Metody (NGS) umožnily generování nových sekvencí genomu mnohem rychleji a levněji než předchozí Sangerovo sekvenování metody. Tyto metody však mají vyšší chybovost,^[10][11] což komplikuje následnou analýzu sekvence a může dokonce vést k chybným závěrům. Bylo vyvinuto mnoho metod k opravě chyb ve čtení NGS, ale využívají velké množství paměti, což je činí nepraktickými pro velké genomy, jako je lidský genom. Proto byly vyvinuty nástroje využívající Bloom filtry k řešení těchto omezení, využívajících výhod jejich efektivního využití paměti. Mušketa^[12] a BLESS^[13] jsou příklady takových nástrojů. Obě metody používají pro korekci chyb přístup k-merního spektra. Prvním krokem tohoto přístupu je spočítat multiplicitu k-merů, avšak zatímco BLESS používá k ukládání počtů pouze Bloomovy filtry, Musket používá Bloomovy filtry pouze k počítání jedinečných k-merů a ne-jedinečné k-mery ukládá do hash tabulka, jak je popsáno v předchozí práci^[14]

RNA-sekv

V některých jsou také použity filtry Bloom RNA-sekv potrubí. RNA-Skim^[15] shluky RNA přepisy a poté pomocí Bloomových filtrů najde sig-méry: k-mery, které se nacházejí pouze v jednom z klastrů. Tyto signály se poté použijí k odhadu úrovní hojnosti přepisu. Proto neanalyzuje všechny možné k-mer, které vedou ke zlepšení výkonu a využití paměti, a ukázalo se, že funguje stejně jako předchozí metody.

Reference