A Simple Statistical Algorithm for Biological Sequence Compression
The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Abstract
This paper introduces a novel algorithm for biological sequence compression that makes use of both statistical properties and repetition within sequences. A panel of experts is maintained to estimate the probability distribution of the next symbol in the sequence to be encoded. Expert probabilities are combined to obtain the final distribution. The resulting information sequence provides insight for further study of the biological sequence. Each symbol is then encoded by arithmetic coding. Experiments show that our algorithm outperforms existing compressors on typical DNA and protein sequence datasets while maintaining a practical running time.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A universal algorithm for sequential data compression
Ziv, J., & Lempel, A. (1977) · IEEE Transactions on Information Theory · doi:10.1109/tit.1977.1055714 · Cited by 5,456
Compression of individual sequences via variable-rate coding
Ziv, J., & Lempel, A. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055934 · Cited by 3,432 · cited 1×
“Examples of this category are the popular Lempel-Ziv compression algorithms [25, 26] and their variants.”
BackgroundArithmetic coding for data compression
Witten, I. H., Neal, R. M., & Cleary, J. G. (1987) · Communications of the ACM · doi:10.1145/214762.214771 · Cited by 2,877 · cited 1×
“To compress the sequence, we use arithmetic coding [24] to code each symbol based on the probability distribution combined from experts.”
MethodData Compression Using Adaptive Coding and Partial String Matching
Cleary, J., & Witten, I. (1984) · IEEE Transactions on Communications · doi:10.1109/tcom.1984.1096090 · Cited by 1,241 · cited 1×
“On the other hand, a statistical compression encoder such as prediction by partial match (PPM) [8] predicts the probability distribution of each symbol.”
BackgroundThe context-tree weighting method: basic properties
Willems, F. M. J., Shtarkov, Y. M., & Tjalkens, T. J. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.382012 · Cited by 919 · cited 1×
“The CTW+LZ algorithm developed by Matsumoto et al. [16] encodes significantly long repeats by the substitution method, and encodes short repeats and non repeat areas by context tree weighting [23].”
MethodA new challenge for compression algorithms: Genetic sequences
Grumbach, S., & Tahi, F. (1994) · Information Processing & Management · doi:10.1016/0306-4573(94)90014-0 · Cited by 272 · cited 2×
“The improved version, BioCompress-2 [12] uses a Markov model of order 2 to encode non-repeat regions.”
MethodA compression algorithm for DNA sequences and its applications in genome comparison
Chen, X., Kwong, S., & Li, M. (2000) · Proceedings of the fourth annual international conference on Computational molecular biology · doi:10.1145/332306.332352 · Cited by 218 · cited 2×
“Due to space limitations, we present here the most efficient algorithms, including BioCompress-2 (BioC) [12], GenCompress (GenC) [6], DNACompress (DNAC) [7], DNAPack (DNAP) [4], CDNA [15] and GeMNL [14].”
MethodDNACompress: fast and effective DNA sequence compression
Chen, X., Li, M., Ma, B., & Tromp, J. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.12.1696 · Cited by 209 · cited 2×
“The same compression technique is used in the DNACompress algorithm by Chen et al. [7], which finds significant inexact repeats in one pass and encodes these in another pass.”
MethodGrumbach, S., & Tahi, F. (2002) · DCC · doi:10.1109/dcc.1993.253115 · Cited by 204 · cited 1×
“The earliest special purpose DNA compression algorithm found in the literature is BioCompress developed by Grumbach and Tahi [11].”
MethodBiological sequence compression algorithms.
Matsumoto, T., Sadakane, K., & Imai, H. (2000) · PubMed · Cited by 132
Cited by
Efficient DNA sequence compression with neural networks
Silva, M., Pratas, D., & Pinho, A. J. (2020) · GigaScience · doi:10.1093/gigascience/giaa119 · Cited by 57
“Specifically, the XM algorithm [43] combines 3 types of experts, namely, repeat models, a low-order context model, and a short memory context model of 512 B.”
Metadata
- Authors
- Duc Cao, M., Dix, T. I., Allison, L., & Mears, C.
- Venue
- 2007 Data Compression Conference (DCC'07)
- Publisher
- IEEE
- Published
- 2007
- Pages
- 43-52
- ISSN
- 1068-0314 (ISSN-L)
- OpenAlex
- W2127912200
- Cited by
- 177
- References
- 20
- FWCI
- 4.34
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.