構造的分子計算理論-- 自律的計算系の解析と設計のための基礎理論
横森 貴（早稲田大学 教育学部）

１．研究の目的
我々はこれまでの研究において，核酸塩基対の相補性による自律的会合，分子構造の形態変化などの様々な生体分子反応を解析し，それらの知見をヒントとして情報処理のための新たな基本的計算機構の開発と自律的分子計算モデルの提案を行ってきた．提案した多くの計算モデルは従来の計算機と同等の計算能力（チューリング計算可能性）を有することが証明され，実際に分子生物学的な基礎実験によりその実装可能性の一部が検証されたものもある．また，細胞内の生体分子反応をモデル化した抽象化学反応系にコンパートメントを導入することにより細胞計算モデルを構築しその計算能力を理論的に解析してきた．
一方，分子計算の分子生物学実験におけるハミルトン経路問題や充足可能性問題に対する解法はハイブリダイゼーションという分子反応やPCR増幅等の実験操作を含んでいるが，それらの実行過程の信頼性はまだ低く反応特性の詳細な解析や基本操作の問題点については不明な点が少なくない．したがって，上述の新規な計算モデルの実装可能性を検証するためにも計算機シミュレーションシステ
ムを開発し，人工的な仮想分子などを用いることによりPCRなどDNAによる様々な生体分子反応や分子計算モデルの挙動をシミュレーションすることが必要となっている．この意味において，分子反応系のための確率的あるいは近似的計算モデルとその解析手法に関する研究の必要性が強く示唆される．

自律的分子計算系 （基本スキーマ）
入力（記号列）

基本分子群
プログラム
（DNAコード化）

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

２．

研究項目と役割分担

本研究では上記の目的を達成するために以下の３つの研究項目，すなわち「自律的分子計算系の基礎的考察」，「抽象化学反応計算モデルの研究」，および「並列計算系による分子計算シミュレ
ータの設計と試作」を設定した．本節ではこれら３つの研究項目について、その概要と各研究メンバーの役割分担について説明する．

２．１

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

DNA，RNAの構造分子やタンパク質のような高次構造を持つ生体高分子は分子認識（分子会合），自己組織化，形態変化などの生体反応・現象によって目的をもった分子系を形成し機能を発現する．そこ
で，本研究項目では分子計算において基本的な̀̀自律的計算スキーマ''に立ち返って考える．すな
わち，充分な量の構造分子群からなる溶液（これをプログラムとする）を仮定し，これに対して外部からある情報（これが入力である）が与えられると，その入力に対する計算・演算の結果としてある特定の構
造化分子を生じる．意図した構造化分子の形成がここでの計算の出力結果である（前出の図参照）．この分子計算における基本スキーマを基に，自己組織化や形態変化などの概念による新しい自律的分子計算メカニズムと計算モデルの構築を試みる．と同時に，自律計算メカニズムにとって最も基礎的な分子の符号化技法の開発を目指す．

２．２ 抽象化学反応計算モデルの研究
化学反応は分子群の間の相互作用により新たな分子群を生成する．ここでは構成分子の種類だ
けでなく，その量的な変化も重要な計算要素である．このような化学反応系を抽象化した計算モデルの理論とその応用について研究する．具体的には，化学反応の抽象計算モデルARMSをシミ
ュレート可能な，ある種の確率的な細胞膜計算モデルを用いてARMSの計算理論を考察する．また，ARMSの力学系におけるアトラクタを受理可能な記号列とみなし，与えられた書き換え規則の記号生成能力を，その規則を用いて原理的に構成可能なアトラクタの総数とみなすことにより，抽象化
学反応系の計算能力の特徴付けを行う．さらに，受理状態間の遷移可能性などについても考察する．一方でARMSの工学応用についてその枠組みと適用可能な問題の発見と解決に関する研究を行う．以上の研究を通して"Natural Computing"の計算モデルとしての抽象化学系モデルの可能性について考察する．

２．３ 並列計算系による分子計算シミュレータの設計と試作
分子計算系において計算素子としての分子群のとる構造の変化や化学反応系における分子量の変化等，分子の局所的な振る舞いを忠実に模倣するために，多重集合を扱える並列分散型のシミュレーション言語を設計し実装することを目的とする．このような局所的並列性をシリコン上で実装するために，ノードの多重集合，膜とその階層化，リンク，グラフ変換の４つの概念に基づく新たな計算モデル の設計と実装を目指す．

理論分子
計算系

自律的分子計算系

分子計算シミュレータ

理論モデル構築
分子構造設計法
In Vitro ラボ（榊原、小林、横森、楠元）（バーチャル・シリコンラボ）
並列プログラミング系（上田、鈴木、横森）

抽象化学反応系
多重集合書き換え系（鈴木、横森）

