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

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 年度以降も 15 年度までの流れを引き継ぎ，横森班（18 年度は上田班）との定期的な会議を設けながら本領域理論班としての方向性を確認しながら研究を進めており，その研究成果は DNA コンピューティングに関する国際ワークショップなどで発表されている．（後述）
また平成 18 年度には，山下班・上田班を中心とした「計算機科学における連続と離散」に関する会合を計 3 回行い，本研究の更なる方向性について議論を行った．

平成 16 年度までに行われた研究会・会合は以下のとおりである．

平成 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)
理論班合同研究会 in 九州 (H15.12.22-24)
第 3 回班研究会（タイリングセミナー） (H16.1.28)
第 2 回理論班合同会議, 早稲田大学 (H16.1.31)
平成 16 年度
第 1 回理論班合同会議, 早稲田大学 (H16.5.22)
第 2 回理論班合同会議, 九州大学 (H16.7.11)
第 3 回理論班合同会議， 早稲田大学（H16.10.30）
理論班合同研究会 in 九州 (H16.12.10-12)
第 4 回理論班合同会議，早稲田大学（Ｈ17.3.12）
平成 1７年度
第 1 回理論班合同会議， 早稲田大学（H17.10.1）
理論班合同研究会 in 九州 (H17.12.17-19)
平成 1８年度
第１回理論班合同会議, 沖縄 (H18. 6.17)
第２回理論班合同会議, 早稲田大学（H18．7.15）
第３回理論班合同会議, 九州大学 (H18.12.22-23)
関連会合「計算機科学における連続と離散」
第 1 回会議，名古屋大学（H.18.5.27）
第 2 回会議，早稲田大学（H18.7.15）
第 3 回会議，早稲田大学（H18.9.2）
第 4 回会議，東京大学（H19.3.24）

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 ， 23, 6,
583-593 (2004).

[DSY03b] A. Dumitrescu, I. Suzuki, and M. Yamashita: ̀̀Motion Planning for Metamorphic
Systems: Feasibility, Decidability and Distributed Reconfiguration,'' IEEE Trans. Robotics

and Automation. 20, 3, 409-418 (2004)[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
[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

平成 17 年度報告
山下は前年度に引き続き，分散システムの耐故障性の観点から研究を進めた [HY05].
横尾は前年度に引き続き，分散制約充足／プランニングおよびメカニズムデザインに関する研究を進めた．
業績[HY05]T. Harada and M. Yamashita: ̀̀Transversal Merge Operation: A NondominatedCoterie Construction Method for Distributed Mutual Exclusion,'' IEEE Transactions on
Parallel and Distributed Systems, 16, 2, 183-192 (2005).
[MSTY05] Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo, An
Asynchronous Complete Method for Distributed Constraint Optimization, Artificial

Intelligence Journal, vol.161, No. 1-2, pp. 149--180, 2005.
[YSH05] Makoto Yokoo, Koutarou Suzuki, and Katsutoshi Hirayama, ̀̀Secure Distributed
Constraint Satisfaction: Reaching Agreement without Revealing Private Information'',

Artificial Intelligence Journal, vol.161, No. 1-2, pp.~229--246, 2005.
[NVTY05] Ranjit Nair, Pradeep Varakantham, Milind Tambe, and Makoto Yokoo, ̀̀Networked
Distributed POMDPs: A Synthesis of Distributed Constraint Optimization and POMDPs'',

Twentieth National Conference on Artificial Intelligence (AAAI-05), pp. 133--149, 2005.

平成 18 年度報告
山下は自律分散計算の観点から研究をすすめた[TMS06, KY06].
横尾は前年度に引き続き，分子プログラミングの適用が期待される応用問題である，分
散 制 約 充足／ プ ラ ンニン グ お よびメ カ ニ ズムデ ザ イ ンに関 す る 研究を 進 め た [SY06,
VNTY06,BTY06]
藤田は分子プログラミングの分散システムとしての応用の視点から， P2P ネットワーク
やセンサーネットワークットワークなどの分散ネットワークにおける情報伝搬機構について研究を行った．各動作主体が自律的に振舞う分散ネットワークにおける耐故障性の問題と、複製による冗長性を付与することによって耐故障性を与えられたネットワーク上の情報伝搬が、与えられた冗長性の度合いによってどのように変化するのかについて、詳細な

検討を行った[OTF06, TTF06, TMF06].

業績[TMS06] T. Kameda, M. Yamashita, and I. Suzuki: ̀̀On-Line Polygon Search by aSeven-State Boundary 1-Searcher,'' IEEE Transactions on Robotics, 22, 3, 446-460(2006).
}KY06] J. Kiniwa and M. Yamashita: ̀̀A Randomized 1-Latent, Time-Adaptive and Safe
Self-Stabilizing Mutual Exclusion Protocol,'' Parallel Processing Letters, 16, 1, 53-61(2006).
[SY06] Marius C. Silaghi, Makoto Yokoo,̀̀Nogood-based Asynchronous Distributed
Optimization (ADOPT-ng)'',Proceedings of the Fifth International Joint Conference on
Autonomous Agents and Multiagent Systems (AAMAS-2006), pp.1389--1396, 2006.
[VNTY06] Pradeep Varakantham, Ranjit Nair, Milind Tambe, and Makoto Yokoo, "Winningback the cup for distributed POMDPs: Planning over continuous

