Source-linked AI summary
Compression of next-generation sequencing reads aided by highly efficient de novo assembly
Daniel C. Jones, Walter L. Ruzzo, Xinxia Peng, Michael G. Katze
TL;DR
Next-generation sequencing produces rapidly expanding datasets that strain storage and computational infrastructure. Quip addresses this with lossless reference-based and assembly-based compression plus specialized statistical models, achieving practical compression and speed while retaining information.
Problem
Next-generation sequencing generates many gigabytes of data, creating substantial storage and computational infrastructure demands.
Method
Quip combines reference-based and assembly-based compression with adaptive statistical models for read identifiers, quality scores, nucleotide sequences, and alignment information.
Results
Quip retains original information while compressing FASTQ and SAM/BAM data, operates at three times gzip's speed with assembly, and up to five times gzip's speed without it.
Takeaways & Limitations
Quip provides a practical lossless compression tool for large sequencing datasets, combining strong compression with efficient runtime and flexible handling of alignment data.
Takeaways & Limitations
Assembly-based compression offers only a small advantage for many datasets because low coverage limits its effectiveness across large portions of eukaryotic genomes.
Abstract
from arXiv · showhide
We present Quip, a lossless compression algorithm for next-generation sequencing data in the FASTQ and SAM/BAM formats. In addition to implementing reference-based compression, we have developed, to our knowledge, the first assembly-based compressor, using a novel de novo assembly algorithm. A probabilistic data structure is used to dramatically reduce the memory required by traditional de Bruijn graph assemblers, allowing millions of reads to be assembled very efficiently. Read sequences are then stored as positions within the assembled contigs. This is combined with statistical compression of read identifiers, quality scores, alignment information, and sequences, effectively collapsing very large datasets to less than 15% of their original size with no loss of information. Availability: Quip is freely available under the BSD license from http://cs.washington.edu/homes/dcjones/quip.
1 Introduction
NGS has created rapidly growing storage and transfer demands, while existing compression approaches face format, reference-dependence, and lossiness challenges. Quip addresses these issues with lossless compression for FASTQ and SAM/BAM data, including a self-contained assembly-based approach.
- NGS experiments now produce gigabytes rather than megabytes, creating substantial storage and computational-infrastructure demands.
- FASTQ and SAM/BAM store sequences alongside read identifiers, quality scores, and, for SAM/BAM, alignment information.
- Reference-based compression can be highly effective but requires an appropriate reference database and makes compressed files inaccessible if that database is lost.
- Lossy quality-score compression is attractive because scores can be high-entropy, but its downstream effects remain difficult to assess reliably.
- Quip provides lossless compression for FASTQ and BAM/SAM files while retaining all information from the original files.
2 Materials & Methods
Quip combines adaptive statistical models with reference- and assembly-based techniques to compress sequencing components while reducing dependence on external references. Its assembler uses compact probabilistic k-mer counting and greedy contig construction to encode reads as contig positions.
- Statistical Compression: Quip uses arithmetic coding with separate adaptive statistical models for quality scores, read identifiers, nucleotide sequences, and alignment information.Adaptive parameters are updated during compression to improve modeling on large files.
- Read Identifiers: Read identifiers are compressed by tokenizing fields, exploiting repeated values, numerical offsets, and shared prefixes.Identifiers often 50 bytes or longer are typically reduced to 2–4 bytes.
- Sequence Compression: Nucleotide sequences are modeled with an order-12 Markov chain that predicts each nucleotide from the preceding twelve positions.The model becomes better fitted as millions of reads are compressed.
- Quality Scores: Quality scores use an order-3 Markov chain conditioned on read position and binned counts of large adjacent-score jumps.The distal two positions are coarsely binned to control the number of parameters.
- Assembly-Based Compression: Assembly-based compression builds contigs from an initial subset of reads, then encodes aligned reads as positions within those contigs without an external reference database.The contigs are reassembled during decompression rather than explicitly stored.
- Assembly-Based Compression: Quip reduces de Bruijn-graph memory demands by counting k-mers with a Bloom-filter-based probabilistic data structure.Its d-left counting Bloom filter can produce inflated counts, but assembly inaccuracies affect compression rather than losslessness.
- Assembly-Based Compression: The assembler greedily extends seeded contigs by selecting the most abundant overlapping k-mer, prioritizing efficiency over assembly accuracy.
3 Results
Quip was evaluated across diverse sequencing datasets against general-purpose and domain-specific compressors using lossless benchmarks of size, speed, and memory. Results show reference-based compression usually achieves the smallest files, while assembly-based compression is especially useful for metagenomic data without an obvious reference.
- Compression of Sequencing Data: Six sequencing datasets were compressed with Quip, gzip, bzip2, xz, DSRC, Cramtools, and SRA, using publicly available software where possible.The evaluation covered FASTQ, SAM/BAM, and SRA-related workflows; Cramtools was not fully lossless because it discarded read identifiers.
- Compression of Sequencing Data: Reference-based Quip consistently produced the smallest files for single-genome samples, while reference-free compression matched Cramtools on two datasets.Assembly-based compression provided almost no advantage for single-genome ChIP-Seq, whole-genome, and exome datasets.
- Compression of Sequencing Data: Approximately 35% of total RNA-Seq reads and 70% of mRNA-Seq reads aligned to assembled contigs, but assembly produced only a small overall compression increase.The aligned RNA-Seq reads were relatively low-entropy and therefore already compressed moderately well by the Markov-chain method.
- Compression of Sequencing Data: Nearly 95% of metagenomic reads aligned to assembled contigs, yielding a significant reduction in compressed file size without an obvious reference genome.This benefit may reflect low species diversity and may not extend to all metagenomic datasets.
- Compression of Sequencing Data: Quality scores dominated Quip's compressed files, suggesting that further nucleotide-sequence compression would produce diminishing overall returns.The authors identify quality-score reduction as the larger potential source of additional savings, but lossy transformations may affect downstream analysis.
4 Discussion
Quip combines reference-based and assembly-based compression with statistical modeling to achieve efficient, lossless NGS compression. Its advantages include strong runtime and compression performance, while assembly-based compression is most useful when references are unavailable and quality scores remain the dominant storage challenge.
- Quip matches Cramtools’ speed while providing substantially better lossless compression and retaining read identifiers discarded by Cramtools.Quip also supports multiple alignments per read and does not require sorted or indexed BAM files.
- Assembly-based compression reduces nucleotide-sequence size by over 40% in the evaluated metagenomic dataset, where no obvious reference sequence exists.Its advantage is small on many datasets because assembling a subset of reads gives insufficient coverage for large eukaryotic genomes.
- Assembly-based compression becomes computationally intensive as the assembler scales, making reference-based compression more appropriate for large eukaryotic-genome datasets.The limitation reflects low coverage from assembling only a relatively small subset of reads.
- 3× faster than gzip with assembly and up to 5× faster without assembly, Quip prioritizes runtime for increasingly large sequencing datasets.Only DSRC is faster, but it consistently achieves lower compression.
- Quality scores dominate compressed NGS-file size, so better nucleotide-sequence compression would yield only minor overall reductions.Future work should study lossy quality-score compression while minimizing effects on alignment, SNP calling, and other analyses.
- Quip combines reference-based and assembly-based techniques with statistical compression to remain practical while probing the limits of lossless NGS compression.The approach targets FASTQ and SAM/BAM data while retaining all original information.
5 Funding
The work was supported by federal funds from the National Institute of Allergy and Infectious Diseases, National Institutes of Health, and Department of Health and Human Services.
- Federal funds supported the work through the National Institute of Allergy and Infectious Diseases.
- Support was provided by the National Institutes of Health and Department of Health and Human Services.
- Additional support came through Contract No. HHSN272200800060C and Public Health Service grant P51RR000166.