A new approach in DNA sequence compression: Fast DNA sequence compression using parallel chaos game representation. (February 2019) - poor, Nafise Ramezani; Yaghoobi, Mahdi
Highlights: A new fast DNA sequence compression using parallel chaos game representation is proposed. The mechanism relies on compression DNA sequences using parallel chaos game representation. Chaos game is an iterative function to create a fractal image using DNA sequence. Frequency Chaos Game Representation uses the repetition of characters in DNA. This method demonstrate the high efficiency of the algorithm and the nice compression rate. Abstract: DNA sequence is a long string and contains some hidden significant genetic information which are considered by biological researchers in different laboratories, comparing genomes, medicine, engineering and etc. Due to ascending growth of DNA researches, users have faced some challenges in some fields like transfer, maintenance and data storage. Due to the large size of such sequences, there is a need to have a lot of space for storage, so a method is needed to reduce the amount of required space. Data compression may be an efficient way to reduce the size of DNA sequences and results in reduced storage space and transfer bandwidth requirements. Some patterns of effectiveness and importance of methods in compressing data can be seen in compressing existed sequences in database, compressing image and video and some standards like DICOM.The proposed algorithm is a hybrid one consisting of 4 phases: in phase 1 it divides the sequences into subsequences and takes a parallel chaos game representation approach, in phase 2 it replaces the high-frequency substrings using a dictionary method, in phase 3 it uses a parallel Hoffman coding approach, and in phase 4 it creates a structure based on Hoffman results. Since the algorithm runs in parallel mode and creates a dictionary for each subsequence, it increases the compression speed. Also due to the fact that CGR provides all possible patterns, there is no need to search for patterns and results in reduced computation complexity and time. Through the use of this method a benchmarked DNA string "MPOMTCG" gained a compression ratio of 1.6.