A ‘DNA computer’ has been used for the first time to find the only correct answer from over a million possible solutions to a computational problem. Leonard Adleman of the University of Southern California in the US and colleagues used different strands of DNA to represent the 20 variables in their problem, which could be the most complex task ever solved without a conventional computer. The researchers believe that the complexity of the structure of biological molecules could allow DNA computers to outperform their electronic counterparts in future (R Braich et al 2002 Science to appear).
Scientists have previously used DNA computers to crack computational problems with up to nine variables, which involves selecting the correct answer from 512 possible solutions. But now Adleman’s team has shown that a similar technique can solve a problem with 20 variables, which has 220 – or 1 048 576 – possible solutions.
Adleman and colleagues chose an ‘exponential time’ problem, in which each extra variable doubles the amount of computation needed. This is known as an NP-complete problem, and is notoriously difficult to solve for a large number of variables. Other NP-complete problems include the ‘travelling salesman’ problem – in which a salesman has to find the shortest route between a number of cities – and the calculation of interactions between many atoms or molecules.
Adleman and co-workers expressed their problem as a string of 24 ‘clauses’, each of which specified a certain combination of ‘true’ and ‘false’ for three of the 20 variables. The team then assigned two short strands of specially encoded DNA to all 20 variables, representing ‘true’ and ‘false’ for each one.
In the experiment, each of the 24 clauses is represented by a gel-filled glass cell. The strands of DNA corresponding to the variables – and their ‘true’ or ‘false’ state – in each clause were then placed in the cells.
Each of the possible 1 048 576 solutions were then represented by much longer strands of specially encoded DNA, which Adleman’s team added to the first cell. If a long strand had a ‘subsequence’ that complemented all three short strands, it bound to them. But otherwise it passed through the cell.
To move on to the second clause of the formula, a fresh set of long strands was sent into the second cell, which trapped any long strand with a ‘subsequence’ complementary to all three of its short strands. This process was repeated until a complete set of long strands had been added to all 24 cells, corresponding to the 24 clauses. The long strands captured in the cells were collected at the end of the experiment, and these represented the solution to the problem.
According to Adleman and co-workers, their demonstration represents a watershed in DNA computation comparable with the first time that electronic computers solved a complex problem in the 1960s. They are optimistic that such ‘molecular computing’ could ultimately allow scientists to control biological and chemical systems in the way that electronic computers control mechanical and electrical systems now.
