Information Technology Reference
In-Depth Information
(Step 1)—identify the chains in which the initial nucleotides correspond to the
starting point of all routes and the end nucleotides correspond to the end point.
(Step 2)—identify the chains with the length corresponding to a specified number of
paths.
(Step 3)—determine whether all points of the paths are included in the chains of the
nucleotides of the remaining DNA molecules.
If as a result of these steps DNA molecules still remain that have not been
deleted, we can assume that:
A solution to the problem of Hamiltonian paths exists.
All solutions are contained in the remaining DNA molecules.
It should immediately be noted that the desired sequences of nucleotides com-
prise but a small portion of the material obtained at the first stage. Therefore, at the
first analysis step Adleman used a technique that allowed for a manifold increase in
the number of DNA molecules that remain for the next steps of analysis—PCR, i.e.,
polymerase chain reaction. This reaction starts with primers attaching to DNA
molecules—20-nucleotide sequences corresponding to the start and end points of
Hamiltonian paths. Subsequently the enzyme DNA polymerase reproduces a
sequence of nucleotides located between the primers. This process is repeated
multiple times with the original and the newly derived molecules. As a result, the
number of these molecules after 30-40 cycles may be increased by 10
27
times. This
process also has high sensitivity and can detect 10-100 copies of DNA in the
mixture.
A second step of the analysis relies on liquid gel electrophoresis, which allows
for separating the mixture obtained by PCR into separate components with different
molecular weights.
In the third step of the analysis affine separation on magnetic beads was used.
Microparticles of a paramagnetic material chemically bonded with the chains of
nucleotides corresponding to individual points of the Hamiltonian path were
injected into the mixture analyzed. Upon attachment to the corresponding DNA
molecules, the obtained complexes were extracted by magnetic field.
Adleman himself notes that according to his estimates:
The performance of the proposed devices is 10
14
operations per second.
The energy efficiency is 2
10
19
operations/joule.
The approach can be used to solve combinatorial problems of moderate
complexity.
At the same time, the domain of problems where the approach can be used is
substantially limited.
The results of the calculations depend strongly on the exact fulfillment of the
conditions of the proposed approach.
