The notion of using molecules as the working elements of a computer goes back several decades. It wasn’t until 1994, however, that anyone actually stepped into a laboratory and succeeded in solving a computational problem in a test tube.
That was when computer scientist Leonard M. Adleman of the University of Southern California, using techniques from molecular biology, manipulated strands of DNA to solve a mathematical problem: Given seven points linked by one-way paths, find a route that visits each point once on the way from a specified starting point to a given end point.
Although Adleman’s feat generated considerable interest and prompted a variety of research efforts devoted to molecule-based computing, progress has been relatively slow.
Now, Ehud Shapiro of the Weizmann Institute of Science in Rehovot, Israel, and a team of computer scientists and biochemists have demonstrated how a test tube of DNA molecules can compute on its own. In effect, DNA molecules serve as the biomolecular nanomachine’s software and DNA-manipulating enzymes serve as its hardware. The researchers reported their success in the Nov. 22, 2001 Nature.
“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,” Shapiro noted. “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.”
The team’s approach differed significantly from that used by Adleman and others who have taken up the challenge of molecular computing. Earlier methods generally involved specially designed DNA strands as inputs and required a laborious, human-supervised sequence of lab procedures to achieve the desired results. The biological nanomachine developed by Shapiro and his coworkers depended only on using the appropriate molecular mix to produce, without further human intervention, a DNA molecule representing the answer to a given problem.
The new nanomachine is a molecular realization of a device known as a finite automaton–an idealized machine that operates on finite sequences of symbols.
Mathematician Alan M. Turing (1912–1954) was one of the first to propose the idea of a finite automaton as a universal mathematics machine. Such a Turing machine can be pictured as a black box capable of reading, printing, and erasing symbols on a single tape divided into a long row of cells. Each cell is blank or contains one symbol from a finite alphabet of symbols.
The Turing machine scans the tape, one cell at a time, usually beginning at the cell farthest to the left that contains a symbol. The machine can leave the beginning symbol unchanged, erase it, or print another in its place. If in reading the tape the machine later encounters a blank cell, the machine has the choice of leaving the cell empty or printing a symbol. After it performs its assigned task on a given cell, the machine stops or else moves one cell to the left or right.
What the machine does to a cell and which way it moves afterward depends on the state of the machine at that instant. Like a state of mind, the machine’s internal configuration establishes the environment in which a decision is made. Turing machines are restricted to a finite number of states.
A so-called action table stipulates what a machine will do for each possible combination of symbol and state. The first part of each instruction specifies what the machine should write, if anything, depending on which symbol the machine sees. The second part specifies whether the machine is to shift one cell to the left or to the right along the tape. The third part determines whether the machine stays in the same state or shifts to another state, which usually calls for a different set of instructions.
A Turing machine is somewhat like a typewriter whose characters can be put together in countless different ways. The same typewriter can produce any novel that has ever been written or ever will be written. Similarly, a universal Turing machine can be programmed with a finite set of instructions to imitate any other special-purpose machine. Indeed, given a sufficiently large but finite amount of time, a Turing machine is capable of any computation that can be done by a modern digital computer.
Shapiro and his collaborators designed a molecular version of a finite automaton that features two internal states (S0 and S1) and an alphabet of two input symbols, a and b. Such an automaton can have eight possible transition rules, each one specifying a “next” state based on the current state and the current symbol. For example, given state S0 and symbol a, one transition rule specifies leaving the state unchanged (S0). For the same initial conditions, another rule mandates a transition to state S1–and so on for all possible combinations of state and symbol. Programming amounts to crafting an action table to solve a specific problem by selecting appropriate transition rules to achieve that purpose.
To solve the specific problem of determining whether a string of 0s and 1s has an even number of 1s, the researchers made up a custom solution of DNA molecules and two naturally occurring enzymes. Different DNA segments represented input data and an appropriate selection of the eight transition rules available for a two-state, two-symbol machine. One enzyme, known as FokI, operated chemically like a pair of scissors to cleave DNA strands, and the other–ligase–tied DNA segments together. The enzymes worked together on the available DNA strands to create output DNA molecules encoding the answer. A process known as gel electrophoresis made the final answer visible to the human eye.
By changing the input and software DNA molecules appropriately, the scientists can solve a variety of problems. For example, given a string of 1s and 0s, they might want to determine whether a 0 precedes each of the 1s, or whether a particular string starts with 0 and ends with 1. For illustrations and animations of how such a nanoscale computing machine operates, see http://www.weizmann.ac.il/mathusers/lbn/new_pages/Visual_Presentation.html.
At present, this biological nanocomputer is far too rudimentary for immediate application. The system operates on such a small scale, however, that it’s possible to envision having a trillion or more such biomolecular machines in a drop of water, capable of carrying on a host of operations at once. The researchers estimate that these nanocomputers could collectively perform a billion operations per second with greater than 99.8 percent accuracy per operation while consuming less than a billionth of a watt of power.
Eventually, this research could lead to computers that operate within the human body. “For instance,” says the Weizmann Institute’s Zvi Livneh, “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.”
