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
Atlanta* Dallas* Chicago*
but also molecules like
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
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,
- All molecules which do not start with Fresno* and do not end with
- 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.
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.
© copyright 2000, American Mathematical Society.