Algorithms and Data Compression

Reference normalizations of Effort-To-Compress across length, alphabet size, and composition

The paper introduces normalized versions of Effort-To-Compress (ETC) to enable fair comparisons of symbolic complexity across different sequence lengths, alphabet sizes, and compositions.

biHash: bisulfite-aware recursive nucleotide hashing

biHash is a rolling hash algorithm designed for bisulfite-sequenced data, offering faster hashing by recognizing bisulfite-compatible sequence states.

Minimizer Density revisited: Models and Multiminimizers

This paper revisits the concept of density in k-mer-based sequence analysis, introduces multiminimizers as a novel technique, and proposes deduplicated density as a new metric.

Pareto optimization of masked superstrings improves compression of pan-genome k-mer sets

This paper introduces a Pareto optimization method for masked superstrings to improve the compression of pan-genome k-mer sets, achieving 12-19% better compressibility.

Super Bloom: Fast and precise filter for streaming k-mer queries

The paper introduces Super Bloom, a Bloom filter variant for streaming k-mer queries, which improves cache efficiency and reduces false positives.

Generating minimum-density minimizers

This paper introduces an algorithm to compute minimum-density minimizers for high-throughput sequencing, achieving faster results than brute-force methods.

Byte-exact, format-aware compression for FASTA, FASTQ, BED and VCF files

NYX provides fast, lossless compression for common omics data formats, achieving better compression ratios and speed than existing codecs.

Lossless compression of protein databases for efficient and accurate metagenomic sequence classification with Centrifuger

The paper introduces a lossless compression algorithm for protein databases, improving memory efficiency and classification accuracy in Centrifuger for metagenomic analysis.

Optimized Multiple Circular Sequence Alignment for Cyclic Peptide Motif Discovery

The paper optimizes multiple circular sequence alignment for cyclic peptides, achieving faster performance while maintaining alignment quality.

Dynamic Hierarchical Interleaved Bloom Filter: An Updatable Index for Large-Scale Fast Sequence Search

This paper introduces a dynamic and updatable sequence-search index called Dynamic HIBF, which efficiently handles large-scale data updates and outperforms existing methods in speed.

Binary search and set operations on compacted k-mer lists

The paper introduces a method to perform set operations on k-mers using compacted representations, achieving efficient memory usage and high throughput.

Accelerating String Comparison in RLZ Compressed Sequences via LCE Jumps

This paper introduces an algorithmic framework for comparing and sorting RLZ compressed sequences, achieving speedups over character-based sorting.

Lossless compression of k-mer matrices enabling random row access

The paper introduces kmcomp, a lossless compression method for k-mer matrices that enables fast random access, achieving significant storage savings with minimal query overhead.

Optimizing sparse and skew hashing: faster k-mer dictionaries

The paper introduces an optimized sparse and skew hashing data structure for efficient k-mer representation, showing improved query speed and space efficiency compared to existing methods.

RLBWT-Based LCP Computation in Compressed Space for Terabase-Scale Pangenome Analysis

The paper introduces algorithms for constructing RLBWT-based compressed full text indexes in compressed space, reducing memory usage for large-scale pangenome analysis.

Accelerating k-mer-based sequence filtering

The paper introduces K2Rmini, a tool that efficiently filters sequences based on k-mer matches, achieving 2 Gbp/s on a consumer laptop.

DynamicDemiLog: A Single Sketch for Ultrafast Similarity, Frequency, and Cardinality Estimation

DynamicDemiLog (DDL) is a unified sketch that estimates cardinality, similarity, frequency, and composition efficiently, outperforming existing methods in speed and accuracy.

Movi 2: Fast and Space-Efficient Queries on Pangenomes

Movi 2 improves pangenome indexing by reducing memory footprint and enabling space-time tradeoffs for efficient querying.

A run-length-compressed skiplist data structure for dynamic GBWTs supports time and space efficient pangenome operations over syncmers

DNA Compression with Genomic Language Models: Tokenization, Benchmarking, and an Information-Content Map

The paper evaluates genomic language models as DNA compressors, finds smaller vocabularies perform better, and maps information content across the human genome.

Lossless Pangenome Indexing Using Tag Arrays

The paper introduces a lossless indexing framework for pangenome graphs using tag arrays, enabling efficient haplotype-aware querying and coordinate translation across haplotypes.

Fast Set Operations for Compact k-mer Sets

The paper introduces efficient set operations for SBWT-encoded k-mer spectra, enabling memory-efficient processing of large genomic datasets.

Read-Consistent Minimum Unique Substrings: A Parameter-Free, Linear-Time Framework for Genomic Sequence Representation

This paper introduces Minimum Unique Substrings (MUSs) as a parameter-free, linear-time framework for genomic sequence representation, showing improved coverage and resolution compared to fixed-length k-mers.

Highly efficient genotype compression leveraging genealogical relatedness

The paper introduces a lossless compression method for genotype data using genealogical relatedness, achieving significant size reduction and speedup in genetic analyses.

Sassy: Fuzzy Searching DNA Sequences using SIMD

Sassy is a fast approximate string matching tool for DNA sequences, achieving significant speedups over existing methods for small error tolerances and applied to CRISPR off-target detection.

Rapid-PFP: Accelerating Prefix-Free Parsing with GPU Parallelism

RAPID-PFP accelerates Prefix-Free Parsing using GPU parallelism, achieving significant speedups on genomic datasets compared to CPU implementations.

Singletrack: An Algorithm for Improving Memory Consumption and Performance of Gap-Affine Sequence Alignment

Singletrack improves memory efficiency and performance for gap-affine sequence alignment without sacrificing accuracy.

Why phylogenies compress so well: combinatorial guarantees under the Infinite Sites Model

The paper explains why phylogenetic compression works well by introducing a formal framework and showing that Neighbor Joining achieves near-optimal compression under the Infinite Sites Model.

10-minimizers: a promising class of constant-space minimizers

This paper introduces 10-minimizers, a class of constant-space minimizers with lower density than random minimizers and efficient k-mer key retrieval.

New Space-Time Tradeoffs for Subset Rank and k-mer Lookup

This paper introduces faster subset rank data structures for k-mer lookup with reduced space usage, achieving Pareto optimal performance in memory and time.