Identification
of repeats in DNA sequences using
Doc-Start
nucleotide distribution uniformity

Vol. 00 no. 00 2016
Pages 1–7

Changchuan Yin ∗

arXiv:1608.00567v1 [q-bio.GN] 31 Jul 2016

Department of Mathematics, Statistics and Computer Science
The University of Illinois at Chicago, Chicago, IL 60607-7045, USA

ABSTRACT
Motivation: Repetitive elements are important in genomic structures,
functions and regulations, yet effective methods in precisely
identifying repetitive elements in DNA sequences are not fully
accessible, and the relationship between repetitive elements and
periodicities of genomes is not clearly understood.
Results: We present an ab initio method to quantitatively detect
repetitive elements and infer the consensus repeat pattern in
repetitive elements. The method uses the measure of the distribution
uniformity of nucleotides at periodic positions in DNA sequences or
genomes. It can identify periodicities, consensus repeat patterns,
copy numbers and perfect levels of repetitive elements. The results
of using the method on different DNA sequences and genomes
demonstrate efficacy and accuracy in identifying repeat patterns and
periodicities. The complexity of the method is linear with respect to
the lengths of the analyzed sequences.
Availability: The Python programs in this study are freely available
to the public upon request or at https://github.com/cyinbox
Contact: cyin1@uic.edu

1

INTRODUCTION

Repetitive elements in DNA sequences consist two or more copies
of approximate patterns of nucleotides and are abundant in both
prokaryotic and eukaryotic genomes. Over two-thirds of the
human genome and 5-10% bacterial genomes are repetitive regions
(de Koning et al., 2011). Repetitive elements play important roles
in genome structure and functions such as nucleoprotein complex
formation, chromosome structure, and gene expression. Various
diseases including cancer and neurodegentive disease can also arise
from changes of repetitive elements. The distribution of repetitive
DNA sequences can be used as fingerprints of bacterial genomes
(Versalovic et al., 1991) and human individuals.
Repetitive elements are complex structures. They may exist
as imperfect tandem repeats, insertion and deletions in repeats,
interspersed repeats, and palindromic sequences, etc. These partial
and hidden repeat signals in DNA sequences are difficult to analyze
through straightforward observation and sequence comparison.
Currently, repetitive elements and hidden periodicities of DNA
and protein sequences are primarily detected by digital signal
processing and statistical approaches (Treangen and Salzberg,
2011). In most signal processing methods, DNA sequences are
converted to numerical sequences, and the hidden periodicities
∗ To

arising from repetitive elements can be identified by Fourier power
spectrum at specific periodicities (Yin and Wang, 2016). Commonly
used signal processing methods by Fourier transform include
SRF maps (Sharma et al., 2004), spectral analysis (Buchner and
Janjarasjitt, 2003), Ramanujan-Fourier transform (Yin et al., 2015),
and the periodic power spectrum method (Yin and Wang, 2016). The
statistical methods are based on distribution analysis of nucleotides
in DNA sequences. The common statistical methods for repeat
findings are tandem repeats finder (Benson, 1999) and statistical
spectrum (Epps et al., 2011), maximum likelihood estimation (Arora
and Sethares, 2007), and information decomposition (Korotkov
et al., 2003). Besides signal processing and statistical approaches,
sequence alignments such as RepeatMask are also used to identify
repetitive patterns in genomes, and but require a known reference
repeat sequence.
Despite significant advances in repeat finding, it is still difficult
to precisely capture the essential features of repetitive elements
such as consensus patterns, perfect levels and copy numbers of
repeats. For example, while Fourier transform is the most common
used approach for finding repeats, it may not exactly correlate
the strength of Fourier power spectrum with the perfect level of
repeat patterns. Furthermore, since Fourier power spectrum is weak
for short DNA sequences and long harmonious periodicities are
embedded in short periodicities, Fourier transform can not capture
repeats in short DNA sequences and long harmonious periodicities.
Moreover, the relationship between repetitive elements and
periodicities of genomes is not fully understood. Thus there is a
high potential for improving the accuracy for identifying repetitive
elements and better understanding the relationship of periodicities
and repeats in DNA sequences (Suvorova et al., 2014; Epps et al.,
2011; Illingworth et al., 2008).
In this paper, we present an ab initio method to quantitatively
identify repetitive sequences and periodicities in DNA sequences.
The method is based on the nucleotide distribution uniformity at
periodic positions in DNA sequences or genomes. The distribution
uniformity of nucleotides reflects the unbalance of nucleotide
frequencies on periodic positions and thus can indicate the strength
for periodic signals in DNA sequences. The method can also
reveal the consensus repeat pattern for the major periodicity of
DNA sequences, and quantitatively determine the perfect level and
copy numbers of repetitive sequences. The proposed method also
formulates the relationship between repetitive elements and the
corresponding periodicities in DNA sequences.

