自律的分散型計算としての分子計算
山下雅史 （九州大学大学院システム情報科学研究院）

1. 研究の目的
分子計算には計算過程の物理的拘束や選択的ランダム性など,自律性が由来すると期待される魅力的な側面を有するものの,現在の所は, ごく大雑把に言えば,塩基間の相補性を計算規則とする超並列シラミ潰し探索に留まっている.このため, 分子計算の特徴を生かした分子プ
ログラムの設計論の開発が焦眉の課題であり,これが本特定領域研究を行う目的の一つであった.
分子計算の自然な見方の一つは個々の生体分子をエージェントとする自律的分散型シス
テムと捉えることである. このようにすれば, 分子計算をインターネットなどの計算機ネットワー
クや群ロボットシステムなど他の分散型システムと同じ観点から検討できるとともに, セルオート
マトンやタイリングといった, 計算機科学者にとってなじみの分野で蓄積されてきた研究成果の自然な継承が期待できる. 無論, 分子計算の物理・化学・生物学的特性から，研究成果そのものを直接適用することは必ずしも容易ではないが，それぞれの研究分野の視点で持って分子計算の本質・特性を明らかにすることが可能となる．これが本研究班の分子計算に対する基本的なアプローチである.

2. 研究項目と役割分担
先に述べたように，本班のおおまかな研究アプローチは，分子計算を自律的分散型のシステ
ムとみなすことにより現れる理論計算機科学上の諸問題を解決すること，またこれにより分子計算システムの特性を理解することにある．この「諸問題」を大きく次の 3 つに分類する：
1. 分子計算の自律分散システムとしての特性を明らかにすること，
2. 分子計算の計算モデルに関する研究
3. 分子計算のシステム設計を行ううえで現れる，諸々の最適化問題の解決
ここで「分類」と述べたが，より正確には「切り口」であり，分子計算を既存の理論計算機科学の立場で分析する上での視点である．すなわち，対象はやはり「分散システムとしての分子計算」であり，これを多面的な角度から解析する，というのが本研究班の研究方針である．
さて，本研究班の構成メンバーは以下のとおりである．

山下雅史（九州大学・大学院システム情報科学研究院・教授）
櫻井幸一（九州大学・大学院システム情報科学研究院・教授）
横尾真 （九州大学・大学院システム情報科学研究院・教授） （平成 16 年度から参加）
朝廣雄一（九州産業大学・情報科学部・助教授）
定兼邦彦（九州大学・大学院システム情報科学研究院・助教授） （平成 15 年度から参加
藤田聡（広島大学・大学院工学研究科・助教授）
溝口佳寛（九州大学・大学院数理学研究院・教授）
貞広泰造（熊本県立大学・総合管理学部・講師）
小野廣隆（九州大学・大学院システム情報科学研究院・助手）
以下，各研究項目とその分担について述べる．

分子計算と自律分散システム
研究目的で述べたように，分子計算システムの振る舞い・性質を理解する上で，生体分子をエージェントとする自律的分散型システムとしての視点から考察を行う．具体的には大規模分散システムにおけるランダム性を持った分散アルゴリズム，自律分散型ロボットの制御， 各種の制約条件下で自律的に解を探索するエージェントシステム，について研究する．これらはそれ
ぞれ，自律性，ランダム性，物理・化学的制約など分子計算の持つ特性に着目しており，分子計算の定量・定性的性質を議論する上で欠かせない視点であるといえる．山下が大規模分散システム・自律分散ロボットの視点から，横尾が分散システム上での制約充足問題の視点から研究する．

分子計算の計算モデル
分子計算を考える上で重要となるのが，その背景にある物理・化学現象としての性質（これは反応の非可逆性，自己組織化現象なども含む）であり，これらを表現・実現できるモデルとして考えられているのが例えばタイリングである．ここでは，主にタイリング，グラフ書き換えシステム，
セルオートマトンなど，既存の計算機科学分野の理論をもとに，分子計算の計算過程の表現・解析のためのモデル構築を模索する．
櫻井は一方向性関数と分子現象の非可逆性の関連についての研究を行う．溝口はセルオー
トマトンを使ったモデル, グラフ変換を使ったモデルの 2 通りの方法から分子計算の計算モデルの構築に取り組む．貞広はタイリングの観点からこれに取り組む．

