Algorithms and Data Compression

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.

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.

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.

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.

Conway-Bromage-Lyndon (CBL): an exact, dynamic representation of k-mer sets

The paper introduces CBL, a dynamic and exact k-mer set representation that outperforms existing methods and supports in-place set operations.

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 new paradigm for biological sequence retrieval inspired by natural language processing and database research

The paper introduces a new sequence retrieval method using pattern mining from cross-species omic data, showing it can retrieve homologous sequences with 50% identity without alignment.

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.

Identifying Clusters in Graph Representations of Genomes

The paper develops algorithms to find high-density clusters in graph representations of pangenomes by solving a path-finding problem in weighted directed graphs.

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.

Deep FASTQ and BAM co-compression in Genozip 15

The paper introduces Genozip Deep, a method for losslessly co-compressing FASTQ and BAM files, achieving significant compression improvements over existing methods.

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.

Fractional Hitting Sets for Efficient and Lightweight Genomic Data Sketching

This paper introduces a new sketching method for genomic data that reduces space and memory usage while maintaining efficiency and accuracy compared to existing tools.

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.

Compression algorithm for colored de Bruijn graphs

The paper introduces a new compression tool for colored de Bruijn graphs, achieving better compression than existing tools across various datasets.

Aird-ComboComp: A combinable compressor framework with a dynamic-decider for lossy mass spectrometry data compression

The paper introduces Aird-ComboComp, a compression framework for mass spectrometry data that improves compression ratios and decompression speed compared to existing methods.