Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-11-1 [2018/11/24 15:08]
schabanel [Course Summary: Molecular programming (Lectures 5-8)]
cours:c-2-11-1 [2019/11/01 15:25] (current)
schabanel [Approximation Algorithms& Molecular Algorithms(2019/2020, 8x3h, 3 ECTS)Wednesdays 8:45-11:45 Room SG1014]
Line 1: Line 1:
  
-===== **Approximation Algorithms\\ & Molecular Algorithms**\\ (2018/2019, 8x3h, 3 ECTS)\\ //Mondays 12:45-15:45 Room SG1004// =====+===== **Approximation Algorithms\\ & Molecular Algorithms**\\ (2019/2020, 8x3h, 3 ECTS)\\ //Wednesdays 8:45-11:45 Room SG1014// =====
  
----- +**<color green>Presumed dates for the lectures:</color>**\\ \\ 
- +** <color gray>Approximation algorithms</color> ** 
-**<color green>Dates for the next lectures:</color>** +  * <color gray>Lecture 1: Wed 11 SEP //Approximation algorithms 1/4//</color> 
-  * <color gray>Lecture 1: Mon 17 SEP //Approximation algorithms 1/4//</color> +  * <color gray>Lecture 2: Wed 18 SEP //Approximation algorithms 2/4//</color> 
-  * <color gray>Lecture 2: Mon 24 SEP //Approximation algorithms 2/4//</color> +  * <color gray>Lecture 3: Wed 25 SEP //Approximation algorithms 3/4//</color> 
-  * <color gray>Lecture 3: Mon 1 OCT //Approximation algorithms 3/4//</color> +  * <color gray>Lecture 4: Wed 2 OCT //Approximation algorithms 4/4//</color> 
-  * <color gray>Lecture 4: Mon 8 OCT //Approximation algorithms 4/4//</color> +** <color gray>Molecular programming</color> ** 
-  * <color gray>//No lecture on Mon 15 OCT//</color> +  * <color gray>Lecture 5: Wed 9 OCT //Molecular algorithms 1/4//</color> 
-  * <color gray>Lecture 5: Mon 22 OCT //Molecular algorithms 1/4//</color> +  * <color gray>Lecture 6: Wed 16 OCT //Molecular algorithms 2/4//</color> 
-  * <color gray>Lecture 6: Mon 29 OCT //Molecular algorithms 2/4//</color> +  * <color gray>Lecture 7: Wed 23 OCT //Molecular algorithms 3/4//</color> 
-  * <color gray>Lecture 7: Mon 5 NOV //Molecular algorithms 3/4//</color> +  * <color gray>// No lecture on Wed 30 OCT //</color> 
-  * <color gray>Lecture 8: Mon 12 NOV //Molecular algorithms 4/4//</color> +  * Lecture 8: Wed 6 NOV //Molecular algorithms 4/4// 
-  * <color gray>//No lecture on Mon 19 NOV//</color> +** <color gray>Final exam</color> ** 
-  * <color purple>**Final Exam: Mon 26 NOV**</color>+  * <color gray>// No lecture on Wed 13 and 20 OCT //</color> 
 +  * <color red>**Final Exam: Wed 27 NOV 8:45-11:45**</color>
  
 ---- ----
Line 23: Line 24:
   * [[http://www.di.ens.fr/~cchuang/|Chien-Chung Huang]] ([[http://www.cnrs.fr/ins2i/|CNRS]] - [[http://www.di.ens.fr/|DIENS]]): //Approximation Algorithms//   * [[http://www.di.ens.fr/~cchuang/|Chien-Chung Huang]] ([[http://www.cnrs.fr/ins2i/|CNRS]] - [[http://www.di.ens.fr/|DIENS]]): //Approximation Algorithms//
  
-//**<color blue>Note that there will be __no intersection__ with [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-1-24|Course 1.24]].</color>**//+Lectures will take place every **Wednesdays 08:45-11:45 in room SG1014** starting on 11/9. 
  
-Lectures will take place every **Mondays 12:45-15:45 in room SG1004** starting on 17/9+---- 
 + 
 +Internship proposals: 
 +  * :!: **__2020 M2 Internship proposal:__ [[http://perso.ens-lyon.fr/nicolas.schabanel/stage/2020_M2_Internship.pdf|DNA computing: Theory, Models and wet lab experiments]]** 
 + 
 +----
  
 ==== Goals ==== ==== Goals ====
Line 74: Line 80:
   * Data Streams: Algorithms and Applications (Foundations and Trends in Theoretical Computer Science). S. Muthukrishnan. Now Publishers Inc, 2005.   * Data Streams: Algorithms and Applications (Foundations and Trends in Theoretical Computer Science). S. Muthukrishnan. Now Publishers Inc, 2005.
  
-There are no lecture notes. The lectures will be give on the board. Students will be encourage to write down lecture notes that will be made later available to everyone.+There are no lecture notes. The lectures will be given on the board. Students will be encouraged to write down lecture notes that will be made later available to everyone.
 Some additional reading will be suggested during the course. Some additional reading will be suggested during the course.
      
Line 113: Line 119:
   * [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-11-1|2.11.1 Approximation Algorithms & molecular programming]]   * [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-11-1|2.11.1 Approximation Algorithms & molecular programming]]
   * [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-19|2.19 Biochemical Programming]]   * [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-19|2.19 Biochemical Programming]]
