構造的分子計算理論–自律的計算系の解析と設計のための基礎理論
横森 貴・上田和紀・楠元範明（ 早稲田大学）
榊原 康文（ 慶応義塾大学）
小林 聡（ 電気通信大学）
鈴木康博（ 東京医科歯科大学）

1

研究の背景・目的【本研究の動機と背景】 現在我々が利用しているコンピュータの能力には理論的かつ現実的な意味において限界があることが明らかになっている．理論的には計算不可能性の壁があり，現実的にはいわゆるＮＰとよばれる問題のクラスは実際的な時間内では解けないと信じられている．これらの計算能力の限界を乗り越えるべく近年提案された新しい計算パラダ イムのひとつが分子計算である．欧米をはじめ我が国においても非ノイマン型計算メカニズムを強く志向する機運と相まって分子計算への期待は徐々に高まり，ご く最近では不定形計算 (Amorphous Computing) をはじめとする新しい超並列計算モデルや自然の行っている現象・原理に基づくいわゆる “ナチュラルコンピュテーション ”(Natural Computation : NC) とよばれる新計算パラダ イムの探究へと発展する広がりをみせている．
我々はこれまでの研究において，核酸塩基対の相補性による自律的会合，分子構造の形態変化などの様々な生体分子反応を解析しそれらの知見をヒントとして，情報処理のための新たな基本的計算機構の開発と分子計算モデルの提案を行ってきた．提案した多くの計算モデルは従来の計算機と同等の計算能力（チューリング計算可能性）を有することが証明され，実際に分子生物学的な基礎実験によりその実装可能性の一部が検証されたものもある．また，細胞内の生体分子反応をモデル化した抽象化学反応系にコンパート メントを導入することにより細胞計算モデルを構築しその計算能力を理論的に解析してきた．
一方，分子計算の分子生物学実験におけるハミルトン経路問題や充足可能性問題に対する解法はハイブリダ イゼーションという分子反応や PCR 増幅等の実験操作を含んでいるが，それらの実行過程の信頼性はまだ低く反応特性の詳細な解析や基本操作の問題点については不明な点が少なくない．したがって，上述の新規な計算モデルの実装可能性を検証するためにも計算機シミュレーションシステムを開発し，人工的な仮想分子などを用いることにより PCR など DNA による様々な生体分子反応や分子計算モデルの挙動をシミュレートすることが必要となっている．この意味において，分子反応系のための確率的あるいは近似的計算モデルとその解析手法に関する研究の必要性が強く示唆される．
【本研究の目的】 DNA，RNA の構造分子やタンパク質のような高次構造を持つ生体高分子は分子認識（ 分子会合），自己組織化，形態変化などの生体反応・現象によって目的をもった分子系を形成し機能を発現する．そこで，以下のような “自律的計算スキーマ” を考える．まず充分な量の構造分子群からなる溶液（これをプログラムとする）を仮定する．これに対して外部からある情報（これが入力である）が与えられると，その入力に対する計算・演算の結果としてある特定の構造化分子を生じるとする．意図した構造化分子の形成がここでの計算の出力結果である．本研究の目的は，

1

生体構造分子と生体化学反応系に関わる情報処理能力を計算理論的，アルゴ リズム論的な視点から “解析し設計する” ことである．すなわち，生体分子の構造とその機能との関係を計算能力（あるいは情報処理能力）という視点から解析することにより，基本計算ユニットの集合（ 基本構造分子群）と基礎となる計算原理（ 生体反応系）を明らかにして，それらの組み合わせを基本とする体系的な分子計算の理論モデルを構築することである．ここで計算に用いられる分子群は現実の分子のみならず仮想的な人工分子も考案することにより，抽象的なレベルでの NC 研究への貢献も視野にいれて研究する．さらに，ある問題を解く（ある機能を実現する）ために基本構造分子群に属する各分子計算ユニット上にその問題をどのように符号化し制御すればよいかという分子計算におけるプログラミング技法を研究する．
（ 符号化された）入力分子↓［（プログラム化された）基本構造分子群］===＞［（ 出力の）構造化分子形成］(分子反応)

