TOP > 国内特許検索 > 分子間の類似度を評価するための高速グラフマッチ検索装置及び方法

分子間の類似度を評価するための高速グラフマッチ検索装置及び方法 コモンズ

国内特許コード P120007509
整理番号 24
掲載日 2012年5月10日
出願番号 特願2010-031526
公開番号 特開2011-170444
登録番号 特許第5484946号
出願日 平成22年2月16日(2010.2.16)
公開日 平成23年9月1日(2011.9.1)
登録日 平成26年2月28日(2014.2.28)
発明者
  • 白井 剛
出願人
  • 学校法人関西文理総合学園
発明の名称 分子間の類似度を評価するための高速グラフマッチ検索装置及び方法 コモンズ
発明の概要 【課題】分子グラフに関して、2分子間の原子対応を求め該対応に基づいて2分子を重ね合わせする方法を実現する高速グラフマッチアルゴリズムを提供する。
【解決手段】第1の分子Aの夫々の原子と第2の分子Bの夫々の原子を対応付け(m(Ai)=Bk)て重ね合わせ、ABの間の最適な原子間対応を求める方法であって、S1(Ai,Bk)、S2(Ai,Bk)及びS3(Ai,Bk)の各々を全ての{i,k}の組について求める工程と、その工程にて最大のS3(Ai,Bk)を算出した原子(Ai,Bk)の対応から開始して、未対応の原子の対の中で最大のS3(Aj,Bl)を持つものを対応させることを、対応可能原子の組が無くなるまで続けたときの全体の対応におけるグラフマッチスコアM(A,B)を求める工程と、その工程におけるM(A、B)が閾値より大きいならば、AとBにつき重ね合わせを出力する工程を含む方法を提供する。
【選択図】図2
従来技術、競合技術の概要



医薬や農薬の分子設計において、2つの分子に係る分子構造を仮想空間にて重ね合わせすることが頻繁に行われる。図13は、そのような、2つの分子(Cholic acid[CHD]とCorticosteron[COR])を仮想空間にて重ね合わせすることを模式的に示す図である。しかしながら、2つの分子についての最適な重ね合わせを探索し決定することは非常に困難な問題である。





例えば、分子Aと分子Bとの重ね合わせの問題について、片方の分子Aを『CMP』とした場合に、それに基づき重ね合わせにて探索可能な重ね合わせの対象の分子Bを求める場合を検討する。ここで「探索可能な」というのは、全探査を8時間労働・週休2日の労働時間で50年程度行って、探索が解決され得ると想定される、という程の意味である。例えば、人手による計算による場合では、分子BがCysteinである場合、1.3×10通り程度の重ね合わせの計算を行い、最適な重ね合わせを求めることが可能となる(図14(a))。同様に、デスクトップコンピュータによる場合では、分子BがDiaminopimelateである場合、1.5×1015通り程度の重ね合わせの計算を行い、最適な重ね合わせを求めることが可能となる(図14(b))。更に同様に、超高速度電子計算機による場合でも、分子BがAMPである場合、8.3×1021通りの重ね合わせの計算を行い、最適な重ね合わせを求めることが可能となる(図14(c))。このように、分子Aと分子Bの最適な重ね合わせを全探索に拠ることは、膨大な時間が掛かるため、必ずしも現実的な方法ではない。





よって、2分子間の原子対応を求め該対応に基づいて2分子の最適な重ね合わせを実現するグラフマッチにおいて、多少の間違いを許容しつつも発見的に高速に行うことが求められている。

産業上の利用分野



本発明は、高速グラフマッチ検索アルゴリズムを利用して、2分子間の原子対応を求め対応に基づいて2分子を仮想的に重ね合わせ、2分子間の類似度を求めて評価する、高速グラフマッチ検索装置及び方法に関する。

特許請求の範囲 【請求項1】
第1の分子Aを構成する原子(Ai,Aj,・・・)の各々に係る座標データと第2の分子Bを構成する原子(Bk,Bl,・・・)の各々に係る座標データを記憶部から入力し、演算部にロードされるコンピュータプログラムに従って、演算部及び記憶部に構築される仮想メモリ空間において第1の分子Aの夫々の原子(Ai,Aj,・・・)と第2の分子Bの夫々の原子(Bk,Bl,・・・)との対応付け(m(Ai)=Bk)を求めて重ね合わせを行い(i,j,k,lはいずれも自然数)、第1の分子Aと第2の分子Bの間の最適な原子間対応、及び第1の分子Aと第2の分子Bの類似度に係るデータを出力部に出力する、第1の分子Aと第2の分子Bとの類似度を評価するための高速グラフマッチ検索装置において、
第1の分子Aの全ての原子Aiと第2の分子Bの全ての原子Bkとで形成される、原子Aiと原子Bkの組の全てに関して、原子Ai、Bkの対の各原子からみて、周囲の環境が相互にどれだけ似ているかを示す第1の類似指標S1(Ai、Bk)を求める第1の算出手段と、
第1の分子Aの全ての原子Aiと第2の分子Bの全ての原子Bkとで形成される、原子Aiと原子Bkの組の全てに関して、原子Ai、Bkの対の各原子からみて、等しい結合距離にある周囲の原子Aj、Blの全ての組につき、第1の類似指標S1(Aj,Bl)を積算して算出する第2の類似指標S2(Ai、Bk)を求める算出手段であって、その原子Ai、Bkの対の各原子から等しい結合距離にある周囲の原子Aj、Blが同じ元素であれば、更に第1の類似指標S1(Aj,Bl)に係数を掛けた上で積算する、第2の類似指標S2(Ai、Bk)を求める第2の算出手段と、
第1の分子Aの全ての原子Aiと第2の分子Bの全ての原子Bkとで形成される、原子Aiと原子Bkの組の全てに関して、原子Ai、Bkの対を始点とし、第1の分子Aの原子と第2の分子Bの原子とを順次対応付けして全体の対応を作成し、そのときに算出されるグラフマッチスコアM(A,B)を値とする第3の類似指標S3(Ai、Bk)を求める算出手段であって、対応付け作成時には、既に対応付け済みの原子に直接結合する原子を次に選択すること、及び第2の類似指標S2が高い対を選択することを優先することを、条件とする、第3の類似指標S3(Ai、Bk)を求める第3の算出手段と、
第3の算出手段にて最大のS3(Ai,Bk)を算出した際の、始点の原子(Ai,Bk)の対から開始して、未対応の原子の対の中で最大のS3(Aj,Bl)を持つものを対応させることを、対応可能原子の組が無くなるまで続けたときの、全体の対応におけるグラフマッチスコアM(A,B)を求める第4の算出手段と、
第4の算出手段におけるグラフマッチスコアM(A、B)が閾値より大きいならば、第1の分子Aと第2の分子Bにつき第4の算出手段で算出した原子間対応及びグラフマッチスコアM(A,B)を出力する第5の出力手段と
を含む、分子間の類似度を評価するための高速グラフマッチ検索装置。

【請求項2】
更に、
上記第4の算出手段によりグラフマッチスコアM(A,B)を算出した後に、第1の分子Aにおけるひとつの結合した{Ai,Aj}の組に対応する、第2の分子Bの{Bk,Bl}において、一方を他の原子Bnと入れ換え、入れ換えた原子についてのみ、第1の分子Aにおける原子の対応を変更して、微調整されたグラフマッチスコアM(A,B)を求める第6の算出手段を含み、
上記第6の算出手段にて算出された、微調整されたグラフマッチスコアM(A,B)が、上記第3の算出手段にて算出されたグラフマッチスコアM(A,B)より大きければ、上記第5の出力手段が、微調整されたグラフマッチスコアM(A,B)をグラフマッチスコアM(A,B)に上書きして出力を行う
ことを特徴とする請求項1に記載の高速グラフマッチ検索装置。

