生命情報学 (8) 生物情報ネットワークの構造解析

Slides:



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

奈良女子大集中講義 バイオインフォマティクス (3) 配列アラインメント
生命情報学基礎論 (2) 配列の比較と相同性検索
4.3 マージソート.
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
情報生命科学特別講義III (1) 文字列マッチング
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
タンパク質相互作用ネットワークの スケールフリーモデル
情報生命科学特別講義III (8)木構造の比較: 順序木
奈良女子大集中講義 バイオインフォマティクス (8) タンパク質立体構造予測
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
伝播速度限定モデル Scale Free Network 上 の情報拡散 日本大学文理学部 情報システム解析学科 谷聖一研究室 古池 琢也
Scale Free Network 上における 伝播速度限定モデルの情報拡散シミュレーション
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
奈良女子大集中講義 バイオインフォマティクス (6) モチーフ発見・隠れマルコフモデル
生命情報学入門 タンパク質立体構造予測演習2011年5月31日
リンク構造を考慮したベクトル空間法によるWebグラフ分割手法に関する研究
C11: 大量データ処理のための領域効率の良いアルゴリズム
京都大学 化学研究所 バイオインフォマティクスセンター
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
線形計画法 スケールフリーネットワーク 須藤 孝秀.
京都大学 化学研究所 バイオインフォマティクスセンター
分子生物情報学(7) 遺伝子発現データの情報解析法 スケールフリーネットワーク
京都大学 化学研究所 バイオインフォマティクスセンター
奈良女子大集中講義 バイオインフォマティクス (10) スケールフリーネットワーク
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
電気・通信・電子・情報工学実験D 確率的情報処理の基礎 第3部講義(2007年6月19日,6月26日)
生命情報学基礎論 (5) タンパク質立体構造予測
生命情報学入門 配列のつなぎ合わせと再編成
遺伝的アルゴリズムへの 統計力学的アプローチ 大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部
九州大学大学院 情報学専攻特別講義 (9) ブーリアンネットワークの 解析と制御
膜タンパク質の 立体構造予測.
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
WWW上の効率的な ハブ探索法の提案と実装
『企業と市場のシミュレーション』 井庭 崇 第9回: 成長するネットワークモデル
ランダムグラフ エルデシュとレーニイによって研究された.→ER-model p:辺連結確率 N:ノード総数 分布:
タンパク質の進化 タンパク質は進化の過程でどのようにドメインを獲得してきたのだろうか? 今のタンパク質を調べることでわからないだろうか?
九州大学大学院 情報学専攻特別講義 (3) 配列解析
生  物  数  学 斉木 里恵.
分子生物情報学(2) 配列のマルチプルアライメント法
情報生命科学特別講義III (13) 固定パラメータアルゴリズムと 部分k木
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
生命情報学特論 (8)複雑ネットワークと制御理論
分子生物情報学(3) 確率モデル(隠れマルコフモデル)に 基づく配列解析
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
統計解析 第1回 条件付き独立性と確率的グラフィカルモデル 本講義の全体像
第4章 社会構造概念はどのように豊穣化されるか
九州大学大学院 情報学専攻特別講義 (6) 固定パラメータアルゴリズムと 部分k木
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
京都大学 化学研究所 バイオインフォマティクスセンター
構造的類似性を持つ半構造化文書における頻度分析
九州大学大学院 情報学専攻特別講義 (8) ニューラルネットワークの 離散モデル
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
奈良女子大集中講義 バイオインフォマティクス (7) 進化系統樹
九大数理談話会 複雑ネットワークと制御理論
情報生命科学特別講義III (14) グラフの比較と列挙
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木
生物情報ソフトウェア特論 (4)配列解析II
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
Speaker: Kazuhiro Inaba Paper Introduction from WSDM 2015
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
生物情報ソフトウェア特論 (10)固定パラメータアルゴリズムと 部分k木
集中講義(東京大学)「化学システム工学特論第3」 バイオインフォマティクス的手法による化合物の性質予測(1) バイオインフォマティクス概観
分子生物情報学(0) バイオインフォマティクス
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

