Paper Info
Title
On hairpin-free words and languages
Abstract
The paper examines the concept of hairpin-free words 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 xvyθ (v)z, with certain additional conditions, for an involution θ (a function θ with the property that θ2 equals the identity function). We consider three involutions relevant to DNA computing: a) the mirror image function, b) the DNA complementarity function over the DNA alphabet {A,C,G,T} which associates A with T and C with G, and c) the Watson-Crick involution which is the composition of the previous two. We study elementary properties and finiteness of hairpin (-free) languages w.r.t. the involutions a) and c). Maximal length of hairpin-free words is also examined. Finally, descriptional complexity of maximal hairpin-free languages is determined.
Year
DOI
Venue
2005
10.1007/11505877_26
Developments in Language Theory
Keywords
Field
DocType
dna complementarity function,dna structure,dna computing,dna alphabet,hairpin-free word,watson-crick involution,languages w,maximal hairpin-free language,identity function,mirror image function,finite automaton,molecular genetics
Identity function,Complementarity (molecular biology),Discrete mathematics,Combinatorics,Finite-state machine,DNA,Involution (mathematics),Mathematics,Alphabet,DNA computing
Conference
Volume
ISSN
ISBN
3572
0302-9743
3-540-26546-5
Citations 
PageRank 
References 
14
1.54
9
Authors
4
Name
Order
Citations
PageRank
Lila Kari11123124.45
Stavros Konstantinidis228331.10
Petr Sosík347968.66
Gabriel Thierrin426334.89