05 June 2018

Séminaire CANA: Folding shapes with oritatami systems, Nicolas Schabanel

Abstract: An oritatami system (OS) is a theoretical model of self-assembly via co-transcriptional folding. It consists of a growing chain of beads which can form bonds with each other as they are transcribed. During the transcription process, the $delta$ most recently produced beads dynamically fold so as to maximize the number of bonds formed, self-assemblying into a shape incrementally. The parameter $delta$ is called the emph{delay} and is related to the transcription rate in nature. This article initiates the study of shape self-assembly using oritatami. A shape is a connected set of points in the triangular lattice. We first show that oritatami systems differ fundamentally from tile-assembly systems by exhibiting a family of infinite shapes that can be tile-assembled but cannot be folded by any OS. As it is NP-hard in general to determine whether there is an OS that folds into (self-assembles) a given finite shape, we explore the folding of upscaled versions of finite shapes. We show that any shape can be folded from a constant size seed, at any scale $ngeq 3$, by an OS with delay $1$. We also show that any shape can be folded at the smaller scale $2$ by an OS with emph{unbounded} delay. This leads us to investigate the influence of delay and to prove that there are shapes that can be folded (at scale~$1$) with delay $delta$ but not with delay $delta' 2$. These results serve as a foundation for the study of shape-building in this new model of self-assembly, and have the potential to provide better understanding of cotranscriptional folding in biology, as well as improved abilities of experimentalists to design artificial systems that self-assemble via this complex dynamical process.
05 June 2018, 14h0015h00
Salle de réunion du bâtiment modulaire (Luminy).

Prochains évènements

Retour à l'agenda
20 December 2018

Séminaire CaNa : 20 décembre à 14h : SAT est NP-complet, la preuve !

Résumé : Ne croyez pas ce que l'on vous a dit, le théorème de Cook-Levin n'est pas si difficile que cela à démontrer... J'ai longtemps admis cette preuve, et après l'avoir lue dans le livre de Sylvain Perifel, j'ai envie de la partager ! Venez ajouter LA brique de base à vos connaissances en complexité, ou simplement réviser :-)