【請求項3】
グラフマッチスコアM(A,B)が、下記の数1で定義され、下記数1の各項は、下記の表1で定義され、下記表1の実行modeの値は入力手段を介して外部から設定されることを特徴とする
請求項1又は2に記載の高速グラフマッチ検索装置。
【数1】


【表1】



【請求項4】
上記第1の算出手段における第1の類似指標「S1(Ai,Bk)」が、下記の数2及び表2で定義され、
上記第2の算出手段における第2の類似指標「S2(Ai,Bk)」が、下記の数3及び表3で定義され、
上記第3の算出手段における第3の類似指標「S3(Ai、Bk)」が、下記の数4及び表4で定義される
ことを特徴とする請求項1乃至3のうちのいずれか一に記載の高速グラフマッチ検索装置。
【数2】


【表2】


【数3】


【表3】


【数4】


【表4】



【請求項5】
上記表3における係数が、12であることを特徴とする請求項4に記載の高速グラフマッチ検索装置。

【請求項6】
記憶部に格納される第1の分子Aを構成する原子(Ai,Aj,・・・)の各々に係る座標データと第2の分子Bを構成する原子(Bk,Bl,・・・)の各々に係る座標データを入力し、演算部にロードされる所与のコンピュータプログラムに従って、コンピュータ上に構築される仮想メモリ空間において第1の分子Aの夫々の原子(Ai,Aj,・・・)と第2の分子Bの夫々の原子(Bk,Bl,・・・)との対応付け(m(Ai)=Bk)を求めて重ね合わせを行い(i,j,k,lはいずれも自然数)、第1の分子Aと第2の分子Bの間の最適な原子間対応、及び第1の分子Aと第2の分子Bの類似度を出力部に出力する、コンピュータを用いて第1の分子Aと第2の分子Bとの類似度を評価するための高速グラフマッチ検索方法において、
第1の分子Aの全ての原子Aiと第1の分子Bの全ての原子Bkとで形成される、原子Aiと原子Bkの組の全てに関して、原子Ai、Bkの対の各原子からみて、周囲の環境が相互にどれだけ似ているかを示す第1の類似指標S1(Ai、Bk)を求める第1の工程と、
第1の分子Aの全ての原子Aiと第2の分子Bの全ての原子Bkとで形成される、原子Aiと原子Bkの組の全てに関して、原子Ai、Bkの対の各原子からみて、等しい結合距離にある周囲の原子Aj、Blの全ての組につき、第1の類似指標S1(Aj,Bl)を積算する第2の類似指標S2(Ai、Bk)を求める工程であって、そのAi、Bkの対の各原子から等しい結合距離にある周囲の原子Aj、Blが同じ元素であれば、更に第1の類似指標S1(Aj,Bl)に係数を掛けた上で積算する、第2の類似指標S2(Ai、Bk)を求める第2の工程と、
第1の分子Aの全ての原子Aiと第2の分子Bの全ての原子Bkとで形成される、原子Aiと原子Bkの組の全てに関して、原子Ai、Bkの対を始点とし、第1の分子Aの原子と第2の分子Bの原子とを順次対応付けして全体の対応を作成し、そのときに算出されるグラフマッチスコアM(A,B)を値とする第3の類似指標S3(Ai、Bk)を求める工程であって、対応付け作成時には、既に対応付け済みの原子に直接結合する原子を次に選択すること、及び第2の類似指標S2が高い対を選択することを優先することを、条件とする、第3の類似指標S3(Ai、Bk)を求める第3の工程と、
第3の工程にて最大のS3(Ai,Bk)を算出した際の、始点の原子(Ai,Bk)の対から開始して、未対応の原子の対の中で最大のS3(Aj,Bl)を持つものを対応させることを、対応可能原子の組が無くなるまで続けたときの、全体の対応におけるグラフマッチスコアM(A,B)を求める第4の工程と、
第4の工程におけるグラフマッチスコアM(A、B)が閾値より大きいならば、第1の分子Aと第2の分子Bにつき第4の工程で算出した原子間対応及びグラフマッチスコアM(A,B)を出力する第5の工程と
を含む、分子間の類似度を評価するための高速グラフマッチ検索方法。

