Asymptotic Analysis of DNA Computation using Information Theoretic Method

信息论方法DNA计算的渐近分析

• 批准号: 19560374
• 负责人: KAMABE Hiroshi
• 金额: $ 1.25万
• 依托单位: Gifu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19560374/
• 关键词: DNA 計算; 情報理論; 通信路容量; 母関数; DNA計算; 漸近解析; 漸近的性質; 制約符号; 容量; 記号力学系; 解析的組み合わせ論

DNA 系列は4記号の系列と考えることができるが, 工学的な処理の容易さや構造の安定性などを考慮すると, いくつかの制約を満たしているDNA 系列だけが工学的に利用できると考えることができる.DNA 計算では計算の入力や途中の計算結果をDNA 系列の集合として保存するが, これらも前述の制約を満たしていることが要請される.したがってDNA 計算などで系列を利用するためには, そもそもそうした制約を満たす系列がどれくらい存在するのかを知る必要がある.これは情報理論における「入力制約を持つ通信路の容量」に対応する.しかしながら, DNA 系列が満たすべき制約はこれまで情報理論が対象としてきた制約のクラスには入らない.したがって, 本研究では計算機実験などの方法を試みたがうまくいかず, いろいろ調査した結果, この問題を解くためにうまく応用できる理論があることがわかった.その方法と計算機実験を組みわせることによって, 原理的には容量を計算できることがわかった.この方法を用いてより現実的な制約の容量を計算した.

尽管可以将DNA序列视为四个符号系列，考虑到易于工程处理和结构稳定性，可以认为只有满足一些约束的DNA序列才能使用工程。 DNA计算存储输入和计算在中间作为DNA序列集，但也需要这些来满足上述约束。因此，为了在DNA计算中使用序列，必须了解多少序列首先满足这些约束。这对应于信息理论中的“通道具有输入约束的能力”。但是，DNA序列应满足的约束并不属于信息理论先前针对的限制类别。因此，在这项研究中，我们尝试了诸如计算机实验之类的方法，但它们没有起作用，经过各种调查，我们发现有一种理论可以很好地应用来解决此问题。通过将方法与计算机实验相结合，可以原则上计算能力。该方法用于计算更现实的约束的能力。

项目成果

RNA系列に関する制約の容量

RNA序列的约束能力

• 发表时间: 2007
• 作者: 森岡佑介;宮北和之;中野敬介;仙石正和;篠田庄司;森岡佑介;Hiroshi Kamabe;Hiroshi Kamabe;鎌部浩;H. Kamabe;H. Kamabe;鎌部浩;鎌部 浩
• 通讯作者: 鎌部 浩

Combination of Context-Free Shifts and Shifts of Finite Type

上下文无关移位和有限类型移位的组合

• 发表时间: 2008
• 期刊: Proceedings of BIOCOMP'08 3(印刷中)
• 作者: 森岡佑介;宮北和之;中野敬介;仙石正和;篠田庄司;森岡佑介;Hiroshi Kamabe;Hiroshi Kamabe;鎌部浩;H. Kamabe
• 通讯作者: H. Kamabe

支脈自由文法に上る制約と有限タイプの制約の組み合わせの表現

自由分支语法和有限类型约束的约束组合的表示

• 发表时间: 2008
• 期刊: 電子情報通信学会研究会技術報告 IT 108(202)
• 作者: 森岡佑介;宮北和之;中野敬介;仙石正和;篠田庄司;森岡佑介;Hiroshi Kamabe;Hiroshi Kamabe;鎌部浩
• 通讯作者: 鎌部浩

Combination of Context Free Shifts and Shifts of Finite Tvpe(CDROM)

上下文无关移位和有限电视移位的组合(CDROM)

• 发表时间: 2008
• 期刊: The Proceedings of The 2008 International Conference on Bioinformatics and Computational Biology(CDROM)
• 作者: 森岡佑介;宮北和之;中野敬介;仙石正和;篠田庄司;森岡佑介;Hiroshi Kamabe;Hiroshi Kamabe
• 通讯作者: Hiroshi Kamabe

Combinations of context-free shifts and shifts of finite type

上下文无关移位和有限类型移位的组合

• 发表时间: 2008
• 作者: 森岡佑介;宮北和之;中野敬介;仙石正和;篠田庄司;森岡佑介;Hiroshi Kamabe;Hiroshi Kamabe;鎌部浩;H. Kamabe;H. Kamabe
• 通讯作者: H. Kamabe