Italiano (Italian) English (Inglese)
Tuesday, 12 December 2017

Technical Reports

Technical Report Details
Authors:Giovanni Manzini
Marcella Rastero
Scientific Area:Bioinformatics
Text Compression and Indexing
Title:A simple and Fast DNA Compressor
Published on:TR-INF-2003-04-03-UNIPMN
Publisher:Computer Science Department, UPO
Year:2003
URL:http://www.di.unipmn.it...R-INF-2003-04-03-UNIPMN.pdf
Abstract:In this paper we describe a new DNA compression algorithm. 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.