(57)【要約】【課題】対応関係を示すデータ量を削減する。【解決手段】データ構造は、複数の参照元データと参照先データとがエッジを用いて接続可能な対象から生成される。データ構造は、接続された対象から抽出される完全二部グラフを構成する参照元データの数と参照先データの数とがそれぞれ複数である場合に、参照元データと参照先データとの間に仮想ノードを作成することにより生成される。【選択図】図６
2019159432.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが、
複数の参照元データと参照先データとがエッジを用いて接続可能な対象において、
接続された前記対象から完全二部グラフに対応する情報を抽出し、
抽出された情報であって、前記完全二部グラフを構成する参照元データの数と参照先データの数とがそれぞれ複数である場合に、前記参照元データと前記参照先データとの間に仮想ノードを作成する
処理を実行することを特徴とするデータ生成方法。
【請求項２】
前記完全二部グラフを構成する前記参照元データに対して前記参照先データの数が複数であるか否か、及び前記参照先データに対して前記参照元データの数が複数であるか否かを判定し、
前記完全二部グラフを構成する参照元データ又は参照先データのうちの少なくともいずれか一方に対して他方の数が一つであると判定された場合には、前記仮想ノードを生成せずに前記参照元データと前記参照先データとを接続するエッジを維持することを特徴とする請求項１に記載のデータ生成方法。
【請求項３】
前記参照元データと前記参照先データとを対応付ける情報を、前記参照元データと前記仮想ノードとを対応付ける情報、及び前記参照先データと前記仮想ノードとを対応付ける情報に置き換えることを特徴とする請求項１又は２に記載のデータ生成方法。
【請求項４】
前記参照元データと前記仮想ノードとを対応付ける情報が、前記参照元データと前記仮想ノードとの関係を示す情報をさらに含み、前記参照先データと前記仮想ノードとを対応付ける情報が、前記参照先データと前記仮想ノードとの関係を示す情報をさらに含むことを特徴とする請求項３に記載のデータ生成方法。
【請求項５】
前記参照元データの各々が、全ての前記参照先データとそれぞれ１本のエッジで接続されていると判定され、かつ前記参照先データの各々が、全ての前記参照元データとそれぞれ１つのエッジで接続されていると判定される範囲に含まれる前記参照先データと前記参照元データとを接続するグラフを、完全二部グラフとして抽出することを特徴とする請求項１乃至４のいずれか１つに記載のデータ生成方法。
【請求項６】
前記仮想ノードを作成した場合に生成される前記参照元データと前記仮想ノードとを接続するエッジの数及び前記参照先データと前記仮想ノードとを接続するエッジの数、並びに当該仮想ノードを作成した場合に削減される前記参照元データと前記参照先データとを接続するエッジの数を算出し、
前記削減されるエッジの数から前記生成されるエッジの数を減算した数が最も大きくなる仮想ノードを作成することを特徴とする請求項１乃至５のいずれか１つに記載のデータ生成方法。
【請求項７】
前記参照元データに対応する領域の開始位置を特定する座標及び終了位置を特定する座標、若しくは前記参照先データに対応する領域の開始位置を特定する座標及び終了位置を特定する座標、又はこれらの組み合わせを用いて、前記完全二部グラフを抽出することを特徴とする請求項１乃至６のいずれか１つに記載のデータ生成方法。
【請求項８】
前記座標を用いて３個以上の領域が抽出された場合において、抽出された前記領域のうち、一部の領域を除外して仮想ノードを作成することを特徴とする請求項７に記載のデータ生成方法。
【請求項９】
タンパク質のドメイン領域又はゲノム配列内の遺伝子領域を前記参照先データとし、アミノ酸置換に関する情報又は塩基の変異形に関する情報を前記参照元データとする前記完全二部グラフを抽出することを特徴とする請求項１乃至８のいずれか１つに記載のデータ生成方法。
【請求項１０】
参照先ノードの数と参照元ノードの数の総数が６以上であって、二部グラフに含まれる完全二部グラフの参照元データの数と参照先データの数とがそれぞれ複数である場合に、前記参照元データと前記参照先データとの間に仮想ノードを作成する、ことを特徴とする請求項１乃至９のいずれか１つに記載のデータ生成方法。
【請求項１１】
コンピュータに、
複数の参照元データと参照先データとがエッジを用いて接続可能な対象において、
接続された前記対象から完全二部グラフに対応する情報を抽出し、
抽出された情報であって、前記完全二部グラフを構成する参照元データの数と参照先データの数とがそれぞれ複数である場合に、前記参照元データと前記参照先データとの間に仮想ノードを作成する、
処理を実行させることを特徴とするデータ生成プログラム。
【請求項１２】
複数の参照元データと参照先データとがエッジを用いて接続可能な対象において、
接続された前記対象から完全二部グラフに対応する情報を抽出し、
抽出された情報であって、前記完全二部グラフを構成する参照元データの数と参照先データの数とがそれぞれ複数である場合に、前記参照元データと前記参照先データとの間に仮想ノードを作成する、
製造方法により生成され、
学習装置が、前記参照元データ及び前記参照先データと前記仮想ノードとの関係を入力とし、その入力に対するニューラルネットワークの出力結果と当該関係に対応する教師データとを比較し、２つのデータの誤差を削減するように、ニューラルネットワークの中間層から順に入力層までの重みを更新する、データ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ生成方法、データ生成プログラム及びデータ構造に関する。
【背景技術】
【０００２】
データベースにおいては、配列上の特定の領域と、当該領域に含まれるデータとが対応付けられる場合がある。例えば、タンパク質においては、ドメイン領域とアミノ酸変異、ゲノム配列においては、遺伝子領域と塩基変異など、配列における何らかの領域と、当該領域に包含されるデータが含まれる。このような対応関係を有するデータは、例えば機械学習処理に用いられ、設定問題との関連性を判別するために用いられる。そこで、当該領域とデータとの対応関係を表現する技術が知られている。
【０００３】
例えば、ロケーションの離れた複数の記憶手段の間であっても、データの共有又は非共有をファイル単位で管理することのできるデータ管理システムが知られている。当該システムは、ネットワークに複数のデータ管理ユニットが接続されて構成される。データ管理システム内で共有されるファイルには、各ファイルをシステム内で一意に識別可能なフラグ情報が関連付けられている。データ管理ユニットは、このフラグ情報に基づいて、他のデータ管理ユニットから当該フラグ情報に関連付けられたファイルを取得する。
【０００４】
また、分子データベースの検索および指向性分子ライブラリの設計において、蛋白質表面の共通の三次元の構造の表記を利用しながら、これらの共通構造の特徴を決定する方法も知られている。当該方法は、βターン、ループおよび接触面などの蛋白質表面の解析および表記に関し、Ｃα‐Ｃβベクトルとして簡素化されたアミノ酸側鎖の共通の位置および配向を同定する。また、当該方法は、三次元空間内の格子点によって表わされる表面電荷の共通領域を同定し、蛋白質の共通の三次元構造の特徴にマッチする分子を同定する目的で分子データベースを検索するために使用可能な、これらの共通の三次元構造の特徴を提供する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−２４９２９７号公報
【特許文献２】特表２００５−５２９３８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記技術においては、対応関係を示すデータが膨大になるという問題が生じる。例えば、領域とデータとの対応関係を、エッジとノードとを含むグラフ等を用いて表現する際に、対応関係を示すエッジの数が増大する場合がある。
【０００７】
一つの側面では、対応関係を示すデータ量を削減できるデータ生成方法、データ生成プログラム及びデータ構造を提供することを目的とする。
【課題を解決するための手段】
【０００８】
一つの態様において、データ構造は、複数の参照元データと参照先データとがエッジを用いて接続された対象から生成される。データ構造は、接続された対象から抽出される完全二部グラフを構成する参照元データの数と参照先データの数とがそれぞれ複数である場合に、参照元データと参照先データとの間に仮想ノードを作成することにより生成される。
【発明の効果】
【０００９】
一つの態様によれば、対応関係を示すデータ量を削減できる。
【図面の簡単な説明】
【００１０】
【図１】図１は、ゲノム配列内の遺伝子領域と塩基の変異との関係の一例を示す図である。
【図２】図２は、実施例１における完全二部グラフの一例を示す図である。
【図３】図３は、一般技術における重複領域生成処理の一例を示す図である。
【図４】図４は、実施例１における仮想ノード生成処理の一例を示す図である。
【図５】図５は、実施例１における仮想ノード生成結果の一例を示す図である。
【図６】図６は、実施例１における生成装置の一例を示す図である。
【図７】図７は、実施例１における参照先ＤＢの一例を示す図である。
【図８】図８は、実施例１における参照元ＤＢの一例を示す図である。
【図９】図９は、実施例１における関係ＤＢの一例を示す図である。
【図１０】図１０は、実施例１における仮想ノードＤＢの一例を示す図である。
【図１１】図１１は、実施例１における仮想ノード判定処理に用いるデータの一例を示す図である。
【図１２】図１２は、実施例１における仮想ノード生成後の関係ＤＢの一例を示す図である。
【図１３】図１３は、実施例１における生成処理の一例を示すフローチャートである。
【図１４】図１４は、実施例１における機械学習処理の一例を示す図である。
【図１５】図１５は、実施例２におけるタンパク質のドメイン領域とアミノ酸置換との関係の一例を示す図である。
【図１６】図１６は、実施例２における生成装置の一例を示す図である。
【図１７】図１７は、実施例２における重複領域ＤＢの一例を示す図である。
【図１８】図１８は、実施例２における仮想ノード選定処理に用いるデータの一例を示す図である。
【図１９】図１９は、実施例２における生成処理の一例を示すフローチャートである。
【図２０】図２０は、ＲＤＦファイルの一例を示す図である。
【図２１】図２１は、ハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示するデータ生成方法、データ生成プログラム及びデータ構造の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。また、以下に示す各実施例は、矛盾を起こさない範囲で適宜組み合わせてもよい。
【実施例１】
【００１２】
まず、本実施例における後に説明する生成装置２００は、第１の集合に含まれるノードと第２の集合に含まれるノードとがエッジで接続される二部グラフを読み込む。二部グラフは、例えばグラフデータの機械学習処理に用いられる。なお、以下において、第１の集合に含まれるノードを単に「第１ノード」と表記し、第２の集合に含まれるノードを単に「第２ノード」と表記する場合がある。また、「第１ノード」は、参照先データの一例であり、「第２ノード」は、参照元データの一例である。また、本実施例における二部グラフは、有向グラフであってもよく、無向グラフであってもよい。
【００１３】
本実施例において、第１ノードは、例えばタンパク質に存在するドメイン領域、又はゲノム配列内の遺伝子領域に対応し、第２ノードは、例えばアミノ酸置換の情報、又は塩基の変異の情報に対応する。なお、二部グラフの第１ノード及び第２ノードに対応する情報は一例であり、また、例えば第１ノードがゲノム配列内の遺伝子領域に対応し、第２ノードが塩基の変異の情報に対応するような二部グラフであってもよい。
【００１４】
本実施例における二部グラフと、各ノードに対応する情報について、図１を用いて説明する。図１は、ゲノム配列内の遺伝子領域と塩基の変異との関係の一例を示す図である。図１において、ゲノム配列ＧＮ内には遺伝子Ａ及び遺伝子Ｂが存在する。また、遺伝子Ａの領域内には変異Ｖ及び変異Ｘが存在し、遺伝子Ｂの領域内には変異Ｙが存在する。
【００１５】
この場合において、遺伝子Ａ及び遺伝子Ｂを第１ノード、変異Ｖ、変異Ｘ及び変異Ｙを第２ノードとすると、二部グラフ１０ａにより表現できる。二部グラフ１０ａにおいて、遺伝子Ａは、遺伝子Ａの領域内に存在する変異Ｖとエッジ１３ａで接続され、また変異Ｘとエッジ１３ｂで接続される。同様に、遺伝子Ｂは、遺伝子Ｂの領域内に存在する変異Ｙとエッジ１３ｃで接続される。
【００１６】
また、二部グラフ１０ａに示す関係は、テーブル１４においても表現することができる。テーブル１４は、遺伝子と、遺伝子に含まれる変異とを対応付けて記憶する。
【００１７】
ところで、二部グラフに含まれるノードの数が増えると、例えばある第１ノードに対応する第２ノードと、別の第１ノードに対応する第２ノードとが重複して、完全二部グラフを形成する場合がある。本実施例において、完全二部グラフは、第１ノードが、全ての第２ノードとそれぞれ１本のエッジで接続され、かつ、第２ノードが、全ての第１ノードとそれぞれ１本のエッジで接続される二部グラフである。
【００１８】
そこで、生成装置２００は、読み込んだ二部グラフから、完全二部グラフを抽出する。図２は、実施例１における完全二部グラフの一例を示す図である。図２に示すように、完全二部グラフ１０ｂにおける第１ノード１１ａ及び１１ｂは、完全二部グラフ１０ｂに含まれる全ての第２ノード１２ｘ、１２ｙ及び１２ｚと、それぞれ１本のエッジ１３で接続される。すなわち、完全二部グラフ１０ｂにおける第２ノード１２ｘ、１２ｙ及び１２ｚも、完全二部グラフ１０ｂに含まれる全ての第１ノード１１ａ及び１１ｂと、それぞれ１本のエッジ１３で接続される。
【００１９】
次に、生成装置２００は、二部グラフに含まれるエッジの数を削減するために、例えば、抽出された完全二部グラフに対応する仮想ノードを生成する。しかし、仮想ノードを生成することで、エッジの数が逆に増加してしまう場合がある。図３は、一般技術における重複領域生成処理の一例を示す図である。図３に示すテーブル２４は、「参照先ＩＤ（Identifer）」と「参照元ＩＤ」とを対応付けて記憶する。テーブル２４において、「参照先ＩＤ」は、例えばゲノム配列に含まれる遺伝子領域など、参照先データに対応する情報を一意に識別する識別子を記憶する。また、「参照元ＩＤ」は、例えばゲノム配列に含まれる塩基の変異を一意に識別する識別子を記憶する。
【００２０】
図３のテーブル２４に示すような関係は、二部グラフ２０ａのように表現することができる。二部グラフ２０ａは、３個の第１ノード「ドメイン１」乃至「ドメイン３」と、３個の第２ノード「変異１」乃至「変異３」と、５本のエッジ２３ａ乃至２３ｅとを含む。二部グラフ２０ａにおいて、例えば第１ノード「ドメイン１」は、テーブル２４における参照先ＩＤ「domein_1」に対応し、第２ノード「変異１」は参照元ＩＤ「variant_1」に対応する。また、５本のエッジ２３ａ乃至２３ｅは、テーブル２４における各レコードにそれぞれ対応する。
【００２１】
二部グラフ２０ａにおいて、変異２は、二部グラフ２０ａに含まれる全てのドメイン１乃至３と、それぞれ１本のエッジ２３ｂ、２３ｃ及び２３ｄで接続される。すなわち、二部グラフ２０ａに含まれる全てのドメイン１乃至３も、変異２とそれぞれ１本のエッジ２３ｂ、２３ｃ及び２３ｄで接続される。この場合において、ドメイン１乃至３と、変異２とは、完全二部グラフ２０ｂを形成する。
【００２２】
二部グラフ２０ａは、完全二部グラフ２０ｂに対応する仮想ノード２８を生成することにより、グラフ２０ｃに変換される。しかし、グラフ２０ｃにおいては、図３のテーブル２５及び２６に示すように、エッジ２３ｂ乃至２３ｄがエッジ３３ａ乃至３３ｄに置き換わり、また新たなエッジ３３ａが追加されることにより、エッジの数が６本に増加してしまう。
【００２３】
そこで、本実施例における生成装置２００は、二部グラフに含まれる完全二部グラフの参照元データの数と参照先データの数とがそれぞれ複数である場合に、完全二部グラフ部分に対応する仮想ノードを生成する。一方、生成装置２００は、完全二部グラフの参照元データの数と参照先データの数との少なくともいずれかが１個である場合は、仮想ノードの生成を抑止する。
【００２４】
なお、生成装置２００は、二部グラフに含まれる完全二部グラフの参照元データの数と参照先データの数との総計が６以上である場合であって、二部グラフに含まれる完全二部グラフの参照元データの数と参照先データの数とがそれぞれ複数である場合に、完全二部グラフ部分に対応する仮想ノードを生成してもよい。
【００２５】
図４は、実施例１における仮想ノード生成処理の一例を示す図である。図４において、領域Ａ０１はドメインＡ乃至ドメインＣの各ドメインを含み、またデータ１乃至データ１０を含む。図４において、ドメインＡはデータ１乃至データ６を含む。同様に、ドメインＢはデータ４乃至データ８を含み、ドメインＣはデータ８乃至データ１０を含む。
【００２６】
ドメインＡ乃至ドメインＣを第１ノードとし、データ１乃至データ１０を第２ノードとした場合の関係は、二部グラフ２０ｄで表現することができる。二部グラフ２０ｄは、３個の第１ノードと、１０個の第２ノードと、１４本のエッジとを含む。
【００２７】
図４において、ドメインＡとドメインＢとは、データ４乃至データ６を共通して含む。すなわち、ドメインＡ及びドメインＢと、データ４乃至データ６とは、完全二部グラフ２０ｅを形成する。同様に、ドメインＢ及びドメインＣはデータ８を共通して含むので、ドメインＢ及びドメインＣとデータ８とは、完全二部グラフ２０ｆを形成する。
【００２８】
この場合において、本実施例における生成装置２００は、第１ノード及び第２ノードのいずれもが複数である完全二部グラフ２０ｅに対応する仮想ノード２９を生成することにより、完全二部グラフ２０ｅをグラフ２０ｇに変換する。一方、本実施例における生成装置２００は、第２ノードが１個である完全二部グラフ１０ｆに対応する仮想ノードの生成を抑止する。
【００２９】
図５は、実施例１における仮想ノード生成結果の一例を示す図である。図５に示すグラフ２０ｈは、３個の第１ノードと、１０個の第２ノードと、１個の仮想ノードとを有する。また、グラフ２０ｈが含むエッジの数は１３本であり、二部グラフ２０ｄよりも削減されている。
【００３０】
このように、本実施例における生成装置２００は、二部グラフに含まれる完全二部グラフの参照元の数と参照先の数とが複数である場合に、完全二部グラフ部分に対応する仮想ノードを生成するので、学習処理に用いられるグラフを表現するデータ量を抑制できる。
【００３１】
［機能ブロック］
次に、本実施例における生成装置２００について、図６を用いて説明する。図６は、実施例１における生成装置の一例を示す図である。本実施例における生成装置２００は、外部Ｉ／Ｆ（Interface）２１０と、記憶部２２０と、制御部２３０とを有する。
【００３２】
外部Ｉ／Ｆ２１０は、有線又は無線を問わず、生成装置２００の利用者（不図示）の端末（不図示）など、その他のコンピュータ等との通信や入出力を制御する。外部Ｉ／Ｆ２１０は、例えばＮＩＣ（Network  Interface  Card）等の通信インタフェース等であるが、これに限られず、キーボードなどの入力デバイスや、ディスプレイなどの出力デバイスから構成されていてもよい。
【００３３】
記憶部２２０は、例えば制御部２３０が実行するプログラムなどの各種データなどを記憶する記憶装置の一例であり、例えばメモリやプロセッサなどである。記憶部２２０は、参照先ＤＢ２２１、参照元ＤＢ２２２、関係ＤＢ２２３及び仮想ノードＤＢ２２４を有する。なお、以下の説明では、データベース（Database）を「ＤＢ」と表記する場合がある。
【００３４】
参照先ＤＢ２２１は、例えばタンパク質のドメイン領域や、ゲノム配列の遺伝子領域など、二部グラフの参照先となる第１ノードに関する情報を記憶する。図７は、実施例１における参照先ＤＢの一例を示す図である。図７に示すように、参照先ＤＢ２２１は、例えば、「参照先ＩＤ」に対応付けて、「タンパク質ＩＤ」と、「開始位置」及び「終了位置」と、「ドメインＩＤ」とを対応付けて記憶する。なお、参照先ＤＢ２２１に記憶される情報は、例えば後に説明するグラフ抽出部２３１により入力される。参照先ＤＢ２２１は、例えば、参照先１個ごとに１レコードとして記憶する。
【００３５】
図７において、「参照先ＩＤ」は、例えばタンパク質に含まれるドメイン領域などに対応する、第１ノードを一意に識別する情報を示す。「タンパク質ＩＤ」は、当該ドメイン領域が含まれるたんぱく質を一意に識別する情報を示す。「開始位置」及び「終了位置」は、当該ドメイン領域が開始する座標、及び終了する座標を示す。「ドメインＩＤ」は、当該ドメイン領域を一意に識別する情報を示す。
【００３６】
次に、参照元ＤＢ２２２は、例えばタンパク質に含まれるアミノ酸置換や、ゲノム配列に含まれる塩基の変異など、二部グラフの参照元となる第２ノードに関する情報を記憶する。図８は、実施例１における参照元ＤＢの一例を示す図である。図８に示すように、参照元ＤＢ２２２は、例えば、「参照元ＩＤ」に対応付けて、「座標」を記憶する。なお、参照元ＤＢ２２２に記憶される情報は、例えばグラフ抽出部２３１により入力される。参照元ＤＢ２２２は、例えば、変異１個ごとに１レコードとして記憶する。
【００３７】
図８において、「参照元ＩＤ」は、例えばタンパク質に含まれるアミノ酸置換などに対応する、第２ノードを一意に識別する情報を示す。「座標」は、当該アミノ酸置換が存在する座標を示す。
【００３８】
次に、関係ＤＢ２２３は、参照先データと参照元データとの対応関係を記憶する。図９は、実施例１における関係ＤＢの一例を示す図である。図９に示すように、関係ＤＢ２２３は、例えば、「参照先ＩＤ」と「参照元ＩＤ」とを対応付けて記憶する。なお、関係ＤＢ２２３に記憶される情報は、例えばグラフ抽出部２３１により入力され、後に説明する仮想ノード生成部２３３により更新される。関係ＤＢ２２３は、例えば、参照先ＩＤと参照元ＩＤとの対応関係１個ごとに１レコードとして記憶する。すなわち、参照先ＩＤ１個に対して参照元ＩＤが２個対応している場合、関係ＤＢ２２３は参照元ＩＤごとに２個のレコードを記憶する。なお、関係ＤＢ２２３の１個のレコードは、１個のエッジに対応する。
【００３９】
図９において、参照元ＩＤは、参照先ＩＤに対応する参照元データを示す。例えば、参照先ＩＤ「Ａ」に対しては、参照元ＩＤ「１」乃至「６」の６個の参照元データが対応する。同様に、例えば参照先ＩＤ「Ｂ」に対しては、参照元ＩＤ「４」乃至「８」の５個の参照元データが対応する。
【００４０】
この場合において、範囲２２３ｘに含まれる参照先ＩＤ「Ａ」及び「Ｂ」に対応する各第１ノードは、範囲２２３ｘに含まれる全ての参照元ＩＤ「４」乃至「６」に対応する各第２ノードと、それぞれ１本のエッジで接続される。つまり、範囲２２３ｘに含まれる参照元ＩＤ「４」乃至「６」に対応する各第２ノードは、範囲２２３ｘに含まれる全ての参照先ＩＤ「Ａ」及び「Ｂ」に対応する各第１ノードと、それぞれ１本のエッジで接続される。すなわち、参照先ＩＤ「Ａ」及び「Ｂ」に対応する各第１ノードと参照元ＩＤ「４」乃至「６」に対応する各第２ノードとは、完全二部グラフを形成する。同様に、範囲２２３ｚに含まれる参照先ＩＤ「Ｂ」及び「Ｃ」に対応する各第１ノードと、参照元ＩＤ「８」に対応する第２ノードとは、完全二部グラフを形成する。
【００４１】
次に、仮想ノードＤＢ２２４は、完全二部グラフ対応して生成される仮想ノードに関する情報を記憶する。図１０は、実施例１における仮想ノードＤＢの一例を示す図である。図１０に示すように、仮想ノードＤＢ２２４は、「仮想ノードＩＤ」に対応付けて、「参照先ＩＤ」を記憶する。なお、仮想ノードＤＢ２２４に記憶される情報は、例えば仮想ノード生成部２３３により入力される。
【００４２】
図１０において、「仮想ノードＩＤ」は、完全二部グラフに対応する仮想ノードを一意に識別する情報を示す。「参照先ＩＤ」は、当該仮想ノードと対応付けられる第１ノードを一意に識別する。図１０は、例えば図９の範囲２２３ｘに含まれる、参照先ＩＤ「Ａ」及び「Ｂ」に対応する各第１ノードと参照元ＩＤ「４」乃至「６」に対応する各第２ノードが形成する完全二部グラフに対応する仮想ノードに関するレコードの一例である。図１０に示すように、仮想ノードＤＢ２２４は、例えば、仮想ノードと第１ノードとの対応関係１個ごとに１レコードとして記憶する。すなわち、仮想ノード１個に対して第１ノードが２個対応している場合、仮想ノードＤＢ２２４は第１ノードの参照先ＩＤごとに２個のレコードを記憶する。なお、仮想ノードＤＢ２２４の１個のレコードは、１個のエッジに対応する。
【００４３】
図６に戻って、制御部２３０は、生成装置２００全体を司る処理部であり、例えばプロセッサなどである。制御部２３０は、グラフ抽出部２３１、判定部２３２、仮想ノード生成部２３３及び出力部２３４を有する。なお、グラフ抽出部２３１、判定部２３２、仮想ノード生成部２３３及び出力部２３４は、プロセッサが有する電子回路の一例やプロセッサが実行するプロセスの一例である。
【００４４】
グラフ抽出部２３１は、二部グラフのデータから、完全二部グラフを形成する部分を抽出する。例えば、グラフ抽出部２３１は、外部Ｉ／Ｆ２１０を通じて、生成装置２００の利用者の端末から、二部グラフのデータを含む、データ生成の開始指示を受信する。グラフ抽出部２３１は、開始指示に含まれる二部グラフのデータから、遺伝子領域やタンパク質のドメイン領域などの参照先データに関する情報を抽出して、参照先ＩＤを付与して参照先ＤＢ２２１に記憶する。同様に、グラフ抽出部２３１は、二部グラフのデータから遺伝子変異やアミノ酸置換などの参照元データに関する情報を抽出して、参照先ＩＤを付与して参照元ＤＢ２２２に記憶する。また、グラフ抽出部２３１は、完全二部グラフを形成する部分を抽出し、判定部２３２に出力する。
【００４５】
判定部２３２は、抽出された完全二部グラフに対応する仮想ノードを生成するか否かを判定する。判定部２３２は、例えば完全二部グラフに対応する仮想ノードを生成することにより、二部グラフに含まれるエッジの数を削減できるか否かを判定する。
【００４６】
判定部２３２は、例えば、完全二部グラフに含まれる参照先ノードと参照元ノードとの両方が複数であるか否かを判定する。判定部２３２は、参照先ノードと参照元ノードとの両方が複数であると判定した完全二部グラフに関する情報を、仮想ノード生成部２３３に出力する。判定部２３２は、参照先ノードと参照元ノードとのうち少なくともいずれかが複数ではないと判定した場合、完全二部グラフに関する情報の出力を抑制する。
【００４７】
なお、判定部２３２は、完全二部グラフに含まれる参照先ノードの数と参照元ノードの数の総数が６以上であるか否かを判定してもよい。このとき、判定部２３２は、参照先ノードの数と参照元ノードの数の総数が６以上であって、二部グラフに含まれる完全二部グラフの参照元データの数と参照先データの数とがそれぞれ複数であると判定した完全二部グラフに関する情報を、仮想ノード生成部２３３に出力する。判定部２３２は、参照先ノードの数と参照元ノードの数の総数が６以上であって、二部グラフに含まれる完全二部グラフの参照元データの数と参照先データの数とがそれぞれ複数でないと判定した場合、完全二部グラフに関する情報の出力を抑制する。
【００４８】
図１１は、実施例１における仮想ノード判定処理に用いるデータの一例を示す図である。図１１に示すように、判定部２３２は、対応する仮想ノードを生成すると判定した完全二部グラフに対応付けて、仮想ノードＩＤを生成する。本実施例において、判定部２３２は、例えば、完全二部グラフに含まれる参照先ノードと参照元ノードとの両方が複数である場合に限り、仮想ノードＩＤを生成する。
【００４９】
例えば、判定部２３２は、参照先ＩＤ「Ａ」及び「Ｂ」に対応する各第１ノードと、参照元ＩＤ「４」乃至「６」に対応する各第２ノードとを含む完全二部グラフに対応付けて、仮想ノードＩＤ「Ｖ１」を生成する。一方、判定部２３２は、参照先ＩＤ「Ｂ」及び「Ｃ」に対応する各第１ノードと、参照元ＩＤ「８」に対応する第２ノードとを含む完全二部グラフに対しては、仮想ノードＩＤを生成しない。そして、判定部２３２は、生成した仮想ノードＩＤ「Ｖ１」と、対応する完全二部グラフに関する情報とを、仮想ノード生成部２３３に出力する。
【００５０】
仮想ノード生成部２３３は、完全二部グラフを、対応する仮想ノードを含むグラフに変換する。仮想ノード生成部２３３は、判定部２３２から、仮想ノードＩＤと、対応する完全二部グラフに関する情報が入力されると、仮想ノードＤＢ２２４に、当該完全二部グラフに対応する仮想ノードに関する情報を記憶する。
【００５１】
また、仮想ノード生成部２３３は、仮想ノードに関する情報を用いて、図９に示す関係ＤＢ２２３を更新する。図１２は、実施例１における仮想ノード生成後の関係ＤＢの一例を示す図である。図１２に示すように、仮想ノード生成部２３３は、図９に示す関係ＤＢ２２３の範囲２２３ｘを、出力された仮想ノードＩＤ「Ｖ１」を用いて、範囲２２３ｙに示すように更新する。一方、仮想ノード生成部２３３は、関係ＤＢ２２３の範囲２２３ｚについては、仮想ノードＩＤが出力されていないので更新しない。
【００５２】
出力部２３４は、完全二部グラフを、対応する仮想ノードを用いて変換したグラフを含むグラフに関する情報を出力する。出力部２３４は、例えば図１２に示す更新後の関係ＤＢ２２３、及び仮想ノードＤＢ２２４を参照して、図５に示すようなグラフ２０ｈを生成する。そして、出力部２３４は、生成したグラフ２０ｈを、外部Ｉ／Ｆ２１０を通じて、例えば生成装置２００の利用者の端末に出力する。
【００５３】
［処理の流れ］
次に、本実施例における処理について、図１３を用いて説明する。図１３は、実施例１における生成処理の一例を示すフローチャートである。図１３に示すように、生成装置２００のグラフ抽出部２３１は、例えば外部Ｉ／Ｆ２１０を通じて、生成装置２００の利用者の端末から、二部グラフのデータを含むデータ生成の開始指示を受け付けるまで待機する（Ｓ１０：Ｎｏ）。
【００５４】
グラフ抽出部２３１は、データ生成の開始指示を受け付けたと判定した場合（Ｓ１０：Ｙｅｓ）、二部グラフのデータから、領域とデータとの組み合わせを生成し、図９に示すように関係ＤＢ２２３に記憶する（Ｓ１１）。
【００５５】
次に、判定部２３２は、関係ＤＢ２２３に記憶された領域とデータとの組み合わせのうち、未処理の組み合わせを選択する（Ｓ１２）。例えば、図９に示す参照先ＩＤ「Ａ」の第１ノードと、対応する参照元ＩＤ「１」乃至「６」との組み合わせを選択する。
【００５６】
次に、判定部２３２は、当該組み合わせとその他の組み合わせとの間で、範囲が重複するか否かを判定する（Ｓ２１）。判定部２３２は、重複範囲が有ると判定した場合（Ｓ２１：Ｙｅｓ）、当該組み合わせと重複範囲があるその他の組み合わせとを、仮想ノードの候補として、記憶部２２０に登録し（Ｓ２２）、Ｓ３１に移行する。一方、判定部２３２は、重複範囲がないと判定した場合（Ｓ２１：Ｎｏ）、仮想ノードの候補を登録せずにＳ３１に移行する。
【００５７】
次に、判定部２３２は、記憶部２２０に登録された仮想ノードの候補において、領域とデータとの両方が複数であるか否かを判定する（Ｓ３１）。判定部２３２は、領域とデータとの両方が複数であると判定した場合（Ｓ３１：Ｙｅｓ）、当該仮想ノードの候補に対応する仮想ノードＩＤを生成する。そして、仮想ノード生成部２３３は、仮想ノードＩＤに対応する情報を仮想ノードＤＢ２２４に登録するとともに、関係ＤＢ２２３を更新し（Ｓ３２）、Ｓ４１に移行する。一方、判定部２３２は、領域とデータとのうち、少なくともいずれかが複数ではないと判定した場合（Ｓ３１：Ｎｏ）、仮想ノードＩＤに対応する情報を登録せずに、Ｓ４１に移行する。
【００５８】
そして、判定部２３２は、全ての領域とデータとの組み合わせについて処理が完了するまで（Ｓ４１：Ｎｏ）、Ｓ１２に戻って処理を繰り返す。一方、出力部２３４は、全ての領域とデータとの組み合わせについて処理が完了した場合（Ｓ４１：Ｙｅｓ）、処理結果を出力し（Ｓ４２）、処理を終了する。
【００５９】
［効果］
以上説明したように、本実施例におけるデータ構造は、複数の参照元データと参照先データとがエッジを用いて接続された対象から生成される。データ構造は、接続された対象から抽出される完全二部グラフを構成する参照元データの数と参照先データの数とがそれぞれ複数である場合に、参照元データと参照先データとの間に仮想ノードを作成することにより生成される。データ構造は、学習装置が、参照元データ及び参照先データと仮想ノードとの関係を学習する処理に用いられる。これにより、生成装置は、機械学習処理に用いられる、対応関係を示すデータ量を削減できる。
【００６０】
本実施例において生成されるデータ構造を用いた機械学習処理について、図１４を用いて説明する。図１４は、実施例１における機械学習処理の一例を示す図である。本実施例における機械学習処理は、例えばＲＮＮ（再帰型ニューラルネットワーク：Recurrent  Neural  Network）等の系列データを分析する手法が用いられる。なお、機械学習処理においては、例えばＣＮＮ（Convolutional  Neural  Network）など他のニューラルネットワークを採用することもできる。
【００６１】
図１４に示す学習は、ニューラルネットワークを有する。ニューラルネットワークは、入力層、中間層、及び出力層の３層から構成される。各層は１つ以上のニューロンから構成される。また、各層のニューロンは、他の層の少なくとも１つのニューロンと接続する。具体的には、入力層のニューロンは、中間層の少なくとも１つのニューロンと接続し、また、中間層のニューロンは、出力層の少なくとも１つのニューロンと接続する。なお、誤差逆伝播処理では、参照元データ及び参照先データと仮想ノードとの関係を入力とし、その入力に対するニューラルネットワークの出力結果と当該関係に対応する教師データとを比較し、２つのデータの誤差を削減するように、ニューラルネットワークの出力層に近い層（中間層）から順に入力層までの重みを更新する。すなわち、入力データが出力方向とは逆の方向に重みが更新される。例えば、特定の病気へのかかりやすさや薬の副作用の強さに対応する、参照元データ及び参照先データと仮想ノードとの関係である。また、教師データは、特定の病気へのかかりやすさや薬の副作用の強さに関する情報である。
【００６２】
図１４において、グラフＧ１及びＧ２は、機械学習処理に用いられるグラフデータである。本実施例における機械学習処理においては、例えば、グラフＧ１の参照元データである「Ａ社」と、参照先データである事業部「ＡＸ事業部」、格付「ＡＡ」などとの間にどのような関係があるかを分類するための教師データが生成される。
【００６３】
このようなグラフにおいて、例えばグラフＧ１及びＧ２に共通する完全二部グラフがある場合、実施例１又は２において生成されるデータ構造を用いることで、機械学習処理に用いられるデータ量を削減できる。
【００６４】
また、本実施例における機械学習処理においては、生成された教師データを用いて学習済みモデルが生成され、学習モデルを用いた関連性の判別処理が行われる。グラフＧ１１及びＧ１２は、それぞれグラフＧ１及びＧ２を用いた、設定問題との関連性の判別処理の結果である。判別処理の結果、グラフＧ１１においては、格付「ＡＡ」が設定問題との関連性が高い、すなわち判別の推定に有用だったと判別された。一方、グラフＧ１２においては、設定問題との関連性が高いと判別される参照先データはない。このような場合、判別の推定に有用である対応関係について、学習済みモデルのパラメータの重み付けを更新してもよい。
【００６５】
また、本実施例におけるデータ構造を生成する際に、完全二部グラフを構成する参照元データに対して参照先データの数が複数であるか否か、及び参照先データに対して参照元データの数が複数であるか否かを判定してもよい。データ構造を生成する際に、参照元データ又は参照先データのうちの少なくともいずれか一方に対して他方の数が１個であると判定された場合には、仮想ノードを生成せずに参照元データと参照先データとを接続するエッジを維持してもよい。これにより、データ量の削減効果を向上できる。
【００６６】
また、本実施例におけるデータ構造においては、参照元データと参照先データとを対応付ける情報を、参照元データと仮想ノードとを対応付ける情報、及び参照先データと仮想ノードとを対応付ける情報に置き換えてもよい。これにより、仮想ノードを含むグラフを容易に生成できる。
【００６７】
また、本実施例におけるデータ構造を生成する際に抽出される完全二部グラフにおいては、参照元データの各々が、全ての参照先データとそれぞれ１本のエッジで接続され、かつ参照先データの各々が、全ての参照元データとそれぞれ１本のエッジで接続される。これにより、情報の漏れや重複がなく、新たなグラフを生成できる。
【００６８】
さらに、タンパク質のドメイン領域又はゲノム配列内の遺伝子領域を参照先データとし、アミノ酸置換に関する情報又は塩基の変異形に関する情報を参照元データとする完全二部グラフを抽出してもよい。これにより、タンパク質や遺伝子に関するグラフを示すデータ量を削減できる。
【実施例２】
【００６９】
ところで、遺伝子領域やタンパク質領域等においては、領域の重複がある場合に完全二部グラフが生じる。この場合において、領域の範囲や変異又は置換の位置は座標で示すことができるので、座標を突き合わせることにより、完全二部グラフの有無を判定することができる。
【００７０】
図１５は、実施例２におけるタンパク質のドメイン領域とアミノ酸置換との関係の一例を示す図である。図１５に示すように、タンパク質ＰＲにおいて、ドメインＡの開始位置は座標ｘ１１であり、終了位置は座標ｘ１２である。同様に、ドメインＢ及びドメインＩの開始位置は、それぞれ座標ｘ２１及び座標ｘ３１であり、終了位置はそれぞれ座標ｘ２２及び座標ｘ３２である。また、アミノ酸置換Ｘ乃至アミノ酸置換Ｚの位置は、それぞれ座標ｘ４１、座標ｘ４２及び座標ｘ４３である。なお、このようなドメインＡ乃至ドメインＩとアミノ酸置換Ｘ乃至アミノ酸置換Ｚとの対応関係は、二部グラフ３０ａにより示される。
【００７１】
また、座標により領域の重複を判定する際、完全二部グラフを生じさせる領域の組み合わせが複数生じる場合が考えられる。例えば、図１５においては、ドメインＡ乃至ドメインＩはいずれも重複するが、ドメインＡ及びドメインＢ、並びにドメインＢ及びドメインＩも同様に重複する。この場合において、複数の領域の組み合わせのうち、最もデータ量の削減効果が大きいものを選択するような構成であってもよい。
【００７２】
そこで、本実施例においては、座標を用いて完全二部グラフが生じる領域の重複を特定し、対応する仮想ノードを生成する構成について説明する。なお、以下において、相互に重複する領域の組み合わせを、単に「重複領域」と表記する場合がある。また、本実施例において、領域が重複する場合は、領域の一部のみが重複する場合に加え、複数の領域が完全に一致する場合、及びある領域が他の領域に包含される場合も含むものとする。
【００７３】
［機能ブロック］
図１６は、実施例２における生成装置の一例を示す図である。なお、以下の実施例において、先に説明した図面に示す部位と同一の部位には同一の符号を付し、重複する説明は省略する。
【００７４】
図１６に示すように、本実施例における生成装置３００は、外部Ｉ／Ｆ２１０と、記憶部３２０と、制御部３３０とを有する。記憶部３２０は、例えば制御部３３０が実行するプログラムなどの各種データなどを記憶する記憶装置の一例であり、例えばメモリやプロセッサなどである。また、記憶部３２０は、参照先ＤＢ２２１、参照元ＤＢ２２２、関係ＤＢ２２３、仮想ノードＤＢ２２４及び重複領域ＤＢ３２５を有する。
【００７５】
重複領域ＤＢ３２５は、仮想ノードを生成する対象となる完全二部グラフの候補となる重複領域に関する情報を記憶する。図１７は、実施例２における重複領域ＤＢの一例を示す図である。図１７に示すように、重複領域ＤＢ３２５は、「重複領域ＩＤ」に対応付けて、「タンパク質ＩＤ」と、「領域の組み合わせ」と、「開始位置」及び「終了位置」とを対応付けて記憶する。
【００７６】
図１７において、「重複領域ＩＤ」は、重複領域を一意に識別する情報を示す。「領域の組み合わせ」は、当該重複領域に含まれる領域の組み合わせを示す。「開始位置」及び「終了位置」は、それぞれの領域が重複する部分の開始位置の座標及び終了位置の座標を示す。
【００７７】
なお、図１７の範囲３２５ｘに示すように、重複領域は連続する領域の組み合わせではなく、中間の領域を除外したものであってもよい。
【００７８】
制御部３３０は、生成装置３００全体を司る処理部であり、例えばプロセッサなどである。制御部３３０は、グラフ抽出部３３１、重複領域特定部３３５、仮想ノード選定部３３６、仮想ノード生成部３３３及び出力部２３４を有する。なお、グラフ抽出部３３１、重複領域特定部３３５、仮想ノード選定部３３６、仮想ノード生成部３３３及び出力部２３４は、プロセッサが有する電子回路の一例やプロセッサが実行するプロセスの一例である。
【００７９】
グラフ抽出部３３１は、実施例１におけるグラフ抽出部２３１と同様に、二部グラフに関する情報を参照先ＤＢ２２１及び参照元ＤＢ２２２に記憶する。ただし、グラフ抽出部３３１は、完全二部グラフを形成する部分を抽出する処理を行わない。
【００８０】
重複領域特定部３３５は、二部グラフのデータから、完全二部グラフを形成する複数の重複領域を特定する。例えば、重複領域特定部３３５は、参照先ＤＢ２２１を参照して、タンパク質ＩＤが同一（例えば「Ｐ０ＸＸＸ１」）である複数の領域を抽出する。
【００８１】
次に、重複領域特定部３３５は、抽出した１個の領域の開始位置が、もう１個の領域の終了位置よりも前であるか否かを判定する。重複領域特定部３３５は、領域の開始位置がもう１個の領域の終了位置よりも前であると判定された領域の組み合わせを、重複領域ＤＢ３２５に記憶する。
【００８２】
重複領域特定部３３５は、例えば、参照先ＩＤ「Ａ」の領域の開始位置の座標が「５」であり、参照先ＩＤ「Ｂ」の領域の終了位置の座標「１３２」よりも前であるため、参照先ＩＤ「Ａ」及び「Ｂ」の組み合わせを重複領域ＤＢ３２５に記憶する。なお、重複領域特定部３３５は、例えば、３個以上の領域の組み合わせ、及び中間の領域を除外した領域の組み合わせを含む、全ての領域の組み合わせについて処理を繰り返す。
【００８３】
仮想ノード選定部３３６は、重複領域のうち、最もデータ量の削減効果が高いものを選定する。図１８は、実施例２における仮想ノード選定処理に用いるデータの一例を示す図である。例えば、図１８に示すように、仮想ノード選定部３３６は、重複領域ＤＢ３２５を参照し、各重複領域において生じる完全二部グラフを仮想ノードにした場合のデータ量の削減効果を算出し、記憶部３２０に記憶する。
【００８４】
なお、本実施例において、データ量の削減効果として、仮想ノードを生成することにより削減されるエッジの数から、追加されるエッジの数を差し引いたものを用いる。データ量の削減効果は、例えば、完全二部グラフに含まれる参照先データの数と、完全二部グラフに含まれる参照元データの数とを用いて、例えば以下のような数式により算出される。
【００８５】
削減効果＝参照先データ数×参照元データ数−（参照先データ数＋参照元データ数）
【００８６】
例えば、参照元データの数が「８５４」である場合のデータ量の削減効果は、参照先データの数が「２」であれば「８５２」であるが、参照先データの数が「３」であれば「１７０５」となる。同様に、例えば、参照元データの数が「８３６」である場合のデータ量の削減効果は、参照先データの数が「２」であれば「８３４」であるが、参照先データの数が「４」であれば「２５０４」となる。
【００８７】
次に、仮想ノード選定部３３６は、図１８に示す各レコードのうち、最もデータ量の削減効果が大きいものを選定する。例えば、仮想ノード選定部３３６は、削減効果が「２５０４」である、重複領域ＩＤ「ｖ１９」の重複領域を選定する。そして、仮想ノード選定部３３６は、選定した重複領域に関する情報を、仮想ノード生成部３３３に出力する。なお、仮想ノード選定部３３６は、複数の重複領域が、それぞれ独立して完全二部グラフを生じさせる場合等においては、複数の重複領域を選定してもよい。
【００８８】
仮想ノード生成部３３３は、重複領域から生じる完全二部グラフに対応する仮想ノードを生成する。仮想ノード生成部２３３は、仮想ノード選定部３３６から重複領域に関する情報が入力されると、仮想ノードＤＢ２２４に、当該重複領域から生じる完全二部グラフに対応する仮想ノードに関する情報を記憶する。
【００８９】
［処理の流れ］
次に、本実施例における処理について、図１９を用いて説明する。図１９は、実施例２における生成処理の一例を示すフローチャートである。図１９に示すように、生成装置３００のグラフ抽出部３３１は、例えば外部Ｉ／Ｆ２１０を通じて、生成装置３００の利用者の端末から、二部グラフのデータを含むデータ生成の開始指示を受け付けるまで待機する（Ｓ１００：Ｎｏ）。
【００９０】
グラフ抽出部３３１は、データ生成の開始指示を受け付けたと判定した場合（Ｓ１００：Ｙｅｓ）、二部グラフのデータから、領域とデータとの組み合わせを生成し、図９に示すように関係ＤＢ２２３に記憶する。次に、重複領域特定部３３５は、二部グラフのデータから、タンパク質ＩＤが共通する領域の組み合わせを生成する（Ｓ１１０）。
【００９１】
次に、重複領域特定部３３５は、生成された領域の組み合わせのうち、未処理の領域の組み合わせを選択する（Ｓ１１１）。例えば、図１７に示す重複領域ＩＤ「ｖ１２」に対応する対応する領域の組み合わせ「Ａ」及び「Ｃ」を選択する。
【００９２】
次に、重複領域特定部３３５は、当該組み合わせに含まれる領域の開始位置の座標のうち最も大きい座標「Ｓ＿Ｍａｘ」と、当該組み合わせに含まれる領域の終了位置の座標のうち最も小さい座標「Ｅ＿ｍｉｎ」とを特定する（Ｓ１１２）。そして、重複領域特定部３３５は、領域の組み合わせの範囲が重複するか否か、すなわち「Ｓ＿Ｍａｘ」が「Ｅ＿ｍｉｎ」以下であるか否かを判定する（Ｓ１２０）。
【００９３】
重複領域特定部３３５は、範囲が重複すると判定した場合（Ｓ１２０：Ｙｅｓ）、当該領域の組み合わせを、重複領域として、重複領域ＤＢ３２５に登録し（Ｓ１２１）、Ｓ１４０に移行する。一方、重複領域特定部３３５は、重複範囲がないと判定した場合（Ｓ１２０：Ｎｏ）、重複領域を登録せずにＳ１４０に移行する。
【００９４】
重複領域特定部３３５は、全ての領域の組み合わせについて処理が完了するまで（Ｓ１４０：Ｎｏ）、Ｓ１１１に戻って処理を繰り返す。全ての領域の組み合わせについて処理が完了した場合（Ｓ１４０：Ｙｅｓ）、仮想ノード選定部３３６は、重複領域ＤＢ３２５を参照し、未処理の重複領域を選択する（Ｓ１４１）。
【００９５】
次に、仮想ノード選定部３３６は、未処理の重複領域に対応する変異の数が１を超えるか否かを判定する（Ｓ１５０）。仮想ノード選定部３３６は、未処理の重複領域に対応する変異の数が１を超えないと判定した場合（Ｓ１５０：Ｎｏ）、重複領域ＤＢ３２５に記憶されている、当該重複領域に全ての領域が含まれるその他の重複領域を、処理対象から除外し（Ｓ１５１）、Ｓ１７０に移行する。
【００９６】
一方、仮想ノード選定部３３６は、未処理の重複領域に対応する変異の数が１を超えると判定した場合（Ｓ１５０：Ｙｅｓ）、当該重複領域に対応する完全二部グラフを、対応する仮想ノードを用いて変換した場合における削減効果を算出する（Ｓ１５２）。そして、仮想ノード選定部３３６は、削減効果が正の数であるか否かを判定する（Ｓ１６０）。仮想ノード選定部３３６は、削減効果が０以下であると判定した場合（Ｓ１６０：Ｎｏ）、Ｓ１７０に移行する。
【００９７】
一方、仮想ノード選定部３３６は、削減効果が正の数であると判定した場合（Ｓ１６０：Ｙｅｓ）、処理済みの重複領域のうち、最も削減効果が大きいものを選択し（Ｓ１６１）、その後Ｓ１５１に移行する。
【００９８】
そして、仮想ノード選定部３３６は、全ての重複領域について処理が完了するまで（Ｓ１７０：Ｎｏ）、Ｓ１４１に戻って処理を繰り返す。一方、仮想ノード生成部３３３は、全ての重複領域について処理が完了した場合（Ｓ１７０：Ｙｅｓ）、最も削減効果の大きい重複領域に対応する仮想ノードを生成する（Ｓ１７１）。そして、出力部２３４は、処理結果を出力し（Ｓ１７２）、処理を終了する。
【００９９】
［効果］
以上説明したように、本実施例においては、生成装置３００は、仮想ノードを作成した場合に生成される参照元データと仮想ノードとを接続するエッジの数及び参照先データと仮想ノードとを接続するエッジの数を算出してもよい。また、生成装置３００は、仮想ノードを作成した場合に削減される参照元データと参照先データとを接続するエッジの数を算出してもよい。さらに、生成装置３００は、削減されるエッジの数から生成されるエッジの数を減算した数が最も大きくなる仮想ノードを作成してもよい。これにより、最もデータ量の削減効果の大きいグラフを生成できる。
【０１００】
また、参照元データに対応する領域の開始位置を特定する座標及び終了位置を特定する座標、並びに参照先データに対応する領域の開始位置を特定する座標及び終了位置を特定する座標のうち、少なくともいずれかを用いて、完全二部グラフを抽出してもよい。これにより、座標により特定される領域を対象として、データ量を削減したグラフを生成できる。なお、座標を用いて３個以上の領域が抽出された場合において、抽出された領域のうち、一部の領域を除外して仮想ノードを作成してもよい。
【実施例３】
【０１０１】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。
【０１０２】
また、記憶部２２０は、参照先ＤＢ２２１、参照元ＤＢ２２２、関係ＤＢ２２３及び仮想ノードＤＢ２２４にそれぞれ記憶される情報を、１個のテーブルで一括して記憶するような構成であってもよい。この場合において、記憶部２２０は、例えばＲＤＦ（Resource  Description  Framework）ファイルによって、各情報を一括して記憶することができる。
【０１０３】
図２０は、ＲＤＦファイルの一例を示す図である。図２０に示すように、ＲＤＦファイルは、「ｓ」（主体）と、「ｐ」（属性）と、「ｏ」（対象）とを対応付けて記憶する。
【０１０４】
図２０におけるＲＤＦファイルは、主体と対象との関係を「属性」で表現する。例えば、ＲＤＦファイルは、領域「Ａ」の「開始座標」は「４」であることを記憶する。また、ＲＤＦファイルは、領域「Ａ」には「変異」である「１」が含まれ、変異「１」の「座標」は「４」であることを記憶する。
【０１０５】
このように、データ構造は、参照元データと仮想ノードとの関係を示す情報、及び参照先データと仮想ノードとの関係を示す情報をさらに含んでもよい。これにより、複数の情報が１個のテーブルに集約される。
【０１０６】
また、各実施例において生成されるデータ構造は、変換の対象とする完全二部グラフが有向グラフであってもよく、また無向グラフであってもよい。
【０１０７】
また、生成装置２００又は３００で行われる各種の処理機能は、プロセッサ上で、その全部又は任意の一部を実行するようにしてもよい。また、各種処理機能は、プロセッサで解析実行されるプログラム上、又はワイヤードロジックによるハードウェア上で、その全部又は任意の一部を実行するようにしてもよいことは言うまでもない。
【０１０８】
ところで、上記の実施例で説明した各種の処理は、予め用意されたプログラムをコンピュータで実行することで実現できる。そこで、以下では、上記の実施例と同様の機能を有するプログラムを実行するコンピュータ（ハードウェア）の一例を説明する。図２１は、ハードウェア構成の一例を示す図である。なお、以下においては、実施例１における生成装置２００として機能するコンピュータ１を例として説明するが、実施例２及び３における対応する各装置についても同様である。
【０１０９】
図２１に示すように、コンピュータ１は、各種演算処理を実行するプロセッサ１０１と、データ入力を受け付ける入力装置１０２と、モニタ１０３と、スピーカ１０４とを有する。また、コンピュータ１は、記憶媒体からプログラム等を読み取る媒体読取装置１０５と、各種装置と接続するためのインタフェース装置１０６と、有線又は無線により外部機器と通信接続するための通信装置１０７とを有する。また、コンピュータ１は、各種情報を一時記憶するメモリ１０８と、ハードディスク装置１０９とを有する。また、コンピュータ１内の各部（１０１〜１０９）は、バス１１０に接続される。
【０１１０】
プロセッサ１０１の一例としては、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）、ＭＣＵ（Micro  Controller  Unit）等のマイクロ・コンピュータ）が挙げられる。プロセッサ１０１の一例として、ＤＳＰ（Digital  Signal  Processor）、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）、ＰＬＤ（Programmable  Logic  Device）等であってもよい。また、メモリ１０８の一例としては、ＳＤＲＡＭ（Synchronous  Dynamic  Random  Access  Memory）等のＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ等が挙げられる。
【０１１１】
ハードディスク装置１０９には、上記の実施例で説明したグラフ抽出部２３１、判定部２３２、仮想ノード生成部２３３及び出力部２３４における各種の処理を実行するためのプログラム１１１が記憶される。また、ハードディスク装置１０９には、プログラム１１１が参照する各種データ１１２（参照先ＤＢ２２１、参照元ＤＢ２２２、関係ＤＢ２２３及び仮想ノードＤＢ２２４など）が記憶される。入力装置１０２は、例えば、コンピュータ１の操作者から操作情報の入力を受け付ける。モニタ１０３は、例えば、操作者が操作する各種画面を表示する。インタフェース装置１０６は、例えば印刷装置等が接続される。通信装置１０７は、ＬＡＮ（Local  Area  Network）等の通信ネットワークと接続され、通信ネットワークを介した外部機器との間で各種情報をやりとりする。入力装置１０２、モニタ１０３、インタフェース装置１０６及び通信装置１０７は、各機能部の説明時に示した外部Ｉ／Ｆ２１０に該当する。
【０１１２】
プロセッサ１０１は、ハードディスク装置１０９に記憶されたプログラム１１１を読み出して、メモリ１０８に展開して実行することで、各種の処理を行う。なお、プログラム１１１は、ハードディスク装置１０９に記憶されていなくてもよい。例えば、コンピュータ１が読み取り可能な記憶媒体に記憶されたプログラム１１１を読み出して実行するようにしてもよい。コンピュータ１が読み取り可能な記憶媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤ（Digital  Versatile  Disk）、ＵＳＢ（Universal  Serial  Bus）メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ等に接続された装置にこのプログラム１１１を記憶させておき、コンピュータ１がこれらからプログラム１１１を読み出して実行するようにしてもよい。
【符号の説明】
【０１１３】
２００、３００  生成装置
２１０  外部Ｉ／Ｆ
２２０、３２０  記憶部
２２１  参照先ＤＢ
２２２  参照元ＤＢ
２２３  関係ＤＢ
２２４  仮想ノードＤＢ
３２５  重複領域ＤＢ
２３０、３３０  制御部
２３１  グラフ抽出部
２３２  判定部
２３３、３３３  仮想ノード生成部
２３４  出力部
３３５  重複領域特定部
３３６  仮想ノード選定部
【図１】
2019159432.tif 000003
【図２】
2019159432.tif 000004
【図３】
2019159432.tif 000005
【図４】
2019159432.tif 000006
【図５】
2019159432.tif 000007
【図６】
2019159432.tif 000008
【図７】
2019159432.tif 000009
【図８】
2019159432.tif 000010
【図９】
2019159432.tif 000011
【図１０】
2019159432.tif 000012
【図１１】
2019159432.tif 000013
【図１２】
2019159432.tif 000014
【図１３】
2019159432.tif 000015
【図１４】
2019159432.tif 000016
【図１５】
2019159432.tif 000017
【図１６】
2019159432.tif 000018
【図１７】
2019159432.tif 000019
【図１８】
2019159432.tif 000020
【図１９】
2019159432.tif 000021
【図２０】
2019159432.tif 000022
【図２１】
2019159432.tif 000023