APS/xxx
Complexities of Human Promoter Sequences
Fangcui Zhao1,∗ Huijie Yang2,3,† and Binghong Wang4
College of Life Science and Bioengineering, Beijing University of Technology, Beijing 100022, China
Department of Physics, National University of Singapore, Science Drive 2, Singapore 117543
School of Management, University of Shanghai for Science and Technology,
and Shanghai Institute for Systematic Science, Shanghai 200093, China
Department of Modern Physics, University of Science and Technology of China, Anhui Hefei 230026, China
(Dated: October 26, 2018)
By means of the diffusion entropy approach, we detect the scale-invariance characteristics embed-
ded in the 4737 human promoter sequences. The exponent for the scale-invariance is in a wide range
of [0.3, 0.9], which centered at δc = 0.66. The distribution of the exponent can be separated into
left and right branches with respect to the maximum. The left and right branches are asymmetric
and can be fitted exactly with Gaussian form with different widths, respectively.
PACS numbers: 82.39.Pj, 05.45.Tp
I. INTRODUCTION
Understanding gene regulation is one of the most excit-
ing topics in molecular genetics [1]. Promoter sequences
are crucial in gene regulation. The analysis of these re-
gions is the first step towards complex models of regula-
tory networks.
A promoter is a combination of different regions with
different functions [2, 3, 4, 5]. Surrounding the tran-
scription start site is the minimal sequence for initiat-
ing transcription, called core promoter. It interacts with
RNA polymerase II and basal transcription factors. Few
hundred base pairs upstream of the core promoter are
the gene-specific regulatory elements, which are recog-
nized by transcription factors to determine the efficiency
and specificity of promoter activity. Far distant from
the transcription start site there are enhancers and dis-
tal promoter elements which can considerably affect the
rate of transcription. Multiple binding sites contribute
to the functioning of a promoter, with their position and
context of occurrence playing an important role. Large-
scale studies show that repeats participate in the regula-
tion of numerous human and mouse genes [6]. Hence, the
promoter’s biological function is a cooperative process of
different regions such as the core promoter, the gene-
specific regulatory elements, the enhancers/silencers, the
insulators, the CpG islands and so forth. But how they
cooperate with each other is still a problem to be inves-
tigated carefully.
The structures of DNA sequences determine their bio-
logical functions [7]. Recent years witness an avalanche
of finding nontrivial structure characteristics embedded
in DNA sequences. Detailed works show that the non-
coding sequences carry long-range correlations [8, 9, 10].
The size distributions of coding sequences and non-
coding sequences obey Gaussian or exponential and
∗Electronic address: yangzhaon@eyou.com
†Electronic address: huijieyangn@eyou.com; Corresponding author
power-law [11, 12], respectively. Theoretical model-based
simulations [13, 14, 15, 16] tell us that the parts of the
promoters where the RNA transcription has started are
more active than a random portion of the DNA. By
means of the nonlinear modeling method it is found that
along the putative promoter regions of human sequences
there are some segments much more predictable com-
pared with other segments [17]. All the evidences suggest
that the nontrivial structure characteristics of a promoter
determine its biological functions. The statistical prop-
erties of a promoter may shed light on the cooperative
process of different regions.
Experimental knowledge of the precise 5’ ends of cD-
NAs should facilitate the identification and characteri-
zation of regulatory sequence elements in proximal pro-
moters [18]. Using the oligocapping method, Suzuki et
al. identify the transcriptional start sites from cDNA
libraries enriched in full-length cDNA sequences. The
identified transcriptional start sites are available at the
Database, http://dbtss.hgc.jp/. [19]. Consequently,
Leonardo et al. have used this data set and aligned
the full-length cDNAs to the human genome, thereby
extracting putative promoter regions (PPRs) [20]. Us-
ing the known transcriptional start sites from over 5700
different human full-length cDNAs, a set of 4737 distinct
PPRs are extracted from the human genome. Each PPR
consists nucleotides from −2000 to +1000bp, relative to
the corresponding transcriptional start site. They have
also counted eight-letter words within the PPRs, using
z-scores and other related statistics to evaluate the over-
and under- representations.
In this paper, by means of the concept of diffusion
entropy (DE) we try to detect the scale-invariant char-
acteristics in these putative promoter regions.
II. DIFFUSION ENTROPY ANALYSIS
The diffusion entropy (DE) method is firstly designed
to capture the scale-invariance embedded in time series
[21, 22, 23]. To keep the description as self-contained as
http://arxiv.org/abs/0704.0158v1
mailto:yangzhaon@eyou.com
mailto:huijieyangn@eyou.com
http://dbtss.hgc.jp/
possible, we review briefly the procedures.
We consider a PPR denoted with Y =
(y1, y2, · · · , y3001), where ys is the element at the
position s and ys = A, T,C or G. Replacing A, T and
C,G with −1 and +1, respectively, the original PPR is
mapped to a time series X = (x1, x2, · · · , x3001). There
is not a trend in this series, i.e., X is stationary.
Connecting the starting and the end of X , we can ob-
tain a set of delay-register vectors, which reads,
T1(t) = (x1, x2, · · · , xt)
T2(t) = (x2, x3, · · · , xt+1)
T3001(t) = (x3001, x1, · · · , xt−1)
Regarding each vector as a trajectory of a particle in
duration of t time units, all the vectors can be described
as a diffusion process of a system containing 3001 parti-
cles. The initial state of the system is
T1(0)
T2(0)
T3001(0)
Accordingly, at each time step t we can calculate dis-
placements of all the particles. The probability distribu-
tion function (PDF) of the displacements can be approx-
imated with p(m, t) ∼ Km/3001, where m = −t,−t +
1, · · · , t and Km is the number of the particles whose
displacements are m. It can represent the state of the
system at time t.
As a tenet of complexity theory [24, 25], complexity is
related with the concept of scaling invariance. For the
constructed diffusion process, the scaling invariance is
defined as,
p(m, t) ≈
, (2)
where δ is the scaling exponent and can be regarded as a
quantitative description of the PPR’s complexity. If the
elements in the PPR are positioned randomly, the result-
ing PDF obeys a Gaussian form and δ = 0.5. Complexity
of the PPR is expected to generate a departure from this
ordinary condition, that is, δ 6= 0.5.
The value of δ can tell us the pattern characteristics of
a PPR. The departure from the ordinary condition can
be described with a preferential effect. Let the element
is A, T (or C,G), the preferential probability for the fol-
lowing element’s being A, T (or C,G) is Wpre. A positive
preferential effect, i.e, Wpre > 0.5, leads to the value of δ
larger than 0.5. While a negative preferential effect, i.e,
Wpre < 0.5, can induce the value of δ smaller than 0.5.
101 102 103
PPR-1
 Calculate
