「高速ロバストランダムウォークの設計に基づく物質デザイン」 	

小野廣隆	
（九州大学大学院・経済学研究院）	

研究組織	
o 研究代表：n 小野廣隆（九大経済学研究院）（経済工学部門・数理情報講座）

o 連携研究者：n 山下雅史（九大システム情報）n 松本広重（九大稲盛先端フロンティア）n Colin Cooper (King’s College London)o 研究協力者n 穂坂祐輔（九大システム情報・D2）

2011/10/8「コンピューティクスによる物質デザイン」研究会

2テーマ： 局所構造と大域構造の関係	
o 組合せ最適化n 近似アルゴリズム（局所探索）n 計算複雑度o 分散計算n 局所計算と大域計算

o 乱択計算n ランダムウォーク
o 局所情報と大域情報

o （ちなみに、経済学では）n 数理計画n （局所最適性と大域最適性の関係）	
2011/10/8「コンピューティクスによる物質デザイン」研
究会

3提案研究	o 「高速ロバストランダムウォークの設計に基づく物質デザイン」	o キーワードn ランダムウォーク（マルコフ連鎖）設計＝「局所プロトコル設計」
n 物質デザイン＝「大域構造設計」

o やりたいことn 「物質デザイン」を「マルコフ連鎖設計」の観点から
2011/10/8「コンピューティクスによる物質デザイン」研究会

4

以下の話	o ランダムウォーク（マルコフ連鎖）モデルとその応用
o DNA計算における反応設計
o 「ランダムウォーク」に関する研究進捗

2011/10/8「コンピューティクスによる物質デザイン」研究会

5グラフ上のランダムウォーク	o 適当な確率に従って「グラフ」上の「頂点」におかれた「トークン」が移動するモデル	

-

2011/10/8「コンピューティクスによる物質デザイン」研究会

6グラフ上のランダムウォーク	o 適当な確率に従って「グラフ」上の「頂点」におかれた「トークン」が移動するモデル	

-

2011/10/8「コンピューティクスによる物質デザイン」研究会

7グラフ上のランダムウォーク	
o グラフ： 頂点とそれらを結ぶ辺からなる離散構造
o グラフの頂点上に置かれた粒子が確率的に遷移するモデル

0.5	 
0	 ２
1	 

１
0.5	 

0.5	 0.3	 ３ 0.1	 0.6	 

G

2011/10/8

0.5	  ４11 ⎛ 0234 	 0 ⎞⎜⎟
2 ⎜ 0010 ⎟
P = ⎜
0 0.1 ⎟
3 0.3 0.6⎜⎟⎜
4 ⎝ 00 0.5 0.5 ⎟⎠

「コンピューティクスによる物質デザイン」研究会

0. 5 0. 58

確率現象とグラフ上のランダムウォーク	o 様々な「確率的」な現象がグラフ上のランダムウォークとしてモデル化される
いくつかの例o クーポン収集問題
o 破産の問題o Webクローラー
o 化学変化反応
o 確率アルゴリズム
o ・・・

2011/10/8「コンピューティクスによる物質デザイン」研究会

9生分子・ナノ分野におけるランダムウォーク	
o 分子反応の形態変化はランダムウォーク的	

自己組織化タイルを利用した
ナノ材料加工	 

DNAコンピューティング：
DNA分子の２次構造変化	 
2011/10/8

DNA分子の二次構造変化を利用した計算原理「コンピューティクスによる物質デザイン」研究会

10

DNAの構造変化のマルコフモデル	
o RNAの構造変化はマルコフ過程（ランダムウォーク）でモデル化可能	n 一本の配列間でのみ塩基対を形成[Tacker et al.1993] [Flamm et al. 1999]

o 状態遷移確率は直前の状態のみに依存する（＝マルコフ的＝「ランダムウォーク」）
Pr( X t +1 = xt +1 | X 1 = x1 , X 2 = x2 ,…, X t = xt )= Pr( X t +1 = xt +1 | X t = xt )l RNAの構造変化	 
l 確率的な動作	 

状態	 ：	 RNAの構造	 AUGCAUGUACGUACAUGCAUGUACGUAC

過去の状態に非依存
本質的にはDNA構造変化にも適用可能	l

2011/10/8

AUGCAUGUACGUAC「コンピューティクスによる物質デザイン」研究会

AUGCAUGUACGUAC

11

DNAの構造変化のマルコフモデル	
o 近傍：現在の構造から塩基対を一つ変化させることで形成される構造の集合	
l

状態遷移確率	 
rxy : xからyへの遷移割合	 l N(x) : xの近傍	 
l E(x) : xの自由エネルギー	 l∑r,xzz∈N ( x )大	 自由エネルギ

P( X t +1 = y | X t = x) =rxyyー	 

