ER02: MOLECULAR PROGRAMMING
Theory & Wet Lab Nano-Scale Computation

Monday January 16 to Friday January 20, 2017
at ENS Lyon Computer Science Department

Origanised in collaboration with the Biology Department and the Physics Lab at ENS Lyon

Intervenants:

• Ludovic BELLON (ENS Lyon)
• Cendrine MOSKALENKO (ENS Lyon)
• Yannick RONDELEZ (CNRS, ESPCI)
• Nicolas SCHABANEL (CNRS, U. Paris Diderot & ENS Lyon)
• Damien WOODS (Inria Paris)

Lab coordinator: Florence LORMIÈRES (Biology Dept, ENS Lyon)

Organisateur: Nicolas Schabanel

53 Registered Participants: List

Schedule

• Discrete computation using DNA tiles [ Part 1 ]
• Analog computation using DNA strands to implement numerical partial differential equations [ Part 2 ]

Requirements

Evaluation

• Lectures
• Exercise sessions where we will practice and develop the tools required to design the experiments that we will run
• Wet-lab experiments & observation where we will run the experiments designed in the exercice sessions

• A final exam checking for the main concepts developed in the lectures
• The presentation of a small project (one per group of 4-5 persons) consisting of designing an experiment by computer. It will developed during the exercice sessions

Registration

Registration are now closed.
Students in M1IF and M2IF at ENS Lyon can still register and must contact Anne Benoit or Daniel Hirschkoff to register.

Part 1 - Computing with molecules: Algorithmic self-assembly and Boolean circuit computation with DNA tiles

Instructors: Damien WOODS & Nicolas SCHABANEL

It turns out that molecules compute. By this we mean that it is possible to design molecules so that they sort numbers or simulate Turing machines or carry out other complicated nanoscale tasks that are best described as algorithms.

In the first part of the course we will give an overview of the state of the art in computing with molecules. This begins with some theoretical models of computation that are used to think about molecular computation in a clear way. Then we will give an overview of various experimental wet-lab implementations of DNA-based molecular computers including tile-based algorithmic systems that implement cellular automata and DNA strand displacement systems that implement Boolean circuits and chemical reaction networks.

We will cover our recent theoretical and experimental work on designing and implementing a set of 356 self-assembling DNA tiles that implement any one of 2⁴⁴ 6-bit Boolean circuits (by Woods, Doty, Myhrvold, Hui, Zhou, Yin, Winfree). The programmer first specifies a 6-bit input string encoded in a cylindrical-shaped "DNA seed" structure, then chooses a subset of 89 or more DNA tiles so that they begin attaching to the seed, self-assembling into a cylindrical nanotube lattice that simulates a Boolean circuit as it grows. We will see how this algorithmic growth process implements any one of a suite computations, such as bit copying, bit sorting, telling if an input string is a palindrome or represents a multiple of three in binary, randomised algorithms, cute patterns, leader election, and even simulation of the Turing-universal cellular automaton Rule 110. As part of the course students will learn how to program DNA molecules to implement Boolean circuits of their choice, and get to see circuits implemented in the wet-lab!

Then we will change focus to some recent theoretical results on algorithmic self-assembly with tiles. We will use the notion of simulation between tile assembly systems to tease apart their relative expressive power. We will show that there is a single "intrinsically universal" tile set capable of simulating any instance of the abstract tile assembly model. Then an overview of results on the relative power of such models will be given. Finally we will show, that if we allow square tiles to bind using only one of their sides (noncooperative, or temperature 1 binding) then these can not simulate the more general abstract tile assembly model.

As part of the course students will learn how to program DNA molecules to implement Boolean circuits of their choice, and get to see circuits implemented in the wet-lab!

Part 2 - Bio-inspired DNA circuits

Instructor: Yannick RONDELEZ

A cell, for example a bacterium, needs to compute a myriad of functions in order to integrate internal or external signals and make decisions: when to divide, where to go, which compounds to express, etc. These cellular computations are done with local means -molecules- and the array of reactions and interactions that link them together. This computing architecture is known as an out-of-equilibrium “reaction network”. Similar to electronic circuits, there is a direct link between the structure (topology, dynamics) of the reaction network and the function it performs.

At the beginning of the course, I will show that reaction networks implement complex control or information-processing tasks in cells. I will then explain that artificial equivalent can be built in test tubes, targeting specific dynamics or computations. We will see how DNA-based molecular programming provide an approach to control the topology and dynamics of a system of cross interacting molecules. I will review some approaches that can be used to create wet, amorphous molecular systems with exotic behaviors. Finaly we will focus on one particular implementation, where the famous Predator-Prey oscillating system is simulated in a test tube. We will see how to design synthetic pieces of DNA oligonucleotides so that they reproduce the fundamental interactions of a minimal ecosystem: prey reproducing exponentially, predators consuming them, growing, and eventually dying. We will DNA-code the circuit in test tubes and check if the molecular populations actually reproduce the predator-prey cycles observed for the real ecosystem.