DNA Sequence Compression using ERGC and NRGC for Better Compression

Author Name:
Author Email:

Abstract

Current improvements in computing technology makes it possible and very easy to build genomic sequences from the billions of reads within a minimal cost and time. In this article, we are proposing an algorithm which is analyzing two compression algorithms Efficient Referential Genome Compression algorithm and Novel Referential Genomic Compression algorithm. Both are effective genomic compression algorithms. The proposed algorithm is analyzing their behaviour for different types of DNA sequences as reference and target genome to produce a result which can predict in which circumstances one algorithm outper-forms other and vice versa. The proposed algorithm analyses the inherent structure of target and reference genomes and predicts the better compression algorithm. Then it compresses the target sequence using predicted algorithm. Proposed algorithm’s experimental results prove that it works better than all existing algorithms in this field.

Introduction

Huge sized data leads to many problems during data transfer over Internet. If the data size is huge it creates a lot of burden over the Internet during transmission. It also occupies a huge space in the local systems. One major side effect of huge data is network congestion. Huge transmission cost is another factor which happens due to large size of data. To remediate these problems, data compression is a very essential tool. For the compression of general purpose data, various tools are available in the market. These general-purpose compression algorithms run very effectively on general purpose data which we use in day to day life. But they are not suitable to compress special data such as DNA sequences which has their own specific structures. Due to this, such type of general purpose compression algorithm is a poor choice to compress DNA sequences. To compress the data such as DNA sequences, some compression algorithms which makes use of the specific structures of DNA sequences to compress them more efficiently. The algorithms ERGC and NRGC achieves compression ratios which is better than the current best algorithms. Compression ratio is the ratio of the uncompressed data size to the compressed data size.

Conclusion

Data compression is a most typical problem in biology especially for NGS data. In this article, we have proposed a comparison algorithm to compare ERGC and NRGC and to use reference based compression efficiently and effectively. It is evident from the simulation results that the proposed algorithm is indeed an effective compressor compared with the state-of-the-art algorithms existing in the current literature. Our algorithm works better in terms of time complexity than the already existing compression algorithms.

 

References

  • Ahn,S.-M. et al. (2009) The first Korean genome sequence and analysis: full genome sequencing for a socio-ethnic group. Genome Res., 19, 1622{1629.

 

  • Altschul,S.F. et al. (2004) Basic local alignment search tool. J. Mol. Biol., 215, 403{410.

 

  • Brandon,M.C. et al. (2009) Data structures and compression algorithms for genomic sequence data. Bioinformatics, 25, 1731{1738.

 

  • Cao,M.D. et al. (2007) A simple statistical algorithm for biological sequence compression. Proceedings of the 2007 IEEE Data Compression Conference (DCC 07), pp. 43{52.

 

  • Christley, S. et al. (2009) Human genomes as email attachments. Bioinformatics, 25, 274{275.

 

  • Deorowicz,S. et al. (2013) Genome compression: a novel approach for large collections. Bioinformatics, 29, 1{7.

 

  • Deorowicz,S. and Grabowski,S. (2011) Robust relative compression of genomes with random access. Bioinformatics, 27, 2979{2986.

 

  • Golomb,S.W. (1966) Run-length encodings. IEEE Trans. Inform. Theor., 12, 399{401.

 

  • Hu man,D. (1952) A method for the construction of minimum-redundancy codes. Proc. Inst. Radio Eng., 1098{1101.

 

  • Kurtz,S. et al. (2004) Versatile and open software for comparing large genomes. Genome Biol., 5, R12.

 

  • Levy, S. et al. (2008) The diploid genome sequence of an Asian individual. Nature, 456, 60{66.

 

  • Mo at, A. (1990) Implementing the PPM data compression scheme. IEEE Trans. Commun., 38, 1917{1921.

 

]13] Ochoa,I. et al. (2014) iDoComp: a compression scheme for assembled genomes. Bioinformatics, 31, 626{633.

 

  • Pavlichin,D. et al. (2013) The human genome contracts again. Bioinformatics, 29, 2199{2202.

 

  • Peter,E. (1975) Universal codeword sets and representations of the integers. IEEE Trans. Inform. Theor., 21, 194{203.

 

  • Pinho,A.J. et al. (2012) GReEn: a tool for efficient compression of genome resequencing data. Nucleic Acids Res., 40, e27.

 

  • Saha,S. and Rajasekaran,R. (2015) ERGC: an efficient referential genome compression algorithm. Bioinformatics, 31, 3468{3475.

 

  • Shanika,K. et al. (2011) Optimized relative lempel-ziv compression of genomes. 34thAus-tralasian Computer Science Conference, 113, pp. 91{98.

 

  • Stephens,Z.D. et al. (2015) Big data: astronomical or genomical? PLoS Biol., 13, e1002195.

 

  • Wang,C. and Zhang,D. (2011) A novel compression tool for efficient storage of genome resequencing data. Nucleic Acids Res., 39, E45{U74.

 

  • Ziv, J. and Lempel, A. (1977) A universal algorithm for sequential data compression. IEEE Trans Inform. Theor., 23, 337{343.

 

 

  • Subrata Saha, Sanguthevar Rajasekaran Bioinformatics NRGC: a novel referential genome compression algorithm (01 August 2016)

 

Comment on: `ERGC: an efficient referential genome compression algorithm’ Sebastian Deorowicz Szymon Grabowski Idoia Ochoa Mikel Hernaez Tsachy Weissman Bioinformatics(2015) 32 (7): 1115-1117.

 

  • Subrata Saha Sanguthevar Rajasekaran Bioinformatics (2015) Authors’ response to `Comment on: ERGC: An efficient Referential Genome Compression Algorithm 32 (7): 1118-1119.

 

  • Fritz,M.H.-Y. et al. (2011) Efficient storage of high throughput DNA sequencing data using reference-based compression. Genome Res., 21, 734{740.

 

  • Sara A.Shehab, Arabi Keshk, Hany Mahgoub (2012) Fast Dynamic Algorithm for Sequence Alignment based on Bioinformatics

 

  • Chandrasai Potladurthi, Shyam Perugu, Durga Bhavani S (2014) Deciphering the sequence alignment by Needleman-Wunsch algorithm on to reduce computational time via high performance computing

 

  • Mo at, Dept. of Computer Sci., Melbourne Univ., Parkville, Vic., Australia, Imple-menting the PPM data compression scheme : 1917 – 1921,Nov 1990

 

  • Idoia Ochoa,Mikel Hernaez, Tsachy Weissman(2014) iDoComp: a compression scheme for assembled genomes

 

  • Sebastian Deorowicz, Agnieszka Danek, Marcin Niemiec (2015), GDC 2: Compression of large collections of genomes

 

  • Tom Madden, The BLAST Sequence Analysis Tool

 

  • Trevor Dale, (1999) Human Genome Project Essay

 

  • Davis MW, Hammarlund M (2006), Single-nucleotide polymorphism mapping

DOWNLOAD THE COMPLETE RESEARCH PAPER PDF

19 total views, 0 views today

About the author: dev