分子計算における最適化問題
分子計算は，DNA 塩基の相補性に基づく結合・解離を計算規則と見なすことにより行われる．
相補性とはアデニン(A)とチミン(T)，グアニン(G)とシトシン(C)が水素結合するというものである．

この結合・解離は大まかに言うと物理・化学的現象であり，単純に全ての A が T と，G が C と結合するわけではなく，多くの制約の下，「起こりやすい」結合・解離が実際に起こると考えられている．ここで，例えば「与えられた制約の下で，最も起こりえる DNA の二次構造はどのようなものか」という問題が現れるが，これは計算機科学の中で言われる最適化問題と見なすことができる．
このように，分子計算，特に分子計算における DNA 配列設計においては数多くの「最適化問題」が顔を出すことになるが，これらを組織的に解決する手段を確立することが，実際に分子「プログラミング」を行ううえでの急務となる．
このような立場から，山下，朝廣，藤田，小野は，特に配列設計問題に注目し，組合せ最適化問題として定式化することにより，これらを効率的に解決する方法について模索する．定兼は DNA 分子を文字列と見なし，その高速な検索手法を構築することにより，諸問題の解決を図る．

3. 活動状況と班内の連携
本研究班の活動は，研究活動は各人が進めるとともに必要に応じて集まり議論する，というス
タイルをとっている．ただし，研究班としての方向性の確認，意見交換などの必要性から，年数回の班会議を設けている．また後述のように，東京の横森班とも定期的に会合を設けている．
以下，発足から現時点までの班活動について概説する．まず発足年度の平成 14 年度は，分子計算に対する本研究班としてのアプローチ，共通問題について確認するとともに，分子計算自体への理解を深めるため，2 度の班会議（会合）を九州大学にて設け，議論を行った．
平成 15 年度の班活動の大きな変化としては，第一に，横森班との合同会議を定期的に開催することになったことがあげられる．両班共通の研究課題として DNA 設計問題が浮上し，その検討を行っている．次に，九州-広島班（本研究班）内部において，タイリングおよびグラフ
書き換えシステムに関する会議を定期的に開催することになったことがある．タイリング，グラフ
書き換えシステムあるいはセルオートマトンは分子計算の基本的な理論モデルであり，本研究班の活動の中核になると期待している．
平成 16 年 8 月まで行われた研究会・会合は以下のとおりである．
平成 14 年度
第 1 回班会議 (H14.10.7)
第 1 回研究会 (H14.12.9)
理論関係研究会 (H.15.1.10-11)
平成 15 年度
第 1 回班研究会 (H15.6.19)

第 2 回班研究会（タイリングセミナー） (H15.11.20)
第 1 回理論班合同会議, 早稲田大学 (H15.11.22)
理論班合同研究会(H15.12.22-24)
第 3 回班研究会（タイリングセミナー） (H16.1.28)
第 2 回理論班合同会議, 早稲田大学 (H16.1.31)
平成 16 年度
第 1 回理論班合同会議, 早稲田大学 (H16.5.22)
第 2 回理論班合同会議, 九州大学 (H16.7.11)

4. 各項目の研究報告
現在までの研究成果のいくつかを，2 節で述べた項目ごと年度順に概説する.

4.1

分子計算と自律分散システム

平成 14 年度報告
山下は，巨大分散システムの振る舞いを統計的に解析することを目指して，有限グラフ上のランダムウォークの振る舞いを解析した[IOKY02, IKY02].分子の統計的な振る舞いを知ることが効率的な分子プログラムを作成するために不可欠であると考えられ, 上記の解析技術はそのための基礎技術となる.つぎに，一過性の故障から自律的に復帰するような分散システムである自己安定システムについて検討した[KY02]. 自己安定システムは初期化がまったく必要のないシステムとして特徴付けられる. 分子プログラミングは，多くの分子を含むシステムを対象とするが， 制御対象を理想的に̀̀初期化''することは困難であると考えられる. このような不安定な初期状況から実行を行っても正しい結果を返すシステムはその意味で自己安定的であると考えられる.
業績[IOKY02] S. Ikeda, N. Okumoto, I.Kubo, and M. Yamashita: ̀̀Fair Circulation of a Token,''IEEE Trans. Parallel and Distributed Systems 13, 4, 367--372 (2002).
[IKY02] S. Ikeda, I. Kubo, N. Okumoto, and M. Yamashita: ̀̀Local Topological Information
and Cover Time,''(submitted to Siam J. Computing).
[KY02] H. Kakugawa and M. Yamashita: ̀̀Uniform and Self-Stabilizing Fair Mutual Exclusion
on Unidirectional Rings with Unfair Distributed Daemonʼʼ, Journal of Parallel andDistributed Computing 62, 885--898 (2002).

