(57)【要約】【課題】  蛋白質相互作用データの特性を踏まえて蛋白質相互作用を3次元空間に描く新しいフォース-ダイレクト(force-directed)レイアウトアルゴリズムを提案すること。【解決手段】  本発明は、ノードを相互作用特性によって3グループに分類して視覚化することによって、従来のアルゴリズムよりはるかに速く大規模の蛋白質相互作用データを明確で美的に優れたグラフに視覚化する技法を提供する。【選択図】      図１
2005285130.tif 000002
【特許請求の範囲】
【請求項１】
蛋白質相互作用データを視覚化するために蛋白質をノード(node)として蛋白質間相互作用をエッジ(edge)とするグラフを生成する蛋白質相互作用ネットワークの視覚化技法において、次数(degree)が1の最終ノードの集合を第1グループと定義し、上記第1グループのノードを除外した後、切断頂点(cutvertex)によって分離されるサブグラフ中で個数の少ないノードを含むサブグラフに属するノードの集合を第2グループと定義した後、上記第1グループと上記第2グループに属するノードを除外した残りのノードの集合を第3グループと定義するグループ化段階、上記各グループ内のノード間の最短経路、上記第1グループノードと上記第2グループノード間の最短経路、上記第1グループノードと上記第3グループノード間の最短経路、上記第2グループノードと上記第3グループノード間の最短経路を計算する最短経路計算段階及び、上記計算された最短経路を使用するスプリングフォース(spring-force)レイアウト技法を適用して、上記第3グループのノードを球体の中央に配置し、上記第2グループのノードを上記第3グループの外郭部分に配置した後、上記第1グループのノードを上記第2グループと上記第3グループの外郭部分に配置するレイアウト段階を含むことを特徴とする蛋白質相互作用ネットワークの分割視覚化技法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、蛋白質相互作用データを3次元グラフに視覚化する新しい技法に関するものである。特に蛋白質ノードを三つのグループに分類して大規模の蛋白質相互作用データを明確で美的に優れたグラフに視覚化する技法に関するものである。
【背景技術】
【０００２】
蛋白質相互作用データは、その容量が予測できない程度に多きくなってきており、テキストファイルやデータベース形態で提供される。データの容量が大規模であるため相互作用する蛋白質の長いリストより、グラフで表現することが理解しやすいために蛋白質相互作用ネットワークの視覚化に対する研究が活溌に進められている。
【０００３】
しかし、蛋白質相互作用データは無方向(undirected)グラフに視覚化した時、次のような特性を持つ傾向がある。第一に、グラフに視覚化するとエッジ交差(edge crossing)が多い複雑な非平面グラフになる。2次元グラフでは、このエッジの交差を除去出来ない。第二に、各蛋白質が相互作用する回数がとても多様なため、次数(degree)が高いノードと次数が低いノードを同時に含むグラフになる。第三に、複数個の連結コンポーネント(connected component)で構成された分離グラフ(disconnected graph)になる。  例えば、MIPS遺伝的相互作用データ(http://mips.gsf.de/proj/yeast/tables/interaction/)は、113個の連結グラフを持つようになる。第四に、ソースノード(source node)とターゲットノード(target node)が一致するエッジである自己ループ(self-loop)を多く含む。
【０００４】
上記特性のため、従来のグラフドロー(drawing)道具は、速度が遅すぎ多くのデータでインタラクティブ(interactive)な作業をしにくく、エッジ交差が多すぎ繁雑なグラフを描いたり、データの変更修正しにくい静的グラフを生成する為、蛋白質相互作用の視覚化に使用するには難点があった。
【０００５】
弛緩(relaxation)アルゴリズムに基づいて蛋白質相互作用を視覚化する為にJAVAアプレットプログラムが開発され、Y2H(Yeast two-hybrid)データでテストされたことがあります。このプログラムは、全ての蛋白質相互作用データがHTMLソースのアプレットプログラムにパラメーターで提供されなければならず。ウィンドウをキャプチャーすること以外には、視覚化されたグラフを保存(save)する方法がなく、ウィンドウからキャプチャーされたイメージは、静的イメージであり一般的に質が低く、データ変更を反映させた改良または修正が出来ない。また、ユーザ(user)がノードを移動できるが、後で使用する為に特定蛋白質を含んだ連結コンポーネントを選択または保存することが出来ない。
【０００６】
一方、多くの蛋白質相互作用視覚化作業に固有のアルゴリズムまたはプログラムが使用されないで、一般用途のドロー道具が使用されている。例えば、PSIMAPは、Y2HデータとDIPデータを比較することによって蛋白質ファミリー間の相互作用を図示する。これは、トムソーヤソフトウェア(http://www.tomsawyer.com/)によって描いた後、エッジ交差を除去する為に多くの手作業を経て修正されたものである。グラフを描く観点から見ると、PSIMAPは静的イメージであり改善されなければならない点が多い。ワシントン大学のある研究チームは、また異る一般用途のドロー道具であるAGD(http://www.mpisb.mpg.de/AGD/)を使用して、Y2Hデータを視覚化した。AGDが強力な道具であるとは言え、一般用途のドロー道具であるため蛋白質相互作用研究に必要な機能を提供することは出来ない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、上記問題点を解決する為に、上述した蛋白質相互作用データの特性を踏まえて蛋白質相互作用を3次元空間に描く新しいフォース-ダイレクト(force-directed)レイアウトアルゴリズムを提案することを目的とする。より詳細には、ノードを相互作用特性によって3グループに分類して視覚化することによって、従来のアルゴリズムよりはるかに速く大規模の蛋白質相互作用データを明確で美的に優れたグラフに視覚化する技法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上記目的を解決する為に、蛋白質相互作用データを視覚化するために蛋白質をノードとして蛋白質間相互作用をエッジとするグラフを生成する蛋白質相互作用ネットワークの視覚化技法において、次数が1の最終ノードの集合を第1グループと定義し、上記第1グループのノードを除外した後、切断頂点(cutvertex)によって分離されるサブグラフ中で個数の少ないノードを含むサブグラフに属するノードの集合を第2グループと定義した後、上記第1グループと上記第2グループに属するノードを除外した残りのノードの集合を第3グループと定義するグループ化段階; 上記各グループ内のノード間の最短経路、上記第1グループノードと上記第2グループノード間の最短経路、上記第1グループノードと上記第3グループ ノード間の最短経路、上記第2グループノードと上記第3グループノード間の最短経路を計算する最短経路計算段階;及び上記計算された最短経路を使用するスプリング-フォース (spring-force)レイアウト技法を適用して、上記第3グループのノードを球体の中央に配置し、上記第2グループのノードを上記第3グループの外郭部分に配置した後、上記第1グループのノードを上記第2グループと上記第3グループの外郭部分に配置するレイアウト段階;を含むことを特徴とする蛋白質相互作用ネットワークの分割視覚化技法を提供する。
【発明の効果】
【０００９】
上述したように、多くのフォース-ダイレクトアルゴリズムの共通的な問題は、大きなグラフを処理する時に、とても時間がかかることである。それで、本発明では、ノードをそれらの相互作用特性を基礎に3グループに分けるアルゴリズムを提案することによって、実行速度を向上させる。本発明で提案するレイアウトは、2次元グラフを描くカマダ-カワイ(Kamada & Kawai)アルゴリズムの拡張である。このアルゴリズムは、3次元グラフの描写だけではなく、アルゴリズムの効率及び結果を改善するために修正された。
【発明を実施するための最良の形態】
【００１０】
ノードのグループ化をまず詳しく見てみることにする。以下には、第1グループ、第2グループ、第3グループを各々 V1、V2、V3と表記する。
【００１１】
蛋白質相互作用データは、無方向(undirected)グラフG=(V,E)に視覚化され、ここで Vは蛋白質をEは蛋白質間相互作用を示す。ノードviの次数(degree)はdeg(vi)で表示されるエッジの数である。vi=vjであるエッジe=(vi、vj)は、セルフループであり、グラフGの切断頂点(cutvertex)は、除去時Gを分離(disconnect)させるノードのことを言う。グラフGでパス(path)は、Gの個別ノードのシーケンス(v1、v2、v3,...、vn)である。ここで、(vi、vi+1) ∈ E、1≦i≦n-1である。
【００１２】
本発明では、ノードVを三つの排他的(exclusive)で完全な(exhaustive)グループに分離する。これら3グループは、次のように定義される。i)グループV1は最終ノード、つまり次数が1のノードの集合である。ii)グループV2はV1のノードを除外したノード中で、切断頂点 (cutvertex)によって分離されるサブグラフ中の個数の少ないノードを含むサブグラフに属するノードの集合である。 iii)グループV3はV1やV2のメンバーではないノードで構成される。
【００１３】
図1は、分割されたグラフの一例として、グラフG=(V、E)のノードが3グループに分離されていることが見られる。V1には6個のノードが属しており、これらは、三つのサブ-グループ(V1=｛v1｝,｛v5、v9、v10｝,｛v31、v32｝))に分離され、サブ-グループは一つのとなりのノードを共有する。
【００１４】
図1において、二つのサブ-グループS1=｛v0、v7｝とS2=｛v29、v30｝は、切断頂点 v11を共有するので、V2の一つのサブ-グループに統合される。サブ-グループS3=｛v24、v26、v27｝とS4=｛v2、v20、v21、v22、v23、v24、v26、v27｝は切断頂点を共有しない。これはS3の切断頂点はv2であり、S4の切断頂点はv25であるためである。しかし、S3の切断頂点がS4に属するためS3も切断頂点をv25とするV2のサブ-グループにみなされる。
【００１５】
各グループのノードは、V1、V2、V3の順に発見される。まず、一つの隣ノードを持ったノードがV1に分類された後、V1のノードは共有する隣ノードによってサブ-グループに分けられる。次は、V-V1からV2のノードを発見し、残りノードは全てV3を構成するようになる。
【００１６】
V2に属するノードは、V1を探し出した後、図2に簡略に記述されたFindCutvertexという発見アルゴリズムによって決定される。このアルゴリズムの初期入力は、V-V1のノードであり、各入力ノードが切断頂点であるかどうかが検査される(3行)。Pをviと開始ノード間の経路にあるノードの集合、P'を上記経路に無いノードの集合とし、PとP'中どちら側も空集合でなければ、ノードviが切断頂点でありループは残りノードに対して反復実行される。PとP'中さらに小さい集合に属するノードがV2に含まれる(図3の11-17行)。その次に、V2のノードはそれらの切断頂点に基づきサブ-グループに分離され、上記サブ-グループが同一な切断頂点を持った場合は一つに統合される。V1とV2を決定した後、残った全てのノードはV3を構成するようになる。したがって、V3は蛋白質相互作用データの双方連結(biconnected)サブグラフ(切断頂点がない連結グラフ)に該当する(但、全てのノードが一列に連結されている特殊なグラフの場合には、V3は双方連結サブグラフではない)。
【００１７】
次に、本発明で提案する3次元グラフのフォース-ダイレクト(forced-directed)レイアウトについて説明する。
本発明が基礎としているカマダとカワイのアルゴリズムは、エネルギーが地域的に最少のドローを求める。本発明によるアルゴリズムは、二ノード間の実際距離がそれらの間の好ましい距離に大略比例するドローを求めることに焦点を合わせている。n個のノードを持ったスプリングシステムのグローバルエネルギーEは、次の数式1によって定義される。
【００１８】
【数１】
2005285130.tif 000003
【００１９】
式中、kijはスプリングの剛性度(stiffness)パラメーター、piはノードviの位置、lijはviとvjを連結するスプリングの長さである。 
【００２０】
本発明のアルゴリズムは、スプリングシステムの位置エネルギーを最小化するために各頂点(vertex)vmに対して位置pm=(xm、ym、zm)を求める。次に数式2のようにEを各変数xm、ym、zmで部分微分した値が0の時、位置エネルギーが最少になる。ここで、3｜V｜= 3n個の方程式集合が生じる。
【００２１】
【数２】
2005285130.tif 000004
【００２２】
カマダとカワイのアルゴリズムでは、他の全てのノードを固定させたままエネルギーを最小化する位置に一つのノードを移動する。移動するノードには最も大きな力(force)が与えられるノード、つまり全てのvm(∈V)に対して次の数式3の値が最大のものが選択される。
【００２３】
【数３】
2005285130.tif 000005
【００２４】
しかし、このような接近方式によれば、好ましくないグラフの生成を行なったり、大規模の蛋白質相互作用に対しては非常に多くの時間が所要される場合がしばしば発生する。したがって、本発明によるアルゴリズムには、現在位置と以前の位置間の差が一定臨界値以下に下がる時まで、各反復(ループ)において全てのノードを一定レベルに移動する。
【００２５】
初期レイアウトによって、本発明ではノードをランダムに配置する代わりに球体(sphere)表面に配置する。したがって、カマダとカワイのアルゴリズムに比べてさらに好ましいドローを生成して均衡をなすグループを持ったグラフを生成することにより速度が速い。
【００２６】
次に、図4及び図5を参照しながら各グループで最短経路を求める方法について説明する。図4及び図5は最短距離を計算するアルゴリズムを記述したもので、各グループVi(i=1、2、3)に対して全てのノード対間の最短経路が計算される。V2とV1については、各サブ-グループでの最短経路が決定されなければならない。各サブ-グループ内のノード 間の最短経路が計算された後、V2の各サブ-グループの共有切断頂点を使用してV2のノードとV3のノード間の最短経路が計算される(図4の9行)。これと同様に、V1の各サブ-グループの共有隣ノードを利用してV1のノードとV2及びV3のノード間の最短経路が計算される(14行)。V1のサブ-グループに対して、全てのノード対間の初期最短経路は2に設定される。これはノードとその共有隣ノード間の距離が1であるためである(図5の3行)。
【００２７】
図6は本発明によるMIPS物理的相互作用データ(MIPS-P)のドローを図示したものである。図6aは初期レイアウトを図示したもので、1526個のノードと2372個のエッジを持ち、図6bは四角形内のV3ノードをドローした後の状態を、図6cは四角形内のV3及びV2のノードをドローした後の状態を、図6dは最終的なドローを示している。つまり、V1、V2、V3の順にグループを求める反面、レイアウトの順序はこれと反対である。まず、V3が球体の中央に配置され、V2はV3の外郭部分に、V1はV2とV3の外郭部分に配置される。ノードの位置が固定されたグループは、四角形内に図示されたものである。残りグループに属するノードを固定グループの外郭部分に配置する為に、修正された極座標に移動させる。図6b及び図6cで、外部分のノード間のエッジはドローの明確性のために図示しなかった。各グループに属するノードを配置するには、スプリング-フォース(spring-force)レイアウト技法を使用し、これよって図4及び図5のアルゴリズムによる最短経路が計算された。
【００２８】
本発明の視覚化技法によるアルゴリズムの計算費用を簡略に分析した結果を詳しく見てみる。3グループが均衡をなすことを考慮すると、本発明のアルゴリズムに対する総時間は
【数４】
2005285130.tif 000006
である。これは各グループにスプリング-エンベダー(spring-embedder)アルゴリズムを適用したためである。本発明によるアルゴリズムの漸近(symptotic)時間複雑度は、カマダとカワイのアルゴリズムの時間複雑度のO(n3)と同一である。しかし、カマダとカワイのアルゴリズムより本発明のアルゴリズムが実質的にずっと速い。V1とV2のノードがあとでサブ-グループに分けられるため、実際実行時間は、均衡あるグループを持ったグラフに比べてさらに減少される。均衡をなしていないグループを持ったグラフ(例えば、切断頂点や最終ノードが少なくV3 部分が高いグラフ)に対しては、3グループに分けた効果に限界があるが、蛋白質相互作用においてこのような場合は非常に珍しい。このような事実は、後述する実験結果によって裏付けされる。
【実施例１】
【００２９】
本発明では、マイクロソフトC#でアルゴリズムを具現した。本発明によって具現されたプログラムは、運営体制にウィンドウ2000/XP/Me/98/NT4.0等が設置されたどんなPCにおいても遂行される。本発明ではブレイン (http://www.infosun.fmi.uni-passau.de/GD2001/graphC/brain.gml)、Gd29 (http://www.infosun.fmi.uni-passau.de/GD2001/graphA/GD29.gml)、Y2H、MISデータベース(http://mips.gsf.de/proj/yeast/tables/interaction)の遺伝的相互作用及び物理的相互作用を含めて5つの場合に対してプログラムをテストした。Y2HとMIPSからの蛋白質相互作用データにおいては、最も大きい連結コンポーネントが使用された。
【００３０】
次の表1は、ノードを3グループに分ける段階(P)、各グループで最短経路を求める段階 (SP)、レイアウト及びドロー段階(LD)の実行時間を示したものである。ブレイン（Brain）とGd29の場合は、データ集合の大きさとV3の相対的な大きさが、他の蛋白質相互作用データのものとは異る。ブレインの場合は、総33個のノード中で28個のノード(84.8%)が V3に含まれ、Gd29の場合は総178個のノード中の128個のノード(71.9%)がV3に含まれたが、Y2H、MIPS-G及びMIPS-Pの場合には、ノードの総数に対するV3比率が各々24.9%、43.5%及び 37.4%であり50%以下であった。
【００３１】
【表１】
2005285130.tif 000007
【００３２】
実験結果によると、本発明の視覚化技法は、大規模の蛋白質相互作用ネットワークに対して図6に図示したように明確で美的に優れたドローを生成でき、速度面においても他のフォース-ダイレクト（forced-directed）レイアウトに比べて非常に速い。
従来の他のアルゴリズムとの実験的な比較のために、フルチター及びレインゴールド（Fruchter及びReingold）のアルゴリズムを利用したパジェ（Pajek）とカマダとカワイのアルゴリズムを拡張したアルゴリズムを一緒に実行した。カマダとカワイのアルゴリズムは2次元ドローだけを生成するため、3次元ドローを生成するように拡張して比較したものである。次の表2は、上記5種類のテストケースに対してペンティアムII299Mhzプロセッサーで本発明のアルゴリズム、カマダとカワイの拡張アルゴリズム、そしてフルチター及びレインゴールド（Fruchter及びReingold）のアルゴリズム、パジェ(Pajek(F-R))の実行時間を示したものである。表2に示したように、本発明による分割方法によって計算時間が、最大1/51まで大きく減少された。また、図7は上記3アルゴリズムの実行時間を比較したグラフである。本発明によるアルゴリズムは、大きさが大きいグラフとV3の比率があまり大きすぎないグラフに対してさらに効率的であることが分かった。
【表２】
2005285130.tif 000008
【図面の簡単な説明】
【００３３】
【図１】分割されたグラフの例を図示した図である。
【図２】V2のノードを決定する発見アルゴリズムのFindCutvertexを記述した図である。
【図３】図2のアルゴリズムから呼出だされたもので、ノードが切断頂点であるかどうかを検査するIsCutvertexアルゴリズムを記述した図である。
【図４】各グループの全てのノード対間の最短経路を求めるアルゴリズムを記述した図である。
【図５】図4のアルゴリズムで呼出されるもので、各サブ-グループ内の全てのノード対間の最短経路を求めるアルゴリズムを記述した図である。
【図６】MIPS 物理的相互作用データのドロー過程を図示した図である。
【図７】三つのグラフドローアルゴリズムの実行時間を比較したグラフである。
【図２】
2005285130.tif 000009
【図３】
2005285130.tif 000010
【図４】
2005285130.tif 000011
【図５】
2005285130.tif 000012
【図６】
2005285130.tif 000013
【図７】
2005285130.tif 000014
【図１】
2005285130.tif 000015