A group of scientists headed by Prof. Ehud Shapiro at the Weizmann Institute of Science has used biological molecules to create a tiny computer - a programmable two-state, two-symbol finite automaton - in a test tube. Reported today in Nature, this biological nanocomputer is so small that a trillion (1,000,000,000,000) such computers co-exist and compute in parallel, in a drop the size of 1/10 of a milliliter of watery solution held at room temperature. Collectively, the computers perform a billion operations per second with greater than 99.8% accuracy per operation while requiring less than a billionth of a Watt of power. This study may lead to future computers that can operate within the human body, interacting with its biochemical environment to yield far-reaching biological and pharmaceutical applications.
The computer's input, output, and 'software' are made up of DNA molecules. For 'hardware,' the computer uses two naturally occurring enzymes that manipulate DNA. When mixed together in a solution, the software and hardware molecules operate in harmony on the input molecule to create the output molecule, forming a simple mathematical computing machine, known as a finite automaton. This nanocomputer can be programmed to perform several simple tasks by choosing different software molecules to be mixed in solution. For instance, it can detect whether, in an input molecule encoding a list made of 0's and 1's, all the 0's precede all the 1's.
'The living cell contains incredible molecular machines that manipulate information-encoding molecules such as DNA and RNA in ways that are fundamentally very similar to computation,' says Prof. Shapiro of the Institute's Computer Science and Applied Mathematics Department and the Biological Chemistry Department. 'Since we don't know how to effectively modify these machines or create new ones just yet, the trick is to find naturally existing machines that, when combined, can be steered to actually compute.'
Shapiro challenged his Ph.D. student, Yaakov Benenson, to do just that: to find a molecular realization of one of the simplest mathematical computing machines - a finite automaton that detects whether a list of 0's and 1's has an even number of 1's. Benenson came up with a solution using DNA molecules and two naturally occurring DNA-manipulating enzymes: Fok-I and Ligase. Operating much like a biological editing kit, Fok-I functions as a chemical scissors, cleaving DNA in a specific pattern, whereas the Ligase enzyme seals DNA molecules together.
As the lab work progressed, Shapiro and his team realized that the automaton they built could be programmed to perform different tasks by selecting different subsets of the molecules realizing the eight possible rules of operation controlling the performance of a two-state, two-symbol finite automaton. The software molecules, together with two 'output display' molecules used to visualize the final result of the computation, can be used to create a total of 765 software programs. Several of these programs were tested in the lab, including the 'even 1's checker' and the '0's before 1's' test mentioned above, as well as programs that check whether a list of 0's and 1's has at least (or at most) one 0, and whether it both starts with a 0 and ends with a 1.
The nanocomputer created by Shapiro's team uses the four DNA bases known as A, G, C and T, to encode the input data as well as the program rules underlying the computer 'software.' Both input and software molecules are designed to have one DNA strand longer than the other, resulting in a single-strand overhang called a 'sticky end.' Two molecules with complementary sticky ends can temporarily stick to each other (a process known as hybridization), allowing DNA Ligase to permanently seal them into one molecule. The sticky end of the input molecule encodes the current symbol and the current state of the computation, whereas the sticky end of each 'software' molecule is designed to detect a particular state-symbol combination. A two-state, two-symbol automaton has four such combinations. For each combination the nanocomputer has two possible next moves, to remain in the same state or to change to the other state, allowing eight software molecules to cover all possibilities.
In each processing step the input molecule hybridizes with a software molecule that has a complementary sticky end, allowing Ligase to seal them together using two ATP molecules as energy. Then comes Fok-I, detecting a special site in the software molecule known as the recognition site. It cleaves the input molecule in a location determined by the software molecule, thus exposing a sticky end that encodes the next input symbol and the next state of the computation. Once the last input symbol is processed, a sticky end encoding the final state of the computation is exposed and detected, again by hybridization and ligation, by one of two 'output display' molecules. The resulting molecule, which reports the output of the computation, is made visible to the human eye in a process known as gel electrophoresis.
The nanocomputer created is too simple to have immediate applications, however it may pave the way to future computers that can operate within the human body with unique biological and pharmaceutical applications. 'For instance, such a future computer could sense an abnormal biochemical change in the body and decide how to correct it by synthesizing and releasing the necessary drug,' says Prof. Zvi Livneh, a DNA expert from the Institute's Department of Biological Chemistry who collaborated on this project.
Other contributors to this research include Dr. Tamar Paz-Elizur and Dr. Rivka Adar from the Weizmann Institute's Department of Biological Chemistry, and Prof. Ehud Keinan from the Department of Chemistry at the Technion Israel Institute of Technology and the Department of Molecular Biology of The Scripps Research Institute.
About Prof. Shapiro
Prof. Shapiro received his Ph.D. from Yale University and joined the Department of Computer Science and Applied Math of the Weizmann Institute in 1982. During the 1980s he was involved with the Japanese Fifth Generation Computer Project and published numerous scientific papers in the area of concurrent logic programming languages.
In the early 1990s, Shapiro's innovative research in programming languages led to the establishment of Ubique, a company that develops interactive online environments. Shapiro took a leave from Weizmann to establish Ubique, and when the company was bought by America Online, Inc., he moved to the U.S. to assist in integrating Ubique's technology in America Online's internet services. When America Online sold Ubique to IBM in 1998, Shapiro returned to his research post at the Weizmann Institute and established the Laboratory for Biological Nanocomputers at the Department of Biological Chemistry, where the research reported in Nature was conducted.
Shapiro's design of a universal molecular computer, which inspired the creation of the molecular automaton reported in Nature, was recently awarded a U.S. Patent 6,266,569.
Note to journalists: A video presentation in beta format illustrating the operation of the molecular computer developed by Prof. Shapiro's team is available upon request. Ehud.Shapiro@weizmann.ac.il
Professor Ehud Shapiro's research is supported by the Ebner Family Biomedical Research Foundation and the Samuel R. Dweck Foundation.
The Weizmann Institute of Science is a major center of scientific research and graduate study located in Rehovot, Israel. Its 2,500 scientists, students and support staff are engaged in more than 1,000 research projects across the spectrum of contemporary science.