本研究班は横森を代表（取りまとめ役）として以下のメンバーにより構成されている．
横森 貴・楠元範明（早稲田大学・教育学部）
上田和紀（早稲田大学・理工学部）
榊原 康文（慶応義塾大学・理工学部）
小林 聡（電気通信大学・電気通信学部）
鈴木康博（東京医科歯科大学・難治疾患研究所）
これらのメンバーの役割分担は図に示されている．「自律的分子計算系」においては，榊原・小林・横森（ともに計算機科学）は楠元（理論生物学）の生物学における知識・知見をもとに，計算理論・形式言語理論の立場から自律的分子計算のメカニズムと計算モデルを研究している．また，分子プログラミン
グにおける分子設計にとって不可欠な分子への符号化技法の研究や，提案したアイディアの分子実装の可能性を検証するためのに小規模なIn Vitro実験も行っている．「抽象化学反応系」においては，
鈴木（計算機科学）が主導的にAbstract Rewriting system on Multisets(ARMS)とよぶ生体化学
反応系の記述モデルを提唱し，細胞内反応系や細胞膜の機能を利用する計算モデルを研究している．
また，上田（計算機科学）は「分子計算シミュレータ」の設計と開発を目的として，独自の並列分散型の計算を志向した言語処理系（ LMNtal エレメンタル）を提案し実装し，これを用いた分子計算シミュレータの実装を目指している．

