九州大学集中講義2010

集中講義(九州大学数理学研究院)
バイオ構造データに対する数理モデルと
アルゴリズム(1)
スケールフリーネットワーク
阿久津 達也
京都大学 化学研究所
バイオインフォマティクスセンター
講義内容





バイオインフォマティクス概観
スケールフリーネットワーク
タンパク質進化の数理モデル
木構造および画像データに対する文法圧縮
ブーリアンネットワーク



定常状態検出アルゴリズム
ブーリアンネットワークの制御
木の編集距離
スケールフリーネットワーク
グラフとネットワーク

グラフ


情報科学や離散数学における基礎概
念
グラフは頂点集合と辺集合から構成さ
れる





頂点 ⇔ 物 (例:化合物)
辺 ⇔ 2個の物の間の関係 (例:化学反
応)
無向グラフ:辺に方向無し
有向グラフ:辺に方向有り
ネットワーク


無向グラフ
グラフの辺などに意味や量などのつい
たもの
本講義ではグラフとネットワークを区別
しない
有向グラフ
グラフと生物情報ネットワーク
代謝ネットワーク (KEGG)
グラフ
・点と線で構造を表す
グラフと実際のネットワークの対応

代謝ネットワーク


頂点 ⇔ 遺伝子、
辺 ⇔ 遺伝子間制御関係
WWW


頂点 ⇔ タンパク質、 辺 ⇔ 相互作用
遺伝子ネットワーク


辺 ⇔ 代謝反応
タンパク質相互作用ネットワーク


頂点 ⇔ 化合物、
頂点 ⇔ WEBページ、辺 ⇔ リンク
共著関係

頂点 ⇔ 研究者、
辺 ⇔ 共著論文の有無
スモールワールド: 頂点間の距離



二つの頂点をつなぐ辺の列
G
A
F
パスの長さ


H
頂点間のパス
パス中の辺の個数
B
頂点間の距離

I
距離が最短のパスの長さ
C

D
AとEの間のパスの例




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)
スモールワールド: クラスター係数

クラスター係数
2mi
Ci 
ki (ki  1)

mi :頂点 i に隣接する頂点
間の辺の個数


Ci = 1
ki :頂点 i の次数
頂点のまわりのモジュー
ル性の指標

Ci ≒ 1 <-> クリークに
近い

i
mi の最大値は
ki (ki  1)
2
i
Ci = 0
スモールワールド



任意の2頂点間の距離(最短
経路)の平均値が小さく
(O(log n)以下)、かつ、クラス
ター係数の平均値が大きいグ
ラフ
多くの現実のネットワークはス
モールワールドとなる
WWWの直径(各サイト間の
リンク数の平均値)は? ⇒
約19クリック(Albert al., Nature, 1999)
H
G
A
F
B
E
I
C
D
直径≦3
スケールフリーネットワーク(1)

頂点の次数


P(k)



次数=5
その頂点につながっ
ている辺の個数
次数分布
次数 k の頂点の頻
度
次数=2
スケールフリーネッ
トワーク

P(k) がべき乗則に
従う
P( k )  k

次数=3
スケールフリーネットワーク (2)
次数=5
次数=2
頂
点
数
頂点数 ∝ (次数)-3
次数
次数=3
スケールフリーネットワーク (3)

次数 k の頂点の個数が k -γに比例(べき乗則)

ランダムな場合(ポアソン分布: e-λλk/k!)と大差

Barabasi らが1999年頃に発見。以降、数多くの研
究
特徴: 有力な頂点(ハブ)に多くの頂点が連結

実際のネットワークにおける k –γ






タンパク質相互作用: γ≒2.2
代謝ネットワーク: γ≒2.24 (生物種により異なる)
映画俳優の共演関係:γ≒2.3
WWW:γ≒2.1
送電網: γ≒4
ポアソン分布とべき乗分布
べき乗分布
(スケールフリーグラフ)
P (k)
log P (k)
ポアソン分布
(ランダムグラフ)
k
log(k)
タンパク質ネットワークの解析

タンパク質相互作用のネットワークもべき乗則に
従う(酵母の場合)



次数5以下の頂点(全体の93%)


頂点:タンパク質
辺:相互作用の有無
21%程度が必須(生存に必要)
次数16以上の頂点(全体の0.7%)


62%程度が必須
次数の高い頂点はハブと呼ばれ、重要な役割を果た
すものが多い
スケールフリーネットワーク構成法:優先的選択法

優先的選択法(優先的選択型成長モデル)


