Algorithms and Data Compression

Optimized k-mer search across millions of bacterial genomes on laptops

The paper develops Phylign-Fulgor, a method for efficient k-mer search across millions of bacterial genomes on laptops, improving speed and reducing memory usage compared to existing tools.

Compressed inverted indexes for scalable sequence similarity

The paper introduces Onika, a system using inverted indexes for efficient sequence similarity search, improving scalability and performance over existing tools.

MaxGeomHash: An Algorithm for Variable-Size Random Sampling of Distinct Elements

The paper introduces a new sketching algorithm for genomic sequences that produces sub-linear sketches, balancing efficiency and accuracy between MinHash and FracMinHash.

Optimizing Genomic Data Compression with Genetic Algorithms

This paper optimizes genomic sequence compression using genetic algorithms, achieving high compression rates on large datasets like the human genome.

Efficient Grammar Compression via RLZ-based RePair

The paper introduces RLZ-RePair, a method that combines RLZ parsing with RePair to create efficient grammar-based compression with reduced memory usage and comparable performance to standard RePair.

Efficiency of Learned Indexes on Genome Spectra

The paper introduces CaPLa, a measure to predict the performance of learned indexes on genomic k-mer data, showing it varies across genomes and can predict space bounds.

Human readable compression of GFA paths using grammar-based code

The paper introduces a grammar-based compression method for GFA haplotype paths, improving storage efficiency and runtime for pangenome graph analyses.

Movi Color: fast and accurate long-read classification with the move structure

Movi Color improves long-read classification accuracy and speed using a move structure and color-based indexing, outperforming existing methods in precision and recall.

Partitioned Multi-MUM finding for scalable pangenomics

The paper extends the Mumemto tool to compute multi-MUMs across large pangenomes using new partitioning strategies, enabling scalability to 474 human haplotypes.

Sequence alignment with k-bounded matching statistics

This paper introduces a novel algorithm for approximate local alignment search using k-bounded matching statistics, showing it is as fast and accurate as state-of-the-art tools in bacterial genomics tasks.

The small genomics lab experience optimizing data cold storage

The paper evaluates compression algorithms for reducing cold storage costs in small genomics labs, finding zstandard provides better space savings than gzip.

Dynamic μ-PBWT: Dynamic Run-length Compressed PBWT for Biobank Scale Data

This paper introduces Dynamic μ-PBWT, a memory-efficient data structure for dynamic updates of haplotype panels, supporting efficient queries and reducing memory usage compared to existing methods.

Haplotype Matching with GBWT for Pangenome Graphs

This paper defines haplotype matches in pangenome graphs and provides efficient algorithms for querying them using GBWT and related data structures.

Faster and Scalable Parallel External-Memory Construction ofColored Compacted de Bruijn Graphs with Cuttlefish 3

Cuttlefish 3 is a parallel external-memory algorithm for constructing colored compacted de Bruijn graphs, achieving significant speedup over existing tools.

SimdMinimizers: Computing random minimizers, fast

The paper introduces a fast library for computing random minimizers using SIMD instructions, achieving significant speed improvements over existing methods.

Brisk: Exact resource-efficient dictionary for k-mers

This paper introduces Brisk, a resource-efficient k-mer dictionary that reduces memory usage and improves throughput compared to existing methods.

Hyper-k-mers: efficient streaming k-mers representation

The paper introduces hyper-k-mers, a more efficient k-mer representation, and presents KFC, a tool that significantly reduces memory usage and improves speed for k-mer counting.

A near-tight lower bound on the density of forward sampling schemes

The paper establishes a near-tight lower bound on the density of forward sampling schemes and shows existing schemes are closer to optimal than previously thought.

A fast and simple approach to k-mer decomposition

The paper introduces a fast and simple method for k-mer decomposition using an integer representation to enable constant-time sequence processing.

Recursive RePair: Increasing the Scalability of RePair by Decreasing Memory Usage

This paper introduces Re2Pair, a modified RePair algorithm that reduces memory usage and improves speed for compressing large genomic datasets.

Constrained enumeration of k-mers from a collection of references with metadata

The paper introduces a framework to efficiently enumerate k-mers from a collection of references based on metadata constraints, using a specialized data structure and demonstrating it on microbial and RNA-seq data.

The mod-minimizer: a simple and efficient sampling algorithm for long k-mers

The paper introduces the mod-minimizer, a sampling algorithm that improves k-mer density over existing methods for large k and w, achieving optimal density as k approaches infinity.

Cliffy: robust 16S rRNA classification based on a compressed LCA index

Cliffy improves 16S rRNA classification by reducing index size and increasing accuracy compared to Kraken2 and Bracken.

MEM-based pangenome indexing for k-mer queries

The paper introduces MEMO, a pangenome indexing method that efficiently handles k-mer queries and conservation analysis across pangenomes.

A*PA2: up to 20 times faster exact global alignment

A*PA2 is an exact global aligner that achieves up to 20x faster runtime than existing methods on long reads with high divergence.

GeneSqueeze: A Novel Lossless, Reference-Free Compression Algorithm for FASTQ/A Files

GeneSqueeze is a lossless, reference-free compression algorithm for FASTQ/A files that achieves higher compression ratios than gzip and SPRING while preserving data integrity.

Towards Efficient k-Mer Set Operations via Function-Assigned Masked Superstrings

This paper introduces f-masked superstrings to enable efficient set operations on k-mer sets using index merging and Burrows-Wheeler Transform techniques.

Finimizers: Variable-length bounded-frequency minimizers for k-mer sets

This paper introduces finimizers, frequency-bounded minimizers for k-mer sets, to address frequent minimizer issues in indexing, showing improved query times with a prototype implementation.

The De Bruijn Graph Sequence Mapping Problem with Changes in the Graph

This paper reformulates the De Bruijn Graph Sequence Mapping Problem to allow for changes in the graph and presents a polynomial-time algorithm for solving it.

PLA-complexity of k-mer multisets

The paper introduces PLA-complexity as a measure of k-mer multiset structure and presents PLA-index for efficient approximation and querying of rank functions in genomic data.