平成 15 年度報告
山下は, 自律分散ロボットの制御方法について検討した [DSY03a,b]自律分散ロボットは自律的に動作する多くのコンポーネントから構成されるロボットで，自由に形を変えながら移動し，

所期の目的を達成する．精密機械の研究者は分子程度の大きさのコンポーネントをアドガボ
ロ数程度の個数だけ組み合わせてできる自律分散ロボットを既にその視野に入れて研究を進めているが，これはほとんど分子プログラミングの研究領域である．また，このような巨大分散シ
ステムの振る舞いを統計的に解析することを目指して,有限グラフ上のランダムウォークの振る舞いを解析した[IKOY03, IKY03]. 分子の統計的な振る舞いを知ることが効率的な分子プログ
ラムを作成するために不可欠であると考えられ, 上記の解析技術はそのための基礎技術となる.巨大なシステムでは必ず故障するコンポーネントが現れる．そこで，その制御に必須の要請
は故障に対する強度である．この立場から，山下は耐故障アルゴリズムを検討した[HY03].
業績[DSY03a] A. Dumitrescu, I. Suzuki, and M. Yamashita: ̀̀High Speed Formations ofReconfigurable Modular Robotic Systems,'' Int'l Journal on Robotic Research (to appear).
[DSY03b] A. Dumitrescu, I. Suzuki, and M. Yamashita: ̀̀Motion Planning for Metamorphic
Systems: Feasibility, Decidability and Distributed Reconfiguration,'' IEEE Trans. Robotics

and Automation (to appear)[IKOY03] S. Ikeda, I. Kubo, N. Okumoto, and M. Yamashita: ̀̀Impact of Local Topological
Information on Random Walks on Finite Graphs'', Proc. 30th International Colloquium on

Automata, Languages and Programming (ICALP2003), June 30 - July 4, 2003, Eindhoven,
Netherlands, 1054--1067, 2003.
[IKY03] S. Ikeda, I. Kubo, and M. Yamashita: ̀̀Reducing the Hitting and the Cover Times ofRandom 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 .
[HY03] T. Harada and M. Yamashita: ̀̀Transversal Merge Operation and Nondominated Grid
Coteries,'' Proc. 15th IASTED International Conference Parallel and Distributed Computing

and Systems (PDCS 2003), Nov. 2003, Marina del Rey, CA, USA, 128--133, 2003.

平成 16 年度報告
山下は前年度に引き続き，分散システムの耐故障性の観点から研究を進めている[HY04].
分子計算に対する一つの自然な見方として，個々の生体分子をエージェントとする自律的分散型システムとして捉えるというものがあることは先に述べた．この「自立的分散型システム」
では，個々のエージェントが物理・化学的制約を満たしながら自律的に行動することにより解に辿り着く，という性質を持つ．この観点から，横尾は分散制約充足／プランニングおよびメカ
ニズムデザインに関する研究を進めている．なお，これらの研究の一つが，7 月に米国ニューヨークで開催された自律エージェントおよびマルチエージェントシステムに関する国際会議(AAMAS-2004) で最優秀論文賞を受賞した．
業績

[HY04] T. Harada and M. Yamashita: ̀̀k-Coteries for Tolerating Network 2-Partition,''IEEE Trans. Parallel and Distributed Systems, 15, 7, 666-672, (2004).
[IYM04] Takayuki Ito, Makoto Yokoo, and Shigeo Matsubara, ̀̀A Combinatorial Auction
among Versatile Experts and Amateurs'',

Third International Joint Conference on

Autonomous Agents and Multi-Agent Systems (AAMAS2004), 2004
[SY04] Takayuki Suyama, Makoto Yokoo, ̀̀Strategy/False-name Proof Protocols for
Combinatorial Multi-Attribute

