A simple and fast DNA compressor
- 25 August 2004
- journal article
- research article
- Published by Wiley in Software: Practice and Experience
- Vol. 34 (14) , 1397-1411
Abstract
In this paper we consider the problem of DNA compression. It is well known that one of the main features of DNA sequences is that they contain substrings which are duplicated except for a few random mutations. For this reason most DNA compressors work by searching and encoding approximate repeats. We depart from this strategy by searching and encoding only exact repeats. However, we use an encoding designed to take advantage of the possible presence of approximate repeats. Our approach leads to an algorithm which is an order of magnitude faster than any other algorithm and achieves a compression ratio very close to the best DNA compressors. Another important feature of our algorithm is its small space occupancy which makes it possible to compress sequences hundreds of megabytes long, well beyond the range of any previous DNA compressor. Copyright © 2004 John Wiley & Sons, Ltd.Keywords
This publication has 10 references indexed in Scilit:
- DNACompress: fast and effective DNA sequence compressionBioinformatics, 2002
- PatternHunter: faster and more sensitive homology searchBioinformatics, 2002
- Data compression with long repeated stringsInformation Sciences, 2001
- An information-based sequence distance and its application to whole mitochondrial genome phylogenyBioinformatics, 2001
- Off-line compression by greedy textual substitutionProceedings of the IEEE, 2000
- Sequence complexity for biological sequence analysisComputers & Chemistry, 2000
- Compressing Integers for Fast File AccessThe Computer Journal, 1999
- A new challenge for compression algorithms: Genetic sequencesInformation Processing & Management, 1994
- Arithmetic coding for data compressionCommunications of the ACM, 1987
- Efficient randomized pattern-matching algorithmsIBM Journal of Research and Development, 1987