whom correspondence should be addressed. Email: cyin1@uic.edu

c Changchuan Yin, Ph.D., University of Illinois at Chicago 2016.

1

Yin, C.

2
2.1

METHODS AND ALGORITHMS
Periodic nucleotide frequencies in a DNA sequence

A DNA molecule consists of four linearly joined nucleotides,
adenine (A), thymine (T), cytosine (C), and guanine (G). A DNA
sequence can be represented as a string of the four characters
A, T, C, and G. The nucleotide frequencies at periodic positions,
which can be represented by a congruence derivative vector (Wang
et al., 2012; Yin and Wang, 2016; Wang and Yin, 2016), reflect
the arrangement of repetitive elements and inner periodicities in a
DNA sequence. The congruent derivative vector of a nucleotide α
for a specific periodicity is constructed by the cumulative occurring
frequencies of nucleotides at the periodic positions (Definition 2.1).

j
G
C
A
T

D EFINITION 2.1. For a DNA sequence of length n, let uα (k) = 1
when the nucleotide α appears at position k, otherwise, uα (k) = 0,
where α ∈ {A, T, C, G} and k = 1, · · · , n. The congruence
derivative vector of the nucleotide α of the sequence for periodicity
p, is defined as
fα,j =

X

uα (k)

mod (k,p)=j

(1)

j = 1, · · · , p, k = 1, · · · , n

1
3
2
11
0

2
1
1
3
11

3
2
13
0
1

4
7
3
3
3

5
10
4
2
0

Fig. 1: The congruence derivative matrix of periodicity 5 of
an artificial DNA sequence (left) and the inferred 16 copies of
approximate 5 bp repeats (right). The consensus sequence of the
repeats inferred from the matrix is ATCGG in color. The DNA
sequence of 80 bp is described in the text.

where mod(k, p) is the modulo operation and returns the remainder
after division of k by p, and fα = (fα (1), fα (2), · · · , fα (p)).
Four congruence derivative vectors fα of periodicity p for
nucleotides A, T, C and G form a congruence derivative (CD) matrix
of size 4 × p. The columns of the CD matrix indicate nucleotide
frequencies at the periodic positions k = pt − q, where k is the
position index of a DNA sequence, t = 1, 2, . . ., and q = p −
1, . . . , 2, 1, 0. For example, consider the CD matrix of periodicity
5 for DNA sequence, the first column of the CD matrix shows the
nucleotide frequencies at periodic positions k = 1, 6, 11, . . . , 5t−4;
the second column of the matrix shows the nucleotide frequencies
at periodic positions k = 2, 7, 12, . . . , 5t − 3; the third column of
the matrix shows the nucleotide distributions at periodic positions
k = 3, 8, 13, . . . , 5t − 2, and so on. In this way, the CD matrix
of a DNA sequence describes nucleotide frequencies at all periodic
positions and can be used to efficiently compute Fourier power
spectrum and determine periodicities in the DNA sequence (Yin and
Wang, 2016). In this study, instead of Fourier transform, we use the
CD matrix to identify repetitive elements and periodicities directly.
This approach offers elaboration of the repetitive elements such as
the consensus repeat pattern, copy number and perfect level.
To illustrate the nucleotide frequencies in the CD matrix, an
artificial DNA sequence of 80 bp, ATTGAACCCGGTGCGAACACATCTCCACTCATCGAAGCGCGTCGGATCAGGTCAGATCGGATCTGATCGGAACGGCTGCG, which contains 5 bp approximate
repeats, is constructed. The CD matrix of periodicity 5 for this
sequence is shown in Fig.1. The base with the highest frequency
in each column is labeled in color, while the other bases are labeled
in black. The consensus sequence of the repeats can be identified
as ATCGG from the highest frequency in each column in the CD
matrix. Thus, we may determine that the DNA sequence contains
16 copies of approximate ATCGG (Fig.1). The bases show in black
in columns are then the mismatched nucleotides when the actual
sequence is compared with the consensus sequence at the periodic
positions.