Procurement Auction'',Third International Joint

Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2004), 2004
[NMRY04] Ranjit Nair, Tambe Milind, Maayan Roth, and Makoto Yokoo, ̀̀Communication for
Improving Policy Computation in Distributed POMDPs'',

Third International Joint

Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2004), 2004
[SMY04] Kiam Tian Seow, Chuan Ma, and Makoto Yokoo, ̀̀Multiagent Planning as Control
Synthesis'', Third International Joint Conference on Autonomous Agents and Multi-Agent
Systems (AAMAS2004), 2004

4.2

分子計算の計算モデル（タイリング・セルオートマトン etc）

平成 14 年度報告
櫻井と貞広は有限オートマンによる２次元タイル張りの構造を解析した[SS02]. Wang タイル貼り
は２次元の有限型記号力学系と考えることが出来る. 高次元の有限型記号力学系のエントロ
ピーについて理論的, 実験的な研究を行った. DNA 計算でも、いくつかのタイルモデルが研究されている．DNA 計算の場合は、有限オートマトンよりも能力の高い計算機を考察している．
我々が行ってきた古典的なタイル張りおよび DNA 計算のおけるタイルモデルの研究の相関と違いを調査した．
溝口は, セルオートマトンと有限遷移系について以下の研究を行った.分散計算モデルとしても用いられるセルオートマトン(CA)は, 汎用性に富む計算モデルとして人工生命, ダイナミ
カルシステム, カオス理論など様々な分野で応用されている. J. Watrous は, 1995 年, 従来のセルオートマトンの定義を一般化し, 量子セルオートマトン(QCA)を提案した. しかし, この
QCA は遷移関数が well-formed かどうかの判断が難しく, 具体的な QCA の挙動については
ほとんど調べられていなかった. そこで, QCA と分割 QCA の定義を一般化し, 遷移関数がwell-formed であるための十分条件を与えると共に, 具体的な挙動をシミュレーションを駆使して検討した[IM02]. つぎに, 有限遷移系の挙動解析に関して, 有限遷移系の遷移図を代数式で表現する方法を定式化し, その代数式から直接有限遷移系の遷移図をグラフ表示する
アルゴリズムを Mathematica を用いて実現した[IMK02].
業績[SS02] 貞広泰造，櫻井幸一：自己相似タイル貼り構成の計算例, 数理解析研究所講究録

1286, 数学解析の計算機上での理論的展開とその遂行可能性 pp.119-130, 2002.
[IM02] S. Inokuchi, Y. Mizoguchi, Generalized Partitioned Quantum Cellular Automata andQuantumization of Classical CA (Draft), Eighth International Workshop on Cellular
Automata, Prague, Czech Republic, 2002.
[IMK02] 井口修一, 溝口佳寛, 河原康雄, 有限遷移系の木表現式からの遷移図の自動作
成, 応用数学合同研究集会報告集, pp.25-30, 2002 年 12 月.

平成 15 年度報告
櫻井は一方向性関数と分子現象の非可逆性に関する調査研究を行った．Adlemann は分子の非可逆現象をモデルに一方向性関数の理論を展開した.その後, 一方向性関数は暗号理論の発展に伴い大きく進歩するが,分子現象の非可逆性への演繹まではいたっていないようであることを認識した.つぎに，ソフトウエア工学の立場から，ソフトウエアの解析をより困難にする技術（難読化）を研究した[FTS03,FS03]. プログラムの著作権保護などで注目される技術であるが, このようなプログラムの複雑性を分子モデルで論じることが次年度の課題である.
溝口は量子セル・オートマトンとグラフ書き換えシステムについて考察した[IM03, MM03].
文献[IM03]は量子計算の分子計算による模倣という問題意識から検討が開始されたものであり，量子セル・オートマトンの(局所)遷移関数に要請される条件を調べている．文献[MM04]ではラベルと確率情報を持ったグラフが考察対象である．1 つのグラフ(式)はそのラベル情報で規定される複数のグラフの集合を表現する. 集合内のグラフ全体へのグラフ変換を一括して行う操作をその表現グラフ式への変換として定式化する. このグラフの集合への変換は, 分子
プログラミングのモデルを考える際の複数の遺伝子集合に対しての一括変換を表現するために有効である．
貞広はタイリングを考察している．Winfree たちは誤ったタイリングも多くの場合に自動的に訂正されるような機能を持ったタイルの設計とその訂正メカニズムを提案しているが，貞広の問題意識も同じ所にある（16 年度と続く内容のため，詳しくはそちらに記載する）.
業績[IM03] 井口修一, 溝口佳寛: ̀̀巡回型量子セルオートマトンの挙動について,''応用数学合同研究集会報告集, 85-88, 2003 年 12 月.
[MM03] M. Mori and Y. MIzoguchi: “Graph transformation approach for the shortest pathsearch and length calculation”, Bull. of Informatics and Cybernetics, Vol.35(2003), 57-67.
[FTS03] K. Fukushima, T. Tabata, and K. Sakurai: ̀̀Proposal and Evaluation of Obfuscation
Scheme for Java Source Codes by Partial Destruction of Encapsulation,'' International
Symposium on Information Science and Electrical Engineering 2003 (ISEE 2003), Nov. 2003.
[FS03] K. Fukushima, and K. Sakurai ̀̀A Software Fingerprinting Scheme for Java Using
Classfiles Obfuscation,ʼʼ Proc. of the 4th International Workshop on Information Security
Applications (WISA2003), 337-350, Aug. 2003.

