Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

2 2006

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Block Substitutions and Their Properties

Kari L., Losseva E.

Fundamenta Informaticae

2006

Vol. 73, nr 1-2

165-178

We introduce a type of substitution operation inspired by errors occurring in biologically encoded information. We derive the closure properties of language families in the Chomsky hierarchy under these substitution operations. Moreover, we consider some language equations involving these operations and investigate decidability of the existence of solutions to such equations.

A Formal Language Analysis of DNA Hairpin Structures

Kari L., Losseva E., Konstantindis S., Sosik P., Thierrin G.

Fundamenta Informaticae

2006

Vol. 71, nr 4

453-475

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 xvyq(v)z, with certain additional conditions, for an involution q (a function q with the property that q2 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.