{'fraction_non_alphanumeric': 0.04843205574912892, 'fraction_numerical': 0.028842431281455673, 'mean_word_length': 4.573031283710895, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantifying Local Randomness in Human DNA and RNA Sequences Using Erdos Motifs

In 1932, Paul Erdos asked whether a random walk constructed from a binary sequence can achieve the lowest possible deviation (lowest discrepancy), for the sequence itself and for all its subsequences formed by homogeneous arithmetic progressions. Although avoiding low discrepancy is impossible for infinite sequences, as recently proven by Terence Tao, attempts were made to construct such sequences with finite lengths. We recognize that such constructed sequences (we call these"Erdos sequences") exhibit certain hallmarks of randomness at the local level: they show roughly equal frequencies of subsequences, and at the same time exclude the trivial periodic patterns. For the human DNA we examine the frequency of a set of Erdos motifs of length-10 using three nucleotides-to-binary mappings. The particular length-10 Erdos sequence is derived by the length-11 Mathias sequence and is identical with the first 10 digits of the Thue-Morse sequence, underscoring the fact that both are deficient in periodicities. Our calculations indicate that: (1) the purine (A and G)/pyridimine (C and T) based Erdos motifs are greatly underrepresented in the human genome, (2) the strong(G and C)/weak(A and T) based Erdos motifs are slightly overrepresented, (3) the densities of the two are negatively correlated, (4) the Erdos motifs based on all three mappings being combined are slightly underrepresented, and (5) the strong/weak based Erdos motifs are greatly overrepresented in the human messenger RNA sequences.

Given our knowledge of these evolutionary processes, one might imagine a project to computationally simulate the DNA sequence changes (e.g. (Li, 1992;Koroteev and Miller, 2011)).
However, there is a tremendous challenge in choosing the correct model parameter values (Li, 2011), in modelling the natural selection (Bustamante et al., 2005), in putting the model in the context of diploid with recombination (Duret and Arndt, 2008), and in a population (Hartl and Clark, 1997). Point mutations lead to lesser destruction of the genome than largerscale changes, thus are more likely to survive to the next generation. Many point mutations manifest as neutral mutations (Kimura, 1983). If the point mutations dominate, the DNA sequences would become more and more random.
There has been a debate on whether DNA sequences from the human genome should be considered to be random (IHGSC, 2001;Clay and Bernardi, 2001;Li et al., 2002). If the DNA sequence from a complete chromosome is examined from one end to another, everybody agrees it is not consistent with independent and identically distributed (iid) random variables (Bernardi, 2001). It was known that genome contains large domains with alternating high and low GC content called isochores (Bernardi et al., 1985). Spectral analysis also confirmed that genome sequences are not white noise (Voss, 1992;Holste, 2004, 2005). For coding regions including the regulatory sites, codon structures as well as gene structure often cause the DNA sequences to be non-random (Mani, 1992;Almirantis, 1999;Nikolaou and Almirantis, 2002;Hackenberg et al., 2012;Cocho et al., 2014). However, such debate has not really reached a consensus at the local level in non-coding, non-functional regions. Part of the reason is that randomness definitions are mostly based on probability models of infinitely long sequences, and corresponding definitions for finite sequences are not universally adopted.
Defining randomness in a sequence is not easy (Knuth, 1997). On the one hand, for a sequence of infinite length, being random implies "any motif can appear". This includes the series composed of the same symbol of arbitrary length, which by itself can not be considered as random. On the other hand, for a finite sequence, the intuitive notion of being random is that all symbols, dimers, triplets, etc. appear with equal frequency. However, a periodic sequence would also satisfy this requirement, which nevertheless is hardly considered to be random.
In the field of mathematics, a discussion concerning the Erdös discrepancy problem (Erdös, 1957) seems to provide a foundation of randomness in finite sequences. Given an infinite binary sequence {x i }, taking values x i = (−1, 1), we define the discrepancy function for the sequence up to the length L, of an integer spacing d: In other words, D(d, L) is the cumulative sum of the subsequence sampled from every d positions, starting from the position d, of the length-L window. Erdös asked the question: given any constant C, can one find a sequence of length L and a spacing value d so that for one value of spacing d. The problem is solved by Terence Tao, and the answer is yes (Tao, 2016;Soundararajan, 2018), no matter how large the value of C, one can always find the above defined sum larger than C for certain spacing d value, at a particular length L.
When d = 1, | k=L i=1 x i | is just the cumulative function of a (random) walk whose steps are given by the {x i } series. In order for the Erdös question to have the negative answer, one should design steps to be as close to the origin as possible. A periodic walk of period 2 with alternating positive and negative steps is the best solution. However, this solution is unstable in the sense that as soon as one changes the d value to 2, | k≤L/2 i=1 x 2i | diverges. Therefore, allowing d to be different from 1, or, allowing one to sample other subsequences in {x j=id } (i = 1, 2, 3, · · · ) of spacing d (called "homogeneous arithmetic progression"), is a solution to exclude periodic sequences from "low discrepancy" (low cumulative value for the random walk) category, while "low discrepancy" is one essential concept in our definition of randomness.
We can reverse the Erdös question to design a finite sequence which has the "lowest possible discrepancy" but exclude periodic sequence, for a given C value. Such designed sequence exhibits the hallmark of a locally random sequence: uniform distribution of single symbol and low-order tuples. It has been shown that there is a length-11 sequence which has the lowest possible discrepancy, not larger than C=1 for any d values (Mathias, 1993). All other sequences with longer lengths would lead to discrepancy larger than 1. Similarly, for C = 2, a length-1160 sequence is able to limit its discrepancy to equal or less than 2 for any d (Konev and Lisitsa, 2014), but once the length is extended to 1161, discrepancy can increase above 2. We call these designed finite series "Erdös sequences with the limit of C and of length L" (E C,L ). E C,L is our candidate of a locally random string at the corresponding string length.
In this work, we will show that the length-11 sequence constructed by Mathias is not unique, whereas there exists a unique sequence with the required low-discrepancy feature at length 10.
We focus on this length-10 sequence (E 1,10 ) and translate it to 10-mers in the DNA sequence of the human genome. The length of 10 is particularly appealing as the DNA double helix makes one complete turn after approximately 10 base-pairs (spacing between two ladder steps is 0.34 nm, and one helix turn is 3.4 nm) (Calladine et al., 2004). We will use the human genome to examine the distribution of DNA substrings of length 10 which are consistent with the E 1,10 sequence. The goal of this investigation is to examine whether the human genome tends to possess these "low discrepancy", "locally random" sequences.
In the next section, we review the previously studied Mathias E 1,11 sequence and propose the unique low discrepancy E 1,10 sequence. We translate the Erdös E 1,10 motif to DNA sequences, using different base pair definitions. In section 3, the result section, we present the observed and expected E 1,10 values obtained from the human genome, and apply the same analysis to genomic sequences windowed by 1Mb windows to study its frequency at the local level. Then, the presence of E 1,10 sequences in particular functional DNA units and mRNA is discussed.
In the Discussion and conclusions section, the results are recapitulated and open problems are proposed, in particular the relation of E 1,10 and Thue-Morse sequences, and the relevance of Kolmogorov complexity in defining locally random motifs. In the Appendix comparison of the 2 Erdös sequences 2.1 The unique length-10 Erdös sequence with binary symbols The E 1,11 derived in (Mathias, 1993) is + --+ -+ + --+ + , which is called the "Mathias sequence". Fig.1 illustrates why it satisfies Erdös' low discrepancy requirement: the sum of x id | for d=1,2,3,4,5 is always bounded by 1. If a 12th value is added to the sequence, it can not be +, as there would be three +'s in a row. If it is "-", the deviation would be larger than C=1 for d=3. Note that | i<12/d i=1 x 1+(i−1)d | has huge discrepancy for d = 3, reminding us that arithmetic progression has to start from position d.
Also note that if an Erdös sequence reverses its direction, it may not be an Erdös sequence anymore. There could be two different causes. Take the first 7 positions of E 1,11 for example ( Fig.1): in the forward direction, the discrepancy series is (position 0 is also included): (0, 1,0, -1, 0, -1, 0, 1). In the backward direction, the discrepancy series is not a reverse of the above, but (0, 1,2,1,2,1,0,1). The two walks are mirror image of each other with respect to 0.5. Only when the forward walk ends up at discrepancy of zero value, would the two walks be mirror image of each other with respect to 0, and the backward sequence to be also a Erdös sequence. The second cause is about "phase". Since for d > 1, the subsequence selected starts from the position i = d, forward and backward sequence may select different subsequences, thus potentially different discrepancy series.
We can see that E 1,11 has a balanced single symbol frequencies (f(+)=6/11, f(-)=5/11), and almost balanced dimer frequencies (f(--)=2/10, f(-+)=3/10, f(+-)=3/10, f(++)=2/10). At the same time, E 1,11 is mostly not periodic. Interestingly, when a sequence contains any kmer exactly once (called De Bruijn sequence (De Bruijn, 1946, 1975, its k-mer frequency is exactly balanced. There are attempts to design shortest sequences to contain all k-mers in both direct and reverse direction of DNA sequences (Orenstein and Shamir, 2013). Again, to be the shortest means to contain any k-mer only once, therefore resulting to a balanced k-mer frequencies. We do not expect Erdös sequence to have a balanced k-mers frequencies when k is large, as the presence of the all-1 or all-0 k-mers will lead to a large discrepancy for d = 1. However, for k's being less, equal, or close to C, we may hypothesize balanced k-mer frequencies in Erdös sequences.
It is not difficult to check that there is another sequence + --+ -+ + --+ -, denoted E ′ 1,11 , with the last symbol changed from + to -, which is also an Erdös sequence. It is because 11 is a prime number and changing the last symbol only affects the discrepancy for d = 1, changing the final cumulative value from 1 to -1. Swap + and -would not change any of the discrepancy values. Running through all possible length-11 binary sequences, we observed that Mathias' E 1,11 and E ′ 1,11 (plus the two derived from swapping the binary symbols) are the only Erdös sequences at C = 1.
Further simulations show that E 1,L is unique when L ≤ 10 is even, and not unique when L ≤ 11 is odd, all with a degeneracy at the last symbol (can be either + or -). E 1,L does not exist when L > 11. In the following, we focus on the unique Erdös sequence with the maximum length, E 1,10 , and its frequency of appearance in the human genome.
2.2 DNA motifs of length 10 bases which are associated with E 1,10 Erdös sequence DNA sequences use four symbols (A,C,G,T). There are three different ways to split the four symbols into two groups: (a) R/Y binarization combines AG (R for purine) and CT (Y for pyrimidine), (b) W/S binarization combines AT (W for weak) and CG (S for strong), (c) K/M binarization combines GT (K for keto) and AC (M for amino). The W/S binarization characterizes the binding strength between the two DNA strands (G and C bind more strongly), and GC-content is an experimentally measurable quantity (Schildkraut et al., 1962) which is widely studied in genomic analysis (Li, 2013). The R/Y binarization highlights the size difference of the two types of bases (A and G are larger in size), and has been proposed to be relevant to codon patterns (Shepherd, 1981), regulatory sequence patterns (Christophe et al., 1985), and the double helix structure (Arnott et al., 1974). The last binarization (M/K) is rarely used. The fact that the DNA molecule has the form of a double helix implies that we must examine two strands for Erdös motifs, the direct strand, and the reverse complement strand.
(a) For R/Y binarization, four sequences are associated with E 1,10 , considering both the direct DNA sequence and its reverse complement sequence on the opposite strand: In terms of the four nucleotide symbols, each motif represents 2 10 = 1024 4-symbol patterns.
Multiplying by 12, and subtracting 48 = 16 × 3 10-mers which belong to more than one type of motifs (e.g. ACCACAACCA is either a RY or a WS motif), we are dealing with 12240 10-mers which are associated with the Erdös sequence E 1,10 in either one of the strands.
3 Distribution of Erdös sequences in the human genome

DNA sequence data
In this study, the sequence of human reference genome hg38 is used, which is downloaded from UCSC Genome Browser http://hgdownload.soe.ucsc.edu/goldenPath/hg38/chromosomes/.
We use chromosomes 1,2, · · · 22, and chromosome X but we exclude chromosome Y due to large amount of non-sequenced regions. The 23 sequences contain RepeatMasker filtering information: lowercase letters represent regions that match transposons or other repetitive or low-complexity sequences, whereas uppercase letters represent unique sequences.
The messenger RNA (mRNA) sequence of "known genes" (last updated in July 2016) is ob- the last bands of a chromosome is considered to be the telomere regions. We first use the same file to bracket the centromere region (when the band is labeled as "acen"). Then we further fine-tune the boundary by an observation made in (Thanos et al., 2018) that windowed statistical qualities (e.g. entropy) have extremely low variations in the centromere region.

Distribution of Erdös sequences in the human genome at the chromosome level
For R/Y binarization, out of 2.911 billions overlapping 10-mers in the human genome (chromosomes 1-22,X, excluding any 10-mers which contain unsequenced bases) there are 6,161,338 counts of R/Y E 1,10 , or 0.21% of all 10-mer counts. The ratio between R/Y E 1,10 and non-R/Y-E 1,10 sequence counts is 1:471. This frequency is severely underrepresented as the expected frequency is 0.39% if the strand symmetry holds true (see Appendix, from both analytic formula and simulation results). The observed over expected ratio (O/E) is 0.54, or equivalently 1/1.85. On individual chromosomes, the R/Y observed frequency of E 1,10 compatible 10-mers is also much lower than those in sequences generated randomly using the observed base composition (see Appendix).
For W/S E 1,10 , there are 10,073,985 copies of them in the human genome (0.35%). For each W/S E 1,10 , there are 288 10-mers that are not E 1,10 compatible. This frequency is slightly higher than the expected value of 0.32% (O/E=1.05), if we make a simple assumption that the GC-content is 40% (see Appendix). The 40% value is a good approximation for global GCcontent (Li, 2013). Even if we use the observed GC-content at the individual chromosome, the conclusion remains true that the frequency is slightly higher than expected (except for chromosomes 16 and 19) (see Appendix).
Finally, there are 8,782,253 copies of M/K based E 1,10 (0.3%), slightly lower than expected (0.39%, assuming strand symmetry). There are more W/S or M/K E 1,10 than R/Y E 1,10 , even though R/Y E 1,10 is expected to appear more often than W/S E 1,10 , and equally likely as M/K E 1,10 . Combining the three types of E 1,10 , there are in total 24,692,591 copies of 10-mer motifs associated with E 1,10 . This number is slightly lower than the sum of the three counts for R/Y, W/S, and K/M based E 1,10 because some 10-mers belong to more than one type.
There are other nucleosome positioning sequence patterns proposed, in particular, the period-  Notably, the rate of W/S based Erdös sequence is positively correlated with the GC-content, and the frequency of R/Y based Erdös sequence is positively correlated with the chromosome length.
For completeness, we also show the correlation among the frequencies of various sequence features in Table 1(c). Interestingly (and perhaps counter-intuitively), both the polyA/polyT density and polyC/polyC density (which is very low) are positively correlated with the GCcontent. Fig.2 highlights a few strong correlations: negative correlation between two types of Erdös E 1,10 's, positive correlation between R/Y based E 1,10 and sequence length, negative correlation between R/Y based E 1,10 and GC-content, and positive correlation between polyA/polyT density and GC-content. Other large (in absolute value) and significant correlations are marked as bold in Table 1.  Fig.3), including the negative correlation between R/Y based and W/S (and K/M based) Erdös sequence frequency, the negative (positive) correlation between R/Y (W/S and overall) Erdös sequence frequency and GC-content, the positive correlation between polyA/polyT and GC-content, etc. The scatter plots in Fig.3 also show the existence of outliers which are all from centromere regions. It also shows that the positive correlation between polyA/polyT and GC-content coexist with a larger variance for polyA/polyT at GC-rich regions (see Fig.3(d)). The statistical test results in Table 2 are all more significant than the corresponding ones in Table 1, as the sample size is increased from the 23 chromosomes to 2755 1Mb windows. In (Li et al., 2013) it was observed that the R5Y5 density is negatively correlated with that of the transposon and other repetitive sequences at 64kb window level. Table 2 shows that this conclusion remains true at the 1Mb window level (positive correlation between R5Y5 density and unique sequence density).

Frequency of Erdös motifs in various functional, regional, sequence-feature classes
Besides counting Erdös motifs in the whole genome, we also count them in sequences belonging to specially defined sub-categories. The first subcategory consists of the genome free   For W/S based Erdös motifs, most observed frequencies are consistent or slightly higher than the expected (Fig.4), except for mRNA sequences. We hypothesize that it might be related to a "hidden" periodicity in the E 1,10 sequence. If we examine the E 1,10 sequence closely in Fig.1 The reason that this local periodicity evades the attention in the mathematics community in the discussion of Erdös problem is that the homogeneous arithmetic progression requires the step-d walk to start from position d. When d = 3, this requirement forces the walk to start from the third reading frame, not the first or the second reading (see Fig.1). Since mRNA sequences contain periodicity-three signals, it is not unreasonable to speculate that it is a possible cause of the Erdös sequence enrichment. In addition, mRNAs contain specific motifs of codons; these may also be mirrored in the Erdös sequences and thus contribute further in the observed enrichment of W/S-Erdös motifs.
Finally, adding the three types of Erdös frequency together, for both expected and observed sequences, we see in Fig.4 a pattern of underrepresentation (with the exception of mRNA). This underrepresentation, generally speaking, supports the idea that the human DNA sequences are not locally random.
ognizing the nearest neighbor correlations (Swartz et al., 1962) to the detection of long-range correlations (Li and Kaneko, 1992;Peng et al., 1992;Voss, 1992). The debate on whether the human genome sequences are homogeneous, iid (independent and identically distributed), random (IHGSC, 2001;Clay and Bernardi, 2001;Li et al., 2002) is often based on concepts defined on infinitely long sequences. There is always a lack of adequate concepts related to randomness on finite scales. In this study, our aim is to consider a type of low-discrepancy sequences, called Erdös sequences E C,L , and perhaps their generalization, as candidates for locally random sequences.
The underrepresentation of overall E 1,10 compatible motifs in the human genome (Fig.4) can be interpreted as a lack of locally random sequences. This is particularly true for R/Y based E 1,10 10-mers. Interestingly, it was observed that long-range correlation scaling is best observed in the R/Y binarization (Peng et al., 1992). The surprising overrepresentation of W/S based E 1,10 10-mers in mRNA sequences might reflect, among others, a potentially periodicity-3 tendency in certain reading frames in this sequence. Further investigation is required to pinpoint the cause of the overrepresentation.
The underrepresentation of R/Y based E 1,10 is not a consequence of lower or higher R content, or equivalently, a violation of Chargaff's second parity. Indeed, if R% is too high or too low, other R/Y-based 10-mers may become the most frequent motifs, such as R-track or Y-track (Almirantis and Provata, 1997). However, Chargaff's rule is well preserved both at the chromosomal and at the 1Mb window levels (result not shown). Furthermore, we observed that among R/Y based 10-mers with R%=Y%, the Erdös motifs are still underrepresented (result not shown).
The key component in an Erdös sequence is its low discrepancy, either in the direct cumulative plot or in many of its equally spaced subsequences. The cumulative plot or (random) walk representation has been frequently used in DNA sequences (Berthelsen et al., 1992;Peng et al., 1992;Zhang and Zhang, 1994), but the inclusion of equally spaced subsequences is an ingenious device to exclude periodic sequences. An open question is how low discrepancy property fits other hallmarks of local randomness.
Using a semi-periodic pattern to reduce discrepancy while at the same time to avoid exact periodicity may have other applications in sequence analysis. For example, it is well known that in the promoter region of housekeeping genes, CpG dinucleotide is common, forming CpG islands (Vinson and Chatterjee, 2012). However, they can not be arranged in a periodic fashion. When they appear in a periodic arrangement of CGG repeats with more than 200 copies in gene FMR1, it leads to a form of intellectual disability (Park et al., 2015).
Another property of local randomness is the difficulty in recreating the sequence. This property makes randomness equivalent to a measure of complexity (Li, 1991). The use of Kolmogorov complexity as a way to measure local randomness is an involved topic (Allouche, 1999;Vitányi, 2001;Li and Vitányi, 2009;Soler-Toscano et al., 2014) and will not be addressed here. However, compressibility based calculation can be easily carried out (Ziv and Lempel, 1977;Benedetto et al., 2002;Estevez-Rams et al., 2013). Preliminary calculations indicate that E 1,10 belong to a harder-to-compress group, but not the hardest-to-compress (results not shown).
In conclusion, the search for low discrepancy sequences in the human DNA has shown that these motifs are overall underrepresented (except for some particular cases). This results is consistent with nonrandomness at the local scale. In future studies, it would be interesting to extend this search into the full 4-letter alphabet scheme, Erdös sequences of longer sizes, both of which require considerably more involved computational effort, as well as extending low discrepancy property to all reading frames. Knowing that DNA sequences are not homogeneous, but are composed by sub-regions (isochores, genes, etc.), it would be interesting to quest whether these inhomogeneities are also mirrored locally following the randomness criteria as posed by the Erdös problem.
Appendix: estimation of the E 1,10 frequencies in random sequences If each symbol appears with equal probability, the expected E 1,10 frequency can be estimated by counting the number of 4-symbol sequences matching E 1,10 of the total number of possible 10-mers. There are 4 motifs in Eq.
We also ran a simulation to generate artificial chromosomes with the same base composition as the real human chromosomes, but bases are scrambled. The numbers of R/Y and W/S based Erdös sequence E 1,10 in the simulated artificial chromosomes are shown in Table A1 (column "exp(simu)". These can be compared to the estimated from the formula ("exp(form)"). These two columns match very well. In comparison, the observed numbers of     x id | at any j (for d=1, 2, 3, 4, 5) is shown. When the 12th value is −1, the cumulative sum is larger than 1 (in absolute value) for d=3. If the 12th value is +1 (not shown), it would lead to the cumulative sum larger than 1 for d=1,2.  Figure 4: Comparison of the observed Erdös sequence frequency (y-axis) and the expected (x-axis). The letter labeling the dots indicates the type: r for R/Y based, w for W/S based, k for K/M based E 1,10 , "a" is the sum of the three. The color indicates the source of the sequences: whole genome, non-transposon-nonrepetitive unique sequences (green), mRNA sequences (blue), gene sequences (grey), centromere (red) and telomere (yellow) sequences. The expected frequency is based on the product of single symbol frequencies obtained from the examined sequence.    Table 1 is no longer a variable here.