Paper Info
Title
Bounded hairpin completion
Abstract
Hairpin completion is a formal operation inspired from biochemistry. Here we consider a restricted variant of hairpin completion called bounded hairpin completion. Applied to a word encoding a single stranded molecule x such that either a suffix or a prefix of x is complementary to a subword of x, hairpin completion produces a new word z, which is a prolongation of x to the right or to the left by annealing. Although this operation is a purely mathematical one and the biological reality is just a source of inspiration, it seems rather unrealistic to impose no restriction on the length of the prefix or suffix added by the hairpin completion. The restriction considered here concerns the length of all prefixes and suffixes that are added to the current word by hairpin completion. They cannot be longer than a given constant. Closure properties of some classes of formal languages under the non-iterated and iterated bounded hairpin completion are investigated. We consider the bounded hairpin completion distance between two words and generalize this distance to languages and discuss algorithms for computing them. Finally also the inverse operation, namely bounded hairpin reduction, as well as the set of all primitive bounded hairpin roots of a regular language are considered.
Year
DOI
Venue
2011
10.1016/j.ic.2010.11.014
Inf. Comput.
Keywords
DocType
Volume
current word,inverse operation,bounded hairpin completion distance,formal operation,hairpin completion,new word,formal language,bounded hairpin reduction,bounded hairpin completion,iterated bounded hairpin completion,dna computing,formal languages,primitive bounded hairpin root,regular language
Journal
209
Issue
ISSN
Citations 
3
Information and Computation
8
PageRank 
References 
Authors
0.59
10
4
Name
Order
Citations
PageRank
Masami Ito129966.19
Peter Leupold2244.30
Florin Manea337258.12
Victor Mitrana4950119.63