The Classic "Traveling Salesman" problem. Find the routes from A -> G going through each city only once. This problem is solved quickly by DNA, yet it can stump a super computer. Who knew? |
| The first problem that was completed by using DNA was the world renown "Traveling Salesman" problem, also known as the Hamiltonian Path problem. The problem, known as a "key-into-lock" problem, asks for the routes that pass through 7 cities, going through each once and only once and starting at point A and finishing at point G each time. The problem is set up like this: |
|
The Classic "Traveling Salesman" problem. Find the routes from A -> G going through each city only once. This problem is solved quickly by DNA, yet it can stump a super computer. Who knew? |
| What
happens first is that each city is assigned two four-letter names like
Atlanta = ACTTgcag , Boston = TCGGactg, Chicago
= GGCTatgt etc. (where the a, c, t, g stand
for nucleic acids). Then each city is given a name for its arriving
and departing flights and a complement for its original name like Atlanta
(comp)= TGAAcgtc. When all of these are mixed together, they form
multiple strands. The next step is to separate the good answers from
the bad answers. How is this done? Well, to be honest, hours
of laboratory separation are required, which makes for one of the humps
that need to be crossed in the field of DNA computing.
Click here to see how scientists are trying to simplify or even eradicate the separation process. |
 |
Created as part of a term project
for SCEN103
at the University of Delaware
Comments, suggestions, or requests to vverruto@udel.edu "http://www.udel.edu/physics/scen103/CGZ/DNAcomp1.html" Last updated May 11, 2000. Copyright Jen Franchino, Vinnie Verruto, Allison Zuckerbrow, Jeff May, Univ. of Delaware, 2000 |