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. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1109/tcbb.2007.1017 | Computational Biology and Bioinformatics, IEEE/ACM Transactions |
Keywords | Field | DocType |
DNA,biology computing,decision making,molecular biophysics,DNA files,Markovian dependencies,annotated nucleotide sequences,decision-making,grammar parser,4 [Data]: Coding and Information Theory | Data compaction and compression,Annotation,Compression,F.4 [Theory of Computation]: Mathematical Logic and Formal Languages | Formal languages,Formal Grammars,G.3 [Mathematics of Computing]: Probability and Statistics | Markov processes,J.3 [Computer Applications]: Life and Medical Sciences | Biology and genetics,Nucleotide sequences | Annotation,Computer science,Nucleic acid sequence,Grammar,Artificial intelligence,Natural language processing,Nucleotide,Machine learning,Lossless compression | Journal |
Volume | Issue | ISSN |
4 | 3 | 1545-5963 |
Citations | PageRank | References |
4 | 0.45 | 24 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gergely Korodi | 1 | 78 | 5.57 |
Ioan Tabus | 2 | 276 | 38.23 |