Compression of next-generation sequencing reads aided by highly efficient de novo assembly

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 proba...

Full description

Saved in:
Bibliographic Details
Published in:Nucleic acids research 2012-12, Vol.40 (22), p.e171-e171
Main Authors: Jones, Daniel C, Ruzzo, Walter L, Peng, Xinxia, Katze, Michael G
Format: Article
Language:English
Subjects:
Algorithms
Compression
Data Compression - methods
Data processing
High-Throughput Nucleotide Sequencing - methods
Memory
Methods Online
Probability
Software
Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 data sets to
ISSN:0305-1048
1362-4962
DOI:10.1093/nar/gks754