C-5-56
Towards Persistent Molecular Computers for
Molecular Robots
Masami Hagiya 1

Ibuki Kawamata 1

hagiya@is.s.u-tokyo.ac.jp

ibuki@is.s.u-tokyo.ac.jp

Nathanael Aubert 1
nathanael.aubert@gmail.com

1

Department of Computer Science, Graduate School of Information Science and Technology
The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan

Keywords: Molecular computing, DNA computing, Molecular robotics
Although a large number of models for molecular computers have been proposed a nd many of them
have actually been implemented typically by using DNA molecules with or without modifications,most of those models are restricted in the sense that computational resources are consumed by each
instance of computation and cannot be reused i teratively. Models based on strand displacement ofDNA, such as that of seesaw gates by Qian et al. [1], are not exceptions . On the other hand, theidea of molecular robots is now commonly accepted [2], and computers for molecular robots areexpected to be reusable and sustainable. The model of dynamical systems by Rond elez et al. is oneof few such models [3]. We envision that molecular computers for molecular robots should havethe following properties. They 1) receive input from the environment, 2) adapt to the environment
by solving some optimization (or learning) problems, and finally 3) save the result of computation(solutions to the problems) for handling the next input from the environment.
In this ongoing and preliminary work, we take the k -SAT problem as an optimization problem
whose clauses model input from the environment. The molecular computer solves the problem, andre-solves it when its clauses are modified or new ones are added. As in the work by Sakamoto et al.
[4], each clause of an instance of the k-SAT problem is represented by a computational unit. While
one literal is chosen from a clause in advance in [4], a computational unit in this work takes one of
the literals in its corresponding clause as a state, and changes the state for sol ving or re-solving theproblem.
In this poster, we propose and compare three molecular implementation s of the above abstractscheme. 1) Implementation by a molecular complex whose conforma tional changes realize
progression of state transitions by alternating irradiation of two kinds of light [5]. 2)
Implementation by polymerase extension and digestion by nicking enzymes, which can beconsidered as an extension of DWPCR [6]. 3) Implementation by a dynamical system of Montagneet al. [3].
[1] Qian et al.: Neural network computation with DNA strand displacement cascades, Nature475:368, 2011.
[2] Molecular Robotics: http://www.molecular-robotics.org/en/[3] Montagne et al.: Programming an in vitro DNA oscillator using a molecular networking
strategy, Molecular Systems Biology 7:466, 2011.
[4] Sakamoto et al.: Molecular computation by DNA hairpin formation, Science 288:1223, 2000.
[5] Nishioka et al.: A photon-fueled DNA nanodevice that contains two different photoswitches,
Angewandte Chemie International Edition, 51:1165, 2012.
[6] Rose et al.: Displacement Whiplash PCR: Optimized Architecture and Experimental Validation,
Lecture Notes in Computer Science 4287:393, 2006.