Strings and Genomes - Infobiotics: Information in Biotic Systems - page 50

2.4.1 Adleman's Experiment

The main idea of Adleman's experiment is the representation of a graph in a DNA
pool. To this end, it is enough to encode nodes with single DNA strands and edges
as other strands in such a way that when an edge f connects two nodes a and b ,then
it is encoded by a strand which hybridizes with one half of the strand encoding a
and one half of the strand encoding b . Figure 2.26 illustrates this idea of realizing
connections with hybridization of single DNA strands. In this manner, when many
copies of strands encoding all the nodes and edges of a graph are put in a DNA pool,
then, in a very short time, they hybridize by providing all the possible paths which
can be formed in the graph. Some specific operations involving the ligase and poly-
merase enzymes are necessary for having stable and abundand strands. Ligase fuses
all the strands in the paths by performing the missing OH-P bonds between consec-
utive strands which are linearly arranged, while polymerase provides a generation of
many copies of the formed paths, according to the polymerase chain reaction which
we will study in a following section.
The question posed by Adleman, solved by DNA operations, was the determi-
nation of a Hamiltonian path connecting a start node with an end node (a path
passing exactly once for each node of the graph). In terms of DNA strands, this
corresponds to finding a DNA strand beginning with a given prefix and end-
ing with a given suffix, having a given length ( nk length if in the graph there
are k nodes, all encoded by strands of length n ) and where the encoding of
each node is included. The solution (only one solution was possible in the prob-
lem considered by Adleman) was found by selecting by electrophoresis all the
strands of the required length, and then by keeping only those which are com-
plete , in the sense of including the encoding of all nodes. The check of com-
pleteness is performed by the crucial operation of extraction . Given a DNA pool
P , the extraction of its

γ -strands, provides strands of P having a type includ-

ing the string ,..., α k are the strings en-

coding the nodes, then the strands solving the problem have to include types
α 1 , α 2 ,..., α k . Let us consider k probes, that is, strands having types comple-
mentary to the strings

γ . In Adleman's experiment, if α , α

1 2

α 1 , α 2 ,..., α k . Therefore, by using the first probe, all the
strands are selected, by complementarity (we avoid the biochemical details), with
types including the string α 1 , then, from this selection, with a second probe, the

strands can be selected which include α 2 , and by proceeding in this way, after

k steps ( k the number of nodes of the graph), the required solution can be ob-
tained. Sequencing the final strands, the required Hamiltonian path can be easily
determined.

Bj Ai Bi

Bj ' Ai '

Fig. 2.26 Adleman experiment