Bounded hairpin completion
Autor: | Florin Manea, Peter Leupold, Victor Mitrana, Masami Ito |
---|---|
Rok vydání: | 2011 |
Předmět: |
Bounded hairpin completion
Reduction (recursion theory) Hairpin completion Bounded hairpin completion distance Theoretical Computer Science Computer Science Applications Prefix Combinatorics DNA computing Formal languages Closure (mathematics) Regular language Computational Theory and Mathematics Bounded function Formal language Iterated bounded hairpin completion Suffix Word (computer architecture) Bounded hairpin reduction Mathematics Information Systems |
Zdroj: | Information and Computation. 209(3):471-485 |
ISSN: | 0890-5401 |
DOI: | 10.1016/j.ic.2010.11.014 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |