A trillion computers in a drop of water: Scientists build a nanoscale computing machine using biological...( compute. Shapiro challenged his P...)

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 0s and 1s has an even number of 1s. 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 1s checker and the 0s before 1s test mentioned above, as well as programs that check whether a list of 0s and 1s has at least (or at most) one, and whether it both starts with a 0 and ends with a 1.

The nanocomputer created by Shapiros 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 molecul
'"/>

Contact: Jeffrey Sussman
jeffrey@acwis.org
212-895-7951
American Committee for the Weizmann Institute of Science
21-Nov-2001