３．活動状況と班内の連携状況
各研究項目の主導的な担当者（以下，主務者とよぶ）は通常各自の研究目標を達成すべく研究活動を遂行しているが，班内の研究における連携活動は以下のように行っている．
・ 「自律的計算系」の各メンバーは計算の理論が専門分野であることから，鈴木の行っている「抽象化学反応系」の研究における計算モデルに関して，その計算可能性や計算能力についての理論的な考察や有用な知見を与え共同研究を行っている．
・ 鈴木もまた自らの計算モデルARMSが「多重集合による計算系」であるため，化学反応・ 計算系における多重集合に関する研究の成果を，自律的計算系における多重集合計算モデルの構築へ反映させるべく議論・検討を重ねている．
・ 「分子計算シミュレータ」の上田は並列分散計算言語の専門家であることから，多重集合を扱う計算モデルを当初から研究しており，蓄積した知識と経験を「自律的分子計算系」と「抽象化学反応系」の両方へ効果的に反映させるべく，議論を重ねている．
以上の活動に加えて，本特定領域研究内の他の理論グループ（九大山下班、東大萩谷班など）との合同研究会を定期的に開催し，意見・アイディア・情報の交換を行い互いの研究目的を達成するた
めに役立てている．さらに，プロジェクトの定期的な全体会議に参加し，他の研究班との緊密な交流を通して有用な情報の交換を行っている．
平成14年度と平成15年度における早大での研究会開催などの活動の概略は以下のとおりである：【「分子プロ」研究会の定例開催】の概要
場所： 早稲田大学教育学部１４号館
年月日： 平成14年４月12日、５月17日、10月18日
平成15年４月25日，10月31日
出席者数： (各回）平均して約20名
内容： 発表者のオリジナル論文の紹介、最近のホットな話題の紹介などを中心に、アイディアの紹介・情報交換・自由討論を行なった．

４．研究成果
本節では各研究項目についてこれまでの研究成果の概要をまとめる．

４．１ 自律的分子計算系の基礎的考察
主務者：横森 貴・楠元範明（早稲田大学），榊原康文（慶応義塾大学），小林 聡（電気通信大学）【平成14年度】
14年度の研究成果は４つの課題に大別される．その概要を以下で述べる．
(1). 自律的計算スキーマ再考：Adlemanによる有向ハミルトンパス問題(DHPP)に対するDNAを用いた解法を基本として幾つかの自律的計算モデルが提案され，自律的計算系の計算論的な万能性もよく知られている．一般にそれらの解法においては分子配列の設計という問題が重要な要素を占める．本
研究では，長さのみによる分子配列の設計法に関して考察し，有限オートマトンやDHPPなどがそのような簡単な設計手法によって解決されることを示した[Yokomori et al.:02]．具体的な結果のひとつとして，「有限オートマトンの最も簡便な分子実装法」を提案した．この方法の重要な特徴のひとつは「有限オートマトンの情報を長さの違いのみによって分子へ符号化している」ことである．基本的な考えは

「入力記号はそのアルファべト順に対応する長さで，状態は“総状態数”を基準として符号化する」ことである．下記の図では，４状態の有限オートマトンにおいて，例えば状態遷移規則：１→b ２を符号化す
るのに状態数４を基準として，「(４−１)個のＡ・ＧＧ・２個のＡ」とする．これにより複雑な符号化手法を用いることなくオートマトンの情報が分子配列として符号化され，受理すべき入力列に対して完全二重鎖が形成されることにより計算が実現される．

w = abba

2（受理される）入力
a

初期状態 ０

b

b
a

１

３

最終状態

4-0 a 10a

1

５ʼ- AAAAGA

4-1
1
2
1

b
b
a

b

2

2

５ʼ- AAAGGAA

1５ʼ- AAGGA

3５ʼ- AAAGAAAA

3+1(2). 挿入・削除システムの解析 ：DNAを用いた計算モデルのひとつとして挿入・削除システムが提案されている．これは特定のDNA配列がある認識部位において挿入されたり，削除される現象をモデル化したものであり，その計算能力は万能であることが知られている．本研究では，このシステムが理論的に万能性を保持しながらどこまで簡約化できるかを探究し，認識部位および挿入・削除記号列の長さが共に１まで簡約化が可能であることを示した[Takahara and Yokomori:02]．
(3). 挿入型計算モデルの研究 ：認識部位から数塩基離れた位置でDNA二重鎖を切断する特殊な制限酵素と環状DNA鎖を用いた新しいDNAコンピュータの方式について考案し，そのモデルの数学的解析を行った．その結果，計算モデルが万能計算能力を有することを明らかにし，また文脈自由文法などを用いた構文解析問題も効率よく解くことを示した[Sakakibara and Imai:02]．さらに，転写，翻訳，代謝などの細胞内分子反応メカニズムを用いた新たな分子計算方式の可能性を検討した．
(4). 分子配列設計法の考案 ： 構造分子の設計問題の最も基本的な課題として，DNA分子の配列設計は避けて通れない重要な問題である．本年度は，構造分子の設計・解析のための理論の構築のための第一歩として，この配列設計の問題に着手した．ハミング距離等をベースとした配列設計の理論では，配列の高速な評価が行えるため，比較的大きな配列空間を対象として，実験要求に適合する配列セットを探索することが可能である．しかしながら，ハミング距離等では，バルジループや内部ループ等の二次構造形成に対処することが難しい．そこで本研究では，ハミング距離等をベースにした設計手法で得られた配列セットから，二次構造をできるだけ形成しない配列セットを抽出するための手法を考案した[Arita and Kobayashi:02], [Kobayashi et al.:02]．
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.
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.
Takashi Yokomori : Molecular computing paradigm--toward freedom from Turing's charm,

Natural Computing, Vol.4, No.1, pp.333-390, 2002.
Gh. Paun, Y. Sakakibara, T. Yokomori：P-systems on Graphs of restricted forms, Publ. Math

Debrecen, 60, pp.635-660, 2002.
Y.Sakakibara and H.Imai : A DNA-based Computational Model using a Specific Type ofRestriction Enzyme, Proc. of DNA Based Computers(DNA8)(Lecture Notes in Computer
Science, Vol.2568）, pp.290-300, Springer, 2002.
M.Arita and S.Kobayashi : DNA Sequence Design Using Templates,
20, pp.263-277, 2002.

New Generation Computing,

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.
奥田 講平，小林 聡 : バルジ・内部ループを形成しないDNA配列セットの設計, 情報処理学会研究報告, 2002-MPS-42, pp.99-102, 2002.
【平成15年度】
15年度の研究成果は２つの課題に大別される．その概要を以下で述べる．
(1). 無細胞タンパク質合成系による計算モデルの研究 ：無細胞タンパク質合成系を用いたまったく
新しい分子コンピュータの方式を提案した [Sakakibara and Hohsaka:03]．この方式は，有限オート
マトンという計算モデルをタンパク質合成系と拡張コドンを用いて実現し，試験管の中でその計算を実行する「新しいタイプの DNA コンピュータ」を提案したものである．タンパク質合成系を用いることにより，従来の DNA コンピュータにおいて最大の問題となっていた，DNA 分子の水素結合を用いたハイブリダイ
ゼーションという演算による精度の低さとエラーの多さを解決することができた．具体的な手順として，まず入力文字をある RNA 部分配列にコード化し，有限オートマトンの状態も RNA 部分配列にコード化した．
これらのコード化された配列の最後に，受理されたか否かを検出するために GFP レポート遺伝子を加えた．次に，転移 RNA がもつアンチコドンを用いて，有限オートマトンの状態遷移関数をコード化した．このように，入力文字列をコード化した RNA 配列をメッセンジャーRNA として，また拡張アンチコドンをもつ
転移 RNA を無細胞タンパク質合成系に加えて，タンパク質合成反応を実行した．このとき，入力文字列
が正しい場合には，タンパク質合成が最後まで実行され，GFP タンパク質が合成されることにより発光が検出された．このようにして有限オートマトンはその文字列を受理したことが確認できた．

無細胞タンパク質合成系を用いた有限オートマトンの実装
入力文字列の mRNA 上へのコード化:“11” : ＧＧＧＵＡＧＧＧＵＡＡＡＵＡＧＣ-[GFP]
1

状態

1

1
1

ストップコドン状態

Ｙ

Ｘ

拡張アンチコドンをもつ tRNAによる状態推移のコード化

計算成功!

1
Ｙ

Ｘ
1

mRNA:

δ ( X , 1) = Y

CCCA UCC CAU UUAUCGＧＧＧＵＡＧＧＧＵＡＡＡＵＡＧＣ-[GFP]

４塩基アンチコドン

1CCCA

δ ( Y , 1) = X

３塩基アンチコドン

+
UCC

1

ストップ
コドン

状態をコード化

CAU(2). 分子配列設計法の考案：DNA 計算で用いる配列集合の設計に役立つアルゴリズムとシステムの開発を行った．まず，配列集合 S が与えられたとき，S+ に属するすべての配列が線形な二次構造を取らないための十分条件を求めた．この十分条件は，効率良く評価できるので実際の配列集合の評価に利用できる．また，二次構造を取らない配列の抽出問題を，この十分条件を利用することにより，超グラフ上の最大クリーク抽出問題に還元することに成功した．そして，富田らの彩色数を利用した分枝限定法による最大クリーク探索アルゴリズムを超グラフのクリーク探索に拡張して応用することにより，配列抽出システムを実装し，その有効性を確認した([Kobayashi:03a],[Kobayashi:03b])．
また，その後の研究の進展により，S+ が線形な二次構造を取らないための効率良く評価できる必要十分条件を求めることに成功した({Kobayashi:04a})．提案した手法は，与えられた長さ n の配列の有限集合(m 本の配列)に対し，S+が線形な二次構造を取り得るかどうかを O(m6n6) 時間で判定する．
このアルゴリズムは，二次構造の非形成判定問題を，グラフの最短経路問題に還元して解く．本年度
は，このアルゴリズムを実装して，配列集合を評価するシステムを構築した．
Akihiro Takahara and Takashi Yokomori: On the computational power of Insertion-Deletion
Systems, Natural Computing, Vol.2, No.4, pp.321-336, 2003.
Yasubumi Sakakibara and Takahiro Hohsaka : In Vitro Translation-based Computations,
Proceedings of 9th International Meeting on DNA Based Computers, Madison, Wisconsin,
175--179, 2003.
Yasubumi Sakakibara : DNA-based Algorithms for Learning Boolean Formulae, Natural

Computing, Vol.~2, No.~2, 153--171, 2003.
榊原康文: 分子コンピュータを用いた計算と学習アルゴリズム, 第 6 回情報論的学習理論ワークショ
ップ (IBIS2003), 京都, 2003.
榊原康文: 「ナノテクノロジーハンドブック」（第３編５章（DNA・分子コンピュータ）分担執筆）, オーム社,
2003.
Satoshi Kobayashi, Tomohiro Kondo, Kohei Okuda and Etsuji Tomita : Extracting Globally

Structure Free Sequences by Local Structure Freeness, in Preliminary Proceedings of 9th
International Meeting on DNA Based Computers, pp.206, 2003.
Satoshi Kobayashi, Tomohiro Kondo, Kohei Okuda, and Etsuji Tomita : A method forextracting globally structure free set of sequences, Technical Report of IEICE,COMP2003-16, pp.1-6, 2003.
Structure Free Sequences for Biomolecular Computing, The 990th
American Mathematical Society Fall Eastern Sectional Meeting, Binghamton University, Oct.
11-12, 2003, p.80, 2003 (invited).
Satoshi Kobayashi :Satoshi Kobayashi, Takashi Yokomori, Yasubumi Sakakibara : An Algorithm for Testing
Structure Freeness of Biomolecular Sequences, in Aspects of Molecular Computing --Essays dedicated to Tom Head on the occasion of his 70th birthday, Springer-Verlag, LNCS
Vol. 2950, pp.266-277, 2004.
小林 聡 : 分子計算のための配列設計，第 6 回情報論的学習理論ワークショップ予稿集,
pp.307-314, 2003.
小林 聡 :
2004.

DNA コンピューティングのための配列設計, 情報処理, Vol.45, No.2, pp.164-169,【平成16年度】
16 年度における現在までの研究成果は２つの課題に大別される．その概要を以下で述べる．
(a). 新方式の分子計算モデルの提案と分子基礎実験：分子コンピュータの理論的解析を行い，新しい分子コンピュータ計算モデルの提案を行った [Sakakibara and Imai:04]．具体的には，２つの認識部位をもち，その認識部位から離れた２つの場所で同時に DNA２重鎖を切断する非常に特殊な制限酵素を用いる．次に，環状 DNA 鎖にプログラムをコード化して，アニーリング，DNA ポリメラーゼ伸長，制限酵素による切断，ライゲーション，メルティングという標準的な DNA コンピュータの演算を用いることにより，強力で多機能な DNA 計算方式を開発した．この新しい DNA 計算方式は，万能計算能力をもつ
DNA コンピュータを容易に構築することができる．
(b). 分子配列設計法の考案：前年度に得られた任意有限回の連接によって構成される配列集合の構造非形成検証アルゴリズムを一般化して，任意の正則な配列集合に対する効率の良い構造非形成
検証アルゴリズムを考案した．これは，Condon らが未解決としていた問題を解決したものである．また前年度得られた構造非形成検証アルゴリズムを実装し，最短経路アルゴリズムとしては
Goldberg-Radzig のアルゴリズムが適していることを実験的に確認した．さらに，テンプレート法と構造非形成検証アルゴリズムによる設計法を 2 段に組み合わせた二段階配列設計システムを構築した．

二次構造のクラス① 線形な二次構造
ヘアピンループ、バルジループ、内部ループからなる二次構造
5’3’② シュードノットフリーな二次構造
ヘアピンループ、バルジループ、内部ループ
マルチプルループからなる二次構造
5’3’

シュードノット構造を持たない

Satoshi Kobayashi: Testing Structure Freeness of Regular Sets of Biomolecular Sequences,in Preliminary Proceedings of 10th InternationalMeeting on DNA Based Computers,
pp.395-404, 2004.
Kazuya Nagatsu, Atsushi Kijima, Satoshi Kobayashi: Evaluating Biomolecular Sequences
Using Hydrogen Bond Network Graph, in Preliminary Proceedings of 10th International
Meeting on DNA Based Computers, pp.441, 2004.
Y.Sakakibara and H.Imai : A DNA-based Computational Model using a Specific Type ofRestriction Enzymes, Journal of Automata, Languages and Combinatorics,
Vol.9, No.1, pp.111—119, 2004.
小林聡 ： DNA 計算のための配列集合評価アルゴリズム，第 52 回数理モデル化と問題解決研究会
予稿集, 2004-MPS-52, pp.89-92, 2004.
小林 聡・榊原康文・横森 貴：分子計算の理論モデル, 「分子コンピュータの現状と展望」（萩谷編）,
サイエンス社, pp.32—40, 2004.
榊原康文 ：分子コンピューティングの新しいモデル, 「分子コンピュータの現状と展望」（萩谷編）, サ
イエンス社, pp.84—90, 2004.

４．２ 抽象化学反応計算モデルの研究
主務者：鈴木泰博（東京医科歯科大学）【平成14年度】
細胞内反応計算モデルの研究 ：化学反応における情報伝達のメカニズムを理解することを目的として

京大と共同研究を行い，抽象化学反応系(Abstract Rewriting System on Multisets : ARMS)を用いて化学情報物質による種間の情報伝達が介在する植物ー食植者ー天敵の３者生態系のモデル化を行い，実験と合致する結果を得た．また，Max Plank Institute Chemical Ecology と共同研究を開始し，京大のグループとは異なった３者系のモデル化を行った．さらに，ARMSを用いて炎症反応をモデル化する研究を行った．炎症反応は風邪，喘息，多臓器不全，脳梗塞，心筋梗塞などの重要な疾患の基礎となるものであるが，そのしくみは複雑である．ARMSを用いることにより直観的かつ容易にモデル化を行うことができた．
Yasuhiro Suzuki, Junji Takabayashi, Hiroshi Tanaka :Investigation of tritrophic systemin ecological systems byusing an artificial chemistry, to appear in J.AROB, 2004.

Abstract Rewriting system on Multisets (ARMS)
その特徴

multiset{a,a,a,b,b,c}a,a,b→c{a,a,b,c,c}○ARMSは記号の個数の書き換え系（多重集合の計算モデル）○反応規則の適用方法：
濃度の積に比例して規則を選択し、反応定数によって反応を生じさせる（素朴な化学反応モデル）○計算機科学的な背景：
書き換え系（形式言語理論など）、特にP Systemsとは密接な関係○物理化学的な背景：
化学反応の理論モデルMaster Equationとほぼ等価なモデル【平成15年度】
細胞内シグナル伝達系・化学反応系モデルの設計と実装 ：分子コンピューティングの基礎的な研究として，化学反応の抽象モデル ARMS の研究を応用と理論の両面から行った．応用研究としては癌関連
タンパクとしてよく知られている P53 に関する細胞内シグナル伝達系のモデル化を中心に行った．このモデルは細胞質と核の２つの部分からなり，その各々に分子生物学的な知見を基にして化学反応を定義し，DNA の損傷を活性化された P53 の 4 量体が修復する過程をモデル化した．計算機シミュレーシ
ョンによりこのモデルが分子生物学的な知見と一致するように振舞うことを確認した．また，生物を含めた自己発展系にみられるランダムな構造から相互作用の履歴により構造が出現・発展する系のモデルとして自己強化反応系を構築し，その振舞いを計算機実験を通して調査した．この系では最初はランダムに相互作用が生じるが，相互作用の履歴を持つ分子とのより効率的な反応を促進する"自己強化反応(self-reinforcement reaction)"を仮定すると，分子間相互作用内に構造が出現し，またカタ
ストロフィックな構造崩壊を繰り返す動的な現象が生じることを確認した．理論的な側面からは化学反応の計算論的な特徴付けを目指し，ミラノ大学と共同研究を行った．ARMS と P Systems とを，ある種の確率的 P Systems を構築することで融合させ，非線形化学反応のモデルであるブルセレータのモデル化とシミュレーションを行った．
Yasuhiro Suzuki, Junji Takabayashi, Hiroshi Tanaka : Investigation of tritrophic systemin ecological systems by using an artificial chemistry, J. of Artificial Life andRobotics, Vol. 6, 129-132, Springer-Verlag, Tokyo, 2002.
Yasuhiro Suzuki, Peter Davis, Hiroshi Tanaka : Emergence of auto-catalytic structure instochastic self-reinforcing reaction networks, J. of ArtificialLife and Robotics, Vol.7,
Springer-Verlag Tokyo, (in press).
【平成16年度】
反応速度論ならびに化学量論 (Stoichiometric chemistry)とマルチ集合書き換え系を融合した化学反応の計算モデル(ARMS)と，膜を用いた計算モデル P Systems との関連について考察した．また，ARMSをBioinformaticsにおけるP53シグナル伝達系の動的シミュレーションに適用し，その解析に化
学量論の手法を応用した．
Gh. Paun, Y. Suzuki, H. Tanaka, T. Yokomori：On the Power of Membrane Division in P Systems,
Theoretical Computer Science, 324, 61-85, 2004.
Y.Suzuki and H.Tanaka：Modeling P53 signaling network by using Abstract Rewriting System
on Multisets, a class of P Systems, Applications of Membrane Computing, Natural Computing
series, Springer-Verlag, to appear．

４．３ 並列計算系による分子計算シミュレータの設計と試作
主務者：上田和紀（早稲田大学）【平成14年度】
分子計算系における局所的並列性をシリコン上で実装するために，ノードの多重集合，膜とその階層化，リンク，グラフ変換の４つ概念に基づく新たな計算モデル LMNtal の設計に着手し，基本設計を完了した．また，Java を用いて試作処理系のコンパイラとランタイムを実装した．LMNtal は(i) 多重集合や会合概念をもった数多くの計算モデルの統合(ii) リソースコンシャスな計算の基本モデルなどを目指したモデルであり，14年度は上記に加えて他の計算モデルとの比較検討も進めた．（言語モデル LMNtal の特徴をまとめると図のようになる．)

言語モデル LMNtal (pronounce: elemental) の特徴
階層グラフ（ ⊇ 階層多重集合）書換え言語
 概念統合を目指した並行分散計算モデル


例： 自律プロセス = メッセージ = データ

簡潔な仕様，多様な表現力
計算はグラフ構造の直接操作
膜構造による多重集合とルール局所性の表現
 自己組織化原理によるプログラミングが可能

処理系 (Java) の開発・公開（2004年3月〜）
Kazunori Ueda :http://www.ueda.info.waseda.ac.jp/lmntal/
Java のほとんどの機能が利用可能

A Pure Meta-Interpreter for Flat GHC, A Concurrent Constraint Language,

Computational Logic: Logic Programming and Beyond (Essays in Honour of Robert A. Kowalski,
Part I) (A.C. Kakas, F. Sadri,Eds.)Springer-Verlag, pp.138-161, 2002.
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.
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.
上田和紀, 加藤紀夫: Programming with Logical Links，日本ソフトウェア科学会第19回大会論文集, 2002.(CD-ROM)
加藤紀夫, 上田和紀:モード制約の漸近的一様補強による並行論理プログラムのoccurs-check解析，
日本ソフトウェア科学会第19回大会論文集, 2002.(CD-ROM)
松村量, 高山啓, 高木祐介, 加藤紀夫, 上田和紀: 分散言語処理系DKLIC の設計と実装，日本ソフトウェア科学会第19回大会論文集, 2002.(CD-ROM)
上田和紀,加藤紀夫: GHCからLMNtalへ，情報処理学会 2002年度 夏のプログラミングシンポジウム,
2002.(http://www.ipsj.or.jp/prosym/sprosym/program/index.html)
網代育大，上田和紀：反復深化A*探索によるもっともらしいプログラムの効率的な生成，人工知能学会
全国大会（第17回）論文集，1E3-02, 2002年6月．(CD-ROM)

Yasuhiro Ajiro and Kazunori Ueda :Kima: an Automated Error Correction System for
Concurrent Logic Programs, Automated Software Engineering, Vol.9, No.1, pp.67-94, 2002.
【附記】（2002年度受賞）
上田 和紀：日本ソフトウェア科学会 第19回大会 高橋奨励賞, 2002.(論文題目： Programmingwith Logical Links)【平成15年度】
15 年度は階層的グラフ書換えに基づく並行言語モデル LMNtal について下記の研究開発を行った．
(1) 言語仕様の詳細検討 ：平成 14 年度に設計した基本言語仕様について，セル（膜で囲まれた分子）の複製および消去を実現するための拡張を行った．この拡張を実現するために，プロセス文脈（膜内の不特定多数のアトムとマッチする言語機能）に関する仕様を詳細に再検討し，新たな言語規則の形でまとめた．また上記の拡張に伴い，言語の操作的意味論（構造合同規則および遷移規則）も詳細に再検討し再定義した．
(2) 処理系の開発 ：14 年度の試作処理系をベースに，15 年度には今後開発予定の本格的並列分散処理系開発のベースとなる強固な基準実装の構築を進めることとした． Ruby で全体の枠組を試作したのち，Java で処理系を作成して最初の版を公開した*)．本処理系はまだ開発過程にあるが，LMNtal
言語仕様のうち，プロセス文脈の拡張機能などを除く大多数の機能を提供しており，さらに数値演算などを記述するために書換え規則に条件部（ガード）を指定する機能を設計実装している．また，Java で記述したインラインコードを呼び出す機能および簡単なモジュール化機能を持ち，ライブラリの蓄積による発展の礎を与えることができた．
(3) プログラミング例の蓄積 ：LMNtal の重要な応用分野として自己組織化原理に基づくプログラミン
グがあり，この領域の開拓は分子プログラミングの発展のみならず，プログラミングパラダイム全般にとっても重要である．そこで，自己組織化と関連の深い題材として PCR，セルオートマトン，二分子生物ロ
ボット，平衡二分木などをとりあげ，例題の記述実験を通じて，LMNtal が自己組織化反応のプログラミ
ングのための記述力と簡潔性の両方を備えていることを確認した．
*) http://www.ueda.info.wased.ac.jp/lmntal/