2

2.2

Computing the distribution uniformity (DU) of a
DNA sequence

Identification of repeats and periodicities in DNA sequences is
often realized by Fourier transform. However, Fourier power
spectrum may not characterize repetitive elements precisely. It
does not identify the consensus repetitive pattern, copy number
and perfect level. We propose to employ the periodic nucleotide
frequencies as a measure of repeats and periodicities. Previously
we showed that the nucleotide distribution on periodic positions
correlates with the strength of periodicity 3 (Yin and Yau, 2005).
We here generalize to use the nucleotide distribution as the signal
measure for any periodicities. Since the CD matrix contains the
nucleotide frequencies on periodic positions, the variance of the
matrix elements can measure the nucleotide distribution. For the CD
matrix of periodicity p, the summation of total 4p elements of the
matrix is equal to length n of the DNA sequence, the mean of the
n
. To measure the nucleotide distribution
elements of the matrix is 4p
and use it to indicate the periodic signal in a DNA sequence, we
define the distribution uniformity (DU) of a DNA sequence using
the CD matrix (Definition 2.2).
D EFINITION 2.2. For a DNA sequence of length n, let fi,j be an
element of the CD matrix of periodicity p, the distribution uniformity
of periodicity p of the sequence is defined as
DU (p) =

p
4 X
X
i=1 j=1

(fi,j −

n 2
)
4p

(2)

From Definition 2.2., we notice that the distribution uniformity
at periodicity p is an intuitive description for the level of unbalance
of nucleotide frequencies on periodic positions. It depends on the
quadratic function of the nucleotide frequencies, sequence and
periodicity length. Additionally, Definition 2.2 can be rewritten as

Identification of repeats in DNA sequences

Equation (3). It shows that for fixed length and periodicity, the
distribution uniformity only depends on the squares of nucleotide
frequencies. The proof of Equation (3) is provided in the
supplementary materials.
DU (p) =

p
4 X
X

2
fi,j
−

i=1 j=1

n2
4p

(3)

For a DNA sequence of length n consisting of tandem perfect
repeats of size p, each column of the CD matrix contains three
zeros and one non-zero element n/p. Therefore, the distribution
uniformity of tandem perfect repeats is described in Equation (4).
DUX (p) =

p
4 X
X

(fi,j −

i=1 j=1


=p

=

n
n
−
p
4p

2



n 2
)
4p

n
+3 0−
4p

2 !

(4)

3n2
4p