=0.662
101 102 103
PPR-1000
 Calculate
=0.760
101 102 103
PPR-2000
 Calculate
=0.703
101 102 103
PPR-3000
 Calculate
=0.500
FIG. 1: (Color online) Typical DE results. The results for
the PPRs numbered 1, 1000, 2000 and 3000 are presented. In
considerable wide regions of t , the curves of DE can be fitted
almost exactly with the linear relation in Eq.(4).
Hence, a large value of δ implies that A, T or C,G accu-
mulate strongly in a scale-invariance way, respectively.
However, correct evaluation of the scaling exponent is a
nontrivial problem. In literature, variance-based method
is used to detect the scale-invariance. But the obtained
Hurst exponent Hmay be different from the real δ, that
is, generally we haveH 6= δ. And for some conditions,
the variance is divergent, which leads the invalidation of
the variance-method at all. To overcome these shortages,
the Shannon entropy for the diffusion can be used, which
reads,
S(t) = −
p(m, t) ln p(m, t)
This diffusion-based entropy is called diffusion entropy
(DE). A simple computation leads the relation between
the scaling invariance defined in Eq.2 and the DE as,
S(t) = A+ δ ln t, (4)
where A is a constant depends on the PDF. Detailed
works show that DE is a reliable method to search the
correct value of δ, regardless the form of the PDF [26,
27, 28, 29].
The complexity in the PDF can be catalogued into
two levels [30], the primary one due to the extension of
the probability to all the possible displacements m, and
the secondary one due to the internal structures. Conse-
quently, we should consider also the corresponding shuf-
fling sequences as comparison.
0 200 400 600 800 1000 1200 1400 1600
FIG. 2: Distribution of the maximum interval ∆t in which one
can find scale-invariant characteristics. Keeping the standard
deviation of the fitting result in the range of ≤ 0.05 , we
can find the maximum intervals ∆t for all the PPRs. The
distribution tells us that generally the scale-invariance can be
found over two to three decades of the scale t .
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
600  Calculate
 Gauss fit
 Gauss fit
left=0.67
   wleft=0.17
right=0.65
   wright=0.10
