DNA-based Learning Algorithms and their Applications

基于DNA的学习算法及其应用

• 批准号: 13680464
• 负责人: SAKAKIBARA Yasubumi
• 金额: $ 2.3万
• 依托单位: Keio University (2002-2003)Tokyo Denki University (2001)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680464/
• 关键词: DNA Computer; Molecular Computing; Machine Learning; Biomolecule; Massive Parallel; Biotechnology; Boolean Function; Automaton; 生体分子; 無細胞タンパク質合成系; 計算理論

We have considered a probabilistic interpretation of the test tube which contains a large amount of DNA strands, and proposed a population computation using a number of DNA strands in the test tube and a probabilistic logical inference based on the probabilistic interpretation.We have applied a DNA-based massively parallel exhaustive search to solving the computational learning problems of DNF Boolean formulae. We propose new methods to encode any k-term DNF formula to a DNA strand, evaluate the encoded DNF formula for a truth value assignment by using hybridization and primer extension with DNA polymerase, and find a consistent DNF formula with the given examples. By employing these methods, we have shown that the class of k-term DNF formulae and the class of general DNF formulae are efficiently learnable on DNA computer.We have employed the translation mechanism combined with four-base codon techniques to develop a molecular machine which computes finite automata (finite-state machine). We have reported some experimental results where we have succeeded to implement a finite automaton on an E.coli in vitro translation system with four-base codons.

考虑了含有大量DNA链的试管的概率解释，提出了利用试管中DNA链数量的群体计算和基于概率解释的概率逻辑推理，并应用基于DNA的大规模并行穷举搜索解决了DNF布尔公式的计算学习问题.我们提出了新的方法来编码任何k项DNF公式的DNA链，评估编码的DNF公式的真值分配通过使用杂交和引物延伸与DNA聚合酶，并找到一个一致的DNF公式与给定的例子。利用这些方法，我们证明了k项DNF公式类和一般DNF公式类在DNA计算机上是可有效学习的，并利用翻译机制和四碱基密码子技术，构造了一个计算有限自动机（有限状态机）的分子机器。我们已经报道了一些实验结果，我们已经成功地实现了一个有限自动机在大肠杆菌体外翻译系统与四个碱基的密码子。

项目成果

Yokomori, T., Sakakibara, Y., Kobayashi, S.: "A Magic Pot : Self assembly computation Revisited"Formal and Natural Computing. 418-429 (2002)

Yokomori, T.、Sakakibara, Y.、Kobayashi, S.：“魔法壶：重新审视自组装计算”形式和自然计算。

Y.Sakakibara, T.Hohsaka: "In Vitro Translation-based Computations"Proceedings of 9th International Meeting on DNA Based Computers. 175-179 (2003)

Y.Sakakibara、T.Hohsaka：“基于体外翻译的计算”第九届国际 DNA 计算机会议论文集。

Y.Sakakibara: "DNA-based Algorithms for Learning Boolean Formulae"Natural Computing. 2・2. 153-171 (2003)

Y. Sakakibara：“基于 DNA 的布尔公式学习算法” 153-171 (2003)。

Sakakibara, Y., Hohsaka, T.: "In Vitro Translation-based Computations"Proceedings of 9th International Meeting on DNA Based Computers. 175-179 (2003)

Sakakibara, Y., Hohsaka, T.：“基于体外翻译的计算”第九届国际 DNA 计算机会议论文集。

Sakakibara, Y., Imai, H.: "A DNA-based Computational Model using a Specific Type of Restriction Enzyme"Proceedings of 8th International Meeting on DNA Based Computers. 315-325 (2002)

Sakakibara, Y., Imai, H.：“使用特定类型限制性酶的基于 DNA 的计算模型”第八届国际 DNA 计算机会议论文集。