特定領域「分子プログラミング」平成 17 年度報告書

自律的分散型計算としての分子計算
山下雅史∗ , 櫻井幸一∗ , 横尾真† , 朝廣雄一‡ ,定兼邦彦∗ , 藤田聡§ , 溝口佳寛¶ , 貞廣泰造k , 小野廣隆∗

1

研究目的と研究実施状況
分子計算には計算過程の物理的拘束や選択的ランダム性など, 自律性が由来すると期待される魅力的な側面を有するものの, 現在の所は, ごく大雑把に言えば, 塩基間の相補性を計算規則とする超並列シラミ潰し探索に留まっている. そこで, 分子計算の特徴を生かした分子プログラムの設計論の開発が焦眉の課題であり, これが本特定領域研究を行う目的の一つであった.
分子計算の自然な見方の一つは個々の生体分子をエージェントとする自律的分散型システムと捉えることである. このようにすれば, 分子計算をインターネットなどの計算機ネットワークや群ロボットシステムなど他の分散型システムと同じ観点から検討できるとともに, セルオートマトンやタイリングといった, 計算機科学者にとってなじみの分野で蓄積されてきた多くの研究成果を自然に継承できると期待できる. これが九州-広島班の分子計算に対するアプローチ方法である.
本年度は，基本的に各自で研究を進め，数ヶ月に一度設ける横森班との合同会議で，各自の研究進捗報告，研究の方向性の確認を行う形で本研究課題に取り組んだ．これは一昨年度，昨年度に確立されたスタイルである．今年
度は特に，横森班・本班共通の研究課題として取り組んでいる DNA 設計問
題，またタイリングおよびグラフ書き換えシステムの観点に焦点を当てた形で研究を進めた．なお，本班の活動状況の一端は本科研のホームページからリンクされている九州-広島班ホームページに紹介されている．

∗ 九 州 大 学 大 学 院 シ ス テ ム 情 報 科 学 研 究 院 情 報 工 学 部 門 {mak,sakurai,sada,ono}@csce.kyushu-u.ac.jp† 九州大学 大学院システム情報科学研究院 知能システム部門 yokoo@is.kyushu-u.ac.jp‡ 九州産業大学情報科学部 社会情報システム学科 asahiro@is.kyusan-u.ac.jp§ 広島大学大学院工学研究科情報工学専攻 fujita@se.hiroshima-u.ac.jp¶ 九州大学大学院数理学研究院 ym@math.kyushu-u.ac.jp
k 熊本県立大学総合管理学部総合管理学科 sadahiro@pu-kumamoto.ac.jp

1

2

研究成果概要本年度の研究成果のいくつかを概説する. 文献番号は次節に掲載する研究業績リスト番号である.
先に，横森班との合同研究会を通して，DNA 設計問題が共通の重要な研究課題として捉えられていることを述べた．この重要な視点として，分子の二次構造を特定し，その変化について理解することがあげられる．定兼，山下は，分子計算における計算速度の見積もりのために，分子の二次構造の変化をマルコフ過程とみなし，分子が安定状態に至るまでの時間の解析を目指した [1, 2].
一方，分子の反応性質/速度に強い関わりを持つと考えられているのが, 反応におけるエネルギー障壁である. エネルギー障壁は, 反応経路の中間物質(分子) の最大の自由エネルギー値（の最小値）として定義される. 一般に分子反応は原子数の指数サイズの中間物質を経て起こるため, 単純な探索でこのエネルギー値を求めるのは不可能である．小野，山下はエネルギー障壁を求める問題を組合せ最適化問題として定式化し, 実用的な計算時間でこれを求めるアルゴリズムを提案した [3]．
組合せ最適化は DNA 配列設計のもう一つの側面である．朝廣は，DNA 配列設計において，その最も基本的な制約条件である，ハミング距離，G と Cの含有量，相補列とのハミング距離とそれらの組み合わせの条件を考慮した配列設計アルゴリズムを提案した．いずれも貪欲アルゴリズムに基づいた単純なアルゴリズムながら，長さの短い配列の設計においては，既知の方法と遜色ない大きさの配列集合を出力することが分かった．また，理論的な複雑さについての一考察を与えた [5]．配列設計問題に関しては，小野，定兼，山下も取り組んでおり，局所探索に基づくアルゴリズムを用いて，既存手法よりも良い評価尺度を満たす配列集合の設計に成功している [4]．この他にも，生物配列の解析に用いられる隠れマルコフモデルの，配列設計への適用可能性についての調査も行っている [6]．
分子計算は，分子同士の局所計算（分子反応）から導かれる大域計算と捉えることが可能である．溝口は局所計算を 1 つのグラフの変換, 大域計算をグラフの集合上の変換と捉え, 確率的に大域計算の性質を考察するための枠組みとシミュレータを開発し提案している [7]. 量子セルオートマトンは，古典的な遷移規則を厳密に定義したセルオートマトンを，緩やかな遷移規則へと拡張したという側面を持つ．これに対する挙動の確率的評価を行ったのが
文献 [8, 9] である. これは，同じく緩やかな遷移規則に基づく分子計算を解析するのに有用と考えられる．また，分子計算の超大規模性を擬似連続と捉える立場がある．セルオートマトンのような（有限）離散系のシステムを，連続系の微分方程式の超離散化に基づき解析し，知見を得ている [10].
貞廣はタイリングを考察している．Winfree たちは誤ったタイリングも多2くの場合に自動的に訂正されるような機能を持った DNA タイルの設計とその訂正メカニズムを提案している. この際，DNA タイリングは確率的に起こるため，生成されるタイリングの成す分布を解析できることが望ましい．ある種の一次元力学系から生成される平面の準周期性をもつタイル貼りの基本的な性質について調べることにより，この分布に関する知見を得ている [11].
櫻井は一方向性関数と分子現象の非可逆性に関する調査研究を行った．Adle-mann は分子の非可逆現象をモデルに一方向性関数の理論を展開している．櫻井は，特に一方向性ハッシュ関数の分類と性質の観点から分子現象の非可逆性に関する調査を行っている [12, 13].
藤田は，進化的計算に DNA 計算を利用するための具体的な手法について研究をおこなっている．今年度は、問題を DNA 上にマッピングする際の問題のひとつであるリンケージ同定問題に焦点をあて、組合せ最適化問題におけるオブジェクト間の関係の強さに注目した新しいリンケージ同定手法の提案と評価をおこなった [14].
横尾は，分散制約充足／プランニングおよびメカニズムデザインに関する研究を進めた. これらは，大規模分散システムとみなすことのできる「分子コンピュータ」上での適用が期待される応用問題である [15, 16]. なお関連する研究成果に対して，第二回学士院学術奨励賞が授与されることとなった．

