生命情報学特論 （８）複雑ネットワークと制御理論 生命情報学特論 （８）複雑ネットワークと制御理論 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

内容 スケールフリーネットワーク スケールフリーネットワークの構造的可制御性 最小支配集合（MDS) MDSサイズの理論解析 計算機シミュレーションによる解析 データベース解析 生物情報ネットワーク解析への応用 MDSの拡張 結論

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

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

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

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

スケールフリーネットワークの構造的可制御性 [Liu, Slotine, Barabasi: Nature, 2011]

線形システムの可制御性 （１） 入力: 出力: 線形システム: 初期状態: x0 目標状態: xF 線形システムの可制御性　（１） 入力: 線形システム: 初期状態: x0 目標状態: xF 出力: 有限時間で、システムの状態を x0 から xF へ導く制御 u(t) (tの関数) x(t): N-dim. real vector (internal nodes) u(t): M-dim. real vector (control nodes) A: N×N real matrix B: N×M real matrx

線形システムの可制御性　（２） 定理. システムが可制御 iff N×NM 行列 C=(B,AB,A2B,…,AN-1B) のランクがN (i.e., rank(C)=N). ほとんど係数について rank(C)=4 ⇒ 構造的可制御性

構造的可制御性 定理. [Liu et al. 2011] GB(VL,VR;EB) : G(V,E) から以下により構成した二部グラフ M* を GB の最大マッチングのサイズ（辺数）とする時。 システムを構造的可制御とするために必要な制御頂点（driver nodes）の最小数は max {N-M*,1} driver nodes

スケールフリーネットワークの構造的可制御性 構造的可制御のための driver nodes 数 [Liu et al. 2011] ランダムなネットワーク スケールフリーネットワーク ⇒ γ<2 の場合、多くの driver nodes が必要 n: ネットワークの頂点数

最小支配集合（MDS）

最小支配集合 （１） VD が無向グラフ G(V,E) の支配集合（dominating set） ⇔ (∀v∈V)（v ∈VD∨(∃u∈VD)({u,v}∈E)) 最小支配集合（MDS: minimum dominating set）: 要素数最小の支配集合

最小支配集合 （２） NP困難であるが、線形計画法＋分枝限定法に基づく実用的ソフトが存在 人工ネットワークの設計・制御への既存応用 mobile ad-hoc networks (MANET) transportation routing computer communication networks

MDSと可制御性の関係 定理. [Nacher & Akutsu, 2012] ネットワークの各辺は両方向性であり、MDSの各頂点はすべての接続辺を個別に制御可能であると仮定。すると、MDSを driver nodes として選択すれば、システムは構造的可制御。

MDSサイズの理論解析

解析結果 （近似的な解析） γ>2 上限: trivially O(n) 下限: O(n) (to be shown) γ<2 解析結果　（近似的な解析） γ>2 上限: trivially O(n) 下限: O(n) (to be shown) γ<2 上限: O(n1-(2-γ)(γ-1)) 下限: ?

γ>2 の時の下限 （１） 次数分布がαk-γに従うとして、 以下のようにαを決定 γ>2 の時の下限 （１） 次数分布がαk-γに従うとして、 以下のようにαを決定 C(S) をS と V-S の間の辺の集合とすると、 |S|+|C(S)|<n であれば、 S は支配集合でない S として次数 K 以上の頂点をすべて選ぶと

γ>2 の時の下限 （２） |S|<n/2 を仮定できるので、 よって、 |S| の下限は以下のように見積もれる γ>2 の時の下限 （２） |S|<n/2　を仮定できるので、 よって、 |S| の下限は以下のように見積もれる これは γ についての増加関数になっている

γ<2 の場合の上限の解析 (1) 次数 K=nβ 以上の頂点集合を DS とする その頂点数NDS は、 一方、辺の総数 EG は、 γ<2 の場合の上限の解析 (1) 次数 K=nβ 以上の頂点集合を DS　とする その頂点数NDS は、 一方、辺の総数 EG は、 EDS (=DSに接続する辺の個数) は、 よって、任意に選んだ辺が DS に接続しない確率は、

γ<2 の場合の上限の解析 (2) DSに接続しない辺があると、その頂点がDSにカバーされない可能性　⇒ DSにカバーされない頂点数の期待値 (NG-DS) は次式以下 NG-DS と NDS をバランスさせると より、β=2-γ を得る よって、MDS の上限は この式は 1<γ<2　において o(n) さらに、γ=1.5 の時、最小オーダー (O(n0.75))となる This analysis is a corrected version of one in our paper appeared in New Journal of Physics.

γ<2の時の説明 次数 nβ 以上の頂点数 そこから出る辺でカバー されない頂点数 以下を満たす β を選ぶ MDSのサイズ ≥nβ

生物情報ネットワーク解析への応用

MDS の生体ネットワーク解析への応用 実際の生物の制御は困難 でも、MDS は重要性の高いタンパク質や遺伝子の検出には有効 タンパク質相互作用ネットワーク解析への応用 [Milenkovic et al. PLoS One, 2011] (before our work) [Wuchty, PNAS, 2014] [Khuri & Wuchty, BMC Bioinformatics, 2015] [Wang et al., BIBM 2014] 代謝ネットワーク解析への応用 [Asgari et al., PLoS ONE, 2013]

タンパク質相互作用ネットワーク解析への応用 MDSは重要なタンパクの検出に有効　 [Wuchty, PNAS 2014] 必須遺伝子、がん関連遺伝子、ウィルスの標的遺伝子などにおいて、MDS 中のタンパク質の比率が高い. These proteins are highly involved in regulatory functions, showing high enrichment in transcription factors and protein kinases, and participate in regulatory links, phosphorylation events, and genetic interactions. [Wuchty, PNAS 2014]

MDSの拡張

二部グラフ構造を持つネットワークの制御 多くのネットワークは二部グラフ構造を持つ 薬剤・標的、研究者・共著論文、遺伝子・疾患ネットワークなど 左側頂点のみが制御頂点となる MDSは常にLiuらの手法以下の頂点数を与える [Nacher & Akutsu: Sci. Rep. 2013]

必須・冗長頂点の計算 Jiaらにより提案された必須および冗長頂点 [Jia et al.: Nat. Comm. 2013] の概念をMDSに適用（⇐MDSは一意とは限らない） 必須頂点: すべてのMDSにおいて出現 冗長頂点: どのMDSにも出現しない 必須頂点は単なるMDS頂点より重要性が高いと考えられる [Nacher & Akutsu: J. Comp. Net. 2015]

ロバストMDS ロバストMDS (RMDS): 各頂点がC個以上の頂点によりカバーされる (C=1 ⇒ MDS) RMDSサイズは最小次数が D-C+1のMDSサイズとオーダーが一致 [Nacher & Akutsu: PRE, 2015]

Molnarらによる研究 次数カットとMDSサイズの関連性 [Sci. Rep. 2013]

結論

既存結果と矛盾しない理由 Liu et al. 提案手法（MDS法） Driver node の値のみが制御可能と仮定 ⇒ 次数 k の頂点は、k 個の driver nodes に相当

結論 γ<2 であれば、MDSのサイズは小さい(o(n)) ⇒ 非一様性の高いネットワーク（heterogeneous network）は制御が比較的容易 その傾向をシミュレーション解析およびデータベース解析により検証 人工ネットワーク(e.g., mobile networks and computer networks) では接続辺の個別な制御が可能であると思われるので、この結果が有効である可能性 しかし、生体内ネットワークではその仮定が成立しない 今後の課題 生体内ネットワークの制御を容易とする理論的枠組みの構築 MDSサイズのより精緻な解析