Definition 2.2 and Equation (4) indicate that if the length n of
a DNA sequence is long or if repeat length p is short, then the
nucleotide distribution uniformity becomes large. For a random
DNA sequence with uniform nucleotide distribution, each element
n
of the CD matrix of periodicity p is equal to 4p
, so the DU (p) is
zero. Thus the distribution uniformities of any DNA sequences are
2
].
in range [0, 3n
4p
A copy number of repeats indicates how many repeats in a
DNA sequence or genome. Copy number variations depends on
repeat types and genomes and play an important role in generating
variation in population and disease phenotype (McCarroll and
Altshuler, 2007). The strength of a distribution uniformity is
impacted by the copy number of repeats. The more copies of repeats,
the stronger of the distribution uniformity. We define the copy
number of repeats as follows (Definition 2.3).
D EFINITION 2.3. The copy number of the repeats of size p is
equal to the division of the sequence length by the periodicity length
p.
n
CP (p) =
(5)
p
The above definitions indicate that the longer a DNA sequence
is, the larger the copy number is and the stronger distribution
uniformity is. To consistently compare the strengths of periodic
signals in DNA sequences of different lengths, we use the
normalized distribution uniformity (NDU), which can be considered
as the mean distribution uniformity. It is defined as the distribution
uniformity of periodicity p divided by the length of the sequence
(Definition 2.4). NDU(p) can be used to indicate for existence of
the periodicity p in a DNA sequence.
D EFINITION 2.4. The normalized distribution uniformity (NDU)
is equal to the distribution uniformity divided by the sequence length
n,
DU (p)
N DU (p) =
(6)
n
From Equation (3), the normalized distribution uniformity of
periodicity p of a DNA of length n can be further described as in

Equation (7)
N DU (p) =

p
4
1 XX 2
n
fi,j −
n i=1 j=1
4p

(7)

For tandem perfect repeats, we get NDU by Definitions 2.3 and
Equation (4) as follows.
N DUX (p) =

DUX (p)
3n2
3n
3
=
=
= CP (p)
n
4pn
4p
4

(8)

Equation (8) indicates that if the NDU of tandem perfect repeats
is larger than 1, the copy number of tandem perfect repeats is at
least 4/3. This fact designates the sequence feature of the NDU
threshold value as 1. When the NDU of a DNA sequence is larger
than 1, it suggests existence of a significant periodicity and repeats
in the sequence. This is the foundation of our algorithm for detecting
periodicity and repeats by using the distribution uniformity of
nucleotides.

2.3

Identifying the repeat pattern of length p in a DNA
sequence

Using the CD matrix of periodicity p, we can determine the
dominant nucleotide in each column of the matrix, where the
nucleotide has the maximum frequency at the qth periodic position
q = 1, 2 . . . , p (Definition 2.5). From the positions of dominant
nucleotides, we can determine the consensus repeat pattern.
D EFINITION 2.5. The dominant nucleotide of the congruence
derivative matrix of periodicity p of a DNA sequence is the element
with the maximum frequency in each column of the matrix.
dj = max(fi,j ), i ∈ {1, 2, 3, 4}, j = 1, 2, . . . , p

(9)

The consensus repeat pattern of size p of a DNA sequence
may be inferred from the dominant nucleotide frequencies of the
congruence derivative matrix of a periodicity p. In a CD matrix, dj
is the maximum of the jth column, if the corresponding nucleotide
in the matrix for dj is α ∈ {G, C, A, T }, then nucleotide α appears
periodically at the jth positions in the sequence. In detail, let rj be
jth nucleotide of the repeat unit of size p of the DNA sequence,
j = 1, 2, . . . p. If dj = fi,j , then rj = αi , α ∈ {G, C, A, T }. Thus
the consensus repeat pattern can be identified.
After the consensus repeat pattern of repetitive elements is
determined, a parameter is needed to measure the perfect level of
the approximate repeats compared with the tandem perfect repeats
of the same length. We define the perfect level P R(p) as the
percentage of matched nucleotides in a DNA sequence with tandem
perfect repeats of the same length (Definition 2.6).
D EFINITION 2.6. The perfect level P R(p) is the percentage of
matched nucleotides in a DNA sequence with tandem perfect repeats
of the same length. It is equal to the summation of dominant column
elements in the CD matrix divided by the sequence length n.
P R(p) =

p
1X
dj
n j=1

(10)

Since the NDU value of approximate repeats also depends on
perfect level, if at least two copies of tandem repeats are required,

3

Yin, C.

then from equations (3-10), the perfect level must be at least 2/3
(i.,e., 66.67%) to make NDU threshold larger than 1. In this study,
we use a NDU threshold of 1 (i.e., 100%) to determine whether a
distribution uniformity truly indicates the periodicity.
As an example, from the CD matrix of periodicity 5 in Fig.1, the
dominant nucleotide frequencies dj of the DNA sequence of length
80 bp are [11,11,13,7,10] and the derived consensus repeat pattern
is ATCGG. The perfect level computed by Equation (10) is 65%.
It indicates that among repeat elements, 65% nucleotides match 16
copies of tandem perfect repeats ATCGG.

2.4

Algorithms

The inputs for computing the distribution uniformity, copy number,
and perfect level are the sequence length n and periodicity length
p. Given a DNA sequence and periodicity p as inputs, we have
the following algorithm, named the distribution uniformity (DU)
method, for identifying repetitive elements and periodicities in a
DNA sequence.
Input: A DNA sequence of length n, periodicity p
Output: DU, NDU, consensu repeat pattern, perfect level, copy
number
Step: initialization
1. Convert DNA sequence into 4D binary indicators.
2. Compute congruence derivative (CD) matrix of periodicity p
from the 4D indicators.
3. From the CD matrix, we can compute:
3.1. DU (p) at periodicity p (Equation (3)).
3.2. N DU (p) (Equation (6)).
3.3. Consensus repeat pattern of size p (Equation (9)).
3.4. Perfect level P R(p) (Equation (10)).
3.5. Copy number for the repeat of size p (Equation (5)).
Algorithm 1: The algorithm for identifying repeats and periodicity
in a DNA sequence.

To compute distribution uniformities of different periodicities of
a DNA sequence, we first scan the sequence in different periodicity
sizes, construct the congruence derivative matrix of each periodicity,
and compute the distribution uniformities of these periodicities. The
periodicity with the maximum distribution uniformity reflects the
dominant pattern of repetitive elements.
Just like the short-time Fourier transform (STFT), to identify the
repeat regions in a DNA sequence, we adopt a fixed size window
to slide along DNA sequences, and compute the NDU values of
different periodicities in the window continuously. The NDU values
of periodicities indicate the perfect levels and copy numbers of
corresponding repeat regions.

3
3.1

RESULTS
Periodic analysis of short DNA sequences

For the artificial DNA sequence as described in Fig.1, the DU
method can identify harmonious periodicities 5, 10, 15, 20, 25, etc
(Fig.2 (a)). The NDU for periodicity 5 (Fig.2 (b)) and NDU values
1-40 in the sequence using short sliding window of length 20 bp
(Fig.2,(c)) conform the repeat structures in the sequence. The results

4

show that the signal of periodicity 5 is clear with very short window
size 20 bp. The capacity of capturing periodic signals from short
DNA sequences is an advantage of the proposed method.

3.2

Periodic analysis of highly complex repeats in DNA
sequences

The effectiveness of the proposed algorithm is tested on
Homo sapiens collagen type IV alpha 6 chain (COL4A6)
(GenBankID:NC_001847, 6618 bp). This gene contains repeats of
length 9 bp by the EPSD method (Gupta et al., 2007). The result
by the DU method shows that the sequence contains repeats of 3
bp, 6 bp, 9 bp (Fig.3(a)). The sliding window approach shows the
location and strength of the periodicity 9 (Fig.3(b)) and periodicities
1 100 (Fig.3(c)). The corresponding periodicity strength, NDU,
perfect level, consensus pattern, and copy number can be revealed
by the method (Table 1.). Table 1 shows that the perfect levels
of periodicities 3 , 6 and 9 are similar, but the periodicity 3 has
the largest mean NDU because of the highest copy number of
periodicity 3. The periodicities in this DNA sequence identified
by the proposed method are consistent with the EPSD method
(Gupta et al., 2007). The results demonstrate the effectiveness of the
proposed method in capturing different repeats and periodicities.
Table 1. Characterization of the repeats in human COL4A6 gene
(GenBankID:NC_001847).

p
3
6
9

NDU(p)
26.81036
13.9946
10.4310

PR(p)
0.3262
0.3262
0.3312

pattern
GGA
GGAGGA
GCAGGAGGT

copies
2206
1103
735

To test if the DU method can identify complex repeats, we
use the method to analyze Human microsatellite repeats (GenBank
locus:HSVDJSAT, 1985 bp). The DNA sequence contains variable
length tandem repeats (VLTRs) (Hauth and Joseph, 2002). The DU
method may detect accurately all different the short periodicities
and corresponding perfect levels and copy number of the repeats
in the full DNA sequence (Fig.4(a), Table 2). As an example, the
sliding window approach for the NDU of periodicity 7 indicates
that the 7 bp repeats are between positions 1000 and 1550 when
using the NDU threshold as 1 (Fig.4(b)). The method may locate
the positions of other repeats from the corresponding periodicities
(Fig.4(c)). Specially, in the region between 1000 and 1550 bp, two
long repeats of 18 bp and 19 bp can be identified using the DU
method (Table 3). These results agree with the previous studies by
statistical methods (Hauth and Joseph, 2002; Gupta et al., 2007),
however, the previous studies need different threshold settings and
sometimes get conflicting results.

3.3

Computational complexity

The computation complexity of the DU method for specific
periodicity p of DNA sequence of length n only involves computing
CD matrix O(n) and small number of multiplication of entries in
the matrix O(p2 + p)). Because periodicity p is much smaller
than n, O(p2 + p)) is very small, the computation complexity of
the DU method is approximate linear with the sequence length,

