Physical complexity of symbolic sequences
From MaRDI portal
Publication:1969877
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.
Recommendations
Cites work
- A Theory of Program Size Formally Identical to Information Theory
- Combinatorial foundations of information theory and the calculus of probabilities
- Complexity
- scientific article; zbMATH DE number 3427210 (Why is no real title available?)
- scientific article; zbMATH DE number 176034 (Why is no real title available?)
- scientific article; zbMATH DE number 1096979 (Why is no real title available?)
- scientific article; zbMATH DE number 3062467 (Why is no real title available?)
- On Computable Numbers, with an Application to the Entscheidungsproblem
- On grammars, complexity, and information measures of biological macromolecules
- On the Complexity of Finite Sequences
- On the Length of Programs for Computing Finite Binary Sequences
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- Universal computation and physical dynamics
Cited in
(17)- The structural complexity of DNA templates -- implications on cellular complexity
- What is adaptation and how should it be measured?
- Evolutionary dynamics, epistatic interactions, and biological information
- The performances of the chi-square test and complexity measures for signal recognition in biological sequences
- Complexity analysis to explore the structure of ancient stromatolites
- Statistical complexity of the kicked top model considering chaos
- Selective pressures on genomes in molecular evolution
- Statistical complexity and generalized number system
- Statistical complexity of the quasiperiodical damped systems
- Predictability, complexity, and learning
- Complexity and asymptotic stability in the process of biochemical substance exchange in a coupled ring of cells
- Gaussian curvature of spherical shells: a geometric measure of complexity
- Was there an ice cube there or am I just remembering it?: Does the reversibility argument really imply scepticism about records?
- Statistical complexity of the time dependent damped L84 model
- Co-evolution and information signals in biological sequences
- Nonlinearity of the non-abelian lattice gauge field theory according to the spectrum of Kolmogorov-Sinai entropy and complexity
- Quantum information as a general paradigm
This page was built for publication: Physical complexity of symbolic sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1969877)