リスト連結プロ
リスト連結プログラム（右）とグラム（右）と
実行スナップ実行スナップショット（下）ショット（下）

Z0

a

X0

Y

A
c

X

Z0

A
c

Z

a
Y

X

Z0

a

X0

Y

n

Z0

=
Y

Kazunori Ueda and Norio Kato : The Language Model LMNta, In Proc. Nineteenth Int. Conf.
on Logic Programming (ICLP'03), LNCS 2916, Springer-Verlag, pp.517-518, 2003.
上田和紀，加藤紀夫： 言語モデル LMNtal．コンピュータソフトウェア, Vol.21, No.2 (2004),
pp.44-60．
稲垣 良一, 上田 和紀 : SMP クラスタにおける効率的な MPI 集団通信関数の実装. 先進的計算基
盤システムシンポジウム SACSIS2003, pp.171-172, 2003 年 5 月.
加藤紀夫，上田和紀： LMNtal プロセスの振舞いの定式化．日本ソフトウェア科学会第 20 回大会論文集，2003 年 9 月，pp.16-20．
矢島伸吾，永田貴彦，加藤紀夫，上田和紀：LMNtal プロトタイプ処理系の設計と実装．日本ソフトウェ
ア科学会第 20 回大会論文集，2003 年 9 月，pp.21-25．
圷 弘明，加藤 紀夫，上田 和紀：LMNtal におけるルールセット不変性の検査．第 6 回プログラミング
およびプログラミング言語ワークショップ (PPL2004)，pp.211-216, 日本ソフトウェア科学会，2004 年 3月．
加藤 紀夫，上田 和紀：並行言語モデル LMNtal におけるプロセス構造の解析．第 6 回プログラミング
およびプログラミング言語ワークショップ (PPL2004)，pp.217-222, 日本ソフトウェア科学会，2004 年 3月．

水野 謙，永田 貴彦，加藤 紀夫，上田 和紀：LMNtal ルールコンパイラにおける内部命令の設計．情報処理学会第 66 回全国大会論文集，5G-2, 2004 年 3 月．
【附記】（2003 年度受賞）
網代育大，上田和紀：人工知能学会 2002 年度全国大会ベストプレゼンテーション賞，2003．（発表題
目「反復深化 A*探索によるもっともらしいプログラムの効率的生成」）【平成16年度】
階層グラフ書換えモデル LMNtal の言語仕様について、ひきつづき形式的意味論の洗練および言語拡張案の検討を進めた．実装については，年度末に公開した処理系の整備拡張とともに，新たに分散処理系の設計と実装を進めている．理論面では，多重集合や膜概念をもつ他の計算モデルとの具体的関連づけの検討を始めた．
加藤 紀夫, 上田 和紀:階層グラフ書換え言語における並行プロセスの型推論,情報処理学会第 50
回プログラミング研究会 (SWoPP2004), July 2004.
原 耕司, 水野 謙, 矢島 伸吾, 永田 貴彦, 中島 求, 加藤 紀夫, 上田 和紀:LMNtal 処理系および他言語インタフェースの設計と実装,情報処理学会第 50 回プログラミング研究会 (SWoPP2004),
July 2004.
Kazunori Ueda and Norio Kato, LMNtal: a language model with links and membranes. In Proc.
Fifth Workshop on Membrane Computing, pp.65-79, June 2004.
大橋智昭, 上田和紀: SAT ソルバ zchaff の MPI による並列化, 先進的計算基盤シンポジウム
SACSIS2004, pp.147-148, May 2004.
大橋智昭, 稲垣良一, 上田和紀: SAT ソルバ zchaff の MPI による並列化, 情報処理学会研究報告,
2004-HPC99-5 (SWoPP2004), pp.25-30, July 2004.
加藤紀夫，水野謙，上田和紀： 言語モデル LMNtal の操作的意味論の設計，日本ソフトウェア科学会
第 21 回大会論文集，2004．
中島求，加藤紀夫，水野謙，上田和紀： LMNtal 分散処理系の設計と実装，日本ソフトウェア科学会
第 21 回大会論文集，2004．
上田和紀： プログラムと対称性，夏のプログラミングシンポジウム「アッと驚くプログラミング」報告集，情報処理学会，pp.69-74, 2005.
中島 求，加藤 紀夫，水野 謙，上田 和紀： LMNtal を用いた分散処理の実現，第 8 回 プログラミン
グおよび応用のシステムに関するワークショップ(SPA 2005)，2005 年 3 月．
Kazunori Ueda and Norio Kato： LMNtal: a Language Model with Links and Membranes. To apperin Proc. Fifth Workshop on Membrane Computing, LNCS 3365, Springer-Verlag, 2005.

５．今後の課題
まず上述の各研究項目について今後の課題について述べ，さらに展開すべき新たな方向性について簡単にふれる．
自律的分子計算系の基礎的考察：自律的な計算モデルの構築と設計に関しては，現在までに提案されている幾つかの有力なモデルの中から，実装可能性，計算能力，および並列計算可能性の視点に立ってバランスの良い計算モデルを再構築していく必要があると思われる．特に，In Vitro実験における実現可能性を考慮すると，近似的・確率的な要素を取り入れた拡張計算モデルの開発が不可欠であると思われる．また，考察し提案した計算モデルが機能するかの検証は重要であり，小規模なバイオ実験も行いたいと考える．
分子配列の設計論に関しては，現在までの構造フリーな配列の設計法を一般化することにより，特定の構造をとる分子配列集合の設計論を展開することが考えられる．
抽象化学反応計算モデルの研究：分子計算におけるタンパク質の利用は重要なアイディアのひとつであり，特にP53タンパクは細胞をDNA修復と細胞死の2つの状態に誘導する．これまではDNA修復の系をモデル化してきたが，今後はミラノ大学などとの共同研究により，細胞死関連のモデル化も行い，この2つの系を融合したものの計算機シミュレーションを行う予定である． このようなARMSを基本としたモデリ
ングとシミュレーションによる実験結果を通して，細胞内のタンパク質の変化に基づく新しい計算モデルの開発を視野にいれて研究する予定である．
従来からこうしたシミュレーションでは各種パラメータ（反応速度定数など）の実験データを揃えるという根源的な困難さがあるが，ARMSが化学量論のモデルであることから，従来からの代謝量の化学量論的解析手法として研究されているConservation Analysisなどを用いることにより，計算系内部での生成と消費をバランスさせるための条件式や反応式を見出すことができると期待される．
並列計算系による分子計算シミュレータの設計と試作：当初からの目的であるが，並列計算言語
LMNtal の開発の完了を契機として，この言語体系を基に分子計算系における種々の計算メカニズムの実装可能性を検証するための「バーチャル分子計算環境」の実現を目指す．これらのシミュレーショ
ン実験系を利用することにより，バイオ実装可能性の検証のみならず，現実の世界にはまだ存在しな
い人工的な分子の仮想的性質・機能の検証も可能になることが予想される．
上述の各研究項目に加えて，“自律的解析計算モデル”の研究も試みたい．従来の自律的計算モ
デルでは，符号化配列からなる基本プログラム群と入力分子とが与えられたとき，自律的に解分子が生成され構造化される方向に計算が進むのが通例である．これとは逆に，計算を「ある規則的な構造体からはじめ，プログラム分子群により徐々にその構造が解析されていく」という過程としてとらえる考えも可能であろう．この逆計算の利点のひとつは，自律的に生成する場合に比べエラー率が少なくなるのではと予想される．また，問題のクラスによっては計算時間の効率化も期待できると思われる．
これらの Non-standard な計算原理をさらに一般的に研究することも視野に入れておきたい．分子計
算系における計算素子は分子，超分子から始まり，今やタンパク質，ホルモン，免疫系システム，細胞（膜），ウイルス，微生物（単体），多数の微生物の集団へと多様なレベルにまで広がりを示している．これらのいわゆる自然計算系の研究への貢献の可能性も検討したい．

６．研究費の使用状況

本研究班は分子計算の理論モデルの構築を主要な課題としている．そのため，本特定領域研究での
平成 14 年度から本年度までの３年間における全予算の使用内訳の概要は，計算機設備を主体とした基盤的設備備品の整備に約７割，研究成果の発表や共同研究のための研究出張に約 1.5 割，年度毎に必要不可欠な消耗品の充当に約 1.5 割を各々使用している．
設備備品の使用状況に関する具体例として，横森，榊原，小林の「自律的分子計算系」では配列設計のための計算機実験を，また鈴木は「抽象化学反応系」の計算機シミュレーションを行っており，15
年度購入した高機能 PC システムを有効利用している．また，上田は「分子計算シミュレータ」の実装のため，購入した PC サーバ群から構成された大規模な計算機資源を効果的に利用している．
研究出張などの旅費の使用状況に関しては，海外での国際会議での招待講演，一般発表をはじめとして，内外の大学・研究機関との共同研究，情報交換，および班合同の研究活動のための旅費として有効に使用され，多くの研究成果を学術誌・会議録などに発表している．