平成 16 年度報告
櫻井は一方向性関数と分子現象の非可逆性に関する調査研究において，一方向性ハッシュ関数の分類と性質を調べた[LMSCLS04]．現在，一対一の一方向性と，ハッシュ関数のような多対一の一方向性との間の関係を，分子現象の非可逆性と関連してモデル化を検討中であり，今年度後半から次年度も研究を継続する予定である．
溝口は 15 年度に引き続き，はグラフ変換を使った計算モデルの構築に力を入れている. １
つのグラフを時間軸で次々とグラフ変換していくだけでなく, ある時間に存在する複数のグラ
フの分布状態を与え, グラフ変換をこの複数のグラフに一斉に行い分布状態を変化させるグ
ラフ変換システム(計算モデル)の形式的(formal)な定式化を試みている. また, そのシミュレー
ターの作成を行っている. その後, 各種計算シミュレーションによる変換により変化しない安定部分を探し, その事実への形式的な証明を与えることを考えている.
貞広は前年度に引き続き，分子計算の基礎理論として重要であると考えられている Wang タイルによるタイリングの基本的な性質について考察している．一般に複数の Wang タイルのプロ
トタイプと，敷きつめ可能な領域を与えたとき，敷きつめの方法は複数存在するため，敷きつ
める面積が大きくなると敷きつめの方法の数は指数関数的に増大する．しかし，領域サイズが十分大きくなるときにタイル貼りの様々な統計的性質が精密に計算出来るものがある．こういったタイル貼りに関する研究とそのシミュレーション（に関する研究）はマルコフ連鎖モンテカルロ
法における CFTP アルゴリズムやグラフの全域木をランダム生成する LERW アルゴリズムなどを生み出したが，今まで詳しい性質が分かったものは dimer モデルと呼ばれる種類のものだけである．より一般のタイル貼りへの拡張を念頭に一意に組上がらないタイルの巨視的な振舞について具体例の計算と計算機シミュレーション技術の研究を進めている．

LERW アルゴリズムによるランダムタイリング

業績[LMSCLS04] W. Lee, M. Nandi, P. Sarkar, D. Chang, S. Lee, and K. Sakurai,
Pseudorandomness of SPN-Type Transformations, Information Security and Privacy: 9thAustralasian Conference, ACISP 2004, LNCS, 3108, 2004.
[MM04] 溝口佳寛, 森雅生: ̀̀グラフの集合を表現するラベル付グラフについて''火の国情報シンポジウム 2004, 2004 年 3 月.
[MM04] S. Inokuchi and Y. Mizoguchi : Generalized partitioned quantum cellular automata
and quantization of classical CA, arXiv:quant-ph/0312102, (to appear in Int. J.
Unconventional Computing)[Sh04]貞廣泰造 ： ランダムタイリングの数値シミュレーション，数理解析研究所講究録 1381
pp.182-189, 2004.

4.3

分子計算における最適化問題

