Necklaces, MSS Sequences, and DNA Sequences

Based on a unified approach via the classical Burnside Lemma in combinatorics, we deal with some problems arising from symbolic dynamics and biology. The MSS sequences play an important role in symbolic dynamics, and they are in one-to-one correspondence with necklaces of beads with two colors. This...

Full description

Saved in:
Bibliographic Details
Published in:Advances in applied mathematics 1997-01, Vol.18 (1), p.18-32
Main Authors: Chen, William Y.C., Louck, James D.
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Data processing. List processing. Character string processing
Exact sciences and technology
Language theory and syntactical analysis
Memory organisation. Data processing
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Based on a unified approach via the classical Burnside Lemma in combinatorics, we deal with some problems arising from symbolic dynamics and biology. The MSS sequences play an important role in symbolic dynamics, and they are in one-to-one correspondence with necklaces of beads with two colors. This necklace problem was studied by Fine, Gilbert, and Riordan in the 1950s and 1960s. Recently, a problem on the classification of the DNA sequence arose in biology and was studied by Bell, Torney, and others. In this paper, we present a further treatment of the necklace problem which shows a closer connection with MSS sequences and brings more combinatorial insight into the properties of symbolic dynamics. We also give a clear derivation of the formula for the classification of DNA sequences. The techniques used in this paper originate principally from properties of cycle structures, which are related to the fixed points of then-cube recently studied by Chen and Stanley.
ISSN:0196-8858
1090-2074
DOI:10.1006/aama.1996.0494