Compression of annotated nucleotide sequences

IEEE/ACM Trans Comput Biol Bioinform. 2007 Jul-Sep;4(3):447-457. doi: 10.1109/tcbb.2007.1017.

Abstract

This article introduces an algorithm for the lossless compression of DNA files, which contain annotation text besides the nucleotide sequence. First a grammar is specifically designed to capture the regularities of the annotation text. A revertible transformation uses the grammar rules in order to equivalently represent the original file as a collection of parsed segments and a sequence of decisions made by the grammar parser. This decomposition enables the efficient use of state-of-the-art encoders for processing the parsed segments. The output size of the decision-making process of the grammar is optimized by extending the states to account for high-order Markovian dependencies. The practical implementation of the algorithm achieves a significant improvement when compared to the general-purpose methods currently used for DNA files.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Base Sequence
  • DNA / chemistry
  • DNA / classification*
  • DNA / genetics*
  • Data Compression / methods*
  • Databases, Genetic*
  • Documentation / methods*
  • Molecular Sequence Data
  • Natural Language Processing*
  • Sequence Analysis, DNA / methods*

Substances

  • DNA