A simple and fast DNA compressor

Giovanni Manzini, Marcella Rastero

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)1397-1411
Number of pages15
JournalSoftware - Practice and Experience
Volume34
Issue number14
DOIs
Publication statusPublished - 25 Nov 2004
Externally publishedYes

Keywords

  • Approximate repeats encoding
  • DNA sequences
  • Data compression
  • Space economical algorithms

Fingerprint

Dive into the research topics of 'A simple and fast DNA compressor'. Together they form a unique fingerprint.

Cite this