Italiano (Italian) English (Inglese)
venerdì, 29 marzo 2024

Rapporti Tecnici

Dettagli rapporto tecnico
Autori:Giovanni Manzini
Marcella Rastero
Area Scientifica:Bioinformatics
Text Compression and Indexing
Titolo:A simple and Fast DNA Compressor
Apparso su:TR-INF-2003-04-03-UNIPMN
Editore:Computer Science Department, UPO
Anno:2003
URL:http://www.di.unipmn.it...R-INF-2003-04-03-UNIPMN.pdf
Sommario: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.