Identification of repeats in DNA sequences

4.0

30

3.5

25

3.0

20

NDU

NDU

2.5
2.0
1.5

15
10

1.0

5

0.5
0.0

0

10

20

30

40

Periodicity

0

50

0

20

40

(a)

5
4

NDU

NDU

100

6

2.0
1.5

3
2

1.0

1
0

10

20

30

40

Nucleotide position

50

0

60

0

1000

2000

3000

4000

Nucleotide position

(b)

5000

6000

0

2.7

5

2.4

10

2.1
1.8

15

1.5

20

1.2

25

0.9

30

0.6

35

0

10.5
9.0

20

7.5

40

6.0
4.5

60

3.0

80

1.5

0.3
0

10

20

30

Nucleotide position

7000

(b)

Periodicity

Periodicity

80

(a)

2.5

0.5

60

Periodicity

40

50

0.0

(c)

Fig. 2: The distribution uniformity of the artificial DNA sequence.
The sequence and its CD matrix are shown in Fig.1. (a) NDU
of different periodicities. (b) NDU of periodicity 5 of the DNA
sequence by sliding window of 20 bp. (c) NDU of different
periodicities in the DNA sequence by sliding window of 20 bp.

0

1000

2000

3000

4000

Nucleotide position

5000

6000

0.0

