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 technology'' 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.

Welcome to the
Feature Column!

These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.