集中講義（九州大学数理学研究院） バイオ構造データに対する数理モデルと アルゴリズム（ 1 ） スケールフリーネットワーク 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター.

Presentation on theme: "集中講義（九州大学数理学研究院） バイオ構造データに対する数理モデルと アルゴリズム（ 1 ） スケールフリーネットワーク 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター."— Presentation transcript:

1 集中講義（九州大学数理学研究院） バイオ構造データに対する数理モデルと アルゴリズム（ 1 ） スケールフリーネットワーク 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

2 講義内容 バイオインフォマティクス概観 スケールフリーネットワーク タンパク質進化の数理モデル 木構造および画像データに対する文法圧縮 ブーリアンネットワーク  定常状態検出アルゴリズム  ブーリアンネットワークの制御 木の編集距離

3 スケールフリーネット ワーク

4 グラフ  情報科学や離散数学における基礎概 念  グラフは頂点集合と辺集合から構成 される 頂点 ⇔ 物 （例：化合物） 辺 ⇔ ２個の物の間の関係 （例：化学 反応）  無向グラフ：辺に方向無し  有向グラフ：辺に方向有り ネットワーク  グラフの辺などに意味や量などのつ いたもの  本講義ではグラフとネットワークを 区別しない グラフとネット ワーク

5 グラフと生物情報ネットワー ク 代謝ネットワーク (KEGG) グラ フ ・ 点と線で構造を表す

6 代謝ネットワーク  頂点 ⇔ 化合物、 辺 ⇔ 代謝反応 タンパク質相互作用ネットワーク  頂点 ⇔ タンパク質、 辺 ⇔ 相互作用 遺伝子ネットワーク  頂点 ⇔ 遺伝子、 辺 ⇔ 遺伝子間制御関係 WWW  頂点 ⇔ WEB ページ、辺 ⇔ リンク 共著関係  頂点 ⇔ 研究者、 辺 ⇔ 共著論文の有無 グラフと実際のネットワークの対 応

7 スモールワールド： 頂点間の距離 頂点間のパス  二つの頂点をつなぐ辺の列 パスの長さ  パス中の辺の個数 頂点間の距離  距離が最短のパスの長さ A と E の間のパスの例 パス 1: (A,G), (G,B), (B,F),(F,E) ⇒長さ =4 パス 2: (A,G), (G,F), (F,E) ⇒長さ =3 パス 3: (A,B), (B,E) ⇒長さ =2 A と E の距離＝２ (A と I の距離 =3 、 C と H の距離 =3)

8 スモールワールド： クラスター係 数 クラスター係数  m i ：頂点 i に隣接する頂点 間の辺の個数  k i ：頂点 i の次数 頂点のまわりのモ ジュール性の指標  C i ≒ 1 ＜－＞ クリーク に近い  m i の最大値は i Ci = 1 i Ci = 0

9 スモールワールド 任意の２頂点間の距離（最 短経路）の平均値が小さく （ O(log n) 以下）、かつ、ク ラスター係数の平均値が大 きいグラフ 多くの現実のネットワーク はスモールワールドとなる WWW の直径（各サイト間 のリンク数の平均値）は？ ⇒約１９クリック (Albert al., Nature, 1999) 直径≦３

10 頂点の次数 その頂点につな がっている辺の個 数 P(k) 次数分布 次数 k の頂点の頻 度 スケールフリー ネットワーク P(k) がべき乗則に 従う スケールフリーネットワーク （１）

11 スケールフリーネットワーク （２） 次数 頂点数 ∝ ( 次数 ) -3

12 スケールフリーネットワーク （３） 次数 k の頂点の個数が k -γ に比例（べき乗則）  ランダムな場合 ( ポアソン分布 : e -λ λ k /k!) と大差 Barabasi らが 1999 年頃に発見。以降、数多く の研究 特徴： 有力な頂点（ハブ）に多くの頂点が連 結 実際のネットワークにおける k –γ  タンパク質相互作用： γ ≒ 2.2  代謝ネットワーク： γ ≒ 2.24 （生物種により異なる）  映画俳優の共演関係： γ ≒ 2.3  WWW ： γ ≒ 2.1  送電網： γ ≒ 4

