NECKLACES, MSS SEQUENCES, AND DNA-SEQUENCES

Based on a unified approach via the classical Burnside Lemma in combin atorics, we deal with some problems arising from symbolic dynamics and biology. The MSS sequences play an important role in symbolic dynamic s, and they ale in one-to-one correspondence with necklaces of beads w ith two colors. This necklace problem was studied by Fine, Gilbert, an d Riordan in the 1950s and 1960s. Recently, a problem on the classific ation of the DNA sequence arose in biology and was studied by Bell, To rney, and others. In this paper, we present a further treatment of the necklace problem which shows a closer connection with MSS sequences a nd brings more combinatorial insight into the properties of symbolic d ynamics. We also give a clear derivation of the formula for the classi fication of DNA sequences. The techniques used in this paper originate principally from properties of cycle structures, which are related to the fixed points of the n-cube recently studied by Chen and Stanley. (C) 1997 Academic Press.