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

1

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

2

研究成果概要本年度の研究成果のいくつかを概説する. 文献番号は次節に掲載する研究業績リスト番号である.
山下は, 自律分散ロボットの制御方法について検討した [1, 2]. 自律分散ロボットは自律的に動作する多くのコンポーネントから構成されるロボットで，自由に形を変えながら移動し，所期の目的を達成する．精密機械の研究者は分子程度の大きさのコンポーネントをアドガボロ数程度の個数だけ組み合わせてできる自律分散ロボットを既にその視野に入れて研究を進めているが，これはほとんど分子プログラミングの研究領域である．また，このような巨大分散システムの振る舞いを統計的に解析することを目指して, 有限グラフ上のランダムウォークの振る舞いを解析した [3, 4]. 分子の統計的な振る舞いを知ることが効率的な分子プログラムを作成するために不可欠であると考えられ, 上記の解析技術はそのための基礎技術となる. 巨大なシステムでは必ず故障するコンポーネントが現れ∗ 九州大学大学院システム情報科学研究院 ({mak,sakurai,sada,ono}@csce.kyushu-u.ac.jp)† 九州産業大学情報科学部 (asahiro@is.kyusan-u.ac.jp)‡ 広島大学工学部 (fujita@se.hiroshima-u.ac.jp)§ 九州大学大学院数理学研究院 (ym@math.kyushu-u.ac.jp)¶ 熊本県立大学総合管理学部 (sadahiro@pu-kumamoto.ac.jp)

1

る．そこで，その制御に必須の要請は故障に対する強度である．この立場から，山下は耐故障アルゴ
リズムを検討した [5, 6].
先に，横森班との合同会議から共通の研究テーマとして DNA 設計問題が浮上したことを述べた．
そのためには，分子の二次構造を特定し，その変化について理解することが必要になる．定兼は，分子計算における計算速度の見積もりのために，分子の二次構造の変化をマルコフ過程とみなし，分子が安定状態に至るまでの時間の解析を目指した [7]. また，DNA 配列の高速検索のためのデータ構造とその構築アルゴリズムについて研究した [8, 9, 10]．従来法ではデータ構造構築のために大量の一時的な記憶領域が必要であったが，新しいアルゴリズムによりこれを削減することができた．
最適問題は DNA 設計問題の別の側面である．分子の反応性質/速度に強い関わりを持つと考えられているのが, 反応におけるエネルギー障壁である. エネルギー障壁は, 反応経路の中間物質 (分子)の最大の自由エネルギー値（の最小値）として定義される. 一般に分子反応は原子数の指数サイズの中間物質を経て起こるため, 単純な探索でこのエネルギー値を求めるのは不可能である．朝廣，小野，
山下はエネルギー障壁を求める問題を組合せ最適化問題として定式化し, 実用的な計算時間でこれを求めるアルゴリズムを検討中である．本年度はこのために必要な道具となる, 組合せ最適化問題に対するメタ戦略アルゴリズムの設計・並列化に関する研究を中心に行った [11, 12].
分子計算のモデルとして，セル・オートマトン，タイリング，グラフ書き換えシステムなどが検討されている．溝口は量子セル・オートマトンとグラフ書き換えシステムについて考察した [13, 14] 文
献 [13] は量子計算の分子計算による模倣という問題意識から検討が開始されたものであり，量子セル・オートマトンの (局所) 遷移関数に要請される条件を調べている．文献 [14] ではラベルと確率情報を持ったグラフが考察対象である．1 つのグラフ (式) はそのラベル情報で規定される複数のグラフの集合を表現する. 集合内のグラフ全体へのグラフ変換を一括して行う操作をその表現グラフ式への変換として定式化する. このグラフの集合への変換は, 分子プログラミングのモデルを考える際の複数の遺伝子集合に対しての一括変換を表現するために有効である．貞広はタイリングを考察している．Winfree たちは誤ったタイリングも多くの場合に自動的に訂正されるような機能を持ったタイルの設計とその訂正メカニズムを提案しているが，貞広の問題意識も同じ所にある [15]．
櫻井は一方向性関数と分子現象の非可逆性に関する調査研究を行った．Adlemann は分子の非可逆現象をモデルに一方向性関数の理論を展開した. その後, 一方向性関数は暗号理論の発展に伴い大きく進歩するが, 分子現象の非可逆性への演繹まではいたっていないようであることを認識した. つぎに，ソフトウエア工学の立場から，ソフトウエアの解析をより困難にする技術（難読化）を研究した[16, 17] プログラムの著作権保護などで注目される技術であるが, このようなプログラムの複雑性を分子モデルで論じることが次年度の課題である.
Papadimitriou らは，与えられた問題例のランドスケープを進化の概念に基づいてより滑らかなものに変化させ，問題例をより高速に解くことを提案している．一方，先に説明したように DNA 設計問題がある与えられた塩基列の二次構造間の遷移可能性が組合せ最適化問題として定式化され検討されている．藤田は，後者を前者の方針で解決することを目指して，Papadimitriou らのメタ解法をTSP を対象として追試を行うとともに，問題例の進化に関する新しい方法の提案とその実験的評価を行った [18, 19]．つぎに，DNA 配列の安定性に関する新しい尺度として，グラフの極大マッチング数に着目し，先行研究の調査を行うとともに，数値実験とその理論的解析を行った．

