Programming biomolecules that fold greedily during transcription

Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

20 Sitaatiot (Scopus)
42 Lataukset (Pure)


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.
Otsikko41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland
ToimittajatPiotr Faliszewski, Anca Muscholl, Rolf Niedermaier
KustantajaSchloss Dagstuhl - Leibniz Center for Informatics
ISBN (elektroninen)978-3-95977-016-3
DOI - pysyväislinkit
TilaJulkaistu - 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Mathematical Foundations of Computer Science - Krakow, Puola
Kesto: 22 elok. 201626 elok. 2016
Konferenssinumero: 41


NimiLIPIcs - Leibniz International Proceedings in Informatics
KustantajaDagstuhl Publishing
ISSN (elektroninen)1868-8969


ConferenceInternational Symposium on Mathematical Foundations of Computer Science


Sukella tutkimusaiheisiin 'Programming biomolecules that fold greedily during transcription'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä