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. |
