Properties of Words on Four Letters from Those on Two Letters with an Application to DNA Sequences

AbstractThe problem of classifying words on four letters into equivalence classes under the operations of conjugacy and reverse complementation is solved by using a surjective mapping to words on two letters of even length. This classification problem for words on four letters arises in the study of DNA sequences. For words on two letters the concept of a lexical word, which is based on a total order relation, allows one to assign a distinguished word to each conjugacy class. The mapping between words on four letters and those on two letters is used to assign a distinguished word to the conjugacy classes of words on four letters. The Möbius inversion formulas are basic to this enumeration problem