平成 14 年度報告
朝廣, 小野, 山下は組合せ最適化問題の発見的アルゴリズムの並列／分散化を検討した[IAY02, IOAY03]．この研究の動機は，分子計算は超並列の発見的アルゴリズムと見做すことができるのではないか，という仮説に基づくものであり，従来から検討が進んでいる発見的手法を分子計算アルゴリズムの設計に活かすことを視野に入れたものである．
藤田は分子の構造配置に関して, 以下の詰め込み問題を考察した[Fuji03]．ここで考えるのは, アイテムの(オンライン)系列を正方形のグリッド列に効率よく詰め込む問題であるが, 空
けておくことのできるグリッド数をひとつに限定しているという特徴がある. 分子計算との関係は明確ではないが, 具体的な構造をもつ分子を固定された空間にどのくらいたくさんオンライ
ン的に詰め込めるかといった, 一種の密度の見積もりに使えないかと考えている. また, 応用
面から今後に期待できる, 以下の結果を示した. 二次元平面上に配置された(無線通信のための)ベースステーション上にサーバから配送される位置依存情報をキャッシュしておくことを考える. キャッシュのリプレースメントアルゴリズムをシミュレーションで評価した[TWF02] 通常の LRU だけでなく, 空間的な連続性(対象が位置依存情報なので) や統計情報などもうまく併用すべきだということがこれまでにわかっている. 分子計算の内部でおこなわれる自律的な振る舞いを特定の解空間にマップしてから使うのではなく, 「そのままの形」でうまく観測して利用することを狙っている.
業績[IAY02] M. Ishibashi, Y. Asahiro, and M. Yamashita: ̀̀Parallelization of a Local Search
Method for the Generalized Assignment Problem,'' Proc. of the Second Japanese-Sino
Optimization Meeting (JSOM 2002)}, p.85 (2002).
[IOAY03] 石橋正裕，小野廣隆，朝廣雄一，山下雅史: ̀̀メタ戦略アルゴリズムに対するロバ

ストな並列化'' 冬の LA シンポジウム，1--8 (2003).
[Fuji03] S. Fujita: ̀̀On-Line Grid Packing with a Single Active Grid,'' Information
Processing Letters, 85, 4, 28, 199--204 (2003).
[TWF02] S. Tagashira, Y. Wang, and S. Fujita: ̀̀Location-Aware Buffering Schemes forRoad Vehicle Communication Systems,'' Proc. IASTED Int'l Conf. Networks, Parallel andDistributed Processing and Applications (NPDPA 2002)\/}, Tsukuba, 99-104 (2002).