FIG. 3: (Color online) The complex index δ distributes in
a wide range of [0.3, 0.9]. The distribution can be sepa-
rated into two branches with respect to the center δc = 0.66.
The two branches are asymmetric and obey exactly the Gau-
usian function, respectively. The widths and centers of
the left and right branches are (wleft, xleftc ) = (0.17, 0.67),
(wright, xrightc ) = (0.10, 0.65). The centers coincide with each
other, wleft ≈ wright ≈ δc = 0.66. The right branch dis-
tributes in a significant narrow region.
III. RESULTS AND DISCUSSIONS
The DEs for all the 4737 PPRs are calculated. As a
typical example, Fig.1 presents the DE results for the
PPRs numbered 1, 1000, 2000 and 3000. In considerable
wide regions of t, the curves of DE can be fitted almost
exactly with the linear relation in Eq.4.
For each PPR, there exists an interval, t0 ∼ t0+∆t, in
which the PDF behaves scale-invariance. Keeping simul-
taneously the standard deviation and the error of the
scaling exponent for the fitting result in the range of
≤ 0.05 and ≤ 0.03, we can find the maximum intervals
∆t for all the PPRs. In the fitting procedure, the confi-
dence level is set to be 95%. The distribution of ∆t, as
shown in Fig.2, tells us that generally the scale-invariance
can be found over two to three decades of the scale t.
The concept of DE is based upon statistical theory, that
is, t0 should be large enough so that the statistical as-
sumptions are valid. To cite an example, we consider a
random series, whose elements obey a homogenous dis-
tribution in [0, 1]. Only the length of the delay-register
vectors, t, in Eq.(1) is large enough, the corresponding
PDF for the displacements, i.e, the summation value of
each delay-register vector, approaches the Gaussian dis-
tribution. Consequently, t0 is not a valuable parameter.
The values of t0 for different PPRs are not presented.
The resulting scaling exponent δ ± 0.03 distributes
in a wide range of [0.3, 0.9]. The distribution can
be separated into two branches with respect to the
center δc = 0.66. The two branches are asymmet-
ric and can be fitted exactly with the Gauusian func-
tion, respectively. The widths and centers of the left
and right branches are (wleft, xleftc ) = (0.17, 0.67),
(wright, xrightc ) = (0.10, 0.65). That is to say, the centers
coincide with each other, wleft ≈ wright ≈ δc = 0.66.
Comparatively, the right branch distributes in a signifi-
cant narrow region.
The PPRs are shuffled also. For each PPR, the shuf-
fling result is obtained by averaging over ten shuffling
samples. The scaling exponents are almost same, i.e.,
δshuffling = 0.5±0.03. The detected scale-invariant char-
acteristics are internal-structure-related.
How to understand the asymmetric characteristic of
the distribution of the complexity index δ is an in-
teresting problem. In literature, some statistical char-
acteristics of DNA sequences are captured with evo-
lution models, such as the long-range correlations and
the over- and under-representation of strings and so on
[31, 32, 33]. From the perspective of evolution, per-
haps the distribution characteristics may favor a stochas-
tic evolution model. The initial sequences have same
complexity δinitial = δc = 0.66. With the evolution
processes the sequences diffuse along two directions, in-
creasing complexity and decreasing complexity, i.e, the
index δ increases and decreases, respectively. The diffu-
sion coefficients for the two directions are significantly
different, denoted with Dleft 6= Dright. Based upon
the widths of the two branches we can estimate that,
Dleft
Dright =
δleft
δright = 1.7. It should be noted
that, the complexity is regarded as the departure from
the ordinary condition, δ = 0.5. In the totally 4737 values
of δ, only a small portion of them are less than 0.5. Ac-
cordingly, the PPRs may be catalogued into two classes,
the PPRs with high complexity and the PPRs with low
complexity. The former class evolves averagely with a
slow speed while the later one with a high speed.
In summary, by means of the DE method, we calculate
the complexities of the 4737 PPRs. The distribution of
the complexity index includes two asymmetric branches,
which obey Gaussian form with different widths, respec-
tively. A stochastic evolution model may provide us a
comprehensive understand of these characteristics.
IV. ACKNOWLEDGEMENTS
This work is funded by the National Natural Sci-
ence Foundation of China under Grant Nos. 70571074,
10635040 and 70471033, by the National Basic Re-
search Program of China (973 Program) under grant
No.2006CB705500), by the President Funding of Chinese
Academy of Science, and by the Specialized Research
Fund for the Doctoral Program of Higher Education of
China. One of the authors (H. Yang) would like to thank
Prof. Y. Zhuo for stimulating discussions.
[1] Ohler,U. and Niemann,H. (2001) Identification and anal-
ysis of eukaryotic promoters: recent computational ap-
proaches. Trends Genet., 17, 56-60.
[2] Werner,T. (1999) Models for prediction and recognition
of eukaryotic promoters. Mammalian Genome, 10, 168-
[3] Pedersen,A.G., Baldi,P., Chauvin,Y., Brunak,S. (1999)
The biology of eukaryotic promoter prediction - a review.
Comput. Chem., 23, 191-207.
[4] Zhang,M.Q. (2002) Computational methods for promoter
recognition. In: Jiang T, Xu Y, Zhang,M.Q., editors.
Current topics in computational molecular biology. Cam-
bridge, Massachusetts: MIT Press; p. 249-268.
[5] Narang,V., Sung,W.-K., Mittal A. (2005) Computational
modeling of oligonucleotides positional densities for hu-
man promoter prediction. Art. Intel. Med., 35, 107-119.
[6] Rosenberg, N. and Jolicoeur, P. (1997) Retroviral patho-
genesis. In Retroviruses (Coffin, J.M. et al., eds), pp.
475–586, Cold Spring Harbor Press.
[7] Buldyrev,S.V., Goldberger,A.L., Havlin,S., Man-
tegna,R.N., Matsa,M.E., Peng,C.-K., Simons, M. and
Stanley,H.E. (1995) Long-range correlation properties
of coding and noncoding DNA sequences: GenBank
analysis. Phys. Rev. E 51, 5084-5091.
[8] Peng,C.K., Buldyrev,S., Goldberger,A., Havlin, S.,
Sciortino,F., Simons,M. and Stanley,H.E.(1992) Long-
range correlations in nucleotide sequences. Nature 356,
168-171.
[9] Li,W., Kaneko,K. (1992) Long-range correlations and
partial 1/f −α spectrum in a noncoding DNA sequence.
Europhys. Lett. 17, 655.
[10] Yang,H., Zhao,F., Zhuo,Y., et al. (2002) Analysis of DNA
chains by means of factorial moments. Phys. Lett. A
292,349-356.
[11] Provata, A., Almirantis,Y. (1997) Scaling properties of
coding and non-coding DNA sequences. Physica A 247,
[12] Provata,A., Almirantis,Y. (2000) Fractal cantor patterns
in the sequence structure of DNA, Fractals 8 ,15-27.
[13] Yang,H., Zhuo,Y., Wu,X. (1994) Investigation of ther-
mal denaturation of DNA molecules based upon non-
equilibrium transport approach. J. Phys. A 27, 6147-
6156.
[14] Salerno,M. (1991) Discrete model for DNA-promoter dy-
namics. Phys. Rev. A 44, 5292-5297.
[15] Lennholm,E., Homquist,M. (2003) Revisiting Salerno’s
sine-Gordon model of DNA: active regions and robust-
ness. Physica D 177, 233-241.
[16] Kalosakas,G., Rasmussen,K.O. and Bishop,A.R. (2004)
Sequence-specific thermal fluctuations identify start sites
for DNA transcription. Europhys. Lett. 68, 127-133.
[17] Yang,H., Zhao,F., Gu,J. and Wang,B. (2006) Nonlin-
ear modeling approach to human promoter sequences. J.
Theo. Bio. 241, 765-773.
[18] Trinklein, N.D., Aldred, S.J., Saldanha, A.J., My-
ers, R.M., 2003. Identification and functional analysis
of human transcriptional promoters. Genome Res. 13,
308C312.
[19] Suzuki,Y., Yamashita,R., Nakai,K. and Sugano,S. (2002)
DBTSS:DataBase of human transcriptional start sites
and full-length cDNAs. Nucleic Acids Res., 30, 328-331.
[20] Leonardo,M.–R., John,L.S., Gavin,C.K. and
David,L. (2004) Statistical analysis of over-
represented words in human promoter sequences.
Nucleic Acids Res., 32, 949-958. See also,
ftp://ftp.ncbi.nlm.nih.gov/pub/marino/published/
hs promoters/fasta/.
[21] Grigolini,P., Palatella,L. and Raffaelli,G. (2001) Complex
Geometry, Patterns, and Scaling in Nature and Society.
Fractals 9, 439-449.
[22] Scafetta,N., Hamilton,P. and Grigolini,P. (2001) The
thermodynamics of social processes: the teen birth phe-
nomenon. Fractals 9, 193-208.
[23] Scafetta,N. and Grigolini,P. (2002) Scaling detection in
time series: Diffusion entropy analysis. Phys. Rev. E 66,
036130.
[24] Bar-Yam, Y. (1997) Dynamics of Complex Systems.
Addison-Wesley, Reading, MA.
[25] Mandelbrot,B. B. (1988) Fractal Geometry of Nature.
W.H. Freeman, San Francisco, CA.
[26] Scafetta,N. and West, B. J. (2003) Solar flare intermit-
tency and the earth’s temperature anomalies. Phys. Rev.
Lett. 90, 248701.
[27] Scafetta,N., Latora,V. and Grigolini,P. (2002) Levy scal-
ing: The diffusion entropy analysis applied to DNA se-
quences. Phys. Rev. E 66, 031906.
[28] Yang,H., Zhao,F., Zhang,W. and Li,Z. (2005) Diffusion
entropy approach to complexity for a Hodgkin–Huxley
neuron. Physica A 347, 704-710.
[29] Yang,H., Zhao,F., Qi,L. and Hu,B. (2004) Temporal se-
ries analysis approach to spectra of complex networks.
Phys. Rev. E 69, 066104.
[30] Pipek,J. and Varga,I. (1992) Universal classification
scheme for the spatial-localization properties of one-
ftp://ftp.ncbi.nlm.nih.gov/pub/marino/published/
particle states in finite, d-dimensional systems. Phys.
Rev. A 46,3148-3163.
[31] Hsieh,L.-C., Luo,L., Ji F. and Lee,H.C. (2003) Minimal
model for genome evolution and growth. Phys. Rev. Lett.
90, 018101.
[32] Kloster,M. (2005) Analysis of evolution through compet-
itive selection. Phys. Rev. Lett. 95, 168701.
[33] Messer,P.W., Arndt,P.F. and Lassig,M. (2005) Solvable
sequence evolution models and genomic correlations.
Phys. Rev. Lett. 94, 138103.

  By means of the diffusion entropy approach, we detect the scale-invariance
