# Fractals and Hidden Symmetries in DNA

Authors: Carlo Cattani
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

This paper deals with the digital complex representation of a
DNA sequence and the analysis of existing correlations by wavelets.  The symbolic DNA sequence is mapped into a nonlinear time series. By studying this time series the existence of fractal shapes and symmetries will be shown.  At first step, the indicator matrix enables us to recognize some typical patterns of nucleotide distribution. The DNA sequence, of the influenza   virus A (H1N1),  is investigated by using the
complex  representation,  together with the corresponding walks on DNA; in particular,  it is shown that  DNA walks are fractals. Finally, by using  the wavelet analysis, the existence of symmetries is proven.


---

## Body

## 1. Introduction

The main task of this paper is to show the existence of hidden geometries which underly the structure of a DNA sequence. Moreover, it will be shown that this geometry is fractal. In order to achieve this goal the fundamental steps are(1)
the choice of the digital representation of the symbolic sequence of DNA,(2)
the definition of the indicator matrix,(3)
the construction of walks on DNA,(4)
the cluster analysis  of wavelet coefficients.In this paper it will be shown that the distribution of nucleotidesA,C,G,T along the sequence must fulfill some hidden geometrical rules, thus implying that the biological activity depends on these geometrical rules. The understanding of the underlying biological function from a possible interpretation of the given sequence of nucleotides [1–6] is still under investigation.The existence of hidden law, periodicities, and statistical correlations [2, 7–9] might help us to characterize each DNA sequence in order to construct a possible (functional) classification.From mathematical point of view the DNA sequence is a symbolic sequence (of nucleotides) with some empty spaces (no coding regions). In order to get some numerical information from this sequence it must be transformed into a digital sequence. When the symbolic sequence ofA,C,G,T is digitalized into one or more sequences of digits one may benefit from the statistical analysis of the digitalized time series, so that the genome can be characterized by the classical statistical parameters like variance, deviation, or nonclassical like complexity, fractal dimension, or long range dependence.There follows that the symbolic sequence is transformed into a very large time series (from half million of digits, for the primitive organisms such as fungus and eukaryotes and, to several millions, as for mammals, like the nearly 1.5 billion of nucleotides for the humans DNA). However, these large sequences look like some random sequences, from where it seems to be quite impossible to single out any single correlation (see, e.g., [8] and references therein).In any case the arbitray choice of the representative digital time series (discrete time signal) for the symbolic sequence of the genome, so that the representation would be the most suitable for the statistical-mathematical analysis, is a difficult task, that was approached with some interesting preliminary results by using a complex representation [10, 11].The easiest mathematical model for the transformation of a symbolic string into a numerical string is based on the Voss indicator function [12, 13] which is a discrete binary function. In the following a suitable generalization is given and it will be shown that the graphical representation gives rise to some featuring patterns. The existence of patterns and symmetries is shown also through the cluster analysis of the wavelet coefficients [14, 15].The analysis of DNA by wavelets [7, 9, 16], as seen in [9, 16–19], is an expedient tool to single out local behavior and to characterize singularities as local spikes and jumps [7, 14] or to express the scale invariance of coefficients [20] and thus the multifractal nature of the time series [21–23]. However, as shown below, the wavelet transform features also a decorrelation of the sequence, so that it allows the emergence of the basic rules of the uncorrelated sequence. We will see that the wavelet coefficients of the short Haar wavelet transform are quantized. This can be achieved by a decomposition of the sequence into short segments of equal length and by a wavelet transform to be applied to each segment.The long range-correlation in the digital representation of the DNA sequence [12, 13, 24–34] is a fundamental problem in DNA analysis. Correlation in a digital signal can be roughly linked with the concept of dependence, in a statistical sense, of elements which are far away from each other. The existence of correlation in DNA has been explained with the so-called process of duplication-mutation. According to [29, 35] in the evolutionary model the actual DNA sequence results from an original short-length chain that was duplicating and modifying some pieces of the sequence. Due to this there followed the characterizing 1/f power law decay [13, 26, 27]. The power law for long-range correlations is a measure of the scaling law, showing the existence of self-similar structures similar to the physics of fractals. The long-range correlation, which can be detected by the autocorrelation function, implies the scale independence (scale invariance) which is typical of fractals.The power law for long-range correlations is a measure of the scaling law, showing the existence of self-similar structures similar to the physics of fractals. The long-range correlation, which can be detected by the autocorrelation function [12, 13, 30–32, 36, 37], implies the scale independence (scale invariance) which is typical of fractals. However, the preliminary results in this topics were disputed [26, 27, 38] because of the limited number of available data and because of different approaches to this analysis. On the other hand the existence of patchiness and correlation would imply some important understanding of DNA organization. Therefore, in the following we will discuss the correlation of a DNA virus sequence, roughly 2000 base pairs (bp), with the undertsanding that a well-defined concept of correlation holds only on a long sequence of the order higher than 105. However, the most important are the fractal properties and symmetries which are well defined even for a short sequences. The identification (and classifications) of these patches could be the key point for understanding the large-scale structure of DNA.Due to the recent outbreak of 2009 H1N1 Flu Virus (Swine Flu) in humans, this paper will focus on the DNA influenza virus (for similar results on a mammalian and a fungus see [10, 11, 20]) with particular regards to the A (H1N1) variant provided by the National Center for Biotechnology Information [3–6]: (1)
influenza A virus (A/Puerto Rico/8/34(H1N1)) segment 1, complete sequence, 2341 bp,(2)
influenza A virus (A/Mexico City/MCIG01/2009(H1N1)) segment 4 sequence, submitted 13-Jan-2010, 1719 bp,(3)
influenza A virus (A/Nagasaki/HA-46/2009(H1N1)) segment 4, HA gene for hemagglutinin, complete cds, submitted 07-Jan-2010, 1701 bp,(4)
influenza A virus (A/Tver/IIV2969/2009(H1N1)) segment 4 hemagglutinin (HA) gene, complete cds, submitted 13-Jan-2010, 1744 bp,(5)
influenza A virus (A/Novosibirsk/02/2009(H1N1)) segment 4 hemagglutinin (HA) gene, complete cds, submitted 10-Jan-2010, 1752 bp,(6)
influenza A virus (A/Rio Grande do Sul/7108/2009(H1N1)) segment 4 sequence, submitted 08-Jan 2010, 1701 bp,(7)
influenza A virus (A/Rio de Janeiro/5090/2009(H1N1)) segment 4 sequence, submitted 08-Jan 2010, 1701 bp,(8)
influenza A virus (A/Ankara/03/2009(H1N1)) segment 4 hemagglutinin (HA) gene, complete cds, submitted 04-Jan-2010, 1701 bp.It will be shown that as the dog and candida DNA the influenza virus is characterized by DNA walks with fractal shape. The most amazing is that the same symmetries seen on the wavelet coefficients of the DNA walks for dog and candida holds true also for viruses. The fractal dimension of the indicator matrix for this virus is 2.03 much higher than dog's [11]; moreover some difference in the DNA walks for segment 4 will be highlighted.This paper is organized as follows. Section2 deals with some preliminary remarks on flu epidemiology; DNA and DNA representation together with the indicator matrix is given in Section 3. Here the global fractal estimate is computed and the existence of fractal patterns is shown. The complex (cardinal) representation is given in Section 4 and the DNA (complex) walks are analysed in Section 5. It is proven that DNA complex walks are fractals and they are compared with walks on pseudorandom and deterministic complex sequences. Section 6 deals with correlation, power spectrum, and complexity of DNA. Sections 7 and 8 deal with wavelets analysis and show the existence of simmetries in the wavelet coefficients.


## 2. Flu Epidemiology