平成 15 年度報告
先に，横森班との合同会議から共通の研究テーマとして DNA 設計問題が浮上したことを述べた．そのためには，分子の二次構造を特定し，その変化について理解することが必要になる．
分子の反応性質/速度に強い関わりを持つと考えられているのが, 反応におけるエネルギー障壁である. エネルギー障壁は，反応経路の中間物質(分子)の最大の自由エネルギー値（の最小値）として定義される. 一般に分子反応は原子数の指数サイズの中間物質を経て起こる
ため，単純な探索でこのエネルギー値を求めるのは不可能である． 朝廣，小野，山下はエネルギー障壁を求める問題を組合せ最適化問題として定式化し, 実用的な計算時間でこれを求めるアルゴリズムを検討中である．15 年度はこのために必要な道具となる, 組合せ最適化問題に対するメタ戦略アルゴリズムの設計・並列化に関する研究を中心に行った[IOAY03,
IAY03]. 山下，定兼は，分子計算における計算速度の見積もりのために，分子の二次構造の変化をマルコフ過程とみなし，分子が安定状態に至るまでの時間の解析を目指した[JSSSY03].
また定兼は DNA 配列の高速検索のためのデータ構造とその構築アルゴリズムについて研究した [Sk03,HSS03,HLSS03]. 従来法ではデータ構造構築のために大量の一時的な記憶領域が必要であったが，新しいアルゴリズムによりこれを削減することができた．
Papadimitriou らは，与えられた問題例のランドスケープを進化の概念に基づいてより滑らかなものに変化させ，問題例をより高速に解くことを提案している．一方，先に説明したように
DNA 設計問題がある与えられた塩基列の二次構造間の遷移可能性が組合せ最適化問題として定式化され検討されている．藤田は，後者を前者の方針で解決することを目指して，
Papadimitriou らのメタ解法を TSP を対象として追試を行うとともに，問題例の進化に関する新
しい方法の提案とその実験的評価を行った[MF03,FN03].
業績[IOAY03] 石橋正裕，小野廣隆，朝廣雄一，山下雅史: ̀̀メタ戦略アルゴリズムに対するロバ
ストな並列化''， 数理解析研究所講究録 1325, pp.1-7, 2003 年 6 月.
[IAY03] M. Ishibashi, Y. Asahiro, and M. Yamashita: ̀̀Independent and Cooperative Parallel
Search Methods for the Generalized Assignment Problem,'' Optimization Methods andSoftware, 18,2,129-141, 2003.
[JSSSY03] J. Jansson, 定兼邦彦, W.K. Sung, 塩崎真史, 山下雅史: ̀̀局所情報を用いたランダムウォークの拡張,'' ＩPSJ SIG Notes, SIGAL-92-3}, 2003.
[Sk03] K. Sadakane: ̀̀New Text Indexing Functionalities of the Compressed Suffix
Arrays,'' Journal of Algorithms, 48, 2, 292--313, 2003.
[HSS03 ] W.K. Hon, K. Sadakane and W.K. Sung: ̀̀Breaking a Time-and-Space Barrier inConstructing Full-Text Indices,'' Proc. IEEE FOCS, 251--260, 2003.
[HLSS03] W.K. Hon, T.W. Lam, K. Sadakane and W.K. Sung: ̀̀Constructing Compressed
Suffix Arrays with Large Alphabets,'' Proc. ISAAC, LNCS 2906, 240--249, 2003.
[MF03] M. Mito and S. Fujita: ̀̀On Heuristics for Solving Winner Determination Problem in
Combinatorial Auctions,'' 2003 IEEE/WIC International Conference on Intelligent Agent
Technology (IAT 2003), October 13-17, Halifax, Canada, 25-31 2003.
[FN03] S. Fujita and A. Nakatani: ̀̀A Vehicle Scheduler for On-Demand Bus Systems Basedon a Heuristic Cost Estimation,'' IEEE 2003 International Conference on Intelligent
Transportation Systems (ITS 2003), October 12-15, Shanghai, 1194-1199 2003.

平成 16 年度報告
先年度から取り組んでいる DNA 配列設計において現れる諸問題について取り組んでいる．
小野，山下はエネルギー障壁を求める問題を組合せ最適化問題として定式化し, これを求める近似アルゴリズムを実装，計算実験を行っている[TOSY04]．本領域の萩谷班では，同様の問題を解く厳密アルゴリズムを提案しているが，問題例によっては計算時間が爆発する可能性が指摘されている．ここでの提案アルゴリズムは，実用的な時間でこれを近似的に求めるものであり，萩谷班アルゴリズムとの比較実験を行っている．16 年度後半はこのアルゴリズムの理論的解析・評価を行う予定である．
山下，定兼は昨年度から引き続き，分子の二次構造の変化をマルコフ過程とみなし，分子が安定状態に至るまでの時間を解析する．各二次構造をグラフの節点，二次構造の変化をグ
ラフの枝で表すと，分子の二次構造変化はグラフ上のランダムウォークとして表すことができる．
本研究ではこのランダムウォークの理論的および計算機シミュレーションによる解析を行う．16
年度はハイブリダイゼーション速度の見積もりを行っている．計算機シミュレーションによる結果と，本研究領域の陶山教授らの実験結果を比較し，計算モデルの正確さを調査している．
朝廣は高密度な配列（集合）設計について考察を行っている．分子計算では，ある長さのDNA 配列集合の構成が必要となる局面があるが，符号化の尺度からはなるべく多くの要素（配列）を持つ集合を構成することが望まれる．と同時に，「計算」の誤りを防ぐためには集合内の各配列が複数の尺度で「遠い」構造となっていることが望ましい．朝廣はこのような観点から，
貪欲法に基づく組織的な DNA 配列の構成法（符号化法）の提案・評価を行っている．
藤田は DNA 配列の設計問題を，DNA 配列のとりうる二次構造に対して与えられたインスタンスの局所安定状態をどのように割り当てるか，という問題と見なし諸問題について考察を行っている．まず，DNA 配列の安定性に関する新しい尺度としてグラフの極大マッチング数に着目し、より自由エネルギーの低いマッチングを高速に列挙するための発見的な手法について考察を行っている．また，配列設計を発見的に行うための枠組みとして Papadimitriou らによって提案されたメタ解法に着目し、DNA 計算の分野で取り上げられることの多い巡回セール
スマン問題（TSP）を対象とした追試を行うとともに，最適な DNA 配列の進化的計算法に関する新しい手法の提案とその実験的評価を行った[MF04, TSF04]．さらに進化的計算（EC)の分
野で幅広く研究されている DSM(DependencyStructure Matrix)を併用した最適なビルディング
ブロック特定手法に着目し，DNA 配列中の適切なブロックを部分インスタンスに対応させるための手法について考察を行っている．
この他に，定兼は分散環境における DNA 配列の高速検索のためのデータ構造についても研究している[MNS04,Sk04,HLSSY04]．
業績[TOSY04] 武田勉, 小野廣隆, 定兼邦彦, 山下雅史, DNA 計算における局所探索法

