Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami
Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami
复制标题
贪婪确定性 Oritatami 中构象大小的线性界限
DOI：
10.1142/s0129054121410082
复制
发表时间：
2021
影响因子：
0.8
通讯作者：
Seki Shinnosuke
中科院分区：
文献类型：
--
作者：
Fazekas Szilard Zsolt;Kim Hwee;Matsuoka Ryuichi;Morita Reoto;Seki Shinnosuke
Oritatami是RNA共转录折叠的计算模型，其中RNA转录本在从其模板DNA合成时自身折叠。这个模型被认为是图灵普适的。然而，在其参数delay和arity均为1的限制下，已知任何确定性可折叠构象至多是其初始构象（种子）的10倍，因此，模型变得较弱。在本文中，我们将尺寸上界从下到上加以改进，并给出一个系统，它可以折叠成一个尺寸的构象。这些更严格的界限从一个新的图形表示确定性oritatami折叠途径。我们还将研究转录本被困在由种子封闭的区域中的情况，并表明在这种限制下，上限进一步提高到。
Oritatami is a computational model of RNA cotranscriptional folding, in which an RNA transcript is folding upon itself while being synthesized from its template DNA. This model is known to be Turing universal. Under the restriction on its parameters delay and arity both being 1, however, any deterministically foldable conformation is known to be at most ten times as large as its initial conformation (seed), and hence, the model becomes weaker. In this paper, we shall improve the size upper bound fromdown toand also provide a system that can fold into a conformation of size. These tighter bounds result from a novel graph representation of deterministic oritatami folding pathways. We shall also study the case in which a transcript is trapped in a region closed by a seed and show that under this confinement, the upper bound is further improved to.