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...

Descripción completa

Detalles Bibliográficos
Autores principales: Mehringer, Svenja, Seiler, Enrico, Droop, Felix, Darvish, Mitra, Rahn, René, Vingron, Martin, Reinert, Knut
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2023
Materias:
Method
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10230713/
https://www.ncbi.nlm.nih.gov/pubmed/37259161
http://dx.doi.org/10.1186/s13059-023-02971-4
_version_ 1785051594257072128
author Mehringer, Svenja
Seiler, Enrico
Droop, Felix
Darvish, Mitra
Rahn, René
Vingron, Martin
Reinert, Knut
author_facet Mehringer, Svenja
Seiler, Enrico
Droop, Felix
Darvish, Mitra
Rahn, René
Vingron, Martin
Reinert, Knut
author_sort Mehringer, Svenja
collection PubMed
description 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. SUPPLEMENTARY INFORMATION: The online version contains supplementary material available at 10.1186/s13059-023-02971-4.
format Online
Article
Text
id pubmed-10230713
institution National Center for Biotechnology Information
language English
publishDate 2023
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-102307132023-06-01 Hierarchical Interleaved Bloom Filter: enabling ultrafast, approximate sequence queries Mehringer, Svenja Seiler, Enrico Droop, Felix Darvish, Mitra Rahn, René Vingron, Martin Reinert, Knut Genome Biol Method 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. SUPPLEMENTARY INFORMATION: The online version contains supplementary material available at 10.1186/s13059-023-02971-4. BioMed Central 2023-05-31 /pmc/articles/PMC10230713/ /pubmed/37259161 http://dx.doi.org/10.1186/s13059-023-02971-4 Text en © The Author(s) 2023 https://creativecommons.org/licenses/by/4.0/Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) . The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/ (https://creativecommons.org/publicdomain/zero/1.0/) ) applies to the data made available in this article, unless otherwise stated in a credit line to the data.
spellingShingle Method
Mehringer, Svenja
Seiler, Enrico
Droop, Felix
Darvish, Mitra
Rahn, René
Vingron, Martin
Reinert, Knut
Hierarchical Interleaved Bloom Filter: enabling ultrafast, approximate sequence queries
title Hierarchical Interleaved Bloom Filter: enabling ultrafast, approximate sequence queries
title_full Hierarchical Interleaved Bloom Filter: enabling ultrafast, approximate sequence queries
title_fullStr Hierarchical Interleaved Bloom Filter: enabling ultrafast, approximate sequence queries
title_full_unstemmed Hierarchical Interleaved Bloom Filter: enabling ultrafast, approximate sequence queries
title_short Hierarchical Interleaved Bloom Filter: enabling ultrafast, approximate sequence queries
title_sort hierarchical interleaved bloom filter: enabling ultrafast, approximate sequence queries
topic Method
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10230713/
https://www.ncbi.nlm.nih.gov/pubmed/37259161
http://dx.doi.org/10.1186/s13059-023-02971-4
work_keys_str_mv AT mehringersvenja hierarchicalinterleavedbloomfilterenablingultrafastapproximatesequencequeries
AT seilerenrico hierarchicalinterleavedbloomfilterenablingultrafastapproximatesequencequeries
AT droopfelix hierarchicalinterleavedbloomfilterenablingultrafastapproximatesequencequeries
AT darvishmitra hierarchicalinterleavedbloomfilterenablingultrafastapproximatesequencequeries
AT rahnrene hierarchicalinterleavedbloomfilterenablingultrafastapproximatesequencequeries
AT vingronmartin hierarchicalinterleavedbloomfilterenablingultrafastapproximatesequencequeries
AT reinertknut hierarchicalinterleavedbloomfilterenablingultrafastapproximatesequencequeries

Ejemplares similares