Intrinsic universality of co-transcriptional folding

共转录折叠的内在普遍性

• 批准号: 20K11672
• 负责人: 関 新之助
• 金额: $ 2.66万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11672/
• 关键词: 分子自己組織化; RNA共転写性フォールディング; 折り畳みシステム; 本質的計算完全性; 共転写性フォールディング; 2次元チューリングマシン; チューリング完全性; Intrinsic simulation; 分子計算

RNA1本鎖はポリメラーゼがDNA2本鎖の情報を1文字（A, G, G, T）ずつ読み取り、A→U, C→G, G→C, T→Aという規則に則って伸長することで合成（転写）される。転写と並行して鎖は折り畳まれていくのだが、この現象をRNA co-transcriptional folding（CF）といい、生体内の様々な情報処理を司っている。折り畳み（oritatami）はCFの計算能力を調べるために提唱された数理モデルである。このモデルでは全ての計算可能関数が計算できるが、それは入力に対して正しい出力を返すというだけでその出力を如何にして得たかという示唆を何ら与えるものではない。フォールディングの過程を理解することこそCF駆動の生体内計算機構の実装には不可欠であるから、本研究課題はある折り畳みシステムの振る舞いを別の折り畳みシステムで模倣できるか、さらにはあるクラスに含まれる全ての折り畳みシステムの振る舞いを模倣する汎用折り畳みシステムの設計が可能か、という問題に解を与えることにある。折り畳み計算の主要な駆動原理にシフトがある。転写のある段階において、転写物の一部がある環境では短く縮み、別の環境では伸びるとすると、それ以降の転写は異なった場所で起こることになる。例えば転写産物の上に書かれているテーブルを入力に応じた量だけ左右にスライドさせ特定のセルを参照する、などといったことが可能になる。折り畳みシステムの計算完全性の証明もこのテーブル参照法に依拠している。シフトの新しい応用として、複数のシグナルを並行かつ独立して折り畳みシステムに伝送させる方法の確立がある。この並列情報伝送に重要な役割を果たすモジュール「elastic glider」を開発し、入力として与えられた任意の自然数nに対し、一辺がnの正方形へと折り畳まれる折り畳みシステムの設計に着手した。

通过聚合酶在一个字母（A，G，G，T）中读取双DNA链的信息，并根据规则A→U，C→G，G→C，T→A合成单个RNA链（转录）。链与转录并行折叠，该现象称为RNA共转录折叠（CF），该折叠（CF）控制体内的各种信息处理。折叠（Oritatami）是一种数学模型，旨在研究CF的计算能力。尽管可以在此模型中计算所有可计算的功能，但它并未提供任何仅通过返回输入的正确输出来获得输出的任何指示。了解折叠过程对于实施CF驱动的体内计算机制至关重要，因此该研究主题是解决一个问题的问题，即是否可以通过另一个折叠系统模仿一个折叠系统的行为，甚至可以模拟一类中包含所有折叠系统的通用折叠系统的设计。折叠计算的主要驾驶原理有所转移。如果在转录的一个阶段，某些转录本在一个环境中缩小并在另一种环境中延伸，则随后的转录将发生在不同的位置。例如，可以将写在左右转录的上方的表格上的表格，以对应于特定单元格的输入，依此类推。折叠系统的计算完整性证明也依赖于该表查找方法。转移的新应用是建立并行和独立地传输多个信号的方法。我们已经开发了一个称为“弹性滑翔机”的模块，该模块在此并行信息传输中起着重要作用，并开始设计一个折叠系统，其中将一侧折叠成一个正方形，并在任何自然数字n作为输入的任何自然数n上折叠。

项目成果

Special Issue Developments in Language Theory 2018 ? Preface

2018 年语言理论发展特刊？

• DOI: 10.1142/s0129054120020025
• 发表时间: 2020
• 期刊: International Journal of Foundations of Computer Science
• 影响因子: 0.8
• 作者: Takehiro Ito;Yuni Iwamasa;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Yuta Nozaki;Yoshio Okamoto;Kenta Ozeki;Seki Shinnosuke
• 通讯作者: Seki Shinnosuke

A general architecture of oritatami systems for simulating arbitrary finite automata

用于模拟任意有限自动机的折纸系统的通用体系结构

• DOI: 10.1016/j.tcs.2020.12.014
• 发表时间: 2021
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Han Yo-Sub;Kim Hwee;Masuda Yusei;Seki Shinnosuke
• 通讯作者: Seki Shinnosuke

Counting infinitely by oritatami co-transcriptional folding

通过oritatami共转录折叠无限计数

• DOI: 10.1007/s11047-021-09842-6
• 发表时间: 2021
• 期刊: Natural Computing
• 影响因子: 2.1
• 作者: Maruyama Kohei;Seki Shinnosuke
• 通讯作者: Seki Shinnosuke

On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding

通过共转录折叠进行正方形的算法自组装

• 发表时间: 2022
• 期刊: Leibniz International Proceedings in Informatics (LIPIcs)
• 作者: Fazekas Szilard Zsolt、Kim Hwee、Matsuoka Ryuichi、Seki Shinnosuke;Takeuchi Hinano
• 通讯作者: Takeuchi Hinano

Turedo a new computational model for molecular nanobots?

Turedo 是分子纳米机器人的新计算模型？

• 发表时间: 2022
• 作者: 水谷晃輔;菱田勢始;川上恭司郎;藤田泰典;加藤卓;高井学;飯沼光司;中根慶太;土屋朋大;三浦ゆり;伊藤雅史;古家卓也;Xuehou Tan;Nicolas Schabanel
• 通讯作者: Nicolas Schabanel