Lossy Compression of Quality Values via Rate Distortion Theory

Himanshu Asnani, Dinesh Bharadia, Mainak Chowdhury, Idoia Ochoa, Itai Sharon, Tsachy WeissmanarXiv 2012 · arXiv

Introduction

Next-Generation Sequencing (NGS) has revolutionized biological research, but the resulting data volume poses significant storage challenges. Genomic data is typically stored in FASTQ files, which consist of DNA sequences and their associated "quality values" (Phred scores). These scores represent the sequencer's confidence in each base call. While DNA sequences are relatively compressible, quality values are inherently noisy and often consume over half of the total storage space.

Traditional lossless compression is inefficient for quality scores because it allocates bits to preserve random measurement noise. This paper proposes a principled framework for the lossy compression of genomic quality values using Rate Distortion Theory. By discarding non-essential information, the authors demonstrate that storage requirements can be reduced to below one bit per value with minimal impact on downstream biological analyses like genome alignment.

Methodology

The authors treat quality scores as noisy signals and apply concepts from Information Theory to find the theoretical minimum bit-rate required for a specific level of allowed error (distortion). The process involves several key stages:

  1. Statistical Modeling: Quality values within a read are modeled as a multivariate Gaussian random vector, assuming that base-calling noise results from multiple independent physical factors.
  2. Decorrelation via SVD: Since quality values at adjacent positions are often correlated, the framework uses Singular Value Decomposition (SVD) to transform the data into a coordinate system where components are independent.
  3. Optimal Bit Allocation: The algorithm, termed SVD-BitAllocate, solves a convex optimization problem to distribute a fixed bit budget across transformed components, prioritizing those that most significantly reduce the total Mean Squared Error (MSE).
  4. Quantization and Reconstruction: A Lloyd-Max scalar quantizer maps the continuous Gaussian values into discrete bit representations. For analysis, the process is reversed to provide a "denoised" approximation of the original scores.
Schematic of the transform coding framework using SVD and optimal bit allocation for genomic quality values.

Experimental Results

The framework was evaluated using 20 million reads (46 bases each) from the NCBI Human Genome Sequence Read Archive (ERR000531). The performance was measured using both mathematical metrics (MSE) and biological metrics (Relative Mapping Accuracy via the Bowtie aligner).

Performance at Low Bit Rates

A primary finding is the framework's ability to break the "1-bit barrier." Most existing compressors struggle to maintain utility below 1 bit per quality value. However, the SVD-BitAllocate method achieved significantly lower MSE than standard heuristic approaches like "Log Binning" at these extremely low bit rates.

Comparison of Mean Square Error (MSE) across different bit rates, showing the superior performance of SVD-BitAllocate at low bitrates compared to Log binning.

Biological Fidelity

At a rate of just 1 bit per quality value—a 6x reduction from the standard 6 bits used in FASTQ—the Relative Mapping Accuracy remained above 93%. Furthermore, the fraction of reads aligning to different positions after compression was remarkably low, suggesting that the essential information required for alignment is preserved even when the majority of the raw data is discarded.

Discussion and Future Work

While the Gaussian model is highly effective at low bit rates, it faces a "gap" at very high bit rates where simple integer-based binning performs better. This is because the model assumes continuous values, whereas original Phred scores are restricted to a small integer set (0-40).

Future research may focus on reducing the computational overhead of SVD through read clustering and exploring the "denoising" hypothesis—the idea that lossy compression might actually improve downstream results by filtering out measurement noise. Additionally, adapting the framework for variable-length reads produced by newer sequencing technologies remains a key objective.

Summary updated

Abstract

Next Generation Sequencing technologies revolutionized many fields in biology by enabling the fast and cheap sequencing of large amounts of genomic data. The ever increasing sequencing capacities enabled by current sequencing machines hold a lot of promise as for the future applications of these technologies, but also create increasing computational challenges related to the analysis and storage of these data. A typical sequencing data file may occupy tens or even hundreds of gigabytes of disk space, prohibitively large for many users. Raw sequencing data consists of both the DNA sequences (reads) and per-base quality values that indicate the level of confidence in the readout of these sequences. Quality values account for about half of the required disk space in the commonly used FASTQ format and therefore their compression can significantly reduce storage requirements and speed up analysis and transmission of these data. Results: In this paper we present a framework for the lossy compression of the quality value sequences of genomic read files. Numerical experiments with reference based alignment using these quality values suggest that we can achieve significant compression with little compromise in performance for several downstream applications of interest, as is consistent with our theoretical analysis. Our framework also allows compression in a regime - below one bit per quality value - for which there are no existing compressors.
BibTeX
@misc{asnani2012lossy,
  author = {Himanshu Asnani and Dinesh Bharadia and Mainak Chowdhury and Idoia Ochoa and Itai Sharon and Tsachy Weissman},
  title = {{Lossy Compression of Quality Values via Rate Distortion Theory}},
  year = {2012},
  eprint = {1207.5184},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1207.5184},
}
Figure