Algorithms and Data Compression

On the Complexity of Sequence to Graph Alignment

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.

A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets

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.

Sparse Binary Relation Representations for Genome Graph Annotation

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

PgRC: Pseudogenome based Read Compressor

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

A New approximate matching compression algorithm for DNA sequences

The paper introduces a DNA sequence compression algorithm using redundancy and approximate selection, achieving better compression than LZW and Huffman but with slower decompression.

An improved encoding of genetic variation in a Burrows-Wheeler transform

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.

Improved Representation of Sequence Bloom Trees

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.

Haplotype-aware graph indexes

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

A massively parallel algorithm for finding non-existing sequences in genomes

The paper introduces a GPU-accelerated algorithm to identify absent sequences in genomes with Hamming distance guarantees and detailed mismatch information.

MassComp, a lossless compressor for mass spectrometry data

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: Genotype compression in large project

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

Building Large Updatable Colored de Bruijn Graphs via Merging

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.

Practical universal k-mer sets for minimizer schemes

The paper introduces a method to create practical universal k-mer sets for minimizer schemes that can handle larger k-mer lengths, reducing false positives in sequence matching.

Augmented Interval List: a novel data structure for efficient genomic interval search

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

Prefix-Free Parsing for Building Big BWTs

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

Locality sensitive hashing for the edit distance

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

deGSM: memory scalable construction of large scale de Bruijn Graph

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

A framework for space-efficient variable-order Markov models

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

Bit-parallel sequence-to-graph alignment

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

Improving Min Hash via the Containment Index with applications to Metagenomic Analysis

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

Nucleotide Archival Format (NAF) enables efficient lossless reference-free compression of DNA sequences

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.

Compressing Streams of Phylogenetic Trees

The paper compresses streams of phylogenetic trees using advanced compression algorithms, achieving significant compression rates compared to existing methods.

An introduction to MPEG-G, the new ISO standard for genomic information representation

This paper introduces MPEG-G, an ISO standard for genomic data compression, highlighting its format, decoding process, and interoperability features.

Improving on hash-based probabilistic sequence classification using multiple spaced seeds and multi-index Bloom filters

The paper introduces a multi-index Bloom filter for alignment-free sequence classification, showing improved sensitivity and efficiency over existing methods in read binning and taxonomic assignment.

Dynamic compression schemes for graph coloring

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.

MSAC: Compression of multiple sequence alignment files

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

DREAM-Yara: An exact read mapper for very large databaseswith short update time

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

Mantis: A Fast, Small, and Exact Large-Scale Sequence Search Index

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

GaKCo: a Fast GApped k-mer string Kernel using COunting

GaKCo improves the speed of gapped k-mer string kernels by using cumulative counting, achieving faster performance on DNA, protein, and text classification tasks.

A space and time-efficient index for the compacted colored de Bruijn graph

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.