Algorithms and Data Compression

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.

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.

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.

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.

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.

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.

DREAM-Stellar: Parallel and space efficient exactlocal alignment

DREAM-Stellar improves local alignment speed and accuracy by using parallel processing and a new prefilter, outperforming existing tools like BLAST.

Kaminari: a resource-frugal index for approximate colored k-mer queries

Kaminari improves approximate k-mer query performance by using k-mer minimizers and integer compression, outperforming Bloom filters in memory and speed with minimal false positive impact.

Measuring Genomic Data with PFP

The paper evaluates the prefix-free parse (PFP) as a tool for measuring repetitiveness and pangenome openness, showing it is more efficient than existing measures in time and space.

FroM Superstring to Indexing: a space-efficient index for unconstrained k-mer sets using the Masked Burrows-Wheeler Transform (MBWT)

This paper introduces FMSI, a superstring-based index for k-mer sets that improves space efficiency and query performance compared to existing methods.

Haplotype-based Parallel PBWT for Biobank Scale Data

The paper introduces HP-PBWT, a parallel PBWT algorithm for efficient haplotype matching in large biobank datasets, achieving significant speed-ups in both IO-included and IO-excluded benchmarks.

Direct construction of sparse suffix arrays with Libsais

The paper introduces a method to directly construct sparse suffix arrays with reduced memory and time usage, using a text encoding and Libsais library for bioinformatics applications.

Indexing All Life's Known Biological Sequences

The paper develops a scalable indexing framework for biological sequences, enabling efficient and cost-effective full-text search across vast genomic datasets.

REINDEER2: practical abundance index at scale

REINDEER2 provides a scalable, dynamic abundance index for RNA datasets, achieving faster construction and accurate abundance recovery.

Linear indexing for all strings under all internal nodes in suffix trees

The paper introduces two algorithms to linearly index all strings under internal nodes in suffix trees, enabling efficient DNA sequence analysis and pattern matching.

Efficient Seeding for Error-Prone Sequences with SubseqHash2

This paper introduces SubseqHash2, an improved subsequence-based seeding method that achieves faster computation while maintaining high accuracy for error-prone long reads.

GreedyMini: Generating low-density DNA minimizers

GreedyMini generates DNA minimizers with low expected density, improving HTS analysis performance and approaching theoretical lower bounds.

A new compression strategy to reduce the size of nanopore sequencing data

This paper introduces ex-zd, a compression strategy for nanopore sequencing data that reduces file sizes by removing redundant bits without affecting downstream analyses.

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 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.

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.