Not only genetic information, also its processing functions are carried by proteins, DNAs, and their interactions. This process is observed typically in signal transduction (pathways). The final aim of this project is to establish a theoretical foundation for utilizing their information-processing function of molecules in a conventional engineering sense. It's final aim is to realize, by depeveloping novel experimental procedures, a multi-purpose computer functioning by molecular-level interactions.

We use molecular-level interaction to achieve faster (massively parallel), smaller (ultramicro), and cost effective (energy-efficient) computation. If each molecule could participate in a different computation, we would achieve a massively pallarel computer no one has ever seen before. If every single molecule could work as a memory, we would achive smaller and energy-efficient computers. DNAs and protein molecules are ideal for these purposes; they have complex structures with combinatorial variety, which enables them to work as building blocks and effectors of biomolecules. We expect to realize various physico-chemical functions using this novel computation.

Our Research

The entire research field called `DNA Computing' originates in a single research paper in Science (vol266, 1994,pp 1021-1024) by L.Adleman. He proposed an algorithm to solve Hamiltonian Path Problem using DNAs, and, by a lab experiment, actually confirmed a Hamiltonian path of seven vertices in a directed graph. Though his paper focused on the parallelism in the computation, this method has other applications than computation, such as micro-fabrication. Our project focuses not only on basic lab operations and theoretical computational model in Adleman's style, but also on in-vitro selection and evolutional reactors, hinted by the relation between computation and evolution. Our research is done in three groups.

Basic operations and their realization in molecular computation

In this project, we proposed several computations based on bio-molecules and examined their possibility as basic operators.

Hamiltonian Path Problem

Although this problem was tackled in Adleman's pioneering work, we specifically concentrate on the stepwise extention of paths on a solid surface, and try lab experiments to remove looping paths by utilizing bulge loops of DNAs.

Molecular Automata

We aim to perform different calculations in each molecule, and continue research on realization of automata using molecules. We have proposed methods to simulate finite automata and boolean mu formulas, and proved their realizability in lab experiments. Transitions in these automata are perfomed by polymerase extention of a hairpin loop.

Relationally Complete Operators

Using DNA strands as tuples in relational database, we proposed lab operations achieving basic operators in relational algebra and experimentally examined their realizability.

Theory of computing in molecular computation

Splicing System

Splicing system is a formal language system modeling DNA (or RNA) splicing. The computation power of splicing on linear molecule is equal to a regular language, therefore this project tries various enhancement to strengthen its computation power. Our results include circular splicing system which is equivalent to a universal computer, and tree splicing system whose power corresponds to a context-free grammar.

Hybridization System

We also research on a system based on hybridization, another basic characteristic of DNA strands.

In-vitro selection and evolutinary reactor

There is a close similarity between molecular computation and molecular evolution.

In-vitro selection

In this research, we succeeded in the separation of novel RNAs with a binding specificity to a certain small molecules, and the purification of enzymes whose binding specificity is artificially modified.

3SR method

We use PCR in amplifying DNA strands, but our 3SR method aims at amplification at a constant temperature. This method amplifies different DNAs in the same tube, and good individuals (DNAs) survive this process. This method can be called an evolutinary reactor.

Term

Apr 1996 - Mar 2001

Members (Ball colors show research category above.)

Project leader Prof. Masami Hagiya (home page) Hagiya Laboratory, Dept of Information Science, University of Tokyo. hagiya@is.s.u-tokyo.ac.jp Core members Prof. Shigeyuki Yokoyama Yokoyama Laboratory, Dept of Biochemistry, University of Tokyo. yokoyama@y-sun.biochem.s.u-tokyo.ac.jp Prof. Takashi Yokomori (home page) Yokomori Laboratory, Dept of Computer Science, Tokyo Electro-Communication University. yokomori@mn.waseda.ac.jp Prof. Akira Suyama Suyama Laboratory, Physics Instit, Faculty of Arts and Sciences, University of Tokyo. suyama@dna.c.u-tokyo.ac.jp Prof. Yuzuru Hushimi Hushimi Laboratory, Saitama University. husimi@biomol.saitama-u.ac.jp

Projects in Other Countries

Like ours, several projects start in US, Canada, and Europe. Their home pages are maintained by leading figures in each group. For the overview and the list of researchers in this field, visit Erik's Molecular Computation page (the best page in DNA computing).

ITO DARPA Project (Prototyping Biomolecular Computations)
Project Home page by J. Reif (Duke University)
This project aims exmerimental demonstration of biomolecular computation (BMC) and its application, nano-constraction of 3D structures, and mathematical models and software tools for simulation of BMC.

Related Links

Home page of UDel and UPenn group

Home page of Wisconsin group

Project in Canada
Home page of Lila Kari (University of Western Ontario)
Her group aims at solving Shortest Common Superstring Problem experimentally, and also aims at making models of computation theoretically. According to an anonymous source, she is trying to establish a new journal on molecular computation.

Projects in Europe
The community can be largely divided to continental formalists (G.Rozenberg at Leiden Univ Holland, G.Paun at Math Instit Romania, R.Freund at Tech Univ Wien and others), and English empiricists (M.Amos and others). The former group focus on theoretical analysis of molecular operations based on formal language theory.

Related Links

Home page of Liverpool group

Home page of Wayne group

Home page of Max Garzon

Home page of Seeman's Lab

Home page of Tom Head

Home page of Gregorz Rozenberg

Bibliography by Ray Dassen

Molecular computer page by Ian Brandt

Pacific Symposium on Biocomputing'98