Programming biomolecules that fold greedily during transcription

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Date
2016
Major/Subject
Mcode
Degree programme
Language
en
Pages
14
43:1-43:14
Series
41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, LIPIcs - Leibniz International Proceedings in Informatics, Volume 58
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 istime 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.
Description
Keywords
natural computing, self-assembly, molecular folding
Other note
Citation
Geary , C , Meunier , P-É , Schabanel , N & Seki , S 2016 , Programming biomolecules that fold greedily during transcription . in P Faliszewski , A Muscholl & R Niedermaier (eds) , 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland . , 43 , LIPIcs - Leibniz International Proceedings in Informatics , vol. 58 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , Germany , pp. 1-14 , International Symposium on Mathematical Foundations of Computer Science , Krakow , Poland , 22/08/2016 . https://doi.org/10.4230/LIPIcs.MFCS.2016.43