License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.43
URN: urn:nbn:de:0030-drops-64567
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6456/
Go to the corresponding LIPIcs Volume Portal

Geary, Cody ; Meunier, Pierre-Etienne ; Schabanel, Nicolas ; Seki, Shinnosuke

Programming Biomolecules That Fold Greedily During Transcription

pdf-format:
LIPIcs-MFCS-2016-43.pdf (4 MB)

Abstract

We introduce and study the computational power of Oritatami, a theoretical model to explore greedy molecular folding, by which a molecule begins to fold before awaiting the end of its production. This model is inspired by a recent experimental work demonstrating the construction of shapes at the nanoscale by folding an RNA molecule during its transcription from an engineered sequence of synthetic DNA.

An important challenge of this model, also encountered in experiments, is to get a single sequence to fold into different shapes, depending on the surrounding molecules. Another big challenge is that not all parts of the sequence are meaningful for all possible inputs. Hence, to prevent them from interfering with subsequent operations in the Oritatami folding pathway we must structure the unused portions of the sequence depending on the context in which it folds.

Next, we introduce general design techniques to solve these challenges and program molecules. Our main result in this direction is an algorithm that is time linear in the sequence length that finds a rule for folding the sequence deterministically into a prescribed set of shapes, dependent on its local environment. This shows that the corresponding problem is fixed-parameter tractable, although we also prove it NP-complete in the number of possible environments.

BibTeX - Entry

@InProceedings{geary_et_al:LIPIcs:2016:6456,
  author =	{Cody Geary and Pierre-Etienne Meunier and Nicolas Schabanel and Shinnosuke Seki},
  title =	{{Programming Biomolecules That Fold Greedily During Transcription}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6456},
  URN =		{urn:nbn:de:0030-drops-64567},
  doi =		{10.4230/LIPIcs.MFCS.2016.43},
  annote =	{Keywords: natural computing, self-assembly, molecular folding}
}

Keywords: natural computing, self-assembly, molecular folding
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI