PubMed Health⌕ Search
Home/Archive/PubMed

PubMed · 42635238

RSHash: a fast and space-efficient hash table for k-mers.

Jonas Schulte-Mattler·Knut Reinert
View original source ↗Export metadata ↓

Abstract

SUMMARY: Large genomic data collections can be viewed as a continuous string of DNA characters. The essential operations for data structures indexing the k-mer content of such a string are lookup and locate. Lookup determines whether a query k-mer q exists in the string and locate returns all locations in the string where q is present. High-throughput DNA sequencing generates very many k-mer sets of size exceeding billions of characters. In such scenarios, memory consumption and query efficiency pose significant challenges to a data structure supporting the above mentioned queries. To address this problem, we describe a simple, compressed, static data structure for k-mers that answers lookup and can be extended for supporting locate. The general scheme follows the use of minimizers like the state-of-the art SSHash. However, instead of using minimum perfect hash functions our solution (RSHash for Rank-Select Hash) relies on bitvectors with rank and select support, a multiple layered minimizer scheme, and a clever buffering strategy. We can show that RSHash is on average 40% and in some cases up to two times faster than SSHash while having the same memory requirements. Indeed we can go as low as 8 bits per canonical 31-mer on a human dataset. AVAILABILITY: https://github.com/jonsmcode/rshash.

Explore related subjects

Sequence Analysis, DNASoftwareAlgorithmsHigh-Throughput Nucleotide SequencingDNAGenomicsJournal Article

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Jonas Schulte-Mattler, Knut Reinert. 2026-08-01. RSHash: a fast and space-efficient hash table for k-mers.. https://doi.org/10.1093/bioinformatics%2Fbtag440

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

KEEP EXPLORING

Related citations

PubMed2026

OligoSeq: Rapid nanopore-sequencing of single-stranded oligonucleotides.

Nanopore-based DNA sequencing technology has achieved remarkable success in sequencing increasingly long DNA strands (e.g., over a million nucleotides long) for genomics research and biotechnology applications. However, the same level of progress has not been achieved for DNA oligonucleotides (usually ≤ 300 nucleotides long). Oligonucleotides play a crucial role in genome engineering efforts through oligo library generation and in DNA data storage, where they are used to encode computer information, such as binary (digital) data in DNA libraries. To enable these applications, accurate sequencing of oligonucleotides in a way that allows to assess for sequence variability, quality and length is essential. But sequencing solutions for oligonucleotides - particularly DNA primers for PCR, oligo DNA libraries used for mutagenesis or cDNA libraries used in gene expression analysis - remain inadequate. To address this gap, OligoSeq is presented as an innovative approach that integrates two complementary techniques: AmpliSeq (based on PCR) and RevSeq (based on reverse complementation with sequence-specific or random primers) to facilitate sequencing of single-stranded oligonucleotides using reference sequence anchor matches of more than ≥ 90% identity spanning from about 70% to 10% with AmpliSeq or RevSeq with random nonamers, respectively, and resolving the final reference sequence based on the most likely candidate from basecall frequencies, regardless of length and double-stranding method. OligoSeq can be integrated with nanopore sequencing technology pipelines and can be used as a reference for other sequencing platforms requiring double-stranded adapters, offering a practical and scalable alternative for standard quality control in single-stranded oligonucleotide synthesis. The use of nanopore technology, compatible with the double-stranding methods showcased, is shown to be the most cost-effective method for resolving original DNA sequences of different length and quality, and to assess its sequence variability, compared to other methods such as Illumina, PacBio or HPLC/MS.

Sequence Analysis, DNA↗
PubMed2026

Leveraging ONT move table values for signal aware variant calling.

Oxford Nanopore Technologies (ONT) sequencing enables long-range haplotype phasing and contiguous genome assembly but still exhibits elevated error rates that challenge small variant calling, particularly for insertions and deletions (Indels). While raw electrical signals contain rich information, existing signal-aware methods require computationally intensive processing of large signal files. Here, we present Clair3 v2, a method that leverages the ONT move table-a lightweight byproduct of basecalling that maps signal events to nucleotide positions-to improve variant calling accuracy. Clair3 v2 builds upon Clair3 and integrates signal-level dwelling time to significantly enhance variant calling performance. We also propose a genome position based circular buffer to incorporate dwelling time with minimal computational overhead. Benchmarking across six Genome in a Bottle samples demonstrates substantial improvements in variant calling accuracy. With HAC basecalling, Clair3 v2 achieves a mean SNP F1-score of 97.69% at 10 × depth (compared to 96.45% for baseline Clair3), and Indel F1 scores improved from 64.27% to 76.70%, while gains persisted at higher depths. The benefits were most pronounced for longer Indels and in complex genomic regions, where Indel F1 scores in long homopolymer regions improved from 14.3% to 45.2%. Benchmark results across various basecalling modes, samples, and coverage settings outperformed Clair3 baselines and other methods, including DeepVariant and Dorado Variant, and demonstrate the significant benefits of Clair3 v2. Furthermore, Clair3 v2 incurs negligible runtime compared to standard Clair3, making it practical for routine use.

Sequence Analysis, DNA↗
PubMed2026

Detecting and reconstructing breakage-fusion-bridge cycles from long-read sequencing using BFBArchitect.

MOTIVATION: Focal oncogene amplification is a key driver of tumor progression. Remarkably, the increased pathology depends on the context-whether the amplification is extrachromosomal (ecDNA) or intrachromosomal. EcDNA amplifications promote heterogeneity, therapy resistance, and poor prognosis. Focal intrachromosomal amplifications often arise through breakage-fusion-bridge (BFB) cycles, which produce highly rearranged but stable chromosomes. Distinguishing BFB from ecDNA remains challenging due to overlapping genomic signatures. To address this, we present BFBArchitect, a computational method leveraging long-read Oxford Nanopore data to identify BFB sequences consistent with both copy number and structural variations. RESULTS: We provide a novel combinatorial characterization of BFB, which naturally leads to an integer linear programming (ILP) optimization. The ILP optimization generates a BFB sequence that best explains experimentally observed copy numbers and foldback structural variants. We implement this idea in a tool called BFBArchitect, which achieves near-perfect accuracy in distinguishing BFB from non-BFB structures in extensive simulations as well as on 18 validated tumor samples. Moreover, it generates sequence-level BFB reconstructions that provide mechanistic insights into BFB formation, including repair mechanisms with template switching and other structural variants, and recapture of telomere for stabilization. AVAILABILITY AND IMPLEMENTATION: BFBArchitect is available at https://github.com/AmpliconSuite/BFBArchitect.

Sequence Analysis, DNA↗