ROBIN: アイテム集合を付与した大規模ネットワーク解析による副作用の発見
福崎 睦美

1

(指導教員：瀬々 潤)

まえがき

本研究では薬の副作用を解析する手法の一つとしてRelatiOn Between Items and Network(ROBIN) を提案する．信頼性のある副作用候補を発見するためには，遺伝子ネットワークと遺伝子発現情報を統合した解析が重要である．そこで ROBIN では，遺伝子ネットワー
クをあらわすグラフの頂点 (遺伝子) に遺伝子発現量から得た活性条件のアイテム集合を付与することで，2つの情報を統合する．そして，このグラフから共通するアイテム集合を持つ部分グラフ集合の列挙によって，副作用の出る可能性のあるネットワーク群とその条件を同時に発見する．ROBIN は以下のような手順で構成される．(1) 共通アイテム集合を有する部分グラフの列挙 (2)(1) で列挙した部分グラフを組み合せ，部分グラフ集合を包含関係が無いように列挙する．本研究では，(1) では COPINE[3] を使用し，(2) における効率よい共通アイテム集合を持つ部分グラフ集合の列挙を提案する.
図 1(a) は無向グラフであり，(b) はその各頂点のアイテム集合を表す．ROBIN では結果のネットワークの信頼性を高めるため，共通アイテム数が閾値 θI ，大きさが閾値 θS を満たす部分グラフのみ列挙する．図1 を，θI = 2，θS = 2 で解析した一例が図 2 である．
図 2 において太線で示した二つの部分グラフは {i2 , i3 }という条件で副作用を起こす可能性のあるネットワー
クを表すと言える．
関連研究としては，グラフデータベース解析手法である頻出サブグラフ列挙手法 [1] やデータベース上の遺伝子群の持つアイテム集合からの頻出アイテム集合
マイニング [2] も存在するが，遺伝子ネットワークとアイテムの両方を考慮することはできない．COPINE[3]は，二つのデータベースを統合した解析を可能にするが，連結グラフのみを考慮している.

2v0v1v2v3v4v5v6v7v0v1v2v3v4v5v6v7v8v8(a) 遺伝子ネットワークを表すグラフ{i1 , i2 , i3 }
{i1 , i2 }
{i1 , i2 }
{i2 , i3 , i4 }
{i1 , i2 , i3 }
{i1 , i2 , i3 , i4 }
{i2 , i4 }
{i1 , i2 , i3 }
{i2 , i3 }(b) アイテム集合

図 1: IA graph の例

v0v1v2v3v4v5v6v7v8

図 2: ISS 集合の例:太枠の部分グラフは共通アイテム{i2 , i3 } を持つめる.
定義 2：(ISS 集合列挙問題) G = {G1 , . . . , Gn } を ISSの集合とする. ここで Gi は ISS である. θS をユーザ定義の値とすると，(1) V (Gi )∩V (Gj ) = φ (ただし i と jは異なる), (2) G に隣接する頂点 v に関し I(v) 6⊇ I(G)，(3) |Gi | ≥ θS ，(4) G 内の ISS 以外に θS 以上の大きさの I(G) に関する ISS は存在しない，を全て満たすグラフを ISS 集合と呼ぶ. 本研究ではこの中から，θF 個以上の部分グラフを持ち，θI 以上の大きさのアイテム集合に関連づけられた ISS 集合を列挙する. この問題を，ISS 集合列挙問題と呼ぶ.

3

提案手法

ROBIN では ISS 列挙問題を解くため，閾値を満たす ISS を COPINE によって列挙し，その中から共通するアイテムをもつ ISS 集合を発見する．このとき ISSの全通りの組み合せを調べる必要がある．その方法の一つとして ISS の深さ優先による組み合せがあるが，ISS 数が多い場合，組み合せを探索する木が深くなる．
そこで本手法では，ISS を関連するアイテム集合でグループ化することで，集合の組み合わせを可能にし，高速化する.
定義 3：(陽な ISS 集合と陰な ISS 集合)
ISS に関連したアイテム集合を I とすると ISS 集合 G に関し，I(G) ∈ I の時，G を陽な ISS 集合，それ以外を陰なISS 集合と呼ぶ.

問題設定

本研究で使用する定義を以下に示す．G は非連結でラベルや重みのない無向グラフであり，その各頂点はアイテム集合を持つ．このようなグラフ Gを itemset-associated graph(IA graph) と定義する．
V (G), E(G), I(G) および I(v) は，それぞれ G の頂点集合，G の辺集合, G に含まれるアイテムの種類，v∈V (G) のアイテム集合を表す．|E(G)| は，G の大きさを表す．また，G の部分グラフの中でも重要なのはより大きなグラフであると言えるので，次の ItemsetSharing Graph (ISS) を，G の興味深い部分グラフであるとし，その共通アイテムとともに定義を示す．
定義 1：(ISS)G0 を IA∩ graph G の部分グラフとする．I(G0 ) を I(G0 ) = v∈V (G0 ) I(v) と定義したとき，I(G0 ) をグラフ G0 の共通アイテムとし，I(G0 ) 6=φ かつ，G0 に隣接する全てのノード v 0 についてI(v 0 )6⊇I(G0 ) のとき，G0 を I(G0 ) についての ISS と定義する．

ROBIN では列挙した ISS をアイテム集合に着目してグループ化することで陽な ISS 集合を求める. 次に，陽な ISS 集合を組み合わせることで陰な ISS 集合を求める. ISS のグループ化にはアイテム集合のプレフィックス木を利用する．また，アイテムは添字通りの順序を持つ．
定義 4：(ISS プレフィックス木) TG を木，n をそのノードとする. この木は次の性質を持つ. n はアイテ
ム in と ISS 集合 G(n) を持つ. ni , nj ∈TG のノードとこの ISS を用い，本研究は次の定義の部分グラフを求