- 
-==== Course Summary: Molecular programming  (Lectures 5-8) ==== 
  
 Some related research articles: Some related research articles:
Line 131: Line 135:
   * Oritatami:   * Oritatami:
     * [[http://perso.ens-lyon.fr/nicolas.schabanel/publications/2018/2018-ISAAC-OritatamiTuring-GearyMeunierSchabanelSeki.pdf|Oritatami is Turing universal]]      * [[http://perso.ens-lyon.fr/nicolas.schabanel/publications/2018/2018-ISAAC-OritatamiTuring-GearyMeunierSchabanelSeki.pdf|Oritatami is Turing universal]] 
-    * [[http://perso.ens-lyon.fr/nicolas.schabanel/publications/2018/2018-DNA24-OritatamiShapes-DemaineHendricksOlsenPatitzRogersSchabanelSekiThomas.pdf|Shapes in Oritatami]] +    * [[http://perso.ens-lyon.fr/nicolas.schabanel/publications/2018/2018-DNA24-OritatamiShapes-DemaineHendricksOlsenPatitzRogersSchabanelSekiThomas.pdf|Shapes in Oritatami]] 
 +==== Course Summary 2019-20: Molecular programming  (Lectures 5-8) ====
  
-**Lecture 8: Oritatami: A computational model for cotranscriptional molecular folding [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4.pdf|Slides]] ]**+**Lecture 7 (2019.10.23)Universality in assembly Model (II): experiment, intrinsic universality and Oritatami** 
 +  * **An experimental realisation of a universal computer (II) [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture2B.pdf|Slides (again)]] ]** 
 +    * Examples of nanotube circuits 
 +    * 6-bits Turing universal nanotube circuit 
 +    * Minimizing errors with proof-reading tiles 
 +    * Counting the glues 
 +    * Sequence design 
 +    * Experiment results 
 +  * **Intrinsic Universality in tile assembly model [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture3A.pdf|Slides]] ]** 
 +    * Intrinsic universality at T°2 
 +    * The supercell, the probes 
 +    * One (polygonal) tile is enough 
 +  * **Oritami: a computational model for co-transcriptional folding [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture3B.pdf|Slides]] ]** 
 +    * RNA co-transcriptional folding 
 +    * Oritatami model 
 +    * A first example: a binary counter 
 +    * Proving its correctness 
 +    * Rule design is NP-hard but FP-tractable 
 +    * Oritatami is Turing complete 
 +    * Simple intrinsic Oritatami simulation of cellular automata 
 +  * **Exercise sessions [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW3.pdf|HW3]] ]** 
 +    - :!: Window movie Lemma //**return your solution to questions 1.1 and 1.2 by Wed Nov 6 before 11:45**//
  