belief spaces",

Proceedings of the Fifth International Joint Conference on Autonomous Agents andMultiagent Systems (AAMAS-2006), pp. 289--296, 2006.
[BTY06] Emma Bowring, Milind Tambe, and Makoto Yokoo, ̀̀Multiply constrained
distributed constraint optimization'',ConferenceonAutonomous

Proceedings of the Fifth International Joint

AgentsandMultiagent

Systems(AAMAS-2006),

pp.~1413--1420, 2006.
[OTF06] H. Ochi, S. Tagashira, S. Fujita: A Localization Scheme for Sensor Networks Basedon Wireless Communication with Anchor Groups, IEICE Trans. Inf. & Syst.,
E89-D(5):1614--1621 (2006).
[TTF06] D. Takemoto, S. Tagashira, S. Fujita: A Fault-Tolerant Content Addressable
Network, IEICE Trans. Inf. & Syst., E89-D(6):1923--1930 (2006).
[TMF06]for

S. Tagashira, M. Mito,S. Fujita: A Generic Solver based on Functional Parallelism

Solving

Combinatorial

Optimization

Problems,

IEICE

Trans.

Inf.

&

Syst.,

E89-D(6):1940--1947 (2006).

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, pp. 212−223, 2004.
[MM04] 溝口佳寛, 森雅生: ̀̀グラフの集合を表現するラベル付グラフについて''火の国情報シンポジウム 2004, 2004 年 3 月.
[MM04] S. Inokuchi and Y. Mizoguchi : Generalized partitioned quantum cellular automata
and quantization of classical CA, International Journal of Unconventional Computing,
Vol.1(2005), 149-160.

[Sh04]貞廣泰造 ： ランダムタイリングの数値シミュレーション，数理解析研究所講究録 1381
pp.182-189, 2004.

平成 17 年度報告
貞廣は引き続きタイリングの観点から研究を進めており, 昨年度から今年度にかけて Pisot
numeration system とそれが生成するタイル貼りの研究を行った. 特にタイル貼り多重点をモ
デルセットとして具体的に表示する計算アルゴリズムを与えた．また Numeration System を利用したトーラス型ネットワーク上のブロードキャストアルゴリズムの研究を行い。従来から知られていた 2 次元のアルゴリズムを 3 次元に拡張した.
溝口はラベル付格子グラフの変換を利用した自己組織化の計算モデルを提案した. 辺のラベルに確率情報を保存し, ひとつのグラフで分布グラフ集合を表現する方法, ならびに, その変換を定式化する. 変換規則の辺の数を制限し, 変換がある規則を満たせば, グラフ変換
時の分布確率の計算を単純に行えることを示した. また,その変換のシミュレータを Haskell 言語で実装し, セルオートマトンや正方タイル貼りの例で, 変換が上記の制限規則を満たすことも示した.
業績[OOSY05]

R. Okazaki, H. Ono, T. Sadahiro, M. Yamashita, Circuit Switched Broadcastingsand Digit Tilings on Torus Networks, Proceedings of 4th Japanese-Hungarian Sympothium
on Discrete Mathematics and Its Applications, pp. 288̶295.
[MK05] 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.

