集中講義（九州大学数理学研究院） バイオインフォマティクスにおける カーネル法およびグラフ理論 (1) スケールフリーネットワーク

Presentation on theme: "集中講義（九州大学数理学研究院） バイオインフォマティクスにおける カーネル法およびグラフ理論 (1) スケールフリーネットワーク"— Presentation transcript:

1 集中講義（九州大学数理学研究院） バイオインフォマティクスにおける カーネル法およびグラフ理論 (1) スケールフリーネットワーク
阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

2 内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法
Preferential Attachment (Rich-get-Richer) 線グラフ変換によるスケールフリー性の変換則 階層型スケールフリーネットワークの構成法

3 背景 システム生物学 ネットワーク生物学 生命をシステムとして理解 生命をネットワークとして理解 ネットワークの構造上の特徴の解析
相互作用、ネットワーク推定 シミュレーション 安定性解析、制御 ネットワーク生物学 生命をネットワークとして理解 スモールワールド(1998) スケールフリーネットワーク(1999) ネットワークモチーフ(2002) ネットワークの構造上の特徴の解析 ネットワークの動的挙動の解析

4 内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法
Preferential Attachment (Rich-get-Richer) 線グラフ変換によるスケールフリー性の変換則 階層型スケールフリーネットワークの構成法

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

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

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

8 内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法
Preferential Attachment (Rich-get-Richer) 線グラフ変換によるスケールフリー性の変換則 階層型スケールフリーネットワークの構成法

9 スモールワールド： 頂点間の距離 頂点間のパス パスの長さ 頂点間の距離 AとEの間のパスの例
二つの頂点をつなぐ辺の列 パスの長さ パス中の辺の個数 頂点間の距離 長さが最短のパスの長さ 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)

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

11 内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法
Preferential Attachment (Rich-get-Richer) 線グラフ変換によるスケールフリー性の変換則 階層型スケールフリーネットワークの構成法

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

13 代謝マップ, グラフ, 次数 A B C D F G H I J E 次数 次数分布: P(k) 次数1の頂点： J
　代謝マップ, グラフ, 次数 A B C D F G H I J E 次数 次数1の頂点： J 次数2の頂点： B, C, F, G, H 次数3の頂点： E, I, A, D 次数分布: P(k) P(1)=0.1, P(2)=0.5, P(3)=0.4

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

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

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

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

18 内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法
Preferential Attachment (Rich-get-Richer) 線グラフ変換によるスケールフリー性の変換則 階層型スケールフリーネットワークの構成法

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

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

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

22

23 内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法
Preferential Attachment (Rich-get-Richer) 線グラフ変換によるスケールフリー性の変換則 (Nacher, Yamada, Goto, Kanehisa, Akutsu: Physica A, 349: , 2005) (関連研究：　Ramezanpour & Karimipour: Physical Review E, 67:046107, 2003) 階層型スケールフリーネットワークの構成法

24 代謝ネットワークの二種類の表現法 化合物ネットワーク 反応ネットワーク 頂点 ⇔ 化合物 辺 ⇔ 化学反応 頂点 ⇔ 化学反応（酵素反応）
頂点　⇔　化合物 辺　　 ⇔　化学反応 反応ネットワーク 頂点　⇔　化学反応（酵素反応） 辺　　 ⇔　二つの化学反応が共通に持つ化合物

25 　化合物ネットワークと反応ネットワーク 　化合物ネットワーク 　反応ネットワーク

26 線グラフ変換 a c e d b G の辺 ⇒ L(G) の頂点 L(G) に辺 iff. G の二つの辺が同じ頂点を端点として共有 1 5
　線グラフ変換 G の辺 ⇒ L(G) の頂点 L(G) に辺 iff. G の二つの辺が同じ頂点を端点として共有 1 5 2 4 3 a b c d e

27 線グラフ変換と代謝ネットワーク 対応関係 ただし、この変換は厳密ではない 化合物ネットワーク ⇔ 変換前のグラフ
　線グラフ変換と代謝ネットワーク 対応関係 化合物ネットワーク　⇔　変換前のグラフ 反応ネットワーク 　　⇔　変換後のグラフ ただし、この変換は厳密ではない ⇒　Physical Line Graph Transformation を後で定義

28 線グラフ変換によるスケールフリー性の変換則
P(k) ∝ k –γ in G　⇒ P(k)∝ k –γ+1 in L(G) ただし、 assortative mixing が G に無いと仮定 (i.e, どの頂点も隣接点の次数に関する好みが無い) 直感的な説明 G における次数 k の頂点 v には k 本の辺が接続 これらの k 本の辺は L(G) における k 個の頂点に対応 これらの k 個の頂点は k 程度の次数を持つと期待される よって、 G の頂点 v から、 L(G) における次数 k 程度の k 頂点を得る よって、 P(k) ∝ k・k –γ ＝ k –γ が L(G)　において成立 次数 k 次数≒ k (少なくとも k)

29 　Physical Line Graph変換 　実際の化学反応に対応する辺のみを L(G) に作成 C1 C3 C6 C2 C5

30 人工ネットワークに対する結果 Inverted Beta Distr. L(G) G Polygamma Distr.

31 WWW Protein-protein Interaction KEGG Metabolic pathways KEGG-real line graph transformation Metabolic pathways

32 線グラフ変換に関する結果 線グラフ変換によりスケールフリー性は保存されるが、γは１だけ変化
　線グラフ変換に関する結果 線グラフ変換によりスケールフリー性は保存されるが、γは１だけ変化 変換後のネットワークでは、実際のネットワークと似た、山なりの部分が観測される

33 内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法
Preferential Attachment (Rich-get-Richer) 線グラフ変換によるスケールフリー性の変換則 階層型スケールフリーネットワークの構成法 (Nacher, Ueda, Kanehisa, Akutsu: Physical Review E, 71:036132, 2005)

34 スケールフリーネットワーク構成法：階層型ネットワーク
Hierarchical Scale-Free Network [Ravasz, Barabasi et al. 2002] 別名：Deterministic Scale-Free Network 再帰的に構成 フラクタル的 L角形を使うと P(k)= k -1-(ln(L+1)/ln(L))

35 L+Mモデル Barabasi のモデルの拡張

36 　L+M モデルの解析

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

38 L+Mモデルに関するまとめ L+Mモデル：Barabasi らの階層スケールフリーネットワークモデルの拡張
２より大きな任意の値にいくらでも近いγを持つネットワークを構成可能

39 まとめ グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法
　まとめ グラフとネットワーク 頂点と辺 スモールワールド ２頂点間の平均距離が短いグラフ スケールフリーネットワーク 次数分布がべき乗則に従うネットワーク スケールフリーネットワークの構成法 Preferential Attachment (Rich-get-Richer) 線グラフ変換によるスケールフリー性の変換則 P(k)∝k -γ ⇒ 線グラフ変換 ⇒ P(k)∝k -γ+1 階層型スケールフリーネットワーク の構成法

40 　参考文献 A-L. Barabasi, Z. N. Oltvai, Network biology: Understanding the cell’s functional organization, Nature Reviews Genetics, 5: , 2004. A-L. Barabasi 著（青木訳）, 新ネットワーク思考, NHK出版, 2002 J.C. Nacher et al., Two complementary representations of a scale-free network, Physica A, 349: , 2005. J.C. Nacher et al., Flexible construction of hierarchical scale-free networks with general exponent, Physical Review E, 71:036132, 2005. 阿久津、ネットワーク生物学における情報解析、実験医学増刊号「ゲノム医科学研究の最先端」、23(4): , 2005.