Time & Place:  Second term, 2001, Beckman Institute 23, Tuesdays, 5:30-7:00pm.  Pizza provided.

Plan:  We will read roughly 40 papers on the physics of computation, biochemical and cellular computation,
DNA nanotechnology and DNA computing.    Students will present the papers in class, and will write a final paper.

Objectives: To identify key concepts and results in the readings, understand and illustrate them using simple examples, critique the limitations of the results, and brainstorm.  Students should not attempt to present all aspects of the all papers, but rather should choose one or two key issues and explore them in detail during the presentation.   The presenter should assume that everyone in the class has read the required readings (but maybe doesn't fully understand it yet).

Grading will be based on (1) participation in class discussions, including 3 short discussion questions (less than 1 page, typed) handed in before each class, (2) presentation of an article, (3) a 5-page final paper investigating a topic discussed in the class.

Office hours: Moore 204, Tuesdays, 2:30-3:30pm
Pre-presentation discussion (one week ahead): Moore 204, Tuesdays, 2:00-2:30pm

Topics:

Jan 9:  Physics of computation: energy and reversibility [Ben Rahn and Joseph Schaeffer]

Jan 16: Cellular computing:  chemotaxis, biochemical networks [Chris Hart and Ewa Matejska]

Jan 23:  Genetic regulatory networks: models and synthetic design [Ryan Mackey and Roger Revilla]

Jan 30:  Synthetic biochemical systems: predator-prey, simulations, noise, and robustness [Jongmin Kim and Paul Rothemund]

Feb 6:  In vitro evolution of DNA and RNA [Leila Reddy and Rory Sayres]

Feb 13: DNA computing for combinatorial search [Geoffrey Hom and Matt Cook]

Feb 20: Thermodynamics and kinetics of DNA hybridization and folding [Ben Rahn and Caglar Tanrikulu]

Feb 27: Molecular engineering and DNA nanotechnology: DNA structures, beacons, tweezers, and catalysts [Ryan Mackey and Leila Reddy]

Mar 6: Computation by molecular self-assembly and molecular folding [Geoffrey Hom and Matt Cook]

Mar 16: No class... final paper due.

Papers:

Jan 9: Physics of Computation

• R. Landauer, "Irreversibility and Heat Generation in the Computing Process." IBM J. Res. Develop. 3: 183-191 (1961).
• C. H. Bennett, "Logical Reversibility of Computation."  IBM J. Res. Develop. 17: 525-532 (1973).
• C. H. Bennett, "The Thermodynamics of Computation -- a Review." Int. J. Theor. Phys. 21: 905-940 (1982).
• (optional) E. Fredkin and T. Toffoli, "Conservative Logic." Int. J. Theor. Phys. 21: 219-253 (1982).
• (optional) C. H. Bennett, "Time/Space Trade-offs for Reversible Computation." SIAM J. Comput. 18: 766-776 (1989).
• (optional -- overlaps with #3 but better figures) C. H. Bennett and Rolf Landauer, "The Fundamental Physical Limits of Computation," Scientific American, (198?)

D. Bray, "Protein Molecules as Computational Elements in Living Cells." Nature. 376: 307-312 (1995).

D. C. Hauri and J. Ross, "A Model of Excitation and Adaptation in Bacterial Chemotaxis." Biophysical Journal 68: 708-722 (1995).

M. O. Magnasco, "Chemical Kinetics is Turing Universal." Phys. Rev. Let. 78: 1190-1193 (1997).

A. Hjelmfelt, E. D. Weinberger, and J. Ross, "Chemical Implementation of Neural Networks and Turing Machines." Proc. Natl. Acad. Sci. USA88: 10983-10987 (1991).

(optional) A. Hjelmfelt and J. Ross, "Chemical Implementation and Thermodynamics of Collective Neural Networks." Proc. Natl. Acad. Sci. USA 89: 388-391 (1992).

• R. Weiss, G. H. Homsy, and T. F. Knight, Jr., "Toward in vivo Digital Circuits."  Proceedings of DIMACS Workshop on Evolution as Computation (1999).
• M. B. Elowitz and S. Leibler, "A Synthetic Oscillatory Network of Transcriptional Regulators." Nature 403: 335-338 (2000).
• T. S. Gardner, C. R. Cantor, and J. J. Collins, "Construction of a Genetic Toggle Switch in Escherichia coli." Nature 403: 339-342(2000).
• (optional) R. Weiss and T. F. Knight, Jr., "Engineerings Communications for Microbial Robotics." Proceedings of the Sixth International Meeting on DNA-Based Computers (2000).
• (optional) C. H. Yuh, H. Bolouri, and E. H. Davidson, "Genomic Cis-Regulatory Logic: Experimental and Computational Analysis of a Sea Urchin Gene." Science279: 1896-1902 (1998).

• B. Wlotzka and J. S. McCaskill, "A Molecular Predator and Its Prey: Coupled Isothermal Amplification of Nucleic Acids." Chemistry and Biology 4: 25-33 (1997).
• J. Ackermann, B. Wlotzka, and J. S. McCaskill, "In vitro DNA-based Predator-Prey Systems with Oscillatory Kinetics."  Bull. Math. Biol. 60: 329-353 (1998).
• H. H. McAdams and A. Arkin, "Stochastic Mechanisms in Gene Expression." Proc. Natl. Acad. Sci. USA 94: 814-819 (1997).
• N. Barkai and S. Leibler, "Circadian Clocks Limited by Noise." Nature403: 267-268 (2000).
• (optional) M. A. Gibson and J. Bruck, "Efficient Exact Stochastic Simulation of Chemical Systems with Many Species and Many Channels." J. Phys. Chem. A 104: 1876-1889 (2000).

Feb 6:  In vitro evolution of DNA and RNA

• D. R. Mills, R. L. Peterson, and S. Spiegelman, "An Extracellular Darwinian Experiment with a Self-Duplicating Nucleic Acid Molecule." Proc. Natl. Acad. Sci. USA 58: 217-224 (1967).
• D. P. Bartel and J. W. Szostak, "Isolation of New Ribozymes from a Large Pool of Random Sequences." Science 261: 1411-1418 (1993).
• W. P. C. Stemmer, "DNA Shuffling by Random Fragmentation and Reassembly: In vitro Recombination for Molecular Evolution." Proc. Natl. Acad. Sci. USA 91: 10747-10751 (1994).
• (optional) R. R. Breaker and G. F. Joyce, "Emergence of a Replicating Species from an in vitro RNA Evolution Reaction."  Proc. Natl. Acad. Sci. USA 91: 6093-6097 (1994).
• M. C. Wright and G. F. Joyce, "Continuous in vitro Evolution of Catalytic Function." Science 276: 614-617 (1997).
• (optional) R. R. Breaker and G. F. Joyce, "A DNA Enzyme that Cleaves RNA." Chemistry and Biology 1: 223-229 (1994).
• (optional) M. Eigen, J. McCaskill, and P. Schuster, "Molecular Quasi-Species." J. Phys. Chem. 92: 6881-6891 (1988).

• L. M. Adleman, "Molecular Computation of Solutions to Combinatorial Problems." Science 266: 1021-1023 (1994).
• D. Boneh, C. Dunworth, R. J. Lipton, and J. Sgall, "On the Computational Power of DNA." Discr. Appl. Math. 71: 79-94 (1996).
• R. S. Braich, C. Johnson, P. W. K. Rothemund, D. Hwang, N. Chelyapov, and L. M. Adleman, "Solution of a Satisfiability Problem on a Gel-Based DNA Computer." Proceedings of the Sixth International Meeting on DNA-Based Computers (2000).
• (optional) K. Chen and E. Winfree, "Error Correction in DNA Computing: Misclassification and Strand Loss."  Pages 49-63 in E. Winfree, D. Gifford (eds.) DNA Based Computers V, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Providence, RI. American Mathematical Society (2000).
• (optional) K. Chen and V. Ramachandran, "A Space-Efficient Randomized DNA Algorithm for k-SAT." Proceedings of the Sixth International Meeting on DNA-Based Computers (2000).

• J. SantaLucia, Jr., "A Unified View of Polymer, Dumbell, and Oligonucleotide DNA Nearest-Neighbor Thermodynamics."   Proc. Natl. Acad. Sci. USA 95: 1460-1465 (1998).
• B. Yurke and A. Mills, Jr., "Toehold-Enhanced DNA Strand Exchange: Fuel for Nanomachines."  Preprint (1998).
• M. Zuker and P. Stiegler, "Optimal Computer Folding of Large RNA Sequences using Thermodynamics and Euxiliary Information."  Nucleic Acids Research 9: 133-148 (1981).
• C. Flamm, W. Fontana, I. L. Hofacker, P. Schuster, "RNA Folding at Elementary Step Resolution."  RNA 6: 325-338 (2000).
• I. Biswas, A. Yamamoto, and P. Hsieh, "Branch Migration Through DNA Sequence Heterology."  J. Mol. Biol. 279: 795-806 (1998).

• K. E. Drexler, "Molecular Engineering: An Approach to the Development of General Capabilities for Molecular Manipulation." Proc. Natl. Acad. Sci. USA 78: 5275-5278 (1981).
• G. M. Whitesides, J. P. Mathias, C. T. Seto, "Molecular Self-Assembly and Nanochemistry: A Chemical Strategy for the Synthesis of Nanostructures." Science 254: 1312-1319 (1991).
• N. Seeman et. al., "New Motifs in DNA Nanotechnology." Nanotechnology 9: 257-273 (1998).
• G. Bonnet, S. Tyagi, A. Libchaber, and F. R. Kramer, "Thermodynamic Basis of the Enhanced Specificity of Structures DNA Probes." Proc. Natl. Acad. Sci. USA 96: 6171-6176 (1999).
• A. J. Turberfield, B. Yurke, and A. P. Mills, Jr., "DNA Hybridization Catalysts and Molecular Tweezers." Pages 171-182 in E. Winfree, D. Gifford (eds.) DNA Based Computers V, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Providence, RI. American Mathematical Society (2000).
• B. Yurke, A. J. Turberfield, A. P. Mills, Jr., F. G. Simmel, and J. L. Neumann, "A DNA-Fuelled Molecular Machine Made of DNA."  Nature406: 605-608 (2000).

• E. Winfree, "Whiplash PCR for O(1) Computing."  Proceedings of the Fourth International Meeting on DNA-Based Computers (1998).
• K. Komiya, K. Sakamoto, H. Gouzu, S. Yokoyama, M. Arita, A. Nishikawa, and M. Hagiya, "Successive State Transitions with I/O Interface by Molecules." Proceedings of the Sixth International Meeting on DNA-Based Computers (2000).
• K. Sakamoto, H. Gouzu, K. Komiya, D. Kiga, S. Yokoyama, T. Yokomori, and M. Hagiya, "Molecular Computation by DNA Hairpin Formation."  Science288: 1223-1226 (2000).
• E. Winfree, F. Liu, Lisa A. Wenzler, and N. C. Seeman, "Design and Self-Assembly of Two-Dimensional DNA Crystals."  Nature 394: 539-544 (1998).
• M. G. Lagoudakis and T. H. LaBean, "2D DNA Self-Assembly for Satisfiability." Pages 141-154 in E. Winfree, D. Gifford (eds.) DNA Based Computers V, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Providence, RI. American Mathematical Society (2000).
• C. Mao, T. H. LaBean, J. H. Reif, and N. C. Seeman, "Logical Computation using Algorithmic Self-Assembly of DNA Triple-Crossover Molecules."  Nature 407: 493-496 (2000).
• (optional) R. M. Robinson, "Undecidability and Nonperiodicity for Tilings of the Plane."  Inventiones Math. 12: 177-209 (1971).
• (optional) W. P. C. Stemmer, A. Crameri, K. D. Ha, T. M. Brennan, and H. L. Heyneker, "Single-Step Assembly of a Gene and Entire Plasmid from Large Numbers of Oligodeoxyribonucleotides."  Gene 164: 49-53 (1995).