  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.

Genomics