On the regularity of iterated hairpin completion of a single word

preprint2011arXivOpen access

Abstract

Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand $w = xαy \calpha$, and outputs w′=xαyαˉxˉw' = x αy \barα \bar{x}, where xˉ\bar{x} denotes the Watson-Crick complement of xx. 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 αα and $\calpha$ that initiate hairpin completion and how they are scattered, we classify the set of all words ww. For some basic classes of words ww containing small numbers of occurrences of αα and $\calpha$, we prove that the iterated hairpin completion of ww is regular. For other classes with higher numbers of occurrences of αα and $\calpha$, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.