Information Technology Reference
In-Depth Information
Fig. 7.12 Main stages of solving the problem of determining Hamiltonian paths by the technique
of DNA computing
segment is divided into two parts, corresponding to the right and the left neighbor of
the point. In addition, 20-nucleotide sequences of the single-stranded DNA are
synthesized corresponding to all possible distances between points (1-2, 1-3
1-
...
N
,
2-1, 2-3, 2-4, etc.). Each segment corresponding to the distance between the
i
th and the
j
th points is a sequence of 10 nucleotides complementary to the right part
of the code of the point
i
and 10 nucleotides complementary to the left of the code of
the point
j
. All segments of nucleotides corresponding both to the points and to the
possible distances between them are merged into a reactor. As a result hydrogen
bonds are formed between the complementary DNA codes corresponding to each
other. In other words, the process called hybridization takes place. After this, a
special enzyme (ligase) cross-links the segments connected by hydrogen bonds into
single-stranded DNA fragments. Thus, synthesis method implies that a huge num-
ber of DNA molecules corresponding to all possible paths between points are
produced. In this case, all of them are synthesized simultaneously, i.e., with a
huge degree of parallelism.
The second stage of the solution to the problem of Hamiltonian paths developed
by Adleman was using genetic engineering techniques in order to determine
whether, among the components of the mixture of single-stranded DNA, there are
copies corresponding to these paths. Adleman applied an analysis technique based
on the principle of successive removal of anything not related to the solution of the
problem.
To accomplish this, Adleman proposed the following analysis
...
scheme
(Fig.
7.12
):
