Molecular programming: Theory & wet-lab experiments

For 2024-25, lectures will take place on Tuesdays at 15:45-17:45 and Fridays at 13:30-15:30.

First lecture on Tuesday September 10th, 2024 at 15:45-17:45

Next lecture (2/16) on Friday September 20th, 2024 at 13:30-15:30

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.

• 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

• The final grade will be the sum of HOMEWORK and EXAM both over 10 points
  FINAL_GRADE = HOMEWORK + EXAM
• HOMEWORK will be the sum of the grades for a set of 5 tiny exercices to solve from one week to the next
• EXAM = MINI-PROJECT + WRITTEN_EXAM where MINI-PROJECT is graded over 4pts et WRITTEN_EXAM is over 6pts
• MINI-PROJECT will be a mini-project to realize using ENSnano by groups of 3-5 people over about a month
• WRITTEN_EXAM will be a 1h30/2h-written exam at the end of the lecture

This grading system ensures that you will work and train regularly for the final exam and get the best grade possible.

• Tue Sep 10 (15:45-17:45) Lecture 1/16: Introduction to molecular programming [ slides | HW1 | Solutions ]
• Fri Sep 13 No Lecture
• Tue Sep 17 No Lecture
• Fri Sep 20 (13:30-15:30) Lecture 2/16: HW1 by Daria Pchelina
• Tue Sep 24 (15:45-17:45) Lecture 3/16: Universality in Abstract Tile Assembly Systems (aTAM) [ slides | HW2 | Solutions ]
• Fri Sep 27 No Lecture
• Tue Oct 1 (15:45-17:45) Lecture 4/16: Experimental realisation of a universal computer [ slides ]
• Fri Oct 4 (13:30-15:30) Lecture 5/16: How do we make origami (1/2) [ slides ]
• Tue Oct 8 (15:45-17:45) Lecture 6/16: How do we make origami (2/2) (mini-project presentation) [ miniprojects.pdf | mini-project files ]
• Fri Oct 11 (13:30-15:30) Lecture 7/16: Intrinsic universality in aTAM [ slides ] + mini-project + Oritatami 1/2 [ slides ]
• Tue Oct 15 (15:45-17:45) Lecture 8/16: Oritatami 2/2
• Fri Oct 18 (13:30-15:30) Lecture 9/16: DNA enzyme toolbox [ slides | Yannick Rondelez's talk video | DNA in action webinar | HW3 | Solutions ]
• Sun Oct 20 Return of your mini-project report + production
• Tue Oct 22 (15:45-17:45) Lecture 10/16 (mini-project defense)
• Fri Oct 25 (13:30-15:30) Lecture 11/16 Strand displacement [ slides | HW4 | Solutions ]
• Tue Oct 29 Holidays
• Fri Nov 1 Holidays
• Tue Nov 5 (15:45-17:45) Lecture 12/16: Update on the origami design ordered + Intrinsic universality in Turedos [ slides | article ]
• Fri Nov 8 (13:30-15:30) Lecture 13/16: Experiments I - lab work [ HW5 | Solutions | PCR ] room LE804
  La salle LE804 est tout au bout de l'allée B côté droit (biologie), une fois au bout de l'allée B, il faut aller tout au bout à gauche
• Tue Nov 12 (15:45-17:45) Lecture 14/16: Written exam
• Fri Nov 15 (13:30-17:30) Lecture 15+16/16: Experiments II: Atomic Force Microscopy imaging (Rooms B1 & AFM, located at the basement in front of the Foyer) Meeting point in room B1 - there will be a zoom link for watching the AFM room from the room B1

• 2025 M2 Internship proposal: DNA computing: Theory, Models and wet lab experiments

• http://perso.ens-lyon.fr/nicolas.schabanel/
• https://www.ens-lyon.fr/ensnano/
• http://molecular-programming.org/
• http://self-assembly.net/
• https://www.dietzlab.org/
• https://dna.hamilton.ie/woods/

• Tue 09.19 15:45 Lecture 1/16 - Introduction to molecular programming [ slides | HW1 ]
  
• Fri 09.22 13:30 Lecture 2/16 - aTAM: Tile assembly systems
  
• Tue 09.26 15:45 Lecture 3/16 - Universality in aTAM [ slides ]
  
• Fri 09.29 13:30 Lecture 4/16 - How do we make DNA origami [ slides ]
  
• Tue 10.03 15:45 Lecture 5/16 - Experimental realization of a universal computer with DNA nanotubes [ slides ]
  
• Fri 10.06 13:30 Lecture 6/16 - Intrinsic universality in aTAM [ slides | HW2 ]
  
• Tue 10.10 15:45 Lecture 7/16 - Oritatami [ slides | HW3 ]
  
• Fri 10.13 13:30 Lecture 8/16 - Oritatami simulates Turedo
  
• Tue 10.17 15:45 Lecture 9/16 - Universality in Turedos [ slides ]
  
• Fri 10.20 13:30 Lecture 10/16 - Strand displacements and DNA Boolean circuits [ slides ]
  
• Tue 10.24 15:45 Lecture 11/16 - PEN toolbox [ slides | Yannick Rondelez's talk video | DNA in action webinar ]
  
• Fri 10.27 13:30 Lecture 12/16: Mini-project presentation [ HW4 | pistol shrimp in action ]:
  
  • You are asked to address one of the three questions bellow in groups of 3-5 persons. A short report will be returned (at most 4 pages including illustrations). A short presentation will be given by each group on Friday Oct 27. We will discuss the proposed solutions together during that session. At the end of the session, we will vote for the best P01-design to be ordered, assembled and imaged at the end of the lecture.
  • [P01] Trapezoid with alpha-stacking: Add complementary protuberances and recessions on the ensnano file trapezoid.ens (the xover positions are not optimized). How to make sure that the pieces get together upright (and make a circle) and not upside down (which would assemble a line)?
  • [P02] Parametrized shape: Propose a framework that allows a parametrized definition of a multi-component flat 2D shape and propose an algorithm that solves the constraints (assuming a scaffold length) and positions the corresponding helices in ENSnano (beware that the scaffold must be routed within every helices). What kind of shapes can your algorithm solve? Show an execution of your algorithm on a small representative example. (no implementation asked)
  • [P03] Adapting helices parameters: you are given a shape that is supposed to assemble into a lattice (as for the P01-trapezoid), some helices are identified as “identical” as they are supposed to click one into the other. Propose a data structure and an algorithm that adjust the helices parameters (roll, rise, helicity) so that each pair of helices marked as identical matches. What kind of constraints can your algorithm solve? Show an execution of your algorithm on a small representative example. (no implementation asked)
• Tue 11.07 10:15 (exceptionally) Lecture 13/16
  
• Fri 11.10 13:30 Lecture 14/16 - Final written exam
  
• Tue 11.14 15:45 Lecture 15/16 - Lab experiments 1/2: mixing and cooking
  
• Fri 11.17 13:30 Lecture 16/16 - Lab experiments 2/2: AFM imaging

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 B_n≥3
  • Filling a pseudo-hexagon
  • Bead type set for tight Oritatami systems
  • Algorithm for scales A_n≥5
  • Algorithm for scale A₄
  • Algorithm for scale A₃
  • Time anomalies and how to fix them

• Strand displacement boolean circuits [ Slides ]
  • DNA Strand displacement mechanism
  • Some basic of thermodynamics [ Slides ]
  • Reading with fluophore
  • Dealing with leaks
  • Double long domain [ 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

• Exercise sessions [ HW4 ]
  1. Window movie lemma
  2. 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
    • Windows: (1) http://dl.free.fr/nzL3MS15h (2) http://dl.free.fr/hHQDyYA9A
  • Cadnano 2.2 for Maya 2015 (All platforms): http://dl.free.fr/iBgfRXG07
  • Installation instructions: MacOS X Windows Other
• 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 ]
  1. 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
• Exercise sessions [ HW2 ]
  1. Assembly time = O(rank of the produced shape) (from HW1)
  2. Exponential random variables and kTAM implementation
  3. Triangle tile assembly
  4. Tileset for simulating cellular automata (HW2: return your solution by email on or before Thursday Nov 7 at noon)
  5. 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
• Exercise sessions [ HW1 ]