E(y) - E x(x)小分子の構造	 2011/10/8y’⎧ ⎛ E ( y ) − E ( x) ⎞⎟ ( E ( y ) > E ( x))⎪exp⎜ −rxy = ⎨ ⎝
RT⎠⎪
1( E ( y ) < E ( x))⎩[Wolfinger et al. 2004]「コンピューティクスによる物質デザイン」研究会

12実生化学実験との比較	
o DNA分子反応のランダムウォークによるモデル化[Shiozaki, et.al 2006]	
n 遷移確率	p

P ( X t +1 = y | X t = x ) =⎧⎪ ⋅ rxy
Rxy = ⎨⎪⎩rxyRxy∑Rxzz∈ N ( x ),最初に複数塩基が結合する場合		

それ以外⎧ ⎛ E ( y ) − E ( x) ⎞⎟ ( E ( y ) > E ( x))⎪exp⎜ −rxy = ⎨ ⎝RT⎠⎪1( E ( y ) < E ( x))
⎩

類似！	 

生化学実験結果	 
2011/10/8

提案モデルのシミュレーション結果	 

「コンピューティクスによる物質デザイン」研究会

13

DNAタイルによる物質デザイン	
o DNAによるシェルピンスキー三角形（Rothemund, Papadakis,Winfree 2004)
イメージを表示できません。メモリ不足のためにイメージを開くことができないか、イメージが破損している可能性があります。コンピューターを再起動して再度ファイルを開いてくだイメージを表示できません。メモリ不足のためにイメージを開くことができないか、イメージが破損している可能性があります。コンピューターを再起動

さい。それでも赤い x が表示される場合は、イメージを削除して挿入してください。

して再度ファイルを開いてください。それでも赤い x が表示される場合は、イメージを削除して挿入してください。

n 左： シェルピンスキー三角形
n 右： 300のDNAタイルから構成されたシェルピン
スキー三角形イメージを表示できません。メモリ不足のためにイメージを開くことができないか、イメージが破損している可能性があります。コンピューターを再起動して再度ファイルを開いてください。それでも赤い x が表示される場合は、イメージを削除して挿入してくだ
さい。

出典：

http://eands.caltech.edu/articles/LXVII4/crystalpower.html	
2011/10/8「コンピューティクスによる物質デザイン」研究会

14ここまでのまとめ	
o ランダムウォーク（マルコフ連鎖）モデル
o DNA生体反応に対するランダムウォークモデル
o DNAタイリングを用いた「物質デザイン」2011/10/8「コンピューティクスによる物質デザイン」研究会

15

ランダムウォークに基づく物質デザイン	
o DNAを用いた材料デザインと本領域の「物質デザイン」の違い
n DNA：o 状態空間の離散化に適している（文字列集合空間）
o サイズが比較的大きい（？）
o 物質デザインというよりは形状デザイン？

n 本領域：o 状態空間は必ずしも離散化に適しない
o サイズが小さい

o 共通する点o {生体分子、化学}反応は無記憶的（マルコフ性）
2011/10/8「コンピューティクスによる物質デザイン」研究会

16ランダムウォークに基づく物質デザイン	
想定している当面のテーマ
o 連続事象をいかに上手に離散化するかn （逆方向： 解析のための連続緩和・埋め込み）

o 離散化したモデル上での最適化問題
n e.g., DNAタイリングモデルで、所定の模様を実現するための、最小のタイル集合は？
n Mixing Time (ランダムウォークが定常分布に到達するまでの時間)は行列の第２固有値によりもとまる
2011/10/8「コンピューティクスによる物質デザイン」研究会

17

研究進捗	o ランダムウォークの速度の評価n （物質デザインへの応用可能性）

o 多種ランダムウォークの速度の評価

2011/10/8「コンピューティクスによる物質デザイン」研究会

18到達時間と訪問時間	
グラフG=(V,E) とその上の遷移確率P に対してo 到達時間 (Hitting time)n s-t の到達時間： H GP ( s, t )G上の遷移確率P のランダムウォークにおいて，s におかれたトークンが t に到達するまでの平均ステップ数n 到達時間：

H GP = max H GP ( s, t )s ,t∈Vo 全訪問時間 (Cover time)n s の Uに対する訪問時間 : CGP ( s, U )同じく，s におかれたトークンが Uの全ての頂点を訪問するまでの平均ステップ数n 全訪問時間： 	
CGP = max CGP ( s,V )2011/10/8s∈V「コンピューティクスによる物質デザイン」研究会

19

Mathew の定理とその一般化	
o Mathew の定理[Mathew 1988]n G=(V,E) 上の遷移確率 P のランダムウォークにおいて，以下が成立