(c)

Fig. 3: The distribution uniformity analysis of Homo
sapiens collagen type IV alpha 6 chain (COL4A6)
(GenBankID:NC_001847). (a) NDU of different periodicities.
(b) NDU of periodicity 9 of the DNA sequence the sliding window
approach. (c) NDU of different periodicities in the DNA sequence
by sliding window approach. The window size is 200 bp.

5

Yin, C.

Table 2. Characterization of repeats in the Human microsatellite sequence
(GenBank locus:HSVDJSAT, region 1-1985 bp).

10
8

p
7
8
9
10
16
17
18
19

NDU

6
4
2
0

0

20

40

60

80

Periodicity

NDU(p)
3.0935
3.3153
2.8575
2.7049
1.9299
1.6939
1.7932
2.0291

PR(p)
0.3274
0.3314
0.3312
0.3314
0.3324
0.3324
0.3340
0.3420

pattern
GGGGGGG
GGAGGGTG
GGGGGGGGA
GGAGTGGGGG
GGAAGGTGGGAGGGTG
GGAAGGTGGGAGGGTG
AGGGGGAGGGGGGAGGGA
GGCGGGGGTAGGCGGGGAG

copies
283
248
220
198
124
116
110
104

100

(a)

Table 3. Characterization of long repeats in the Human microsatellite
sequence (GenBank locus:HSVDJSAT, region 1000-1550 bp).

4.5

p
18
19

4.0
3.5

NDU(p)
1.9875
3.5210

PR(p)
0.4560
0.5200

pattern
GGGGGGGGGGGGGGGGGG
CTGGGAGGGCTGGGAAAGG

copies
27
26

NDU

3.0
2.5
2.0
1.5

0.010

1.0
0.5

0.008

0

250

500

750

1000

1250

Nucleotide position

1500

1750

Time

0.0

(b)

0

22.5
20.0

Periodicity

20

17.5

40

15.0

60

10.0

80

5.0

12.5
7.5

0.006
0.004
0.002
0.000

0

1000

2000

3000

4000

DNA length

5000

6000

7000

(a)

Fig. 5: Running time of the DU method on DNA sequences of
different lengths.

2.5
0

500

1000

Nucleotide position

1500

0.0

(c)

