30034887
Horn Clause Computation with DNA Molecules
In this paper, we will propose Horn clause computation as an underlying computational framework of DNA computer. Horn clause program is a subclass of the formulas of first order logic and has close relation to PROLOG language. The computational power of Horn clauses was discussed in (Tärnland, 1977) and it was shown that a finite set of Horn clauses is computationally equivalent to Turing Machine. Furthermore, it should be noted that Horn programs are adequate for representing nondeterministic computation. Thus, its parallel implementation with huge number of molecules might have possibility to overcome the computational power of conventional computers. It should also be noted that the clear logical semantics of Horn programs might enable us to accept it as a higher-level programming language of DNA computer. The aim of this paper is to propose an experimental method for implementing deduction with a subclass of Horn programs, called simple Horn programs. The computational power of this model is theoretically investigated and demonstrated with some applications to NP-complete problems.
40461039
Learning local languages and its application to protein /spl alpha/-chain identification
Concerns an efficient algorithm for learning in the limit a special type of regular language called a locally testable language from positive data, and its application to identifying the protein /spl alpha/-chain region in amino acid sequences. First, we present a linear-time algorithm that, given a locally testable language, learns (identifies) its deterministic finite state automaton in the limit from only positive data. This provides a practical and efficient learning method for a specific domain of symbolic analysis. We then describe several experimental results using the learning algorithm. Following a theoretical observation which strongly suggests that a certain type of amino acid sequence can be expressed by a locally testable language, we apply the learning algorithm to identifying the protein /spl alpha/-chain region in amino acid sequences for hemoglobin. Experimental scores show an overall success rate of 95% correct identification for positive data and 96% for negative data.<<ETX>>
32287187
Sticker systems with complex structures
Abstract In this paper, we propose a variant of sticker systems which uses molecules with complex structures. Since the original sticker systems (Paun et al. (1998) [2, 8]) working on double strands of DNA have been studied as a formal model for self-assembly in DNA computing, we extend the sticker systems to working on more complex (higher-order) structures of DNA molecules. The advantage of sticker systems with complex structures is that augmented with weak codings we can obtain the characterization of recursively enumerable languages by using only sticking (hybridization) operations for complex molecules, while the usual sticker systems require more complicated operations such as the simultaneous use of couples of dominoes or coherent computations besides morphisms.
36727244
Horn Clause Computation by Self-assembly of DNA Molecules
Kobayashi proposed Horn clause computation by DNA molecules, which is more suitable for expressing complex algorithms than other models for DNA computing. This paper describes a new implementation of Horn clause computation by DNA. It employs branching DNA molecules for representing Horn clauses. As derivations are realized by self-assembly of such molecules, the implementation requires only a constant number of laboratory operations. Furthermore, it deals with firstorder Horn clauses with some restrictions. In order to realize first-order logic, we implement variable substitutions by string tiling proposed by Winfree, et al. As we show the computational power of a Horn clause program in our model, we give another proof that a polynomial number of operations using self-assembly of DNA molecules can compute any problem in NP.
38554897
Tree Adjoining Grammars for RNA Structure Prediction
In this paper, we are concerned with identifying a subclass of tree adjoining grammars (TAGs) that is suitable for the application to modeling and predicting RNA secondary structures. The goal of this paper is twofold: For the purpose of applying to the RNA secondary structure prediction problem, we first introduce a special subclass of TAGs and develop a fast parsing algorithm for the subclass, together with some of its language theoretic characterizations. Then, based on the algorithm, we develop a prediction system and demonstrate the effectiveness of the system by presenting some experimental results obtained from biological data, where free energy evaluation selection for parse trees is incorporated into the algorithm.
28066504
Multiple splicing systems and the universal computability
We propose a new extension of splicing systems, called multiple splicing systems, based on a kind of logic grammars. First, we introduce a class of Elementary formal systems, called simple H-form EFS, and show that its generative power is equivalent to the class of basic splicing systems (the original Head's splicing system) and is more adequate as representation device for formal languages. Next, we gradually extend the simple class of EFSs and get a very natural extension of splicing systems, multiple splicing systems. We show that multiple splicing systems have universal computability.
28922785
Realizability Interpretation of Generalized Inductive Definitions
Generalized inductive definitions give a way of defining a predicate as the least solution P of the equation [email protected]?A[P] where a predicate variable P may occur in a formula A[P] positively. This paper gives aq-realizability interpretation of generalized inductive definitions and proves the soundness of the interpretation.