Flu epidemics cause morbidity and mortality worldwide. Each year, only in the USA, more than 200000 patients are infected by influenza and there are approximately 36000 deaths due to influenza virus. Of the three types of influenza virus—A, B and C—the A and B types can cause flu epidemics. Influenza A virus is found not only in humans but also in many other animals. There are over hundreds of subtypes of Influenza A virus. All subtypes have been detected in wild birds, which are considered the source of influenza A viruses in all other animals. For example, pigs may be infected with influenza A viruses from different species (e.g., ducks and humans) at the same time, which may allow the genes of these viruses to mix, creating new variants of the hemagglutinin and/or neuraminidase proteins on the surface of the virus (antigenic shift). If these variants spread to humans, then they would not be recognized by the immune system and so can cause seasonal epidemics of flu. In addition, influenza viruses undergo mutations when they spread from place to place and therefore introduce gradual changes in the hemagglutinin and/or neuraminidase proteins (antigenic drift). It will be shown however, that even if there are some variants of the same virus at different places, still the DNA structure remains the same (at least in the indicator matrix, see below), without significant variations. In other words the DNA sequence might apparently show some differences, but when we pass to the digital representation and the indicator matrix, these differences vanish.Each year, it is essential to identify new flu virus variants and produce vaccines against them to avoid flu epidemics. Therefore the investigation of DNA sequence of variants might help to better understand the intrinsic nature of variation.The Centers for Disease Control and Prevention (CDC) and other health organizations are actively investigating the recent outbreak of 2009 H1N1 Flu Virus (Swine Flu) in humans. First cases were reported at the beginning of 2009. CDC has determined that this swine influenza A (H1N1) virus is contagious and is spreading from human to human. Swine Influenza is a respiratory disease of pigs (swine) caused by type A influenza virus that regularly causes outbreaks of flu in pigs. Like all influenza viruses, swine flu viruses change constantly. Pigs can be infected by avian influenza and human influenza viruses as well as swine influenza viruses. When influenza viruses from different species infect pigs, the viruses can reassort (i.e., swap genes) and new viruses that are a mix of swine, human, and/or avian influenza viruses can emerge. There are four main influenza type A virus subtypes that have been isolated in pigs: H1N1, H1N2, H3N2, and H3N1, but most of the recently isolated influenza viruses from pigs have been H1N1 viruses. While swine flu viruses do not normally infect humans, sporadic human infections with swine flu have occurred. Most commonly, these cases occur in persons with direct exposure to pigs; human-to-human transmission of swine flu can also occur, as is the case with the 2009 outbreak.An influenza A virion is composed of the nucleocapsid, a surrounding layer of the matrix protein (M1) and the membrane envelope. The envelope contains two major surface glycoproteins, that is, hemagglutinin (HA) and neuraminidase (NA), and a minor membrane protein M2. The nucleocapsid consists of individual ribonucleoproteins (vRNPs). Each vRNP contains one of the 8 genomic negative sense RNA segments (vRNA), multiple copies of the major structural protein NP, and a few copies of the RNA dependent-RNA-polymerase complex. All 8 vRNA species must be present in an infectious virion.A virion attaches to the host cell membrane via HA and enters the cytoplasm by receptor-mediated endocytosis, thereby forming an endosome. A cellular trypsin-like enzyme cleaves HA into products HA1 and HA2. HA2 promotes fusion of the virus envelope and the endosome membranes. A minor virus envelope protein M2 acts as an ion channel thereby making the inside of the virion more acidic. As a result, the major envelope protein M1 dissociates from the nucleocapsid and vRNPs are translocated into the nucleus via interaction between NP and cellular transport machinery. In the nucleus, the viral polymerase complexes transcribe and replicate the vRNAs. Newly synthesized mRNAs migrate to cytoplasm where they are translated. Posttranslational processing of HA, NA, and M2 includes transportation via Golgi apparatus to the cell membrane. NP, M1, NS1 (nonstructural regulatory protein), and NEP (nuclear export protein, a minor virion component) move to the nucleus, where bind freshly synthesized copies of vRNAs. The newly formed nucleocapsids migrate into the cytoplasm in an NEP-dependent process and eventually interact via M1 with a region of the cell membrane, where HA, NA, and M2 have been inserted. Then the newly synthesized virions bud from infected cell. NA destroys the sialic acid moiety of cellular receptors, thereby releasing the progeny virions.


## 3. Patterns on the Indicator Matrix

The DNA of each organism of a given species is a long sequence of a specific (large) number of base pairs (bp). The size of the DNA might range from105 to 109 number of base pairs. Each base pair is defined on the 4 elements alphabet of nucleotides: (3.1)A=adenine,C=cytosine,G=guanine,T=thymine.Let(3.2)𝒜=def{A,C,G,T}be the finite set (alphabet) of nucleotides andx∈𝒜 any member of the alphabet.A DNA sequence is the finite symbolic sequence(3.3)𝒮=ℕ×𝒜
so that
(3.4)𝒮=def{xh}h=1,…,N,N<∞
being
(3.5)xh=def(h,x)=x(h),(h=1,2,…,N;x∈𝒜)
the value x at the position h.


### 3.1. Indicator Matrix

