【作 者】Konstantinidis, S.Losseva, E.Thierrin, G.Kari, L.Sosík, P.
【作者单位】1 Department of Computer Science, The University of Western Ontario, London, ON, N6A 5B7, Canada 2 Facultad de Informática, Universidad Politécnica de Madrid, Campus de Montegancedo s/n, Boadilla del Monte 28660, Madrid, Spain 3 Institute of Computer Science, Silesian University, 74601 Opava, Czech Republic 4 Dept. of Mathematics and Computing Science, Saint Mary's University, Halifax, Nova Scotia, B3H 3C3, Canada 5 Department of Mathematics, The University of Western Ontario, London, ON, N6A 5B7, Canada
【摘 要】 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... 更多 >> 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. [ABSTRACT FROM AUTHOR] << 收起
