notes
Structure
Computing with DNA
  Overview
1. Introduction
2. Hamiltonian Path Problem
3. Finding Solution with DNA Experiment
4. Summary & Conclusion
1. INTRODUCTION
Computing with computer:
CPU, memory, I/O
Binary coding
Serial processing
Computing with DNA
Invented (discovered?) by Dr. Leonard M. Adleman of USC in 1994, a computer scientist and mathematician
Basic Idea: Perform molecular biology experiment to
        find solution to math problem.
“DNA Computer”
“Biological Computation”  vs “computational biology”
“Molecular Computer”
2. HAMILTONIAN PATH PROBLEM
(Posed by William Hamilton)
Given a network of nodes and directed connections between them, is there a path through the network that begins with the start node and concludes with the end node visiting each node only once (“Hamiltonian path")?
“Does a Hamiltonian path exist, or not?”
Hamiltonian path does exist?
Hamiltonian path does not exist?
Solving the Hamiltonian Problem
  Generation-&-Test Algorithm:
 Step 1: Generate random paths on the network.
 Step 2: Keep only those paths that begin with start city and
  conclude with end city.
 Step 3: If there are N cities, keep only those paths of length N.
 Step 4: Keep only those that enter all cities at least  once.
 Step 5. Any remaining paths are solutions (I.e., Hamiltonian
paths).
"[X]"
 [X] D -> B -> A
 [X] B -> C -> D -> B -> A -> B
 [X] A -> B -> C -> B
 [X] C -> D -> B -> A
 [X] A -> B -> A -> D
 [O] A -> B -> C -> D
 [X] A -> B -> A -> B -> C -> D
Does a Hamiltonian path exist for the following network?
Combinatorial Explosion
 The total number of paths grows exponentially as the network size increases:
 (e.g.) 106 paths for N=10 cities, 1012 paths (N=20),
10100 paths!! (N =100)
 The Generation-&-Test algorithm takes “forever”. Some sort of smart algorithm must be devised; none has been found so far (NP-hard).
3. FINDING SOLUTION WITH
DNA EXPERIMENT
DNA is a double-strand polymer made up of alternating series of four bases, A, T, C, G.
DNA makes multiple copies of itself during cell differentiation.
DNA for Hamiltonian Problem
The key to solving the problem is using DNA to perform the five steps of the Generation-&-Test algorithm in parallel search, instead of serial search.
Solving the Hamiltonian Problem
DNA Polymerase
- Protein that produces complementary DNA strand
- A -> T, T -> A, C -> G, G -> C
- Requires primer and starter
- Enables DNA to reproduce
Polymerase in Action
The “bio” nanomachine:
hops onto DNA strand
slides along
reads each base
writes its complement onto new strand
DNA Experiment Set-up
Ingredients and tools needed:
- DNA strands that encode city names and connections between them
- Polymerases, ligase, water, salt, other ingredients
- Polymerase chain reaction (PCR) set
- Gel electrophoresis tool (that filters out non-solution strands)
Gel Electrophoresis
Page 19
Page 20
DNA encoding of city-network
Page 22
Page 23
DNA Experiment
1. In a test tube, mix the prepared DNA pieces together
(which will randomly link with each other, forming all different paths).
2. Perform PCR with two ‘start’ and ‘end’ DNA pieces as primers (which creates millions’ copies of DNA strands with the right start and end).
3. Perform gel electrophoresis to identify only those pieces of right length (e.g., N=4).
"4."
4. Use DNA ‘probe’ molecules to check whether their paths pass through all intermediate cities.
5. All DNA pieces that are left in the tube should be precisely those representing Hamiltonian paths.
- If the tube contains any DNA at all, then conclude that a Hamiltonian path exists, and otherwise not.
- When it does, the DNA sequence represents the specific path of the solution.
4. SUMMARY & CONCLUSION
- Why does it work?
Enormous parallelism, with 1023 DNA pieces working in parallel to find solution simultaneously.
Takes less than a week (vs. thousands yrs for supercomputer)
-  Extraordinary energy efficient
(10-10 of supercomputer energy use)
-  Future work:
Weather forecasting, robot brain, …, using DNA computers?
(Note: DNA is a Universal Turing machine.)