Transcript Davidson`s PPT for VT - Genomics and Bioinformatics @ Davidson

Living Hardware to Solve the
Hamiltonian Path Problem
Professors: Dr. Malcolm Campbell and Dr. Laurie Heyer
Students: Oyinade Adefuye, Will DeLoache, Jim Dickson,
Andrew Martens, Amber Shoecraft, and Mike Waters
The Hamiltonian Path Problem
Computational Complexity
• Millennium Problem
• P=NP?
• Brute Force required
Does a Hamiltonian Path
exist in this graph?
Why Should We Use Bacteria?
VS.
Adleman LM (1994). Science 266 (11): 1021-1024.
Flipping DNA with Hin/hixC
Using Hin/hixC to Solve the HPP
Using Hin/hixC to Solve the HPP
hixC Sites
Using Hin/hixC to Solve the HPP
Using Hin/hixC to Solve the HPP
Using Hin/hixC to Solve the HPP
Solved Hamiltonian Path
What Genes Can Be Split?
GFP before hixC insertion
What Genes Can Be Split?
GFP displaying hixC insertion point
Gene Splitter Software
Input
1. Gene Sequence
Output
1. Generates 4 Primers
(optimized for melting
temperature).
2. Where do you want
your hixC site?
2. Biobrick ends are added
to primers.
3. Pick an extra base to
avoid a frameshift
3. Frameshift is eliminated.
Gene-Splitter Output
Note: Oligos are
optimized for melting
temperatures.
Use GFP to Split RFP
Green Fluorescent Protein
Red Fluorescent Protein
Can We Detect A Solution?
True Positives
Elements in the shaded region can
be arranged in any order.
Number of True Positives = (Edges-Nodes+1)! * 2
(Edges-Nodes+1)
False Positives
Extra Edge
False Positives
PCR Fragment Length
PCR Fragment Length
Detection of True Positives
Total # of Positives
1.0E+08
1.0E+07
1.0E+06
1.0E+05
1.0E+04
1.0E+03
1.0E+02
1.0E+01
1.0E+00
6/9
7/12
7/14
# of Nodes / # of Edges
1
Total # of Positives
# of True Positives ÷
4/6
0.75
0.5
0.25
0
4/6
6/9
7/12
# of Nodes / # of Edges
7/14
How Many Plasmids Do We Need?
Probabili ties for the Adleman graph
Probabili ty of at least k solutions on m plasmi ds.
k=1
5
10
20
m =10,000,000
.0697
0
0
0
50,000,000
.3032
.00004 0
0
100,000,000
.5145
.0009
0
0
200,000,000
.7643
.0161
.000003 0
500,000,000
.973
.2961
.0041
0
1,000,000,000
.9992 .8466 .1932 .00007
50
0
0
0
0
0
0
1 mL of culture = 10 9 cells
k = actual number of occurrences
λ = expected number of occurrences
λ = m plasmids * # solved permutations of edges ÷ # permutations of edges
Cumulative Poisson Distribution:
-λ . x
λ
_____
e
P(# of solutions ≥ k) = 1 X!
X=0
k-1
∑
Probability of HPP Solution
Starting Arrangement
4 Nodes & 3 Edges
Number of Flips
Where Are We Now?
First Bacterial Computer
Starting Arrangement
First Bacterial Computer
Starting Arrangement
Solved Arrangement
Future Directions
Split additional genes:
Make more complex graphs:
Solve other problems such as the
Traveling Salesperson Problem:
Living Hardware to Solve the
Hamiltonian Path Problem
Collaborators at MWSU:
Dr. Todd Eckdahl, Dr. Jeff Poet, Jordan Baumgardner,Tom
Crowley, Lane H. Heard, Nickolaus Morton, Michelle Ritter,
Jessica Treece, Matthew Unzicker, Amanda Valencia
Additional Thanks:
Karen Acker, Davidson College ‘07
Support:
Davidson College
The Duke Endowment
HHMI
NSF
Genome Consortium for Active Teaching
James G. Martin Genomics Program
Extra Slides
Traveling Salesperson Problem
Processivity
Problem:
•The nature of our construct requires a stable transcription
mechanism that can read through multiple genes in vivo
•Initiation Complex vs. Elongation Complex
•Formal manipulation of gene expression (through promoter
sequence and availability of accessory proteins) is out of the
picture
Solution : T7 bacteriophage RNA polymerase
• Highly processive single subunit viral polymerase which
maintains processivity in vivo and in vitro
Path at 3 nodes / 3 edges
HP- 1 12 23
1
2
T
3
Path at 4 nodes / 6 edges
HP-1 12 24 43
1
2
T
4
3
Path 5 nodes / 8 edges
HP -1 12 25 54 43
1
2
5
T
4
3
Path 6 nodes / 10 edges
HP-1 12 25 56 64 43
1
2
6
5
T
4
3
Path 7 nodes / 12 edges
HP-1 12 25 56 67 74 43
1
2
6
5
T
4
7
3
More Gene-Splitter Output
Promoter Tester
•
•
RBS:Kan:RBS:Tet:RBS:RFP
Tested promoter-promoter tester-pSBIA7 on varying concentration plates
Kanamycin
Tet
Kan-Tet
50
50
50 / 50
75
75
75 / 75
100
100
100 / 100
125
125
125 / 125
•Used Promoter Tester-pSB1A7 and Promoter Tester-pSB1A2 without
promoters as control
•Further evidence that pSB1A7 isn’t completely insulated
Promoters Tested
•Selected “strong” promoters that were also repressible from
biobrick registry
•ompC porin (BBa_R0082)
•“Lambda phage”(BBa_R0051)
•pLac (BBa_R0010)
•Hybrid pLac (BBa_R0011)
•None of the promoters “glowed red”
•Rus (BBa_J3902) and CMV (BBa_J52034)
not the parts that are listed in the registry
Splitting Kanamycin Nucleotidyltransferase
•Determined hixC site insertion at AA 125 in each monomer subunit
-AA 190 is involved in catalysis
-AA 195 and 208 are involved in Mg2+ binding
-Mutant Enzymes 190, 205, 210 all showed changes in mg+2 binding from the
WT
-Substitution of AA 210 (conserved) reduced enzyme activity
-AA 166 serves to catalyze reactions involving ATP
-AA 44 is involved in ATP binding
-AA 60 is involved in orientation of AA 44 and ATP binding
-We did not consider any Amino Acids near the N or C terminus
-Substitution of AA 190 caused 650-fold decrease in enzyme activity
-We did not consider any residues near ß-sheets or ∂-helices close to the
active site because hydrogen bonding plays an active role in substrate
stabilization and the polarity of our hix site could disrupt the secondary
structure and therefore the hydrogen bonding ability of KNTase)
•Did not split
Plasmid Insulation
• “Insulated” plasmid was designed to
block read-through transcription
•Read-through = transcription
without a promoter
•Tested a “promoter-tester” construct
•RBS:Kan:RBS:Tet:RBS:RFP
•Plated on different concentrations of
Kan, Tet, and Kan-Tet plates
•Growth in pSB1A7 was stunted
•No plate exhibited cell growth in
uninsulated plasmid and cell
death in the insulated plasmid
Tetracycline Resistance Protein
•Did not split
•Transmembrane protein
•Structure hasn’t been crystallized
•determined by computer modeling
•Vital residues for resistance are in
transmemebrane domains (efflux function)
•HixC inserted a periplasmic domains AA
37/38 and AA 299/300
•Cytoplasmic domains allow for
interaction with N and C terminus
Splitting Cre Recombinase
What Genes Can Be Split?
GFP before hixC insertion
GFP displaying hixC insertion point
Gene Splitter Software