characteristics embedded in the 4737 human promoter sequences. The exponent for
the scale-invariance is in a wide range of $[ {0.3,0.9} ]$, which centered at
$\delta_c = 0.66$. The distribution of the exponent can be separated into left
and right branches with respect to the maximum. The left and right branches are
asymmetric and can be fitted exactly with Gaussian form with different widths,
respectively.

APS/xxx
Complexities of Human Promoter Sequences
Fangcui Zhao1,∗ Huijie Yang2,3,† and Binghong Wang4
College of Life Science and Bioengineering, Beijing University of Technology, Beijing 100022, China
Department of Physics, National University of Singapore, Science Drive 2, Singapore 117543
School of Management, University of Shanghai for Science and Technology,
and Shanghai Institute for Systematic Science, Shanghai 200093, China
Department of Modern Physics, University of Science and Technology of China, Anhui Hefei 230026, China
(Dated: October 26, 2018)
By means of the diffusion entropy approach, we detect the scale-invariance characteristics embed-
ded in the 4737 human promoter sequences. The exponent for the scale-invariance is in a wide range
of [0.3, 0.9], which centered at δc = 0.66. The distribution of the exponent can be separated into
left and right branches with respect to the maximum. The left and right branches are asymmetric
and can be fitted exactly with Gaussian form with different widths, respectively.
PACS numbers: 82.39.Pj, 05.45.Tp
I. INTRODUCTION
Understanding gene regulation is one of the most excit-
ing topics in molecular genetics [1]. Promoter sequences
are crucial in gene regulation. The analysis of these re-
gions is the first step towards complex models of regula-
tory networks.
A promoter is a combination of different regions with
different functions [2, 3, 4, 5]. Surrounding the tran-
scription start site is the minimal sequence for initiat-
ing transcription, called core promoter. It interacts with
RNA polymerase II and basal transcription factors. Few
hundred base pairs upstream of the core promoter are
the gene-specific regulatory elements, which are recog-
nized by transcription factors to determine the efficiency
and specificity of promoter activity. Far distant from
the transcription start site there are enhancers and dis-
tal promoter elements which can considerably affect the
rate of transcription. Multiple binding sites contribute
to the functioning of a promoter, with their position and
context of occurrence playing an important role. Large-
scale studies show that repeats participate in the regula-
tion of numerous human and mouse genes [6]. Hence, the
promoter’s biological function is a cooperative process of
different regions such as the core promoter, the gene-
specific regulatory elements, the enhancers/silencers, the
insulators, the CpG islands and so forth. But how they
cooperate with each other is still a problem to be inves-
tigated carefully.
The structures of DNA sequences determine their bio-
logical functions [7]. Recent years witness an avalanche
of finding nontrivial structure characteristics embedded
in DNA sequences. Detailed works show that the non-
coding sequences carry long-range correlations [8, 9, 10].
The size distributions of coding sequences and non-
coding sequences obey Gaussian or exponential and
∗Electronic address: yangzhaon@eyou.com
†Electronic address: huijieyangn@eyou.com; Corresponding author
power-law [11, 12], respectively. Theoretical model-based
simulations [13, 14, 15, 16] tell us that the parts of the
promoters where the RNA transcription has started are
more active than a random portion of the DNA. By
means of the nonlinear modeling method it is found that
along the putative promoter regions of human sequences
there are some segments much more predictable com-
pared with other segments [17]. All the evidences suggest
that the nontrivial structure characteristics of a promoter
determine its biological functions. The statistical prop-
erties of a promoter may shed light on the cooperative
process of different regions.
Experimental knowledge of the precise 5’ ends of cD-
NAs should facilitate the identification and characteri-
zation of regulatory sequence elements in proximal pro-
moters [18]. Using the oligocapping method, Suzuki et
al. identify the transcriptional start sites from cDNA
libraries enriched in full-length cDNA sequences. The
identified transcriptional start sites are available at the
Database, http://dbtss.hgc.jp/. [19]. Consequently,
Leonardo et al. have used this data set and aligned
the full-length cDNAs to the human genome, thereby
extracting putative promoter regions (PPRs) [20]. Us-
ing the known transcriptional start sites from over 5700
different human full-length cDNAs, a set of 4737 distinct
PPRs are extracted from the human genome. Each PPR
consists nucleotides from −2000 to +1000bp, relative to
the corresponding transcriptional start site. They have
also counted eight-letter words within the PPRs, using
z-scores and other related statistics to evaluate the over-
and under- representations.
In this paper, by means of the concept of diffusion
entropy (DE) we try to detect the scale-invariant char-
acteristics in these putative promoter regions.
II. DIFFUSION ENTROPY ANALYSIS
The diffusion entropy (DE) method is firstly designed
to capture the scale-invariance embedded in time series
[21, 22, 23]. To keep the description as self-contained as
http://arxiv.org/abs/0704.0158v1
mailto:yangzhaon@eyou.com
mailto:huijieyangn@eyou.com
http://dbtss.hgc.jp/
possible, we review briefly the procedures.
We consider a PPR denoted with Y =
(y1, y2, · · · , y3001), where ys is the element at the
position s and ys = A, T,C or G. Replacing A, T and
C,G with −1 and +1, respectively, the original PPR is
mapped to a time series X = (x1, x2, · · · , x3001). There
is not a trend in this series, i.e., X is stationary.
Connecting the starting and the end of X , we can ob-
tain a set of delay-register vectors, which reads,
T1(t) = (x1, x2, · · · , xt)
T2(t) = (x2, x3, · · · , xt+1)
T3001(t) = (x3001, x1, · · · , xt−1)
Regarding each vector as a trajectory of a particle in
duration of t time units, all the vectors can be described
as a diffusion process of a system containing 3001 parti-
cles. The initial state of the system is
T1(0)
T2(0)
T3001(0)
Accordingly, at each time step t we can calculate dis-
placements of all the particles. The probability distribu-
tion function (PDF) of the displacements can be approx-
imated with p(m, t) ∼ Km/3001, where m = −t,−t +
1, · · · , t and Km is the number of the particles whose
displacements are m. It can represent the state of the
system at time t.
As a tenet of complexity theory [24, 25], complexity is
related with the concept of scaling invariance. For the
constructed diffusion process, the scaling invariance is
defined as,
p(m, t) ≈
, (2)
where δ is the scaling exponent and can be regarded as a
quantitative description of the PPR’s complexity. If the
elements in the PPR are positioned randomly, the result-
ing PDF obeys a Gaussian form and δ = 0.5. Complexity
of the PPR is expected to generate a departure from this
ordinary condition, that is, δ 6= 0.5.
The value of δ can tell us the pattern characteristics of
a PPR. The departure from the ordinary condition can
be described with a preferential effect. Let the element
is A, T (or C,G), the preferential probability for the fol-
lowing element’s being A, T (or C,G) is Wpre. A positive
preferential effect, i.e, Wpre > 0.5, leads to the value of δ
larger than 0.5. While a negative preferential effect, i.e,
Wpre < 0.5, can induce the value of δ smaller than 0.5.
101 102 103
PPR-1
 Calculate
