Properties of words on four letters from those on two letters with an application to DNA sequences (Q1312842)

The rapid growth of DNA-sequence databases in the last few years makes it increasingly possible to identify biologically interesting sequence motifs by mathematical and statistical methods. Some special patterns, the tandem repeats of short sequence fragments, deserve great attention in the DNA sequence analysis. The article starts with the definition of an equivalence class consisting of a repeated word, all of its cyclic permutations, together with the reverse complements of each. In connection with such a construction the authors put the question: How many equivalence classes are there and how can they be characterised? Results already found for two letter words are used to infer certain properties of words on four letters. By a surjective mapping \(\varphi\) each letter \(A,C,G,T\) in DNA sequences is replaced by a pair of letters, say \(A \to RL\), \(C \to RR\), \(G \to LR\), \(T \to LL\). As a main result it is shown how a set of cycle class labels for words of length \(n\) on four letters can be constructed from the analogue on two letters using the bijection \(\varphi\). It is shown that the Möbius formulas for \(k = 2\) and \(k = 4\) give the number of cycle classes into which a set of primitive words is partitioned under conjugacy.