別名: Rich-get-richer モデル
構成法(ほぼ、k -3 のべき乗則従うネットワークを生成)


m0 個の頂点から成るグラフを構成する
以下のステップを必要なだけ繰り返す



[Barabasi & Albert 1999]
現在のグラフに新たな頂点 v を追加する
v から既存の頂点に、deg(vi)/(Σj deg(vj)) に従う確率で、ランダムに辺を
張る(全部で m 本の辺を張る)
参考:ランダムグラフの構成法


N個の頂点を配置
以下の操作を辺の個数が指定の数になるまで繰り返す

任意の2頂点をランダムに選んでは辺を追加
(もしくは、一様な確率pで任意の2頂点間に辺を引く)
ランダムネットワーク vs. スケールフリーネットワーク
ランダムネットワーク
スケールフリーネットワーク
2/6
2/6
4/14
3/10
3/10
2/6
2/14
4/14
2/10
2/10
2/14
2/14
優先的選択法の平均場近似による解析



ki(t): (時刻 ti)に追加された頂点 i の時刻 t における次数
時刻 t までに追加された辺の個数≒mt
ki (t ) mk i (t )

時刻 t において頂点 i の次数が増加する確率は t
2mt
t
ki (t )  m 
 ti 
0.5

この微分方程式を条件 ki(ti)=m のもとで解くと

時刻 tn にネットワークが完成したとすると、
次数 k の頂点の生成時刻は、ki(tn)=k を解いて、


ここで、k が1だけ増えると、ti がどれくらい減るかは、  2m 2t
n
上の式を k で微分することにより、
k3
よって、時刻が 2tnm2k -3 だけ異なると k が1変わる

よって、次数 k の頂点は 2tnm2k -3 のオーダーの個数存在
m 2t n
ti  2
k
ki (t)
k+1
k
m
 2m 2t n
ti 
k3
m 2t n
ti  2
k
tn
t
階層型スケールフリーネットワーク

優先的選択法によるスケールフリーネットワーク


クラスター係数の平均値(
実際の代謝ネットワーク


1
n
C
1i n
i
)が小さい( O(n
 ( 3 / 4)
))
クラスター係数の平均値が大きい
階層的な構造をしていると考えられる
⇒ クラスター係数が大きな階層的スケールフリー
ネットワークの構成法
階層型ネットワークの構成法



再帰的、かつ、決定的(乱数を使わず)に構成
フラクタル的
L角形を使うと
P(k )  k 1(ln(L1) / ln(L))

クラスター係数
は定数オーダー
[Ravasz et al, Nature, 2002]
階層型ネットワークの解析
レベル i のハブの次数は
n=1
i=1のハブ
2  2 2  23    2i
 2i 1  2  2i
n=2
i=2のハブ
ステップ n におけるレベル
i のハブの個数は
n=3
(2 / 3)3n i 1  3n i
i=2
n=4
ここで、k  2i とおくと、
3
i=1
n i
 3 / 3  3 (k
よって、γ
n
i
n
 lnln 32
)
ln 3
ln 2
(実際には binningのため、
γ 1  lnln 32 )
L+Mモデル


Barabasi のモデルの拡張
2より大きな任意の値にいくらでも近いγを持つネットワ
ークを構成可能
(Barabasi モデルでは γ<2.58 )
ln(L  M )
  1
ln(L)
(L=2)
(M=2)
L+M モデルの解析
Degree of i - th levelnode is around Li
T henumber of i - th levelnodes in n - th step is around
( L  M ) n i
By letting k  L ,
i
( L  M ) n i  ( L  M ) n /( L  M ) i  ( L  M ) n (k
T hus, we have γ
 ln (lnLLM )
)
ln ( L  M )
ln ( L )
(Finally, by binning, γ 1 
ln( L  M )
ln ( L )
)
ln(L  M )
  1
ln(L)
Barabasiらの階層モデルの解釈

Barabasi らの階層スケールフリーモデル
⇒ L+Mモデルにおける M=1 の場合に相当
ln(L  M )
ln(L  1)
ln(3)
  1
 1
 1
 2.58
ln(L)
ln(L)
ln(2)
L=3, M=1
まとめ

グラフとネットワーク


スモールワールド


2頂点間の平均距離が短いグラフ
スケールフリーネットワーク


頂点と辺
次数分布がべき乗則に従うネットワーク
スケールフリーネットワークの構成法



優先的選択型成長モデル
階層型モデル
L+Mモデル