平成 18 年度報告
貞廣は前年度から継続して，分子プログラミングの基礎としての Wang タイル貼り, 自己相似
タイル貼りの研究を行った．前者については特に統計力学のダイマー模型との関連から研究を行った. ダイマー模型を loop erased random walk を用いて高速にシミュレートするアルゴリ
ズムを実装し計算機実験を行った．後者については配列設計などと関係の深い Constrained
coding との関連から研究を進めた[Sh06]
溝口も前年度から引き続き，セルオートマトン的視点から分子同士の反応による計算を局所計算から導かれる大域計算と捉え, 局所計算と大域計算の定義と関係式, 導かれる大域計算を代数的, かつ,形式的に評価する手法について研究を進めている.今年度は特に有限状態の遷移系のなかで, 連続系の微分方程式の超離散化により得られる系(周期型箱玉系)について, 厳密な定式化とその挙動, とくに周期性について解析を行った. 周期性などに注目すると，これらの結果は乱数発生などに利用できる可能性を持つことを示唆している[MIMF06] .
業績[Sh06] Taizo Sadahiro Multiple points of tilings associated with Pisot numeration systems
Theoretical Computer Science 359 133-147 (2006)[MIMF06] A. Mikoda, S. Inokuchi, Y. Mizoguchi, M. Fujio, The number of orbits of periodic
box-ball systems. Lecture Notes in Computer Science, Vol.4135(2006), pp.181-194.

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, pp. 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 年度はハイブリダイ
ゼーション速度の見積もりを行っている．計算機シミュレーションによる結果と，本研究領域の陶山教授らの実験結果を比較し，計算モデルの正確さを調査している．[SOSY05a] なおこれらの研究は，「分子計算の計算モデル」とも大いに関連している．
朝廣は密度な配列（集合）設計について考察を行っている．藤田は DNA 配列の設計問題
を，DNA 配列のとりうる二次構造に対して与えられたインスタンスの局所安定状態をどのように割り当てるか，という問題と見なし諸問題について考察を行っている．まず，DNA 配列の安定性に関する新しい尺度としてグラフの極大マッチング数に着目し、より自由エネルギーの低いマッチングを高速に列挙するための発見的な手法について考察を行っている．また，配列設計を発見的に行うための枠組みとして Papadimitriou らによって提案されたメタ解法に着目し、DNA 計算の分野で取り上げられることの多い巡回セールスマン問題（TSP）を対象とした追試を行うとともに，最適な DNA 配列の進化的計算法に関する新しい手法の提案とその実験的評価を行った[MF04, TSF04]．さらに進化的計算（EC)の分野で幅広く研究されている DSM(Dependency Structure Matrix) を併用した最適なビルディングブロック特定手法に着目し，DNA 配列中の適切なブロックを部分インスタンスに対応させるための手法について考察を行っている．
この他に，定兼は分散環境における DNA 配列の高速検索のためのデータ構造についても研究している[MNS04,Sk04,HLSSY04]．
業績[TOSY04] 武田勉, 小野廣隆, 定兼邦彦, 山下雅史, DNA 計算における局所探索法による反応障壁近似計算, 信学技報, vol. 104, no. 339, COMP2004-49, pp. 41-46, 2004 年 10 月.
[SOSY05a] 塩崎真史，小野廣隆，定兼邦彦，山下雅史, 分子構造変化のモデル化と反応度の理論的解析, 2005 年冬の LA シンポジウム, 数理解析研究所講究録 1426，pp.232-237．