13 ポアソン分布とべき乗分布 P (k)P (k) klog(k) log P (k) ポアソン分布 （ランダムグラフ） べき乗分布 （スケールフリーグラ フ）

14 タンパク質ネットワークの解 析 タンパク質相互作用のネットワークもべき乗 則に従う（酵母の場合）  頂点：タンパク質  辺：相互作用の有無 次数５以下の頂点（全体の 93% ）  ２１％程度が必須（生存に必要） 次数１６以上の頂点（全体の 0.7 ％）  62 ％程度が必須  次数の高い頂点はハブと呼ばれ、重要な役割を果 たすものが多い

15 スケールフリーネットワーク構成法：優先的選択 法 優先的選択法 ( 優先的選択型成長モデル ) [Barabasi & Albert 1999]  別名： Rich-get-richer モデル 構成法 （ほぼ、 k -3 のべき乗則従うネットワークを生成）  m 0 個の頂点から成るグラフを構成する  以下のステップを必要なだけ繰り返す 現在のグラフに新たな頂点 v を追加する v から既存の頂点に、 deg(v i )/(Σ j deg(v j )) に従う確率で、ランダムに 辺を張る（全部で m 本の辺を張る） 参考：ランダムグラフの構成法  N 個の頂点を配置  以下の操作を辺の個数が指定の数になるまで繰り返す 任意の２頂点をランダムに選んでは辺を追加 （もしくは、一様な確率 p で任意の 2 頂点間に辺を引く）

16 ランダムネットワーク vs. スケールフリーネット ワーク 2/6 3/10 2/10 4/14 2/14 4/14 ランダムネットワーク スケールフリーネットワーク

17 優先的選択法の平均場近似による解析 k i (t): （時刻 t i ）に追加された頂点 i の時刻 t における次数 時刻 t までに追加された辺の個数≒ mt 時刻 t において頂点 i の次数が増加する確率は この微分方程式を条件 k i (t i )=m のもとで解くと 時刻 t n にネットワークが完成したとすると、 次数 k の頂点の生成時刻は、 k i (t n )=k を解いて、 ここで、 k が１だけ増えると、 t i がどれくらい減るかは、 上の式を k で微分することにより、 よって、時刻が 2t n m 2 k -3 だけ異なると k が１変わる よって、次数 k の頂点は 2t n m 2 k -3 のオーダーの個数存在

18

19 階層型スケールフリーネットワーク 優先的選択法によるスケールフリーネットワ ーク  クラスター係数の平均値（ ）が小さい（ ） 実際の代謝ネットワーク  クラスター係数の平均値が大きい  階層的な構造をしていると考えられる ⇒ クラスター係数が大きな階層的スケールフ リーネットワークの構成法

20 階層型ネットワークの構成法 再帰的、かつ、決定的（乱数を使わず）に構成 フラクタル的 L 角形を使うと クラスター係数 は定数オーダー [Ravasz et al, Nature, 2002]

21 階層型ネットワークの解析

22 L+M モデル Barabasi のモデルの拡張 ２より大きな任意の値にいくらでも近い γ を持つネ ットワークを構成可能 ( Barabasi モデルでは γ<2.58 ) ( L =2) (M=2)

23 L+M モデルの解析

24 Barabasi らの階層モデルの解釈 Barabasi らの階層スケールフリーモデル ⇒ L+M モデルにおける M =1 の場合に相 当 L =3, M =1

25 まとめ グラフとネットワーク  頂点と辺 スモールワールド  ２頂点間の平均距離が短いグラフ スケールフリーネットワーク  次数分布がべき乗則に従うネットワーク スケールフリーネットワークの構成法  優先的選択型成長モデル  階層型モデル  L+M モデル