3

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

2

参考文献
[1] A. Dumitrescu, I. Suzuki, and M. Yamashita: “High Speed Formations of Reconfigurable Modular
Robotic Systems,” Int’l Journal on Robotic Research (to appear).
[2] A. Dumitrescu, I. Suzuki, and M. Yamashita: “Motion Planning for Metamorphic Systems: Feasibility,Decidability and Distributed Reconfiguration,” IEEE Trans. Robotics and Automation (to appear)[3] S. Ikeda, I. Kubo, N. Okumoto, and M. Yamashita: “Impact of Local Topological Information onRandom Walks on Finite Graphs,” Proc. 30th International Colloquium on Automata, Languages andProgramming (ICALP2003), June 30 - July 4, 2003, Eindhoven, Netherlands, 1054–1067, 2003.
[4] S. Ikeda, I. Kubo, and M. Yamashita: “Reducing the Hitting and the Cover Times of Random Walks
on Finite Graphs by Local Topological Information,” The 2003 International Conference on VLSI(VLSI’03) June 23-26, 2003, Las Vegas, Nevada, USA, 203–207, 2003 .
[5] T. Harada and M. Yamashita: “k-Coteries for Tolerating Network 2-Partition,” IEEE Trans. Paralleland Distribted Systems (to appear).
[6] Takashi Harada and Masafumi Yamashita: “Transversal Merge Operation and Nondominated GridCoteries,” Proc. 15th IASTED International Conference Parallel and Distributed Computing and Systems (PDCS 2003), November 3-5, 2003, Marina del Rey, CA, USA, 128–133, 2003.
[7] J. Jansson, 定兼邦彦, W.K. Sung, 塩崎真史, 山下雅史: “局所情報を用いたランダムウォークの拡張,”
IPSJ SIG Notes, SIGAL-92-3, 2003.
[8] K. Sadakane: “New Text Indexing Functionalities of the Compressed Suffix Arrays,” Journal ofAlgorithms, 48, 2, 292–313, 2003.
[9] W.K. Hon, K. Sadakane and W.K. Sung: “Breaking a Time-and-Space Barrier in Constructing FullText Indices,” Proc. IEEE FOCS, 251–260, 2003.
[10] W.K. Hon, T.W. Lam, K. Sadakane and W.K. Sung: “Constructing Compressed Suffix Arrays withLarge Alphabets,” Proc. ISAAC, LNCS 2906, 240–249, 2003.
[11] 石橋正裕，小野廣隆，朝廣雄一，山下雅史: “メタ戦略アルゴリズムに対するロバストな並列化” 数理解析研究所講究録 1325, pp.1-7, 2003 年 6 月.
[12] M. Ishibashi, Y. Asahiro, and M. Yamashita: “Independent and Cooperative Parallel Search Methods
for the Generalized Assignment Problem,” Optimization Methods and Software, 18,2,129-141, 2003.
[13] 井口修一, 溝口佳寛: “巡回型量子セルオートマトンの挙動について,” 応用数学合同研究集会報告集, 85-88,
2003 年 12 月.
[14] 溝口佳寛, 森雅生: “グラフの集合を表現するラベル付グラフについて” 火の国情報シンポジウム 2004, 2004
年 3 月 (発表予定).
[15] 貞広泰造: “ランダムタイリングの数値シミュレーション,” 数理解析研究所講究録

2004 年.

[16] Kazuhide Fukushima, Toshihiro Tabata, and Kouichi Sakurai: “Proposal and Evaluation of Obfuscation Scheme for Java Source Codes by Partial Destruction of Encapsulation,” International Symposiumon InformationScience and Electrical Engineering 2003 (ISEE 2003), Nov. 2003.
[17] Kazuhide Fukushima, and Kouichi Ssakurai “A Software Fingerprinting Scheme for Java Using Classfiles Obfuscation,” Proc. of the 4th International Workshop on Information Security Applications(WISA2003), 337-350, Aug. 2003.
[18] M. Mito and S. Fujita: “On Heuristics for Solving Winner Determination Problem in CombinatorialAuctions,” 2003 IEEE/WIC International Conference on Intelligent Agent Technology (IAT 2003),
October 13-17, Halifax, Canada, 25-31 2003.
[19] S. Fujita and A. Nakatani: “A Vehicle Scheduler for On-Demand Bus Systems Based on a Heuristic
Cost Estimation,” IEEE 2003 International Conference on Intelligent Transportation Systems (ITS2003), October 12-15, Shanghai, 1194-1199 2003.

3