3

研究成果
前節で触れた結果に関する業績だけをリストアップした. 各人のそれ以外の業績については各人のホームページを参照頂きたい.

参考文献[1] Masashi Shiozaki, Hirotaka Ono, Kunihiko Sadakane and Masafumi
Yamashita, Modeling DNA Conformation Change and TheoreticalAnalysis on the Reaction Rate, Preproceedings of the 11th International Meeting on DNA Computing, DNA11, 408, 2005.
[2] 塩崎真史, 小野廣隆, 定兼邦彦, 山下雅史, DNA 分子の濃度と反応速度の関係解析, 数理解析講究録、『計算機科学基礎理論とその応用』, 2006.
[3] T. Takeda, H. Ono, K. Sadakane and M.Yamashita, A Local Search
Based Barrier Height Estimation Algorithm for DNA Molecular Transitions, Preproceedings of the 11th International Meeting on DNA Computing, DNA11, 354-365, 2005.

3

[4] 川下優，小野廣隆，定兼邦彦，山下雅史，局所探索法を用いた塩基配列
集合設計，火の国情報シンポジウム 2006, 2006 年 3 月.
[5] Y. Asahiro, Simple Greedy Methods for DNA Word Design, Proc. 9thWorld Multi-Conference on Systemics, Cybernetics and Informatics,Vol.III, pp.186-191, Jul. 2005.
[6] 前村一哉，小野廣隆，定兼邦彦，山下雅史，隠れマルコフモデルを用いた DNA 配列設計, 火の国情報シンポジウム 2006, 2006 年 3 月.
[7] Y.Mizoguchi and W.Kahl, Tagged Choice Graph Transformations (Abstract) Proc. of the 11th international meeting on DNA computing,p.405, June 2005, London, Canada.
[8] N. Inui, S. Inokuchi, Y. Mizoguchi, N. Konno, Statistical propertiesof a quantum cellular automaton, Physical Review A, Vol.72(2005),
032323(8pages).
[9] S. Inokuchi, K. Honda, H. Lee, T. Sato, Y. Mizoguchi, Y. Kawahara
On reversible cellular automata with finite cell array. Proc. 4th International Confeence on Unconventional Computation, Lecture Notes in
Computer Science, Vol.3699(2005), pp.130-141.
[10] Mikoda,A., Inokuchi,S., Mizoguchi,Y., The number of orbits of periodic
box-ball systems, 応用数学合同研究集会報告集, 63-66, 2005 年 12 月.
[11] T. Sadahiro, Multiple points of tilings associated with Pisot numeration
systems, to appear in Theoretical Computer Science.
[12] W. Lee, P. Sarkar, S. Lee, M. Nandi, D. Chang K. Sakurai, PGV
Style Block-Cipher-Based Hash Families and Black Box Analysis, IEICE Transactions, Vol.E88-A, No.1, pp. 39・8, (1, 2005)[13] M. Nandi, K. Sakurai, W. Lee, S. Lee, Security Analysis of a 2/3-Rate
Double Length Compressio Function in the Black-Box Model, FSE
2005, pp. 243・54, Feb. 2005.
[14] Shin’ichiro Umezane, Satoshi Fujita, On Linkage Identification in EC
for Solving Combinatorial Optimization Problems, In Proc. The International Conference on Systems, Man and Cybernetics (SMC2005),IEEE, Oct. 2005.
[15] Marius Silaghi, Makoto Yokoo, “Nogood-based Asynchronous Distributed Optimization (ADOPT-ng)”, Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS06), to appear.
4[16] Emma Bowring, Milind Tambe, and Makoto Yokoo, “MultiplyConstrained Distributed Constraint Optimization” Fifth International
Joint Conference on Autonomous Agents and Multi-Agent Systems(AAMAS-06), to appear.

5