Affiliations: Department of Computer Science, The University of
Western Ontario, London, ON, N6A 5B7, Canada. E-mail:
{lila,elena}@csd.wuo.ca | Dept. of Mathematics and Computing Science, Saint
Mary's University, Halifax, Nova Scotia, B3H 3C3, Canada. E-mail:
s.konstantinidis@smu.ca | Facultad de Informática, Universidad
Politécnica de Madrid, Campus de Montegancedo s/n, Boadilla del Monte
28660, Madrid, Spain and Institute of Computer Science, Silesian University,
74601 Opava, Czech Republic. E-mail: petr.sosik@fpf.slu.cz | Department of Mathematics, The University of Western
Ontario, London, ON, N6A 5B7, Canada. E-mail: thierrin@uwo.ca
Abstract: The concept of hairpin structures in formal languages is motivated
from the biocomputing and bioinformatics fields. Hairpin (-free) DNA structures
have numerous applications to DNA computing and molecular genetics in general.
A word is called hairpin-free if it cannot be written in the form
xuyθ(u)z, with certain additional conditions, for an involution θ
(a function θ with the property that θ^2 equals
the identity function). A particular involution, the so-called Watson-Crick
involution, can characterize binding of two DNA strands. We study algebraic and decision properties, finiteness and
descriptional complexity of hairpin (-free) languages. We show an existence of
polynomial-time algorithms deciding hairpin-freeness of regular and
context-free sets. Two related DNA secondary structures are considered, taking
into the account imperfect bonds (bulges, mismatches) and multiple hairpins.
Finally, effective methods for design of long hairpin-free DNA words are
given.
Keywords: DNA computing, DNA hairpin, involution, formal language
