Algorithms and Data Compression

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.

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

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 reduces false-positive rates in approximate membership queries for k-mers without increasing space or memory usage.

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

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

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

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.

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

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

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

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

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

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

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 provides a scalable lossy to lossless compression solution for NGS quality values, achieving efficient storage without re-encoding.

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

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

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 improves FASTQ file compression by using k-mer-based methods, achieving better compression ratios than existing tools.

This paper proves sequence to graph alignment is NP-complete under Hamming and edit distances for alphabets of size ≥2 and presents an efficient algorithm for when only sequence changes are allowed.

This paper introduces PASHA, a randomized parallel algorithm for generating near-optimal universal hitting sets, which is significantly faster and more memory-efficient than existing methods.

This paper introduces a new compression method for de Bruijn graph labels, showing improved performance over existing methods on real-world datasets.

PgRC compresses DNA sequencing data more efficiently than existing tools while maintaining comparable decompression speed.

The paper introduces an improved encoding of genetic variation in a Burrows-Wheeler transform to enhance read mapping accuracy by handling multiple types of variation efficiently.

The paper introduces HowDe-SBT, an improved indexing method for RNA-seq data that reduces construction time, space, and query time compared to existing SBT methods.

The paper introduces haplotype-aware graph indexes to improve the representation of genetic variation in variation graphs.

MassComp is a lossless compressor for mass spectrometry data that reduces file size by up to 89% compared to uncompressed data and outperforms existing compressors.

GTShark compresses large genotype datasets and single samples to achieve previously unattainable file sizes.

The paper introduces an algorithm to merge succinct de Bruijn graph representations, enabling efficient construction of large colored de Bruijn graphs with reduced space usage.