A Generalized Topological Entropy for Analyzing the Complexity of DNA Sequences

Shuilin Jin, Renjie Tan, Qinghua Jiang, Xu Li, Jiajie Peng, Yong Wang, Yadong WangPLoS 2014 · DOI

Abstract

Topological entropy is one of the most difficult entropies to be used to analyze the DNA sequences, due to the finite sample and high-dimensionality problems. In order to overcome these problems, a generalized topological entropy is introduced. The relationship between the topological entropy and the generalized topological entropy is compared, which shows the topological entropy is a special case of the generalized entropy. As an application the generalized topological entropy in introns, exons and promoter regions was computed, respectively. The results indicate that the entropy of introns is higher than that of exons, and the entropy of the exons is higher than that of the promoter regions for each chromosome, which suggest that DNA sequence of the promoter regions is more regular than the exons and introns.

The Challenge of Measuring DNA Complexity

In information theory, entropy serves as a fundamental measure of randomness or complexity. While Shannon entropy—based on symbol probability—is widely known, topological entropy is often more appropriate for analyzing symbol dynamics like DNA because it counts the number of distinct "subwords" or patterns within a sequence.

However, traditional topological entropy faces a significant hurdle: it is mathematically defined for infinite sequences. DNA sequences are finite, leading to "high-dimensionality" problems. As the pattern length ($n$) increases, the entropy values often become unreliable or drop off sharply, making it difficult to extract a stable complexity metric from finite biological samples.

Figure 3: Topology Entropy vs. Subword Length. This plot illustrates how traditional topological entropy values for specific genes decline as subword length increases, highlighting the metric's sensitivity to pattern length.

Methods: Introducing Generalized Topological Entropy (GTE)

To address these limitations, researchers developed Generalized Topological Entropy (GTE). This framework moves away from relying on a single, often arbitrary, pattern length.

  1. The Formula: Instead of analyzing subwords of a fixed length $n$, GTE averages complexity across a range of subword lengths. This holistic approach makes the measure significantly more robust against the noise inherent in finite genomic data.
  2. Mathematical Unification: The authors demonstrated that standard topological entropy is a special case of this generalized version, providing a theoretical bridge between the two.
  3. Application: By utilizing a non-overlapping window algorithm, the researchers were able to scan DNA sequences and calculate GTE consistently, allowing for fair comparisons between sequences of varying lengths.

Mapping the Human Genome

The study applied GTE to the hg19 human genome assembly. Using the Galaxy platform, the researchers extracted three distinct functional regions for every chromosome (1–22, X, and Y):

  • Introns: Non-coding sections of genes.
  • Exons: Coding sections of genes.
  • Promoter Regions: The 2000 base pairs (bp) upstream of a gene's transcription start site.

To ensure statistical rigor, they randomly sampled 100 sequences of each type per chromosome, repeating the procedure 100 times to establish reliable average complexity values.

Results: A Universal Hierarchy of Randomness

The analysis revealed a consistent "complexity map" across the entire human genome. For every single chromosome, a clear hierarchy emerged: Introns > Exons > Promoters.

Figure 4: Generalized Topological Entropy across the Human Genome. The bar chart demonstrates the consistent hierarchy of entropy (Introns > Exons > Promoters) across all human chromosomes (1-22, X, and Y).

Key Insights

  • Complexity as a Proxy for Selection: The results suggest that mathematical complexity mirrors biological evolution. Introns, which are under less selective pressure, exhibit higher randomness. Conversely, promoters—the "instruction manuals" of the genome—must maintain specific motifs (like TATA boxes) to function, resulting in higher regularity and lower entropy.
  • Statistical Significance: Using ANOVA (Analysis of Variance), the differences between these three regions were confirmed to be statistically significant ($p < 0.005$).
  • Functional Detection: Because GTE distinguishes these regions so clearly, it holds potential as a tool for identifying unknown functional regions in poorly annotated genomes.

Discussion and Future Directions

While GTE proves to be a powerful metric, future work will need to address computational scaling as genomic datasets reach the terabyte scale. Additionally, exploring the "optimal" range of subword lengths ($k$) for different organisms could further refine the tool's accuracy. Beyond basic mapping, GTE could eventually be used to study genetic diseases where sequence regularity might be disrupted, or to detect regions under intense selective constraint in non-human species.

Summary updated

Abstract

Topological entropy is one of the most difficult entropies to be used to analyze the DNA sequences, due to the finite sample and high-dimensionality problems. In order to overcome these problems, a generalized topological entropy is introduced. The relationship between the topological entropy and the generalized topological entropy is compared, which shows the topological entropy is a special case of the generalized entropy. As an application the generalized topological entropy in introns, exons and promoter regions was computed, respectively. The results indicate that the entropy of introns is higher than that of exons, and the entropy of the exons is higher than that of the promoter regions for each chromosome, which suggest that DNA sequence of the promoter regions is more regular than the exons and introns.
BibTeX
@inproceedings{jin2014generalized,
  author = {Shuilin Jin and Renjie Tan and Qinghua Jiang and Xu Li and Jiajie Peng and Yong Wang and Yadong Wang},
  title = {{A Generalized Topological Entropy for Analyzing the Complexity of DNA Sequences}},
  booktitle = {PLoS},
  year = {2014},
  doi = {10.1371/journal.pone.0088519},
}
Figure