YouTube Facebook LinkedIn Google+ Twitter Xingrss  



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.


 

STEP 1

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


STEP 2

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.

 

STEP 3

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.
 


IMAGES BY JOHN MACNEILL



Back to Calculating with DNA 




For reprints and/or copyright permission, please contact  Terry Manning, 781.972.1349 , tmanning@healthtech.com.