表題番号:1998A-824 日付:2003/05/12
研究課題DNAコンピュータの計算モデルの研究
研究者所属(当時) 資格 氏名
(代表者) 教育学部 教授 横森 貴
研究成果概要
従来のシリコンベース・ノイマン型コンピュータの計算能力の限界を乗り越えるための研究動向の一つとして、DNAなどのミクロ分子を用いた計算機の研究が進んでいる。本研究ではDNAコンピュータの開発の理論的な基盤を構築するための計算モデルの提案を行った。1994年の科学誌Scienceに発表されたAdlemanによる有向ハミルトンパス問題の分子生物学的解放において用いられた基本的な操作はアニーリング(annealing)、融解(melting)、検知(detection)などであるが、本研究の過程において「これらの基本操作と自己組織(自律)的な性質に基づく計算メカニズム」が実際的な実現可能性からみて最も有力な、かつ有益な計算モデルであろうという知見が得られた。そこで、この視点から研究を続けた結果、『有限個の基本DNA構造分子から、アニーリング・融解・検知操作のみを用いて万能計算能力を実現する(すなわち、チューリング計算可能な)自己組織型の計算モデル:YAC(Yet Another Computation of Self-Assembly)』を提案することができた。この計算モデルは、計算能力の万能性、基本操作の実装における容易性、クラスNPの多項式時間DNA計算可能性、などにおいて優れた特徴をもつと言える。一方、その実装モデルによる計算においては、問題サイズの増大に比例して膨大なDNA分子量を必要とするという問題点が理論的に指摘される。したがって、本計算モデルの基本的枠組みを維持しつつ、かつ現実的な資源量で計算が可能な問題のクラスとその実現方法の探求が、今後の残された重要な課題であると思われる。