dna-abc6

$e-MATH$
The ABC of DNA Computing

6. Using recombinant chemistry to extract the solution.

In Adleman's Hamiltonian path experiment (involving seven ``airports'' and fifteen ``flights'') the yield of the first mixing included molecules like


               Atl->Dal        Dal->Chi
            

     Atlanta*          Dallas*        Chicago*

but also molecules like


               Chi->Dal        Dal->Chi
            

     Chicago*          Dallas*        Chicago*

in which an airport is visited more than once. Also the sequences shown here visit only three of the seven airports, and none of them start with Fresno or end with Boston. A sequence of steps (the chemical details are given in Adleman's article) uses recombinant DNA technology to eliminate

All molecules which do not start with Fresno* and do not end with Boston*.
All molecules which do not contain exactly 7 airports (i.e. all molecules which do not have a certain exact length).
All molecules which contain a repeated airport.

If there is anything left, it must be molecules encoding a path that goes from Fresno to Boston visiting each of the other airports exactly once: the graph has a Hamiltonian path. In our example there is exactly one such path, which can be read off by analysis of the yield of the complete experiment,

It is interesting that even though this whole procedure is completely artificial, the ``techology'' which permits the various steps comes from the harnessing of the enzymes used by cells themselves to replicate, to transcribe and when necessary to destroy DNA.