Information Technology Reference
In-Depth Information
Fig. 7.11 Encoding of graph elements in the problem of determining Hamiltonian paths
In particular, he was attracted to the problems of storing genetic information by
DNA molecules, transcription of this information, and its transmission.
A unique feature of Adleman was that his interest in information issues of
molecular biology was combined with a deep understanding of the problems of
high computational complexity. While developing an encryption system, he per-
fectly realized that traditional mathematical methods were insufficient. Taken
together all this led him to develop an approach called DNA computing.
As a concrete problem of high computational complexity, which could serve for
working out the basic principles of the approach, Adleman chose the problem of
finding Hamiltonian paths—an integral part of the traveling salesman problem. The
problem of finding Hamiltonian paths is to determine all possible paths that pass
through each point (the city that the traveling salesman needs to visit) of a set
containing
N
points. In this set the start and the end points are defined and thus each
point can be visited only once. Adleman chose as an object a system of seven points
(Fig.
7.11
). His approach was to solve the problem in two stages. The first stage
involved simultaneous identification of all the possible paths for this set of points,
both passing through all the points and not passing through some points several
times and only once, etc. The computation time of this stage is exponential in the
conventional numerical techniques for solving the problem.
The second stage is to analyze the obtained mixture of all possible paths.
Adleman showed that this process can be performed by methods of modern genetic
engineering in polynomial rather than exponential time.
The technical side of the approach was that each point of the system was
“modeled” by a segment of single-stranded DNA molecule (Fig.
7.11
). In
Adleman's methodology a segment containing 20 different nucleotides corresponds
to each point (city). Since each point of the path is joined with two others, the DNA