[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. .
[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.

平成 17 年度報告
基本的に各人とも前年度までの流れに沿って研究を行っている．まず小野，山下は前年度から取り組んで来たエネルギー障壁発見問題に対する近似アルゴリズムの改良を行った．これにより， 上述の厳密アルゴリズムでは事実上発見不可能なエネルギー障壁値の高精度な近似値を，高速に発見することが出来ることが確認された[TOSY05]．
山下，定兼は昨年度に引き続き分子の二次構造の変化をマルコフ過程とみなし，分子が安定状態に至るまでの時間を解析した．昨年度から考察を行っているモデル上での計算機シミュレーション結果と，本領域陶山教授らによる生物実験の結果の一例を以下に挙げる．実験
結果の多くの類似点は本提案モデルの妥当性を示唆するものと考えている．[SOSY05b]
朝廣は高密度な配列（集合）設計について考察を行っている．分子計算では，ある長さのDNA 配列集合の構成が必要となる局面があるが，符号化の尺度からはなるべく多くの要素（配列）を持つ集合を構成することが望まれる．と同時に，「計算」の誤りを防ぐためには集合内の各配列が複数の尺度で「遠い」構造となっていることが望ましい．朝廣はこのような観点から，
貪欲法に基づく組織的な DNA 配列の構成法（符号化法）の提案・評価を行っている．なお，
配列設計に関しては小野，定兼，山下も取り組んでおり，隠れマルコフモデルを利用した配列
設計手法について考察を行った[MOSY06]．
藤田は引き続き進化的計算に DNA 計算を利用するための具体的な手法について研究をおこなっている．今年度は、問題を DNA 上にマッピングする際の問題のひとつであるリンケー
ジ同定問題に焦点をあて、組合せ最適化問題におけるオブジェクト間の関係の強さに注目した新しいリンケージ同定手法の提案と評価をおこなっている．

陶山班による生物実験の結果（左）と山下・定兼によるシミュレーション結果（右）業績[TOSY05] T.Takeda, H.Ono, K.Sadakane and M.Yamashita, A Local Search Based
Barrier Height Estimation Algorithm for DNA Molecular Transitions, Revised
Selected Papers of the 11th International Meeting on DNA Computing, DNA11,
Lecture Notes in Computer Science, 3892, pp. 359-370, 2006.
[SOSY05b] M. Shiozaki, H. Ono, K. Sadakane and M. Yamashita, Modeling DNA
Conformation Change and Theoretical Analysis on the Reaction Rate, Preproceedingsof the 11th International Meeting on DNA Computing, DNA11, p. 408, 2005.

[Asa05] Y. Asahiro, Simple Greedy Methods for DNA Word Design, Proc. 9th World
Multi-Conference on Systemics, Cybernetics and Informatics, vol. III, pp. 186 ‒ 191, 2005.
[MOSY05]前村一哉，小野廣隆，定兼邦彦，山下雅史，隠れマルコフモデルを用いた DNA
配列設計，火の国情報シンポジウム 2006，2006 年 3 月．

[UF05] S. Umezane, S. Fujita, On Linkage Identification in EC for Solving Combinatorial
Optimization Problems, Proc. IEEE SMC (October 2005)．

平成 18 年度報告
定兼・山下は，分子の二次構造の変化をマルコフ過程とみなすことにより分子が安定状態に至るまでの時間を解析した．これは前年度まで取り組んできたテーマをより進めたものである．
今年度の研究進展により，ブランチマイグレーションなどの複数の分子配列が反応することによる複雑な反応過程のシミュレーションが可能となった[SOSY06]
小野・山下は前年度まで取り組んできたエネルギー障壁値の近似アルゴリズムのアイデアを
DNA 配列設計への適用に取り組んだ．ここでの配列設計は「望ましい性質を持つできるだけ大きな配列集合」を設計する問題であり，配列間のハミング距離に基づくもの（前年度の朝廣の配列設計もこれを尺度としている），熱力学的制約に基づくものなどがある．本研究で提案した局所探索に基づくアルゴリズムは，ハミング距離に基づくもの，熱力学的制約に基づくもの
両者に対応できるものでありながら，それぞれ既存手法よりも良い評価尺度を満たす配列集

合の設計に成功している[KOSY06]
朝廣は分子計算の分散並列処理的側面に注目し，この処理の高速化の可能性を最適化
問題の形で評価しようと試みている．すなわち分散処理のプロセス同士（頂点）にある因果関係（枝）が構成する非巡回なグラフに対して，頂点を縮約することにより最長路をできるだけ短くすることを試みる最適化問題を考え，それにより分子計算の高速化に対する指標を与えることを試みている[AFIM06a,AFIM06b]．
業績[SOSY06] Masashi Shiozaki, Hirotaka Ono, Kunihiko Sadakane and Masafumi Yamashita, A
Probabilistic Model of DNA Conformational Change, Revised Selected Papers of the 12th
International Meeting on DNA Computing, DNA12, Lecture Notes in Computer Science,
4287, pp. 274--285.
[KOSY06] Suguru Kawashimo, Hirotaka Ono, Kunihiko Sadakane and Masafumi
Yamashita, DNA Sequence Design by Dynamic Neighborhood Searches, Revised
Selected Papers of the 12th International Meeting on DNA Computing, DNA12,
Lecture Notes in Computer Science, 4287, pp. 157--171.

[KOSY07] 川下優，小野廣隆，定兼邦彦，山下雅史，局所探索法に基づく DNA 配列設計手法，2007 年冬の LA シンポジウム，2007 年 1 月．
[AFIM06a] Y. Asahiro, T. Furukawa, K. Ikegami, and E. Miyano: How to pack directed acyclic
graphs into small blocks Proc. 6th International Conference on Algorithms and Complexity(CIAC2006), Lecture Notes in Computer Science, Vol.3998, pp.272-283, May. 2006.
[AFIM06b] 朝廣雄一，古川哲也，池上佳一，宮野英次: サイズ 3 の最小ブロック転送問題の近似困難性 電気関係学会九州支部連合大会，(CDROM), 2006 年 9 月

5. 今後の課題
本報告の冒頭で述べたように，本研究班の「分子プログラミング」に対するアプローチは，既存の計算機科学分野のモデルとの対比を通して分子計算を捉えなおすと共に，新たな計算モデルを開拓するというものであった．前節で概観したように，その試みは当初の目標と照らし合わせると十分な成果を上げたと言える．しかしここ数年，分子プログラミング発足時には予期していなかった，構成的生物学，構成的材料科学など，生化学分野や材料化学分野に「プログラミング」もしくは「アルゴリズム」の概念を導入した， 新たな研究分野が生まれつつある．このことから，これらの新しい分野までも網羅する計算機科学理論の構築が重要な研究課題として残されている．

6. 研究費の使用状況

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