Name
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. |
Year | Venue | Keywords |
|---|---|---|
2006 | Fundam. Inform. | formal language analysis,hairpin structure,so-called watson-crick involution,long hairpin-free dna word,dna structure,dna computing,multiple hairpin,identity function,dna hairpin structures,related dna,dna strand,particular involution,involution,formal language,formal languages |
Field | DocType | Volume |
Identity function,Discrete mathematics,Formal language,Algebraic number,Imperfect,DNA,Involution (mathematics),Mathematics,DNA computing | Journal | 71 |
Issue | ISSN | Citations |
4 | 0169-2968 | 14 |
PageRank | References | Authors |
0.90 | 10 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| L. Kari | 1 | 21 | 1.79 |
| E. Losseva | 2 | 14 | 0.90 |
| S. Konstantinidis | 3 | 26 | 2.81 |
| P. Sosik | 4 | 33 | 3.82 |
| G. Thierrin | 5 | 68 | 10.18 |