=0.662
101 102 103
PPR-1000
 Calculate
=0.760
101 102 103
PPR-2000
 Calculate
=0.703
101 102 103
PPR-3000
 Calculate
=0.500
FIG. 1: (Color online) Typical DE results. The results for
the PPRs numbered 1, 1000, 2000 and 3000 are presented. In
considerable wide regions of t , the curves of DE can be fitted
almost exactly with the linear relation in Eq.(4).
Hence, a large value of δ implies that A, T or C,G accu-
mulate strongly in a scale-invariance way, respectively.
However, correct evaluation of the scaling exponent is a
nontrivial problem. In literature, variance-based method
is used to detect the scale-invariance. But the obtained
Hurst exponent Hmay be different from the real δ, that
is, generally we haveH 6= δ. And for some conditions,
the variance is divergent, which leads the invalidation of
the variance-method at all. To overcome these shortages,
the Shannon entropy for the diffusion can be used, which
reads,
S(t) = −
p(m, t) ln p(m, t)
This diffusion-based entropy is called diffusion entropy
(DE). A simple computation leads the relation between
the scaling invariance defined in Eq.2 and the DE as,
S(t) = A+ δ ln t, (4)
where A is a constant depends on the PDF. Detailed
works show that DE is a reliable method to search the
correct value of δ, regardless the form of the PDF [26,
27, 28, 29].
The complexity in the PDF can be catalogued into
two levels [30], the primary one due to the extension of
the probability to all the possible displacements m, and
the secondary one due to the internal structures. Conse-
quently, we should consider also the corresponding shuf-
fling sequences as comparison.
0 200 400 600 800 1000 1200 1400 1600
FIG. 2: Distribution of the maximum interval ∆t in which one
can find scale-invariant characteristics. Keeping the standard
deviation of the fitting result in the range of ≤ 0.05 , we
can find the maximum intervals ∆t for all the PPRs. The
distribution tells us that generally the scale-invariance can be
found over two to three decades of the scale t .
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
600  Calculate
 Gauss fit
 Gauss fit
