Search bioRxiv⌕ Search
Home/Archive/bioRxiv

bioRxiv · 10.1101/2022.08.01.502266

Hierarchical Interleaved Bloom Filter: Enabling ultrafast, approximate sequence queries

Mehringer, S.·Seiler, E.·Droop, F.·Darvish, M.·Rahn, R.·Vingron, M.·Reinert, K.
View original source ↗Export metadata ↓

Abstract

Searching sequences in large, distributed databases is the most widely used bioinformatics analysis done. This basic task is in dire need for solutions that deal with the exponential growth of sequence repositories and perform approximate queries very fast. In this paper, we present a novel data structure: the Hierarchical Interleaved Bloom Filter (HIBF). It is extremely fast and space efficient, yet so general that it has the potential to 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 (Mantis and Bifrost). 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. This can be considered a quantum leap that opens the door to indexing complete sequence archives like the European Nucleotide Archive or even larger metagenomics data sets.

Source connections

Explore related subjects

bioinformaticsPreprint

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Mehringer, S., Seiler, E., Droop, F., Darvish, M., Rahn, R., Vingron, M., Reinert, K.. 2022-08-01. Hierarchical Interleaved Bloom Filter: Enabling ultrafast, approximate sequence queries. https://doi.org/10.1101/2022.08.01.502266

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related preprints

bioRxiv2026

Accelerating discovery and integration from RNA to Protein with R2T2P

Integrating transcriptomics and proteomics data remains an unmet challenge in the post-genomics era, discouraging researchers from pursuing integrative approaches to molecular biology research. Leveraging the power of translation profiling, we present RNA to Translation to Protein (R2T2P), a computational platform integrating genome-guided transcriptome assembly with identification of translation and proteins, including a tailored differential analysis framework and support for multiple reference transcriptomes. We applied R2T2P to investigate a cellular model of facioscapulohumeral muscular dystrophy (FSHD), where ectopic expression of the DUX4 retrogene in skeletal muscle triggers significant alterations in transcription and RNA metabolism. We uncovered hundreds of uncharacterized, highly overexpressed RNAs, including antisense and alternative transcripts, and quantified their contribution to translatome and proteome. Re-analysis of expression datasets from patient-derived myotubes and muscle biopsies validated this alternative transcriptome in FSHD patients, adding a reservoir of bona-fide novel molecular actors in a rare disease. Available at https://github.com/nfdata-omics/R2T2P/, R2T2P is a flexible and powerful workflow in modern integrative biology.

bioinformatics↗
bioRxiv2026

MorphoANOVA: Dissecting Histology-Gene Expression Relationships in Spatial Transcriptomics

Spatial transcriptomics (ST) measures the expression of hundreds to thousands of genes within tissue architecture, often accompanied by histology images. However, it remains challenging to systematically characterize which genes exhibit associations with tissue morphology, whether these associations vary spatially, and which genes show additional spatial expression patterns beyond those captured by morphology. Here we introduce MorphoANOVA, a gene-wise statistical framework for characterizing morphology--expression relationships across genes measured by ST. Using nested spatially varying coefficient models and sequential ANOVA, MorphoANOVA assesses slide-wide associations with an H\&E-derived morphology feature, location-specific changes in these associations, and additional spatial variation after accounting for the selected feature. The resulting statistics enable gene prioritization and pathway enrichment analysis, while spatial component maps support the interpretation of individual genes. Simulations demonstrate MorphoANOVA's ability to distinguish the modeled components and recover their spatial patterns. Applications to human cortex and breast cancer identify biological programs associated with different morphology--expression patterns and reveal distinct relationships with cell composition. Across three HER2-positive breast cancer patients, invasive-cancer marker genes consistently exhibit stronger evidence of location-specific morphology associations. MorphoANOVA thus provides a framework for systematically interpreting spatial gene-expression patterns in relation to tissue morphology.

bioinformatics↗
bioRxiv2026

Evaluation effects can rival reported concordance gains in cross-cancer survival prediction

Studies of cross-cancer learning for survival prediction from tumour omics have reported concordance gains of 0.020 and 0.045, but how such gains compare with evaluation effects remains unclear. We examined these effects across 13 TCGA cancers (5,761 patients, 1,526 disease-specific deaths), using five repeats of five-fold cross-validation and paired bootstrap intervals. When model selection did not use test data, our borrowing model gained 0.009 (95% interval 0.001 to 0.016) over its target-fitted reference when cancers received equal weight (post hoc). Random-effects pooling gave a gain of 0.002 (-0.002 to 0.006), with most weight assigned to cancers where the model made little use of the pretrained score. Choosing the fusion weight on test splits raised the apparent equal-weight gain to 0.017. We reimplemented a published method, VAECox, which showed no pretraining gain over random initialisation at the last or validation-selected training step. Choosing each network's best test step, as the published code does, raised concordance by 0.03 to 0.05 across the 13-cancer and ten-cancer overall-survival settings, but barely changed the difference between networks. In a constructed post hoc experiment, choosing the best test step only for the pretrained network changed the equal-weight mean difference from -0.004 to +0.045 (+0.035 to +0.054). Across seven multi-omics comparisons, estimates from single five-fold runs differed from their cancer's five-run mean by at least 0.02 in 11% to 42% of runs. Concordance was about 0.02 lower at held-out tissue source sites. Interpreting a reported gain therefore requires each model's selection rule, variation across repeated partitions, the weighting of cancers and the evaluation population.

bioinformatics↗