【請求項7】
記憶部に格納される第1の分子Aを構成する原子(Ai,Aj,・・・)の各々に係る座標データと第2の分子Bを構成する原子(Bk,Bl,・・・)の各々に係る座標データを入力し、コンピュータ上に構築される仮想メモリ空間において、第1の分子Aの夫々の原子(Ai,Aj,・・・)と第2の分子Bの夫々の原子(Bk,Bl,・・・)との対応付け(m(Ai)=Bk)を求めて重ね合わせを行い(i,j,k,lはいずれも自然数)、第1の分子Aと第2の分子Bの間の最適な原子間対応、及び第1の分子Aと第2の分子Bとの類似度を評価する処理を、コンピュータに実行させるコンピュータプログラムにおいて、
第1の分子Aの全ての原子Aiと第2の分子Bの全ての原子Bkとで形成される、原子Aiと原子Bkの組の全てに関して、原子Ai、Bkの対の各原子からみて、周囲の環境が相互にどれだけ似ているかを示す第1の類似指標S1(Ai、Bk)を求める第1の算出ステップと、
第1の分子Aの全ての原子Aiと第2の分子Bの全ての原子Bkとで形成される、原子Aiと原子Bkの組の全てに関して、原子Ai、Bkの対の各原子からみて、等しい結合距離にある周囲の原子Aj、Blの全ての組につき、第1の類似指標S1(Aj,Bl)を積算する第2の類似指標S2(Ai、Bk)を求める算出ステップであって、そのAi、Bkの対の各原子から等しい結合距離にある周囲の原子Aj、Blが同じ元素であれば、更に第1の類似指標S1(Aj,Bl)に係数を掛けた上で積算する、第2の類似指標S2(Ai、Bk)を求める第2の算出ステップと、
第1の分子Aの全ての原子Aiと第2の分子Bの全ての原子Bkとで形成される、原子Aiと原子Bkの組の全てに関して、原子Ai、Bkの対を始点とし、第1の分子Aの原子と第2の分子Bの原子とを順次対応付けして全体の対応を作成し、そのときに算出されるグラフマッチスコアM(A,B)を値とする第3の類似指標S3(Ai、Bk)を求める算出ステップであって、対応付け作成時には、既に対応付け済みの原子に直接結合する原子を次に選択すること、及び第2の類似指標S2が高い対を選択するのを優先することを、条件とする、第3の類似指標S3(Ai、Bk)を求める第3の算出ステップと、
第3の算出ステップにて最大のS3(Ai,Bk)を算出した際の、始点の原子(Ai,Bk)の対から開始して、未対応の原子の対の中で最大のS3(Aj,Bl)を持つものを対応させることを、対応可能原子の組が無くなるまで続けたときの、全体の対応におけるグラフマッチスコアM(A,B)を求める第4の算出ステップと、
第4の算出ステップにおけるグラフマッチスコアM(A、B)が閾値より大きいならば、第1の分子Aと第2の分子Bにつき第4の工程で算出した原子間対応及びグラフマッチスコア(A,B)を出力する第5の出力ステップとを
コンピュータに実行させるコンピュータプログラム。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2010031526thum.jpg
出願権利状態 登録
参考情報 (研究プロジェクト等) 発明の概要: 本特許を基に発明者は分子検索用ソフトCOMPLIGを開発した。Protein Data Bankに登録された分子の各原子の三次元位置情報を基に、COMPLIGは各原子の近傍の原子の環境(その原子に結合している化学結合の数や元素の違い)の類似性に基づき、2分子間の原子対応を評価する。この評価方法により、任意の化合物およびその部分構造とDBに登録された化合物の検索を高速で行い、類似の化合物を抽出し、かつ両化合物の原子の対応関係を示せる。その結果、両化合物の立体構造を重ね合わせて表示できることが特徴である。なお、COMPLIG はSDFフォーマットされた化合物の検索も可能である。


PAGE TOP

close
close
close
close
close
close
close