-Movies & animations: [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/RNAfolding.mov|RNA folding (slide 11)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-step1.gif|Oritatami step 1 (slide 15)]] [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-step2.gif|(slide 21)]] [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-several-max.gif|3 (slide 25)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-counter.mp4|Oritatami counter (slide 30)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/ModuleG.mp4|Module G (slide 102)]] ]+**Lecture 6 (2019.10.16)Universality in assembly Model (I): Theory and experiment** 
 +  * **Universality in assembly Model (I) [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture2A.pdf|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°=in aTAM in 3D 
 +  * **An experimental realisation of a universal computer (I[[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture2B.pdf|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 [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW2.pdf|HW2]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW2-SOL.pdf|Solutions]] ]** 
 +    Staged self-assembly (from HW1) 
 +    - Exponential random variables and kTAM implementation 
 +    - :!: Tileset for simulating cellular automata   
 +    - Probabilistic simulation of Turing Machine at T°=1 in 2D
  
-  * **Co-transcriptional RNA folding experiment** +**Lecture (2019.10.09): Introduction to DNA programming & Tile Assembly Systems [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture1.pdf|Slides]] ]**
-  * **Oritatami** +
-    * The model +
-    * A binary counter +
-    * Proving the binary counter +
-  * **Complexity** +
-    * NP-hardness of the rule design problem +
-    * Fixed parameter linear-time algorithm of the rule design problem +
-  * **Efficient Turing machine simulation in oritatami** +
-    * Skipping cyclic tag systems (SCTS) +
-    * Simulating SCTS with oritatami +
-    * Proving the correctness of the simulation +
-    * Oritatami programming toolbox: switchback/glider, offsets, exponential coloring & socks +
-    * Proving the correctness of the implementation +
-  * **Exercise sessions** +
-      - HW2 exercise 1       +
-      - HW3 exercise 2 +
- +
-**Lecture 7: Strand Displacement** +
-  * **Boolean circuits using Strand displacement [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture3.pdf|Slides (by Chris Thachuk)]] ]** +
-    * Making an AND gate: rough computation of energy and entropy deltas +
-    * Composing gates: making a wire +
-    * Reading the result optically: fluorophore and quencher +
-    * Implementing a reaction gate +
-    * Implementing monotonic gates (AND and OR) +
-    * Handling NOT gates with dual rails +
-    * Moving NOT gates to the top +
-    * Robustness: preventing leaking: +
-      * Fixing molecular synthesis imperfection +
-      * Using double long domains (DLD) +
-    * Presenting Breadboard 1.0 +
-  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW3.pdf|HW3]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW3-SOL.pdf|Solutions]] ] +
-      - :!: **DNA circuits (Assignment to return on Monday 12/11 before 12:45)**  +
-      - Building shapes with oritatami +
- +
-**Lecture 6: Universality in assembly models & Introduction to Strand displacement** +
-  * **Universality in assembly models [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture2A.pdf|Slides A]] ]** +
-    * aTAM simulate Turing machines at temperature T=2 +
-    * Optimal seed encoding at T=2: Kolmogorov complexity & unpacking +
-    * aTAM simulate Turing machines at temperature T=1 in 3D but not 2D +
-    * Intrinsic universality of aTAM at temperature T=2 +
-    * One (polygonal) tile is enough! +
-  * **Introduction to Strand displacement [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture2B.pdf|Slides B (by Chris Thachuk)]] ]** +
-  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW2.pdf|HW2]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW2-SOL.pdf|Solutions]] ] +
-    - Tileset for simulating cellular automata +
-    - Probabilistic simulation of Turing machine at temperature T=1 in 2D +
-    - :!: **Window movie lemma (Assignment to return on Monday 5/11 before 12:45: solve questions 3.1 and 3.2)**  +
- +
-**Lecture 5: Introduction to DNA programming & Tile Assembly Systems [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture1.pdf|Slides]] ]**+
   * Introduction to DNA programming & overview of the field   * Introduction to DNA programming & overview of the field
   * Abstract tile assembly systems:   * Abstract tile assembly systems:
     * Definition     * Definition
     * Minimizing the assembly time     * Minimizing the assembly time
-  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW1.pdf|HW1]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW1-SOL.pdf|Solutions]] ]+  * **Exercise sessions [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW1.pdf|HW1]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW1-SOL.pdf|Solutions]] ]**
     - Guess the assembly 1     - Guess the assembly 1
     - Guess the assembly 2     - Guess the assembly 2
-    - **:!: A binary counter (Assignment to return on Monday 29/10 before 12:45)** +    - :!: A binary counter
     - Staged self-assembly     - Staged self-assembly
     - Assembly time = O(rank of the produced shape)     - Assembly time = O(rank of the produced shape)
-    - Minimum number of tiles self-assembling squares and rectangle 
  