生命情報学 (8) 生物情報ネットワークの構造解析 生命情報学 (8) 生物情報ネットワークの構造解析 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

講義予定 4月13日(月): 生命情報学の基盤 4月20日(月): 配列の比較と相同性検索 4月27日(月): 進化系統樹推定 4月13日(月): 生命情報学の基盤 4月20日(月): 配列の比較と相同性検索 4月27日(月): 進化系統樹推定 5月1日(金):  隠れマルコフモデル 5月11日(月): 遺伝子ネットワークの解析と制御(田村) 5月18日(月): タンパク質立体構造予測 5月25日(月)、6月1日(月): カーネル法 6月8日(月):  代謝ネットワークの堅牢性(田村) 6月15日(月): 生物情報ネットワークの構造解析 6月22日(月): 木の編集距離(田村) 6月29日(月): タンパク質相互作用予測(林田) 7月6日(月):  タンパク質複合体予測(林田) 7月13日(月): 生物データの圧縮による比較(林田)

内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法 ネットワークモチーフ 優先的選択型成長モデル 階層型ネットワーク ネットワークモチーフ

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

内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法 ネットワークモチーフ 優先的選択型成長モデル 階層型ネットワーク ネットワークモチーフ

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

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

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

内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法 ネットワークモチーフ Preferential Attachment (Rich-get-Richer) 階層型ネットワーク ネットワークモチーフ

スモールワールド: 頂点間の距離 頂点間のパス パスの長さ 頂点間の距離 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の距離=2 (AとIの距離=3、CとHの距離=3)

スモールワールド: クラスター係数 i i mi :頂点 i に隣接する頂点間の辺の個数 ki :頂点 i の次数 頂点のまわりのモジュール性の指標 Ci ≒ 1  ⇔ クリークに近い mi の最大値は i Ci = 1 i Ci = 0

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

内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法 ネットワークモチーフ 優先的選択型成長モデル 階層型ネットワーク ネットワークモチーフ

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

代謝マップ, グラフ, 次数 A B C D F G H I J E 次数 次数分布: P(k) 次数1の頂点: J 次数3の頂点: A, E, I 次数分布: P(k) P(1)=0.1, P(2)=0.6, P(3)=0.3, P(4)=P(5)=P(6)=…=0

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

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

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

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

内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法 ネットワークモチーフ 優先的選択型成長モデル 階層型ネットワーク ネットワークモチーフ

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

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

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

内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法 ネットワークモチーフ 優先的選択型成長モデル 階層型ネットワーク ネットワークモチーフ

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

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

内容 背景 グラフとネットワーク スモールワールド スケールフリーネットワーク スケールフリーネットワークの構成法 ネットワークモチーフ 優先的選択型成長モデル 階層型ネットワーク ネットワークモチーフ

ネットワークモチーフ モチーフ ネットワークモチーフ ネットワークモチーフの例 配列解析において現れる機能と関連した配列パターン 例: L-x(6)-L-x(6)-L-x(6)-L (ロイシンジッパーモチーフ) ネットワークモチーフ (ランダムなネットワークと比べて)実際のネットワークにおいて頻出する(統計的に有意に)ネットワークのパターン ネットワークのパターン: 部分グラフ ランダムネットワークの作成: 辺の交換の繰り返し ネットワークモチーフの例 フィードフォワード制御 Single Input Module Dense Overlapping regulons

配列モチーフの例 ジンクフィンガーモチーフ C-x(2,4)-C-x(3)-[LIVMFYWC]-x(8)-H-x(3,5)-H ロイシンジッパーモチーフ L-x(6)-L-x(6)-L-x(6)-L

ネットワークモチーフの例 (1) ネットワーク モチーフ

ネットワークモチーフの例 (2)

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