# Compression of Next-Generation Sequencing Data and of DNA Digital Files +
## 2 Ngs
### Data Compression Tools  
FASTQ, SAM, and BAM files can be compressed by using generic lossless compression tools. This compression software tool is based on the Lempel-Ziv 77 algorithm (widely used in many domains, see, for example, [11; 12]).  
There are general-purpose lossless compression tools, such as _gzip_[13] and _bzip2_[14], which generally can significantly deflate the size of the genomic file. Their performance is supposed to be good on average on almost all genomic files.  
Gzip is based on the Lempel-Ziv 77 algorithm (widely used in many domains, see, for example, [15; 16]) and it is a lossless codec that replaces an uncompressed file with a compressed one that has a \(.gz\) extension.  
_bzip2_ is a general purpose lossless compressor, often more efficient than gzip. It is based on the Burrows-Wheeler transform and on Huffman coding.  
The data compressors in use today that are specifically targeted to genomic data are often reference-based compression methods that align reads to a known reference genomic sequence and store only relative genomic positions. The reference genomic sequence is somehow considered as a reference dictionary and needs to be available at both ends of communication: the sender (compressor)and the receiver (decompressor). For example, _Scramble_ (implementing the CRAM file format) [15] and _DeeZ_[16] are reference-based methods.  
The authors in [17; 18] present the key ideas for compressive genomics and introduce algorithms that allow direct genetic computation on the compressed data. For a review of compressive genomics, see also [4].  
_Quip_[6] is a special purpose lossless compressor targeted to the compression of genetic data. Quip was presented in 2012. It has been widely used and studied because of its open source distribution that is available on the internet at [19] and it is still updated with new distributions. The version of Quip we have tested is not reference-based (it does not need a reference genomic sequence to compress the data) and it uses arithmetic coding, which is another compression strategy used in many domains (see, for example, [20; 21; 22]). There is also a reference-based version of Quip.  
Quip is a command line application and generates files that have _.qp_ as extension. It uses arithmetic encoding to encode all the components of the FASTQ file, but the arithmetic encoder uses different statistical models--one for each different component.  
Moreover, Quip uses adaptive modeling by updating the statistics at run time on which arithmetic coding is based in order to upgrade the compression rate on large files.  
Quip improves its performances by applying coding strategies specifically targeted to genomic data. For example, we have a unique reading identifier for each reading, and Quip uses delta encoding to remove the redundancy in the reading identifiers (see [6]).  
Quip embeds a Markov chains model to compress nucleotide sequences. The prediction of the nucleotide in a given position in the reading is computed by using the 12 previous positions, and a similar approach is used for quality scores too (see [6]).  
Recently, a number of effective compression tools that deal specifically with FASTQ or FASTA data have been developed and they are currently tested on real data: _fastqz_[10], _MFCompress_[23], _ALAPY_[24], and _NAF_[25], just to name a few. [PERSON] and others in [26] benchmarked 26 genomic compressors (including Quip, fastqz, MFCompress, ALAPY, NAF, and others), together with 18 general-purpose compressors, on a FASTA files data set.  
By taking into consideration both the compression performance and the compression/ decompression speed, [26] shows that the recent NAF codec demonstrates the best results on that data set.