による反応障壁近似計算, 電気関係学会九州支部連合大会, 2004.
[MF04] M. Mito, S. Fujita, ̀̀On Heuristics for Solving Winner Determination Problem in
Combinatorial Auctions,'' in press.
[TSF04] S. Tagashira, S. Shirakawa, S. Fujita, ̀̀Proxy-Based Index

Caching forContent-Addressable Networks,'' Proc. International Conference on

Parallel andDistributed Processing Techniques and Applications (PDPTA2004), June 21--24, Las Vegas,
pp. 1154--1160 (2004).
[FU04] S. Fujita, S. Umezane, ̀̀An Improved Heuristic for Solving TSP Based on the
Evolution of Easy Instances,'' Proc. International Conference on Parallel and Distributed
Processing Techniques and Applications (PDPTA 2004),June 21--24, Las Vegas, pp.
324--330 (2004).
[MNS04] V. Makinen, G. Navarro and K. Sadakane. Advantages of Backward Searching --Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays.
In Proc. of ISAAC, LNCS, 2004. To appear.
[Sk04] K. Sadakane. Compressed Suffix Trees with Full Functionality. Theory of Computing
Systems, 2004. In press.
[HLSSY04]W. K. Hon, T. W. Lam, K. Sadakane, W. K. Sung, and S. M. Yiu. Compressed
Index for Dynamic Text. In Proc. of IEEE Data Compression Conference (DCC 2004),
pages 102--111, 2004.

5. 今後の課題
各研究項目とも前節の 16 年度で個々の今後の課題を合わせて述べているが，研究班全体としての観点から，今後の課題について簡単に補足を述べる．
活動状況の節でも述べたように，タイリング，グラフ書き換えシステムあるいはセル・オートマ

トンに関する側面からの研究が本研究班の今後の活動の中核になると考えている．ここにもう一つ大きな軸となるキーワードとして存在するのが「ランダム性」である．実際，現時点までの研究の中にも，「ランダム（ウォーク）」というキーワードが，「ランダムウォークに基づく分散アルゴリ
ズム（山下）」「マルコフ連鎖（ランダムウォーク）アルゴリズムによるタイリング（貞広）」「マルコフ連鎖による分子反応速度見積もり（山下・定兼）」などと現れているが，これらは上の成果報告
ではそれぞれ別の項目にある内容であり，元来動機も異なる．分子計算のランダム性を考えると，これは当然といえば当然かもしれないが，やはり本質の一つであり，研究を進める上での重要な軸であると考えられる．

6. 研究費の使用状況
本研究班では，14 年度・15 年度ともに計算機シミュレーション用のワークステーション(高性能PC)，PC クラスタなどの購入，また地理的な制約から生じる旅費としてその多くを利用している．
具体的には，計算機実験，シミュレーションは，まず上記研究項目の「組合せ最適化問題に対する近似アルゴリズム」の実験的評価，またさらに PC クラスタ上での並列アルゴリズムによる計算実験（シミュレーション）に利用している（山下，朝廣，定兼，小野（九大），藤田（広大）が利用）．また「タイリング」の項のタイリングシミュレーションの出力確認も本研究費により購入したレーザープリンタ（熊本県立大）により行っている．