CIGARCoil: A New Algorithm for the Compression of DNA Sequencing Data
Abstract
DNA sequencing machines produce tens of thousands to hundreds of millions of reads. Each read
consists of letters from the alphabet X= {A, T, C, G, N} and varies in length between 30 to 120 characters
and beyond. The DNA reads are stored in a standard FASTQ file format that contains not only the reads
but also a quality score for each character in each read that corresponds to the probability that the
identified character is correct. The FASTQ files vary in size between 100s of megabytes to 10s of
gigabytes. The reads in the FASTQ files are processed as part of many DNA algorithms for various
sequence analyses. Given the fact that the size of each file is considerable, keeping and handling
multiple of these files in main memory for faster processing is not possible on commodity hardware. In
this thesis, we propose a lossless compression mechanism named CIGARCoil that operates on the FASTQ
files and other files that contain the DNA reads. The other salient features of CIGARCoil are:
• It is a not a reference-based algorithm in the sense that one does not need to create a reference
string before the compression can begin. Reference strings are undesirable due to them not only
being hard to determine, but also due to them being required for both the compression and
decompression of the file.
• In this thesis, for the first time, we show that each of the reads can be accessed directly on the
compressed structure created by CIGARCoil. That is, we provide access to each read without
having to uncompress the file.
• Since we can provide direct access to a read on the CIGARCoil compressed structure, we have
implemented a [] (square-bracket) array indexing operator. Through this implementation, we
can implement a predictive caching mechanism that will make the reads available for the enduser based on their access pattern.
We have analyzed our compressed mechanism on various well-known FASTQ data sets along with
synthetic data sets. In all cases, our compression method produces a compressed file that is smaller or
approximately the same size as ones created by the existing DNA compression mechanisms, including
BZIP, DSRC2, and LFQC.
Collections
- OU - Theses [2090]
The following license files are associated with this item: