# Compression of Next-Generation Sequencing Data and of DNA Digital Files +
## 4 DNA Compression  
There are four nitrogen bases that make up DNA. They are Adenine (A), Cytosine (C), Guanine (G), and Thymine (T). In double-stranded DNA, each of these can only be linked to a single nitrogen base: Guanine can only bind with Cytosine (and vice versa) while Adenine can only bind with Thymine (and vice versa). Therefore, to memorize a DNA sequence, only one base of each couple (for example, the first element of each couple) need to be coded since the other can be easily deducted [4]. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Sequences** & **Description** & **Format** & **Size** \\ \hline GM-12878-CYTOSOL & Short RNA & FASTQ & 5.31 GB \\ GM-12878-CYTOSOL & Short RNA & BAM & 29.1 MB \\ GM-12801S4 & Repli-Seq Illumina & FASTQ & 1.01 GB \\ BG02-1-DS9028-FC20 EM7-1 & Repli-Seq Illumina & FASTQ & 739.6 MB \\ BG02-1-DS9028-FC20 EMB-6 & Repli-Seq Illumina & FASTQ & 797.3 MB \\ NA12156 (No graph) & CEPH/UTAH PED. 1408 & BAM & 8.8 MB \\ GM-06990S3 & Repli-Seq Illumina & BAM & 288.3 MB \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Test data set. Figure 1: Quip, gzip, and bzip2: experimental results. DNA sequencing is normally obtained from a single strand, and the genomic files in FASTA or FASTQ format almost always concern a single-stranded sequence from which the double-stranded DNA can be easily retrieved by coupling each base in the single strand with the other, complementary, base (see [4]). Even by doing this (and saving about half of the coding), DNA files are very heavy and need several Gigabytes of memory. This of course makes it difficult to store them or to transmit them efficiently. Here we present an approach to DNA compression that will only consider the relevant DNA data: the combination of the nitrogen bases. By working on such files, we can easily compare and study the DNA of living organisms--even better than with FASTA or FASTQ files. Suppose we have a file that contains only combinations of the four nitrogen bases. For example, if we begin with a file in the FASTA format, we first need to preprocess the file by considering only one strand (in case the file reports both strands of a double-stranded DNA) and by removing all the other information that do not refer directly to DNA--leaving in the file with all the sequences of nitrogen bases. We can code each of the four nitrogen bases with only two bits. The way DNA is made and the fact that only four nitrogen bases are present in the file often brings repeated sequences of the same character in the file. Therefore, we can implement a compression algorithm that is theoretically based on run length encoding. The coding of a DNA sequence will be done by coding each nitrogen base by using two bits. Given that the bases are often consecutively repeated in the text, after coding a base, we will code the number of consecutive occurrences of that base. This number of occurrences can be potentially unlimited and, therefore, we need a strategy to represent it in a decodable way. For each base we choose to code this number by using first a fixed number of bits that depends on the base and on the file to be coded. Algorithm 1 and Algorithm 2 present the basic encoding and decoding steps. Suppose we have associated to each base \(x\) a function \(\mathit{maxrep}\left(x\right)\), where \(2^{\mathit{maxrep}\left(x\right)}-2\) indicates the maximum number of expected consecutive repetitions for that base in the input file. _maxrep_\(\left(x\right)\), for each base \(x\), can be computed by preprocessing the input file and by sending the maxrep numbers to the decoder. Another possibility for managing the maxrep numbers is to initialize these values to a common value and subsequently to use a wise management of the decoded information that leads to a run time adjustment done consistently by encoder and decoder. In Algorithm 1, we read a base from the input file, we output two bits to code the base and then we count how many consecutive repetitions of that base are present.