22 November 2001
Nanoscale Computer Built Using Biological Molecules
by Kate Melville 
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 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 finite automaton.
This nanocomputer can be programmed to perform 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 735 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, 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.
| 
