Top > Search of Japanese Patents > DEVICE AND METHOD FOR HIGH-SPEED GRAPH MATCHING SEARCH FOR EVALUATING SIMILARITY BETWEEN MOLECULES

DEVICE AND METHOD FOR HIGH-SPEED GRAPH MATCHING SEARCH FOR EVALUATING SIMILARITY BETWEEN MOLECULES commons

Patent code P120007509
File No. 24
Posted date May 10, 2012
Application number P2010-031526
Publication number P2011-170444A
Patent number P5484946
Date of filing Feb 16, 2010
Date of publication of application Sep 1, 2011
Date of registration Feb 28, 2014
Inventor
  • (In Japanese)白井 剛
Applicant
  • (In Japanese)学校法人関西文理総合学園
Title DEVICE AND METHOD FOR HIGH-SPEED GRAPH MATCHING SEARCH FOR EVALUATING SIMILARITY BETWEEN MOLECULES commons
Abstract PROBLEM TO BE SOLVED: To provide high-speed graph matching algorithm for achieving a method for determining matching between atoms of two molecules and superimposing the molecules accordingly, with respect to a molecular graph.
SOLUTION: The method for determining the optimum atomic matching between a first molecule A and a second molecule B by determining the degree of matching between each atom of the first molecule A and each atom of the second molecule B (represented by the expression m(Ai) = Bk) and superimposing the molecules. The method comprises: a step of calculating S1(Ai, Bk), S2(Ai, Bk), and S3(Ai, Bk) for all sets {i, k}; a step of determining the overall graph matching score M(A, B) by first associating the pair of atoms (Ai, Bk) having the largest calculated value for S3(Ai, Bk) with that having the second largest value for S3(Aj, Bl), then associating the pair of atoms having the second largest value for S3(Aj, Bl) with that having the third largest value, and repeating this procedure until all pairs of atoms have been associated with one another; and a step of, if the determined M(A, B) exceeds a threshold value, outputting superimposition of the molecules A and B.
Outline of related art and contending technology (In Japanese)

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

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

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

Field of industrial application (In Japanese)

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

Scope of claims (In Japanese)
【請求項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(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2010031526thum.jpg
State of application right Registered


PAGE TOP

close
close
close
close
close
close
close