ERGC: an efficient referential genome compression algorithm
Open Access
- 2 July 2015
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 31 (21) , 3468-3475
Abstract
Motivation: Genome sequencing has become faster and more affordable. Consequently, the number of available complete genomic sequences is increasing rapidly. As a result, the cost to store, process, analyze and transmit the data is becoming a bottleneck for research and future medical applications. So, the need for devising efficient data compression and data reduction techniques for biological sequencing data is growing by the day. Although there exists a number of standard data compression algorithms, they are not efficient in compressing biological data. These generic algorithms do not exploit some inherent properties of the sequencing data while compressing. To exploit statistical and information-theoretic properties of genomic sequences, we need specialized compression algorithms. Five different next-generation sequencing data compression problems have been identified and studied in the literature. We propose a novel algorithm for one of these problems known as reference-based genome compression. Results: We have done extensive experiments using five real sequencing datasets. The results on real genomes show that our proposed algorithm is indeed competitive and performs better than the best known algorithms for this problem. It achieves compression ratios that are better than those of the currently best performing algorithms. The time to compress and decompress the whole genome is also very promising. Availability and implementation: The implementations are freely available for non-commercial purposes. They can be downloaded from http://engr.uconn.edu/∼rajasek/ERGC.zip. Contact:rajasek@engr.uconn.eduKeywords
This publication has 17 references indexed in Scilit:
- Binary Interval Search: a scalable algorithm for counting interval intersectionsBioinformatics, 2012
- GReEn: a tool for efficient compression of genome resequencing dataNucleic Acids Research, 2011
- A novel compression tool for efficient storage of genome resequencing dataNucleic Acids Research, 2011
- Efficient storage of high throughput DNA sequencing data using reference-based compressionGenome Research, 2011
- The first Korean genome sequence and analysis: Full genome sequencing for a socio-ethnic groupGenome Research, 2009
- Data structures and compression algorithms for genomic sequence dataBioinformatics, 2009
- The diploid genome sequence of an Asian individualNature, 2008
- A universal algorithm for sequential data compressionIEEE Transactions on Information Theory, 1977
- Universal codeword sets and representations of the integersIEEE Transactions on Information Theory, 1975
- Run-length encodings (Corresp.)IEEE Transactions on Information Theory, 1966