Chinese Journal of Computers   Full Text
Title	A Biomolecular Computing Model in Vivo for Minimum Dominating Set Problem
Authors	LIU Xiang-Rong1),2) WANG Shu-Dong3) XI Fang1) CHEN Mei1)
Address	1)(Institute of Software, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871) 2)(Department of Computer Science, School of Information Science and Technology, Xiamen University, Xiamen, Fujian 361005) 3)(College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong 266510)
Year	2009
Issue	No.12(2325—2331)
Abstract &   Background	Abstract Biomolecular computing models in vivo are an emerging computing model inspired from the biological phenomena that the biochemical molecular in living perform computation, communications, and signal processing collaboratively. In this paper, a biomolecular computing model in vivo for minimum dominating set problem is presented, a synthetic gene network is constructed by RNAi and lactose operon in living cell. This model explores further the ability to solve hard problems based on organism processing signal，and try to construct an intelligent molecule machine in cell. It may be widely and further used in computing science, biology, and medicine. Keywords biomolecular computing in vivo; gene network; RNA interference; minimum dominating set problem Background Computation is a map or a transform process of symbol strings based on the rules. Symbol is the special physics state. It can be the electronic circuit behavior based on transistor technology. The machine is successfully realized by digital computer with a vast number of states. If the interaction between the bimolecular can be viewed as a finite number of components and the components can take on a few states. The particular biochemical reaction is biomolecular computing. In 1994, Adleman was the first to demonstrate by a DNA experiment for solving a small instance of traveling salesman problem that biomolecular computations are feasible.Features such as the massive parallelism are very interesting from the computational point of view. A number of experiments solving hard computational problems have been presented.Researchers realized some of the obstacles related to this incipient technology soon thereafter, efficiency and precision of biochemical reaction, and exponential explosion of solution space with respect to problem size. Therefore, progress in biomolecular computing will depend on both novel computing concepts and biological operation technique. The goal of researchers is to find biomolecular computing paradigms capable more than Turing machines, or a new application platform. The architecture of gene regulatory networks is reminiscent of electronic circuits. Increasing knowledge on how cell behavior is shaped by the complex regulatory transcription networks of different sets of genes, which show response characteristics as electric circuits. Precise and programmed control of gene activity can be accomplished by incorporating synthetic biochemical logic circuits into the cells. Such biochemical circuits perform a variety of simple computational tasks including amplification, integration and information storage. Bacterial illustrates other common features of biomolecular computing in vivo, such as their ability to integrate multiple inputs. Plasmid is a circular, double-stranded DNA molecular, which contain an origin for replication and allows the production in bacteria. A method of computing using DNA plasmids is introduced by Head in 2000. It illustrated by reporting a laboratory computation of an instance of the NP-complete algorithmic problem of computing the cardinal number of a maximal independent subset of the vertex set of a graph. Henkel extended plasmid computing with protein expression by the construction of the whole computing region of a plasmid as part of an open reading frame. In 2007, several instances of knapsack problems using plasmids were presented. Finite state automata operating autonomously at the molecular scale can be sued conceptually for applications in the living cell. Shapiro built a small finite state automaton from DNA strands and enzymes. This approach might be applied in vivo to biochemical sensing, genetic engineering and even medical diagnosis and treatment. The first autonomous finite state machine working in a living cell was proposed by Sakakibara and Coworkers. Genetic circuits are collections of basic elements that interact to produce a particular behavior．By constructing biochemical logic circuits and embedding them in cells, one can extend or modify the behavior of cells. To date, several small synthetic gene networks have been built that accomplish specific genetic regulatory functions in vivo. The auto regulatory is a repressor regulates its own production to reduce noise in gene expression. Savageau proposed but not demonstrated that the negative feedback loops in gene circuits provide stability. Becskei and Serrano have designed and constructed simple gene circuits consisting of a regulator and transcriptional repressor modules in Escherichia coli and show the gain of stability produced by negative feedback. To test the role of negative feedback in the stability of gene networks, they first designed simple gene circuits based on simple control systems. Gardner presented the construction of a genetic toggle switch, a synthetic, bistable gene-regulatory network, in Escherichia coli and provided a simple theory that predicts the conditions necessary for bistability. The toggle is constructed from any two repressible promoters arranged in a mutually inhibitory network. Elowitz present the design and construction of a synthetic network to implement a particular function, three transcriptional repressor systems that are not part of any natural biological clock to build an oscillating network in Escherichia coli. To overcome the shortcoming and challenge for the design and construction of more sophisticated genetic circuitry in the future. A combined rational and evolutionary design strategy for constructing genetic regulatory circuits proposed. Weiss presented a genetic component library and a gene circuit design methodology for assembling these components into compound circuits. In 2004, Kramer pioneer a variety of different two- and three-input biologic gates in mammalian cells by combining several compatible heterogonous gene control units responsive to tetracycline, streptogramin, macrolide, and butyrolactoes. In 2007, Weiss and Benenson used RNA interference (RNAi) in human kidney cells to construct a molecular computing core that implements general Boolean logic to make decisions based on endogenous molecular inputs. Computational gene model, a molecular finite state machine which can be implemented in molecular diagnostic and therapy of disease. Here the authors propose a theoretics model in vivo for minimum dominating set problem. In the model, a synthetical gene network constituting a lactose operon and RNAi is constructed in living cell. The problem is solved by gene regulation in transcription and translation process. The inputs are RNA double strands and target DNA molecules, target DNA encoded the information, i.e. the logic values of the vertex of a graph. The computation is realized by vector construction, cell culture and transfection, and detection. The outputs are fluorescence protein.