2

研究成果概要本年度の研究成果はふたつの分野に大別される．その概要を以下で述べる．
（ 詳細は関連する論文を参照されたい．
）

2.1

自律的分子計算系のための基礎的考察

1. 〈 自律的計算モデルの再考 〉 Adleman による有向ハミルトンパス問題 (DHPP)
に対する DNA を用いた解法を基本として幾つかの自律的計算モデルが提案され，自律的計算系の計算論的な万能性もよく知られているが，一般に，そこでは分子配列の設計という問題が重要な要素を占める．本研究では，長さのみによる分子配列の設計法に関して探究し，有限オートマトンや DHPP などがそのような簡単な設計によっても解決されることを示した [1]．
2. 〈 挿入・削除システムの解析 〉 DNA を用いた計算モデルのひとつとして挿入・削除システムが提案されている．これは特定の DNA 配列がある認識部位において挿入されたり，削除される現象をモデル化したものであり，その計算能力は万能であることが知られている．本研究では，このシステムが理論的に万能性を保持しながらどこまで簡約化できるかを探究し，認識部位および挿入・削除記号列の長さが共に１まで簡約化が可能であることを示した [2]．
3. 〈 挿入型計算モデルの研究 〉認識部位から数塩基離れた位置で DNA 二重鎖を切断する特殊な制限酵素と環状 DNA 鎖を用いた新しい DNA コンピュータの方式について考案し ，そのモデルの数学的解析を行った．その結果，計算モデルが万能計算能力を有することを明らかにし ，また文脈自由文法などを用いた構文解析問題も効率よく解くことを示した [13]．さらに，転写，翻訳，代謝などの細胞内分子反応メカニズムを用いた新たな分子計算方式の可能性を検討した．
4. 〈 分子配列設計法の考案 〉 構造分子の設計問題の最も基本的な課題として，DNA 分子の配列設計は避けて通れない重要な問題である．本年度は，構造分子の設計・解析のための理論の構築のための副目標として，この配列設計の問題に着手した．ハミング距離等をベースとした配列設計の理論では，配列の高速2な評価が行えるため，比較的大きな配列空間を対象として，実験要求に適合する配列セットを探索することが可能である．しかしながら，ハミング距離等では，バルジループや内部ループ等の二次構造形成に対処することが難しい．そこで本研究では，ハミング距離等をベースにした設計手法で得られた配列セットから，二次構造をできるだけ形成しない配列セットを抽出するための手法を考案した [14, 15, 16]．

5. 〈 細胞内反応計算モデルの研究 〉 京大と共同研究を行い，抽象化学反応系(Abstract Rewriting System on Multisets : ARMS) を用いて化学情報物質による種間の情報伝達が介在する植物・食植者・天敵の３者生態系のモデル化を行い，実験と合致する結果を得た．また，Max Plank Institute Chemical Ecologyと共同研究を開始し，京大のグループとは異なった３者系のモデル化を行った．
また，ARMS を用いて炎症反応をモデル化する研究を行った．炎症反応は風邪，喘息，多臓器不全，脳梗塞，心筋梗塞などの重要な疾患の基礎となるものであるが，そのしくみは複雑である．だが，ARMS を用いることにより直観的かつ容易にモデル化を行うことができた [17]．

2.2並列計算系による分子計算シミュレータの設計と試作

分子計算系における局所的並列性をシリコン上で実装するために，ノード の多重集合，膜とその階層化，リンク，グラフ変換の四概念に基づく新たな計算モデル LMNtal の設計に着手し ，基本設計をほぼ完了した [5, 7, 10]．また，Java を用いて試作処理系のコンパイラとランタイムを実装した．LMNtal は• 多重集合や会合概念をもった数多くの計算モデルの統合• リソースコンシャスな計算の基本モデルなどを目指したモデルであり，今年度は上記に加えて他の計算モデルとの比較検討も進めた．

《本年度

