This is an old revision of the document!
Research lecture (CR)
Molecular programming: Theory & wet-lab experiments
Presentation
In this lecture, we will overview the various approaches to the uprising field of Molecular programming where one uses algorithms to design real molecules that processes information algorithmically. We will explore in details the various theoretical models, their complexity and expressiveness, learn how to program them and survey their experimental realizations, in particular how to design algorithmically these molecules for real. We will have you take part to real wet-lab experiments where we will design molecules executing a (simple) program for us and observe the nanoscopic result of their execution (usually only about few 100nm large) thru atomic force microscope (DNA origami) and fluorescence microscopy (DNA circuit). Wet-lab experiments will be conducted in collaboration with the biology & physics departments.
Outline
- DNA as information processing material
- Tile assembly model : Theory & experiments
- Strand displacement circuits: Theory & experiments
- Oritatami, a computational model for co-transcriptional folding: Theory & experiments
- Wetlab experiments: making a DNA origami from scratch, making a DNA strand displacement circuit from scratch
Schedule
- Thursdays morning (Room B1, ENS de Lyon Monod 4th floor)
- 8:45-10:45: Lecture
- (15 min break)
- 11:00-12:00: Exercises session
- Dates: 17/10, 24/10, 7/11 (learn how to design DNA orgami), 14/11 (vote for the origami to order for lab experiment), 21/11, 28/11 (wetlab experiments), 5/12, 12/12, 19/12, 9/1 14:00-16:00 (Final exam)
- No prior experience on experiments required
Internship proposals
- 2020 M2 Internship proposal: DNA computing: Theory, Models and wet lab experiments
Related resources
Past Lectures summary
Lecture 9 (2019.12.19 - Last): Oritatami Shapes & Strand displacement boolean circuits
- Oritatami: building shapes [ Slides ]
- The problem
- Some impossible shapes
- Scaling schemes
- Algorithm for scales Bn≥3
- Filling a pseudo-hexagon
- Bead type set for tight Oritatami systems
- Algorithm for scales An≥5
- Algorithm for scale A4
- Algorithm for scale A3
- Time anomalies and how to fix them
- Strand displacement boolean circuits [ Slides ]
Lecture 8 (2019.12.12): Oritatami: A computational model for co-transcriptional folding [ Slides A | Slides B ]
- RNA Origami experiments
- Oritatami model
- A binary counter
- Proving the correctness of the folding
- Tag system and Oritatami simulating Turing machine efficiently
- An Oritatami system simulating any Cellular Automaton
-
- Window movie lemma
- Oritatami
Lecture 7 (2019.12.05)
- L'an 01: [ mkv | passwd: an01 ]
Lecture 6 (2019.11.28): Wetlab Experiments
- Making an Origami [ Instructions ]
Lecture 5 (2019.11.21): Intrinsic universality in tile assembly [ Slides ]
- Intrinsic universality at T°2
- The supercell, the probes
- One (polygonal) tile is enough
Lecture 4 (2019.11.14): An experimental realisation of a universal computer (II) [ Slides ]
- Examples of nanotube circuits
- A 6-bits Turing universal nanotube circuit
- Minimizing errors with proof-reading tiles
- Counting the glues
- Sequence design
- Experiment results
Lecture 3 (2019.11.07):
- Useful stuff to install cadnano:
- Maya 2015:
- Linux: http://dl.free.fr/qySF9Q3Eh
- MacOS X: http://dl.free.fr/vLUy5QlY9
- Cadnano 2.2 for Maya 2015 (All platforms): http://dl.free.fr/iBgfRXG07
- standalone version for older MacOS X, you can try to install the all-in-one package for cadnano 2.2: cadnano2.2.pkg.zip (try this first!)
- Exercise sessions [ HW3 ]
- Making a DNA Origami
Lecture 2 (2019.10.24): Universality in assembly Model (I): Theory and experiment
- Universality in assembly Model (I) [ Slides ]
- Simulating a Turing machine at temperature T°=2 in aTAM
- Optimal hardcoding of a binary string at T°=2 in aTAM
- Simulating a Turing machine at temperature T°=1 in aTAM in 3D
- An experimental realisation of a universal computer (I) [ Slides ]
- Single stranded tile nanotubes
- Atomic Force Microscopy (AFM)
- Marking 0s and 1s using biotin-streptavidin
- kTAM kinetic assembly model
- Error correction using proof-reading tiles
- DNA nanotube circuit model
-
- Assembly time = O(rank of the produced shape) (from HW1)
- Exponential random variables and kTAM implementation
- Triangle tile assembly
- Tileset for simulating cellular automata (HW2: return your solution by email on or before Thursday Nov 7 at noon)
- Probabilistic simulation of Turing Machine at T°=1 in 2D
Lecture 1 (2019.10.17): Introduction to DNA programming & Tile Assembly Systems [ Slides ]
- Introduction to DNA programming & overview of the field
- Abstract tile assembly model (aTAM):
- Definition
- Minimizing the assembly time