The 2D indicator function, based on the 1D-definition given in [12], is the map
(3.6)u:𝒮×𝒮→{0,1}
such that(3.7)u(xh,xk)=def{1ifxh=xk,0ifxh≠xk,(xh∈𝒮,xk∈𝒮),
being
(3.8)u(xh,xk)=u(xk,xh),u(xh,xh)=1.According to (3.7), the indicator of an N-length sequence can be easily represented by the N×N sparse symmetric matrix of binary values {0,1} which results from the indicator matrix(3.9)uhk=defuxh(xk),(xh∈𝒮,xk∈𝒮;h,k=0,…,N-1),
being, explicitly, (3.10)⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋰G0100000001⋯C0001000010⋯A1000101100⋯A1000101100⋯T0010010000⋯A0000100100⋯C0001000010⋯T0010010000⋯G0100000001⋯A1000100100⋯uhkAGTCATAACG⋯This squared matrix can be plotted in 2 dimensions by putting a black dot where (Figure1) uhk=1 and white spot when uhk=0.Indicator matrix Influenza A virus (H1N1).
(a)(b)(c)(d)(e)(f)(g)(h)


### 3.2. Indicator Matrix for the Influenza Virus A H1N1

The data, under investigation, refer to influenza virus A (H1N1) segment 1 (Puerto Rico) and segment 4 recently submitted (January 2010) in different world regions: Russia (Tver, Novosibirsk), Japan (Nagasaki), America (Mexico City, Rio Grande do Sul, Rio de Janeiro) and Turky (Ankara).The plots of indicator matrix (Figure1) show that(1)
there are some motifs which are repeated at different scales like in a fractal;(2)
empty spaces are more distributed than filled spaces, in the sense that the matrixuhk is a sparse matrix (having more zeroes than ones);(3)
it seems that there are some square-like islands where black spots are more concentrated;(4)
some indicator matrix can be grouped into different sets like, (a) Tver, Novosibirsk; (b) Nagasaki, Rio GRande do Sul, Rio De Janeiro, Ankara; and (c) Mexico City.From the analyis of Figure1 we can also notice that even if there is a big distance among different places, the corresponding virus does not change (Nagasaki, Rio do Janeiro and Ankara are nearly the same).


### 3.3. Fractal Dimension

From the indicator matrix we can have an idea of the “fractal-like” distribution of nucleotides. The fractal dimension for the graphical representation of the indicator matrix plots can be computed as the average of the numberp(n) of "1" in the randomly taken n×n minors of the N×N correlation matrixuhk:(3.11)D=1N∑n=2Nlogp(n)logn.
The fractal dimension of the influenza virus A (H1N1) is 2.30±0.1 while that for the dog DNA and candida was 1.66±0.01 (see, e.g., [11]). However some interesting coinciding values can be observed in the following table where the fractal dimension up to 10-2 shows the same groups already seen in the matrix shapes of Figure 1:(3.12)PuertoRico2.322MexicoCity2.307Nagasaki2.302Tver2.328Novosibirsk2.323RioGrandedoSul2.302RiodeJaneiro2.299Ankara2.307


## 3.1. Indicator Matrix

The 2D indicator function, based on the 1D-definition given in [12], is the map
(3.6)u:𝒮×𝒮→{0,1}
such that(3.7)u(xh,xk)=def{1ifxh=xk,0ifxh≠xk,(xh∈𝒮,xk∈𝒮),
being
(3.8)u(xh,xk)=u(xk,xh),u(xh,xh)=1.According to (3.7), the indicator of an N-length sequence can be easily represented by the N×N sparse symmetric matrix of binary values {0,1} which results from the indicator matrix(3.9)uhk=defuxh(xk),(xh∈𝒮,xk∈𝒮;h,k=0,…,N-1),
being, explicitly, (3.10)⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋰G0100000001⋯C0001000010⋯A1000101100⋯A1000101100⋯T0010010000⋯A0000100100⋯C0001000010⋯T0010010000⋯G0100000001⋯A1000100100⋯uhkAGTCATAACG⋯This squared matrix can be plotted in 2 dimensions by putting a black dot where (Figure1) uhk=1 and white spot when uhk=0.Indicator matrix Influenza A virus (H1N1).
(a)(b)(c)(d)(e)(f)(g)(h)


## 3.2. Indicator Matrix for the Influenza Virus A H1N1

The data, under investigation, refer to influenza virus A (H1N1) segment 1 (Puerto Rico) and segment 4 recently submitted (January 2010) in different world regions: Russia (Tver, Novosibirsk), Japan (Nagasaki), America (Mexico City, Rio Grande do Sul, Rio de Janeiro) and Turky (Ankara).The plots of indicator matrix (Figure1) show that(1)
there are some motifs which are repeated at different scales like in a fractal;(2)
empty spaces are more distributed than filled spaces, in the sense that the matrixuhk is a sparse matrix (having more zeroes than ones);(3)
it seems that there are some square-like islands where black spots are more concentrated;(4)
some indicator matrix can be grouped into different sets like, (a) Tver, Novosibirsk; (b) Nagasaki, Rio GRande do Sul, Rio De Janeiro, Ankara; and (c) Mexico City.From the analyis of Figure1 we can also notice that even if there is a big distance among different places, the corresponding virus does not change (Nagasaki, Rio do Janeiro and Ankara are nearly the same).


## 3.3. Fractal Dimension

From the indicator matrix we can have an idea of the “fractal-like” distribution of nucleotides. The fractal dimension for the graphical representation of the indicator matrix plots can be computed as the average of the numberp(n) of "1" in the randomly taken n×n minors of the N×N correlation matrixuhk:(3.11)D=1N∑n=2Nlogp(n)logn.
The fractal dimension of the influenza virus A (H1N1) is 2.30±0.1 while that for the dog DNA and candida was 1.66±0.01 (see, e.g., [11]). However some interesting coinciding values can be observed in the following table where the fractal dimension up to 10-2 shows the same groups already seen in the matrix shapes of Figure 1:(3.12)PuertoRico2.322MexicoCity2.307Nagasaki2.302Tver2.328Novosibirsk2.323RioGrandedoSul2.302RiodeJaneiro2.299Ankara2.307


## 4. Complex Representation

The (digital) representation of a DNA sequence is defined as the map of𝒮 into ℝℓ,ℓ≥1.  The embedding space of representation is based on the 4 vectors
(4.1)Xx:𝒜→ℝℓ,(x∈𝒜,ℓ≥1)
in the real space ℝℓ, or almost equivalently in the complex space ℂℓ,(4.2)Xx:𝒜→ℂℓ,(x∈𝒜,ℓ≥1)
so that X(x)≡Xx is a ℓ-ple which is associated with the symbol x∈𝒜.There follows that the basic elements of the representation are(4.3)XA=(xA1,xA2,…,xAℓ),XC=(xC1,xC2,…,xCℓ),XG=(xG1,xG2,…,xGℓ),XT=(xT1,xT2,…,xTℓ)(ℓ≥1).The digital representation inℝℓ or ℂℓ of a N-length DNA sequence is the map ℛ:ℕ×𝒜→ℝℓ or, for a complex representation, ℛ:ℕ×𝒜→ℂℓ so that for each xn∈𝒮 it is
(4.4)xn→ℛY(n),(xn∈𝒮;Y(n)∈ℝℓ),
being
(4.5)Y(n)=defY(xn)=(3.5)Y(x(n))
defined as follows. Each element of the DNA sequence can be considered [39] as the linear combination:
(4.6)Y(n)=defu(A,xn)XA+u(C,xn)XC+u(G,xn)XG+u(T,xn)XT,(n=1,…,N).The graph ofYn=Y(n) is 𝒢 and if we define
(4.7)an=def∑i=1nu(A,xi),cn=def∑i=1nu(C,xi),gn=def∑i=1nu(G,xi),tn=def∑i=1nu(T,xi)
it is
(4.8)an+cn+gn+tn=n,
so that, as a consequence of (4.6) and the definition (4.7), the following identity holds:
(4.9)nY(n)=anXA+cnXC+gnXG+tnXT.
We have a degeneracy (or a loop, circuit, or periodicity) if it is (see, e.g., [40]) Y(n)=0 or, equivalently,
(4.10)anXA+cnXC+gnXG+tnXT=0.If, we do not have a degeneracy, then there is a one-to-one correspondence between the DNA sequence𝒮 and 𝒢, that is, 𝒮↔𝒢.


### 4.1. Cardinal Complex Representation

In the remaining part of the paper we consider the cardinal representation [11] in ℂ1, so that the DNA digital representation is the N-length one-dimensional complex signal {Yn}n=0,…,N-1. In this case, from (4.6) we have (4.11)Yn=u(A,xn)-u(C,xn)i-u(G,xn)+u(T,xn)i=[u(A,xn)-u(G,xn)]+[u(T,xn)-u(C,xn)]i
or
(4.12)Yn=ξn+ηni,|ξn|+|ηn|=1,ξnηn=0
with
(4.13)ξn=defu(A,xn)-u(G,xn),ηn=defu(T,xn)-u(C,xn),
so that the representation is a map 𝒮→ℂ1 and the time series Y(n) is a sequence of complex numbers:
(4.14){Yn}n=0,…,N-1,Yn=ξn+ηni.


## 4.1. Cardinal Complex Representation

In the remaining part of the paper we consider the cardinal representation [11] in ℂ1, so that the DNA digital representation is the N-length one-dimensional complex signal {Yn}n=0,…,N-1. In this case, from (4.6) we have (4.11)Yn=u(A,xn)-u(C,xn)i-u(G,xn)+u(T,xn)i=[u(A,xn)-u(G,xn)]+[u(T,xn)-u(C,xn)]i
or
(4.12)Yn=ξn+ηni,|ξn|+|ηn|=1,ξnηn=0
with
(4.13)ξn=defu(A,xn)-u(G,xn),ηn=defu(T,xn)-u(C,xn),
so that the representation is a map 𝒮→ℂ1 and the time series Y(n) is a sequence of complex numbers:
(4.14){Yn}n=0,…,N-1,Yn=ξn+ηni.


## 5. DNA Walks

DNA walk is defined as the series(5.1)∑Yn,n=0,…,N-1,
which is the cumulative sum on the DNA sequence representation:
(5.2){Y0,Y0+Y1,…,∑s=0n-1Ys,…,∑s=0N-1Ys}.
Taking into account (4.7), (4.11), for the complex cardinal representation, it is
(5.3)Zn=def∑s=0n-1Ys=∑s=0n-1{[u(A,xs)-u(G,xs)]+[u(T,xs)-u(C,xs)]i}=(an-gn)+(tn-cn)i,
so that the DNA walk is the complex values signal {Zn}n=0,…,N-1 with
(5.4)Zn=(an-gn)+(tn-cn)i,
where the coefficients an,gn,tn,cn given by (4.7)  and fulfil condition (4.8).The DNA walk (DNA series) on a complex cardinal representation is a complex series as well. If we map the points(5.5)Pn=(ℜ[Zn],ℑ[Zn])=(an-gn,tn-cn),n=0,…,N-1
whose coordinates are the real and the imaginary coefficients of each term of the DNA walk sequence, we obtain a cluster showing the existence of some patches or some kind of self-similarity (Figures 2 and 3).DNA walk of the influenza virus A.
(a)(b)(c)(d)(e)(f)(g)(h)DNA walk of the influenza virus A, on the bp of the interval (200,500).
(a)(b)(c)(d)(e)(f)(g)(h)Both figures for the influenza virus (Figures2 and 3) show that there exists a fractal behavior of the random walk on DNA sequence. Moreover, focussing on some segments of the DNA walks it can be seen that there are some featuring patterns (see, e.g., Figure 3, with respect to the base pairs between 200 and 500).Let us now compare the DNA walks with walks on pseudorandom and deterministic sequences.A pseudorandom (white noise) complex sequence similar to the cardinal complex representation (4.11) can be defined as follows:
(5.6)Rn=def(-1)rnisn
with rn, s2 being random integers and it looks like (5.7){-1,i,1,1,-i,i,-1,-i,i,1,-i,i,-1,i,1,-i,-i,-i,-1,…}.
Its random walk is(5.8)∑(-1)rnisn.
A deterministic walk can be (Figure 4(c))
(5.9)∑zn=def∑(-i)nsinπn+1
or, more similar to a DNA sequence (Figure 4(d)), (5.10)∑zn=def∑inn+1.
It can be seen (Figure 4) how the fractal shape of DNA walk is completely different from corresponding walks on random and deterministic sequences.Figure 4
Walks on random (a), flu DNA (b), and deterministic sequences (c, d).


## 6. Statistical Correlations in DNA

For a given sequence{Y0,Y1,…,YN-1} the variance is
(6.1)σ2=def1N∑i=0N-1Yi2-(1N∑i=0N-1Yi)2,
and the variance at the distance N-kis(6.2)σk2=def1N-k∑i=0N-k-1Yi2-(1N-k∑i=0N-k-1Yi)2.From the variance follows immediately the standard deviation(6.3)σ=σ2.The autocorrelation at the distancek,(k=0,…,N-1) is the sequence (see, e.g., [36])
(6.4)ck=def1σ2(1N-k∑i=0N-k-1YiYi+k-1(N-k)2∑i=0N-k-1Yi∑i=0N-k-1Yi+k)
with k=0,…,N-1.A simplified definition of correlation, in the fragmentF-N has been given [41] as follows: (6.5)ck=def∑i=FN-1-k1N-F-kuxi(xi+1+k)
with the indicator given by (3.7).The power spectrum can be computed as the Fourier transform ofck: (6.6)Sk=defĉk=∑n=0N-1cne-2πink/N.Ifck=0, there is no linear correlation, ck>0 means that there is a strong (linear) correlation (anticorrelation when ck<0), while c0=1 does not give any information about correlations. A true random process has a vanishing correlation ch=δ0h and its power spectrum Sh is constant. Its integral gives the Brownian motion (random walk) whose power spectrum is proportional to 1/k2.It has been shown [24, 34, 42] that correlations in DNA are linear. However, the main problem of this measure is that it strongly depends on the representation, on the length of the sequence, and, for nonbinary representation, it is affected by spurious results [36]. Moreover, the definition (6.4) holds only for real values of the representation.


### 6.1. Power Spectrum

Let{Yn}n=0,…,N-1 be a given series; the discrete Fourier is the sequence
(6.7)Ŷs=1N∑n=0N-1Yne-2πins/N,s=0,…,N-1.The power spectrum of the sequence{Yn}n=0,…,N-1, that is, the mean square fluctuation, is defined as [43]
(6.8)Sk=def∑s=0k-1|Ŷs|2.The power spectrum of a stationary sequence gives an indirect measure of the autocorrelation. A long-range correlation can be detected if the fluctuations can be described by a power law so that(6.9)Sk≅αkmax1≤k≤kmax[αk],1≤k≤kmax
with α>1/2.The fluctuation exponentα, with its values, characterizes a sequence as (1)
anticorrelated:α<1/2,(2)
uncorrelated (white noise):α≅1/2,(3)
correlated (long range correlated):α>1/2,(4)
1/f noise: α≅1,(5)
nonstationary, random-walk like:α>1(6)
Brownian noise:α≅3/2.For the human DNA there was observed [44] a long range correlation, only for coding regions, with α=0.61. However, the same value can be seen also for dog's and candida DNA [11] for the complete sequence (coding and noncoding regions), even if, by including the noncoding regions, this value is a little bit higher being α≅0.65 for the dog's, and α≅0.62 for the candida's DNA, respectively. For the Influenza virus A it is instead  α=0.02 (Figure 5).Figure 5
Power spectrum for influenza virus A DNA walk.When the power spectrum is a power-law function(6.10)S(k)=Sk∝1kα
then this function is scale invariant (like fractals), that is, f(λx)=λHf(x). It can be shown (see, e.g., [29]) that for the power-law functional dependence, in the N→∞ limit, it is (6.11)S(λk)∝λ1-aS(k),S(k)=1kb
with k≃1-a, and a being related to the so-called Hurst exponent. In other words, for a power-law function the power spectrum is scale-invariant (like a fractal).In particular, from Equation (6.11) there follows that when b≃1 and a≃0, the correlation function has a slow decay to zero and the spectrum is more properly called 1/f-noise (or white noise). This spectrum appears in many natural phenomena (noise in electronic devices, traffic flow, signals, radio-antenna, turbolence).The power spectrum1/k  has been observed in DNA sequences [30, 37], however it is not yet clear how the correlation function should be (step-function, power law decay, white-noise), and in particular if there exists a single length scale or a multilength scale [29]. This scale-dependence (or self-similarity) of DNA cannot yet been explained from biological point of views. A possible explanation could be the dynamic process of the evolution or maybe the functional activity inside constrained domain (like the fractal shape of brain, lungs, etc.) which might have some influence on the spatial geometry [38].The biological explanation of long-range correlations can be explained by the existence of heterogeneity in DNA (i.e., different density distribution of bases). The main questioning is about the power law spectrum:1/k [35] or 1/k2 [29]. Indeed it has been observed that the the power spectrum is nearly flat for low and high frequencies and only for the central part has a power low decay.However, [29, 30] the existence of long range correlation in DNA should be intended from statistical point of view in the sense that far away base pairs tend to have similar variation. In other words, this correlation should be understood as a periodic distribution of base pairs without a causality law between base pairs located at different segments far away from each other.


### 6.2. Complexity

The existence of repeating motifs, periodicity, and patchiness can be considered as a simple behavior of sequence, while nonrepetitiveness or singularity is taken as a characteristic feature of complexity. In order to have a measure of complexity, for ann-lenght sequence, [44] the following has been proposed:
(6.12)K=logΩ1/n
with
(6.13)Ω=n!an!cn!gn!tn!.
By using a sliding n-window [44] over the full DNA sequence one can visualize the distribution of complexity on partial fragment of the sequence. For the whole sequence the asymptotic constant value is (Figure 6) (6.14)K≅1.3,
that has been observed also for other DNA sequences [11].Figure 6
Complexity for the first 100 base pairs of influenza virus A DNA.Moreover, as can be seen from Figure6, initially Tver and Novosibirsk DNA shows a lower complexity (see also Figure 1).


## 6.1. Power Spectrum

Let{Yn}n=0,…,N-1 be a given series; the discrete Fourier is the sequence
(6.7)Ŷs=1N∑n=0N-1Yne-2πins/N,s=0,…,N-1.The power spectrum of the sequence{Yn}n=0,…,N-1, that is, the mean square fluctuation, is defined as [43]
(6.8)Sk=def∑s=0k-1|Ŷs|2.The power spectrum of a stationary sequence gives an indirect measure of the autocorrelation. A long-range correlation can be detected if the fluctuations can be described by a power law so that(6.9)Sk≅αkmax1≤k≤kmax[αk],1≤k≤kmax
with α>1/2.The fluctuation exponentα, with its values, characterizes a sequence as (1)
anticorrelated:α<1/2,(2)
uncorrelated (white noise):α≅1/2,(3)
correlated (long range correlated):α>1/2,(4)
1/f noise: α≅1,(5)
nonstationary, random-walk like:α>1(6)
Brownian noise:α≅3/2.For the human DNA there was observed [44] a long range correlation, only for coding regions, with α=0.61. However, the same value can be seen also for dog's and candida DNA [11] for the complete sequence (coding and noncoding regions), even if, by including the noncoding regions, this value is a little bit higher being α≅0.65 for the dog's, and α≅0.62 for the candida's DNA, respectively. For the Influenza virus A it is instead  α=0.02 (Figure 5).Figure 5
Power spectrum for influenza virus A DNA walk.When the power spectrum is a power-law function(6.10)S(k)=Sk∝1kα
then this function is scale invariant (like fractals), that is, f(λx)=λHf(x). It can be shown (see, e.g., [29]) that for the power-law functional dependence, in the N→∞ limit, it is (6.11)S(λk)∝λ1-aS(k),S(k)=1kb
with k≃1-a, and a being related to the so-called Hurst exponent. In other words, for a power-law function the power spectrum is scale-invariant (like a fractal).In particular, from Equation (6.11) there follows that when b≃1 and a≃0, the correlation function has a slow decay to zero and the spectrum is more properly called 1/f-noise (or white noise). This spectrum appears in many natural phenomena (noise in electronic devices, traffic flow, signals, radio-antenna, turbolence).The power spectrum1/k  has been observed in DNA sequences [30, 37], however it is not yet clear how the correlation function should be (step-function, power law decay, white-noise), and in particular if there exists a single length scale or a multilength scale [29]. This scale-dependence (or self-similarity) of DNA cannot yet been explained from biological point of views. A possible explanation could be the dynamic process of the evolution or maybe the functional activity inside constrained domain (like the fractal shape of brain, lungs, etc.) which might have some influence on the spatial geometry [38].The biological explanation of long-range correlations can be explained by the existence of heterogeneity in DNA (i.e., different density distribution of bases). The main questioning is about the power law spectrum:1/k [35] or 1/k2 [29]. Indeed it has been observed that the the power spectrum is nearly flat for low and high frequencies and only for the central part has a power low decay.However, [29, 30] the existence of long range correlation in DNA should be intended from statistical point of view in the sense that far away base pairs tend to have similar variation. In other words, this correlation should be understood as a periodic distribution of base pairs without a causality law between base pairs located at different segments far away from each other.


## 6.2. Complexity

The existence of repeating motifs, periodicity, and patchiness can be considered as a simple behavior of sequence, while nonrepetitiveness or singularity is taken as a characteristic feature of complexity. In order to have a measure of complexity, for ann-lenght sequence, [44] the following has been proposed:
(6.12)K=logΩ1/n
with
(6.13)Ω=n!an!cn!gn!tn!.
By using a sliding n-window [44] over the full DNA sequence one can visualize the distribution of complexity on partial fragment of the sequence. For the whole sequence the asymptotic constant value is (Figure 6) (6.14)K≅1.3,
that has been observed also for other DNA sequences [11].Figure 6
Complexity for the first 100 base pairs of influenza virus A DNA.Moreover, as can be seen from Figure6, initially Tver and Novosibirsk DNA shows a lower complexity (see also Figure 1).


## 7. Wavelet Analysis

Wavelet analysis can be considered as a good tool [19, 24, 29, 42] for studying the heterogeneity in a time series and in particular in a DNA sequence. Heterogeneity can be shortly described as follows: in some fragments of DNA there exists a higher concentration of nucleotides C,G with poor distribution of A,T while, on the contrary, other fragments are more rich of A,T and poor of C,G (see Figure 1). Thus a fundamental problem is to make a partition of a DNA sequence into homogenous segments. This segmentation can be done by minimizing the variance (or maximizing the entropy [36]).The wavelet transform expresses the signal in terms of dilated and scaled instances of the wavelet basis functions. If we callW[f]x0 the wavelet transform of the signal f(x) computed in x=x0 at the scale 2-n and h(x0) the local Hölder exponent, it is [24] W[f]x0≃2-nh(x0). Therefore, wavelet transform is one of the most expedient tools for detecting singularities. It can be used to define a generalization of box-counting method, the so-called wavelet transform modulus maxima, in order to focus on scaling behavior [24] and to visualize the multifractal property.In this section some fundamentals on Haar wavelet theory will be given and applied to the analysis of DNA sequences.


### 7.1. Haar Wavelet Basis

TheHaar scaling functionφ(x) is the characteristic function on [0,1]; its family of translated and dilated scaling functions is defined as (7.1)φkn(x)=def2n/2φ(2nx-k),(0≤n,0≤k≤2n-1),φ(2nx-k)={1,x∈Ωkn,0,x∉ΩknΩkn=def[k2n,k+12n).
The Haar wavelet family {ψkn(x)} is the orthonormal basis for the L2(ℝ) functions [45]: (7.2)ψkn(x)=def2n/2ψ(2nx-k),∥ψkn(x)∥L2=1,ψ(2nx-k)=def{-1,x∈[k2n,k+122n),1,x∈[k+122n,k+12n)0elsewhere,(0≤n0≤k≤2n-1),


### 7.2. Discrete Haar Wavelet Transform

LetY≡{Yi}, (i=0,…,2M-1,2M=N<∞,M∈ℕ) be a real and square summable time-series Y∈𝕂N⊂ℓ2 (where 𝕂 is a real field), sampled at the dyadic pointsxi=i/(2M-1), in the interval restricted, for convenience and without restriction, to Ω=[0,1]. The discrete Haar wavelet transform is the N×N matrix 𝒲N:𝕂N⊂ℓ2→𝕂N⊂ℓ2 which maps the vector Y into the vector of wavelet coefficientsβN={α,βkn}: (7.3)𝒲NY=βN,βN=def{α,β00,…,β2M-1-1M-1},Y=def{Y0,Y1,…,YN-1}(2M=N).Let the direct sum of matricesA,B be defined as (7.4)A⊕B=(A00B),
being 0 the matrix of zero elements. The N×N matrix 𝒲N can be computed by the recursive product [14, 15] (7.5)𝒲N=def[∏k=1M((P2k⊕I2M-2k)(H2k⊕I2M-2k))],N=2M
of the direct sum of the following elementary matrices. (1)
Identity:(7.6)I2k=(10⋱︸2k01),
which is equivalent to
(7.7)I2≡(1001),I2k≡I2⊕⋯⊕I2︸k=(I20⋱︸k0I2).(2)
Shuffle:(7.8)P2≡(1001),P4≡(1000001001000001),P8=(1↓→1↓→1↓→1→→1↓→1↓→1↓→1).
The arbitrary shuffle matrix P2k=(aij);  i,j=1,…,2k can be defined as ai+1,j+2=1,i=1,…,2k-1,j=1,…,2k-3,i=2k-1,…,2k-1,j=0,…,2k-2 and zero elsewhere.(3)
Lattice (derived from the recursive inclusion formulas see, e.g., [14, 15]):(7.9)H2≡(1212-1212),H4=H2⊕H2=(121200-12120000121200-1212),…,and in general(7.10)H2k≡H2⊕⋯⊕H2︸k=(H20⋱︸k0H2).For example, withN=4,M=2, assuming the empty set I0=def∅ as the neutral term for the direct sum ⊕ so that A⊕I0=I0⊕A=A, it follows from(7.5)(7.11)𝒲4=∏k=1,2[(P2k⊕I4-2k)(H2k⊕I4-2k)]=[(P2⊕I2)(H2⊕I2)]k=1[(P4⊕I0)(H4⊕I0)]k=2,
that is, (7.12)𝒲4=(12121212-12-121212-12120000-1212).


### 7.3. Haar Wavelet Coefficients and Statistical Parameters

From (7.3) with M=2,N=4, by explicit computation, we have (7.13)α=14(Y0+Y1+Y2+Y3)
and [10, 11, 20] (7.14)β00=12(Y2-Y0+Y3-Y1),β01=12(Y0-Y1),β11=12(Y3-Y2).
When the wavelet coefficients are given, the above equations can be solved with respect to the original data. With M=2,N=4, we have, for example,(7.15)Y0=α-β00+2β012,Y1=α-β00-2β012,Y2=α+β00-2β112,Y3=α+β00+2β112.Thus the first wavelet coefficientα represents the average value of the sequence and the other coefficients β the finite differences. The wavelet coefficients β's, also called details coefficients, are strictly connected with the first-order properties of the discrete time-series.


### 7.4. Hurst Exponent

Concerning the variance, from definition (6.1) we obtain by a direct computation its expression in terms of wavelet coefficients:
(7.16)σ2=1N∑n=0M-1∑k=02n-1(βkn)2(N=2M).It has been observed [25] that for scale invariant functions the standard deviation (6.3), as a function of the scale n, is (7.17)σ(2n)=σ(20)2n(H-1)
with H being Hurst exponent, so that in a log-log plot (7.18)log2σ(2n)=[n(H-1)+log2σ(20)]
we obtain a straight line whose slope gives an estimate of H.The Hurst exponent, in terms of wavelet coefficients, can be evaluated by the following [11].Theorem 7.1.
The Hurst exponent is given by(7.19)H=12+log2[∑k=02n-1(βkn)2]1/2|β00|n.Proof.
Taking into account (6.3) and (7.16), definition (7.17) become:
(7.20)12n/2[∑k=02n-1(βkn)2]1/2=|β00|2n(H-1),log2{12n/2[∑k=02n-1(βkn)2]1/2}-log2|β00|=n(H-1),
that is,
(7.21)1nlog212n/2[∑k=02n-1(βkn)2]1/2|β00|=(H-1),log22+1nlog212n/2[∑k=02n-1(βkn)2]1/2|β00|=H
from where (7.19) follows.


## 7.1. Haar Wavelet Basis

TheHaar scaling functionφ(x) is the characteristic function on [0,1]; its family of translated and dilated scaling functions is defined as (7.1)φkn(x)=def2n/2φ(2nx-k),(0≤n,0≤k≤2n-1),φ(2nx-k)={1,x∈Ωkn,0,x∉ΩknΩkn=def[k2n,k+12n).
The Haar wavelet family {ψkn(x)} is the orthonormal basis for the L2(ℝ) functions [45]: (7.2)ψkn(x)=def2n/2ψ(2nx-k),∥ψkn(x)∥L2=1,ψ(2nx-k)=def{-1,x∈[k2n,k+122n),1,x∈[k+122n,k+12n)0elsewhere,(0≤n0≤k≤2n-1),


## 7.2. Discrete Haar Wavelet Transform

LetY≡{Yi}, (i=0,…,2M-1,2M=N<∞,M∈ℕ) be a real and square summable time-series Y∈𝕂N⊂ℓ2 (where 𝕂 is a real field), sampled at the dyadic pointsxi=i/(2M-1), in the interval restricted, for convenience and without restriction, to Ω=[0,1]. The discrete Haar wavelet transform is the N×N matrix 𝒲N:𝕂N⊂ℓ2→𝕂N⊂ℓ2 which maps the vector Y into the vector of wavelet coefficientsβN={α,βkn}: (7.3)𝒲NY=βN,βN=def{α,β00,…,β2M-1-1M-1},Y=def{Y0,Y1,…,YN-1}(2M=N).Let the direct sum of matricesA,B be defined as (7.4)A⊕B=(A00B),
being 0 the matrix of zero elements. The N×N matrix 𝒲N can be computed by the recursive product [14, 15] (7.5)𝒲N=def[∏k=1M((P2k⊕I2M-2k)(H2k⊕I2M-2k))],N=2M
of the direct sum of the following elementary matrices. (1)
Identity:(7.6)I2k=(10⋱︸2k01),
which is equivalent to
(7.7)I2≡(1001),I2k≡I2⊕⋯⊕I2︸k=(I20⋱︸k0I2).(2)
Shuffle:(7.8)P2≡(1001),P4≡(1000001001000001),P8=(1↓→1↓→1↓→1→→1↓→1↓→1↓→1).
The arbitrary shuffle matrix P2k=(aij);  i,j=1,…,2k can be defined as ai+1,j+2=1,i=1,…,2k-1,j=1,…,2k-3,i=2k-1,…,2k-1,j=0,…,2k-2 and zero elsewhere.(3)
Lattice (derived from the recursive inclusion formulas see, e.g., [14, 15]):(7.9)H2≡(1212-1212),H4=H2⊕H2=(121200-12120000121200-1212),…,and in general(7.10)H2k≡H2⊕⋯⊕H2︸k=(H20⋱︸k0H2).For example, withN=4,M=2, assuming the empty set I0=def∅ as the neutral term for the direct sum ⊕ so that A⊕I0=I0⊕A=A, it follows from(7.5)(7.11)𝒲4=∏k=1,2[(P2k⊕I4-2k)(H2k⊕I4-2k)]=[(P2⊕I2)(H2⊕I2)]k=1[(P4⊕I0)(H4⊕I0)]k=2,
that is, (7.12)𝒲4=(12121212-12-121212-12120000-1212).


## 7.3. Haar Wavelet Coefficients and Statistical Parameters

From (7.3) with M=2,N=4, by explicit computation, we have (7.13)α=14(Y0+Y1+Y2+Y3)
and [10, 11, 20] (7.14)β00=12(Y2-Y0+Y3-Y1),β01=12(Y0-Y1),β11=12(Y3-Y2).
When the wavelet coefficients are given, the above equations can be solved with respect to the original data. With M=2,N=4, we have, for example,(7.15)Y0=α-β00+2β012,Y1=α-β00-2β012,Y2=α+β00-2β112,Y3=α+β00+2β112.Thus the first wavelet coefficientα represents the average value of the sequence and the other coefficients β the finite differences. The wavelet coefficients β's, also called details coefficients, are strictly connected with the first-order properties of the discrete time-series.


## 7.4. Hurst Exponent

Concerning the variance, from definition (6.1) we obtain by a direct computation its expression in terms of wavelet coefficients:
(7.16)σ2=1N∑n=0M-1∑k=02n-1(βkn)2(N=2M).It has been observed [25] that for scale invariant functions the standard deviation (6.3), as a function of the scale n, is (7.17)σ(2n)=σ(20)2n(H-1)
with H being Hurst exponent, so that in a log-log plot (7.18)log2σ(2n)=[n(H-1)+log2σ(20)]
we obtain a straight line whose slope gives an estimate of H.The Hurst exponent, in terms of wavelet coefficients, can be evaluated by the following [11].Theorem 7.1.
The Hurst exponent is given by(7.19)H=12+log2[∑k=02n-1(βkn)2]1/2|β00|n.Proof.
Taking into account (6.3) and (7.16), definition (7.17) become:
(7.20)12n/2[∑k=02n-1(βkn)2]1/2=|β00|2n(H-1),log2{12n/2[∑k=02n-1(βkn)2]1/2}-log2|β00|=n(H-1),
that is,
(7.21)1nlog212n/2[∑k=02n-1(βkn)2]1/2|β00|=(H-1),log22+1nlog212n/2[∑k=02n-1(βkn)2]1/2|β00|=H
from where (7.19) follows.


## 8. Algorithm of the Short Haar Discrete Wavelet Transform

In order to reduce the computational complexity of the wavelet transform (7.3), (7.5), the sequence Y can be sliced into subsequences and the wavelet transform is applied to each slice. With the reduced Haar transform [10, 11, 20] it is possible to reduce the number of basis functions and the computational complexity.Algorithm 8.1.
LetY={Yi}i=0,…,N-1 of N data, segmented into σ=N/p,(1≤σ≤N) segmentsofp=2m data:(8.1)Y={Yi}i=0,…,N-1=⨁s=0σ-1Ys,Ys≡{Ysp,Ysp+1,…,Ysp+p-1}(s=0,…,N-p;1≤p≤N),
and thep-parameters short (reduced or windowed) discrete Haar wavelet transform 𝒲p,σY of Yis defined as
(8.2)𝒲p,σ≡⨁s=0σ-1𝒲p,Y=⨁s=0σ-1Ys,𝒲p,σY=(⨁s=0σ-1𝒲p)Y=(⨁s=0σ-1𝒲pYs),𝒲2mYs={α00(s),β00(s),β01(s),β11(s),…,β2m-1-1m-1(s)}(2m=p).
For example, the reduced wavelet transform𝒲4,2 (to be compared with 𝒲8) is
(8.3)𝒲4,2=𝒲4⊕𝒲4,
that is,
(8.4)𝒲4,2=(121212120000-12-1212120000-121200000000-121200000000121212120000-12-1212120000-121200000000-1212).


### 8.1. Clusters of Wavelet Coefficients

Significant information on a time-series can be derived not only from the wavelet coefficients but also from clusters of wavelet coefficients.For theN=2M-length real vector Y the wavelet transform 𝒲NY represents a point in the N-dimensional Euclidean space (8.5)ℝN:(α,β00,β01,…,β2M-1-1M-1)
of the wavelet coefficients.For theN=2M-length complex vector Y the wavelet transform is applied to the real 𝒲Nℜ(Y) and to the imaginary part 𝒲Nℑ(Y) and gives either 1 point in (8.6)ℂN=ℝ2N:(α,β00,β01,…,β2M-1-1M-1,α*,β0*0,β0*1,…,β2M-1-1*M-1)
or 2 points in (8.7)ℝN×ℝN:(α,β00,β01,…,β2M-1-1M-1)×(α*,β0*0,β0*1,…,β2M-1-1*M-1)
or a cluster of N points in the product of 2 dimensional spaces: (8.8)∏i=1Nℝi2:(α,α*)×(β00,β0*0)×(β01,β0*1)×⋯×(β2M-1-1M-1,β2M-1-1*M-1),
where the star denotes the wavelet coefficients of ℑ(Y). In each 2-dimensional (phase) space ℝi2 there is only one point and these single points do not give any significant information about the existence of some autocorrelation of data. By using, instead, the p-parameter short Haar wavelet transform we can analyse the cluster of points (8.9)(𝒲pℜ(Ys),𝒲pℑ(Ys)),s=0,…,σ=Np
in the 2p-dimensional space ℝp×ℝp, that is, (8.10)(α,α*),(β00,β0*0),…,(β2p-1-1p-1,β2p-1-1*p-1).For a complex sequence{Yk}k=0,…,N-1={xk+iyk}k=0,…,N-1 we can consider the correlations (if any) between the wavelet coefficients of the real part {xk}k=0,…,N-1 against the imaginary coefficients {yk}k=0,…,N-1. This can be realized by the cluster algorithm of Table 1.Table 1{Y0,Y1,…,Yp}⊕{Yp+1,Yp+2,…,Y2p}⊕⋯Complex values sequence⇓xi=ℜ(Yi),yi=ℑ(Yi)Real values sequences⇓{x0,x1,…,xp}⊕{xp+1,xp+2,…,x2p}⊕⋯{y0,y1,…,yp}⊕{yp+1,yp+2,…,y2p}⊕⋯〉Real sequences⇓𝒲p{x0,x1,…,xp}⊕𝒲p{xp+1,xp+2,…,x2p}⊕⋯𝒲p{y0,y1,…,yp}⊕𝒲p{yp+1,yp+2,…,y2p}⊕⋯〉Wavelet transform⇓{α,β00,β01,β11,…}1⊕{α,β00,β01,β11,…}2⊕⋯{α*,β0*0,β0*1,β1*1,…}1⊕{α*,β0*0,β0*1,β1*1,…}2⊕⋯〉Wavelet coefficients⇓{(α,α*)}1⊕{(α,α*)}2⊕{(α,α*)}3⋯{(β00,β0*0)}1⊕{(β00,β0*0)}2⊕{(β00,β0*0)}3⋯{(β01,β0*1)}1⊕{(β01,β0*1)}2⊕{(β01,β0*1)}3⋯〉Clusters⋮⋮⋮This algorithm enables us to construct clusters of wavelet coefficients and to study the correlation between the real and imaginary coefficients of the DNA representation and DNA walk, as given in the following section.


### 8.2. Cluster Analysis of the Wavelet Coefficients of the Complex DNA Representation

The cluster algorithm of Table1, applied to the complex representation sequence (4.11), which is in the form (8.11){-1,i,1,1,-i,i,-1,-i,i,1,-i,i,-1,i,1,-i,-i,-i,-1,…}
shows that the values of the wavelet coefficients belong to some discrete finite sets (Figure 7).Cluster analysis of the 4th short Haar wavelet transform of the complex representation of the DNA influenza virus A H1N1 (Mexico City) in the planes: (a)(α,α*);(b) (β00,β0*0);(c) (β01,β0*1);(d)  (β11,β1*1).
(a)(b)(c)(d)For each complex DNA representation there are 2 sets of wavelet coefficients which correspond to the real and complex coefficient of the complex values of (5.1) and (5.4). However, even if the real and complex coefficients of the DNA walk show some nonlinear patterns (Figures 2 and 3 the detail coefficients range in some discrete sets of values. It can be seen by a direct computation that the jumps from one value to another belong to some discrete sets (see, e.g., Figure 7).If we compare the clusters of Figure7 with the clusters (Figure 8) of the pseudorandom sequence (5.6), which is similar to the above sequence, we can see that the set of wavelet coefficients is larger (still discrete) than the set for the DNA  although the detail coefficients have (more or less) the same values.Cluster analysis of the4th short Haar wavelet transform of the pseudo-random sequence (5.6) (n≤1200):(a) (α,α*);(b) (β00,β0*0); (c) (β01,β0*1); (d) (β11,β1*1).
(a)(b)(c)(d)As can be seen from Figure7,  the real and imaginary coefficients of the complex DNA representation increase with a given law and the distribution of the nucleotides must follow this rule. Moreover, it should be noticed that all wavelet coefficients are distributed on symmetric grids (Figure 7). Even if the DNA representation looks like the pseudorandom sequence (5.6), the wavelet (detail) coefficients are quantized and symmetrically distributed in the sense that the detail coefficients of both the representation and the DNA walks (see [11]) have discrete finite values (Figure 7), being, in particular, (8.12)|β00±β0*0|≤2.This is not true for the pseudorandom series, because the wavelet coefficients of the sequence are still quantized (see Figure8) while the wavelet coefficients of the corresponding random walk are randomly distributed in the phase plane (Figure 10). It is very interesting to compare also the DNA walk (Figure 9) with the random walk (Figure 10) and random walk on deterministic sequence. DNA walk shows a clear symmetry which is missing in the others.Cluster analysis of the 4th short Haar wavelet transform of the walk on (whole sequence) DNA for the influenza virus A H1N1 (Mexico City) in the planes: (a)(α,α*);(b) (β00,β0*0);(c) (β01,β0*1);(d) (β11,β1*1).
(a)(b)(c)(d)Cluster analysis of the 4th short Haar wavelet transform of the random walk(n≤1200) of the random sequence (5.6) in the planes:(a) (α,α*);(b) (β00,β0*0);(c) (β01,β0*1);(d) (β11,β1*1).
(a)(b)(c)(d)Cluster analysis of the 4th short Haar wavelet transform of the walk (n≤1200) of the deterministic sequence (5.9) in the planes: (a) (α,α*);(b) (β00,β0*0);(c) (β01,β0*1);(d) (β11,β1*1).
(a)(b)(c)(d)


## 8.1. Clusters of Wavelet Coefficients

Significant information on a time-series can be derived not only from the wavelet coefficients but also from clusters of wavelet coefficients.For theN=2M-length real vector Y the wavelet transform 𝒲NY represents a point in the N-dimensional Euclidean space (8.5)ℝN:(α,β00,β01,…,β2M-1-1M-1)
of the wavelet coefficients.For theN=2M-length complex vector Y the wavelet transform is applied to the real 𝒲Nℜ(Y) and to the imaginary part 𝒲Nℑ(Y) and gives either 1 point in (8.6)ℂN=ℝ2N:(α,β00,β01,…,β2M-1-1M-1,α*,β0*0,β0*1,…,β2M-1-1*M-1)
or 2 points in (8.7)ℝN×ℝN:(α,β00,β01,…,β2M-1-1M-1)×(α*,β0*0,β0*1,…,β2M-1-1*M-1)
or a cluster of N points in the product of 2 dimensional spaces: (8.8)∏i=1Nℝi2:(α,α*)×(β00,β0*0)×(β01,β0*1)×⋯×(β2M-1-1M-1,β2M-1-1*M-1),
where the star denotes the wavelet coefficients of ℑ(Y). In each 2-dimensional (phase) space ℝi2 there is only one point and these single points do not give any significant information about the existence of some autocorrelation of data. By using, instead, the p-parameter short Haar wavelet transform we can analyse the cluster of points (8.9)(𝒲pℜ(Ys),𝒲pℑ(Ys)),s=0,…,σ=Np
in the 2p-dimensional space ℝp×ℝp, that is, (8.10)(α,α*),(β00,β0*0),…,(β2p-1-1p-1,β2p-1-1*p-1).For a complex sequence{Yk}k=0,…,N-1={xk+iyk}k=0,…,N-1 we can consider the correlations (if any) between the wavelet coefficients of the real part {xk}k=0,…,N-1 against the imaginary coefficients {yk}k=0,…,N-1. This can be realized by the cluster algorithm of Table 1.Table 1{Y0,Y1,…,Yp}⊕{Yp+1,Yp+2,…,Y2p}⊕⋯Complex values sequence⇓xi=ℜ(Yi),yi=ℑ(Yi)Real values sequences⇓{x0,x1,…,xp}⊕{xp+1,xp+2,…,x2p}⊕⋯{y0,y1,…,yp}⊕{yp+1,yp+2,…,y2p}⊕⋯〉Real sequences⇓𝒲p{x0,x1,…,xp}⊕𝒲p{xp+1,xp+2,…,x2p}⊕⋯𝒲p{y0,y1,…,yp}⊕𝒲p{yp+1,yp+2,…,y2p}⊕⋯〉Wavelet transform⇓{α,β00,β01,β11,…}1⊕{α,β00,β01,β11,…}2⊕⋯{α*,β0*0,β0*1,β1*1,…}1⊕{α*,β0*0,β0*1,β1*1,…}2⊕⋯〉Wavelet coefficients⇓{(α,α*)}1⊕{(α,α*)}2⊕{(α,α*)}3⋯{(β00,β0*0)}1⊕{(β00,β0*0)}2⊕{(β00,β0*0)}3⋯{(β01,β0*1)}1⊕{(β01,β0*1)}2⊕{(β01,β0*1)}3⋯〉Clusters⋮⋮⋮This algorithm enables us to construct clusters of wavelet coefficients and to study the correlation between the real and imaginary coefficients of the DNA representation and DNA walk, as given in the following section.


## 8.2. Cluster Analysis of the Wavelet Coefficients of the Complex DNA Representation

The cluster algorithm of Table1, applied to the complex representation sequence (4.11), which is in the form (8.11){-1,i,1,1,-i,i,-1,-i,i,1,-i,i,-1,i,1,-i,-i,-i,-1,…}
shows that the values of the wavelet coefficients belong to some discrete finite sets (Figure 7).Cluster analysis of the 4th short Haar wavelet transform of the complex representation of the DNA influenza virus A H1N1 (Mexico City) in the planes: (a)(α,α*);(b) (β00,β0*0);(c) (β01,β0*1);(d)  (β11,β1*1).
(a)(b)(c)(d)For each complex DNA representation there are 2 sets of wavelet coefficients which correspond to the real and complex coefficient of the complex values of (5.1) and (5.4). However, even if the real and complex coefficients of the DNA walk show some nonlinear patterns (Figures 2 and 3 the detail coefficients range in some discrete sets of values. It can be seen by a direct computation that the jumps from one value to another belong to some discrete sets (see, e.g., Figure 7).If we compare the clusters of Figure7 with the clusters (Figure 8) of the pseudorandom sequence (5.6), which is similar to the above sequence, we can see that the set of wavelet coefficients is larger (still discrete) than the set for the DNA  although the detail coefficients have (more or less) the same values.Cluster analysis of the4th short Haar wavelet transform of the pseudo-random sequence (5.6) (n≤1200):(a) (α,α*);(b) (β00,β0*0); (c) (β01,β0*1); (d) (β11,β1*1).
(a)(b)(c)(d)As can be seen from Figure7,  the real and imaginary coefficients of the complex DNA representation increase with a given law and the distribution of the nucleotides must follow this rule. Moreover, it should be noticed that all wavelet coefficients are distributed on symmetric grids (Figure 7). Even if the DNA representation looks like the pseudorandom sequence (5.6), the wavelet (detail) coefficients are quantized and symmetrically distributed in the sense that the detail coefficients of both the representation and the DNA walks (see [11]) have discrete finite values (Figure 7), being, in particular, (8.12)|β00±β0*0|≤2.This is not true for the pseudorandom series, because the wavelet coefficients of the sequence are still quantized (see Figure8) while the wavelet coefficients of the corresponding random walk are randomly distributed in the phase plane (Figure 10). It is very interesting to compare also the DNA walk (Figure 9) with the random walk (Figure 10) and random walk on deterministic sequence. DNA walk shows a clear symmetry which is missing in the others.Cluster analysis of the 4th short Haar wavelet transform of the walk on (whole sequence) DNA for the influenza virus A H1N1 (Mexico City) in the planes: (a)(α,α*);(b) (β00,β0*0);(c) (β01,β0*1);(d) (β11,β1*1).
(a)(b)(c)(d)Cluster analysis of the 4th short Haar wavelet transform of the random walk(n≤1200) of the random sequence (5.6) in the planes:(a) (α,α*);(b) (β00,β0*0);(c) (β01,β0*1);(d) (β11,β1*1).
(a)(b)(c)(d)Cluster analysis of the 4th short Haar wavelet transform of the walk (n≤1200) of the deterministic sequence (5.9) in the planes: (a) (α,α*);(b) (β00,β0*0);(c) (β01,β0*1);(d) (β11,β1*1).
(a)(b)(c)(d)


## 9. Conclusion

In this paper some fractal shapes and symmetries in DNA sequences and DNA walks have been shown and compared with random and deterministic complex series. DNA sequences are structured in  such a way that there exists some fractal behavior which can be observed both on the correlation matrix and on the DNA walks. Wavelet analysis confirms by a symmetrical clustering of wavelet coefficients the existence of scale symmetries.



---

*Source: 507056-2010-06-15.xml*