Conférence CoA 2014: Algorithmes Naturels et Complexité 🧠

troisièmes journées du GT CoA Complexité et Algorithmes :
Algorithmes naturels
du mercredi 10 septembre 12h30 au vendredi 12 septembre 13h30, Université Paris Diderot
LIAFA, Salle 1009, Bâtiment Sophie Germain Paris 13ème

9:00-9:40 - Shinnosuke SEKI (U. Aalto)
DNA pattern-assembly: introduction and recent breakthroughs

Self-assembly is a process through which disorganized, relatively simple components autonomously coalesce according to local rules to form more complex target structures, in the absence of orders from an external global conductor. DNA self-assembly can produce various nanoscale structures experimentally, including regular arrays, fractal structures, smiley faces, logic circuits, and molecular robots. In particular, pattern-assembly aims at allocating molecular components on a 2D-array according to a given layout called pattern. A long-standing open problem (PATS) is about the complexity of optimizing the design of DNA self-assembly system that self-assembles a given pattern. In this talk, an overview is given about DNA pattern-assembly, a mathematical model for that, and PATS. Recent breakthroughs on PATS are also reported, including a computer-assisted proof for the open problem.