Fig. 4: The distribution uniformity analysis of variable length
tandem repeats (VLTRs). (a) NDU of different periodicities. (b)
NDU of periodicity 5 of the DNA sequence by the sliding window
approach. (c) NDU of different periodicities of the DNA sequence
by the sliding window approach. The window size is 200 bp.

6

O(n). In contrast, using Fourier transform in detecting repetitive
elements has high computational complexity. The fast Fourier
transform (FFT) needs O(n log n) computational time. Because
only distribution uniformities at specific periodicities are needed for
detecting repetitive elements of interested lengths, instead of DUs
for all periodicities, the performance of the DU method for specific
periodicities is more efficient than Fourier transform. Performance
tests were performed on a PC with configuration as Intel Core
i5 processor, 6G RAM. The DU method has linear runtime for
any sequence lengths as shown in Fig.5. This result verifies the
complexity analysis, showing high efficiency of the DU method.

Identification of repeats in DNA sequences

4

DISCUSSION

Using the distribution uniformity of nucleotides in DNA sequences,
we establish an ab initio method in identifying repeats and
periodicities in the DNA sequences. The distribution uniformity
intuitively depicts the level of unbalance of nucleotide frequencies
on periodic positions. The unbalance of nucleotide frequencies
determine the nature of repeats and periodicities in DNA sequences.
The method does not rely upon previously known repeat sequence
information and is natural, effective and convenient. It can
quantitatively describe a DNA repeat with NDU, consensus repeat
pattern, perfect level, and copy number.
This study shows that the periodicities of genome is contributed
by the tandem repeats of the corresponding length. For example,
a strong periodicity of length 5 is caused by large copies of 5
bp repeats. The approximate repeats render high frequencies of
nucleotides at periodic positions in DNA sequences. The consensus
repeat patterns identified by the proposed method can be considered
as the original sequences from which the approximate repeats
have been evolved in evolutionary history. The perfect level of
the approximate repeats represent the evolutionary progress. Thus
the repetitive sequences can be used in phylogenetic analysis
(Versalovic et al., 1991).
Unlike the Fourier transform method, the DU method can reveal
long harmonious periodicities, which are often missed in Fourier
transform. The DU method also directly computes the distribution
uniformity for interested periodicities, whereas Fourier transform
computes the power spectrum for frequencies, and there is no a
straightforward solution to convert it into the power spectrum for
periodicities.
Despite the efficacy in capturing repeats and the corresponding
features by the proposed method, there are some limitations that the
DU method cannot solve. One limitation is that it can not identify
interspersed repetitive elements or repeats interrupted by deletion
mutations. We will address this limitation in our future research.
The frequencies of nucleotides vary significantly across
eukaryotic genes and may present specific regulatory motifs (Louie
et al., 2003). Because the nucleotide distribution represents the
essential characteristics of a DNA sequence, the distribution
uniformities of different periodicities may have broad applications
in functional analysis of genomes.

