Reference normalizations of Effort-To-Compress across length, alphabet size, and composition
Preprint
Abstract
Comparing finite symbolic complexity requires an explicit reference. Effort-To-Compress (ETC) counts the recursive pair substitutions needed to reduce a symbolic sequence to a constant. Its conventional normalization with L − 1 leaves systematic dependence on sequence length L and alphabet size k , confounding comparisons across datasets. We derive certified lower bounds for ETC and show that, for L ≥ k ≥ 2, the ceiling L − 1 is attainable if and only if L ≤ k 2 + k + 1. For fixed k ≥ 2, the global ensemble mean and maximum ETC grow as Θ k ( L/ log k L ) as L → ∞. These support two normalized ETC coordinates. Global-ensemble normalized ETC (nETC) maps a certified lower bound to zero and the uniform ensemble mean at the same L and k to one. Composition-conditioned normalized ETC (cETC) uses corresponding references restricted to the observed symbol composition. In Potts chains, nETC substantially reduced dependence on length and alphabet size. cETC further reduced differences associated with unequal symbol frequencies, while retaining sensitivity to temporal dependence. In human chromosome 22, the exploratory predictor nETC – cETC outperformed LZ76 in distinguishing CpG islands and long interspersed nuclear elements from genomic background with AUROC of 0.947 and 0.848. Matched references therefore enable interpretable comparisons of symbolic complexity across sequence lengths, alphabet sizes, and compositions.Keywords
Funding Information
- National Institute of General Medical Sciences (R01GM103894)
- Center for Consciousness Science, Department of Anesthesiology, University of Michigan Medical School
This publication has 27 references indexed in Scilit:
- Measuring the dynamic balance of integration and segregation underlying consciousness, anesthesia, and sleep in humansNature Communications, 2024
- The complexity of the stream of consciousnessCommunications Biology, 2022
- A joint NCBI and EMBL-EBI transcript set for clinical genomics and researchNature, 2022
- Study of LZ-word distribution and its application for sequence comparisonJournal of Theoretical Biology, 2013
- Using RepeatMasker to Identify Repetitive Elements in Genomic SequencesCurrent Protocols in Bioinformatics, 2009
- Predictability: a way to characterize complexityPhysics Reports, 2002
- Surrogate time seriesPhysica D: Nonlinear Phenomena, 2000
- Exact results for the zeros of the partition function of the Potts model on finite latticesPhysica A: Statistical Mechanics and its Applications, 2000
- CpG Islands in vertebrate genomesJournal of Molecular Biology, 1987
- On grammars, complexity, and information measures of biological macromoleculesMathematical Biosciences, 1980