Physical Complexity of Symbolic Sequences

Abstract

A practical measure for the complexity of sequences of symbols (``strings'') is introduced that is rooted in automata theory but avoids the problems of Kolmogorov-Chaitin complexity. This physical complexity can be estimated for ensembles of sequences, for which it reverts to the difference between the maximal entropy of the ensemble and the actual entropy given the specific environment within which the sequence is to be interpreted. Thus, the physical complexity measures the amount of information about the environment that is coded in the sequence, and is conditional on such an environment. In practice, an estimate of the complexity of a string can be obtained by counting the number of loci per string that are fixed in the ensemble, while the volatile positions represent, again with respect to the environment, randomness. We apply this measure to tRNA sequence data.

12 pages LaTeX2e, 3 postscript figures, uses elsart.cls. Substantially improved and clarified version, includes application to EMBL tRNA sequence data

Cited by in corpus (17)

• Evolution of Biological Complexity
• Information theory in molecular biology
• Features of the Extension of a Statistical Measure of Complexity to Continuous Systems
• Evolution of complex modular biological networks
• Integrated information increases with fitness in the evolution of animats
• What is Information?
• Selective pressures on genomes in molecular evolution
• Strong Selection Significantly Increases Epistatic Interactions in the Long-Term Evolution of a Protein
• Information-theoretic considerations concerning the origin of life
• Information content of colored motifs in complex networks
• Natural selection. V. How to read the fundamental equations of evolutionary change in terms of information theory
• Dynamics of order-disorder and complexity for interacting bosons in optical lattice
• Emergence of functional information from multivariate correlations
• Complexity and asymptotic stability in the process of biochemical substance exchange in a coupled ring of cells
• Physical Complexity of Variable Length Symbolic Sequences
• Gaussian curvature of spherical shells: A geometric measure of complexity
• Rebuilding the Habitable Zone from the Bottom Up with Computational Zones