-==== Course Summary: Approximation algorithms  (Lectures 1-4) ====+ 
 +==== Course Summary 2019-20: Approximation Algorithms  (Lectures 1-4) ==== 
 + 
 +**Lecture 1: Introduction ** 
 +  * Introduction to Approximation Algorithms & overview of the field 
 +  * Examples of Combinatorial/LP-Based/Randomized Algorithms for NP-hard Problems 
 +  * Min-Cut Algorithm of Karger 
 +  * First Assignment [[http://www.di.ens.fr/~cchuang/devoirs_aama_2019/premier.pdf|PDF]] 
 +  
 + 
 +**Lecture 2: Chernoff Bounds ** 
 +  * Christofides' TSP algorithm 
 +  * Chernoff Bounds 
 +  * Integer Multi-commodity Flow 
 +  * 3-Coloring Dense Graphs 
 +  * Second Assignment [[http://www.di.ens.fr/~cchuang/devoirs_aama_2019/deuxieme.pdf|PDF]] 
 + 
 +**Lecture 3: Random Walk and Submodular Function **  
 +  * 2SAT 
 +  * K-Coverage  
 + 
 +**Lecture 4: Semi-Definitie Programming **  
 +  * Max-Cut 
 +  * Color-Coding 
 +  * Vertex-Cover Revisited 
 +  * Third Assignment [[http://www.di.ens.fr/~cchuang/devoirs_aama_2019/troiseme.pdf|PDF]]   
 +   
 +===== **Archives 2018-2019 (8x3h)** ===== 
 +==== Course Summary 2018-19: Approximation algorithms  (Lectures 1-4) ====
  
 **Lecture 1 Introduction to Randomised and Approximation Algorithms** **Lecture 1 Introduction to Randomised and Approximation Algorithms**
Line 225: Line 246:
   * Max-Cut   * Max-Cut
   * Color-Coding and Vertex-Feedback Set   * Color-Coding and Vertex-Feedback Set
 +
 +==== Course Summary 2018-19: Molecular programming  (Lectures 5-8) ====
 +
 +**Lecture 5: Introduction to DNA programming & Tile Assembly Systems [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture1.pdf|Slides]] ]**
 +  * Introduction to DNA programming & overview of the field
 +  * Abstract tile assembly systems:
 +    * Definition
 +    * Minimizing the assembly time
 +  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW1.pdf|HW1]] ]
 +    - Guess the assembly 1
 +    - Guess the assembly 2
 +    - :!: A binary counter
 +    - Staged self-assembly
 +    - Assembly time = O(rank of the produced shape)
 +    - Minimum number of tiles self-assembling squares and rectangle
 +
 +
 +
 +
 +**Lecture 6: Universality in assembly models & Introduction to Strand displacement**
 +  * **Universality in assembly models [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture2A.pdf|Slides A]] ]**
 +    * aTAM simulate Turing machines at temperature T=2
 +    * Optimal seed encoding at T=2: Kolmogorov complexity & unpacking
 +    * aTAM simulate Turing machines at temperature T=1 in 3D but not 2D
 +    * Intrinsic universality of aTAM at temperature T=2
 +    * One (polygonal) tile is enough!
 +  * **Introduction to Strand displacement [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture2B.pdf|Slides B (by Chris Thachuk)]] ]**
 +  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW2.pdf|HW2]] ]
 +    - Tileset for simulating cellular automata
 +    - Probabilistic simulation of Turing machine at temperature T=1 in 2D
 +    - :!: Window movie lemma
 +
 +**Lecture 7: Strand Displacement**
 +  * **Boolean circuits using Strand displacement [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture3.pdf|Slides (by Chris Thachuk)]] ]**
 +    * Making an AND gate: rough computation of energy and entropy deltas
 +    * Composing gates: making a wire
 +    * Reading the result optically: fluorophore and quencher
 +    * Implementing a reaction gate
 +    * Implementing monotonic gates (AND and OR)
 +    * Handling NOT gates with dual rails
 +    * Moving NOT gates to the top
 +    * Robustness: preventing leaking:
 +      * Fixing molecular synthesis imperfection
 +      * Using double long domains (DLD)
 +    * Presenting Breadboard 1.0
 +  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW3.pdf|HW3]] ]
 +      - :!: DNA circuits
 +      - Building shapes with oritatami
 +
 +
 +**Lecture 8: Oritatami: A computational model for cotranscriptional molecular folding [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4.pdf|Slides]] ]**
 +
 +Movies & animations: [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/RNAfolding.mov|RNA folding (slide 11)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-step1.gif|Oritatami step 1 (slide 15)]] [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-step2.gif|2 (slide 21)]] [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-several-max.gif|3 (slide 25)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-counter.mp4|Oritatami counter (slide 30)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/ModuleG.mp4|Module G (slide 102)]] ]
 +
 +  * **Co-transcriptional RNA folding experiment**
 +  * **Oritatami**
 +    * The model
 +    * A binary counter
 +    * Proving the binary counter
 +  * **Complexity**
 +    * NP-hardness of the rule design problem
 +    * Fixed parameter linear-time algorithm of the rule design problem
 +  * **Efficient Turing machine simulation in oritatami**
 +    * Skipping cyclic tag systems (SCTS)
 +    * Simulating SCTS with oritatami
 +    * Proving the correctness of the simulation
 +    * Oritatami programming toolbox: switchback/glider, offsets, exponential coloring & socks
 +    * Proving the correctness of the implementation
 +  * **Exercise sessions**
 +      - HW2 exercise 1      
 +      - HW3 exercise 2
 +
  
 ===== **Archives 2017-2018 (8x3h)** ===== ===== **Archives 2017-2018 (8x3h)** =====
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA