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
Significantly Lower Entropy Estimates for Natural DNA Sequences
Loewenstern, D., & Yianilos, P. N. (1999) · Journal of Computational Biology · doi:10.1089/cmb.1999.6.125 · Cited by 112 · cited 2×
“Due to space limitations, we present here the most ecient algorithms, including BioCompress-2 (BioC) [12], GenCompress (GenC) [6], DNACompress (DNAC) [7], DNAPack (DNAP) [4], CDNA [ 15 ] and GeMNL [14].”
A guaranteed compression scheme for repetitive DNA sequences
Rivals, É., Delahaye, J.-P., Dauchet, M., & Delgrange, O. (2002) · DCC · doi:10.1109/dcc.1996.488385 · Cited by 108 · cited 1×
“The Cfact DNA compressor developed by Rivals et al. [20] also searches for the longest exact repeats but is a two-pass algorithm.”
MethodAn efficient normalized maximum likelihood algorithm for DNA sequence compression
Korodi, G., & Tăbuş, I. (2005) · ACM Transactions on Information Systems · doi:10.1145/1055709.1055711 · Cited by 97 · cited 2×
“In the MNL algorithm by Tabus et al. [22] and its improvement, GeMNL by Korodi and Tabus [14], the DNA sequence is split into fixed size blocks.”
MethodNevill-Manning, C. G., & Witten, I. H. (1999) · DCC · doi:10.1109/dcc.1999.755675 · Cited by 95 · cited 2×
“Nevill-Manning and Witten [18] designed CP, a protein-oriented compression algorithm based on PPM.”
MethodDNA Compression Challenge Revisited: A Dynamic Programming Approach
Behzadi, B., & Fessant, F. L. (2005) · Lecture notes in computer science · doi:10.1007/11496656_17 · Cited by 93 · cited 2×
“At the cost of time complexity, DNAPack Behzadi and Fessant [4] employs a dynamic programming approach to find repeats.”
BackgroundMethodCompression of biological sequences by greedy off-line textual substitution
Apostolico, A., & Lonardi, S. (2002) · DCC · doi:10.1109/dcc.2000.838154 · Cited by 67 · cited 1×
“The Off-line approach by Apostolico and Lonardi [3] iteratively selects repeated substrings for which encoding would gain maximum compression.”
MethodDNA sequence compression using the normalized maximum likelihood model for discrete regression
Tabus, I., Korodi, G., & Rissanen, J. (2003) · DCC · doi:10.1109/dcc.2003.1194016 · Cited by 64 · cited 1×
“In the MNL algorithm by Tabus et al. [22] and its improvement, GeMNL by Korodi and Tabus [14], the DNA sequence is split into fixed size blocks.”
MethodCompression of strings with approximate repeats.
Allison, L., Edgoose, T. C., & Dix, T. I. (1998) · PubMed · Cited by 44
Self-citationDiscovering patterns in Plasmodium falciparum genomic DNA
Stern, L., Allison, L., Coppel, R. L., & Dix, T. I. (2001) · Molecular and Biochemical Parasitology · doi:10.1016/s0166-6851(01)00388-7 · Cited by 36 · cited 3×
“Work by Stern et al. [21] recognizes the importance of mutual compressibility for discovering patterns of interest from genomes.”
BackgroundMethodSelf-citationOn Compressibility of Protein Sequences
Adjeroh, D., & Nan, F. (2006) · DCC · doi:10.1109/dcc.2006.56 · Cited by 25 · cited 2×
“Note that an incorrect protein corpus that was more compressible was made available at some point resulting in a significantly lower compression ratios being reported in ProtComp [13] and BW [1].”
BackgroundMethod
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.