| | Ivars Peterson's MathTrek |
July 22, 1996
In the July 12 Science, a team of researchers at the Mount Sinai School of Medicine in New York City report that they have developed an algorithm that permits the use of single-stranded DNA reactions to add together two, nonnegative binary numbers. More impressively, they have the experimental evidence to back their scheme.
Since 1994, when computer scientist Leonard M. Adleman of the University of Southern California first demonstrated the feasibility of a molecular approach to solving mathematical problems, researchers have focused on finding ways to link mathematics and biochemistry to perform different kinds of computations. Their long-term hope is that DNA-based computers will eventually prove superior in speed, memory capacity, and energy efficiency over electronic computers for solving certain kinds of problems.
Most research efforts have tried to take advantage of the enormous number of DNA molecules that can be packed into a small volume. Adleman, for example, solved a combinatorial problem by generating all the possible combinations as different strands of DNA, then searching for, isolating, and identifying the one strand representing the correct solution.
In contrast, Mount Sinai's Frank Guarnieri and Carter Bancroft have concentrated on developing a DNA-based addition algorithm, which demands only that the correct output is produced in response to specific inputs. "Consequently, the addition operation requires a quite different model for the use of DNA in computing than that used previously for search procedures," the researchers note.
A single strand of DNA consists of a chain of simpler molecules called bases, which protrude from a sugar-phosphate backbone. The four varieties of bases are known as adenine (A), thymine (T), guanine (G), and cytosine (C). Any strand of DNA will adhere tightly to its complementary strand, in which T substitutes for A, G for C, and vice versa. For example, a single-stranded DNA segment consisting of the base sequence TAGCC will stick to a section of another strand made up of the complementary sequence ATCGG. The links between pairs of bases are responsible for binding together two strands to form the characteristic double helix of a DNA molecule.
Adding binary numbers, represented as strings of 1s and 0s, requires keeping track of the position of each digit and of any "carries" that come up when 1 is added to 1 to give the result 10. For example, adding 11 to 01 means starting with the digits farthest to the right of each number: 1 + 1 = 10, so 0 goes in the first place from the right, and 1 is carried over to the next column. When the carried digit is added to the two digits in the second position from the right (1 + 1 + 0), the result is 10, with 0 in the second position from the right and 1 in the third position to give the final answer 100.
Converting this procedure into manipulations of DNA molecules demands the use of DNA sequences that not only represent strings of 0s and 1s but also allow for carries and the extension of DNA strands to represent the answers. In their DNA addition algorithm, Guarnieri and Bancroft use special sequences that encode the number in a given position (0 or 1) and its position from the right.
+ 0 1
1 0 0
For example, the first digit in the first position is given by two DNA strands, each consisting of a short sequence representing a "position transfer operator," which carries information to the adjacent position, a short sequence representing the value of the digit (0 or 1), and a short sequence representing a "position operator."
In their Science paper, Guarnieri, Bancroft, and Makiko Fliss supply DNA representations of all possible two-digit binary integers (00, 01, 10, 11), which can then be added in pairs. Adding such a pair involves four steps in which the appropriate complementary sequences link up and strands are successively extended to make new, longer strands, finally yielding the correct output.
The researchers term this set of steps a horizontal chain reaction. Input DNA sequences serve as successive templates for constructing an extended result strand. Like a tape recording, the final strand encodes the outcomes of successive operations, yielding the digits of the answer in the correct order.
"The growing strand is also an active participant in the addition algorithm because the output strand for each operation (reaction) serves as the operator (primer) for the succeeding operation," they note. "Thus, the result DNA strand serves both as an operator that transfers information during the addition algorithm and as a tape that records the outcome of the algorithm."
"What we've done with the horizontal chain reaction is to start getting DNA molecules to communicate with each other," Bancroft remarks.
To test their algorithm in the lab, the team combined in a test tube the DNA strands representing the two numbers to be added, along with the chemicals needed for the strand extension reactions. In this way, they successfully determined the sums 0 + 0, 0 + 1, 1 + 0, and 1 + 1 in the form of DNA strands of the appropriate molecular size. The necessary biochemical procedures took about 1 or 2 days of lab work for each calculation.
Though limited in scope, this particular effort represents one of the very few instances so far in the development of DNA-based computing in which real experimental results have emerged to bolster the theory. "One of our strengths is that we can carry out some of our algorithms experimentally," Bancroft says. The field desperately needs more data about what is really feasible with "live" DNA in a test tube.
Of course, the DNA-based algorithm for adding binary digits developed by Bancroft and his colleagues poses no threat to any electronic computer. But that's not really the point. "The paramount thing now is to try to be imaginative in figuring out algorithms to solve interesting problems," Bancroft says.
Bancroft and Guarnieri are continuing their effort to figure out suitable algorithms and to improve experimental procedures. For example, they would like to make it possible to perform either a large number of additions at the same time or successive additions, in which the answer to one calculation becomes the input to the next.
For anyone who can link mathematical expertise with knowledge of biochemistry, there are plenty of opportunities to exercise his or her imagination in designing and executing novel approaches to computation.
Copyright © 1996 by Ivars Peterson.
Guarnieri, Frank, Makiko Fliss, and Carter Bancroft. 1996. Making DNA add. Science 273 (July 12): 220-223.
Guarnieri, Frank, and Carter Bancroft. 1996. Use of a horizontal chain reaction for DNA-based addition. Proceedings of the Second Annual Meeting on DNA Based Computers. Providence, R.I.: American Mathematical Society (in press).
Lander, Eric S., and Michael S. Waterman (Eds.). 1995. Calculating the Secrets of Life. Washington, D.C.: National Academy Press.
Peterson, Ivars. 1996. Computing with DNA. Science News 150 (July 13): 26-27. See also the June 17, 1996, edition of Ivars Peterson's MathLand: DNA, Computers, and Killer Apps.
Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.