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)

Abstrakti

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.
AlkuperäiskieliEnglanti
Otsikko41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland
ToimittajatPiotr Faliszewski, Anca Muscholl, Rolf Niedermaier
JulkaisupaikkaGermany
KustantajaSchloss Dagstuhl - Leibniz Center for Informatics
Sivut1-14
Sivumäärä14
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

Julkaisusarja

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

Conference

ConferenceInternational Symposium on Mathematical Foundations of Computer Science
LyhennettäMFCS
Maa/AluePuola
KaupunkiKrakow
Ajanjakso22/08/201626/08/2016

Sormenjälki

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

Siteeraa tätä