  In a recent article, Behrens and Vingron (JCB 17, 12, 2010) compute waiting
times for k-mers to appear during DNA evolution under the assumption that the
considered k-mers do not occur in the initial DNA sequence, an issue arising
when studying the evolution of regulatory DNA sequences with regard to
transcription factor (TF) binding site emergence. The mathematical analysis
underlying their computation assumes that occurrences of words under interest
do not overlap. We relax here this assumption by use of an automata approach.
In an alphabet of size 4 like the DNA alphabet, most words have no or a low
autocorrelation; therefore, globally, our results confirm those of Behrens and
Vingron. The outcome is quite different when considering highly autocorrelated
k-mers; in this case, the autocorrelation pushes down the probability of
occurrence of these k-mers at generation 1 and, consequently, increases the
waiting time for apparition of these k-mers up to 40%. An analysis of existing
TF binding sites unveils a significant proportion of k-mers exhibiting
autocorrelation. Thus, our computations based on automata greatly improve the
accuracy of predicting waiting times for the emergence of TF binding sites to
appear during DNA evolution. We do the computation in the Bernoulli or M0
model; computations in the M1 model, a Markov model of order 1, are more costly
in terms of time and memory but should produce similar results. While Behrens
and Vingron considered specifically promoters of length 1000, we extend the
results to promoters of any size; we exhibit the property that the probability
that a k-mer occurs at generation time 1 while being absent at time 0 behaves
linearly with respect to the length of the promoter, which induces a hyperbolic
behaviour of the waiting time of any k-mer with respect to the length of the
promoter.
