Transcript DNA Computing on a Chip

DNA Computing on a Chip
Mitsunori Ogihara and Animesh Ray
Nature, vol. 403, pp. 143-144
Cho, Dong-Yeon
Abstract

In a DNA computer
 The input and output are both strands of DNA.
 A computer in which the strands are attached to the
surface of a chip can now solve difficult problems quite
quickly.

[Liu et al., 2000]
 Liu, Q. et al., “DNA computing on a chip,” Nature, vol.
403, pp. 175-179, 2000.
Arriving at the truth by elimination

Problem classes
 Polynomial time or P problems
 O(1),
O(n), O(nlogn), O(n2), O(n3), …
 Non-deterministic polynomial time or NP problems
 ‘Hard’ NP problems
have running times that grow
exponentially with the number of the variables.
 O(2n), O(3n), O(n!) …

New technology for massively parallel elimination
[Liu et al., 2000]
 This algorithm harnesses the power of DNA chemistry
and biotechnology to solve a particularly difficult
problem in mathematical logic.
Adleman’s experiments

Hamilton path problem
 Millions of DNA strands, diffusing
in a liquid, can self-assemble into all
possible path configurations.
 A judicious series of molecular
manoeuvres can fish out the correct
solutions.
 Adleman, combining elegance with
brute force, could isolate the one
true solution out of many probability.
Liu’s experiments

Satisfiability Problem
 Find Boolean values for
variables that make the given
formula true

3-SAT Problem
( x1  x3  x4 )  ( x4 )  ( x2  x3 )
( x1 or x2 or x3 ) AND ( x4 or x5 or x6 )
 Every NP problems can be ( x1 or x2 or x3 ) AND ( x1 or x2 or x3 )
seen as the search for a
solution that simultaneously
satisfies a number of logical
clauses, each composed of
three variables.
Procedure

Step 1.
 Attach DNA strings encoding all possible answers to a
specially treated gold surface.

Step 2.
 Complementary DNA strands that satisfy the first
clauses are added to the solution.
 The remaining single strands are destroyed by enzymes.
 The surface is then heated to melt away the
complementary strands.
 This cycle is repeated for each of the remaining clauses.

Step 3.
 The surviving strands first have to be amplified using
the PCR.
 Their identities are then determined by pairing with an
ordered array of strings identical to the original set of
sequences.

O(3k+1) vs. O(1.33n), O(2n)
 k: the number of clauses
 n: the number of variables
Problems

Scaling up this technique to solve larger 3-SAT
problems is still unrealistic.
 Correcting errors arising from the inherent sloppiness
of DNA chemistry
 High cost of tailor-made DNA sequences
 50-variable
3-SAT: 1015 unique DNA strands
 Designing enough unique DNA strands
 Exponentially increasing number of DNA molecules
 A compromise
may be achieved by reducing the search space
through heuristics.
Conclusions

The ideal application for DNA computation does
not lie in computing large NP problems
 There may be a need for fully organic computing
devices implanted within a living body that can
integrated signals from several sources and compute a
response in terms of an organic molecular-delivery
device for a drug or signal.