Deoxyribonucleic acid (DNA) is a nucleic acid that contains the genetic instructions used in the development and functioning of all known living organisms and some viruses. The main role of DNA molecules is the long-term storage of information. DNA is often compared to a set of blueprints or a recipe, or a code, since it contains the instructions needed to construct other components of cells, such as proteins and RNA molecules. The DNA segments that carry this genetic information are called genes, but other DNA sequences have structural purposes, or are involved in regulating the use of this genetic information.
DNA structure can be described as DNA sequence, which can only be those consist of following four nucleotides named Adenine, Guanine, Cytosine and Thymine (We can address them A, G, C, T for simplicity). Property varies while the combination of nucleotide changes, thus even a tiny change in the chain of DNA sequence may lead to completely different appearance.
Prof. Adam C. Murphy is now working on a kind of DNA sequence that has more restrictions than ordinary ones. If a sequence’s substring matches any one of set {‘AA’, ‘CC’, ‘GG’, ‘TT’,‘AC’, ‘CA’, ‘CG’, ‘GC’, ‘GT’, ‘TG’}, the sequence is considered illegal.
Besides, an extra restriction comes: diving all the position of the sequence in groups as the sets indicate, every nucleotide must be unique in its set. For example, for given set {{1, 5, 11}, {2, 4}}, the nucleotide in position 1, 5 and 11 must be different for each pair. So is position 2 and 4.
Professor Adam C. Murphy wonders, with so many kinds of restrictions, whether a legal DNA sequence exists.