e1002384.
Epps, J., Ying, H., Huttley, G. A., 2011. Statistical methods for detecting periodic
fragments in DNA sequence data. Biology Direct 6 (21), 1–16.
Gupta, R., Sarthi, D., Mittal, A., Singh, K., 2007. A novel signal processing measure
to identify exact and inexact tandem repeat patterns in DNA sequences. EURASIP
Journal on Bioinformatics and Systems Biology 2007, 3–3.
Hauth, A. M., Joseph, D. A., 2002. Beyond tandem repeats: complex pattern structures
and distant regions of similarity. Bioinformatics 18 (suppl 1), S31–S37.
Illingworth, C. J., Parkes, K. E., Snell, C. R., Mullineaux, P. M., Reynolds, C. A.,
2008. Criteria for confirming sequence periodicity identified by Fourier transform
analysis: application to GCR2, a candidate plant GPCR? Biophysical Chemistry
133 (1), 28–35.
Korotkov, E. V., Korotkova, M. A., Kudryashov, N. A., 2003. Information
decomposition method to analyze symbolical sequences. Physics Letters A 312 (3),
198–210.
Louie, E., Ott, J., Majewski, J., 2003. Nucleotide frequency variation across human
genes. Genome research 13 (12), 2594–2601.
McCarroll, S. A., Altshuler, D. M., 2007. Copy-number variation and association
studies of human disease. Nature genetics 39, S37–S42.
Sharma, D., Issac, B., Raghava, G., Ramaswamy, R., 2004. Spectral repeat
finder (SRF): identification of repetitive sequences using Fourier transformation.
Bioinformatics 20 (9), 1405–1412.
Suvorova, Y. M., Korotkova, M. A., Korotkov, E. V., 2014. Comparative analysis
of periodicity search methods in DNA sequences. Computational Biology and
Chemistry 53, 43–48.
Treangen, T. J., Salzberg, S. L., 2011. Repetitive DNA and next-generation sequencing:
computational challenges and solutions. Nature Reviews Genetics 13 (1), 36–46.
Versalovic, J., Koeuth, T., Lupski, R., 1991. Distribution of repetitive DNA sequences
in eubacteria and application to finerpriting of bacterial enomes. Nucleic Acids
Research 19 (24), 6823–6831.
Wang, J., Liu, G., Zhao, J., 2012. Some features of Fourier spectrum for symbolic
sequences. Numerical Mathematics A Journal of Chinese Universities (4), 341–356.
Wang, J., Yin, C., 2016. A fast algorithm for computing the Fourier spectrum of a
fractional period. arXiv preprint arXiv:1604.01589.
Yin, C., Wang, J., 2016. Periodic power spectrum with applications in detection of
latent periodicities in DNA sequences. Journal of Mathematical Biology, 1–27.
Yin, C., Yau, S. S.-T., 2005. A Fourier characteristic of coding sequences: origins and a
non-Fourier approximation. Journal of Computational Biology 12 (9), 1153–1165.
Yin, C., Yin, X., Wang, J., 2015. A novel method for comparative analysis of DNA
sequences by Ramanujan-Fourier transform. Journal of Computational Biology
21 (12), 867–879.

ACKNOWLEDGEMENT
We appreciate Professor Jiasong Wang at Department of
Mathematics, Nanjing University, China, for his mentorship and
valuable advice for this research. We are grateful to Emily Yin at
Indiana University and Tung Hoang for proof reading of the paper.

REFERENCES
Arora, R., Sethares, W. A., 2007. Detection of periodicities in gene sequences: a
maximum likelihood approach. In: Genomic Signal Processing and Statistics, 2007.
GENSIPS 2007. IEEE International Workshop on. IEEE, pp. 1–4.
Benson, G., 1999. Tandem repeats finder: a program to analyze DNA sequences.
Nucleic Acids Research 27 (2), 573.
Buchner, M., Janjarasjitt, S., 2003. Detection and visualization of tandem repeats in
DNA sequences. Signal Processing, IEEE Transactions on 51 (9), 2280–2287.
de Koning, A. J., Gu, W., Castoe, T. A., Batzer, M. A., Pollock, D. D., 2011. Repetitive
elements may comprise over two-thirds of the human genome. PLoS genetics 7 (12),

SUPPLEMENTARY MATERIALS
T HEOREM 1. The distribution uniformity of a periodicity DU (p)
is determined by the nucleotide frequencies at p−th periodic
positions fi,j , i = 1, 2, 3, 4, j = 1, 2 . . . , p, DNA length n and
periodicity length p.

DU (p) =

p
4 X
X
i=1 j=1

2
fi,j
−

n2
4p

7

Yin, C.

Proof:
DU (p) =

p
4 X
X

(fi,j −

i=1 j=1

=

p
4 X
X

2
(fi,j
−

i=1 j=1

=

p
4 X
X

p
4 X
X

p
p
4
4 X
X
n XX
n2
fi,j +
2p i=1 j=1
16p2
i=1 j=1

2
fi,j
−

n2
n
· n+
· 4p
2p
16p2

2
fi,j
−

n2
n2
+
· 4p
2p 16p2

2
fi,j
−

n2
4p

i=1 j=1

=

p
4 X
X
i=1 j=1

=

p
4 X
X
i=1 j=1

8

n2
nfi,j
+
)
2p
16p2

2
fi,j
−

i=1 j=1

=

n 2
) ·
4p

