YouTube Facebook LinkedIn Google+ Twitter Xinginstagram rss  

Oct. 9, 2002 | In 1994, the first working demonstration of a DNA computer set out to solve what is known as the traveling salesman problem. Specifically, the computer had to find a route between seven cities where you start at City 1 and end at City 7 passing through all cities only once.



Represent each city by a single DNA strand containing 20 randomly chosen amino acid bases.


Represent the route between any two cities by a single DNA strand where the first 10 amino acid bases are the complementary bases to the last 10 bases in City 1 and the second 10 bases are the complementary bases to the first 10 bases in City 2.



Millions of stands of DNA representing every city and every possible route between any two cities are placed in a test tube where the strands combine. The end result is a slew of long strings of variable lengths formed by the strands combining.

To determine the solution, the researchers looked only for strings that have City 1 at one end and City 7 at the other. Among these strands, the researchers looked for only the strings that had seven cities. Among what was left, they looked for a string with seven different cities. That is the solution.


Back to Calculating with DNA 

For reprints and/or copyright permission, please contact Terry Manning, 781.972.1349.