評価装置、及び、コンピュータプログラム
【課題】相互に関連を持つデータをその関連の深さとともに把握可能とし、調査対象のデータに関連する他のデータを関連の深いものから取りこぼしなく所望の数だけ抽出する。
【解決手段】クリーク抽出部１２１は、複数のノードと、当該複数のノードそれぞれが関連する他のノードとを示す関係データに基づいて極大クリークを抽出し、ノードの重複割合が所定以上の極大クリークの組み合わせから擬似クリークを生成する。行列作成部１２２は、ノード及び擬似クリークを行及び列に対応させ、ノードが擬似クリークに含まれる場合は対応する要素に１を、他の要素に０を設定した行列を生成し、対応分析部１２３は、生成された行列の対応分析を行い、ノード及び擬似クリークそれぞれのスコアを算出する。抽出対象リスト作成部１２４は、ノードをスコア順に並べた結果から、注目するノードの近傍の他のノードを所定数抽出して出力する。
【解決手段】クリーク抽出部１２１は、複数のノードと、当該複数のノードそれぞれが関連する他のノードとを示す関係データに基づいて極大クリークを抽出し、ノードの重複割合が所定以上の極大クリークの組み合わせから擬似クリークを生成する。行列作成部１２２は、ノード及び擬似クリークを行及び列に対応させ、ノードが擬似クリークに含まれる場合は対応する要素に１を、他の要素に０を設定した行列を生成し、対応分析部１２３は、生成された行列の対応分析を行い、ノード及び擬似クリークそれぞれのスコアを算出する。抽出対象リスト作成部１２４は、ノードをスコア順に並べた結果から、注目するノードの近傍の他のノードを所定数抽出して出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、相互に関連があるデータ群についてデータ間の関連を評価する評価装置、及び、コンピュータプログラムに関する。
【背景技術】
【０００２】
現在、さまざまな分野で行われているデータマイニングにおいて、データ一つ一つが関係するデータ群の中から、ある目的のために、分析を行う対象を絞り込む、という事が行われている。
【０００３】
例えば、ライフサイエンス分野においては、ある疾患に対する遺伝子の関連を見るために、実験により検証を図る遺伝子群の選定が課題にある。コストを要する生物学的実験により検証が図られることから、薬剤開発等に関わるターゲッティングにあたって、必要な遺伝子のとりこぼしがない、最小限の遺伝子セットの取り揃えを用意することが求められる。通常は、文献調査やデータベース（パスウエィデータベース等）の検索により、このような遺伝子群が定められる。しかしながら、現行のパスウェイ（遺伝子から翻訳されたタンパク質の作用の連鎖構造を表す）抽出は、ターゲットを絞った上で、大量の論文類の精読に基づいて行なわれる（例えば、非特許文献１参照）ことから、部分的にのみ得られている状況にある。
【０００４】
また、例えば、企業の（与信等の）評価にあたって、有価証券報告書等に記載される取引先（の業績等）といった関係データを用いた評価を行なう場合、注目企業の取引先企業を調査対象企業群として選定する必要がある。これまでは直接の取引先を、有価証券報告書等のデータベース検索の結果から取得（例えば、特許文献１参照）してリスト化するのが一般的であった。また、関係データのもつグラフ構造を基に所定の指標を算出してスコア付与する方法もある。
【非特許文献１】K. Oda, Y.Matsuoka, A. Funahashi and H. Kitano,“A comprehensive pathway map of epidermal growth factor receptor signaling,” Mol. Syst. Biol., vol. 1, 2005.0010, May 2005.
【特許文献１】特開２００３−０３０４６７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載されるような、従来のデータベースを検索する方法では、遺伝子と、直接関係のある疾患に限定された把握にとどまっていたため、遺伝子そのものの関係などが考慮されないという限界がある。また、遺伝子関係の視覚化を通して属する遺伝子群を把握するもあるが、規模が大きくなると視覚化の了解性が損なわれ、適切に遺伝子群を得ることが困難であった。一方、特許文献１に記載されるような従来の技術では、取引関係を考慮して対象企業群を取得する際に、調査コストに応じて、より関連が強い企業に限定した数の対象企業群を取得することはできなかった。
【０００６】
本発明は、上記の事情に鑑みてなされたものであり、相互に関連を持つデータをその関連の深さとともに把握可能とし、調査対象のデータに関連する他のデータのセットを、関連の深いものから取りこぼしなく所望の数得ることができる評価装置、及び、コンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、本発明は、相互に関連のあるデータ群より抽出される疑似クリークを構成するための関連度の閾値を記憶する記憶部と、複数のノードと、当該複数のノードそれぞれについての他のノードとの関連をエッジとして表す関係データの入力を受ける入力部と、前記入力部に入力された関係データにより示されるグラフにおける極大クリークを抽出し、抽出した極大クリークの全ての組み合わせのうち、前記閾値より大きい関連度を有する極大クリークの組み合わせを選択し、選択した各極大クリークの組み合わせそれぞれについて、当該組み合わせを構成する極大クリークに含まれる前記ノードの和集合からなる擬似クリークを生成して前記記憶部に書き込むクリーク抽出部と、前記クリーク抽出部により生成された各擬似クリークに含まれる前記ノードを前記記憶部から読み出し、それぞれの前記ノード及びそれぞれの前記擬似クリークを各行及び各列に対応させ、かつ、前記ノードが前記擬似クリークに含まれる場合は当該ノード及び当該擬似クリークに対応する行及び列の要素に１を、含まれない場合は対応する行及び列の要素に０を設定した行列を生成して前記記憶部に書き込む行列作成部と、前記行列作成部により生成された前記行列を前記記憶部から読み出し、当該行列の対応分析を行い、前記ノードそれぞれのスコアを算出して前記記憶部に書き込む対応分析部と、前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果を可視化した情報を出力する可視化部と、を備えることを特徴とする評価装置である。
【０００８】
また、本発明は、上述する評価装置において、前記対応分析部は、前記行列の対応分析を行い、前記ノードそれぞれのスコア及び前記擬似クリークそれぞれのスコアを算出して前記記憶部に書き込み、前記可視化部は、前記対応分析部により算出された前記ノードのスコア及び前記擬似クリークのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果、及び、前記擬似クリークを当該擬似クリークのスコア順に並べた結果と、前記ノードそれぞれが属する前記擬似クリークを可視化した情報を出力する、ことを特徴とする。
【０００９】
また、本発明は、上述する評価装置において、前記入力部は、さらに、調査対象のノード及びノード数の入力を受けて前記記憶部に記憶し、前記入力部が入力を受けた前記調査対象のノード及び前記ノード数の情報と、前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べ、この前記ノードをスコア順に並べた結果において、前記調査対象のノードに隣接する他のノードを前記ノード数分特定する抽出対象リスト作成部をさらに備える、ことを特徴とする。
【００１０】
また、本発明は、上述する評価装置において、前記ノードは、他のノードとの関連であるエッジとして、医学・生物学あるいは取引・資本関係における結びつきを持つノードであることを特徴とする。
【００１１】
また、本発明は、評価装置として用いられるコンピュータを、相互に関連のあるデータ群より抽出される疑似クリークを構成するための関連度の閾値を記憶する記憶部、複数のノードと、当該複数のノードそれぞれについての他のノードとの関連をエッジとして表す関係データの入力を受ける入力部、前記入力部に入力された関係データにより示されるグラフにおける極大クリークを抽出し、抽出した極大クリークの全ての組み合わせのうち、前記閾値より大きい関連度を有する極大クリークの組み合わせを選択し、選択した各極大クリークの組み合わせそれぞれについて、当該組み合わせを構成する極大クリークに含まれる前記ノードの和集合からなる擬似クリークを生成して前記記憶部に書き込むクリーク抽出部、前記クリーク抽出部により生成された各擬似クリークに含まれる前記ノードを前記記憶部から読み出し、それぞれの前記ノード及びそれぞれの前記擬似クリークを各行及び各列に対応させ、かつ、前記ノードが前記擬似クリークに含まれる場合は当該ノード及び当該擬似クリークに対応する行及び列の要素に１を、含まれない場合は対応する行及び列の要素に０を設定した行列を生成して前記記憶部に書き込む行列作成部、前記行列作成部により生成された前記行列を前記記憶部から読み出し、当該行列の対応分析を行い、前記ノードそれぞれのスコアを算出して前記記憶部に書き込む対応分析部、前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果を可視化した情報を出力する可視化部、として動作させることを特徴とするコンピュータプログラムである。
【発明の効果】
【００１２】
本発明によれば、遺伝子及び疾患、または、疾患、あるいは、企業等をノードとし、ノード間に相互に関連がある場合に、ノード間の関係をその関連の深さとともに視覚化することが可能となる。よって、視覚的な確認の下で、ノード間の関連を判断することが可能となる。また、ノード数が大量である場合にも、大局的視点からとりこぼすことなく所望の数だけ、調査対象ノードと関連が深いノードの選定が図られることに加え、ハブ的役割をもつノードの関係の把握が可能となる。よって、ノード間の関連を把握したり、調査対象ノードに関連するノードを選定したりする際に、試行錯誤を繰り返すことなく、工数を削減することができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照して本発明の実施の形態の例について説明する。
本発明の一実施形態による評価装置は、例えば、遺伝子及び疾患をノードとし、これらのノード間に関連があるときに無向のエッジがひかれるグラフデータからクリークを全て抽出し、その抽出したクリーク群の行列表現に対して対応分析を行なった結果得られるノードの並び、つまり、遺伝子と疾患の並びから調査対象遺伝子群を選定する。
【００１４】
ここでのグラフとは、グラフ理論において定義されるものであって、いくつかのノード（点、頂点などとも呼ばれる）と、それらのノードの対を両端とする線分であるエッジ（枝、アーク、辺などとも呼ばれる）によって表される。このようなグラフは、図形を表して表現しても良いし、配列の各要素をノードとした配列処理によって表すようにしても良い。
【００１５】
グラフＧのノードの集合をＶおよびエッジの集合をＥとすると、グラフＧはＧ＝（Ｖ，Ｅ）で表される。また、グラフＧにおけるノードの集合Ｖの部分集合ＶＨとエッジの集合Ｅの部分集合ＥＨに対して、どのエッジｋ∈ＥＨ（ｋは部分集合ＥＨの要素を表す）の両端点もＶＨに含まれるとき、グラフＨ＝（ＶＨ，ＥＨ）をグラフＧの部分グラフという。また、すべてのノードの対がエッジで結ばれているグラフを完全グラフという。
【００１６】
そして、グラフＧの部分グラフＱで完全グラフとなっているものをクリーク（あるいは完全部分グラフ）という。なお、このような部分グラフＱのノードの集合をクリークと呼ぶこともある。クリークＱのサイズをノードの個数で定義し、｜Ｑ｜で表す。また、ノードの個数がｎ個のクリークをサイズｎのクリークとも呼ぶ。そして、グラフＧのクリークＱのノードの集合が他のどのクリークのノードの集合にも真に含まれないとき、集合ＱをグラフＧの極大クリークという。
【００１７】
評価装置が対応分析を行なう対象のクリーク群は、極大クリークから生成される擬似クリークからなる。そのため、評価装置は、まず、グラフデータから極大クリークを抽出し、この極大クリークから擬似クリークを生成する。擬似クリークとは、所定の閾値以上の度合でノードを共有する、複数の極大クリークを統合したものである。つまり、擬似クリークは、抽出した極大クリークのうち、一部に重複するノードを含む極大クリーク同士で、その重複するノードが所定の割合を超えるものを一つの集合としたものであり、この集合は上述したクリークの定義をかならずしも満たさないため、擬似的なクリークと呼ばれている。ここでは、擬似クリークを生成するために複数の極大クリークが統合対象であると判断するための条件である、ノードを共有する割合の閾値を、「擬似クリークの閾値」と記載する。例えば、ある２つの極大クリークＡと極大クリークＢについて、（極大クリークＡと極大クリークＢの積集合に含まれるノード数）／（極大クリークＡと極大クリークＢの和集合に含まれるノード数）＞（擬似クリークの閾値）を満たす場合、極大クリークＡと極大クリークＢの和集合が擬似クリークとなる。
【００１８】
また、対応分析とはサンプルとカテゴリ間の関係のデータを対象に、サンプルとカテゴリとの対応付けを図る公知の統計手法である。前提として、１つのサンプルが複数のカテゴリに属してもよい状況で、一般に、その関係データはサンプルおよびカテゴリをそれぞれ行および列に割り当てた行列データ（データ要素は関係ありとなしに応じて１と０で表される）により記述される。対応分析では行の項目と列の項目の相関が最大化されるようなサンプルスコアとカテゴリスコアが行列の固有ベクトルを通して得られる。このスコアにより行と列をソートすることで、対応が考慮されたサンプルとカテゴリの並びが出力される。
【００１９】
図１は、本発明の一実施の形態による評価装置１００の構成を示す図であり、本発明と関係する機能ブロックのみ抽出して示してある。同図において、評価装置１００は、入力部１１０、演算部１２０、記憶部１３０、出力部１４０を備える。
【００２０】
入力部１１０は、どのノードがどのノードと関連するかを示す関係データテーブルの入力を受け、入力された関係データテーブルＨを行列表現にしたデータを記憶部１３０に書き込む。さらに入力部１１０は、各種パラメータの入力データを受け、記憶部１３０に書き込む。パラメータには、擬似クリークの閾値τ、着眼ノードのｉｄ、及び、着眼ノードとして指定されたノードの関連ノードとして抽出対象とするノード数ｍがある。記憶部１３０は、入力部１１０が入力を受けたデータや、演算部１２０における演算処理の途中結果、演算結果のデータを記憶する。出力部１４０は、例えば、ディスプレイやプリンタなどであり、演算結果を出力する。
【００２１】
演算部１２０は、記憶部１３０に記憶されたデータを用いて演算処理を行い、演算結果として、関連が高いノードがより近い距離となるように順にノードを並べたソート結果を可視化した結果と、着眼ノードに関連が高いノードのリストを示す調査対象リストとを得る。演算部１２０は、クリーク抽出部１２１、行列作成部１２２、対応分析部１２３、抽出対象リスト作成部１２４を備える。
【００２２】
クリーク抽出部１２１は、記憶部１３０から行列表現された関係データを読み出して極大クリークを抽出し、擬似クリークの閾値τを用いて、抽出した極大クリークから擬似クリークを生成する。行列作成部１２２は、クリーク抽出部１２１により生成された擬似クリーク群を行列により表現した行列データを生成する。対応分析部１２３は、行列作成部１２２が生成した行列データに基づき対応分析を行なう。抽出対象リスト作成部１２４は、対応分析部１２３による対応分析の結果に基づいて並べ替えられたノードから、着眼ノードのｉｄにより特定されるノードを中心にノード数ｍ分の近傍のノードを読み出して、調査対象リストを生成する。可視化部１２５は、対応分析部１２３による対応分析の結果に基づいて並べ替えられたノード及び擬似クリークを可視化した情報を出力部１４０に出力する。
【００２３】
次に、評価装置１００の処理について説明する。
図２は、図１に示す評価装置１００の入力部１１０における処理フローを示す。同図において入力部１１０は、関係データテーブルＨと、擬似クリークの閾値τ、抽出対象ノード数ｍ、着眼ノードｉｄとの入力を受け、記憶部１３０に書き込む（ステップＳ１１）。このときの関係データテーブルＨは、例えば、前処理によって、評価装置１００とインターネットなどのネットワークを介して接続されるデータベース、例えば、遺伝子変異による疾患に関する情報が提供されているＯＭＩＭ(Online Mendelian Inheritance in Man)データベースから、疾患と遺伝子の関連データを読み出して生成するようにしてもよい。なお、ＯＭＩＭは、ヒトの遺伝病に関するデータベースとしてよく知られている。
【００２４】
図９は、入力部１１０に入力される遺伝子及び疾患の関係データテーブルＨの例を示す図である。同図において、関係データテーブルＨは、遺伝子Ａ１に関係がある遺伝子または疾患が遺伝子Ａ２、疾患Ａ３、…、遺伝子Ａｎであり、遺伝子Ａ２に関係がある遺伝子または疾患が遺伝子Ａ１、…、遺伝子Ａｎであり、疾患Ａ３に関係がある遺伝子または疾患が遺伝子Ａｎであり、遺伝子Ａｎに関係がある遺伝子または疾患が遺伝子Ａ１、遺伝子Ａ２、疾患Ａ３であることが示されている。入力部１１０は、入力された関係データテーブルに含まれる全てのノード、つまり、遺伝子及び疾患を抽出すると、この抽出したノードそれぞれにノードｉｄを割当てる。ここでは、抽出されたｎ個のノードである遺伝子Ａ１、遺伝子Ａ２、疾患Ａ３、…、遺伝子Ａｎに割当てられたノードｉｄをそれぞれＡ１、Ａ２、Ａ３、…、Ａｎとする。以下、割当てられたノードｉｄがＡｋ（ｋ＝１〜ｎ）のノードをノードＡｉと記載する。
【００２５】
図１０は、入力された関係データテーブルＨ（図９）に基づいて入力部１１０が生成した関係データＧを示す。入力部１１０は、関係データテーブルから抽出されたｎ個のノードＡ１〜Ａｎを１〜ｎ行、及び、１〜ｎ列に対応させ、ノード間に関係がある場合には対応する要素に１を、関係がない場合は対応する要素に０を設定した行列データを生成する。つまり、関係データテーブルＨに、ノードＡｉ（ｉ＝１〜ｎ）がノードＡｊ（ｊ＝１〜ｎ、ｉ≠ｊ）に関連があることが設定されている場合には関係データＧのｉ行ｊ列の要素ｇｉｊ及びｊ行ｉ列の要素ｇｊｉに１を、含まれない場合ことを示している場合は関係データＧのｉ行ｊ列の要素ｇｉｊ及びｊ行ｉ列の要素ｇｊｉに０を設定する。なお、行と列が同じノードに対応する関係データＧの要素、つまり、ｉ行ｉ列（ｉ＝１〜ｎ）の要素には０を設定するが、１を設定するようにしてもよい。この関係データＧは、遺伝子及び疾患をノードとし、ある遺伝子または疾患について関連しあう関係をエッジとしたグラフにより表現したデータに相当する。つまり、この関係データＧはグラフＧ＝（Ｖ，Ｅ）（ただし、Ｖはノード、Ｅはエッジ）を表したものである。入力部１１０は、関係データＧとともに、ノードｉｄとノードの名称とを対応付けた情報も記憶部１３０に書き込むものとする。
【００２６】
図３は、演算部１２０の処理フローを示す図である。
まず、クリーク抽出部１２１は、記憶部１３０から関係データＧを読み出すと、極大クリーク全列挙アルゴリズムを適用して、関係データＧにより表現されるグラフから極大クリークを全て抽出して列挙したのち、エッジの接続条件を緩和した擬似クリークを生成して列挙し、記憶部１３０に書き込む（ステップＳ２１）。なお、擬似クリークについては列挙しなくてもよいが、列挙したほうが関係性を大局的に判断することができる。
【００２７】
次に、行列作成部１２２は、ステップＳ２１において列挙された擬似クリーク群を記憶部１３０から読み出し、当該擬似クリーク群に基づいて、擬似クリークｉｄを行に、ノードｉｄを列に対応させ、各擬似クリークを構成するノードに対応するする要素を１、それ以外の要素を０とした行列データＦを生成し、記憶部１３０に書き込む（ステップＳ２２）。
【００２８】
対応分析部１２３は、ステップＳ２２の結果得られた行列データＦを記憶部１３０から読み出し、当該行列データＦに対して対応分析を適用して、第１固有値からの第１成分スコアをノードの並びを示す値として得る（ステップＳ２３）。なお、第２成分以降のスコアをノードの並びを示す値として採用しても良い。
【００２９】
抽出対象リスト作成部１２４は、記憶部１３０から抽出ノード数ｍ、着眼ノードｉｄを読み出し、ステップＳ２３において得られたスコアに基づいてノードを昇順に並べ替え、並べ替えられたノードの並びにおいて、着眼ノードｉｄ、例えば、ある疾患のノードｉｄを中心にして両側ｍ個ずつの近傍のノードｉｄを読み出し、読み出したノードｉｄのリストを生成し、出力部１４０に出力する（ステップＳ２４）。また、可視化部１２５は、ステップＳ２３において得られたスコアに基づいてノード及び擬似クリークそれぞれを昇順に並べ替え、並びかえられたノード及び擬似クリークの並びと、各ノードがいずれの擬似クリークに含まれるかを可視化した情報を生成して、出力部１４０に出力する（ステップＳ２５）。
【００３０】
図４は、図３のステップＳ２１の詳細な処理フローを示す図である。
同図において、クリーク抽出部１２１は、記憶部１３０から関係データＧ、及び、擬似クリークの閾値τを読み出す（ステップＳ２１１）。クリーク抽出部１２１は、関係データＧにより示されるグラフから極大クリークを抽出する（ステップＳ２１２）。極大クリークの抽出方法には、様々なものがあるが、例えば、以下の方法で行なう。
【００３１】
まず、クリーク抽出部１２１は、関係データＧにより示される、分析対象となる全てのノードＡ１〜Ａｎから、任意のノードＡｉ（ｉ＝１〜ｎ）を１つ選択する。クリーク抽出部１２１は、関係データＧにより示されるノード間の関係から、選択したノードＡｉとリンクを持つノードのリストを作成し、サイズ２のクリークのリストを登録した抽出経過テーブルを記憶部１３０へ書き込む。例えば、関係データＧのｉ行において要素の値が１である列を特定し、特定した列に対応するノードがノードＡｉとリンクを持つノードして抽出され、クリークサイズ「２」とともに抽出経過テーブルに登録される。この際、クリーク抽出部１２１は、集合として同値の組み合わせを抽出経過テーブルから除去する。
【００３２】
次にクリーク抽出部１２１は、関係データＧから、抽出経過テーブルにサイズ２のリストとして記載されたノードと互いにリンクを持つノードのリストを作成し、サイズ３のクリークとして抽出経過テーブルに記憶する。例えば、サイズ２のクリークが、ノードＡｉ、ノードＡｋとからなる場合、関係データＧのｉ行及びｋ列において要素の値が１である列を特定し（ｉ列及びｋ列を除く）、特定した列に対応するノードがノードＡｉ、ノードＡｋとリンクを持つノードして抽出され、クリークサイズ「３」とともに抽出経過テーブルに登録される。この際も、クリーク抽出部１２１は、集合として同値の組み合わせを抽出経過テーブルから除去する。このとき、新たに登録したクリークサイズ「３」のクリークの部分集合となるクリーク「２」のノードの組み合わせも削除されることになる。当該処理を、サイズ４、サイズ５と新たなリンクが見つからなくなるまで繰り返すことにより、選択したノードに関する極大クリークが抽出され、抽出経過テーブルに登録される。
【００３３】
クリーク抽出部１２１は、上記処理を、全てのノードＡ１〜Ａｎについて繰り返すことにより、完全グラフとなる全ての極大クリークを抽出して抽出経過テーブルに登録し、最終的な抽出経過テーブルを生成すると、各極大クリークに極大クリークｉｄを割当てる。クリーク抽出部１２１は、抽出経過テーブルに割当てた極大クリークｉｄの情報を追加し、極大クリーク出力結果テーブルとして記憶部１３０に書き込む。
なお、上記の方法のほか、極大クリーク全列挙アルゴリズムの公知技術であるＣＬＩＱＵＥＳ法などを用いても構わない。ＣＬＩＱＵＥＳ法については、例えば、以下の論文、E. Tomita, A. Tanaka and H. Takahashi : The worst-case time complexity for generating all maximal cliques and computational experiments, Teoret. Comput. Sci. 363, pp. 28-42, 2006.に記載されている。
【００３４】
図１１は、ステップＳ２１２において生成された極大クリーク出力結果テーブルの例を示す図である。同図において、極大クリーク出力結果テーブルには、抽出した極大クリークを特定する識別情報としての極大クリークｉｄと、当該極大クリークのサイズと、当該極大クリークを構成するノードを示す構成要素とが対応づけられて登録されている。ここでは、抽出された極大クリークの数をＣ’ｎｕｍとしている。
同図において、極大クリークｉｄ＝１により特定される極大クリークは、サイズが４であり、遺伝子Ａ１、遺伝子Ａ２、疾患Ａ３、遺伝子Ａ８からなることが示されている。なお、構成要素は、ノードｉｄにより示されることでもよい。以下、極大クリークｉｄ＝ｋにより特定される極大クリークを極大クリークＣ’ｋと記載する。抽出された極大クリークの集合、つまり、｛Ｃ’１，…，Ｃ’Ｃ’ｎｕｍ｝を極大クリーク族Ｃ’とする。
【００３５】
次に、クリーク抽出部１２１は、抽出された極大クリーク群から擬似クリークを抽出する（ステップＳ２１３）。ここでは、クリーク抽出部１２１は、極大クリーク出力結果テーブル（図１１）に登録されている極大クリークから、下記の擬似クリークの条件に当てはまる関連度の高い極大クリークの組み合わせＰＣ（Ｃ’）を抽出するとともに、各ＰＣ（Ｃ’）に含まれるノード数をクリークサイズとして算出する。例えば、擬似クリークの抽出は以下の方法で行う。
【００３６】
まず、クリーク抽出部１２１は、極大クリーク出力結果テーブルにより示される、ステップＳ２２２において抽出された極大クリークＣ’１〜Ｃ’Ｃ’ｎｕｍについて、２以上の極大クリークからなる全ての組み合わせを生成し、テーブルとして記憶部１３０に記憶しておく。次に、クリーク抽出部１２１は、当該テーブルに記憶した極大クリークの組み合わせＰＣ（Ｃ’）を順に個別に取り出し、その組み合わせを構成する極大クリークそれぞれに含まれるノードをクリーク出力結果テーブル（図１１）から読み出すと、本手法では関連度として、式（１）により重複度overlap()を評価値として算出する。この重複度は０以上１以下の値をとり、値が大きくなるほど重複の度合いが大きくなる。この算出した評価結果が、擬似クリークの閾値τを超えた極大クリークの組み合わせＰＣ（Ｃ’）から擬似クリークを生成する。つまり、クリーク抽出部１２１は、式（２）に示すように、極大クリークＣ’１，Ｃ’２，…，Ｃ’Ｃ’ｎｕｍの中から２以上を用いた極大クリークの組み合わせＰＣ（Ｃ’）のうち、重複度overlap(Ｃ’)が擬似クリークの閾値τを越えるような極大クリークの組み合わせＰＣ（Ｃ’）の和集合を、擬似クリークとして定義する。さらに、クリーク抽出部１２１は、極大クリークの組み合わせＰＣ（Ｃ’）を構成する各極大クリークのノードの和集合の個数から当該擬似クリークのサイズを定める。クリーク抽出部１２１は、生成した当該擬似クリークに付与したクリークｉｄと、当該擬似クリークに含まれるノードを擬似クリーク出力結果テーブルに登録する。この擬似クリーク出力結果テーブルは記憶部１３０に記憶される。
下記の式において、∩はクリークの積集合を、∪はクリークの和集合を、｜ ｜はノードの個数を、ｍｉｎは最小値を表す。また、τは重複度を制御する閾値である。
【００３７】
【数１】
【００３８】
なお、上記の方法のほか、公知技術であるエッジ密度に基づく擬似クリーク抽出方法などを用いても構わない。この場合、関連度としてエッジ密度を採用するが、このエッジ密度に基づく擬似クリーク抽出方法については、例えば、以下の論文、T. Uno, “An efficient algorithm for enumerating pseudo cliques,” Lecture Notes in Computer Science, vol. 4835, pp. 402-414, 2007.に記載されている。
【００３９】
なお、擬似クリーク出力結果テーブルは、例えば図１１に示す極大クリーク出力結果テーブルと同じ形式のテーブルであり、擬似クリークを特定する番号であるクリークｉｄと、当該擬似クリークのサイズと、当該擬似クリークの構成要素であるノードの識別情報とが登録される。ここでは、抽出された擬似クリークの数をＣｎｕｍとする。以下、クリークｉｄ＝ｋにより特定される擬似クリークを擬似クリークＣｋと記載する。よって、抽出された擬似クリーク群は、擬似クリークＣ１，Ｃ２，…，ＣＣｎｕｍとなる。
【００４０】
図５は、演算部１２０の行列作成部１２２における処理フローを示す図である。
同図において、行列作成部１２２は、図４の処理によりクリーク抽出部１２１が生成した擬似クリーク出力結果テーブルを記憶部１３０から読み出す（ステップＳ２２１）。行列作成部１２２は、読み出した擬似クリーク出力結果テーブルを参照して、各ノードがどの擬似クリークに属しているかを示す行列データＦを生成し、記憶部１３０に書き込む（ステップＳ２２２）。
【００４１】
図１２は、ステップＳ２２２において生成された行列データＦの例を示す図である。行列作成部１２２は、ノードＡ１〜ノードＡｎそれぞれを行列データＦの１〜ｎ行に、擬似クリークＣ１〜ＣＣｎｕｍを行列データＦの１〜Ｃｎｕｍ列に対応させ、擬似クリーク出力結果テーブルにおいて、ノードＡｉ（ｉ＝１〜ｎ）が擬似クリークＣｊ（ｊ＝１〜Ｃｎｕｍ）に含まれることを示している場合にはｉ行ｊ列の要素ｆｉｊに１を、含まれない場合ことを示している場合は対応する要素ｆｉｊに０を設定する。
【００４２】
図６は、演算部１２０の対応分析部１２３における処理フローを示す図である。
同図において、対応分析部１２３は、図５の処理により行列作成部１２２が生成した後行列データＦを記憶部１３０から読み出す（ステップＳ２３１）。対応分析部１２３は、読み出した行列データＦ（ｎ×ｎｏｂｅ:ｎは分析対象の数、ｎｏｂｅは抽出された擬似クリークの数Ｃｎｕｍに相当）に対して、既知の統計手法である対応分析を実施し、分析の結果得られる２列目以降の任意の固有ベクトルを通して得られるカテゴリスコアとサンプルスコアを算出し、その結果を記憶部１３０に書き込む（ステップＳ２３２）。
【００４３】
ここでの対応分析とは、質的変量を対象にした解析手法であり、この対応分析の処理により、似たようなものを近くに、異なるものを遠くに配置するように、カテゴリとサンプルの並びを表すスコアを算出するものである。実際には、公知のアルゴリズムを用いてこの計算を行うが、ここでは簡単に計算の内容を説明する。
【００４４】
具体的には、行列データＦにおいて、ノードＡｉ（ｉ＝１〜ｎ）をサンプルｘｉとし、擬似クリークＣｉ（ｉ＝１〜Ｃｎｕｍ）をカテゴリｙｉとしたとき、サンプルｘｉとカテゴリｙｉのうち、関連があるとする組み合わせを全て抽出する。抽出された組み合わせの集合に対し、サンプル、カテゴリともに平均（ｘ￣，ｙ￣）を０とすると、相関係数ｒは以下となる。
【００４５】
【数２】
【００４６】
ここで、Ｎは抽出された組み合わせの数、ｆｘｉ、ｆｙｉはサンプルｘｉ、カテゴリｙｉに関連があるとして抽出された度数を表す。
そして、関連するカテゴリとサンプルが近くに並ぶように配置することを考えると、次式の制約条件の下で相関係数ｒの最大化を行うことに帰着する。
【００４７】
【数３】
【００４８】
上記の制約のもと、式（３）を、例えばラグランジュの未定乗数法等を用いて展開すると、固有値問題の形に置き換えられる。この固有値問題を解くことで、複数の固有値が相関係数として、第一固有値から大きい順に得られる。
このとき、固有値は複数得られるが、最大固有値は常に１となるため、第二固有値以降に対応する固有ベクトルが、カテゴリスコアとして得られる。また、算出された固有値とカテゴリスコアから、サンプルスコアをそれぞれの並びを表す数値として算出する。
なお、対応分析は、例えば、J.P. Benzecri, Correspondense analysis handbook, New York, U.S.A.: Marcel Dekker, 1992に記載されている。
【００４９】
図１３は、対応分析の結果得られたカテゴリスコアテーブル及びサンプルスコアテーブルであり、記憶部１３０に記憶される。カテゴリスコアテーブルは、各擬似クリークのクリークｉｄと、当該擬似クリークのスコアとが対応づけて記載されている。また、サンプルスコアテーブルには、各ノードＡ１〜Ａｎのノードｉｄと、当該ノードＡ１〜Ａｎそれぞれのスコアとが対応づけて記載されている。
【００５０】
図７は、演算部１２０の抽出対象リスト作成部１２４における処理フローを示す図である。同図において、抽出対象リスト作成部１２４は、記憶部１３０から、着眼ノードｉｄ及び抽出対象ノード数ｍと、対応分析の結果得られたサンプルスコアテーブル（図１３）を読み出す（ステップＳ２４１）。抽出対象リスト作成部１２４は、読み出したサンプルスコアテーブルのノードｉｄを、スコア順に並べ替える。
【００５１】
図１４は、対応分析の結果得られたサンプルスコアテーブル（図１３）のノードｉｄを、スコア順に並べ替えた結果を示すテーブルであり、記憶部１３０に記憶される。この並べ替えにより、同じ擬似クリークに含まれるノード同士の距離がなるべく近くなるように並べ替えられることになる。
【００５２】
抽出対象リスト作成部１２４は、スコア順に並べ替えられたサンプルスコアテーブル（図１４）から、着眼ノードｉｄと一致するノードｉｄの行を中心として、スコアが大きいノードｉｄ、及び、スコアが小さいノードｉｄをそれぞれｍノード分抽出するとともに、当該ノードｉｄに対応するスコアを抽出する。つまり、サンプルスコアテーブルにおいて、着眼ノードｉｄと一致するノードｉｄがｋ行目、抽出対象ノード数がｍであった場合、（ｋ−１）〜（ｋ−ｍ）行目のノードｉｄとそれらのスコア、及び、（ｋ＋１）〜（ｋ＋ｍ）行目のノードｉｄとそれらのスコアを読み出す（図１５）。なお、抽出対象がテーブル境界にかかる（１行目あるいはｎ行目を超える）場合は、境界までのノードを抽出する。そして、抽出したノードｉｄのリストを示すテーブルを記憶部１３０に書き込むとともに、出力部１４０に出力する（ステップＳ２４２）。このとき、ノードｉｄに併せて、あるいは、ノードｉｄの代わりに、ノードｉｄに対応するノードの名称を記憶部１３０から読み出して出力することでもよい。
【００５３】
なお、着眼ノードｉｄの代わりに着眼ノードの名称をパラメータとして入力することでもよい。この場合、着眼ノードの名称に対応したノードｉｄを着眼ノードｉｄとして使用する。
【００５４】
図８は、演算部１２０の可視化部１２５における処理フローを示す図である。同図において、可視化部１２５は、対応分析の結果得られたカテゴリスコアテーブル及びサンプルスコアテーブル（図１３）を記憶部１３０から読み出し、読み出したカテゴリスコアテーブルのクリークｉｄをスコア順に並べ替えとともに、サンプルスコアテーブルのノードｉｄをスコア順に並べ替える（ステップＳ２５１）。可視化部１２５は、並べ替えられたカテゴリスコアテーブルで示されるソート順の擬似クリークと、並べ替えられたサンプルスコアテーブルで示されるソート順のノードを可視化した情報を、出力部１４０により出力する。例えば、可視化部１２５は、記憶部１３０に記憶されているクリーク出力結果テーブル（図１１）または行列データＦ（図１２）から、各ノードＡ１〜Ａｎがどの擬似クリークＣ１〜ＣＣｎｕｍに属しているかを読み出し、ソートされたノードＡ１〜Ａｎと、ソートされた擬似クリークＣ１〜ＣＣｎｕｍとを２軸として、各ノードがどの擬似クリークに属するかを可視化した情報を出力する。また、可視化部１２５は、各ノードｉｄに対応するノードの名称を読み出し、ノードｉｄに対応させてノードの名称を出力することでもよく、ノードの名称のみによりソートされたノードの並びを出力してもよい。
【００５５】
本実施形態によれば、遺伝子間の医学生物学的結び付き等が記述された関係データに対して極大クリークを全列挙し、極大クリークから生成された擬似クリーク群を対象に行列を構成し、対応分析を適用することにより得られるスコアにより、調査対象の遺伝子を選定することができるとともに、ノード間の関連の深さを視覚的に把握することが可能となる。
【００５６】
以下に、上記の評価装置１００を用いた実験結果について説明する。
［実験内容］
ＯＭＩＭデータベースに記載される遺伝子及び疾患の間の関係データを対象として、メタボリック症候群に着眼し、それを構成する肥満、糖尿病、高脂血症、高血圧に関連する遺伝子から対象の選定を図った。４つの疾患との関連の度合が得られることにより本発明の効果を示す。
【００５７】
［実験データ］
ＯＭＩＭデータベースのハイパーリンクを用いて構築した遺伝子間関係データを関係データテーブルＨとして入力した。ＯＭＩＭデータベースは、疾患や遺伝子について記述されたページから構成され、各々はその疾患や遺伝子を単位にＩＤとなる番号(６桁の数字)が付与されている。各ページの記述には医学生物学的知見に基づく結び付きから疾患や遺伝子のページへの参照のリンク（ハイパーリンク）が含まれており，それらのページ中に含まれる疾患や遺伝子の番号により参照情報を取得して、関係データテーブルＨを構築した。
【００５８】
［分析対象］
着眼ノードｍとしてメタボリック症候群を構成する肥満、糖尿病、高脂血症、高血圧の４疾患を指定し、入力した。
そして、ノードとして、上記疾患に関係を持つ遺伝子１２４個を用いた。よって、分析対象のノード数は、上記の疾患４＋遺伝子１２４個＝１２８個である。
［入力パラメータ］
擬似クリークの閾値τ、抽出対象とする遺伝子（ノード）の数ｍを入力した。
【００５９】
［関係データの構成方法］
ネットワークデータである関係データＧ、遺伝子のＩＤをノードとしたとき、遺伝子ｉと遺伝子ｊの関係からエッジをｇｉｊとする。そして、ＯＭＩＭデータベースからの関係の有無に応じて、それぞれｇｉｊ＝１、ｇｉｊ＝０とし、ｉを行、ｊを列とした要素ｇｉｊからなる関係データＧを生成した。なお、分析の際には疾患のノードも遺伝子のノードと同様に扱ってデータを構成した。
【００６０】
図１６〜図１８は、対応分析で得られたスコアにより、ノードとしての遺伝子１２４個＋疾患４個を並べた結果を示す図である。同図においては、４疾患（糖尿病、高脂血症、高血圧、肥満）のノードを含む１８８クリーク（横軸）を取り上げ、それに含まれる１２８ノード（１２４の遺伝子ノードと４つの疾患ノード、縦軸）について対応分析（からの第１成分のスコア）により並びを得て、描かれている。同図により、４つの疾患との関連による遺伝子の並びが得られることが確認できる。この遺伝子の並びを用いて疾患の近傍の遺伝子を特定することにより、当該疾患に関連の深い遺伝子群を選定可能であることが示されている。
また、同図においては、予め記憶部１３０あるいは他の記憶手段に記憶されている、各遺伝子に関連する疾患の情報（ｏ：肥満、ｄ：糖尿病、ｆ：高脂血症、ｈ：高血圧）を読み出し、各遺伝子に対応付けて、当該遺伝子に関連する疾患の情報を出力している。これにより、これまでに上記の疾患に関連するとして知られている遺伝子は、並べ替えられたノード上でも該当する疾患の近傍に位置することがわかる。
【００６１】
なお、上記においては、ノードとして遺伝子と疾患を用いた場合の関係データテーブルＨを入力しているが、ノードとして遺伝子のみを用いた関係データテーブルＨを入力することでもよい。この場合、可視化部１２５は、対応分析の結果によってソートされた遺伝子の並びを出力するとともに、予め記憶部１３０あるいは他の記憶手段に記憶されている、各遺伝子に関連する疾患の情報を読み出し、各遺伝子に対応付けて、当該遺伝子に関連する疾患の情報を出力する。これにより、疾患に関連する遺伝子群を認識することができる。
【００６２】
また、上記においては、ノードして遺伝子と疾患、あるいは、遺伝子のみを用いているが、分析対象のノードを企業とすることができる。ノードを企業とする場合、企業間の取引の有無が記述された関係データＨを入力し、着眼ノードｉｄとして注目する企業のｉｄを入力する。関係データＨは、企業の財務データなどから、企業間の取引関係を抽出し、作成することができる。ノードを企業とすることで、調査対象である注目する企業と関連がある他の企業を関係が深いものから所望の数だけ選定することができるとともに、企業間の関連を視覚化して確認することができる。
【００６３】
なお、上述の評価装置１００は、内部にコンピュータシステムを有している。そして、評価装置１００の入力部１１０及び演算部１２０の動作の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータシステムが読み出して実行することによって、上記処理が行われる。ここでいうコンピュータシステムとは、ＣＰＵ及び各種メモリやＯＳ、周辺機器等のハードウェアを含むものである。
【００６４】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【図面の簡単な説明】
【００６５】
【図１】本発明の一実施形態による評価装置の構成を示すブロック図である。
【図２】同実施形態による評価装置の入力部における処理フローを示す。
【図３】同実施形態による評価装置の演算部における概要処理フローを示す。
【図４】同実施形態による評価装置のクリーク抽出部における処理フローを示す。
【図５】同実施形態による評価装置の行列作成部における処理フローを示す。
【図６】同実施形態による評価装置の対応分析部における処理フローを示す。
【図７】同実施形態による評価装置の抽出対象リスト作成部における処理フローを示す。
【図８】同実施形態による評価装置の可視化部における処理フローを示す。
【図９】同実施形態による関係データテーブルＨのデータ構成例を示す。
【図１０】同実施形態による関係データＧのデータ構成例を示す。
【図１１】同実施形態によるクリーク出力結果テーブルのデータ構成例を示す。
【図１２】同実施形態による行列データＦのデータ構成例を示す。
【図１３】同実施形態による対応分析の結果得られたカテゴリスコアテーブル及びサンプルスコアテーブルのデータ構成例を示す。
【図１４】同実施形態によるソートされたサンプルスコアテーブルのデータ構成例を示す。
【図１５】同実施形態による抽出対象ノードリストの例を示す。
【図１６】同実施形態による評価装置の実験結果で出力された可視化されたノードの並びを示す。
【図１７】同実施形態による評価装置の実験結果で出力された可視化されたノードの並びを示す。
【図１８】同実施形態による評価装置の実験結果で出力された可視化されたノードの並びを示す。
【符号の説明】
【００６６】
１００…評価装置
１１０…入力部
１２０…演算部
１２１…クリーク抽出部
１２２…行列作成部
１２３…対応分析部
１２４…抽出対象リスト作成部
１３０…記憶部
１４０…出力部
【技術分野】
【０００１】
本発明は、相互に関連があるデータ群についてデータ間の関連を評価する評価装置、及び、コンピュータプログラムに関する。
【背景技術】
【０００２】
現在、さまざまな分野で行われているデータマイニングにおいて、データ一つ一つが関係するデータ群の中から、ある目的のために、分析を行う対象を絞り込む、という事が行われている。
【０００３】
例えば、ライフサイエンス分野においては、ある疾患に対する遺伝子の関連を見るために、実験により検証を図る遺伝子群の選定が課題にある。コストを要する生物学的実験により検証が図られることから、薬剤開発等に関わるターゲッティングにあたって、必要な遺伝子のとりこぼしがない、最小限の遺伝子セットの取り揃えを用意することが求められる。通常は、文献調査やデータベース（パスウエィデータベース等）の検索により、このような遺伝子群が定められる。しかしながら、現行のパスウェイ（遺伝子から翻訳されたタンパク質の作用の連鎖構造を表す）抽出は、ターゲットを絞った上で、大量の論文類の精読に基づいて行なわれる（例えば、非特許文献１参照）ことから、部分的にのみ得られている状況にある。
【０００４】
また、例えば、企業の（与信等の）評価にあたって、有価証券報告書等に記載される取引先（の業績等）といった関係データを用いた評価を行なう場合、注目企業の取引先企業を調査対象企業群として選定する必要がある。これまでは直接の取引先を、有価証券報告書等のデータベース検索の結果から取得（例えば、特許文献１参照）してリスト化するのが一般的であった。また、関係データのもつグラフ構造を基に所定の指標を算出してスコア付与する方法もある。
【非特許文献１】K. Oda, Y.Matsuoka, A. Funahashi and H. Kitano,“A comprehensive pathway map of epidermal growth factor receptor signaling,” Mol. Syst. Biol., vol. 1, 2005.0010, May 2005.
【特許文献１】特開２００３−０３０４６７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載されるような、従来のデータベースを検索する方法では、遺伝子と、直接関係のある疾患に限定された把握にとどまっていたため、遺伝子そのものの関係などが考慮されないという限界がある。また、遺伝子関係の視覚化を通して属する遺伝子群を把握するもあるが、規模が大きくなると視覚化の了解性が損なわれ、適切に遺伝子群を得ることが困難であった。一方、特許文献１に記載されるような従来の技術では、取引関係を考慮して対象企業群を取得する際に、調査コストに応じて、より関連が強い企業に限定した数の対象企業群を取得することはできなかった。
【０００６】
本発明は、上記の事情に鑑みてなされたものであり、相互に関連を持つデータをその関連の深さとともに把握可能とし、調査対象のデータに関連する他のデータのセットを、関連の深いものから取りこぼしなく所望の数得ることができる評価装置、及び、コンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、本発明は、相互に関連のあるデータ群より抽出される疑似クリークを構成するための関連度の閾値を記憶する記憶部と、複数のノードと、当該複数のノードそれぞれについての他のノードとの関連をエッジとして表す関係データの入力を受ける入力部と、前記入力部に入力された関係データにより示されるグラフにおける極大クリークを抽出し、抽出した極大クリークの全ての組み合わせのうち、前記閾値より大きい関連度を有する極大クリークの組み合わせを選択し、選択した各極大クリークの組み合わせそれぞれについて、当該組み合わせを構成する極大クリークに含まれる前記ノードの和集合からなる擬似クリークを生成して前記記憶部に書き込むクリーク抽出部と、前記クリーク抽出部により生成された各擬似クリークに含まれる前記ノードを前記記憶部から読み出し、それぞれの前記ノード及びそれぞれの前記擬似クリークを各行及び各列に対応させ、かつ、前記ノードが前記擬似クリークに含まれる場合は当該ノード及び当該擬似クリークに対応する行及び列の要素に１を、含まれない場合は対応する行及び列の要素に０を設定した行列を生成して前記記憶部に書き込む行列作成部と、前記行列作成部により生成された前記行列を前記記憶部から読み出し、当該行列の対応分析を行い、前記ノードそれぞれのスコアを算出して前記記憶部に書き込む対応分析部と、前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果を可視化した情報を出力する可視化部と、を備えることを特徴とする評価装置である。
【０００８】
また、本発明は、上述する評価装置において、前記対応分析部は、前記行列の対応分析を行い、前記ノードそれぞれのスコア及び前記擬似クリークそれぞれのスコアを算出して前記記憶部に書き込み、前記可視化部は、前記対応分析部により算出された前記ノードのスコア及び前記擬似クリークのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果、及び、前記擬似クリークを当該擬似クリークのスコア順に並べた結果と、前記ノードそれぞれが属する前記擬似クリークを可視化した情報を出力する、ことを特徴とする。
【０００９】
また、本発明は、上述する評価装置において、前記入力部は、さらに、調査対象のノード及びノード数の入力を受けて前記記憶部に記憶し、前記入力部が入力を受けた前記調査対象のノード及び前記ノード数の情報と、前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べ、この前記ノードをスコア順に並べた結果において、前記調査対象のノードに隣接する他のノードを前記ノード数分特定する抽出対象リスト作成部をさらに備える、ことを特徴とする。
【００１０】
また、本発明は、上述する評価装置において、前記ノードは、他のノードとの関連であるエッジとして、医学・生物学あるいは取引・資本関係における結びつきを持つノードであることを特徴とする。
【００１１】
また、本発明は、評価装置として用いられるコンピュータを、相互に関連のあるデータ群より抽出される疑似クリークを構成するための関連度の閾値を記憶する記憶部、複数のノードと、当該複数のノードそれぞれについての他のノードとの関連をエッジとして表す関係データの入力を受ける入力部、前記入力部に入力された関係データにより示されるグラフにおける極大クリークを抽出し、抽出した極大クリークの全ての組み合わせのうち、前記閾値より大きい関連度を有する極大クリークの組み合わせを選択し、選択した各極大クリークの組み合わせそれぞれについて、当該組み合わせを構成する極大クリークに含まれる前記ノードの和集合からなる擬似クリークを生成して前記記憶部に書き込むクリーク抽出部、前記クリーク抽出部により生成された各擬似クリークに含まれる前記ノードを前記記憶部から読み出し、それぞれの前記ノード及びそれぞれの前記擬似クリークを各行及び各列に対応させ、かつ、前記ノードが前記擬似クリークに含まれる場合は当該ノード及び当該擬似クリークに対応する行及び列の要素に１を、含まれない場合は対応する行及び列の要素に０を設定した行列を生成して前記記憶部に書き込む行列作成部、前記行列作成部により生成された前記行列を前記記憶部から読み出し、当該行列の対応分析を行い、前記ノードそれぞれのスコアを算出して前記記憶部に書き込む対応分析部、前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果を可視化した情報を出力する可視化部、として動作させることを特徴とするコンピュータプログラムである。
【発明の効果】
【００１２】
本発明によれば、遺伝子及び疾患、または、疾患、あるいは、企業等をノードとし、ノード間に相互に関連がある場合に、ノード間の関係をその関連の深さとともに視覚化することが可能となる。よって、視覚的な確認の下で、ノード間の関連を判断することが可能となる。また、ノード数が大量である場合にも、大局的視点からとりこぼすことなく所望の数だけ、調査対象ノードと関連が深いノードの選定が図られることに加え、ハブ的役割をもつノードの関係の把握が可能となる。よって、ノード間の関連を把握したり、調査対象ノードに関連するノードを選定したりする際に、試行錯誤を繰り返すことなく、工数を削減することができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照して本発明の実施の形態の例について説明する。
本発明の一実施形態による評価装置は、例えば、遺伝子及び疾患をノードとし、これらのノード間に関連があるときに無向のエッジがひかれるグラフデータからクリークを全て抽出し、その抽出したクリーク群の行列表現に対して対応分析を行なった結果得られるノードの並び、つまり、遺伝子と疾患の並びから調査対象遺伝子群を選定する。
【００１４】
ここでのグラフとは、グラフ理論において定義されるものであって、いくつかのノード（点、頂点などとも呼ばれる）と、それらのノードの対を両端とする線分であるエッジ（枝、アーク、辺などとも呼ばれる）によって表される。このようなグラフは、図形を表して表現しても良いし、配列の各要素をノードとした配列処理によって表すようにしても良い。
【００１５】
グラフＧのノードの集合をＶおよびエッジの集合をＥとすると、グラフＧはＧ＝（Ｖ，Ｅ）で表される。また、グラフＧにおけるノードの集合Ｖの部分集合ＶＨとエッジの集合Ｅの部分集合ＥＨに対して、どのエッジｋ∈ＥＨ（ｋは部分集合ＥＨの要素を表す）の両端点もＶＨに含まれるとき、グラフＨ＝（ＶＨ，ＥＨ）をグラフＧの部分グラフという。また、すべてのノードの対がエッジで結ばれているグラフを完全グラフという。
【００１６】
そして、グラフＧの部分グラフＱで完全グラフとなっているものをクリーク（あるいは完全部分グラフ）という。なお、このような部分グラフＱのノードの集合をクリークと呼ぶこともある。クリークＱのサイズをノードの個数で定義し、｜Ｑ｜で表す。また、ノードの個数がｎ個のクリークをサイズｎのクリークとも呼ぶ。そして、グラフＧのクリークＱのノードの集合が他のどのクリークのノードの集合にも真に含まれないとき、集合ＱをグラフＧの極大クリークという。
【００１７】
評価装置が対応分析を行なう対象のクリーク群は、極大クリークから生成される擬似クリークからなる。そのため、評価装置は、まず、グラフデータから極大クリークを抽出し、この極大クリークから擬似クリークを生成する。擬似クリークとは、所定の閾値以上の度合でノードを共有する、複数の極大クリークを統合したものである。つまり、擬似クリークは、抽出した極大クリークのうち、一部に重複するノードを含む極大クリーク同士で、その重複するノードが所定の割合を超えるものを一つの集合としたものであり、この集合は上述したクリークの定義をかならずしも満たさないため、擬似的なクリークと呼ばれている。ここでは、擬似クリークを生成するために複数の極大クリークが統合対象であると判断するための条件である、ノードを共有する割合の閾値を、「擬似クリークの閾値」と記載する。例えば、ある２つの極大クリークＡと極大クリークＢについて、（極大クリークＡと極大クリークＢの積集合に含まれるノード数）／（極大クリークＡと極大クリークＢの和集合に含まれるノード数）＞（擬似クリークの閾値）を満たす場合、極大クリークＡと極大クリークＢの和集合が擬似クリークとなる。
【００１８】
また、対応分析とはサンプルとカテゴリ間の関係のデータを対象に、サンプルとカテゴリとの対応付けを図る公知の統計手法である。前提として、１つのサンプルが複数のカテゴリに属してもよい状況で、一般に、その関係データはサンプルおよびカテゴリをそれぞれ行および列に割り当てた行列データ（データ要素は関係ありとなしに応じて１と０で表される）により記述される。対応分析では行の項目と列の項目の相関が最大化されるようなサンプルスコアとカテゴリスコアが行列の固有ベクトルを通して得られる。このスコアにより行と列をソートすることで、対応が考慮されたサンプルとカテゴリの並びが出力される。
【００１９】
図１は、本発明の一実施の形態による評価装置１００の構成を示す図であり、本発明と関係する機能ブロックのみ抽出して示してある。同図において、評価装置１００は、入力部１１０、演算部１２０、記憶部１３０、出力部１４０を備える。
【００２０】
入力部１１０は、どのノードがどのノードと関連するかを示す関係データテーブルの入力を受け、入力された関係データテーブルＨを行列表現にしたデータを記憶部１３０に書き込む。さらに入力部１１０は、各種パラメータの入力データを受け、記憶部１３０に書き込む。パラメータには、擬似クリークの閾値τ、着眼ノードのｉｄ、及び、着眼ノードとして指定されたノードの関連ノードとして抽出対象とするノード数ｍがある。記憶部１３０は、入力部１１０が入力を受けたデータや、演算部１２０における演算処理の途中結果、演算結果のデータを記憶する。出力部１４０は、例えば、ディスプレイやプリンタなどであり、演算結果を出力する。
【００２１】
演算部１２０は、記憶部１３０に記憶されたデータを用いて演算処理を行い、演算結果として、関連が高いノードがより近い距離となるように順にノードを並べたソート結果を可視化した結果と、着眼ノードに関連が高いノードのリストを示す調査対象リストとを得る。演算部１２０は、クリーク抽出部１２１、行列作成部１２２、対応分析部１２３、抽出対象リスト作成部１２４を備える。
【００２２】
クリーク抽出部１２１は、記憶部１３０から行列表現された関係データを読み出して極大クリークを抽出し、擬似クリークの閾値τを用いて、抽出した極大クリークから擬似クリークを生成する。行列作成部１２２は、クリーク抽出部１２１により生成された擬似クリーク群を行列により表現した行列データを生成する。対応分析部１２３は、行列作成部１２２が生成した行列データに基づき対応分析を行なう。抽出対象リスト作成部１２４は、対応分析部１２３による対応分析の結果に基づいて並べ替えられたノードから、着眼ノードのｉｄにより特定されるノードを中心にノード数ｍ分の近傍のノードを読み出して、調査対象リストを生成する。可視化部１２５は、対応分析部１２３による対応分析の結果に基づいて並べ替えられたノード及び擬似クリークを可視化した情報を出力部１４０に出力する。
【００２３】
次に、評価装置１００の処理について説明する。
図２は、図１に示す評価装置１００の入力部１１０における処理フローを示す。同図において入力部１１０は、関係データテーブルＨと、擬似クリークの閾値τ、抽出対象ノード数ｍ、着眼ノードｉｄとの入力を受け、記憶部１３０に書き込む（ステップＳ１１）。このときの関係データテーブルＨは、例えば、前処理によって、評価装置１００とインターネットなどのネットワークを介して接続されるデータベース、例えば、遺伝子変異による疾患に関する情報が提供されているＯＭＩＭ(Online Mendelian Inheritance in Man)データベースから、疾患と遺伝子の関連データを読み出して生成するようにしてもよい。なお、ＯＭＩＭは、ヒトの遺伝病に関するデータベースとしてよく知られている。
【００２４】
図９は、入力部１１０に入力される遺伝子及び疾患の関係データテーブルＨの例を示す図である。同図において、関係データテーブルＨは、遺伝子Ａ１に関係がある遺伝子または疾患が遺伝子Ａ２、疾患Ａ３、…、遺伝子Ａｎであり、遺伝子Ａ２に関係がある遺伝子または疾患が遺伝子Ａ１、…、遺伝子Ａｎであり、疾患Ａ３に関係がある遺伝子または疾患が遺伝子Ａｎであり、遺伝子Ａｎに関係がある遺伝子または疾患が遺伝子Ａ１、遺伝子Ａ２、疾患Ａ３であることが示されている。入力部１１０は、入力された関係データテーブルに含まれる全てのノード、つまり、遺伝子及び疾患を抽出すると、この抽出したノードそれぞれにノードｉｄを割当てる。ここでは、抽出されたｎ個のノードである遺伝子Ａ１、遺伝子Ａ２、疾患Ａ３、…、遺伝子Ａｎに割当てられたノードｉｄをそれぞれＡ１、Ａ２、Ａ３、…、Ａｎとする。以下、割当てられたノードｉｄがＡｋ（ｋ＝１〜ｎ）のノードをノードＡｉと記載する。
【００２５】
図１０は、入力された関係データテーブルＨ（図９）に基づいて入力部１１０が生成した関係データＧを示す。入力部１１０は、関係データテーブルから抽出されたｎ個のノードＡ１〜Ａｎを１〜ｎ行、及び、１〜ｎ列に対応させ、ノード間に関係がある場合には対応する要素に１を、関係がない場合は対応する要素に０を設定した行列データを生成する。つまり、関係データテーブルＨに、ノードＡｉ（ｉ＝１〜ｎ）がノードＡｊ（ｊ＝１〜ｎ、ｉ≠ｊ）に関連があることが設定されている場合には関係データＧのｉ行ｊ列の要素ｇｉｊ及びｊ行ｉ列の要素ｇｊｉに１を、含まれない場合ことを示している場合は関係データＧのｉ行ｊ列の要素ｇｉｊ及びｊ行ｉ列の要素ｇｊｉに０を設定する。なお、行と列が同じノードに対応する関係データＧの要素、つまり、ｉ行ｉ列（ｉ＝１〜ｎ）の要素には０を設定するが、１を設定するようにしてもよい。この関係データＧは、遺伝子及び疾患をノードとし、ある遺伝子または疾患について関連しあう関係をエッジとしたグラフにより表現したデータに相当する。つまり、この関係データＧはグラフＧ＝（Ｖ，Ｅ）（ただし、Ｖはノード、Ｅはエッジ）を表したものである。入力部１１０は、関係データＧとともに、ノードｉｄとノードの名称とを対応付けた情報も記憶部１３０に書き込むものとする。
【００２６】
図３は、演算部１２０の処理フローを示す図である。
まず、クリーク抽出部１２１は、記憶部１３０から関係データＧを読み出すと、極大クリーク全列挙アルゴリズムを適用して、関係データＧにより表現されるグラフから極大クリークを全て抽出して列挙したのち、エッジの接続条件を緩和した擬似クリークを生成して列挙し、記憶部１３０に書き込む（ステップＳ２１）。なお、擬似クリークについては列挙しなくてもよいが、列挙したほうが関係性を大局的に判断することができる。
【００２７】
次に、行列作成部１２２は、ステップＳ２１において列挙された擬似クリーク群を記憶部１３０から読み出し、当該擬似クリーク群に基づいて、擬似クリークｉｄを行に、ノードｉｄを列に対応させ、各擬似クリークを構成するノードに対応するする要素を１、それ以外の要素を０とした行列データＦを生成し、記憶部１３０に書き込む（ステップＳ２２）。
【００２８】
対応分析部１２３は、ステップＳ２２の結果得られた行列データＦを記憶部１３０から読み出し、当該行列データＦに対して対応分析を適用して、第１固有値からの第１成分スコアをノードの並びを示す値として得る（ステップＳ２３）。なお、第２成分以降のスコアをノードの並びを示す値として採用しても良い。
【００２９】
抽出対象リスト作成部１２４は、記憶部１３０から抽出ノード数ｍ、着眼ノードｉｄを読み出し、ステップＳ２３において得られたスコアに基づいてノードを昇順に並べ替え、並べ替えられたノードの並びにおいて、着眼ノードｉｄ、例えば、ある疾患のノードｉｄを中心にして両側ｍ個ずつの近傍のノードｉｄを読み出し、読み出したノードｉｄのリストを生成し、出力部１４０に出力する（ステップＳ２４）。また、可視化部１２５は、ステップＳ２３において得られたスコアに基づいてノード及び擬似クリークそれぞれを昇順に並べ替え、並びかえられたノード及び擬似クリークの並びと、各ノードがいずれの擬似クリークに含まれるかを可視化した情報を生成して、出力部１４０に出力する（ステップＳ２５）。
【００３０】
図４は、図３のステップＳ２１の詳細な処理フローを示す図である。
同図において、クリーク抽出部１２１は、記憶部１３０から関係データＧ、及び、擬似クリークの閾値τを読み出す（ステップＳ２１１）。クリーク抽出部１２１は、関係データＧにより示されるグラフから極大クリークを抽出する（ステップＳ２１２）。極大クリークの抽出方法には、様々なものがあるが、例えば、以下の方法で行なう。
【００３１】
まず、クリーク抽出部１２１は、関係データＧにより示される、分析対象となる全てのノードＡ１〜Ａｎから、任意のノードＡｉ（ｉ＝１〜ｎ）を１つ選択する。クリーク抽出部１２１は、関係データＧにより示されるノード間の関係から、選択したノードＡｉとリンクを持つノードのリストを作成し、サイズ２のクリークのリストを登録した抽出経過テーブルを記憶部１３０へ書き込む。例えば、関係データＧのｉ行において要素の値が１である列を特定し、特定した列に対応するノードがノードＡｉとリンクを持つノードして抽出され、クリークサイズ「２」とともに抽出経過テーブルに登録される。この際、クリーク抽出部１２１は、集合として同値の組み合わせを抽出経過テーブルから除去する。
【００３２】
次にクリーク抽出部１２１は、関係データＧから、抽出経過テーブルにサイズ２のリストとして記載されたノードと互いにリンクを持つノードのリストを作成し、サイズ３のクリークとして抽出経過テーブルに記憶する。例えば、サイズ２のクリークが、ノードＡｉ、ノードＡｋとからなる場合、関係データＧのｉ行及びｋ列において要素の値が１である列を特定し（ｉ列及びｋ列を除く）、特定した列に対応するノードがノードＡｉ、ノードＡｋとリンクを持つノードして抽出され、クリークサイズ「３」とともに抽出経過テーブルに登録される。この際も、クリーク抽出部１２１は、集合として同値の組み合わせを抽出経過テーブルから除去する。このとき、新たに登録したクリークサイズ「３」のクリークの部分集合となるクリーク「２」のノードの組み合わせも削除されることになる。当該処理を、サイズ４、サイズ５と新たなリンクが見つからなくなるまで繰り返すことにより、選択したノードに関する極大クリークが抽出され、抽出経過テーブルに登録される。
【００３３】
クリーク抽出部１２１は、上記処理を、全てのノードＡ１〜Ａｎについて繰り返すことにより、完全グラフとなる全ての極大クリークを抽出して抽出経過テーブルに登録し、最終的な抽出経過テーブルを生成すると、各極大クリークに極大クリークｉｄを割当てる。クリーク抽出部１２１は、抽出経過テーブルに割当てた極大クリークｉｄの情報を追加し、極大クリーク出力結果テーブルとして記憶部１３０に書き込む。
なお、上記の方法のほか、極大クリーク全列挙アルゴリズムの公知技術であるＣＬＩＱＵＥＳ法などを用いても構わない。ＣＬＩＱＵＥＳ法については、例えば、以下の論文、E. Tomita, A. Tanaka and H. Takahashi : The worst-case time complexity for generating all maximal cliques and computational experiments, Teoret. Comput. Sci. 363, pp. 28-42, 2006.に記載されている。
【００３４】
図１１は、ステップＳ２１２において生成された極大クリーク出力結果テーブルの例を示す図である。同図において、極大クリーク出力結果テーブルには、抽出した極大クリークを特定する識別情報としての極大クリークｉｄと、当該極大クリークのサイズと、当該極大クリークを構成するノードを示す構成要素とが対応づけられて登録されている。ここでは、抽出された極大クリークの数をＣ’ｎｕｍとしている。
同図において、極大クリークｉｄ＝１により特定される極大クリークは、サイズが４であり、遺伝子Ａ１、遺伝子Ａ２、疾患Ａ３、遺伝子Ａ８からなることが示されている。なお、構成要素は、ノードｉｄにより示されることでもよい。以下、極大クリークｉｄ＝ｋにより特定される極大クリークを極大クリークＣ’ｋと記載する。抽出された極大クリークの集合、つまり、｛Ｃ’１，…，Ｃ’Ｃ’ｎｕｍ｝を極大クリーク族Ｃ’とする。
【００３５】
次に、クリーク抽出部１２１は、抽出された極大クリーク群から擬似クリークを抽出する（ステップＳ２１３）。ここでは、クリーク抽出部１２１は、極大クリーク出力結果テーブル（図１１）に登録されている極大クリークから、下記の擬似クリークの条件に当てはまる関連度の高い極大クリークの組み合わせＰＣ（Ｃ’）を抽出するとともに、各ＰＣ（Ｃ’）に含まれるノード数をクリークサイズとして算出する。例えば、擬似クリークの抽出は以下の方法で行う。
【００３６】
まず、クリーク抽出部１２１は、極大クリーク出力結果テーブルにより示される、ステップＳ２２２において抽出された極大クリークＣ’１〜Ｃ’Ｃ’ｎｕｍについて、２以上の極大クリークからなる全ての組み合わせを生成し、テーブルとして記憶部１３０に記憶しておく。次に、クリーク抽出部１２１は、当該テーブルに記憶した極大クリークの組み合わせＰＣ（Ｃ’）を順に個別に取り出し、その組み合わせを構成する極大クリークそれぞれに含まれるノードをクリーク出力結果テーブル（図１１）から読み出すと、本手法では関連度として、式（１）により重複度overlap()を評価値として算出する。この重複度は０以上１以下の値をとり、値が大きくなるほど重複の度合いが大きくなる。この算出した評価結果が、擬似クリークの閾値τを超えた極大クリークの組み合わせＰＣ（Ｃ’）から擬似クリークを生成する。つまり、クリーク抽出部１２１は、式（２）に示すように、極大クリークＣ’１，Ｃ’２，…，Ｃ’Ｃ’ｎｕｍの中から２以上を用いた極大クリークの組み合わせＰＣ（Ｃ’）のうち、重複度overlap(Ｃ’)が擬似クリークの閾値τを越えるような極大クリークの組み合わせＰＣ（Ｃ’）の和集合を、擬似クリークとして定義する。さらに、クリーク抽出部１２１は、極大クリークの組み合わせＰＣ（Ｃ’）を構成する各極大クリークのノードの和集合の個数から当該擬似クリークのサイズを定める。クリーク抽出部１２１は、生成した当該擬似クリークに付与したクリークｉｄと、当該擬似クリークに含まれるノードを擬似クリーク出力結果テーブルに登録する。この擬似クリーク出力結果テーブルは記憶部１３０に記憶される。
下記の式において、∩はクリークの積集合を、∪はクリークの和集合を、｜ ｜はノードの個数を、ｍｉｎは最小値を表す。また、τは重複度を制御する閾値である。
【００３７】
【数１】
【００３８】
なお、上記の方法のほか、公知技術であるエッジ密度に基づく擬似クリーク抽出方法などを用いても構わない。この場合、関連度としてエッジ密度を採用するが、このエッジ密度に基づく擬似クリーク抽出方法については、例えば、以下の論文、T. Uno, “An efficient algorithm for enumerating pseudo cliques,” Lecture Notes in Computer Science, vol. 4835, pp. 402-414, 2007.に記載されている。
【００３９】
なお、擬似クリーク出力結果テーブルは、例えば図１１に示す極大クリーク出力結果テーブルと同じ形式のテーブルであり、擬似クリークを特定する番号であるクリークｉｄと、当該擬似クリークのサイズと、当該擬似クリークの構成要素であるノードの識別情報とが登録される。ここでは、抽出された擬似クリークの数をＣｎｕｍとする。以下、クリークｉｄ＝ｋにより特定される擬似クリークを擬似クリークＣｋと記載する。よって、抽出された擬似クリーク群は、擬似クリークＣ１，Ｃ２，…，ＣＣｎｕｍとなる。
【００４０】
図５は、演算部１２０の行列作成部１２２における処理フローを示す図である。
同図において、行列作成部１２２は、図４の処理によりクリーク抽出部１２１が生成した擬似クリーク出力結果テーブルを記憶部１３０から読み出す（ステップＳ２２１）。行列作成部１２２は、読み出した擬似クリーク出力結果テーブルを参照して、各ノードがどの擬似クリークに属しているかを示す行列データＦを生成し、記憶部１３０に書き込む（ステップＳ２２２）。
【００４１】
図１２は、ステップＳ２２２において生成された行列データＦの例を示す図である。行列作成部１２２は、ノードＡ１〜ノードＡｎそれぞれを行列データＦの１〜ｎ行に、擬似クリークＣ１〜ＣＣｎｕｍを行列データＦの１〜Ｃｎｕｍ列に対応させ、擬似クリーク出力結果テーブルにおいて、ノードＡｉ（ｉ＝１〜ｎ）が擬似クリークＣｊ（ｊ＝１〜Ｃｎｕｍ）に含まれることを示している場合にはｉ行ｊ列の要素ｆｉｊに１を、含まれない場合ことを示している場合は対応する要素ｆｉｊに０を設定する。
【００４２】
図６は、演算部１２０の対応分析部１２３における処理フローを示す図である。
同図において、対応分析部１２３は、図５の処理により行列作成部１２２が生成した後行列データＦを記憶部１３０から読み出す（ステップＳ２３１）。対応分析部１２３は、読み出した行列データＦ（ｎ×ｎｏｂｅ:ｎは分析対象の数、ｎｏｂｅは抽出された擬似クリークの数Ｃｎｕｍに相当）に対して、既知の統計手法である対応分析を実施し、分析の結果得られる２列目以降の任意の固有ベクトルを通して得られるカテゴリスコアとサンプルスコアを算出し、その結果を記憶部１３０に書き込む（ステップＳ２３２）。
【００４３】
ここでの対応分析とは、質的変量を対象にした解析手法であり、この対応分析の処理により、似たようなものを近くに、異なるものを遠くに配置するように、カテゴリとサンプルの並びを表すスコアを算出するものである。実際には、公知のアルゴリズムを用いてこの計算を行うが、ここでは簡単に計算の内容を説明する。
【００４４】
具体的には、行列データＦにおいて、ノードＡｉ（ｉ＝１〜ｎ）をサンプルｘｉとし、擬似クリークＣｉ（ｉ＝１〜Ｃｎｕｍ）をカテゴリｙｉとしたとき、サンプルｘｉとカテゴリｙｉのうち、関連があるとする組み合わせを全て抽出する。抽出された組み合わせの集合に対し、サンプル、カテゴリともに平均（ｘ￣，ｙ￣）を０とすると、相関係数ｒは以下となる。
【００４５】
【数２】
【００４６】
ここで、Ｎは抽出された組み合わせの数、ｆｘｉ、ｆｙｉはサンプルｘｉ、カテゴリｙｉに関連があるとして抽出された度数を表す。
そして、関連するカテゴリとサンプルが近くに並ぶように配置することを考えると、次式の制約条件の下で相関係数ｒの最大化を行うことに帰着する。
【００４７】
【数３】
【００４８】
上記の制約のもと、式（３）を、例えばラグランジュの未定乗数法等を用いて展開すると、固有値問題の形に置き換えられる。この固有値問題を解くことで、複数の固有値が相関係数として、第一固有値から大きい順に得られる。
このとき、固有値は複数得られるが、最大固有値は常に１となるため、第二固有値以降に対応する固有ベクトルが、カテゴリスコアとして得られる。また、算出された固有値とカテゴリスコアから、サンプルスコアをそれぞれの並びを表す数値として算出する。
なお、対応分析は、例えば、J.P. Benzecri, Correspondense analysis handbook, New York, U.S.A.: Marcel Dekker, 1992に記載されている。
【００４９】
図１３は、対応分析の結果得られたカテゴリスコアテーブル及びサンプルスコアテーブルであり、記憶部１３０に記憶される。カテゴリスコアテーブルは、各擬似クリークのクリークｉｄと、当該擬似クリークのスコアとが対応づけて記載されている。また、サンプルスコアテーブルには、各ノードＡ１〜Ａｎのノードｉｄと、当該ノードＡ１〜Ａｎそれぞれのスコアとが対応づけて記載されている。
【００５０】
図７は、演算部１２０の抽出対象リスト作成部１２４における処理フローを示す図である。同図において、抽出対象リスト作成部１２４は、記憶部１３０から、着眼ノードｉｄ及び抽出対象ノード数ｍと、対応分析の結果得られたサンプルスコアテーブル（図１３）を読み出す（ステップＳ２４１）。抽出対象リスト作成部１２４は、読み出したサンプルスコアテーブルのノードｉｄを、スコア順に並べ替える。
【００５１】
図１４は、対応分析の結果得られたサンプルスコアテーブル（図１３）のノードｉｄを、スコア順に並べ替えた結果を示すテーブルであり、記憶部１３０に記憶される。この並べ替えにより、同じ擬似クリークに含まれるノード同士の距離がなるべく近くなるように並べ替えられることになる。
【００５２】
抽出対象リスト作成部１２４は、スコア順に並べ替えられたサンプルスコアテーブル（図１４）から、着眼ノードｉｄと一致するノードｉｄの行を中心として、スコアが大きいノードｉｄ、及び、スコアが小さいノードｉｄをそれぞれｍノード分抽出するとともに、当該ノードｉｄに対応するスコアを抽出する。つまり、サンプルスコアテーブルにおいて、着眼ノードｉｄと一致するノードｉｄがｋ行目、抽出対象ノード数がｍであった場合、（ｋ−１）〜（ｋ−ｍ）行目のノードｉｄとそれらのスコア、及び、（ｋ＋１）〜（ｋ＋ｍ）行目のノードｉｄとそれらのスコアを読み出す（図１５）。なお、抽出対象がテーブル境界にかかる（１行目あるいはｎ行目を超える）場合は、境界までのノードを抽出する。そして、抽出したノードｉｄのリストを示すテーブルを記憶部１３０に書き込むとともに、出力部１４０に出力する（ステップＳ２４２）。このとき、ノードｉｄに併せて、あるいは、ノードｉｄの代わりに、ノードｉｄに対応するノードの名称を記憶部１３０から読み出して出力することでもよい。
【００５３】
なお、着眼ノードｉｄの代わりに着眼ノードの名称をパラメータとして入力することでもよい。この場合、着眼ノードの名称に対応したノードｉｄを着眼ノードｉｄとして使用する。
【００５４】
図８は、演算部１２０の可視化部１２５における処理フローを示す図である。同図において、可視化部１２５は、対応分析の結果得られたカテゴリスコアテーブル及びサンプルスコアテーブル（図１３）を記憶部１３０から読み出し、読み出したカテゴリスコアテーブルのクリークｉｄをスコア順に並べ替えとともに、サンプルスコアテーブルのノードｉｄをスコア順に並べ替える（ステップＳ２５１）。可視化部１２５は、並べ替えられたカテゴリスコアテーブルで示されるソート順の擬似クリークと、並べ替えられたサンプルスコアテーブルで示されるソート順のノードを可視化した情報を、出力部１４０により出力する。例えば、可視化部１２５は、記憶部１３０に記憶されているクリーク出力結果テーブル（図１１）または行列データＦ（図１２）から、各ノードＡ１〜Ａｎがどの擬似クリークＣ１〜ＣＣｎｕｍに属しているかを読み出し、ソートされたノードＡ１〜Ａｎと、ソートされた擬似クリークＣ１〜ＣＣｎｕｍとを２軸として、各ノードがどの擬似クリークに属するかを可視化した情報を出力する。また、可視化部１２５は、各ノードｉｄに対応するノードの名称を読み出し、ノードｉｄに対応させてノードの名称を出力することでもよく、ノードの名称のみによりソートされたノードの並びを出力してもよい。
【００５５】
本実施形態によれば、遺伝子間の医学生物学的結び付き等が記述された関係データに対して極大クリークを全列挙し、極大クリークから生成された擬似クリーク群を対象に行列を構成し、対応分析を適用することにより得られるスコアにより、調査対象の遺伝子を選定することができるとともに、ノード間の関連の深さを視覚的に把握することが可能となる。
【００５６】
以下に、上記の評価装置１００を用いた実験結果について説明する。
［実験内容］
ＯＭＩＭデータベースに記載される遺伝子及び疾患の間の関係データを対象として、メタボリック症候群に着眼し、それを構成する肥満、糖尿病、高脂血症、高血圧に関連する遺伝子から対象の選定を図った。４つの疾患との関連の度合が得られることにより本発明の効果を示す。
【００５７】
［実験データ］
ＯＭＩＭデータベースのハイパーリンクを用いて構築した遺伝子間関係データを関係データテーブルＨとして入力した。ＯＭＩＭデータベースは、疾患や遺伝子について記述されたページから構成され、各々はその疾患や遺伝子を単位にＩＤとなる番号(６桁の数字)が付与されている。各ページの記述には医学生物学的知見に基づく結び付きから疾患や遺伝子のページへの参照のリンク（ハイパーリンク）が含まれており，それらのページ中に含まれる疾患や遺伝子の番号により参照情報を取得して、関係データテーブルＨを構築した。
【００５８】
［分析対象］
着眼ノードｍとしてメタボリック症候群を構成する肥満、糖尿病、高脂血症、高血圧の４疾患を指定し、入力した。
そして、ノードとして、上記疾患に関係を持つ遺伝子１２４個を用いた。よって、分析対象のノード数は、上記の疾患４＋遺伝子１２４個＝１２８個である。
［入力パラメータ］
擬似クリークの閾値τ、抽出対象とする遺伝子（ノード）の数ｍを入力した。
【００５９】
［関係データの構成方法］
ネットワークデータである関係データＧ、遺伝子のＩＤをノードとしたとき、遺伝子ｉと遺伝子ｊの関係からエッジをｇｉｊとする。そして、ＯＭＩＭデータベースからの関係の有無に応じて、それぞれｇｉｊ＝１、ｇｉｊ＝０とし、ｉを行、ｊを列とした要素ｇｉｊからなる関係データＧを生成した。なお、分析の際には疾患のノードも遺伝子のノードと同様に扱ってデータを構成した。
【００６０】
図１６〜図１８は、対応分析で得られたスコアにより、ノードとしての遺伝子１２４個＋疾患４個を並べた結果を示す図である。同図においては、４疾患（糖尿病、高脂血症、高血圧、肥満）のノードを含む１８８クリーク（横軸）を取り上げ、それに含まれる１２８ノード（１２４の遺伝子ノードと４つの疾患ノード、縦軸）について対応分析（からの第１成分のスコア）により並びを得て、描かれている。同図により、４つの疾患との関連による遺伝子の並びが得られることが確認できる。この遺伝子の並びを用いて疾患の近傍の遺伝子を特定することにより、当該疾患に関連の深い遺伝子群を選定可能であることが示されている。
また、同図においては、予め記憶部１３０あるいは他の記憶手段に記憶されている、各遺伝子に関連する疾患の情報（ｏ：肥満、ｄ：糖尿病、ｆ：高脂血症、ｈ：高血圧）を読み出し、各遺伝子に対応付けて、当該遺伝子に関連する疾患の情報を出力している。これにより、これまでに上記の疾患に関連するとして知られている遺伝子は、並べ替えられたノード上でも該当する疾患の近傍に位置することがわかる。
【００６１】
なお、上記においては、ノードとして遺伝子と疾患を用いた場合の関係データテーブルＨを入力しているが、ノードとして遺伝子のみを用いた関係データテーブルＨを入力することでもよい。この場合、可視化部１２５は、対応分析の結果によってソートされた遺伝子の並びを出力するとともに、予め記憶部１３０あるいは他の記憶手段に記憶されている、各遺伝子に関連する疾患の情報を読み出し、各遺伝子に対応付けて、当該遺伝子に関連する疾患の情報を出力する。これにより、疾患に関連する遺伝子群を認識することができる。
【００６２】
また、上記においては、ノードして遺伝子と疾患、あるいは、遺伝子のみを用いているが、分析対象のノードを企業とすることができる。ノードを企業とする場合、企業間の取引の有無が記述された関係データＨを入力し、着眼ノードｉｄとして注目する企業のｉｄを入力する。関係データＨは、企業の財務データなどから、企業間の取引関係を抽出し、作成することができる。ノードを企業とすることで、調査対象である注目する企業と関連がある他の企業を関係が深いものから所望の数だけ選定することができるとともに、企業間の関連を視覚化して確認することができる。
【００６３】
なお、上述の評価装置１００は、内部にコンピュータシステムを有している。そして、評価装置１００の入力部１１０及び演算部１２０の動作の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータシステムが読み出して実行することによって、上記処理が行われる。ここでいうコンピュータシステムとは、ＣＰＵ及び各種メモリやＯＳ、周辺機器等のハードウェアを含むものである。
【００６４】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【図面の簡単な説明】
【００６５】
【図１】本発明の一実施形態による評価装置の構成を示すブロック図である。
【図２】同実施形態による評価装置の入力部における処理フローを示す。
【図３】同実施形態による評価装置の演算部における概要処理フローを示す。
【図４】同実施形態による評価装置のクリーク抽出部における処理フローを示す。
【図５】同実施形態による評価装置の行列作成部における処理フローを示す。
【図６】同実施形態による評価装置の対応分析部における処理フローを示す。
【図７】同実施形態による評価装置の抽出対象リスト作成部における処理フローを示す。
【図８】同実施形態による評価装置の可視化部における処理フローを示す。
【図９】同実施形態による関係データテーブルＨのデータ構成例を示す。
【図１０】同実施形態による関係データＧのデータ構成例を示す。
【図１１】同実施形態によるクリーク出力結果テーブルのデータ構成例を示す。
【図１２】同実施形態による行列データＦのデータ構成例を示す。
【図１３】同実施形態による対応分析の結果得られたカテゴリスコアテーブル及びサンプルスコアテーブルのデータ構成例を示す。
【図１４】同実施形態によるソートされたサンプルスコアテーブルのデータ構成例を示す。
【図１５】同実施形態による抽出対象ノードリストの例を示す。
【図１６】同実施形態による評価装置の実験結果で出力された可視化されたノードの並びを示す。
【図１７】同実施形態による評価装置の実験結果で出力された可視化されたノードの並びを示す。
【図１８】同実施形態による評価装置の実験結果で出力された可視化されたノードの並びを示す。
【符号の説明】
【００６６】
１００…評価装置
１１０…入力部
１２０…演算部
１２１…クリーク抽出部
１２２…行列作成部
１２３…対応分析部
１２４…抽出対象リスト作成部
１３０…記憶部
１４０…出力部
【特許請求の範囲】
【請求項１】
相互に関連のあるデータ群より抽出される疑似クリークを構成するための関連度の閾値を記憶する記憶部と、
複数のノードと、当該複数のノードそれぞれについての他のノードとの関連をエッジとして表す関係データの入力を受ける入力部と、
前記入力部に入力された関係データにより示されるグラフにおける極大クリークを抽出し、抽出した極大クリークの全ての組み合わせのうち、前記閾値より大きい関連度を有する極大クリークの組み合わせを選択し、選択した各極大クリークの組み合わせそれぞれについて、当該組み合わせを構成する極大クリークに含まれる前記ノードの和集合からなる擬似クリークを生成して前記記憶部に書き込むクリーク抽出部と、
前記クリーク抽出部により生成された各擬似クリークに含まれる前記ノードを前記記憶部から読み出し、それぞれの前記ノード及びそれぞれの前記擬似クリークを各行及び各列に対応させ、かつ、前記ノードが前記擬似クリークに含まれる場合は当該ノード及び当該擬似クリークに対応する行及び列の要素に１を、含まれない場合は対応する行及び列の要素に０を設定した行列を生成して前記記憶部に書き込む行列作成部と、
前記行列作成部により生成された前記行列を前記記憶部から読み出し、当該行列の対応分析を行い、前記ノードそれぞれのスコアを算出して前記記憶部に書き込む対応分析部と、
前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果を可視化した情報を出力する可視化部と、
を備えることを特徴とする評価装置。
【請求項２】
前記対応分析部は、前記行列の対応分析を行い、前記ノードそれぞれのスコア及び前記擬似クリークそれぞれのスコアを算出して前記記憶部に書き込み、
前記可視化部は、前記対応分析部により算出された前記ノードのスコア及び前記擬似クリークのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果、及び、前記擬似クリークを当該擬似クリークのスコア順に並べた結果と、前記ノードそれぞれが属する前記擬似クリークを可視化した情報を出力する、
ことを特徴とする請求項１に記載の評価装置。
【請求項３】
前記入力部は、さらに、調査対象のノード及びノード数の入力を受けて前記記憶部に記憶し、
前記入力部が入力を受けた前記調査対象のノード及び前記ノード数の情報と、前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べ、この前記ノードをスコア順に並べた結果において、前記調査対象のノードに隣接する他のノードを前記ノード数分特定する抽出対象リスト作成部をさらに備える、
ことを特徴とする請求項１及び請求項２に記載の評価装置。
【請求項４】
前記ノードは、他のノードとの関連であるエッジとして、医学・生物学あるいは取引・資本関係における結びつきを持つノードであることを特徴とする請求項１から請求項３のいずれかの項に記載の評価装置。
【請求項５】
評価装置として用いられるコンピュータを、
相互に関連のあるデータ群より抽出される疑似クリークを構成するための関連度の閾値を記憶する記憶部、
複数のノードと、当該複数のノードそれぞれについての他のノードとの関連をエッジとして表す関係データの入力を受ける入力部、
前記入力部に入力された関係データにより示されるグラフにおける極大クリークを抽出し、抽出した極大クリークの全ての組み合わせのうち、前記閾値より大きい関連度を有する極大クリークの組み合わせを選択し、選択した各極大クリークの組み合わせそれぞれについて、当該組み合わせを構成する極大クリークに含まれる前記ノードの和集合からなる擬似クリークを生成して前記記憶部に書き込むクリーク抽出部、
前記クリーク抽出部により生成された各擬似クリークに含まれる前記ノードを前記記憶部から読み出し、それぞれの前記ノード及びそれぞれの前記擬似クリークを各行及び各列に対応させ、かつ、前記ノードが前記擬似クリークに含まれる場合は当該ノード及び当該擬似クリークに対応する行及び列の要素に１を、含まれない場合は対応する行及び列の要素に０を設定した行列を生成して前記記憶部に書き込む行列作成部、
前記行列作成部により生成された前記行列を前記記憶部から読み出し、当該行列の対応分析を行い、前記ノードそれぞれのスコアを算出して前記記憶部に書き込む対応分析部、
前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果を可視化した情報を出力する可視化部、
として動作させることを特徴とするコンピュータプログラム。
【請求項１】
相互に関連のあるデータ群より抽出される疑似クリークを構成するための関連度の閾値を記憶する記憶部と、
複数のノードと、当該複数のノードそれぞれについての他のノードとの関連をエッジとして表す関係データの入力を受ける入力部と、
前記入力部に入力された関係データにより示されるグラフにおける極大クリークを抽出し、抽出した極大クリークの全ての組み合わせのうち、前記閾値より大きい関連度を有する極大クリークの組み合わせを選択し、選択した各極大クリークの組み合わせそれぞれについて、当該組み合わせを構成する極大クリークに含まれる前記ノードの和集合からなる擬似クリークを生成して前記記憶部に書き込むクリーク抽出部と、
前記クリーク抽出部により生成された各擬似クリークに含まれる前記ノードを前記記憶部から読み出し、それぞれの前記ノード及びそれぞれの前記擬似クリークを各行及び各列に対応させ、かつ、前記ノードが前記擬似クリークに含まれる場合は当該ノード及び当該擬似クリークに対応する行及び列の要素に１を、含まれない場合は対応する行及び列の要素に０を設定した行列を生成して前記記憶部に書き込む行列作成部と、
前記行列作成部により生成された前記行列を前記記憶部から読み出し、当該行列の対応分析を行い、前記ノードそれぞれのスコアを算出して前記記憶部に書き込む対応分析部と、
前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果を可視化した情報を出力する可視化部と、
を備えることを特徴とする評価装置。
【請求項２】
前記対応分析部は、前記行列の対応分析を行い、前記ノードそれぞれのスコア及び前記擬似クリークそれぞれのスコアを算出して前記記憶部に書き込み、
前記可視化部は、前記対応分析部により算出された前記ノードのスコア及び前記擬似クリークのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果、及び、前記擬似クリークを当該擬似クリークのスコア順に並べた結果と、前記ノードそれぞれが属する前記擬似クリークを可視化した情報を出力する、
ことを特徴とする請求項１に記載の評価装置。
【請求項３】
前記入力部は、さらに、調査対象のノード及びノード数の入力を受けて前記記憶部に記憶し、
前記入力部が入力を受けた前記調査対象のノード及び前記ノード数の情報と、前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べ、この前記ノードをスコア順に並べた結果において、前記調査対象のノードに隣接する他のノードを前記ノード数分特定する抽出対象リスト作成部をさらに備える、
ことを特徴とする請求項１及び請求項２に記載の評価装置。
【請求項４】
前記ノードは、他のノードとの関連であるエッジとして、医学・生物学あるいは取引・資本関係における結びつきを持つノードであることを特徴とする請求項１から請求項３のいずれかの項に記載の評価装置。
【請求項５】
評価装置として用いられるコンピュータを、
相互に関連のあるデータ群より抽出される疑似クリークを構成するための関連度の閾値を記憶する記憶部、
複数のノードと、当該複数のノードそれぞれについての他のノードとの関連をエッジとして表す関係データの入力を受ける入力部、
前記入力部に入力された関係データにより示されるグラフにおける極大クリークを抽出し、抽出した極大クリークの全ての組み合わせのうち、前記閾値より大きい関連度を有する極大クリークの組み合わせを選択し、選択した各極大クリークの組み合わせそれぞれについて、当該組み合わせを構成する極大クリークに含まれる前記ノードの和集合からなる擬似クリークを生成して前記記憶部に書き込むクリーク抽出部、
前記クリーク抽出部により生成された各擬似クリークに含まれる前記ノードを前記記憶部から読み出し、それぞれの前記ノード及びそれぞれの前記擬似クリークを各行及び各列に対応させ、かつ、前記ノードが前記擬似クリークに含まれる場合は当該ノード及び当該擬似クリークに対応する行及び列の要素に１を、含まれない場合は対応する行及び列の要素に０を設定した行列を生成して前記記憶部に書き込む行列作成部、
前記行列作成部により生成された前記行列を前記記憶部から読み出し、当該行列の対応分析を行い、前記ノードそれぞれのスコアを算出して前記記憶部に書き込む対応分析部、
前記対応分析部により算出された前記ノードそれぞれのスコアを前記記憶部から読み出し、前記ノードを当該ノードのスコア順に並べた結果を可視化した情報を出力する可視化部、
として動作させることを特徴とするコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１０−１０８１５５（Ｐ２０１０−１０８１５５Ａ）
【公開日】平成２２年５月１３日（２０１０．５．１３）
【国際特許分類】
【出願番号】特願２００８−２７８３８１（Ｐ２００８−２７８３８１）
【出願日】平成２０年１０月２９日（２００８．１０．２９）
【出願人】（０００１０２７２８）株式会社エヌ・ティ・ティ・データ (438)
【Ｆターム（参考）】
【公開日】平成２２年５月１３日（２０１０．５．１３）
【国際特許分類】
【出願日】平成２０年１０月２９日（２００８．１０．２９）
【出願人】（０００１０２７２８）株式会社エヌ・ティ・ティ・データ (438)
【Ｆターム（参考）】
[ Back to top ]