Oritatami: A Computational Model for Molecular Co-Transcriptional Folding
Oritatami: A Computational Model for Molecular Co-Transcriptional Folding
复制标题
DOI：
10.3390/ijms20092259
复制
发表时间：
2019-05-01
影响因子：
5.6
通讯作者：
Seki, Shinnosuke
中科院分区：
文献类型：
--
作者：
Geary, Cody;Meunier, Pierre-Etienne;Seki, Shinnosuke
我们介绍并研究Oritatami的计算能力，Oritatami是一种探索贪婪分子折叠的理论模型，即分子链在其生产完成之前开始折叠。这个模型的灵感来自于我们最近的实验工作，这些实验工作展示了从RNA构建纳米级形状，其中RNA链在从合成DNA的工程序列转录过程中折叠成可编程的形状。在Oritatami模型中，我们探索了一条单链一点一点地折叠的过程，最终的折叠以计算的时空图的形式出现。在这个模型中进行计算的一个主要要求是能够根据周围输入的状态对单个序列进行编程以折叠成不同的形状。另一个挑战是将所有的计算组件嵌入到一个连续的链中，并且以这样一种方式，即同一链的不同折叠模式执行不同的计算功能。在这里，我们介绍了一般的设计技术，以解决这些挑战的Oritatami模型。我们在这个方向上的主要结果是一个周期性的Oritatami系统的演示，根据其当前的局部环境，折叠到自己的算法成一组规定的形状，其最终的折叠显示的二进制整数序列从0到种子的大小。我们证明，设计Oritatami是NP-难的可能的局部环境的折叠。然而，我们提供了一个有效的算法，线性的序列的长度，解决了Oritatami设计问题时，当地环境的数量是一个小的固定常数。这表明，该问题实际上是固定参数可处理的（FPT），因此可以有效地解决在实践中。我们希望Oritatami中采用的众多结构策略能够激发新的RNA计算架构，利用RNA的快速动力学折叠。
We introduce and study the computational power of Oritatami, a theoretical model that explores greedy molecular folding, whereby a molecular strand begins to fold before its production is complete. This model is inspired by our recent experimental work demonstrating the construction of shapes at the nanoscale from RNA, where strands of RNA fold into programmable shapes during their transcription from an engineered sequence of synthetic DNA. In the model of Oritatami, we explore the process of folding a single-strand bit by bit in such a way that the final fold emerges as a space-time diagram of computation. One major requirement in order to compute within this model is the ability to program a single sequence to fold into different shapes dependent on the state of the surrounding inputs. Another challenge is to embed all of the computing components within a contiguous strand, and in such a way that different fold patterns of the same strand perform different functions of computation. Here, we introduce general design techniques to solve these challenges in the Oritatami model. Our main result in this direction is the demonstration of a periodic Oritatami system that folds upon itself algorithmically into a prescribed set of shapes, depending on its current local environment, and whose final folding displays the sequence of binary integers from 0 to with a seed of size We prove that designing Oritatami is NP-hard in the number of possible local environments for the folding. Nevertheless, we provide an efficient algorithm, linear in the length of the sequence, that solves the Oritatami design problem when the number of local environments is a small fixed constant. This shows that this problem is in fact fixed parameter tractable (FPT) and can thus be solved in practice efficiently. We hope that the numerous structural strategies employed in Oritatami enabling computation will inspire new architectures for computing in RNA that take advantage of the rapid kinetic-folding of RNA.