Regular Paper: Review PaperNo Access

Advances in high throughput DNA sequence data compression

Muhammad Sardaraz

Department of Computer Science, University of Wah, Quaid Avenue, Wah Cantt 47040, Pakistan

E-mail Address: m.sardaraz@uow.edu.pk

Corresponding author.

Search for more papers by this author

Muhammad Tahir

Department of Computer Science, University of Wah, Quaid Avenue, Wah Cantt 47040, Pakistan

E-mail Address: muhammad.tahir@uow.edu.pk

Search for more papers by this author

, and

Ataul Aziz Ikram

Department of Electrical Engineering, National University, Islamabad 44000, Pakistan

E-mail Address: ata.ikram@nu.edu.pk

Search for more papers by this author

https://doi.org/10.1142/S0219720016300021Cited by:19 (Source: Crossref)

Abstract

Advances in high throughput sequencing technologies and reduction in cost of sequencing have led to exponential growth in high throughput DNA sequence data. This growth has posed challenges such as storage, retrieval, and transmission of sequencing data. Data compression is used to cope with these challenges. Various methods have been developed to compress genomic and sequencing data. In this article, we present a comprehensive review of compression methods for genome and reads compression. Algorithms are categorized as referential or reference free. Experimental results and comparative analysis of various methods for data compression are presented. Finally, key challenges and research directions in DNA sequence data compression are highlighted.

Keywords:

References

