On the Regularity of Iterated Hairpin Completion of a Single Word
Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = x alpha y (alpha) over bar, and outputs w ' = x alpha y (alpha) over bar(x) over bar, where (x) over bar denotes the Watson-Crick complement of x. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words alpha and (alpha) over bar that initiate hairpin completion and how they are scattered, we classify the set of all words w. For some basic classes of words w containing small numbers of occurrences of alpha and (alpha) over bar, we prove that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of alpha and (alpha) over bar, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.
iterated hairpin completion combinatorics on words commutativity of words dna computing regularity test single-primer hairpin completion