79

G0G1G2G3G4G5G6G7G8{i1 , i2 }
{i1 , i3 }
{i1 , i2 }
{i2 , i3 }
{i1 , i2 , i3 }
{i1 , i2 , i4 }
{i1 , i2 , i3 }
{i1 , i3 , i4 }
{i1 , i2 , i3 , i4 }

i3 : G4 , G6
i2 : G0 , G2 , G4 , G6
i1

i3 : G1 , G6 , G7i2

i4 : G8

i4 : G5 , G8
i4 : G7 , G8

i3 : G3 , G4 , G6(b) (a) から作成される ISS プレフィックス木

図 5: 疑似データによる実行結果(a) ISS 集合

図 3: ISS プレフィックス木:太枠のノードが陽な ISS
集合を表す{i1 , i2 , i3 , i4 }{}

{i1 , i2 , i3 }{G4 , G6 }{i1 , i2 , i4 }{G5 , G8 }(a) 硫黄代謝{i1 , i3 , i4 } {i1 , i2 , i3 , i4 }{G7 , G8 }{G8 }図 6: 酵母の実データ解析結果{i1 , i2 }
{i1 , i3 }
{i1 , i4 }{G0 , G2 , G4 , G6 } {G1 , G6 , G7 } {G5 , G7 , G8 }果は図 5 に示した．図 5 は，疑似データ上で頂点数を変化させた場合の実行時間である．比較のため，ISSの単純な深さ優先探索による組み合せの実行時間を計測した．頂点数が増加するほど列挙される ISS 数も増加するため，提案手法が有利になることがわかる．

図 4: 図 3 から作成される ISS 木し，nj が ni の子ノードの時，inj < ini を満たす. ISS
上の根からあるノードまでのパスは，パス上のノードに関連したアイテムの集合からなるアイテム集合を表す. ISS の共有するアイテム集合は全てこの木上の根からのパスで表される. この木を ISS プレフィックス木と呼ぶ.

4.254.1

疑似データによる実験

あとがき

本論文では，遺伝子ネットワークと遺伝子発現量を統合して解析する手法として，無向グラフの頂点にアイテム集合を付与したグラフから複数の部分グラフ間に共通するアイテム集合の列挙アルゴリズム ROBINを提案した．今後の課題としては，ISS の列挙時にアイテムの欠損値を許した枝刈りをする方法や，実データの実行結果の生物学的な解釈を進めていきたい．

定義より，アイテム集合の大きさは単調減少であり枝刈りが可能である. また，ROBIN では新たにノードn0 が作成されるとき，I(n0 ) に関連する全ての ISS をG(n0 ) に加える．図 3 をもとに ISS 木を作成した例を
図 4 に示す．各ノードには，アイテム集合と ISS 集合を示した．θI = 2 の時，灰色のノードは既出のアイテム集合であり，× の子ノードはアイテム集合のサイズが閾値 θI を満たさないため，枝刈りされる．

実行結果

実データによる実験

図 6 は，実データによる実験結果を表す．使用したデータは遺伝子ネットワークのエッジ数が 3,324，各遺伝子の持つ活性化条件 (アイテム) 数の平均が 5.7 となっているデータであり，閾値を θI = 3，
θS = 7 とした．列挙された 3 つのネットワークは共通に {erg2，yhl029c，ERG11(tet promoter)} の条件において活性化している．また，これらのネットワークの機能を KEGG を用いて調べると，(a)，(b)，(c) の何れもアミノ酸代謝に関連する既知のパスウェイと高い相関があり，生物学的な知識と一致する結果が得られた.

これにより，完全一致またはサブセットになるようなアイテム集合に関連した陽な ISS 集合へ高速にアクセスできるようにする．ISS プレフィックス木の例を図3 に示す．図 3(a) は，ISS とそれに関連するアイテム集合を表す．ただし，V (G4 )⊂V (G1 )，V (G5 )⊂V (G0 )，V (G8 )⊂V (G6 ) という包含関係があるとする．
全 ISS 集合に関連するアイテム集合は，ISS 木によって列挙される．
定義 5：(ISS 木) TI を木とし，TI の各ノード n は，アイテム集合 I(n) と ISS 集合 G(n) を持つ．ni , nj ∈TIについて nj が ni の子ノードの時，I(nj ) ⊂ I(ni ) を満たす. この性質を満たす木を ISS 木と呼ぶ．

4(b) バリン，ロイシ (c) アラニン，アスパン，イソロイシン合成 ラギン酸代謝

参考文献[1] X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In ICDM 02, page 721,2002.
[2] J. Han, H. Cheng, D. Xin, and X. Yan. Frequent
pattern mining: Current status and future directions. Data Mining and Knowledge Discovery,
14(1), 2007.

ROBIN の性能の評価のため，疑似データを作成し実験を行った．特に指定しない場合，頂点数 3000，平均次数 10，アイテムの種類 100，平均アイテム集合サイズ 10，解のアイテム集合サイズ |I|=10，解の CCPG
サイズ S=7，解の CCPG 集合サイズ 5，解のパター
ン数 10，閾値 θI = |I| − 1，
θS = S − 1 とする．実行結[3] M. Seki and J. Sese. Identiﬁcation of active biological networks and common expression conditions. In BIBE 08, 2008.

80