DNA computing, or more generally, molecular computing, is a recent development on computations using biological molecules, instead of the traditional silicon-chips. Some computational models which are based on different operations of DNA molecules have been developed by using the concept of formal language theory. The operations of DNA molecules inspire various types of formal language tools which include sticker systems, grammars and automata. Recently, the grammar counterparts of Watson-Crick automata known as Watson-Crick grammars which consist of regular, linear and context-free grammars, are defined as grammar models that generate double-stranded strings using the important feature of Watson-Crick complementarity rule. In this research, a new variant of static Watson-Crick linear grammar is introduced as an extension of static Watson-Crick regular grammar. A static Watson-Crick linear grammar is a grammar counterpart of sticker system that generates the double-stranded strings and uses rule as in linear grammar. The main result of the paper is to determine some computational properties of static Watson-Crick linear grammars. Next, the hierarchy between static Watson-Crick languages, Watson-Crick languages, Chomsky languages and families of languages generated by sticker systems are presented.
Previously, direct-proportional length-based DNA computing (DPLB-DNAC) for solving weighted graph problems has been reported. The proposed DPLB-DNAC has been successfully applied to solve the shortest path problem, which is an instance of weighted graph problems. The design and development of DPLB-DNAC is important in order to extend the capability of DNA computing for solving numerical optimization problem. According to DPLB-DNAC, after the initial pool generation, the initial solution is subjected to amplification by polymerase chain reaction and, finally, the output of the computation is visualized by gel electrophoresis. In this paper, however, we give more attention to the initial pool generation of DPLB-DNAC. For this purpose, two kinds of initial pool generation methods, which are generally used for solving weighted graph problems, are evaluated. Those methods are hybridization-ligation and parallel overlap assembly (POA). It is found that for DPLB-DNAC, POA is better than that of the hybridization-ligation method, in terms of population size, generation time, material usage, and efficiency, as supported by the results of actual experiments.
This paper presents a method to convert the deterministic, continuous representation of a biological system by ordinary differential equations into a non-deterministic, discrete membrane computation. The dynamics of the membrane computation is governed by rewrite rules operating at certain rates. That has the advantage of applying accurately to small systems, and to expressing rates of change that are determined locally, by region, but not necessary globally. Such spatial information augments the standard differentiable approach to provide a more realistic model. A biological case study of the ligand-receptor network of protein TGF-β is used to validate the effectiveness of the conversion method. It demonstrates the sense in which the behaviours and properties of the system are better preserved in the membrane computing model, suggesting that the proposed conversion method may prove useful for biological systems in particular.
Despite an exponential increase in computing power over the past decades, present information technology falls far short of expectations in areas such as cognitive systems and micro robotics. Organisms demonstrate that it is possible to implement information processing in a radically different way from what we have available in present technology, and that there are clear advantages from the perspective of power consumption, integration density, and real-time processing of ambiguous data. Accordingly, the question whether the current silicon substrate and associated computing paradigm is the most suitable approach to all types of computation has come to the fore. Macromolecular materials, so successfully employed by nature, possess uniquely promising properties as an alternate substrate for information processing. The two key features of macromolecules are their conformational dynamics and their self-assembly capabilities. The purposeful design of macromolecules capable of exploiting these features has proven to be a challenge, however, for some groups of molecules it is increasingly practicable. We here introduce an algorithm capable of designing groups self-assembling of nucleic acid molecules with multiple conformational states. Evaluation using natural and artificially designed nucleic acid molecules favours this algorithm significantly, as compared to the probabilistic approach. Furthermore, the thermodynamic properties of the generated candidates are within the same approximation as the customised trans-acting switching molecules reported in the laboratory.