h(n − 1) min H GP (u , v) ≤ CGP ≤ h(n − 1) max H GP (u , v)u ,v∈Vu ,v∈Vo Mathew の定理（一般化） [Ikeda, et.al. 2009]n G=(V,E) 上の遷移確率 P のランダムウォークにおいて，頂点の部分集合U ⊆ V に対して以下が成立

h(| U | −1) min H GP (u , v) ≤ CGP (U ) ≤ h(| U | −1) max H GP (u , v)u ,v∈U2011/10/8

u ,v∈U「コンピューティクスによる物質デザイン」研究会

20ランダムウォークの「種類」	
o ランダムウォークの定義＝遷移確率n 遷移確率の候補は無限にある

o 遷移確率の決め方
n 任意（制限なし）
n 各頂点の「局所情報」のみを利用
o 0近傍： 次数情報のみ
n 例： 単純ランダムウォーク

o 1近傍： 隣接点の次数情報を利用可能
n 例： β-ランダムウォーク，メトロポリスウォーク

2011/10/8「コンピューティクスによる物質デザイン」研究会

21

単純ランダムウォーク	
o 単純ランダムウォーク（Simple Random Walk）	
1/2	 
1/2	 
２
1/2	 

１
1/2	 

1	  ４1/3	 
３ 1/3	 1/3	 G11 ⎛ 0

234 	 1/ 2 1/ 20 ⎞⎜⎟
2 ⎜1 / 20 1 / 2 0 ⎟
P = ⎜
0 1 / 3⎟
3 1/ 3 1/ 3⎜⎜⎟⎟
4 ⎝ 0010 ⎠n 隣接頂点に等確率で遷移するランダムウォーク
1n 遷移確率：
pu ,v =deg(u )2011/10/8「コンピューティクスによる物質デザイン」研究会

22

単純ランダムウォークに関する研究	
G=(V,E)，n=|V|, m=|E| に対してo 到達時間，訪問時間の上界[Aleliunas,1979]（どんなグラフに関しても以下で抑えられる）n 到達時間： O(nm)=O(n3)n 訪問時間： O(nm)=O(n3)o 到達時間，訪問時間の下界上下限が一致！
（解析はタイト）	

（以下をみたすグラフが存在する）n 到達時間： Ω (n3)n 訪問時間： Ω (n3)2011/10/8「コンピューティクスによる物質デザイン」研究会

23

単純ランダムウォークに対する最悪例	
o Lollipop graph2n/3	 n/3	 n 到達時間: Ω (n3)n 訪問時間： およそ 4n3/27	
2011/10/8「コンピューティクスによる物質デザイン」研究会

24

β-ランダムウォーク[Ikeda, et.al. 2003]	
o 隣接する頂点の情報を使うランダムウォークn 遷移確率：	

−β(deg(v) )pu ,v =−β()deg(w)∑

β＝1/2 のとき最適	 w∈N ( u )

13
11+2
312

11+2
3

次数の小さい点を優先する遷移確率！

33
1522
2011/10/8

4「コンピューティクスによる物質デザイン」研究会

25

β-ランダムウォークの速度	
G=(V,E)，n=|V|, m=|E| に対して[Ikeda, et.al, 2003,2009]o 到達時間，訪問時間の上界（どんなグラフに関しても以下で抑えられる）n 到達時間： O(n2)n 訪問時間： O(n2log n)

o 到達時間，訪問時間の下界（以下をみたすグラフが存在する）• 到達時間は上下限が一致！
・ 訪問時間にギャップ！	

n 到達時間： Ω (n2)n 訪問時間： Ω (n2)	
2011/10/8「コンピューティクスによる物質デザイン」研究会

26

β-ランダムウォークの良さ	
o 到達時間の面でβ-ランダムウォーク(β=1/2)は最適なオーダー O(n2)を達成
o パスグラフのランダムウォークn 「既約」ランダムウォークの到達時間は常に Ω (n2)	
どの点から出発しても全頂点を訪問	

2011/10/8「コンピューティクスによる物質デザイン」研究会

27

メトロポリス・ウォーク	
メトロポリス・ヘイスティングス法に基づくランダムウォーク
o メトロポリス・ヘイスティングス法 (MH法)n マルコフ連鎖モンテカルロ法の代表アルゴリズムn SIAMの選んだ20世紀10大アルゴリズムの一つn 特徴o サンプル空間から対象となるサンプルを任意の分布でサンプリングすることが可能
o 適当なサンプリングアルゴリズムを「任意の分布でサンプリングできる」ように修正する

2011/10/8「コンピューティクスによる物質デザイン」研究会

28

メトロポリス・ウォーク	
o 単純ランダムウォークにMH法を適用し，遷移確率を修正して得られランダムウォークn サンプリング・アルゴリズムの側面
n 「定常分布」π を指定可能
o 一様分布を指定することが多い
o つまり，一様サンプリングn 遷移確率： ⎧⎛ π v deg(u ) ⎞1min⎜⎜,1⎟⎟ v ∈ N (u ),⎪⎝ π u deg(v) ⎠⎪⎪ deg(u )puv = ⎨1 − ∑ puw
u = v,⎪ w∈N (u )otherwise.
⎪0⎪⎩

