Algorithms and Data Compression

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.

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.

Efficient protein structure archiving using ProteStAr

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

Exact Sketch-Based Read Mapping

This paper introduces an exact sketch-based read mapping algorithm that finds all mapping positions above a similarity threshold, achieving higher recall than minimap2 on long reads of the human Y chromosome.

Centrifuger: lossless compression of microbial genomes for efficient and accurate metagenomic sequence classification

Centrifuger compresses microbial genomes losslessly for faster and more accurate metagenomic classification by reducing memory use and improving taxonomic resolution.

Designing efficient randstrobes for sequence similarity analyses

This paper introduces new randstrobe construction methods, identifies biases in previous approaches, and improves accuracy in short-read mapping.

kmindex and ORA: indexing and real-time user-friendly queries in terabytes-sized complex genomic datasets

The paper introduces kmindex for fast indexing of complex genomic datasets and ORA for real-time querying of the Tara Oceans metagenomes.

Fulgor: A fast and compact k-mer index for large-scale matching and color queries

Fulgor is a compact k-mer index for efficient sequence matching and color queries, outperforming existing methods in space and speed.

Exact global alignment using A* with chaining seed heuristic and match pruning

This paper introduces an exact global alignment algorithm using A* with chaining seed heuristic and match pruning, achieving near-linear runtime and significant speedups over existing methods.

Meta-colored compacted de Bruijn graphs

The paper introduces a new data structure, Mac-dBG, that improves space efficiency for colored de Bruijn graphs by compressing color representations, while maintaining query efficiency.

Image-centric compression of protein structures improves space savings

The paper introduces PIC, an image-based compression method for protein structures, achieving better compression ratios than gzip for large proteins.

A pipeline for constructing reference genomes for large cohort-specific metagenome compression

The paper presents a pipeline to create simplified reference genomes for metagenomic data compression, achieving high compression ratios across multiple datasets.

General encoding of canonical k-mers

The paper introduces a minimal encoding for canonical k-mers that evenly distributes them in a reduced interval, improving efficiency for sequence indexing and comparison.

Efficient minimizer orders for large values of k using minimum decycling sets

The paper introduces new minimizer orders for large k-values using decycling sets, improving efficiency in DNA sequencing analysis.

WGT: Tools and algorithms for recognizing, visualizing and generating Wheeler graphs

The paper introduces Wheelie, an algorithm to check if a graph has Wheeler properties, and presents the WGT toolkit for visualizing and generating Wheeler graphs.

Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time

The paper introduces an algorithm to compute a minimum plain text representation of k-mer sets without repetitions in linear time and evaluates existing heuristics.

Sequence aligners can guarantee accuracy in almost O(m log n) time: a rigorous average-case analysis of the seed-chain-extend heuristic

The paper provides theoretical guarantees for the seed-chain-extend heuristic in sequence alignment, showing it can achieve near-linear runtime and high accuracy with optimal k-mer size.

Debiasing FracMinHash and deriving confidence intervals for mutation rates across a wide range of evolutionary distances

This paper analyzes FracMinHash, showing it can be corrected for bias and used to estimate mutation distances with confidence intervals.

Hierarchical Interleaved Bloom Filter: Enabling ultrafast, approximate sequence queries

This paper introduces HIBF, a fast and space-efficient data structure for approximate sequence queries, showing significant improvements in speed and resource usage over existing tools.

Scalable sequence database search using Partitioned Aggregated Bloom Comb-Trees

The paper introduces PAC, a scalable approximate membership query data structure for large sequence collections, achieving faster construction and query times than existing methods.

BUSZ: Compressed BUS files

The paper introduces a compression algorithm for BUS files that achieves faster speeds and smaller file sizes than gzip.

Aligning Distant Sequences to Graphs using Long Seed Sketches

The paper introduces a long seed sketch method for sequence-to-graph alignment, improving time-accuracy trade-offs in high mutation rate scenarios.

Recursive Prefix-Free Parsing for Building Big BWTs

This paper introduces recursive prefix-free parsing to reduce memory needed for building run-length encoded BWTs, showing effective memory reduction in experiments.

NanoSpring: reference-free lossless compression of nanopore sequencing reads using an approximate assembly approach

NanoSpring compresses nanopore sequencing reads with a reference-free approximate assembly approach, achieving lower bit per base rates than gzip and competitive performance with CoLoRd.

Optimal gap-affine alignment in O(s) space

This paper introduces BiWFA, an algorithm that performs gap-affine sequence alignment in O(s) memory while maintaining O(ns) time complexity, improving memory efficiency for large-scale alignments.

How to optimally sample a sequence for rapid analysis

The paper introduces a sequence-sampling method that optimizes sensitivity for sequence comparison and improves specificity for biological DNA.

Sequence to graph alignment using gap-sensitive co-linear chaining

The paper develops a new chaining algorithm for aligning long reads to pangenome DAGs, achieving high precision with low unmapped reads.