(57)【要約】　　　（修正有）【課題】従来の蛋白質相互作用データの三次元表示方法は、処理が遅い、コンポーネントの選択、保存ができない、視覚化が十分でないなど、使い勝手が悪く、これを改善する。【解決手段】蛋白質相互作用データの特性を踏まえて蛋白質相互作用を三次元空間に描く新しいフォースダイレクトレイアウトアルゴリズムを提案する。より詳細には、ノードを相互作用特性によって三グループに分類して視覚化することによって、従来のアルゴリズムよりはるかに速く大規模の蛋白質相互作用データを明確で美的に優れたグラフに視覚化する技法を提供する。【選択図】　　　図１
2004118818.tif 000002
【特許請求の範囲】
【請求項１】
蛋白質相互作用データを視覚化するために蛋白質をノード（ｎｏｄｅ）として蛋白質間相互作用をエッジ（ｅｄｇｅ）とするグラフを生成する蛋白質相互作用ネットワークの視覚化技法において、次数（ｄｅｇｒｅｅ）が１の最終ノードの集合を第１グループと定義し、上記第１グループのノードを除外した後、切断頂点（ｃｕｔｖｅｒｔｅｘ）によって分離されるサブグラフ中で個数の少ないノードを含むサブグラフに属するノードの集合を第２グループと定義した後、上記第１グループと上記第２グループに属するノードを除外した残りのノードの集合を第３グループと定義するグループ化段階、上記各グループ内のノード間の最短経路、上記第１グループノードと上記第２グループノード間の最短経路、上記第１グループノードと上記第３グループノード間の最短経路、上記第２グループノードと上記第３グループノード間の最短経路を計算する最短経路計算段階及び、上記計算された最短経路を使用するスプリングフォース（ｓｐｒｉｎｇ−ｆｏｒｃｅ）レイアウト技法を適用して、上記第３グループのノードを球体の中央に配置し、上記第２グループのノードを上記第３グループの外郭部分に配置した後、上記第１グループのノードを上記第２グループと上記第３グループの外郭部分に配置するレイアウト段階を含むことを特徴とする蛋白質相互作用ネットワークの分割視覚化技法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、蛋白質相互作用データを３次元グラフに視覚化する新しい技法に関するものである。特に蛋白質ノードを三つのグループに分類して大規模の蛋白質相互作用データを明確で美的に優れたグラフに視覚化する技法に関するものである。
【０００２】
【従来の技術】
蛋白質相互作用データは、その容量が予測できない程度に多きくなってきており、テキストファイルやデータベース形態で提供される。データの容量が大規模であるため相互作用する蛋白質の長いリストより、グラフで表現することが理解しやすいために蛋白質相互作用ネットワークの視覚化に対する研究が活溌に進められている。
【０００３】
しかし、蛋白質相互作用データは無方向（ｕｎｄｉｒｅｃｔｅｄ）グラフに視覚化した時、次のような特性を持つ傾向がある。第一に、グラフに視覚化するとエッジ交差（ｅｄｇｅ　ｃｒｏｓｓｉｎｇ）が多い複雑な非平面グラフになる。２次元グラフでは、このエッジの交差を除去出来ない。第二に、各蛋白質が相互作用する回数がとても多様なため、次数（ｄｅｇｒｅｅ）が高いノードと次数が低いノードを同時に含むグラフになる。第三に、複数個の連結コンポーネント（ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔ）で構成された分離グラフ（ｄｉｓｃｏｎｎｅｃｔｅｄ　ｇｒａｐｈ）になる。　例えば、ＭＩＰＳ遺伝的相互作用データ（ｈｔｔｐ：／／ｍｉｐｓ．ｇｓｆ．ｄｅ／ｐｒｏｊ／ｙｅａｓｔ／ｔａｂｌｅｓ／ｉｎｔｅｒａｃｔｉｏｎ／）は、１１３個の連結グラフを持つようになる。第四に、ソースノード（ｓｏｕｒｃｅ　ｎｏｄｅ）とターゲットノード（ｔａｒｇｅｔ
ｎｏｄｅ）が一致するエッジである自己ループ（ｓｅｌｆ−ｌｏｏｐ）を多く含む。
【０００４】
上記特性のため、従来のグラフドロー（ｄｒａｗｉｎｇ）道具は、速度が遅すぎ多くのデータでインタラクティブ（ｉｎｔｅｒａｃｔｉｖｅ）な作業をしにくく、エッジ交差が多すぎ繁雑なグラフを描いたり、データの変更修正しにくい静的グラフを生成する為、蛋白質相互作用の視覚化に使用するには難点があった。
【０００５】
弛緩（ｒｅｌａｘａｔｉｏｎ）アルゴリズムに基づいて蛋白質相互作用を視覚化する為にＪＡＶＡアプレットプログラムが開発され、Ｙ２Ｈ（Ｙｅａｓｔ　ｔｗｏ−ｈｙｂｒｉｄ）データでテストされたことがあります。このプログラムは、全ての蛋白質相互作用データがＨＴＭＬソースのアプレットプログラムにパラメーターで提供されなければならず。ウィンドウをキャプチャーすること以外には、視覚化されたグラフを保存（ｓａｖｅ）する方法がなく、ウィンドウからキャプチャーされたイメージは、静的イメージであり一般的に質が低く、データ変更を反映させた改良または修正が出来ない。また、ユーザ（ｕｓｅｒ）がノードを移動できるが、後で使用する為に特定蛋白質を含んだ連結コンポーネントを選択または保存することが出来ない。
【０００６】
一方、多くの蛋白質相互作用視覚化作業に固有のアルゴリズムまたはプログラムが使用されないで、一般用途のドロー道具が使用されている。例えば、ＰＳＩＭＡＰは、Ｙ２ＨデータとＤＩＰデータを比較することによって蛋白質ファミリー間の相互作用を図示する。これは、トムソーヤソフトウェア（ｈｔｔｐ：／／ｗｗｗ．ｔｏｍｓａｗｙｅｒ．ｃｏｍ／）によって描いた後、エッジ交差を除去する為に多くの手作業を経て修正されたものである。グラフを描く観点から見ると、ＰＳＩＭＡＰは静的イメージであり改善されなければならない点が多い。ワシントン大学のある研究チームは、また異る一般用途のドロー道具であるＡＧＤ（ｈｔｔｐ：／／ｗｗｗ．ｍｐｉｓｂ．ｍｐｇ．ｄｅ／ＡＧＤ／）を使用して、Ｙ２Ｈデータを視覚化した。ＡＧＤが強力な道具であるとは言え、一般用途のドロー道具であるため蛋白質相互作用研究に必要な機能を提供することは出来ない。
【０００７】
【発明が解決しようとする課題】
本発明は、上記問題点を解決する為に、上述した蛋白質相互作用データの特性を踏まえて蛋白質相互作用を３次元空間に描く新しいフォース−ダイレクト（ｆｏｒｃｅ−ｄｉｒｅｃｔｅｄ）レイアウトアルゴリズムを提案することを目的とする。より詳細には、ノードを相互作用特性によって３グループに分類して視覚化することによって、従来のアルゴリズムよりはるかに速く大規模の蛋白質相互作用データを明確で美的に優れたグラフに視覚化する技法を提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明は、上記目的を解決する為に、蛋白質相互作用データを視覚化するために蛋白質をノードとして蛋白質間相互作用をエッジとするグラフを生成する蛋白質相互作用ネットワークの視覚化技法において、次数が１の最終ノードの集合を第１グループと定義し、上記第１グループのノードを除外した後、切断頂点（ｃｕｔｖｅｒｔｅｘ）によって分離されるサブグラフ中で個数の少ないノードを含むサブグラフに属するノードの集合を第２グループと定義した後、上記第１グループと上記第２グループに属するノードを除外した残りのノードの集合を第３グループと定義するグループ化段階；　上記各グループ内のノード間の最短経路、上記第１グループノードと上記第２グループノード間の最短経路、上記第１グループノードと上記第３グループ　ノード間の最短経路、上記第２グループノードと上記第３グループノード間の最短経路を計算する最短経路計算段階；及び上記計算された最短経路を使用するスプリング−フォース　（ｓｐｒｉｎｇ−ｆｏｒｃｅ）レイアウト技法を適用して、上記第３グループのノードを球体の中央に配置し、上記第２グループのノードを上記第３グループの外郭部分に配置した後、上記第１グループのノードを上記第２グループと上記第３グループの外郭部分に配置するレイアウト段階；を含むことを特徴とする蛋白質相互作用ネットワークの分割視覚化技法を提供する。
【０００９】
上述したように、多くのフォース−ダイレクトアルゴリズムの共通的な問題は、大きなグラフを処理する時に、とても時間がかかることである。それで、本発明では、ノードをそれらの相互作用特性を基礎に３グループに分けるアルゴリズムを提案することによって、実行速度を向上させる。本発明で提案するレイアウトは、２次元グラフを描くカマダ−カワイ（Ｋａｍａｄａ　＆　Ｋａｗａｉ）アルゴリズムの拡張である。このアルゴリズムは、３次元グラフの描写だけではなく、アルゴリズムの効率及び結果を改善するために修正された。
【００１０】
ノードのグループ化をまず詳しく見てみることにする。以下には、第１グループ、第２グループ、第３グループを各々　Ｖ１、Ｖ２、Ｖ３と表記する。
【００１１】
蛋白質相互作用データは、無方向（ｕｎｄｉｒｅｃｔｅｄ）グラフＧ＝（Ｖ，Ｅ）に視覚化され、ここで　Ｖは蛋白質をＥは蛋白質間相互作用を示す。ノードｖｉの次数（ｄｅｇｒｅｅ）はｄｅｇ（ｖｉ）で表示されるエッジの数である。ｖｉ＝ｖｊであるエッジｅ＝（ｖｉ、ｖｊ）は、セルフループであり、グラフＧの切断頂点（ｃｕｔｖｅｒｔｅｘ）は、除去時Ｇを分離（ｄｉｓｃｏｎｎｅｃｔ）させるノードのことを言う。グラフＧでパス（ｐａｔｈ）は、Ｇの個別ノードのシーケンス（ｖ１、ｖ２、ｖ３，．．．、ｖｎ）である。ここで、（ｖｉ、ｖｉ＋１）　∈　Ｅ、１≦ｉ≦ｎ−１である。
【００１２】
本発明では、ノードＶを三つの排他的（ｅｘｃｌｕｓｉｖｅ）で完全な（ｅｘｈａｕｓｔｉｖｅ）グループに分離する。これら３グループは、次のように定義される。ｉ）グループＶ１は最終ノード、つまり次数が１のノードの集合である。ｉｉ）グループＶ２はＶ１のノードを除外したノード中で、切断頂点　（ｃｕｔｖｅｒｔｅｘ）によって分離されるサブグラフ中の個数の少ないノードを含むサブグラフに属するノードの集合である。　ｉｉｉ）グループＶ３はＶ１やＶ２のメンバーではないノードで構成される。
【００１３】
図１は、分割されたグラフの一例として、グラフＧ＝（Ｖ、Ｅ）のノードが３グループに分離されていることが見られる。Ｖ１には６個のノードが属しており、これらは、三つのサブ−グループ（Ｖ１＝｛｛ｖ１｝，｛ｖ５、ｖ９、ｖ１０｝，｛ｖ３１、ｖ３２｝｝）に分離され、サブ−グループは一つのとなりのノードを共有する。
【００１４】
図１において、二つのサブ−グループＳ１＝｛ｖ０、ｖ７｝とＳ２＝｛ｖ２９、ｖ３０｝は、切断頂点ｖ１１を共有するので、Ｖ２の一つのサブ−グループに統合される。サブ−グループＳ３＝｛ｖ２４、ｖ２６、ｖ２７｝とＳ４＝｛ｖ２、ｖ２０、ｖ２１、ｖ２２、ｖ２３、ｖ２４、ｖ２６、ｖ２７｝は切断頂点を共有しない。これはＳ３の切断頂点はｖ２であり、Ｓ４の切断頂点はｖ２５であるためである。しかし、Ｓ３の切断頂点がＳ４に属するためＳ３も切断頂点をｖ２５とするＶ２のサブ−グループにみなされる。
【００１５】
各グループのノードは、Ｖ１、Ｖ２、Ｖ３の順に発見される。まず、一つの隣ノードを持ったノードがＶ１に分類された後、Ｖ１のノードは共有する隣ノードによってサブ−グループに分けられる。次は、Ｖ−Ｖ１からＶ２のノードを発見し、残りノードは全てＶ３を構成するようになる。
【００１６】
Ｖ２に属するノードは、Ｖ１を探し出した後、図２に簡略に記述されたＦｉｎｄＣｕｔｖｅｒｔｅｘという発見アルゴリズムによって決定される。このアルゴリズムの初期入力は、Ｖ−Ｖ１のノードであり、各入力ノードが切断頂点であるかどうかが検査される（３行）。Ｐをｖｉと開始ノード間の経路にあるノードの集合、Ｐ’を上記経路に無いノードの集合とし、ＰとＰ’中どちら側も空集合でなければ、ノードｖｉが切断頂点でありループは残りノードに対して反復実行される。ＰとＰ’中さらに小さい集合に属するノードがＶ２に含まれる（図３の１１−１７行）。その次に、Ｖ２のノードはそれらの切断頂点に基づきサブ−グループに分離され、上記サブ−グループが同一な切断頂点を持った場合は一つに統合される。Ｖ１とＶ２を決定した後、残った全てのノードはＶ３を構成するようになる。したがって、Ｖ３は蛋白質相互作用データの双方連結（ｂｉｃｏｎｎｅｃｔｅｄ）サブグラフ（切断頂点がない連結グラフ）に該当する（但、全てのノードが一列に連結されている特殊なグラフの場合には、Ｖ３は双方連結サブグラフではない）。
【００１７】
次に、本発明で提案する３次元グラフのフォース−ダイレクト（ｆｏｒｃｅｄ−ｄｉｒｅｃｔｅｄ）レイアウトについて説明する。
本発明が基礎としているカマダとカワイのアルゴリズムは、エネルギーが地域的に最少のドローを求める。本発明によるアルゴリズムは、二ノード間の実際距離がそれらの間の好ましい距離に大略比例するドローを求めることに焦点を合わせている。ｎ個のノードを持ったスプリングシステムのグローバルエネルギーＥは、次の数式１によって定義される。
【００１８】
【数１】
2004118818.tif 000003
【００１９】
式中、ｋｉｊはスプリングの剛性度（ｓｔｉｆｆｎｅｓｓ）パラメーター、ｐｉはノードｖｉの位置、ｌｉｊはｖｉとｖｊを連結するスプリングの長さである。
【００２０】
本発明のアルゴリズムは、スプリングシステムの位置エネルギーを最小化するために各頂点（ｖｅｒｔｅｘ）ｖｍに対して位置ｐｍ＝（ｘｍ、ｙｍ、ｚｍ）を求める。次に数式２のようにＥを各変数ｘｍ、ｙｍ、ｚｍで部分微分した値が０の時、位置エネルギーが最少になる。ここで、３｜Ｖ｜＝　３ｎ個の方程式集合が生じる。
【００２１】
【数２】
2004118818.tif 000004
【００２２】
カマダとカワイのアルゴリズムでは、他の全てのノードを固定させたままエネルギーを最小化する位置に一つのノードを移動する。移動するノードには最も大きな力（ｆｏｒｃｅ）が与えられるノード、つまり全てのｖｍ（∈Ｖ）に対して次の数式３の値が最大のものが選択される。
【００２３】
【数３】
2004118818.tif 000005
【００２４】
しかし、このような接近方式によれば、好ましくないグラフの生成を行なったり、大規模の蛋白質相互作用に対しては非常に多くの時間が所要される場合がしばしば発生する。したがって、本発明によるアルゴリズムには、現在位置と以前の位置間の差が一定臨界値以下に下がる時まで、各反復（ループ）において全てのノードを一定レベルに移動する。
【００２５】
初期レイアウトによって、本発明ではノードをランダムに配置する代わりに球体（ｓｐｈｅｒｅ）表面に配置する。したがって、カマダとカワイのアルゴリズムに比べてさらに好ましいドローを生成して均衡をなすグループを持ったグラフを生成することにより速度が速い。
【００２６】
次に、図４及び図５を参照しながら各グループで最短経路を求める方法について説明する。図４及び図５は最短距離を計算するアルゴリズムを記述したもので、各グループＶｉ（ｉ＝１、２、３）に対して全てのノード対間の最短経路が計算される。Ｖ２とＶ１については、各サブ−グループでの最短経路が決定されなければならない。各サブ−グループ内のノード　間の最短経路が計算された後、Ｖ２の各サブ−グループの共有切断頂点を使用してＶ２のノードとＶ３のノード間の最短経路が計算される（図４の９行）。これと同様に、Ｖ１の各サブ−グループの共有隣ノードを利用してＶ１のノードとＶ２及びＶ３のノード間の最短経路が計算される（１４行）。Ｖ１のサブ−グループに対して、全てのノード対間の初期最短経路は２に設定される。これはノードとその共有隣ノード間の距離が１であるためである（図５の３行）。
【００２７】
図６は本発明によるＭＩＰＳ物理的相互作用データ（ＭＩＰＳ−Ｐ）のドローを図示したものである。図６ａは初期レイアウトを図示したもので、１５２６個のノードと２３７２個のエッジを持ち、図６ｂは四角形内のＶ３ノードをドローした後の状態を、図６ｃは四角形内のＶ３及びＶ２のノードをドローした後の状態を、図６ｄは最終的なドローを示している。つまり、Ｖ１、Ｖ２、Ｖ３の順にグループを求める反面、レイアウトの順序はこれと反対である。まず、Ｖ３が球体の中央に配置され、Ｖ２はＶ３の外郭部分に、Ｖ１はＶ２とＶ３の外郭部分に配置される。ノードの位置が固定されたグループは、四角形内に図示されたものである。残りグループに属するノードを固定グループの外郭部分に配置する為に、修正された極座標に移動させる。図６ｂ及び図６ｃで、外部分のノード間のエッジはドローの明確性のために図示しなかった。各グループに属するノードを配置するには、スプリング−フォース（ｓｐｒｉｎｇ−ｆｏｒｃｅ）レイアウト技法を使用し、これよって図４及び図５のアルゴリズムによる最短経路が計算された。
【００２８】
本発明の視覚化技法によるアルゴリズムの計算費用を簡略に分析した結果を詳しく見てみる。３グループが均衡をなすことを考慮すると、本発明のアルゴリズムに対する総時間は
【数４】
2004118818.tif 000006
である。これは各グループにスプリング−エンベダー（ｓｐｒｉｎｇ−ｅｍｂｅｄｄｅｒ）アルゴリズムを適用したためである。本発明によるアルゴリズムの漸近（ｓｙｍｐｔｏｔｉｃ）時間複雑度は、カマダとカワイのアルゴリズムの時間複雑度のＯ（ｎ３）と同一である。しかし、カマダとカワイのアルゴリズムより本発明のアルゴリズムが実質的にずっと速い。Ｖ１とＶ２のノードがあとでサブ−グループに分けられるため、実際実行時間は、均衡あるグループを持ったグラフに比べてさらに減少される。均衡をなしていないグループを持ったグラフ（例えば、切断頂点や最終ノードが少なくＶ３　部分が高いグラフ）に対しては、３グループに分けた効果に限界があるが、蛋白質相互作用においてこのような場合は非常に珍しい。このような事実は、後述する実験結果によって裏付けされる。
【００２９】
本発明では、マイクロソフトＣ＃でアルゴリズムを具現した。本発明によって具現されたプログラムは、運営体制にウィンドウ２０００／ＸＰ／Ｍｅ／９８／ＮＴ４．０等が設置されたどんなＰＣにおいても遂行される。本発明ではブレイン　（ｈｔｔｐ：／／ｗｗｗ．ｉｎｆｏｓｕｎ．ｆｍｉ．ｕｎｉ−ｐａｓｓａｕ．ｄｅ／ＧＤ２００１／ｇｒａｐｈＣ／ｂｒａｉｎ．ｇｍｌ）、Ｇｄ２９　（ｈｔｔｐ：／／ｗｗｗ．ｉｎｆｏｓｕｎ．ｆｍｉ．ｕｎｉ−ｐａｓｓａｕ．ｄｅ／ＧＤ２００１／ｇｒａｐｈＡ／ＧＤ２９．ｇｍｌ）、Ｙ２Ｈ、ＭＩＳデータベース（ｈｔｔｐ：／／ｍｉｐｓ．ｇｓｆ．ｄｅ／ｐｒｏｊ／ｙｅａｓｔ／ｔａｂｌｅｓ／ｉｎｔｅｒａｃｔｉｏｎ）の遺伝的相互作用及び物理的相互作用を含めて５つの場合に対してプログラムをテストした。Ｙ２ＨとＭＩＰＳからの蛋白質相互作用データにおいては、最も大きい連結コンポーネントが使用された。
【００３０】
次の表１は、ノードを３グループに分ける段階（Ｐ）、各グループで最短経路を求める段階　（ＳＰ）、レイアウト及びドロー段階（ＬＤ）の実行時間を示したものである。ブレイン（Ｂｒａｉｎ）とＧｄ２９の場合は、データ集合の大きさとＶ３の相対的な大きさが、他の蛋白質相互作用データのものとは異る。ブレインの場合は、総３３個のノード中で２８個のノード（８４．８％）が　Ｖ３に含まれ、Ｇｄ２９の場合は総１７８個のノード中の１２８個のノード（７１．９％）がＶ３に含まれたが、Ｙ２Ｈ、ＭＩＰＳ−Ｇ及びＭＩＰＳ−Ｐの場合には、ノードの総数に対するＶ３比率が各々２４．９％、４３．５％及び　３７．４％であり５０％以下であった。
【００３１】
【表１】
2004118818.tif 000007
【００３２】
【発明の効果】
実験結果によると、本発明の視覚化技法は、大規模の蛋白質相互作用ネットワークに対して図６に図示したように明確で美的に優れたドローを生成でき、速度面においても他のフォース−ダイレクト（ｆｏｒｃｅｄ−ｄｉｒｅｃｔｅｄ）レイアウトに比べて非常に速い。
従来の他のアルゴリズムとの実験的な比較のために、フルチター及びレインゴールド（Ｆｒｕｃｈｔｅｒ及びＲｅｉｎｇｏｌｄ）のアルゴリズムを利用したパジェ（Ｐａｊｅｋ）とカマダとカワイのアルゴリズムを拡張したアルゴリズムを一緒に実行した。カマダとカワイのアルゴリズムは２次元ドローだけを生成するため、３次元ドローを生成するように拡張して比較したものである。次の表２は、上記５種類のテストケースに対してペンティアムＩＩ２９９Ｍｈｚプロセッサーで本発明のアルゴリズム、カマダとカワイの拡張アルゴリズム、そしてフルチター及びレインゴールド（Ｆｒｕｃｈｔｅｒ及びＲｅｉｎｇｏｌｄ）のアルゴリズム、パジェ（Ｐａｊｅｋ（Ｆ−Ｒ））の実行時間を示したものである。表２に示したように、本発明による分割方法によって計算時間が、最大１／５１まで大きく減少された。また、図７は上記３アルゴリズムの実行時間を比較したグラフである。本発明によるアルゴリズムは、大きさが大きいグラフとＶ３の比率があまり大きすぎないグラフに対してさらに効率的であることが分かった。
【表２】
2004118818.tif 000008
【図面の簡単な説明】
【図１】分割されたグラフの例を図示した図である。
【図２】Ｖ２のノードを決定する発見アルゴリズムのＦｉｎｄＣｕｔｖｅｒｔｅｘを記述した図である。
【図３】図２のアルゴリズムから呼出だされたもので、ノードが切断頂点であるかどうかを検査するＩｓＣｕｔｖｅｒｔｅｘアルゴリズムを記述した図である。
【図４】各グループの全てのノード対間の最短経路を求めるアルゴリズムを記述した図である。
【図５】図４のアルゴリズムで呼出されるもので、各サブ−グループ内の全てのノード対間の最短経路を求めるアルゴリズムを記述した図である。
【図６】ＭＩＰＳ　物理的相互作用データのドロー過程を図示した図である。
【図７】三つのグラフドローアルゴリズムの実行時間を比較したグラフである。
【図１】
2004118818.tif 000009
【図２】
2004118818.tif 000010
【図３】
2004118818.tif 000011
【図４】
2004118818.tif 000012
【図５】
2004118818.tif 000013
【図６】
2004118818.tif 000014
【図７】
2004118818.tif 000015