成果論文リスト 》[1] T.Yokomori,Y.Sakakibara,S.Kobayashi : A Magic Pot : Self-assembly computation
revisited, Lecture Notes in Computer Science, Vol.2300, pp.418-429, Springer, 2002.
[2] A.Takahara and T.Yokomori : On the computational power of Insertion-Deletion Systems, Proc. of DNA Based Computers(DNA8)(Lecture Notes in Computer Science),
Vol.2568, pp.139-150, Springer, 2002.
[3] Takashi Yokomori : Molecular computing paradigm–toward freedom from Turing’scharm, Natural Computing, Vol.4, No.1, pp.333-390, 2002.
[4] Kazunori Ueda : A Pure Meta-Interpreter for Flat GHC, A Concurrent Constraint
Language, Computational Logic: Logic Programming and Beyond(Essays in Honour ofRobert A. Kowalski, Part I) (A.C. Kakas, F. Sadri,Eds.) Springer-Verlag, pp.138-161,
2002.

3

[5] Kazunori Ueda and Norio Kato : Programming with Logical Links: Design of the LMNtal language, Proc. 3rd Asian Workshop on Programming Languages and Systems(APLAS 2002), pp.115-126, 2002.
[6] Norio Kato and Kazunori Ueda : Sequentiality Analysis for Concurrent Logic Programs, Proc. 6th World Multiconference on Systemics, Cybernetics and Informatics(SCI 2002), Vol.11, pp.329-336, 2002.
[7] 上田和紀, 加藤紀夫: Programming with Logical Links，日本ソフトウェア科学会第 19回大会論文集, 2002.(CD-ROM)[8] 加藤紀夫, 上田和紀: モード 制約の漸近的一様補強による並行論理プログラムの occurscheck 解析，日本ソフトウェア科学会第 19 回大会論文集, 2002.(CD-ROM)[9] 松村量, 高山啓, 高木祐介, 加藤紀夫, 上田和紀: 分散言語処理系 DKLIC の設計と実装，
日本ソフトウェア科学会第 19 回大会論文集, 2002.(CD-ROM)[10] 上田和紀, 加藤紀夫: GHC から LMNtal へ，情報処理学会 2002 年度 夏のプログラミン
グシンポジウム, 2002.(http://www.ipsj.or.jp/prosym/sprosym/program/index.html)[11] 網代育大，上田和紀： 反復深化 A*探索によるもっともらしいプログラムの効率的な生成，人工知能学会全国大会（ 第 17 回）論文集，1E3-02, 2002 年 6 月．(CD-ROM)[12] Yasuhiro Ajiro and Kazunori Ueda : Kima: an Automated Error Correction System
for Concurrent Logic Programs, Automated Software Engineering, Vol.9, No.1, pp.6794, 2002.
[13] Y.Sakakibara and H.Imai : A DNA-based Computational Model using a SpecificType of Restriction Enzyme, Proc. of DNA Based Computers(DNA8) (Lecture Notes
in Computer Science), Vol.2568, pp.290-300, Springer, 2002.
[14] M.Arita and S.Kobayashi : DNA Sequence Design Using Templates, New GenerationComputing, 20, pp.263-277, 2002.
[15] S.Kobayashi, T.Kondo, M.Arita : On Template Method for DNA Sequence Design,
Proc. of DNA Based Computers(DNA8) (Lecture Notes in Computer Science), Vol.2568,
pp.115-124, Springer, 2002.
[16] 奥田 講平，小林 聡 : バルジ・内部ループを形成しない DNA 配列セットの設計, 情報処
理学会研究報告, 2002-MPS-42, pp.99-102, 2002.
[17] Yasuhiro Suzuki, Junji Takabayashi, Hiroshi Tanaka : Investigation of tritrophic system in ecological systems by using an artificial chemistry, to appear in J.AROB, 2003.
【附記】（ 2002 年度受賞）
上田 和紀：日本ソフトウェア科学会 第 19 回大会 高橋奨励賞, 2002. (論文題目： Programming with Logical Links)

4