adleman+lipton.ppt.pptVIP

* DNA Computing Elements of complementary nature abound in nature. Complementary parts (in nature) can “self-assemble”. A universal principle? This “complementary-attraction-principle” seems to pervade many aspects of life (both molecular and higher levels). Elements of complementary nature spontaneously “stick” together. Cells: “atoms” that make up living things DNA: “strings” that encode the traits of living organisms Complementary-attraction in DNA DNA bases and their “complements”: Adenine (A) ----- Thymine (T) Guanine (G) ----- Cytosine (C) If DNA molecules (in a single strand) meet their complements (in another single strand), then the two strands will anneal (stick/coil together to form a double-helix). DNA computing: Basic operations Synthesize Prepare large numbers of copies of any short single DNA strand. Anneal Create a double strand from complementary single strands. Extract “Pull out” those DNA sequences containing a given pattern of length l (from a test tube). Detect Determine whether or not there are any DNA strands at all in a test tube. Amplify Replicate all (or selectively, some) of the DNA strands in a test tube. Hamiltonian Path Problem (HPP) Welling_ton Auck_land Ton_Dune Dune_din Land_Christ Church_Auck Christ_Church Church_Dune Church_Welling land _Dune Adleman’s experiment Auckland Wellington Christ Church Dunedin GGCTCGTT CCGAGCAA Dunedin CCGATACA GGCTATGT Wellington TGAACGTC ACTTGCAG Auckland AGCCTGAC TCGGACTG Christ Church Complement DNA name CITY TGACGGCT Christ Church-Dunedin TGACTGAA Christ Church-Auckland CCGAGGCT Wellington-Dunedin TGACCCGA Christ Church-Wellington CGTCAGCC Auckland-Christ Church CGTCGGCT Auckland-Dunedin DNA flight number FLIGHT Welling_ton Auck_land Ton_Dune Dune_din Land_Christ Church_Auck Christ_Church Church_Dune Church_Welling land _Dune Adleman’s experiment Welling_ton Auck_land Ton_Dune Dune_din Land_Christ Church_Auck Christ_Church Church_Dune Church_Welling land _Dune Adleman’s experimen