Motivering: K-mer-baserade algoritmer har blivit allt populärare vid bearbetning av data med hög genomströmningssekvensering (HTS). Dessa algoritmer spänner gapet av analys pipeline från k-mer räkning (t.ex. för att uppskatta montering parametrar), till felkorrigering, genom och transkriptome sammansättning, och även transkript kvantifiering. Men dessa uppgifter använder ofta mycket olika k-mer representationer och datastrukturer. I detta dokument beskriver vi de grundläggande operationerna för att upprätthålla multiuppsättningar av k-mers och klassificera befintliga system ur ett datastrukturellt perspektiv. Vi visar sedan hur man bygger ett K-mer-counting och multiset-representationssystem med hjälp av counting quotient filter (CQF), en funktionsrik ungefärlig medlemsfråga (AMQ) datastruktur. Vi introducerar K-mer-counting/querying-systemet Squeaker (Enkel Quotient filterbaserad Exakt och Ungefärlig Kmer Representation), som är baserat på CQF. Denna datastruktur utanför hyllorna visar sig vara en effektiv (ungefärlig eller exakt) representation för uppsättningar eller multiuppsättningar av k-mers. Resultat: Squeaker tar 2×-4.3× mindre tid än state-of-the-art att räkna och utföra en slumpmässig pointquery arbetsbelastning. Squeaker är minneseffektiv och förbrukar 1,5X-4,3X mindre minne än toppmodern. Det erbjuder konkurrenskraftig beräkning prestanda, och svar punkt frågor (dvs. frågor om överflödet av en viss k-mer) över en ordning-av-magnitud snabbare än andra system. Den Squeakr representation av k-mer multiset visar sig vara omedelbart användbart för nedströms bearbetning (t.ex. de Bruijn graf traversal) eftersom det stöder snabba frågor och dynamisk k-mer insättning, borttagning och modifiering. Tillgänglighet: https://github.com/splatlab/squeaker Kontakt:
K-mer-kartläggningen är byggd av CQF som konstruerats av Squeaker REF, ett k-mer-räkningsverktyg.
Squeakr: An Exact and Approximate k-mer Counting System
{'venue': None, 'journal': 'bioRxiv', 'mag_field_of_study': ['Computer Science', 'Biology']}