Information Technology Reference
In-Depth Information
The main steps of Adleman's experiments are synthesized in the following list.
1. Encode nodes and edges of the graph under investigation by means of suitable
linear strands which hybridize by providing double strands encoding all the pos-
sible paths of the graph;
2. Add Ligase enzyme in order to transform hybridization paths into double strands
(by concatenating contiguous strands);
3. Amplify, that is, realizes many copies (by using PCR, as will be explained later)
of the double strands starting with the start node and ending with the end node of
the graph;
4. Separate by length the double strands of the previous step encoding paths with 7
nodes (all the nodes of the graph);
5. Extract, from the paths of the previous step, those where all the nodes occur (each
node once, because paths of the previous step contain 7 nodes);
6. The double strands remaining, after the extraction of the previous step, encode
Hamiltonian paths of the given graph.
The procedure of Adleman's experiment has a general validity. In fact, in any combi-
natorial problem we can distinguish two different phases (see Fig. 2.27): the gener-
ation of a solution space where all possible solutions are produced, and a following
phase where the true solution of the given problem is selected. Selection requires
tools for discriminating between false and true solutions. The conceptual strength
of DNA computing relies in the possibility of nature in performing massive string
recombination processes, on the basis of the massive parallelism of strand hybridiza-
tion in DNA pools with billions of billions of strands. The extraction operation is
technologically more complex, expensive, and usually not very reliable. We will
consider an extraction method in a following section. However, in principle, both
generation and extraction operations can be performed in linear time, with respect
to the size of the combinatorial problems. This general model of DNA computation,
usually called Adleman-Lipton extract model [39] was tested and applied in many
specific cases. After almost 10 years of research in this context, the initial enthu-
siasm about the computational efficiency of DNA computing sensibly diminished,
but many aspects and many related fields of investigation were pushed by the Adle-
man's experiment and by all the research following it. We want only to mention the
problem 3-SAT, on which a great deal of research effort was spent in recent years,
for its centrality in the theory of combinatorial problems and for its natural setting
in the context of DNA computing.
The problem 3-SAT consists in the determination of boolean assignments, to the
variables X 1 ,
X 2 ,...,
X n , which satisfy a number of boolean equations C 1 ,
C 2 ,...,
C m
involving X 1 ,
X n . It can be easily shown that without loss of generality
boolean equations can be put in the form of clauses , that is, boolean sums of at
most 3 literals (this explains the name 3-SAT) implicitly equated to the truth value
true, where each literal can be a boolean variable or the negation of a boolean vari-
able. For example, the system of boolean equations 2.1 (
X 2 ,...,
1 is implicit in every
line) is a 3-SAT problem of 4 variables and three clauses which has, for example,
the assignment
=
(
X 1 ,
X 2
X 3 ,
X 4 )
as solution.
 
Search WWH ::




Custom Search