Algorithms and Data Compression

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.

STABIX: Summary statistic-based GWAS indexing and compression

STABIX improves GWAS data compression and query efficiency by enabling summary-statistic-based queries and achieving smaller file sizes and faster decompression speeds compared to tabix.

Efficient and Robust Search of Microbial Genomes via Phylogenetic Compression

This paper introduces phylogenetic compression to efficiently search large microbial genome collections, achieving significant compression improvements and enabling fast BLAST-like searches on desktop computers.

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.

The open-closed mod-minimizer algorithm

The paper introduces the open-closed mod-minimizer, a method that improves k-mer sampling density for all k values compared to existing methods.

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.

A Novel Lossless Encoding Algorithm for Data Compression - Genomics Data as an Exemplar

The paper introduces a novel lossless compression algorithm that improves genomic data compression, achieving better results than state-of-the-art tools.

Prokrustean Graph: A substring index for rapid k-mer size analysis

The paper introduces a substring index called the Prokrustean graph to efficiently analyze k-mer-based quantities across different k-mer sizes.

Improved pangenomic classification accuracy with chain statistics

The paper improves pangenomic classification accuracy by introducing chain statistics that capture coarse-grained co-linearity without requiring chaining algorithms.

K2R: Tinted de Bruijn Graphs implementation for efficient read extraction from sequencing datasets

K2R efficiently indexes sequencing datasets to identify reads containing specific k-mers, outperforming existing methods in speed and resource usage.

Movi: a fast and cache-efficient full-text pangenome index

Movi is a fast pangenome index that enables efficient querying of nanopore sequencing reads using move structures, achieving faster speeds than 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.

The Backpack Quotient Filter: a dynamic and space-efficient data structure for querying k-mers with abundance.

The paper introduces the Backpack Quotient Filter (BQF), a data structure for querying k-mer abundance with improved space efficiency compared to the Counting Quotient Filter.

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.

k-nonical space: sketching with reverse complements

The paper investigates the impact of using canonical k-mers in sketching methods for genomic sequences and proposes solutions to address resulting issues.

Where the patterns are: repetition-aware compression for colored de Bruijn graphs

The paper introduces lossless compression methods for colored de Bruijn graphs, reducing memory usage while maintaining query efficiency.

GIN-TONIC: Non-hierarchical full-text indexing for graph-genomes

GIN-TONIC indexes graph-genomes for efficient substring queries without explicitly storing all walks, showing scalability on human pangenome and transcriptome data.

HiCMC: High-Efficiency Contact Matrix Compressor

HiCMC compresses Hi-C data more efficiently than existing methods by modeling chromosome structures, improving compression rates across multiple cell lines and resolutions.

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.

Efficient protein structure archiving using ProteStAr

ProteStAr compresses protein structure files efficiently, offering better compression ratios than existing tools while maintaining reconstruction accuracy.

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.