Entropy Analysis in DNA Sequences

Abstract

In the first part of this paper, we perform the entropy analysis for codons(or amino acids) of yeast and human. From the analysis, we can see that there exists a language structure in codons(or amino acids) of yeast and human chromosome 22. Surprisingly, human chromosome 22 seems to have different linguistic structure from yeast, which can be seen in the triangle with different vertices from those of yeast. It implies that there may be a proper linguistic structure to each DNA. Also the linguistic structure of NCDS of human chromosome 22 seems not to have a relationship with secondary structure of protein. In the second part, we give an answer for the uestion, "What is a complex graph?" Many papers published in recent years show that real-world graphs G(n,m) (n nodes, m edges) are more or less "complex" in the sense that different topological features deviate from random graphs. Here we narrowthe definition of graph complexity and argue that a complex graph contains many different subgraphs. We present different measures that quantify this complexity. However, because these different subgraph measures are computationally demanding, we also study simpler complexity measures focussing on slightly different aspects of graph complexity. We consider heuristically defined "product measures", the products of two quantities which are zero in the extreme cases of a path and clique, and "entropy measures" quantifying the diversity of different topological features. The previously defined graph complexity measure Offdiagonal complexity (OdC) belongs to the latter class. We study OdC measures in some detail and compare it with our new measures. For all measures, the most complex graph G_(C_(max)) has a medium number of edges, between the edge numbers of the minimum and the maximum connected graph max n-1 ＜ m(G_(c_(max))) ＜ n(n-1) / 2. Interestingly, for some measures C~ this number scales exactly with the geometric mean of the extremes: m(G_(c～))=√n/2(n-1)~n^(1.5). All graph complexity measures are characterized with the help of different example graphs. For all measures the corresponding time complexity is given. Finally, a method for finding modular structure is presented in the last part of the paper.