Geary, Cody ;
Meunier, PierreEtienne ;
Schabanel, Nicolas ;
Seki, Shinnosuke
Programming Biomolecules That Fold Greedily During Transcription
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 fixedparameter tractable, although we also prove it NPcomplete in the number of possible environments.
BibTeX  Entry
@InProceedings{geary_et_al:LIPIcs:2016:6456,
author = {Cody Geary and PierreEtienne 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:143:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6456},
URN = {urn:nbn:de:0030drops64567},
doi = {10.4230/LIPIcs.MFCS.2016.43},
annote = {Keywords: natural computing, selfassembly, molecular folding}
}
2016
Keywords: 

natural computing, selfassembly, molecular folding 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

2016 