Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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

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

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

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

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

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 の距離=2 (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 スモールワールド 任意の2頂点間の距離(最 短経路)の平均値が小さく ( O(log n) 以下)、かつ、ク ラスター係数の平均値が大 きいグラフ 多くの現実のネットワーク はスモールワールドとなる WWW の直径(各サイト間 のリンク数の平均値)は? ⇒約19クリック (Albert al., Nature, 1999) 直径≦3

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

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

12 スケールフリーネットワーク (3) 次数 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 タンパク質ネットワークの解 析 タンパク質相互作用のネットワークもべき乗 則に従う(酵母の場合)  頂点:タンパク質  辺:相互作用の有無 次数5以下の頂点(全体の 93% )  21%程度が必須(生存に必要) 次数16以上の頂点(全体の 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 個の頂点を配置  以下の操作を辺の個数が指定の数になるまで繰り返す 任意の2頂点をランダムに選んでは辺を追加 (もしくは、一様な確率 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 が1だけ増えると、 t i がどれくらい減るかは、 上の式を k で微分することにより、 よって、時刻が 2t n m 2 k -3 だけ異なると k が1変わる よって、次数 k の頂点は 2t n m 2 k -3 のオーダーの個数存在

18

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

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

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

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

23 L+M モデルの解析

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

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


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

Similar presentations


Ads by Google