1. F Sanger, S Nicklen and AR Coulson, DNA sequencing with chain-terminating inhibitors, Proc. Nat. Acad. Sci. 74 (1977) 5463–5467. Crossref, Medline, Google Scholar
2. M Margulies, M Egholm, WE Altman et al., Genome sequencing in microfabricated high-density picolitre reactors, Nature 437 (2005) 376–380. Crossref, Medline, Google Scholar
3. J Shendure and H Ji, Next-generation DNA sequencing, Nature Biotechnol. 26 (2008) 1135–1145. Crossref, Medline, Google Scholar
4. D Branton, DW Deamer, A Marziali et al., The potential and challenges of nanopore sequencing, Nature Biotechnol. 26 (2008) 1146–1153. Crossref, Google Scholar
5. ML Metzker, Sequencing technologies — the next generation, Nature Rev. Genet. 11 (2010) 31–46. Crossref, Medline, Google Scholar
6. Z Zhu, Y Zhang, Z Ji et al., High-throughput DNA sequence data compression, Brief. Bioinform. 16 (2013) 1–15. Crossref, Medline, Google Scholar
7. S Deorowicz and S Grabowski, Data compression for sequencing data, Algorithms Mol. Biol. 8 (2013) 25. Crossref, Medline, Google Scholar
8. http://www.omicsmaps.com/ (18 Feb 2015, date last accessed). Google Scholar
9. A RO and A RE, Will computers crash genomics?, Science 5 (2010) 1190. Google Scholar
10. SD Kahn, On the future of genomic data, Science 331 (2011) 728–729. Crossref, Medline, Google Scholar
11. M Sardaraz, M Tahir, AA Ikram et al., SeqCompress: An algorithm for biological sequence compression, Genomics 104 (2014) 225–228. Crossref, Medline, Google Scholar
12. www.7-zip.org (15 Jan 2015, date last accessed). Google Scholar
13. http://www.gzip.org/ (15 Jan 2015, date last accessed). Google Scholar
14. http://www.bzip.org/ (15 Jan 2014, date last accessed). Google Scholar
15. NS Bakr and AA Sharawi, DNA lossless compression algorithms: Review, Am. J. Bioinf. Res. 3 (2013) 72–81. Google Scholar
16. MC Brandon, DC Wallace and P Baldi, Data structures and compression algorithms for genomic sequence data, Bioinformatics 25 (2009) 1731–1738. Crossref, Medline, Google Scholar
17. S Golumb, Golumb Code: Run-length Encodings, IEEE Trans. Inf. Theory 12 (1966) 399–401. Crossref, Google Scholar
18. P Elias, Universal codeword sets and representations of the integers, IEEE Trans. Inf. Theory 21 (1975) 194–203. Crossref, Google Scholar
19. DA Huffman, A method for the construction of minimum redundancy codes, Proc. IRE 40 (1952) 1098–1101. Crossref, Google Scholar
20. S Christley, Y Lu, C Li et al., Human genomes as email attachments, Bioinformatics 25 (2009) 274–275. Crossref, Medline, Google Scholar
21. C Wang and D Zhang, A novel compression tool for efficient storage of genome resequencing data, Nucleic Acids Res. 39 (2011) e45. Crossref, Medline, Google Scholar
22. AJ Pinho, D Pratas and SP Garcia, GReEn: A tool for efficient compression of genome resequencing data, Nucleic Acids Res. 40 (2012) e27. Crossref, Medline, Google Scholar
23. I Ochoa, M Hernaez and T Weissman, iDoComp: a compression scheme for assembled genomes, Bioinformatics 3 (2014) 626–633. Google Scholar
24. S Deorowicz and S Grabowski, Robust relative compression of genomes with random access, Bioinformatics 27 (2011) 2979–2986. Crossref, Medline, Google Scholar
25. S Deorowicz, A Danek and M Niemiec, GDC 2: Compression of large collections of genomes, Sci. Rep. 5 (2015) 1–12. Crossref, Google Scholar
26. S Wandelt and U Leser, FRESCO: Referential compression of highly similar sequences, IEEE/ACM Trans. Computat. Biol. Bioinf. 10 (2013) 1275–1288. Crossref, Medline, Google Scholar
27. T Bose, MH Mohammed, A Dutta et al., BIND–An algorithm for loss-less compression of nucleotide sequence data, J. Biosci. 37 (2012) 785–789. Crossref, Medline, Google Scholar
28. MH Mohammed, A Dutta, T Bose et al., DELIMINATE — a fast and efficient method for loss-less compression of genomic sequences sequence analysis, Bioinformatics 28 (2012) 2527–2529. Crossref, Medline, Google Scholar
29. S Kuruppu, B Beresford-Smith, T Conway et al., Iterative dictionary construction for compression of large DNA data sets, IEEE/ACM Trans. Comput. Biol. Bioinf. 9 (2012) 137–149. Crossref, Medline, Google Scholar
30. AJ Pinho and D Pratas, MFCompress: A compression tool for FASTA and multi-FASTA data, Bioinformatics 30 (2014) 117–118. Crossref, Medline, Google Scholar
31. S Wandelt, M Bux and U Leser, Trends in genome compression, Curr. Bioinform. 9 (2014) 315–326. Crossref, Google Scholar
32. PJ Cock, CJ Fields, N Goto et al., The Sanger FASTQ file format for sequences with quality scores, and the Solexa/Illumina FASTQ variants, Nucleic Acids Res. 38 (2010) 1767–1771. Crossref, Medline, Google Scholar
33. H Li, B Handsaker, A Wysoker et al., The sequence alignment/map format and SAMtools, Bioinformatics 25 (2009) 2078–2079. Crossref, Medline, Google Scholar
34. R Giancarlo, SE Rombo and F Utro, Compressive biological sequence analysis and archival in the era of high-throughput sequencing technologies, Brief. Bioinform. 15 (2014) 390–406. Crossref, Medline, Google Scholar
35. K Daily, P Rigor, S Christley et al., Data structures and compression algorithms for high-throughput sequencing technologies, BMC Bioinform. 11 (2010) 514. Crossref, Medline, Google Scholar
36. MH-Y Fritz, R Leinonen, G Cochrane et al., Efficient storage of high throughput DNA sequencing data using reference-based compression, Genome Res. 21 (2011) 734–740. Crossref, Medline, Google Scholar
37. C Kozanitis, C Saunders, S Kruglyak et al., Compressing genomic sequence fragments using SlimGene, J. Comput. Biol. 18 (2011) 401–413. Crossref, Medline, Google Scholar
38. JK Bonfield and MV Mahoney, Compression of FASTQ and SAM format sequencing data, PloS one 8 (2013) e59190. Crossref, Medline, Google Scholar
39. N Popitsch and A von Haeseler, NGC: Lossless and lossy compression of aligned high-throughput sequencing data, Nucleic Acids Res. 41 (2013) e27. Crossref, Medline, Google Scholar
40. F Hach, I Numanagiæ, C Alkan et al., SCALCE: Boosting sequence compression algorithms using locally consistent encoding, Bioinformatics 28 (2012) 3051–3057. Crossref, Medline, Google Scholar
41. DC Jones, WL Ruzzo, X Peng et al., Compression of next-generation sequencing reads aided by highly efficient de novo assembly, Nucleic Acids Res. 40 (2012) e171. Crossref, Medline, Google Scholar
42. Y Zhang, L Li, Y Yang et al., Light-weight reference-based compression of FASTQ data, BMC Bioinform. 16 (2015) 188. Crossref, Medline, Google Scholar
43. G Menconi, V Benci and M Buiatti, Data compression and genomes: A two-dimensional life domain map, J. Theor. Biol. 253 (2008) 281–288. Crossref, Medline, Google Scholar
44. W Tembe, J Lowey and E Suh, G-SQZ: Compact encoding of genomic sequence and quality data, Bioinformatics 26 (2010) 2192–2194. Crossref, Medline, Google Scholar
45. V Bhola, AS Bopardikar, R Narayanan et al., No-reference compression of genomic data stored in fastq format, 2011 IEEE Int. Conf. on Proc: Bioinformatics and Biomedicine (BIBM) (2011) 147–150. Google Scholar
46. S Deorowicz and S Grabowski, Compression of DNA sequence reads in FASTQ format, Bioinformatics 27 (2011) 860–862. Crossref, Medline, Google Scholar
47. V Yanovsky, ReCoil-an algorithm for compression of extremely large datasets of dna data, Algorithms Mol. Biol. 6 (2011) 23. Crossref, Medline, Google Scholar
48. Z Zhu, J Zhou, Z Ji et al., DNA sequence compression using adaptive particle swarm optimization-based memetic algorithm, IEEE Trans. Evol. Comput. 15 (2011) 643–658. Crossref, Google Scholar
49. W-H Chen, Y-W Lu, F Lai et al., Integrating human genome database into electronic health record with sequence alignment and compression mechanism, J. Med. Syst. 36 (2012) 2587–2597. Crossref, Medline, Google Scholar
50. AJ Cox, MJ Bauer, T Jakobi et al., Large-scale compression of genomic sequence databases with the Burrows–Wheeler transform, Bioinformatics 28 (2012) 1415–1419. Crossref, Medline, Google Scholar
51. R Wan, VN Anh and K Asai, Transformations for the compression of FASTQ quality scores of next-generation sequencing data, Bioinformatics 28 (2012) 628–635. Crossref, Medline, Google Scholar
52. SC Sahinalp and U Vishkin, Efficient approximate and dynamic matching of patterns using a labeling paradigm, Proc. 37th Annual Symp. on Foundations of Computer Science (1996) 320–328. Google Scholar
53. S Pathak and S Rajasekaran, LFQC: A lossless compression algorithm for FASTQ files, Bioinformatics (2014). Medline, Google Scholar
54. Ł Roguski and S Deorowicz, DSRC 2 — Industry-oriented compression of FASTQ files, Bioinformatics 30 (2014) 2213–2215. Crossref, Medline, Google Scholar
55. J Zhou, Z Ji, Z Zhu et al., Compression of next-generation sequencing quality scores using memetic algorithm, BMC Bioinform. 15 (2014) S10. Crossref, Medline, Google Scholar
56. G Benoit, C Lemaitre, D Lavenier et al., Compression of high throughput sequencing data with probabilistic de Bruijn graph, arXiv preprint arXiv:1412.5932, 2014. Google Scholar
57. S Grabowski, S Deorowicz and Ł Roguski, Disk-based genome sequencing data compression, Bioinformatics 31 (2015) 1389–1395. Crossref, Medline, Google Scholar
58. M Roberts, W Hayes, BR Hunt et al., Reducing storage requirements for biological sequence comparison, Bioinformatics 20 (2004) 3363–3369. Crossref, Medline, Google Scholar
59. I Ochoa, H Asnani, D Bharadia et al., QualComp: A new lossy compressor for quality scores based on rate distortion theory, BMC Bioinform. 14 (2013) 187. Crossref, Medline, Google Scholar
60. R Cánovas, A Moffat and A Turpin, Lossy compression of quality scores in genomic data, Bioinformatics 30 (2014) 2130–2136. Crossref, Medline, Google Scholar
61. G Malysa, M Hernaez, I Ochoa et al., QVZ: Lossy compression of quality values, Bioinformatics 2015 (2015) 1–8. Google Scholar
62. F Yang, N Chia, BA White et al., Compression-based distance (CBD): A simple, rapid, and accurate method for microbiota composition comparison, BMC Bioinform. 14 (2013) 136. Crossref, Medline, Google Scholar
63. NJ Hudson, LR Porto-Neto, J Kijas et al., Information compression exploits patterns of genome composition to discriminate populations and highlight regions of evolutionary interest, BMC Bioinform. 15 (2014) 66. Crossref, Medline, Google Scholar
64. NH Tran and X Chen, Comparison of next-generation sequencing samples using compression-based distances and its application to phylogenetic reconstruction, BMC Res. Notes 7 (2014) 320. Crossref, Medline, Google Scholar
65. M Sardaraz, M Tahir, AA Ikram et al., Cluster based reference of phylogenetic Treess uing hadoop/mapreduce, Int. J. Acad. Res. 7 (2015) 9–14. Google Scholar
66. S Wandelt, J Starlinger, M Bux et al., RCSI: Scalable similarity search in thousand (s) of genomes, Proc. VLDB Endowment 6 (2013) 1534–1545. Crossref, Google Scholar
67. A Danek, S Deorowicz and S Grabowski, Indexes of large genome collections on a PC, PLOS one 10 (2014) e0128172. Google Scholar
68. J Sirén, N Valimaki and V Makinen, Indexing graphs for path queries with applications in genome research, IEEE/ACM Trans. Comput. Biol. Bioinf. 11 (2014) 375–388. Crossref, Medline, Google Scholar
69. AA Ikram, S Ibrahim, M Sardaraz et al., Neural network based cloud computing platform for bioinformatics, Proc Systems, Applications and Technology Conf. (LISAT), New York (2013) 1–6. Google Scholar