Advanced DNA sequence compression algorithm

Abstract

In this thesis we propose an advanced DNA sequence compression algorithm, which is efficient and lossless. None of the available general-purpose compression algorithm compresses these sequences. This is due to the specificity of the genetic sequences. It is believed that DNA sequence encodes life in a nonrandom way. Some important sections of the sequences are shifted, reserved, duplicated, or reversed during evolutions. Despite the apparently chaotic randomness, those repeats undergo elementary mutations mostly during DNA replication in successive cell divisions, and then become approximate repeats. This idea motivates us to locate these segments. Our DNA compression algorithm consists of three phases. First, we build a suffix tree to locate exact repeats. Then, we extend the exact repeats into approximate repeats and the best possible combinations of non-overlapping repeats are found to compress the DNA sequence. Finally, we use two sets of codes: two bit per base for exact and approximate repeats, and arithmetic encoding for non-repeat regions. For encoding the numbers in self-delimited way, the Fibonacci encoding method is used. The time complexity of our algorithm is bounded by O(ISI +llkl\ where 151is the length of the input sequence, I is the average length of repeats and Ikl is the maximum number of repeats among all the repeat groups. We tested our proposed algorithm using some standard DNA test Sequences and the result shows that our algorithm do better than the Cfact, GenCompress and some other algorithm by several orders of magnitude. Moreover, the proposed algorithm can be used to compress long sequences with millions of bases or more.