2011/10/8「コンピューティクスによる物質デザイン」研究会

29

メトロポリス・ウォークの速度	
[Nonaka et.al,2010]
π max := max π uu∈V

π min := min π uu∈Vf := π max / π min

o 到達時間，訪問時間の上界
2n 到達時間 : O ( fn )n 全訪問時間 : O ( fn 2 log n)
o 到達時間，訪問時間の下界
2Ω(fn)n 到達時間 :n 全訪問時間 : Ω( fn 2 log n)
2011/10/8「コンピューティクスによる物質デザイン」研究会

上下限が一致！
（解析はタイト）	

30

メトロポリス・ウォークの良さ	o Glitter star graphn スターの辺に頂点を挿入してできたグラフ

π max
π max

π max π max

o 右のような定常分布を実現する
u
任意のランダムウォークは，
π max π max π minn 到達時間： Ω( fn 2 )π max
2n 全訪問時間： Ω( fn log n)

π max

メトロポリスウォークは到達時間，訪問時間を最適のオーダーで実現！	
2011/10/8「コンピューティクスによる物質デザイン」研究会

31

次数情報とランダムウォークの高速化	
o β-ランダムウォークでは，隣接頂点の次数情報を利用することにより高速化
n 単純ランダムウォークの到達時間 O(n3) からO(n2) に高速化n 到達時間の面で最適

o 隣接頂点の次数情報は本質的か?
n より少ない（?）情報でこれが達成できないか	

2011/10/8「コンピューティクスによる物質デザイン」研究会

32

隣接頂点の次数情報までは不要	o 定理[Cooper, Ono, Radzik]
隣接頂点の次数の桁数までわかっていれば，到達時間O(n2)のランダムウォークが設計可能
o 以下の遷移確率で実現できる
pu ,v =(2)log d ( v ) − β∑ (2w∈N ( u ))log d ( w ) − β

o 隣接頂点の「次数の桁数」情報が本質的?
2011/10/8「コンピューティクスによる物質デザイン」研究会

33

隣接頂点の「次数の桁数」情報は本質的	o 定理[Cooper, Ono, Radzik]
隣接頂点wのlog (d(w))に対して， log (d(w))α
まで（α<1）しかわからない状況では，任意の反転可能なランダムウォークは到達時間はω(n2)となる	

2011/10/8「コンピューティクスによる物質デザイン」研究会

34

DNAの構造変化のマルコフモデル(再掲）	
o 近傍：現在の構造から塩基対を一つ変化させることで形成される構造の集合	
l

状態遷移確率	 rxy : xからyへの遷移割合	 l N(x) : xの近傍	 
l E(x) : xの自由エネルギー	 l∑r,xzz∈N ( x )大	 自由エネルギ

P( X t +1 = y | X t = x) =rxyyー	 E(y) - E x(x)小分子の構造	 2011/10/8y’⎧ ⎛ E ( y ) − E ( x) ⎞⎟ ( E ( y ) > E ( x))⎪exp⎜ −rxy = ⎨ ⎝
RT⎠
⎪
1
( E ( y ) < E ( x))⎩[Wolfinger et al. 2004]「コンピューティクスによる物質デザイン」研究会

35

桁数情報の必要十分性が示唆するもの	
o DNAの構造変化のマルコフモデル
n 隣接頂点のエネルギー情報を利用n エネルギー計算： 動的計画法
DNA配列の長さ k に対し, Θ(k) 時間を要するn 近傍サイズ： Θ(k)n １遷移ステップに Θ(k2)時間を要する

o 正確なエネルギー情報でなくとも，オーダー的には同等の速度のランダムウォークが得られうるn １遷移ステップに要する時間をΘ(k)時間に
2011/10/8「コンピューティクスによる物質デザイン」研究会

36

多種ランダムウォーク	o 一つのグラフの上を複数の粒子が遷移する
o 粒子ごとに遷移確率が異なる
o 到達時間と全訪問時間の関係
o 定理
G=(V,E) 上の遷移確率 P のランダムウォークにおいて，以下が成立
Pk
G

Pk
G

h(n !1)min S"V k ,v"V (H (S, v) !1) # C
PkGC
2011/10/8

PkG# h(n !1)max S"V k ,v"V H (S, v)「コンピューティクスによる物質デザイン」研究会

37

まとめ	
o ランダムウォークの解析から設計へ
o 物質デザインへの応用の可能性

o 興味ある方はご連絡ください
email: hirotaka@en.kyushu-u.ac.jp

2011/10/8「コンピューティクスによる物質デザイン」研究会38