Algorithms and Data Compression

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.

Discovering motifs and genomic patterns with SMT: a high-performance data structure for counting kmers

The paper introduces SMT, a data structure for efficient kmer counting and motif discovery in genomic data, showing its effectiveness in handling noisy datasets and large-scale analysis.

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.

μ-PBWT: Enabling the Storage and Use of UK Biobank Data on a Commodity Laptop

The paper introduces μ-PBWT, a memory-efficient method for haplotype matching, reducing memory usage by up to 25 times and enabling storage of large datasets on a commodity laptop.

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.

Masked superstrings as a unified framework for textual ????-mer set representations

The paper introduces masked superstrings as a unified framework for k-mer set representations, showing they are NP-hard to compute and proposing greedy heuristics for efficient implementation.

Building a Pangenome Alignment Index via Recursive Prefix-Free Parsing

The paper introduces a recursive prefix-free parsing method to improve the efficiency of building pangenome alignment indexes, reducing construction time and memory usage.

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.

aaHash: recursive amino acid sequence hashing

aaHash is a recursive amino acid sequence hashing algorithm that improves speed and sensitivity for protein sequence analysis.

Spectrum preserving tilings enable sparse and modular reference indexing

The paper introduces a method to reduce the space required for reference indexing by using spectrum preserving tilings and sampling schemes, achieving significant space savings with minimal query slowdown.

Heuristics for the De Bruijn Graph Sequence Mapping Problem

The paper introduces exact algorithms and approximate heuristics for mapping sequences onto De Bruijn graphs using edit distance as a similarity metric.

Syllable-PBWT for space-efficient haplotype long-match query

The paper introduces Syllable-PBWT, a space-efficient data structure for haplotype long-match queries, reducing memory use by over 100 times compared to existing methods.

Masked Minimizers: Unifying sequence sketching methods

This paper introduces masked minimizers, a unifying framework for sequence sketching methods, and proposes a new metric to evaluate and optimize them for better genomic analysis.

GBZ File Format for Pangenome Graphs

The paper introduces the GBZ file format for efficiently storing pangenome graphs, providing compression tools and demonstrating efficient system usage.

Compressed Data Structures for Population-Scale Positional Burrows-Wheeler Transforms

The paper presents efficient data structures for storing and querying the positional Burrows-Wheeler Transform (PBWT) to improve memory usage for large haplotype datasets.

Genozip 14 - advances in compression of BAM and CRAM files

Genozip 14 improves BAM and CRAM compression, achieving up to 2.7x better compression than CRAM 3.1 across various genomic data types.

MONI-k: An index for efficient pangenome-to-pangenome comparison

The paper introduces k-MEMs and extends the MONI index to efficiently find them for pangenome-to-pangenome comparison.

fimpera: drastic improvement of Approximate Membership Query data-structures with counts

The paper introduces fimpera, an algorithm that improves counting Approximate Membership Query data structures by reducing false positives and filter size while maintaining precision.

Efficient reconciliation of genomic datasets of high similarity

The paper introduces a method using IBLTs and syncmers to efficiently estimate Jaccard similarity and identify differing k-mers between genomic datasets.

On Weighted K-Mer Dictionaries

This paper introduces an improved weighted k-mer dictionary that compresses k-mer counts more efficiently than existing methods.

Succinct k-mer Sets Using Subset Rank Queries on the Spectral Burrows-Wheeler Transform

This paper introduces the Spectral Burrows-Wheeler Transform (SBWT) and develops succinct index structures for efficient k-spectrum membership queries in genomic data.

Dataset-adaptive minimizer order reduces memory usage in k-mer counting

The paper introduces a dataset-adaptive minimizer order method to reduce memory usage in k-mer counting with minimal runtime increase.

The minimizer Jaccard estimator is biased and inconsistent

The paper shows that the minimizer Jaccard estimator is biased and inconsistent, affecting the accuracy of sequence similarity estimation and a read mapping tool.

Sparse and Skew Hashing of K-Mers

The paper introduces a compressed k-mer dictionary that improves space/time efficiency using statistical properties of k-mer minimizers.

AGC: Compact representation of assembled genomes

AGC provides a compact representation of assembled genomes, reducing storage space by 2-3 orders of magnitude while enabling efficient extraction of contig parts.

CoLoRd: Compressing long reads

CoLoRd compresses third-generation sequencing data by an order of magnitude without affecting downstream analysis accuracy.

BWA-MEME: BWA-MEM emulated with a machine learning approach

BWA-MEME improves short-read alignment efficiency by using a machine learning approach to reduce computational overhead while maintaining accuracy.