Molecular Hairpins That Compute

Not only can DNA spell out life, it also can be used to solve tough math and logic problems--a technology that won't find its way into your laptop computer anytime soon but could be useful in biotechnology. So far, however, "molecular computations" have required lots of old-fashioned, shake-the-test-tube lab work for each step in the calculation. Now, a new type of DNA computation can run more or less on its own by taking advantage of the molecule's penchant for twisting itself into knots.

Biochemist Kensaku Sakamoto of the University of Tokyo and colleagues tackled a version of the satisfiability problem in Boolean logic, a form of reasoning in which "literals"--statements and their opposites--are linked together with or and and to form complicated formulas. They assailed a jumbo formula that can be thought of as a compact way to write down many strings of literals at the same time. The problem is to pick out the handful of strings that do not link contradictory statements. For example, in the simple formula "(I think or I love you) and (I am or I love you not)," the string "I think and I am" pops right out and is perfectly logical. It "satisfies" the formula--and Descartes, too. On the other hand, the equally obvious string "I love you and I love you not" is illogical, not to mention fickle and cruel, and does not satisfy the formula.

To translate their problem into molecules, the researchers began as others have, with a large assortment of pieces of single-stranded DNA, one for each possible solution of the puzzle. But whereas others mixed in one enzyme after another to cut up the lengths representing the wrong answers, Sakamoto and colleagues designed their strands so that the wrong answers spontaneously folded over and stuck to themselves to form molecular "hairpins."

This was possible because DNA naturally comes with two complementary strands twisted together, and the researchers set up their problem so that every length representing a logical contradiction contained at least one 30-base sequence and its complement. When cooled in just the right way, these sequences zipped together to form the hairpins, the researchers report on page 1223 of the 19 May issue of Science. The researchers then cut all the hairpins with a single dose of enzyme and copied the remaining unfolded strands, which represented the right answers.

The new method exploits not only DNA's ability to encode information but also its talent for forming complex structures, says team member Masami Hagiya, a computer scientist at the University of Tokyo. But the method also lets through many more wrong answers than other methods do, notes Laura Landweber, a biologist at Princeton University. "I remain intrigued but skeptical," she says, "until they can reduce the large proportion of errors."