On avoided words, absent words, and their application to biological sequence analysis

The deviation of the observed frequency of a word w from its expected frequency in a given sequence x is used to determine whether or not the word is avoided. This concept is particularly useful in DNA linguistic analysis. The value of the deviation of w, denoted by dev(w), effectively characterises the extent of a word by its edge contrast in the context in which it occurs. A word w of length k > 2 is a ρ-avoided word in x if dev(w) ≤ ρ, for a given threshold ρ < 0. Notice that such a word may be completely absent from x. Hence, computing all such words na？vely can be a very time-consuming procedure, in particular for large k