left=0.67
   wleft=0.17
right=0.65
   wright=0.10
FIG. 3: (Color online) The complex index δ distributes in
a wide range of [0.3, 0.9]. The distribution can be sepa-
rated into two branches with respect to the center δc = 0.66.
The two branches are asymmetric and obey exactly the Gau-
usian function, respectively. The widths and centers of
the left and right branches are (wleft, xleftc ) = (0.17, 0.67),
(wright, xrightc ) = (0.10, 0.65). The centers coincide with each
other, wleft ≈ wright ≈ δc = 0.66. The right branch dis-
tributes in a significant narrow region.
III. RESULTS AND DISCUSSIONS
The DEs for all the 4737 PPRs are calculated. As a
typical example, Fig.1 presents the DE results for the
PPRs numbered 1, 1000, 2000 and 3000. In considerable
wide regions of t, the curves of DE can be fitted almost
exactly with the linear relation in Eq.4.
For each PPR, there exists an interval, t0 ∼ t0+∆t, in
which the PDF behaves scale-invariance. Keeping simul-
taneously the standard deviation and the error of the
scaling exponent for the fitting result in the range of
≤ 0.05 and ≤ 0.03, we can find the maximum intervals
∆t for all the PPRs. In the fitting procedure, the confi-
dence level is set to be 95%. The distribution of ∆t, as
shown in Fig.2, tells us that generally the scale-invariance
can be found over two to three decades of the scale t.
The concept of DE is based upon statistical theory, that
is, t0 should be large enough so that the statistical as-
sumptions are valid. To cite an example, we consider a
random series, whose elements obey a homogenous dis-
tribution in [0, 1]. Only the length of the delay-register
vectors, t, in Eq.(1) is large enough, the corresponding
PDF for the displacements, i.e, the summation value of
each delay-register vector, approaches the Gaussian dis-
tribution. Consequently, t0 is not a valuable parameter.
The values of t0 for different PPRs are not presented.
The resulting scaling exponent δ ± 0.03 distributes
in a wide range of [0.3, 0.9]. The distribution can
be separated into two branches with respect to the
center δc = 0.66. The two branches are asymmet-
ric and can be fitted exactly with the Gauusian func-
tion, respectively. The widths and centers of the left
and right branches are (wleft, xleftc ) = (0.17, 0.67),
(wright, xrightc ) = (0.10, 0.65). That is to say, the centers
coincide with each other, wleft ≈ wright ≈ δc = 0.66.
Comparatively, the right branch distributes in a signifi-
cant narrow region.
The PPRs are shuffled also. For each PPR, the shuf-
fling result is obtained by averaging over ten shuffling
samples. The scaling exponents are almost same, i.e.,
δshuffling = 0.5±0.03. The detected scale-invariant char-
acteristics are internal-structure-related.
How to understand the asymmetric characteristic of
the distribution of the complexity index δ is an in-
teresting problem. In literature, some statistical char-
acteristics of DNA sequences are captured with evo-
lution models, such as the long-range correlations and
the over- and under-representation of strings and so on
[31, 32, 33]. From the perspective of evolution, per-
haps the distribution characteristics may favor a stochas-
tic evolution model. The initial sequences have same
complexity δinitial = δc = 0.66. With the evolution
processes the sequences diffuse along two directions, in-
creasing complexity and decreasing complexity, i.e, the
index δ increases and decreases, respectively. The diffu-
sion coefficients for the two directions are significantly
different, denoted with Dleft 6= Dright. Based upon
the widths of the two branches we can estimate that,
Dleft
Dright =
δleft
δright = 1.7. It should be noted
that, the complexity is regarded as the departure from
the ordinary condition, δ = 0.5. In the totally 4737 values
of δ, only a small portion of them are less than 0.5. Ac-
cordingly, the PPRs may be catalogued into two classes,
the PPRs with high complexity and the PPRs with low
complexity. The former class evolves averagely with a
slow speed while the later one with a high speed.
In summary, by means of the DE method, we calculate
the complexities of the 4737 PPRs. The distribution of
the complexity index includes two asymmetric branches,
which obey Gaussian form with different widths, respec-
tively. A stochastic evolution model may provide us a
comprehensive understand of these characteristics.
IV. ACKNOWLEDGEMENTS
This work is funded by the National Natural Sci-
ence Foundation of China under Grant Nos. 70571074,
10635040 and 70471033, by the National Basic Re-
search Program of China (973 Program) under grant
No.2006CB705500), by the President Funding of Chinese
Academy of Science, and by the Specialized Research
Fund for the Doctoral Program of Higher Education of
China. One of the authors (H. Yang) would like to thank
Prof. Y. Zhuo for stimulating discussions.
[1] Ohler,U. and Niemann,H. (2001) Identification and anal-
ysis of eukaryotic promoters: recent computational ap-
proaches. Trends Genet., 17, 56-60.
[2] Werner,T. (1999) Models for prediction and recognition
of eukaryotic promoters. Mammalian Genome, 10, 168-
[3] Pedersen,A.G., Baldi,P., Chauvin,Y., Brunak,S. (1999)
The biology of eukaryotic promoter prediction - a review.
Comput. Chem., 23, 191-207.
[4] Zhang,M.Q. (2002) Computational methods for promoter
recognition. In: Jiang T, Xu Y, Zhang,M.Q., editors.
Current topics in computational molecular biology. Cam-
bridge, Massachusetts: MIT Press; p. 249-268.
[5] Narang,V., Sung,W.-K., Mittal A. (2005) Computational
modeling of oligonucleotides positional densities for hu-
man promoter prediction. Art. Intel. Med., 35, 107-119.
[6] Rosenberg, N. and Jolicoeur, P. (1997) Retroviral patho-
genesis. In Retroviruses (Coffin, J.M. et al., eds), pp.
475–586, Cold Spring Harbor Press.
[7] Buldyrev,S.V., Goldberger,A.L., Havlin,S., Man-
tegna,R.N., Matsa,M.E., Peng,C.-K., Simons, M. and
Stanley,H.E. (1995) Long-range correlation properties
of coding and noncoding DNA sequences: GenBank
analysis. Phys. Rev. E 51, 5084-5091.
[8] Peng,C.K., Buldyrev,S., Goldberger,A., Havlin, S.,
Sciortino,F., Simons,M. and Stanley,H.E.(1992) Long-
range correlations in nucleotide sequences. Nature 356,
168-171.
[9] Li,W., Kaneko,K. (1992) Long-range correlations and
partial 1/f −α spectrum in a noncoding DNA sequence.
Europhys. Lett. 17, 655.
[10] Yang,H., Zhao,F., Zhuo,Y., et al. (2002) Analysis of DNA
chains by means of factorial moments. Phys. Lett. A
292,349-356.
[11] Provata, A., Almirantis,Y. (1997) Scaling properties of
coding and non-coding DNA sequences. Physica A 247,
[12] Provata,A., Almirantis,Y. (2000) Fractal cantor patterns
in the sequence structure of DNA, Fractals 8 ,15-27.
[13] Yang,H., Zhuo,Y., Wu,X. (1994) Investigation of ther-
mal denaturation of DNA molecules based upon non-
equilibrium transport approach. J. Phys. A 27, 6147-
6156.
[14] Salerno,M. (1991) Discrete model for DNA-promoter dy-
namics. Phys. Rev. A 44, 5292-5297.
[15] Lennholm,E., Homquist,M. (2003) Revisiting Salerno’s
sine-Gordon model of DNA: active regions and robust-
ness. Physica D 177, 233-241.
[16] Kalosakas,G., Rasmussen,K.O. and Bishop,A.R. (2004)
Sequence-specific thermal fluctuations identify start sites
for DNA transcription. Europhys. Lett. 68, 127-133.
[17] Yang,H., Zhao,F., Gu,J. and Wang,B. (2006) Nonlin-
ear modeling approach to human promoter sequences. J.
Theo. Bio. 241, 765-773.
[18] Trinklein, N.D., Aldred, S.J., Saldanha, A.J., My-
ers, R.M., 2003. Identification and functional analysis
of human transcriptional promoters. Genome Res. 13,
308C312.
[19] Suzuki,Y., Yamashita,R., Nakai,K. and Sugano,S. (2002)
DBTSS:DataBase of human transcriptional start sites
and full-length cDNAs. Nucleic Acids Res., 30, 328-331.
[20] Leonardo,M.–R., John,L.S., Gavin,C.K. and
David,L. (2004) Statistical analysis of over-
represented words in human promoter sequences.
Nucleic Acids Res., 32, 949-958. See also,
ftp://ftp.ncbi.nlm.nih.gov/pub/marino/published/
hs promoters/fasta/.
[21] Grigolini,P., Palatella,L. and Raffaelli,G. (2001) Complex
Geometry, Patterns, and Scaling in Nature and Society.
Fractals 9, 439-449.
[22] Scafetta,N., Hamilton,P. and Grigolini,P. (2001) The
thermodynamics of social processes: the teen birth phe-
nomenon. Fractals 9, 193-208.
[23] Scafetta,N. and Grigolini,P. (2002) Scaling detection in
time series: Diffusion entropy analysis. Phys. Rev. E 66,
036130.
[24] Bar-Yam, Y. (1997) Dynamics of Complex Systems.
Addison-Wesley, Reading, MA.
[25] Mandelbrot,B. B. (1988) Fractal Geometry of Nature.
W.H. Freeman, San Francisco, CA.
[26] Scafetta,N. and West, B. J. (2003) Solar flare intermit-
tency and the earth’s temperature anomalies. Phys. Rev.
Lett. 90, 248701.
[27] Scafetta,N., Latora,V. and Grigolini,P. (2002) Levy scal-
ing: The diffusion entropy analysis applied to DNA se-
quences. Phys. Rev. E 66, 031906.
[28] Yang,H., Zhao,F., Zhang,W. and Li,Z. (2005) Diffusion
entropy approach to complexity for a Hodgkin–Huxley
neuron. Physica A 347, 704-710.
[29] Yang,H., Zhao,F., Qi,L. and Hu,B. (2004) Temporal se-
ries analysis approach to spectra of complex networks.
Phys. Rev. E 69, 066104.
[30] Pipek,J. and Varga,I. (1992) Universal classification
scheme for the spatial-localization properties of one-
ftp://ftp.ncbi.nlm.nih.gov/pub/marino/published/
particle states in finite, d-dimensional systems. Phys.
Rev. A 46,3148-3163.
[31] Hsieh,L.-C., Luo,L., Ji F. and Lee,H.C. (2003) Minimal
model for genome evolution and growth. Phys. Rev. Lett.
90, 018101.
[32] Kloster,M. (2005) Analysis of evolution through compet-
itive selection. Phys. Rev. Lett. 95, 168701.
[33] Messer,P.W., Arndt,P.F. and Lassig,M. (2005) Solvable
sequence evolution models and genomic correlations.
Phys. Rev. Lett. 94, 138103.
