Hierarchical Interleaved Bloom Filter: enabling ultrafast, approximate sequence queries

We present a novel data structure for searching sequences in large databases: the Hierarchical Interleaved Bloom Filter (HIBF). It is extremely fast and space efficient, yet so general that it could serve as the underlying engine for many applications. We show that the HIBF is superior in build time...

Full description

Saved in:
Bibliographic Details
Published in:Genome Biology 2023-05, Vol.24 (1), p.131-131, Article 131
Main Authors: Mehringer, Svenja, Seiler, Enrico, Droop, Felix, Darvish, Mitra, Rahn, René, Vingron, Martin, Reinert, Knut
Format: Article
Language:English
Subjects:
Algorithms
Alignment free analysis
Approximate membership query
Bloom filter
Datasets
Genomes
Metagenomics
Method
Miminizer
Queries
Sequence search
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a novel data structure for searching sequences in large databases: the Hierarchical Interleaved Bloom Filter (HIBF). It is extremely fast and space efficient, yet so general that it could serve as the underlying engine for many applications. We show that the HIBF is superior in build time, index size, and search time while achieving a comparable or better accuracy compared to other state-of-the-art tools. The HIBF builds an index up to 211 times faster, using up to 14 times less space, and can answer approximate membership queries faster by a factor of up to 129.
ISSN:1474-760X
1474-7596
1474-760X
DOI:10.1186/s13059-023-02971-4