Symbolic Complexity for Nucleotide Sequences: A Sign of the Genome Structure

Abstract

We introduce a method to estimate the complexity function of symbolic dynamical systems from a finite sequence of symbols. We test such complexity estimator on several symbolic dynamical systems whose complexity functions are known exactly. We use this technique to estimate the complexity function for genomes of several organisms under the assumption that a genome is a sequence produced by a (unknown) dynamical system. We show that the genome of several organisms share the property that their complexity functions behaves exponentially for words of small length $\ell$ ($0\le \ell \le 10$) and linearly for word lengths in the range $11\le \ell \le 50$. It is also found that the species which are phylogenetically close each other have similar complexity functions calculated from a sample of their corresponding coding regions.

4 pages, 3 figures

References in corpus (5)

• Degeneracy: a design principle for achieving robustness and evolvability
• The long reach of DNA sequence heterogeneity in diffusive processes
• A Solvable Sequence Evolution Model and Genomic Correlations
• Evolution models with base substitutions, insertions, deletions and selection
• Exact scaling in the expansion-modification system

Cited by in corpus (3)

• Estimating entropy rate from censored symbolic time series: a test for time-irreversibility
• Noise-induced rectification in out-of-equilibrium structures
• Time-irreversibility tests for random-length time series: the matching-time approach applied to DNA