Compression of annotated nucleotide sequences.
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.
Korodi
Gergely
G
Tabus
Ioan
I
D000465:Algorithms; D001483:Base Sequence; D004247:DNA / Q000737:chemistry / Q000145:classification* / Q000235:genetics*; D044962:Data Compression / Q000379:methods*; D030541:Databases, Genetic; D004282:Documentation / Q000379:methods*; D008969:Molecular Sequence Data; D009323:Natural Language Processing; D017422:Sequence Analysis, DNA / Q000379:methods*
D004247:DNA