# Compression of Next-Generation Sequencing Data and of DNA Digital Files +
## 4 DNA Compression
If there are exactly or more than \(2^{\mathit{maxrep}\left(x\right)}-1\) repetitions, we will need to send another one or more groups of _maxrep_\(\left(x\right)\) bits to code that number. For example, suppose that our file derives from a common FASTQ file (i.e., a file that considers only one of the two strands) and that now we need to code CCAACCCCAAA. If we have allowed two bits for the coding of the repetitions of both C and A, then we will code up to three repetitions with the first two bits. When we code \"three\" with these two bits, the next four bits will still refer to the same base and will be used to code zero (no more), one (five total), two (six total), or three (seven total) repetitions, and so on. In our example, we will need two bits to code a C, then two bits to code one more repetition of C. Two bits for A, two bits to code two more repetitions of A. Two bits for C, two bits to code three more repetitions of C, two bits to code one more repetition of C (for a total of five Cs). The previous two bits shall also code the stop of the repetitions of C. Then two bits for A and two bits to code two more repetitions of A. The total number of bits needed by our example is 18 bits. By coding two bits for character, 26 bits would have been necessary. If the compressor can see the file to be compressed in advance, it can establish the optimal number of bits to code the repetitions of each base and it can send this number, together with the compressed file, to the decompressor. This will improve the compression, and the amount of data needed for this communication will be negligible with respect to the size of the compressed file. However, if the compressor and decompressor work in lockstep, (i.e., on-line compression), then it is possible for both compressor and decompressor to estimate at run time, adaptively, the number of bits needed to code the repetitions for each base. The price we pay, in this case, is sometimes a very small increment in the compressed file dimension. Other times, for longer files, to have the possibility of a variable length encoding of the repetitions can bring advantages. ```
\(\bullet\) \(x\) = readnextbase (\(F\)); do  output 2 bits coding \(x\); \(count=0\); while (\(y\) = readnextbase (\(F\)) == \(x\)) count++;  while (\(count>=2^{\textit{maxrep}\;(x)}-1\)) do begin  output maxrep (\(x\)) bits, all set to 1; \(count=count-2^{\textit{maxrep}\;(x)}-1\); \(\circ\) end while  output maxrep (\(x\)) bits coding in decimal count; \(x=y\); while (\(not\) EOF(\(F\)));
```  
**Algorithm 1**Coding  
```
\(\bullet\)  receive 2 bits and decode next base \(x\); \(count=1\); do  receive maxrep (\(x\)) bits in \(y\); \(count=count+\text{decimalvalue }(y)\); while (decimalvalue (\(y\)) = \(2^{\textit{maxrep}\;(x)}-1\));  output count occurrences of \(x\); while (therearemorebitstodecode (\(0\)));
```  
**Algorithm 2**Decoding  
_Experimental Results: Compressing DNA Files_  
This new representation of the DNA data is shorter than the original text file and it is easier to compress. To experimentally test the algorithm, we considered a test data set composed by six commonly used DNA files: _Lambda Virus_ (file size: 48,502 bytes), _Homo sapiens.GRCh38.dna_ (file size: 3,072,712,323 bytes), _SRR741411\(2\) (file size: 7,982,945,875 bytes), _Mais_ (file size: 2,104,355,422 bytes), _Cricetus_ (file size: 2,320,022,665 bytes), _Pinus_ (file size: 20,547,720,415 bytes). All those files have been preprocessed from the original FASTA format to include only the nitrogen bases. Our coding strategy was used in combination with standard compression tools and we compared the compression results obtained, with or without this coding. The coding parameters were adaptively estimated on-line and, for double-stranded FASTQ files, the coding of successive, identical, couples of nitrogen bases was optimized by considering the repetitions of the first base in the couple. The experimental results obtained are summarized in Tables 2 and 3.