{'fraction_non_alphanumeric': 0.028439388553146108, 'fraction_numerical': 0.013864201919658727, 'mean_word_length': 4.516666666666667, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Genome Compression Against a Reference

Being able to store and transmit human genome sequences is an important part in genomic research and industrial applications. The complete human genome has 3.1 billion base pairs (haploid), and storing the entire genome naively takes about 3 GB, which is infeasible for large scale usage. However, human genomes are highly redundant. Any given individual's genome would differ from another individual's genome by less than 1%. There are tools like DNAZip, which express a given genome sequence by only noting down the differences between the given sequence and a reference genome sequence. This allows losslessly compressing the given genome to ~ 4 MB in size. In this work, we demonstrate additional improvements on top of the DNAZip library, where we show an additional ~ 11% compression on top of DNAZip's already impressive results. This would allow further savings in disk space and network costs for transmitting human genome sequences.


Introduction
Genomes are usually distributed in two formats. Firstly, using the FASTA format. Secondly, and more commonly as two files, one containing the SNPs (Single Nucleotide Polymorphisms), and the other containing insertions and deletions, both with respect to a reference genome (usually hg18 [2,3]).
While the size of a pure FASTA-based genome is about 3 GB, using the second format as mentioned above, James Watson's genome was expressed in about 1.8 GB [7], with reference to the hg18 genome.
The DNAZip project [4] makes use of the database of all SNPs reported (db-SNP) and the hg18 genome to represent this information cleverly in about 4.1 MB. We intend to represent this information in an even more efficient format, and reduce the size of the genome further, without using any extra information.

Relevant Work
The following techniques are used by DNAzip to achieve compression.
1. Variable size integer representation and delta positions: In the variation data, all the variation (indels and SNPs) are expressed as position on the reference genome, plus the variation actually present. The position is expressed as an offset from the beginning of the sequence. Thus, the size required to store the position increases while storing variations at the end of the genome. Instead of storing the entire offset, it is sufficient to store just the delta from the previous variation. One problem with this is that an integer value takes the same amount of space to store, regardless of the value within it.
Thus, by implementing a mechanism to store exactly as many bits are required, storage utilized could be optimized. A variable integer as implemented by DNAzip uses 7 of 8 bits in a character to store the bits of the integer, and 1 bit to indicate whether an integer ends at that byte or not.

K-mer partitioning
A common compression technique used is Huffman coding. By partition-4 ing all the insertion data into K-mers and inserting them into a Huffman tree, the optimal representation of each k-mer can be obtain, and this representation is then stored, thus achieving some level of compression. Compressing the bit-vectors using Huffman Encoding with k-mers of size 5 resulted in the genome being of size 3896467 bytes. While using k-mers of size 6 resulted in the genome being of size 3889100 bytes. This is against the original file of size 4198717 bytes. Thus, using k-mers of size 6, we decreased the size of the genome by 302.36 KB, which is a space-saving of 7.37%. The values being written as VINTs during the compression process were written to an auxilliary file. We then tried to compare the space consumed when the size of the VINT word size is varied. The actual compression received from this was 129 KB roughly, which was in line with our expectation before this experiment.

DELs)
After thorough analysis, we realized that the Insertion/Deletion format in iteself was pretty packed. One optimization possible was to create a Bit Vector for the Insertions and Deletions which were present in dbSNP. This meant that we would not need to store the information for the insertions and deletions which existed in the dbSNP. A bit vector for the insertions / deletions present in db-SNP could be used to encode that information.
The number of deletions in the genome which also existed in dbSNP, was significant but not large enough (Refer Table 2). The percentage of deletions in a chromosome which exist in dbSNP varies from 5.3% to 11.68% (apart from the Mitochondrial DNA, which has only one deletion, which does not exist in dbSNP).
We compressed the bit vector using Run-Length Encoding. This gave us a saving of about 10 KB. Using Huffman Encoding gave us a saving of roughly 20 KB. Another 1 KB of compression was squeezed in by noticing that the bit vector was sparser than the SNP bit vector, and a k-mer length of size 7 was the most suitable for this.
Thus, we only changed the storage for the deletions. The deletions which were present in dbSNP were stored using bitvectors, and compressed using Huffman Encoding with k-mer size as 7.
For insertions we noticed that the number of insertions in the Genome which existed in dbSNP were very few. Thus, the bit vector was extremely sparse.
And hence, there was not much benefit of encoding them as bit-vectors.  It is possible to make the DNAZip utility more useful. A few of them are as follows: 1. Allowing compression and decompression on a chromosome-by-chromosome basis.
2. There is scope for constant-factor improvement in DNAzip's performance, this could be done by using C-style data structures instead of the C++ STL data structures being used.