Algorithms and Data Compression

VCFShark: how to squeeze a VCF file

VCFShark compresses VCF files more efficiently than standard methods, reducing their size by up to an order of magnitude.

BLight: Efficient exact associative structure for k-mers

BLight is a memory-efficient data structure for associating unique identifiers with k-mers and querying them at high speed.

d-PBWT: dynamic positional Burrows-Wheeler transform

The paper introduces d-PBWT, a dynamic version of the PBWT data structure, enabling efficient insertion and deletion of haplotypes while maintaining PBWT functionality.

MQF and buffered MQF: Quotient filters for efficient storage of k-mers with their counts and metadata

The paper introduces MQF and buffered MQF, efficient data structures for storing k-mers with counts and metadata, improving space efficiency and speed over existing methods.

An Incrementally Updatable and Scalable System for Large-Scale Sequence Search using LSM Trees

The paper introduces an updatable and scalable exact sequence-search index based on Mantis, demonstrating its efficiency and scalability over large datasets.

Syncmers are more sensitive than minimizers for selecting conserved k-mers in biological sequences

The paper introduces syncmers as an alternative to minimizers for selecting conserved k-mers, showing they are more sensitive and robust to mutations.

Buffering Updates Enables Efficient Dynamic de Bruijn Graphs

The paper introduces BufBOSS, a compressed dynamic de Bruijn graph that improves update efficiency by buffering changes, outperforming existing tools in time, memory, and deletion speed.

findere: fast and precise approximatemembership query

findere reduces false-positive rates in approximate membership queries for k-mers without increasing space or memory usage.

Data structures based on k-mers for querying large collections of sequencing datasets

The paper surveys computational methods for indexing and querying large sequencing datasets using k-mer-based data structures.

LISA: A Case For Learned Index based Acceleration of Biological Sequence Analysis

The paper introduces LISA, a machine learning-based index for accelerating sequence search in genomics, showing performance improvements over traditional indexes in various case studies.

Representation of k-mer sets using spectrum-preserving string sets

The paper introduces a method to efficiently represent k-mer sets using spectrum-preserving string sets, achieving better compression and indexing than existing tools.

Minimally-overlapping words for sequence similarity search

The paper introduces a sparse-seeding method for sequence similarity search using minimally-overlapping words to improve sensitivity compared to existing methods.

Impact of lossy compression of nanopore raw signal data on basecalling and consensus accuracy

This study evaluates the impact of lossy compression on nanopore sequencing data, showing minimal effects on basecalling and consensus accuracy while significantly reducing storage needs.

Fast Alignment-Free Similarity Estimation By Tensor Sketching

The paper introduces Tensor Sketch, a method for fast and accurate edit distance estimation in biological sequences, outperforming existing methods in speed and accuracy.

Aird: A computation-oriented mass spectrometry data format enables higher compression ratio and less decoding time

Aird is a computation-oriented mass spectrometry data format that achieves higher compression and faster decoding compared to existing formats.

Sapling: Accelerating Suffix Array Queries with Learned Data Models

Sapling improves sequence alignment speed by using a learned data model to enhance suffix array queries, outperforming existing methods on various genomes.

A performant bridge between fixed-size and variable-size seeding

The paper introduces a merge-extend strategy for computing MEMs from fixed-size seeds and benchmarks its performance against existing methods.

Sequence Compression Benchmark (SCB) database - a comprehensive evaluation of reference-free compressors for FASTA-formatted sequences

The paper benchmarks 44 sequence compressors on FASTA-formatted data, identifying optimal tools based on performance metrics like compression ratio and speed.

Calibrating seed-based alignment heuristics with Sesame

This paper develops a theoretical framework to calibrate seeding heuristics in DNA sequencing alignment and provides an open-source implementation called Sesame.

\"GPress: a framework for querying General Feature Format (GFF) files and feature expression files in a compressed form\"

GPress compresses and queries GFF and feature expression files efficiently, achieving significant size reduction without compromising retrieval speed.

Improved design and analysis of practical minimizers

The paper introduces a randomized algorithm called Miniception to design minimizers with optimal density guarantees for practical bioinformatics applications.

The Homo-Edit Distance Problem

The paper introduces the homo-edit distance problem and presents a polynomial-time dynamic programming solution for computing it.

Succinct Dynamic de Bruijn Graphs

This paper introduces DynamicBOSS, a succinct dynamic de Bruijn graph representation that supports unlimited additions and deletions of nodes and edges, outperforming existing methods for large-scale datasets.

ScaleQC: A Scalable Lossy to Lossless Solution for NGS Sequencing Data Compression

ScaleQC provides a scalable lossy to lossless compression solution for NGS quality values, achieving efficient storage without re-encoding.

Engineering the Compression of Sequencing Reads

The paper introduces an optimized, multi-threaded version of PgRC, a FASTQ compressor that improves compression time while maintaining compression ratio and decompression speed.

Accelerating Maximal-Exact-Match Seeding with Enumerated Radix Trees

The paper introduces an optimized data structure for read alignment, improving performance while maintaining accuracy.

Efficient Construction of a Complete Index for Pan-Genomics Read Alignment

The paper introduces an efficient method for constructing a complete index for pan-genomics read alignment, improving memory and time efficiency over existing methods.

An Efficient, Scalable and Exact Representation of High-Dimensional Color Information Enabled via de Bruijn Graph Search

The paper introduces an efficient encoding method for color information in de Bruijn graphs, improving compression and scalability for large-scale genomic applications.

conLSH: Context based Locality Sensitive Hashing for Mapping of noisy SMRT Reads

This paper introduces conLSH, a contextual Locality Sensitive Hashing algorithm for aligning noisy SMRT reads to a reference genome, showing improved speed and memory efficiency compared to existing methods.

FQSqueezer: k-mer-based compression of sequencing data

FQSqueezer improves FASTQ file compression by using k-mer-based methods, achieving better compression ratios than existing tools.