Algorithms and Data Compression

The paper introduces AIList, a data structure for efficient genomic interval search, which outperforms existing methods in speed and memory usage.

The paper introduces a preprocessing algorithm called prefix-free parsing to efficiently build compressed Burrows-Wheeler Transform indexes for large genomic datasets.

The paper introduces an LSH method for edit distance that considers both k-mer content and order, improving alignment detection efficiency.

deGSM constructs large de Bruijn graphs efficiently in limited memory, handling terabase-pair datasets on standard hardware.

The paper introduces a space-efficient framework for variable-order Markov models, reducing memory usage by up to 100 times compared to previous methods.

This paper generalizes sequence-to-sequence alignment algorithms to graphs, achieving significant speedups for aligning sequencing reads to variation graphs.

The paper improves min hash for estimating Jaccard similarity in sets of different sizes, showing better accuracy and efficiency for metagenomic analysis.

The paper introduces NAF, a lossless reference-free compression format for DNA sequences that offers faster decompression than existing tools while maintaining comparable compression ratios.

The paper introduces two compression methods for graph coloring in sequencing data, reducing memory use by up to three orders of magnitude while maintaining dynamic graph topology.

The paper introduces MSAC, a compression algorithm for multiple sequence alignment files, achieving up to six times better compression than gzip.

DREAM-Yara provides an efficient read mapper for large reference databases, reducing index construction time and enabling faster updates.

Mantis provides a fast, small, and exact sequence search index for large RNA-seq datasets, outperforming existing methods in speed and accuracy.

The paper introduces a space and time-efficient index for the compacted colored de Bruijn graph, balancing speed and space usage for k-mer lookup and pattern matching.

The paper analyzes minimizers schemes and shows that asymptotically optimal schemes with lower density than previously thought exist, leading to more efficient bioinformatics tools.

The paper introduces an improved Sequence Bloom Tree data structure that enhances query performance for RNA-seq databases.

The paper introduces an improved indexing method, Split Sequence Bloom Tree (SSBT), for efficiently searching large RNA-seq databases and demonstrates its performance on breast, blood, and brain tissue data.

FaStore compresses FASTQ files with lossy modes, achieving better compression ratios than existing methods while maintaining variant calling accuracy.

GTC is a compressed data structure for genetic variation data that improves compression ratio and query speed compared to existing solutions.

ChIPWig compresses ChIP-seq Wig data with lossless and lossy modes, achieving high compression rates while preserving peak calling and motif discovery accuracy.

Squeakr is a k-mer counting and multiset representation system that improves speed and memory efficiency compared to existing methods.

Quark compresses RNA-seq data using a semi-reference-based approach, achieving better compression than reference-free methods while allowing reference-free decompression.

The paper improves minimizers and winnowing schemes by analyzing k-mer ordering and introducing universal hitting sets to enhance performance.