JP3856242B2 - 3D structure processing equipment - Google Patents

Description

【００４０】
となる。ここで，ｎ＝４，ｍ＝３とすると，
【００４１】
【数２】

【００４２】
となる。すなわち，図３（Ｂ）に示す点集合Ａ（３点）と点集合Ｂ（４点）のような場合，生成される組合せの数は７３通りとなる。実際には，これらの点（要素）の数はもっとずっと多いのが普通であるので，組合せの数は膨大な数となる。
【００４３】
そこで，これらの対応付けを行う際に，以下の(4) ，(5) ，(6) に示す各点集合内の幾何学的な関係，しきい値条件，点の属性を考慮することによって最適な組合せを生成することを図る。
【００４４】
(2) 順序付けられた点集合の対応付け
物質Ａと物質Ｂが各々点集合Ａ＝｛ａ₁ ，ａ₂ ，…，ａ_i ，…，ａ_m ｝，１≦ｉ≦ｍ，Ｂ＝｛ｂ₁ ，ｂ₂ ，…，ｂ_j ，…，ｂ_n ｝，１≦ｊ≦ｎで形成され，各点はａ_i ＝（ｘ_i ，ｙ_i ，ｚ_i ），ｂ_j ＝（ｘ_j ，ｙ_j ，ｚ_j ）からなる三次元座標であり，点集合Ａでは，ａ₁ ＜ａ₂ ＜…＜ａ_i ＜…＜ａ_m （またはａ₁ ＞ａ₂ ＞…＞ａ_i ＞…＞ａ_m ）なる順序関係が成り立ち，同様に点集合Ｂ内でもｂ₁ ＜ｂ₂ ＜…＜ｂ_j ＜…＜ｂ_n （またはｂ₁ ＞ｂ₂ ＞…＞ｂ_j ＞…＞ｂ_n ）なる順序関係が成り立つとする。
【００４５】
この場合，各点集合の要素の対応付けは原理的には各集合内の点を順序関係に基づいて順次対応付けていき，図５（Ａ）に示す木構造を作成することによってすべての組合せを生成することができる。図５（Ｂ）は，点集合Ａの要素が３点，点集合Ｂの要素が４点の場合の例である。すなわち図５（Ｂ）は，順序付けられた点集合Ａ＝｛ａ₁ ，ａ₂ ，ａ₃ ｝，（順序関係はａ₁ ＜ａ₂ ＜ａ₃ ）と，同様に順序付けられた点集合Ｂ＝｛ｂ₁ ，ｂ₂ ，ｂ₃ ，ｂ₄ ｝，（順序関係はｂ₁ ＜ｂ₂ ＜ｂ₃ ＜ｂ₄ ）の対応付けを表している。
【００４６】
点線は生成された候補を表し，その中で最適な対応付け（ａ₁ とｂ₂ ，ａ₂ とｂ₃ ，ａ₃ とｂ₄ ）を実線で表している。図中のｎｉｌは対応する点が存在しない場合に相当する。ｎｉｌを対応付けることによって比較する点集合の要素の数が異なる場合でも最適な対応付けを生成することができる。このようにして生成された組合せの中から，r.m.s.d.値が最小になる組合せを選択することにより，最良の対応付けを生成することができる。
【００４７】
また，点集合内の各要素に対して順序関係を導入することによって上記(1) と比べて大幅に生成する組合せの数を減らすことができる。さらに，これらの対応付けを行う際に，後述する(4) ，(5) ，(6) に示す各点集合内の幾何学的な関係，しきい値，点の属性を考慮することによって，最適な組合せを生成することができる。
【００４８】
図６に順序付けられた点集合の対応付けアルゴリズムの例を示す。
点集合Ａから１つずつ要素ａを取り出し，まだ木構造中の先祖，兄弟に含まれていない要素の中で親ノードの要素より大きい要素ｂｊと組み合わせて，それが制約条件を満たすかどうかを調べる。制約条件を満たしていれば，それを木構造中に登録し，次の要素についての対応付けを行っていく。
【００４９】
このように順序付けられた点集合の場合，生成される組合せの数は，
【００５０】
【数３】

【００５１】
となる。ここで，ｎ＝４，ｍ＝３とすると，
【００５２】
【数４】

【００５３】
となり，図５（Ｂ）のような点集合Ａ（３点）と点集合Ｂ（４点）の場合には，生成される組合せの数は３５通りとなる。
(3) 部分的に対応付けられた点集合または順序付けられた点集合の対応付け
上記(1) または(2) の場合において，部分的に対応付けられる点同士が決まっていることがある。この場合，各点集合の要素の対応付けは，予め部分的に対応が付けられている点の情報を参照しながら，残りの点に対して(1) ，(2) の手法と同様に各集合内の点を順次対応付けていき，図７に示すような木構造を作成することによってすべての組合せを生成することができる。
【００５４】
図７中の×印は部分的な対応付けによって枝刈りされる部分を表す。図では予め点集合Ａの要素ａ₁ と点集合Ｂの要素ｂ₂ とが対応付けられていた場合の対応付けを表している。また，(1) ，(2) と同様にこれらの対応付けを行う際に，後述する(4) ，(5) ，(6) に示す各点集合内の幾何学的な関係，しきい値条件，点の属性を考慮することによって最適な組合せを生成することができる。
【００５５】
(4) 幾何学的な関係による候補の絞り込み
幾何学的関係に基づいて点集合の要素を対応付けることによって，無駄な組合せを生成することを防ぐことができるため，効率よく点集合を対応付けることができる。
【００５６】
(a) 距離関係による候補の絞り込み
対応付けを行う際に，点集合Ａ内の要素ａ_i と近接するｓ個（１≦ｓ≦ｍ−１，ｎ−１）の点間に成り立つ距離関係｜ａ_i −ａ_i-s ｜と，点集合Ｂ内の要素ｂ_j と近接するｓ個の要素間の距離関係｜ｂ_j −ｂ_j-s ｜とが，許容誤差範囲Δｄ（｜｜ａ_i −ａ_i-s ｜−｜ｂ_j −ｂ_j-s ｜｜≦Δｄ）の関係にある点のみを選択し，対応付けることによって対応付ける候補数を絞り込むことができる。
【００５７】
図８に点集合Ａの要素ａ_i に対応する点集合Ｂ内の点ｂ_j を選択する場合の幾何学的関係の使用例を示す。図中の数値は距離を表す。
図８の(A1),(A2) に示すように，点集合Ａ内の要素ａ_i と近接するｓ＝２個の点ａ_i-1 ，ａ_i-2 間に成り立つ距離関係｜ａ_i −ａ_i-1 ｜＝２．０，｜ａ_i −ａ_i-2 ｜＝３．０に対して，点集合Ｂ内の要素ｂ_p ，ｂ_q ，ｂ_r の中で各点と隣接する２個の要素間の距離関係｜ｂ_j −ｂ_j-s ｜が許容誤差範囲Δｄ＝０．５である点のみを選択し，対応付ける。本図では幾何学的関係として点同士の相互距離を比較した結果，点ｂ_p （｜ｂ_p −ｂ_j-1 ｜＝２．２，｜ｂ_p −ｂ_j-2 ｜＝３．３）が距離関係を満たすため，点ｂ_p がｂ_j の候補として選択される。
【００５８】
(b) 角度による候補の絞り込み
立体構造が類似している場合には，立体構造を形成する各点間の角度の関係も類似していると考えることができる。立体では，図８の(B1)に示すように３点間の角度θと４点間のうち各３点から形成される面間の角度φが存在する。以下では，３点間の角度θを例として対応付ける点を絞り込む方法について述べる。
【００５９】
対応付けを行う際に，点集合Ａ内の要素ａ_i と近接するｓ個（２≦ｓ≦ｍ−１，ｎ−１）の点間に成り立つ角度に対し，点集合Ｂ内の要素ｂ_j と近接するｓ個の要素間の角度が許容誤差範囲Δθである点のみを選択し，対応付けることによって対応付ける候補数を絞り込む。
【００６０】
図８(B2)に，点集合Ａの間に成り立つ幾何学的な関係として各要素間の角度を考え，それに基づいて点集合Ｂの点を対応付ける場合の例を示す。
点集合Ａ内の要素ａ_i と近接するｓ＝２個の点ａ_i-1 ，ａ_i-2 間に成り立つ角度がθ_a ，点集合Ｂ内の要素ｂ_p ，ｂ_q ，ｂ_r の中で各点と隣接する２個の要素ｂ_j-1 ，ｂ_j-2 間の角度が各々θ_b1，θ_b2，θ_b3の場合，角度差が許容誤差範囲Δθである点のみを選択し，それらを対応付ける。本図では点ｂ_q に関してのみ許容誤差範囲｜θ_a −θ_b1｜≦Δθを満たすため，ｂ_j の候補としてｂ_q が選択される。
【００６１】
(c) 重心からの距離，角度による候補の絞り込み
立体構造が類似している場合には，重心からの距離，角度も類似していると考えられる。従って，選択した点間で重心を算出し，上記(a) ，(b) と同様の手法で距離，角度を比較することによって，対応付ける候補を絞り込むことができる。
【００６２】
(5) しきい値条件による候補の絞り込み
上述の(1) 〜(4) の方法において，所定のしきい値を設定し，候補の持つ属性値がしきい値より大きい値を持つならば探索の枝刈りをすることによって，対応付けの効率化を図ることができる。このしきい値として，例えばｎｉｌ数の制限やr.m.s.d.値の制限を用いることができる。
【００６３】
(a) ｎｉｌ数の制限
生成した組合せの中でｎｉｌの総数が多くなり過ぎると，結果的に意味のない組合せの候補が生成される。そこで，点集合Ａと点集合Ｂの各要素間の対応付けを行う際に，ｎｉｌの総数があるしきい値以上になったならば，それを組合せの候補から除外することによって無駄な候補の生成を避け，効率よく対応付けを行うことができる。
【００６４】
図９は，点集合Ａ＝｛ａ₁ ，ａ₂ ，ａ₃ ｝，Ｂ＝｛ｂ₁ ，ｂ₂ ，ｂ₃ ，ｂ₄ ｝を対応付ける際にｎｉｌの総数を０個に制限した場合の枝刈りの例を示す。図中，木構造中で×印が付けられた部分が，枝刈りされる部分である。
【００６５】
(b) r.m.s.d.値の制限
点集合Ａの要素ａ_i に点集合Ｂの要素ｂ_j を対応付けることによって，これまでに対応付けられた全点間のr.m.s.d.値が極端に悪くなる場合には，その点を候補から除外することが望ましい。そこで，要素ａ_i に要素ｂ_j を対応付けた場合の全点間のr.m.s.d.値を算出し，r.m.s.d.値があるしきい値以下ならばその点を候補とし，そうでなければ候補から除外することによって対応付ける点の候補を効率よく生成することができる。
【００６６】
(6) 点の属性による候補の絞り込み
点集合Ａの要素ａ_i に点集合Ｂの要素ｂ_j を対応付ける際に，点の属性を利用することによって対応付ける点の候補を絞り込むことができる。点の属性として，例えば原子，原子団，分子の種類や，親水性，疎水性や，電荷の正負などを挙げることができる。これらが一致するかどうかを調べることによって，候補に加えるかどうかを判定する。
【００６７】
例えば，タンパク質の構成要素間を対応付ける場合には，点の属性としてアミノ酸残基の種類（原子団に相当する）を用いることにより，対応付ける候補を絞り込むことができる。なお，アミノ酸残基の種類等に関しては，例えば「“生化学の基礎”（東京化学同人出版）p.21〜26」等の参考資料を参照されたい。
【００６８】
また，ある特定の要素に対して制限を加えることによって，同様に対応付ける点の候補を絞ることができる。例えば，ある点に対してはｎｉｌを挿入しないという制限を設けたり，ある点に対して点の属性を指定することなどにより，検索するものに対してよりきめの細かい絞り込みが可能になる。
【００６９】
次に，物質の立体構造としてタンパク質を題材とした例を説明する。ただし，対象は基本的には立体座標であれば特に限定されないため，一般の分子構造についても同様の手法で適用することができる。
〔本発明の実施例〕
(1) 分子構造を重ね合わせる処理装置の例
物質の性質を調べるときには，各分子同士を重ね合わせてお互いに共通な部分や特異的な部分を判別することによって，各物質の性質を分析したり，あるいは予測したりすることができる。これらの作業は，従来人手で行われているため，各分子構造を自動的に重ね合わせて表示する装置が必要とされている。
【００７０】
それを実現する分子構造重ね合わせ表示装置のシステムは，図１に示す装置構成のうち，物質の立体構造に関する情報を登録したデータベース２１，登録されたデータおよびユーザからの入力コマンドを読み込むデータ入力処理手段１７，重ね合わせる立体構造の要素を対応付ける組合せ生成処理手段１４，データベース２１から読み込んだ物質の立体構造（三次元座標）に基づいて，r.m.s.d.値が最小となるように立体構造同士を重ね合わせる重ね合わせ算出処理手段１５および算出された結果に基づいて立体構造同士を重ね合わせて表示する結果出力処理手段１８等を用いて構成される。
【００７１】
(a) データベース２１
物質の立体構造に関する情報を格納したデータベース２１である。データベース２１には，物質の名称，物質を構成する原子の三次元座標等が格納されている。
【００７２】
(b) データ入力処理手段１７
データ入力処理手段１７では，ユーザの入力コマンドに基づいて重ね合わせる物質のデータ（三次元座標）をデータベース２１から読み込み，組合せ生成処理手段１４，重ね合わせ算出処理手段１５へ送る処理を行う。
【００７３】
(c) 組合せ生成処理手段１４
各要素を対応付ける際に，幾何学的な関係による候補の絞り込み，所定のしきい値条件による候補の絞り込み，または点の属性による候補の絞り込みを行い，これらの幾何学的制約，しきい値条件または点の属性を満たす要素の組合せを生成する。
【００７４】
ここでの対応付けでは，タンパク質を構成するアミノ酸配列順序に基づいて空間的に類似な部分を対応付ける機能とアミノ酸配列順序とは無関係に空間的に類似な部分を対応付ける機能を提供する。アミノ酸配列順序に基づいて空間的に類似な部分を検索する場合には，タンパク質を構成する各アミノ酸をアミノ酸配列番号により順序付けられた順序集合として捉えることができ，対応付け処理の説明における(2) 〜(6) で述べた方式で類似な部分を算出することができる。また，各アミノ酸を単なる集合として捉えることによって，上記(1) ，(3) 〜(6) で述べた方式により，アミノ酸配列順序とは無関係に空間的に類似な部分を算出することができる。
【００７５】
(d) 重ね合わせ算出処理手段１５
重ね合わせ算出処理手段１５では，物質の立体構造（三次元座標）について，r.m.s.d.値が最適な値をとるように物質を構成する要素間の対応付けを行い，その座標変換情報を求めて，結果を結果出力処理手段１８へ送る。
【００７６】
(e) 結果出力処理手段１８
結果出力処理手段１８によるグラフィック表示では，重ね合わせ算出処理手段１５で算出された結果に基づいて物質の立体構造を重ね合わせて表示する。表示結果を回転させながら見ることができるようにすることによって，どの部分がどのように重なっているかを三次元グラフィックにより判別することを，さらに容易化することができる。
【００７７】
タンパク質Calmodulinのアミノ酸残基配列を図１０（Ａ）に，TroponinＣのアミノ酸残基配列を図１０（Ｂ）に示す。図１０（Ｃ）はTroponinＣの立体構造を示している。なお，図１０（Ａ），（Ｂ）は，プロテイン・データ・バンク（ＰＤＢ）に登録されているアミノ酸残基配列を抜粋したものである。
【００７８】
図１０（Ａ）に示したアミノ酸残基配列は，本来のアミノ酸残基配列に対してアミノ酸配列番号１−４，１４８番に相当するアミノ酸が欠落しているため番号がずれているが，以降の説明では，図に示したアミノ酸配列番号を使用することにする。
【００７９】
Calmodulinは生化学的な実験結果より，４個のＣａ²⁺を結合することが知られている。Ｃａ²⁺の結合部位はアミノ酸配列中に４箇所（サイト）あり，その中でアミノ酸配列番号８１−１０８，１１７−１４３は，TroponinＣ中に２箇所あるＣａ²⁺の結合部位と各々似た骨格を取ることが知られている。タンパク質はアミノ酸で構成されるが，その骨格は各アミノ酸を構成する一つの原子（Ｃα）の座標で代表できることが知られている。
【００８０】
そこで，CalmodulinのＣａ²⁺の結合部位８１−１０８を検索キー（検索キーをプローブともいう）として，アミノ酸配列順序に基づいて空間的に類似な部分（単一サイト）を検索した結果を，図１１に示す。図１１の結果から，CalmodulinのＣａ²⁺の結合部位８１−１０８に対応付けられたTroponinＣ中のアミノ酸配列番号は９６−１２３番であることがわかる。本結果は，生化学的な実験結果と一致するものである。
【００８１】
図１２にCalmodulinのＣａ²⁺の結合部位８１−１０８と１１７−１４３とをプローブとしてアミノ酸配列順序に基づいて空間的に類似な部分（複数サイト）を検索した結果を示す。図１２から，CalmodulinのＣａ²⁺の結合部位８１−１０８，１１７−１４３に対応付けられたTroponinＣ中のアミノ酸配列番号は，各々９６−１２３，１３２−１５８であることがわかる。本結果も同様に生化学的な実験結果と一致するものである。
【００８２】
このように，本装置を使用すれば，物質間の立体構造のr.m.s.d.値が小さくなるような物質の構成要素間の対応付けがなされるため，対応付けられた部分を重ね合わせて表示することによって，物質の最適な重ね合わせ表示を実現することができる。
【００８３】
(2) 立体構造検索装置，機能データベース生成装置の例
新薬の開発のように新しい機能を持つ物質を開発したり，既に存在する物質の機能強化を図るためには，物質の機能と構造の相関関係を解明することが不可欠である。このような作業を進めるに当たって，類似な立体構造を持つ物質を多数参照する必要が生じる。そのためには，データベースから立体構造が類似した物質を簡単に取り出せる立体構造検索装置が必要になる（また，このような装置があると機能と関係する立体構造を収集した機能データベースを作成することができる。機能データベースについては次の(3) で後述する）。
【００８４】
それを実現する立体構造検索装置は，図１に示す装置構成のうち，物質の立体構造に関する情報を登録したデータベース２１，登録されたデータおよびユーザからの入力コマンドを読み込むデータ入力処理手段１７，比較する立体構造の要素を対応づける組合せ生成処理手段１４，データベース２１から読み込んだ物質の立体構造（三次元座標）について，r.m.s.d.値が最小となる類似な構造を検索する類似性算出処理手段１６，および検索結果を表示する結果出力処理手段１８等を用いて構成される。
【００８５】
同様に機能データベース生成装置は，データベース２１，データ入力処理手段１７，組合せ生成処理手段１４，類似性算出処理手段１６および機能データベース生成処理手段１９等を用いて構成される。
【００８６】
(a) データベース２１
物質の立体構造に関する情報を格納したデータベースである。データベースには，物質の名称，物質を構成する原子の三次元座標等が格納されている。
【００８７】
(b) データ入力処理手段１７
立体構造のデータおよびユーザからの入力コマンドに基づいて検索のキーとなる立体構造および検索時に参照するデータベース２１に登録されている立体構造のデータを読み込み，組合せ生成処理手段１４および類似性算出処理手段１６へ送る。
【００８８】
(c) 組合せ生成処理手段１４および類似性算出処理手段１６
類似性判定のために各要素を対応付ける際に，幾何学的な関係による候補の絞り込み，所定のしきい値条件による候補の絞り込み，または点の属性による候補の絞り込みを行い，これらの幾何学的制約，しきい値条件または点の属性を満たす要素の組合せを生成する。この際，タンパク質を構成するアミノ酸配列順序に基づいて空間的に類似な部分を検索する機能とアミノ酸配列順序とは無関係に空間的に類似な部分を検索する機能を提供する。アミノ酸配列順序に基づいて空間的に類似な部分を検索する場合には，タンパク質を構成する各アミノ酸をアミノ酸配列番号により順序付けられた順序集合として捉えることができ，対応付け処理の説明における(2) 〜(6) で述べた方式で類似な部分を算出することができる。また，各アミノ酸を単なる集合として捉えることによって，上記(1) ，(3) 〜(6) で述べた方式により，アミノ酸配列順序とは無関係に空間的に類似な部分を算出することができる。これにより類似性算出処理手段１６は，類似性の高い立体構造をデータベース２１中から選出する。
【００８９】
(d) 結果出力処理手段１８
結果出力処理手段１８では，類似性算出処理手段１６の結果に基づいて類似な部分をアミノ酸配列名およびアミノ酸番号で表し，類似性の尺度としてr.m.s.d.値を表示する。
【００９０】
(e) 機能データベース生成処理手段１９
また，機能データベース生成装置の場合，機能データベース生成処理手段１９は，類似性算出処理手段１６の結果に基づいて，プローブの立体構造と類似する立体構造を，プローブの立体構造が発現する機能と同じ機能を持つものとする。そして，その情報を機能データベース２４に格納する。
【００９１】
タンパク質elongation factor のＧＴＰ（グアノシン３リン酸）のリン酸結合部位であるアミノ酸残基番号７から１４に対応するＣαの座標をプローブとしてＰＤＢから類似な立体構造の検索を行った結果を，図１３に示す。
【００９２】
この例では，プロテイン・データ・バンク（ＰＤＢ）に登録されているデータ９０５件中でタンパク質の立体構造７４４件を検索の対象とした。検索結果として，図１３に示すように，検索したターゲットタンパク質のアミノ酸残基番号，アミノ酸残基配列，プローブのアミノ酸残基配列およびターゲットとプローブの立体構造のr.m.s.d.値等の情報が出力される。途中の出力を図示省略するが，検索の結果，８個の立体構造が検索されている（プローブ自身を含む）。
【００９３】
タンパク質の種類別にみると，adenylate kinaseが３件，elongation factor が２件（内１件はプローブ自身），ras protein が３件であり，いずれもＡＴＰまたはＧＴＰのリン酸結合部位であった。これから，ＡＴＰまたはＧＴＰのリン酸との結合という機能と立体構造は非常に密接な関係にあり，かつ他のリン酸結合部位とは無関係な構造と偶然一致することがないため非常に特異的な構造を持っていることがわかる。
【００９４】
このように，本装置を使用すれば，プローブ（検索キー）となる物質の立体構造を指定することによって，物質の立体構造を格納したデータベース２１から類似構造を検索することができる。また，この検索結果を利用し，機能データベース２４を自動生成することができる。
【００９５】
(3) 機能予測装置
図１３に示した結果から推察されるように，タンパク質は，ある機能を発現するためにその機能に特異的な立体構造を持っていると考えられている。したがって，機能ごとにその機能に特異的な立体構造のデータベース（図１に示す機能データベース２４）があると，新しくＸ線結晶解析やＮＭＲ等の手法で物質の立体構造が決定された際に，その機能データベース２４に登録されている構造が立体構造内にあるかを調べることによって，その物質がどのような機能を持っており，その機能は立体構造中のどの部分（以下機能部位とよぶ）によって司られているかを予測することができる。
【００９６】
それを実現する機能予測装置は，図１に示す装置構成のうち，データ入力処理手段１７，機能と関連した立体構造を登録した機能データベース２４，これから読み込んだ立体構造の要素と，比較する立体構造の要素とを対応付ける組合せ生成処理手段１４，類似性を調べる類似性算出処理手段１６，その結果から機能と機能部位を予測する機能予測処理手段２０等を用いて構成される。
【００９７】
(a) データ入力処理手段１７
物質を構成する立体構造のデータを読み込み，組合せ生成処理手段１４へ送る。
【００９８】
(b) 機能データベース２４
物質の機能とその機能に特異的な立体構造に関する情報を格納したデータベースである。機能データベース２４には，機能の名称，機能に特異的な立体構造を構成する原子の三次元座標等が格納されている。
【００９９】
(c) 組合せ生成処理手段１４および類似性算出処理手段１６
ここでは，機能データベース２４に登録されている立体構造と入力された立体構造間の最適な重ね合わせを算出する。この際，タンパク質を構成するアミノ酸配列順序に基づいて空間的に類似な部分を検索する機能とアミノ酸配列順序とは無関係に空間的に類似な部分を検索する機能を提供する。アミノ酸配列順序に基づいて空間的に類似な部分を検索する場合には，タンパク質を構成する各アミノ酸をアミノ酸配列番号により順序付けられた順序集合として捉えることができ，対応付け処理の説明における(2) 〜(6) で述べた方式で類似な部分を算出することができる。また，各アミノ酸を単なる集合として捉えることによって，上記(1) ，(3) 〜(6) で述べた方式により，アミノ酸配列順序とは無関係に空間的に類似な部分を算出することができる。
【０１００】
(d) 機能予測処理手段２０
機能予測処理手段２０では，類似性算出処理手段１６の結果に基づいて機能データベース２４に登録されている機能名，機能部位のアミノ酸配列名およびアミノ酸残基番号で表し，類似性の尺度としてr.m.s.d.値を表示する。
〔本発明に関連する技術の実施例〕
化学物質やタンパク質の構造解析における類似構造の検索では，２つの立体構造を比較して類似性を算出しなければならない。そのために形成する点間の対応付けを自動化することが必要になる。本実施例では，立体構造を形成する点間の対応付けを容易にかつ高速化するために，点集合を構造的に意味のある部分構造に対応する点の部分集合に分割し，相手側の部分構造との類似性を調べ，部分構造が類似している場合に限って点集合全体の対応付けを行う。
【０１０１】
以下に構成要素の対応付けの具体的な方法を述べる。
(1) 点集合の部分集合への分割
構造Ａは点集合Ａ＝｛ａ₁ ，ａ₂ ，ａ₃ ，…，ａ_i ，…，ａ_m ｝，１≦ｉ≦ｍ，Ｂ＝｛ｂ₁ ，ｂ₂ ，ｂ₃ ，…，ｂ_j ，…，ｂ_n ｝，１≦ｊ≦ｎから構成され，各点はａ_i ＝（ｘ_i ，ｙ_i ，ｚ_i ），ｂ_j ＝（ｘ_j ，ｙ_j ，ｚ_j ）からなる三次元座標で表されるとする。
【０１０２】
各点間の対応付けを容易にするために，構造を構造的に意味のある部分構造に分割し，点集合を部分集合に分割する。構造的に意味のある部分構造の例として，化学物質では，官能基やある機能をもった部分構造，タンパク質では二次構造であるヘリックスやシート構造，機能を発現するために必要な部分構造などが挙げられる。
【０１０３】
部分構造の座標は既知のデータを使用したり，あるいは三次元座標より解析することによって求める。部分集合に分割された点集合ＡをＡ＝｛｛ａ₁ ，ａ₂ ，…，ａ_k ｝，｛ａ_k+1 ，ａ_k+2 ，…，ａ_l ｝，…，｛ａ_l+1 ，ａ_l+2 ，…，ａ_m ｝｝，１≦ｋ≦ｌ≦ｍとする。ここで，ＳＡ１＝｛ａ₁ ，ａ₂ ，…，ａ_k ｝，ＳＡ２＝｛ａ_k+1 ，ａ_k+2 ，…，ａ_l ｝，…，ＳＡｐ＝｛ａ_l+1 ，ａ_l+2 ，…，ａ_m ｝とすると，その集合ＳＡは点集合Ａを構成する部分集合であり，ＡはＳＡによってＡ＝｛ＳＡ１，ＳＡ２，…，ＳＡｐ｝と表される。同様に点集合ＢもＢの部分集合であるＳＢに分割することによってＢ＝｛ＳＢ１，ＳＢ２，…，ＳＢｑ｝と表される。
【０１０４】
(2) 部分集合間の対応付け
構造Ａ＝｛ＳＡ１，ＳＡ２，…，ＳＡｐ｝と構造Ｂ＝｛ＳＢ１，ＳＢ２，…，ＳＢｑ｝の各要素を対応付けることを考える。この場合，要素間の対応付けは各集合内の要素を順次対応付けていき，対応付けた状態を表した木構造を作成することにより記述することができる。木のルート(root)の節点は開始点である。葉節点は可能な対応付けの結果を表し，中間節点は部分的な結果を表す。対応する要素が存在しない場合にはｎｉｌを対応付ける。
【０１０５】
全ての組み合わせに対応する状態木を生成すると，節点の数が膨大になるため，枝刈りすることを考える。２つの部分集合を対応付けて節点を加える際に部分集合間でマッチングを行い，その結果が制約条件を満たすものであれば節点を加えることにする。制約条件については後記の(4) で述べる。部分集合間のマッチングに関しては，上述した実施例による立体構造を形成する順序付けられた２つの点集合の各要素を対応付ける立体構造のマッチング方法によって行う。
【０１０６】
部分集合の対応付けを表す図を，図１４に示す。
(3) 部分的に対応付けられた部分集合または順序付けられた部分集合の対応付け
上記(2) の場合において部分的に対応付けられる部分集合同士が決まっている場合，対応付けられている部分集合を節点を生成する候補から取り除き木構造を生成することによって対応付ける。この場合にも(2) と同様の枝刈りを行う。
【０１０７】
(4) 部分集合間の類似性による候補の絞り込み
上記(2) ，(3) の方法において，候補である２つの部分集合間の類似性により枝刈りし，効率よく対応付けを行うことができる。類似性として，候補の持つ属性と２つの構造的な類似性を考える。部分集合の属性は化学物質では官能基の種類や機能の種類，タンパク質では二次構造の構成要素や機能の種類などがある。２つの部分集合の構造的な類似性を判定するためには，前の実施例で説明した立体構造検索装置の立体構造を形成する順序付けられた２つの点集合の各要素を対応付ける立体構造のマッチング方法を用いる。そして，この方法による最適なマッチングを行ったときに得られる各点間の平均二乗距離の平方根（r.m.s.d.）を算出する。
【０１０８】
候補となる２つの部分集合の属性が同じで，かつr.m.s.d.値がしきい値以下の場合だけそれらを対応付けた節点を生成することにより，候補を絞り込むことができる。以上の制約条件を考慮した集合ＡとＢの部分集合の対応付けアルゴリズムを，図１５に示す。
【０１０９】
点集合Ａより部分集合を取り出し，それをＳＡとする。また，点集合ＳＢより木構造中の先祖，兄弟に含まれない要素ＳＢを取り出しｄ_j とする。取り出せる要素がない場合はｄ_j ＝ｎｉｌとする。
【０１１０】
そして，ＳＡとｄ_j の属性が同じであるかどうかを調べ，同じでなければその組合せを棄却し，枝刈りする。属性が同じであれば，各点集合のマッチングを行い，最適なマッチングでのr.m.s.d.値を算出する。これが所定のしきい値以内であれば，ＳＡとｄ_j を対応付け木構造中のｄ_j-1 の子ノードとして登録し，最適な点の対応付けを配列に格納する。以上の処理をすべての部分集合について繰り返す。
【０１１１】
以上の方法を用いて実現可能なタンパク質立体構造の二次構造的類似性による検索システムについて述べる。
(1) タンパク質立体構造の二次構造的類似性による検索システム
図１６にその検索処理機構の構成を示す。本装置は，タンパク質の立体構造情報が登録されているデータベース１６０（図１に示すデータベース２１に相当するもの），データベース中の立体構造情報から二次構造を決定し部分構造に分割する二次構造算出部１６１（図１に示す部分構造算出処理手段１２に相当するもの），二次構造算出部１６１によって得られた結果を二次構造のタイプと構成する点の三次元座標として格納する二次構造座標テーブル１６２（図１に示す部分構造座標テーブル１３に相当するもの），ユーザの入力コマンドを読み込む入力部１６３（図１に示すデータ入力処理手段１７に相当するもの），入力されたコマンドと二次構造座標テーブルのデータに基づいて，前述した手法により類似構造を検索する検索部１６４（図１に示す類似性算出処理手段１６に相当するもの），および検索結果をグラフィカルに表示する表示部１６５（図１に示す結果出力処理手段１８に相当するもの）から構成される。以下に各部の詳細を述べる。
【０１１２】
(a) データベース１６０
タンパク質立体構造情報が格納されているデータベースである。タンパク質ごとに名前と構成する原子の三次元座標データが登録されている。タンパク質の立体構造は一本の鎖状のアミノ酸からなり，構成するアミノ酸は順序付けられている。各アミノ酸の位置をアミノ酸の構成原子の一つであるＣαの座標で代表することとし，順序付けられたアミノ酸の配列の一方の端を１番目とするとｎ個のアミノ酸からなるタンパク質は順序付けられたｎ個の座標の点集合として表される。ｉ番目（１≦ｉ≦ｎ）のアミノ酸の座標はｉ番目の座標に対応する。
【０１１３】
(b) 二次構造算出部１６１
データベースの三次元座標に基づいてタンパク質の構造を二次構造のタイプに分割し，点集合を部分集合に分割する。二次構造のタイプとその定義の例を，図１７に示す。この図１７に示す定義に従ってｉ＝１から順にｉ番目のアミノ酸がどのタイプに属するかを決定し，一連の座標のグループを一つの部分集合とする。決定された二次構造のタイプと構成するアミノ酸の座標データとを二次構造座標テーブル１６２に格納する。この作業を繰り返しｎ個のアミノ酸全てを部分集合に分割する。以上の二次構造の決定と部分集合への分割に関する処理の流れを，図１８に示す。
【０１１４】
(c) 二次構造座標テーブル１６２
二次構造座標テーブル１６２の構成例を，図１９に示す。これには，二次構造算出部１６１により決定された二次構造のタイプと二次構造を構成するアミノ酸の座標データが格納されている。この例では，部分集合Ｓ１，Ｓ２は，αヘリックスのタイプ，部分集合Ｓ３，…は，βシートのタイプに属している。
【０１１５】
(d) 入力部１６３
入力部１６３では，二次構造座標テーブル１６２およびユーザからの入力コマンドに基づいて検索キーとなるタンパク質名を読み込む。それを検索部１６４に送る。
【０１１６】
(e) 検索部１６４
検索部１６４では，入力部１６３から送られてきたキーとなるタンパク質の二次構造座標テーブル１６２に格納されているデータを読み込み，部分集合の対応付けを行い，２つの構造間の平均二乗距離の平方根（r.m.s.d.）を算出し，r.m.s.d.値がしきい値よりも小さいものを選ぶことによって類似性の高い構造を検索する。対応付けの際に前述した部分集合間の対応付けの方法を用いる。この場合，部分集合の属性は二次構造のタイプである。対応付けの候補である２つの部分集合のタイプが一致し，構造を最適にマッチングさせた時のr.m.s.d.値がしきい値以下の場合にのみ対応付けを行う。
【０１１７】
次に，対応付けられた点同士をマッチングさせ，構造全体のr.m.s.d.値を算出する。r.m.s.d.値がしきい値以下の場合類似構造として検索結果に登録する。この作業を二次構造座標テーブル１６２に格納されたタンパク質の全てに関して行い全てのデータから二次構造的に類似した立体構造を検索する。
【０１１８】
以上の検索部１６４での処理の例を，図２０に示す。
(f) 表示部１６５
検索部１６４で得られた検索結果に基づいて，類似構造を持つタンパク質名，およびキータンパク質と類似構造タンパク質の二次構造と，二次構造を構成するアミノ酸を表示する。
【０１１９】
図２１に，その出力例を示す。また，図２２に，検索したキータンパク質Ａとそれに類似する構造を持つ検索結果であるタンパク質Ｂの立体構造を示す。
図２２では，αヘリックスの部分構造をリボンのらせんで，βストランドの部分構造を矢印で，ループやターンの部分構造をチューブで示している。この結果より，キータンパク質はアミノ酸配列の順にαヘリックス，βストランド，ループ，βストランドの４つの部分構造に分割され，それぞれ部分集合ＳＡ１，ＳＡ２，ＳＡ３，ＳＡ４に対応していることがわかる。
【０１２０】
図２１に示すように，Ａ中のＳＡ１，ＳＡ２，ＳＡ４はそれぞれＢ中の矢印で示されている部分構造ＳＢ１０，ＳＢ１，ＳＢ３と類似し，３つの部分構造の空間的位置関係も類似している。Ａ中のループ部分ＳＡ３に矢印がないのは類似する部分構造がなかったことを示す。類似構造タンパク質Ｂ中の類似部分は，図２２（Ｂ）の図においてハッチングを施した部分である。
〔本発明に関連する技術の実施例〕
最初の実施例で説明した立体構造の検索システムでは，立体構造を形成する点集合間の要素の対応付けを，各集合内の点を順次対応付けていくことにより自動化した。この手法では，対応付けるべき点がない場合にｎｉｌを対応付けることによって，比較する点集合の要素の数が異なる場合でも，最適な対応付けを生成することができるようにしている。このようにして，生成された組合せの中からr.m.s.d.値が最小になる組合せを選択することにより，最良の対応付けを生成する。
【０１２１】
ここで，組合せに関する探索の枝刈りが行われない場合，それぞれの点集合の構成要素数をｍ，ｎ個とすると，生成される組合せ数はｍⁿ 個となり，実質的に計算不可能な問題となってしまう。そこで，これらの対応付けを行う際に，各点集合の要素間の距離などの幾何学的関係，r.m.s.d.値，ｎｉｌの個数などのしきい値条件，また，構成要素の属性（タンパク質の場合，アミノ酸の種類など）を考慮することによって最適な組合せを生成するようにしている。どのような条件下でも高速に処理する手法を確立することは困難であるが，場合により，さらに計算時間の高速化を図ることができることがある。
【０１２２】
本実施例では，類似構造の抽出，検索のキーとなる立体構造の形状に注目し，検索などの処理の一層の高速化を可能とする。
図２３に本実施例を適用する対象を説明するための直線的構造と非直線的構造の例を示す。
【０１２３】
図２３（Ａ）に示すように，立体構造の両端の２点が最も遠い距離にあるような構造を直線的構造と呼ぶ。一方，図２３（Ｂ）に示すように，両端の２点が最も遠い距離ではない構造を非直線的構造と呼ぶ。本実施例は，図２３（Ａ）に示すような直線的構造を持つ立体構造に対して適用できる方式であり，さらに高速な検索処理等を可能とするものである。
【０１２４】
本実施例では，立体構造を形成する点集合Ａ，Ｂ間の要素の対応付けを行う際，点集合Ａの空間的な大きさや構成要素の数などに応じて，点集合Ｂを分割し，対応付けの候補となる点の部分集合を求めてから対応付けを行うことによって，効率良く組合せを生成する。以下において，対応付けの候補となる部分集合を求める手段について述べる。
【０１２５】
(1) 点集合Ａの構成要素数に応じた順序付けられた点集合Ｂの分割
図２４は，点集合Ａの構成要素数に応じた順序づけられた点集合Ｂの分割の例を説明するための図である。
【０１２６】
点集合Ａの要素数ｍに応じた探索空間の大きさを設定し，その大きさで順序付けられた点集合Ｂを分割し探索空間を縮小することによって，計算時間の高速化を図る。図２４の例では，点集合Ａの要素数５の２倍の大きさ１０を探索空間の大きさとして設定し処理を行っている。
【０１２７】
図２５にその点集合Ｂの分割アルゴリズムを示す。
順序付けられた点集合Ａ＝｛ａ₁ ，…，ａ_m ｝，Ｂ＝｛ｂ₁ ，…，ｂ_i ，…，ｂ_j ，…，ｂ_n ｝と点集合Ｂの部分集合Ｂ′において，以下の処理を行う。
【０１２８】
処理１：点集合Ａの要素数ｍを求める。
処理２：点集合Ｂ′の大きさを設定する関数ｆ（ｘ）により，Ｂ′の大きさ（ｆ（ｍ））を設定する。
【０１２９】
処理３：点集合Ｂを分割する。
(a) ｊ＝ｉ＋ｆ（ｍ）−１
(b) 点集合Ｂ′＝｛ｂ_i ，ｂ_i+1 ，…，ｂ_j-1 ，ｂ_j ｝
処理４：点ａ₁ とｂ_i を対応付けた後，点集合Ａ，Ｂ′の残りの各要素の対応付けを行う。
【０１３０】
処理５：ｂ_j が点集合Ｂの最後の要素の時，終了。
ｂ_j が点集合Ｂの最後の要素ではない時，ｉ＝ｉ＋１にして処理３に戻る。
【０１３１】
(2) 点集合Ａの空間的な大きさに応じた順序付けられた点集合Ｂの分割１
図２６に示すように，点集合Ａの両端の２点の距離ｄを求め，この距離ｄにより点集合Ｂを分割し探索空間を縮小することによって，計算時間の高速化を図る。特にこの手法は，次の探索空間に移る際，前の探索空間内で得られた解の位置を考慮して次の探索空間を設定することによって，探索空間が重なることにより同じ解を何度も計算してしまうことを避けた手法である。
【０１３２】
図２７は，点集合Ａの空間的な大きさに応じた順序づけられた点集合Ｂの分割アルゴリズムを示す図である。
順序付けられた点集合Ａ＝｛ａ₁ ，…，ａ_m ｝，Ｂ＝｛ｂ₁ ，…，ｂ_i ，…，ｂ_j ，…，ｂ_n ｝と点集合Ｂの部分集合Ｂ′において，以下の処理を行う。
【０１３３】
処理１：点集合Ａ，Ｂの各点間の距離を計算し距離テーブル（図示省略）を作成する。
処理２：点集合Ａの最初と最後の点（ａ₁ ，ａ_m ）の距離を距離テーブルより求め，ｄとする。
【０１３４】
処理３：点集合Ｂを分割する。
(a) ｂ_i （ｉ＝１から）との距離がｄ±αで，かつｍ≦ｊ−ｉ≦２ｍを満たすｂ_j のうちｊが最大のものを距離テーブルから求める。
【０１３５】
(b) 点集合Ｂ′＝｛ｂ_i ，ｂ_i+1 ，…，ｂ_j-1 ，ｂ_j ｝
処理４：点集合Ａ，Ｂ′の各要素の対応付けを行う。
処理５：ｂ_i が点集合Ｂの最後の要素の時，終了。
【０１３６】
処理６：ｂ_i が点集合Ｂの最後の要素ではない時
▲１▼点集合Ａ，Ｂ′の点が対応付けられた時，
ａ₁ と対応付けられた点をｂ_k とする時，ｉ＝ｋ＋１として処理３に戻る。
【０１３７】
▲２▼点集合Ａ，Ｂ′の点が対応付けられなかった時，
ｉ＝ｉ＋１として処理３に戻る。
(3) 点集合Ａの空間的な大きさに応じた順序付けられた点集合Ｂの分割２
図２８に示すアルゴリズムのように，点集合Ａの空間的な大きさに応じた順序付けられた点集合Ｂの分割を行うこともできる。この例でも点集合Ａの両端の２点の距離を求め，この距離により点集合Ｂを分割し探索空間を縮小することによって，計算時間の高速化を図っている。また，次の探索空間に移る際，探索のキーとなる点集合Ａの要素数を考慮して次の探索空間を設定することによって，探索空間が重なり同じ解を何度も計算してしまうことを避けている。
【０１３８】
順序付けられた点集合Ａ＝｛ａ₁ ，…，ａ_m ｝，Ｂ＝｛ｂ₁ ，…，ｂ_i ，…，ｂ_j ，…，ｂ_n ｝と点集合Ｂの部分集合Ｂ′において，
処理１：点集合Ａ，Ｂの各点間の距離を計算し距離テーブル（図示省略）を作成する。
【０１３９】
処理２：点集合Ａの最初と最後の点（ａ₁ ，ａ_m ）の距離を距離テーブルより求め，ｄとする。
処理３：点集合Ｂを分割する。
【０１４０】
(a) ｂ_i （ｉ＝１から）との距離がｄ±αで，かつｍ≦ｊ−ｉ≦２ｍを満たすｂ_j のうちｊが最大のものを距離テーブルから求める。
(b) 点集合Ｂ′＝｛ｂ_i ，ｂ_i+1 ，…，ｂ_j-1 ，ｂ_j ｝
処理４：点集合Ａ，Ｂ′の各要素の対応付けを行う。
【０１４１】
処理５：ｂ_i が点集合Ｂの最後の要素の時，終了。
ｂ_i が点集合Ｂの最後の要素ではない時，ｉ＝ｊ−ｍ＋１にして処理３に戻る。
【０１４２】
以上により，立体構造を形成する点同士を対応付ける際，立体構造の探索空間を分割してから点同士の対応付けを行うため，短時間に点同士を対応付けることができるようになる。
【０１４３】
本実施例による分子構造を重ね合わせて表示するシステムについても，最初に説明した実施例の場合と同様な構成で実現することができる。ただし，図１に示す組合せ生成処理手段１４による対応付け方法が異なる。
【０１４４】
具体例を説明するために，タンパク質Trypsin のアミノ酸（残基）配列を図２９（Ａ）に，Elastaseのアミノ酸配列を図２９（Ｂ）に示す。図２９はＰＤＢに登録されているアミノ酸配列を抜粋したものである。図２９に示したアミノ酸配列番号は，ＰＤＢに記載されているアミノ酸に対して単純に１から番号をふったものであるので本来のアミノ酸番号とは異なっているが，以降の説明では図に示したアミノ酸番号を使用することにする。
【０１４５】
図２９に示したTrypsin ，Elastaseはセリンプロテアーゼと呼ばれるタンパク質分解酵素の仲間で，活性部位にヒスチジン，セリン，アスパラギン酸が不可欠な酵素である。これらの酵素の基質特異性は全く異なるが，構造および触媒機構などの点で類似していることから進化的には一群の酵素であろうと考えられている。
【０１４６】
図３０（Ａ）に，Trypsin のヒスチジン活性部位（３６−４１）をプローブとして，Elastaseのヒスチジン活性部位を検索した結果を示す。この結果によると，Trypsin の活性部位３６−４１に対して，Elastaseの４１−４６が対応付けられたことがわかる。
【０１４７】
また，図３０（Ｂ）に，Trypsin のセリン活性部位（１７５−１７９）をプローブとして，Elastaseのセリン活性部位を検索した結果を示す。この結果によると，Trypsin の活性部位１７５−１７９に対して，Elastaseの１８６−１９０が対応付けられたことがわかる。これらの結果は，生化学的な実験で得られた結果と合致するものである。
【０１４８】
このように，本装置によってプローブとなる物質の立体構造を指定することによって，物質の立体構造を格納したデータベースからr.m.s.d.値が最小となる対応付けが算出できるため，対応付けられた部分を重ね合わせて表示することによって物質の最適な重ね合わせ表示を実現することができる。
【０１４９】
例えば，新薬の開発のように求める機能を持つ物質を開発する場合などには，物質の機能と構造の相関関係を解明するため，類似な立体構造を持つ物質を多数参照する必要が生じる。そのため，データベースから立体構造が類似した物質を簡単に取り出せる立体構造の検索システムが必要になるが，前述した例と同様に高速な検索システムを構成することができる。
【０１５０】
先に説明した実施例の手法により，組合せ生成処理手段１４によって効率よく要素の組合せを生成し，類似性算出処理手段１６によって類似する立体構造をデータベース２１から抽出する。そして，結果出力処理手段１８により，類似性算出処理手段１６の結果に基づいて，類似な部分をアミノ酸配列名，およびアミノ酸番号で表し，類似性の尺度としてr.m.s.d.値を表示する。
【０１５１】
このように，本装置によってプローブ（検索キー）となる物質の立体構造を指定することによって，物質の立体構造を格納したデータベース２１からr.m.s.d.値が最小となる類似構造を検索することができる。
【０１５２】
【発明の効果】
以上説明したように，本発明によれば，立体構造を形成する点同士を自動的に重ね合わせることができるため，グラフィックシステムにより立体構造を自動的に重ね合わせて表示することや，立体構造が類似した構造をデータベースから自動的に検索することが可能になる。また，機能データベースを生成し，新しい物質の機能を予測することが可能になる。したがって，新薬の開発やタンパク質の研究等に寄与するところが大きい。
【図面の簡単な説明】
【図１】本発明の原理説明図である。
【図２】本発明に関係するr.m.s.d.値の算出方法を示す図である。
【図３】順序づけられていない点集合ＡとＢの対応付け説明図である。
【図４】順序付けられていない点集合ＡとＢの対応付けアルゴリズムの例を示す図である。
【図５】順序づけられた点集合ＡとＢの対応付け説明図である。
【図６】順序付けられた点集合ＡとＢの対応付けアルゴリズムの例を示す図である。
【図７】部分的に対応付けられた点集合ＡとＢの対応付け説明図である。
【図８】幾何学的制約による候補の絞り込みを説明するための図である。
【図９】ｎｉｌ数を制限した点集合ＡとＢの対応付け説明図である。
【図１０】タンパク質の例を示す図である。
【図１１】本発明の実施例による検索結果の例を示す図である。
【図１２】本発明の実施例による検索結果の例を示す図である。
【図１３】立体構造検索結果の例を示す図である。
【図１４】集合ＡとＢの部分集合の対応付け説明図である。
【図１５】集合ＡとＢの部分集合の対応付けアルゴリズムの例を示す図である。
【図１６】本発明の実施例に係る検索処理機構の説明図である。
【図１７】タンパク質の二次構造のタイプの例とその定義説明図である。
【図１８】二次構造の決定と部分集合への分割の処理の例を示す図である。
【図１９】二次構造座標テーブルの構成例を示す図である。
【図２０】図１６に示す検索部での処理説明図である。
【図２１】タンパク質Ａのキーとした類似構造検索の出力例を示す図である。
【図２２】図２１に示す検索したタンパク質の立体構造を示す図である。
【図２３】本実施例を適用する対象を説明するための直線的構造と非直線的構造の例を示す図である。
【図２４】点集合Ａの構成要素数に応じた順序づけられた点集合Ｂの分割の例を説明するための図である。
【図２５】点集合Ａの構成要素数に応じた順序づけられた点集合Ｂの分割アルゴリズムを示す図である。
【図２６】点集合Ａの空間的な大きさに応じた順序づけられた点集合Ｂの分割の例を説明するための図である。
【図２７】点集合Ａの空間的な大きさに応じた順序づけられた点集合Ｂの分割アルゴリズムを示す図である。
【図２８】点集合Ａの空間的な大きさに応じた順序づけられた点集合Ｂの他の分割アルゴリズムを示す図である。
【図２９】アミノ酸配列の例を示す図である。
【図３０】本実施例による検索結果の例を示す図である。
【符号の説明】
１０ 処理装置
１１ 制御部
１２ 部分構造算出処理手段
１３ 部分構造座標テーブル
１４ 組合せ生成処理手段
１５ 重ね合わせ算出処理手段
１６ 類似性算出処理手段
１７ データ入力処理手段
１８ 結果出力処理手段
１９ 機能データベース生成処理手段
２０ 機能予測処理手段
２１ データベース
２２ 入力装置
２３ 表示装置
２４ 機能データベース[0001]
[Industrial application fields]
The present invention relates to a three-dimensional structure processing apparatus that superimposes two three-dimensional structures of a substance or extracts a similar portion.
[0002]
In the field of physics and chemistry, in order to investigate the properties of new (unknown) substances, or to create new substances artificially, research is conducted to analyze the molecular structure and elucidate the expression mechanism of the functions of the substances. ing. From past research results, it is known that there is a close relationship between the function of a substance and the three-dimensional structure, and structurally similar parts (or specific parts) greatly contribute to the function of the substance. It is thought to be involved. For this reason, the three-dimensional structure of a substance is determined by an X-ray crystal analyzer or NMR, and the resulting three-dimensional structure database is being developed.
[0003]
For example, if a similar part in a three-dimensional structure can be automatically extracted or searched from this database by a computer, a series of operations performed by researchers in the past can be reduced.
[0004]
[Prior art]
In the field of physics and chemistry, in order to investigate the properties of new (unknown) substances, or to create new substances artificially, the three-dimensional structure of the substance is determined and determined using techniques such as X-ray crystallography and NMR. The information of the obtained three-dimensional structure is stored in a database. As a representative database, the Protein Data Bank (PDB), which has registered three-dimensional structures of proteins, etc., revealed by X-ray crystallographic analysis of proteins, is widely known and used worldwide. Yes. As a database in which chemical substances are registered, the Cambridge Structural Database (CSD) is known.
[0005]
Proteins are linked to each other like a single chain, and these chains are folded in vivo to form a three-dimensional structure and express various functions. Each amino acid is expressed by numbering from 1 in order from the N terminal to the C terminal. These numbers are called amino acid numbers, amino acid sequence numbers or amino acid residue numbers. Each amino acid is composed of a plurality of atoms depending on the type. Therefore, information such as the name of the protein, the management number, the amino acid number forming the protein, the type of each atom constituting each amino acid, and the three-dimensional coordinates are registered in the PDB.
[0006]
From past chemical research results, it is known that there is a close relationship between the three-dimensional structure of substances and their functions. In order to modify substances and create substances with new functions, The relationship between three-dimensional structure and function is being elucidated through experimental experiments. Among them, structurally similar parts (or specific parts) between substances with the same function are considered to be greatly involved in the function of the substance, so finding similar structures that exist in the three-dimensional structure in common Indispensable.
[0007]
However, since there is no way to extract the characteristic part directly from the three-dimensional coordinates, the researchers display each three-dimensional structure with a three-dimensional graphic system and look for it to search for the characteristic part by hand. Currently. In general, there is no way to determine the orientation of a substance, and it takes a considerable amount of time to search for a characteristic part while rotating the other substance based on one substance.
[0008]
When researchers search for similar three-dimensional structures, the r.m.s.d. (root mean square distance) value is used as a measure of the similarity of the three-dimensional structures of substances. The r.m.s.d. value is a value that represents the square root of the mean square distance between the constituents of the substances associated with each other. Empirically, they are considered very similar if the r.m.s.d. value between them is less than 1 mm.
[0009]
FIG. 2 shows a method for calculating the r.m.s.d. value.
For example, a point set A = {a as shown in FIG.₁, A₂, ..., a_i, ..., a_m} And a point set B = {b as shown in (b)₁, B₂, ..., b_j, ..., b_n}, There is a substance represented by Elements constituting these substances A and B are associated with each other as shown in (c), and the substance B is rotated and moved so that the r.m.s.d. value between the associated elements is minimized. The r.m.s.d. value is n for the number of points to associate, U for the rotation matrix, and w for each weight._nThen, the following equation
r.m.s.d. = √ (Σw_k(Ub_k-A_k)²) ÷ n
(However, k is the sum from 1 to n)
Is required. A method for obtaining the rotation and movement of a substance that minimizes the r.m.s.d. value between the associated points has been proposed by Kabusch et al. And is currently widely used. However, in order to compare the same number of points in this method, researchers have tried and tried to determine which component in one substance corresponds to which component in the other substance to minimize the rmsd value. This is the current situation.
[0010]
In addition, in order to create a new material, it is necessary to examine existing materials. For example, when it is desired to enhance the heat resistance of a certain substance, a structure common to a highly heat-resistant substance is searched, and the function is strengthened by adding such a structure to a newly created substance. This requires the ability to search the database for the required structure, but for the same reason as described above, researchers use computer graphics systems to find the required structure from the database through trial and error. Is the current situation.
[0011]
As described above, conventionally, the operator graphically displays the three-dimensional structure of the substance to be analyzed using a graphic system, and manually analyzes it by operations such as visual comparison and overlay with other molecules on the screen. Had to do.
[0012]
In addition, there are basic structures that are commonly found in the three-dimensional structure of proteins, and these are called secondary structures. Several methods have been researched to date for automatic retrieval based on secondary structure similarity without using rmsd, but they represent substructures with secondary structure symbols according to the amino acid sequence. This is a method of comparing by the symbol, and it was not possible to make a comparison based on the similarity of spatial positional relationships.
[0013]
[Problems to be solved by the invention]
As described above, when analyzing the three-dimensional structure of a substance using CSD or PDB as described above, it takes a lot of time and labor to perform structural search and structure comparison from a large amount of data, It was a heavy burden on the workers. For this reason, the data in the database cannot be used effectively, and there is a problem that the structural analysis of the substance cannot be sufficiently performed. Therefore, a search system based on the similarity of the three-dimensional structure in the three-dimensional structure database is required.
[0014]
The present invention solves the above problems and automatically extracts a partial structure having a similar three-dimensional structure to automatically superimpose and display a plurality of three-dimensional structures and to retrieve similar structures from a database. Efficient structure comparison and search for similar structures in protein structure analysis, reducing work time and burden on workers, and enabling analysis of 3D structures for all data that could not be done before The purpose is to provide a system.
[0015]
That is, an object of the present invention is to enable automating the superposition display of a three-dimensional structure in a computer graphic system by automatically extracting similar parts in the three-dimensional structure by a computer.
[0016]
Further, the present invention provides a material analysis / retrieval system that makes it possible to retrieve a similar three-dimensional structure from a database, reduces the time required for each work, the cost of personnel, etc., and makes each work more efficient. For the purpose.
[0017]
Another object of the present invention is to provide means for automatically generating a function database by searching for a similar structure to a three-dimensional structure expressing a certain known function from a database in which the three-dimensional structure of a substance is stored. .
[0018]
Another object of the present invention is to provide means for predicting an unknown function of a certain three-dimensional structure based on a function database in which data relating to a three-dimensional structure related to the function of a substance is stored.
[0019]
Furthermore, an object of the present invention is to provide a system that speeds up the above processing and performs processing in a practically short time.
[0020]
[Means for Solving the Problems]
FIG. 1 is a diagram illustrating the principle of the present invention.
In FIG. 1, 10 is a processing unit comprising a CPU and a memory, 11 is a control unit such as an operating system, and 12 is a partial structure calculation for dividing the three-dimensional structure data of a substance into a subset of coordinates corresponding to the partial structure. Processing means, 13 is a partial structure coordinate table for storing the partial structure name and the position of the element, 14 is a combination generation processing means for generating a combination for associating each element of the two sets under a predetermined constraint condition, 15 Overlay calculation processing means for superimposing two substances etc., 16 is a similarity calculation processing means for examining the similarity of two substances, 17 is a data input processing means for inputting data such as substances, and 18 outputs search results etc. The result output processing means 19, 19 is a function database generation processing means for automatically generating a function database, and 20 is used to predict unknown functions of the specified substance. Function prediction processing means for, 21 database data regarding the three-dimensional structure of a substance is stored, 22 input device such as a keyboard and a pointing device, 23 display device, 24 denotes a function database.
[0021]
When the combination generation processing means 14 associates each element of the two sets related to the elements constituting the three-dimensional structure such as proteins and various molecules, the combination generation processing means 14 narrows down candidates based on geometric relations, This is a processing means for generating a combination of elements satisfying these geometric constraints, threshold conditions, or point attributes by narrowing down or narrowing down candidates based on point attributes.
[0022]
The overlay calculation processing means 15 finds the best match between the two three-dimensional structures by searching for a correspondence between element sets in which the average of the distances between the elements becomes smaller in the combination generated by the combination generation processing means 14. This is a processing means for calculating the position and direction for superposition.
[0023]
The result output processing means 18 is a processing means for outputting the calculated overlay result or a search result to be described later to the display device 23.
Data relating to the three-dimensional structure of a substance such as protein is registered in the database 21. The data input processing means 17 is a processing means for reading data registered in the database 21 and reading instruction information such as a command input by the user from the input device 22.
[0024]
The similarity calculation processing means 16 uses the three-dimensional structure of the designated substance as a search key, and in order to search for a similar three-dimensional structure in the database 21, the combination of the elements of the two three-dimensional structures generated by the combination generation processing means 14 Is a processing means for finding similar spatially.
[0025]
The function database generation processing means 19 uses a similarity calculation processing means for extracting and collecting a three-dimensional structure expressing a function similar to that based on a three-dimensional structure expressing a specified function. 16 is a processing means for generating a function database 24 by collecting three-dimensional structures having high similarity selected by 16 and storing the collected three-dimensional structure data by function.
[0026]
The function prediction processing means 20 collates the three-dimensional structure of a substance whose designated function is unknown with the three-dimensional structure whose function registered in the function database 24 is known, and generates a combination generation processing means 14 and a similarity calculation processing means 16. This is a processing means for predicting the function that expresses a highly similar three-dimensional structure selected by the above process as the function that expresses the three-dimensional structure of a specified substance, and outputs the result.
[0027]
The partial structure calculation processing means 12, when searching for a three-dimensional structure, assigns each set structurally when associating each element of the set composed of the three-dimensional structure serving as a search key and each of the three-dimensional structures to be searched. This is a processing means for speeding up the processing by dividing into a subset of elements corresponding to a meaningful partial structure.
[0028]
The partial structure table 13 is a storage unit in which information divided by the partial structure calculation processing unit 12 is set.
In this case, the similarity calculation processing means 16 examines the similarity between the partial structure on the search key side and the partial structure on the search target side, and associates the entire set only when the partial structures are similar. A three-dimensional structure with high similarity is selected from the database 21 by searching for a correspondence between point sets in which the average of the distances between the elements is small.
[0029]
In addition, the combination generation processing means 14 determines the shape and size of the structure that is a search key when a similar structure is extracted and searched in a three-dimensional structure such as a protein or when two three-dimensional structures are overlapped. Accordingly, the search space is divided, and a combination of elements that are candidates for association is generated in a narrow search space, so that the calculation time can be shortened.
[0030]
[Action]
According to the present invention, the point set forming the three-dimensional structure, the point set having the order relation, and the partially associated point sets can be overlapped so that the rmsd value has the optimum value. It is possible to automate the superposition work of the three-dimensional structure that relied on manpower, and to improve the work efficiency.
[0031]
Further, according to the present invention, it is possible to reduce the burden on the operator by automating the search for a highly similar structure from the protein three-dimensional structure database. As in the past, it can be graphically displayed and compared with other proteins. Also, by automating the work, it becomes possible to analyze the three-dimensional structure for all data that could not be done in the past.
[0032]
  In addition, function databases can be automatically generated and function prediction can be automated by using function databases.The
[0033]
  Points (elements)Search key when matching each otherOne of the three-dimensional structures such asAccording to sizeThe other three-dimensional structureSearch spaceLimitProcessIf you do, Points (elements) can be associated with each other in a short time.
[0034]
【Example】
Embodiments of the present invention will be described below with reference to the drawings.
First, basic processing for associating points by the combination generation processing means 14 shown in FIG. 1 will be described.
[Description of Association Processing by Combination Generation Processing Unit 14]
(1) Point set mapping
Substance A and Substance B are each a point set A = {a₁, A₂, ..., a_i, ..., a_m}, 1 ≦ i ≦ m, B = {b₁, B₂, ..., b_j, ..., b_n}, 1 ≦ j ≦ n, and each point is a_i= (X_i, Y_i, Z_i), B_j= (X_j, Y_j, Z_j). In this case, in principle, the elements of each point set are associated with each other in order, and all combinations are generated by creating a tree structure as shown in FIG. can do.
[0035]
FIG. 3B shows an example of correspondence when there are three elements of the point set A and four sets of the point set B, that is, the point set A = {a₁, A₂, A_Three} And B = {b₁, B₂, B_Three, B_Four} Is represented. The dotted line represents the generated candidate, and the optimum correspondence (a₁And b₂, A₂And b_Three, A_ThreeAnd b_Four) Is represented by a solid line.
[0036]
Nil in the figure corresponds to the case where there is no corresponding point. Even when the number of elements in the point set to be compared is different by associating nil, an optimum association can be generated. The best association can be generated by selecting a combination that minimizes the value of the square root of the mean square distance (r.m.s.d. value) from the combinations generated in this way.
[0037]
FIG. 4 shows an example of an association algorithm of point sets A and B made up of unordered point elements.
The element a is taken out from the point set A one by one and combined with the element bj not yet included in the ancestor and sibling in the tree structure, and it is checked whether or not it satisfies the constraint condition. If the constraint condition is satisfied, it is registered in the tree structure, and the next element is associated.
[0038]
However, when such a method is adopted, for example, combinations of n raised to the mth power are generated, which generally causes a problem that cannot be calculated. Specifically, in the case of an unordered point set A (m point) and point set B (n point), the number of generated combinations is as follows:
[0039]
[Expression 1]

[0040]
It becomes. Here, if n = 4 and m = 3,
[0041]
[Expression 2]

[0042]
It becomes. That is, in the case of point set A (3 points) and point set B (4 points) shown in FIG. 3B, the number of generated combinations is 73. In practice, the number of these points (elements) is usually much larger, so the number of combinations is enormous.
[0043]
Therefore, in making these correspondences, the geometrical relationships, threshold conditions, and point attributes in each point set shown in (4), (5), and (6) below are considered. Aiming to generate an optimal combination.
[0044]
(2) Matching ordered point sets
Substance A and Substance B are each a point set A = {a₁, A₂, ..., a_i, ..., a_m}, 1 ≦ i ≦ m, B = {b₁, B₂, ..., b_j, ..., b_n}, 1 ≦ j ≦ n, and each point is a_i= (X_i, Y_i, Z_i), B_j= (X_j, Y_j, Z_j), And in the point set A, a₁<A₂<... <a_i<... <a_m(Or a₁> A₂> ...> a_i> ...> a_m) Holds, and similarly in the point set B, b₁<B₂<... <b_j<... <b_n(Or b₁> B₂> ...> b_j> ...> b_n).
[0045]
In this case, in principle, the elements of each point set are associated with each other by sequentially associating the points in each set based on the order relation, and by creating the tree structure shown in FIG. Can be generated. FIG. 5B shows an example in which the point set A has 3 elements and the point set B has 4 elements. That is, FIG. 5B shows an ordered point set A = {a₁, A₂, A_Three}, (The order relationship is a₁<A₂<A_Three) And similarly ordered point set B = {b₁, B₂, B_Three, B_Four}, (The order relationship is b₁<B₂<B_Three<B_Four).
[0046]
The dotted line represents the generated candidate, and the optimum correspondence (a₁And b₂, A₂And b_Three, A_ThreeAnd b_Four) Is represented by a solid line. Nil in the figure corresponds to the case where there is no corresponding point. Even when the number of elements in the point set to be compared is different by associating nil, an optimum association can be generated. The best correspondence can be generated by selecting the combination that minimizes the r.m.s.d. value from the combinations generated in this way.
[0047]
In addition, by introducing an order relationship for each element in the point set, the number of combinations to be generated can be greatly reduced compared to (1) above. Furthermore, when making these correspondences, by considering the geometrical relationships, threshold values, and point attributes in each point set shown in (4), (5), and (6) described later, Optimal combinations can be generated.
[0048]
FIG. 6 shows an example of an ordered point set association algorithm.
Take element a from point set A one by one and combine it with element bj that is not included in the ancestors and siblings of the tree structure and is larger than the parent node element, and check if it satisfies the constraint condition Investigate. If the constraint condition is satisfied, it is registered in the tree structure, and the next element is associated.
[0049]
For such an ordered set of points, the number of combinations generated is
[0050]
[Equation 3]

[0051]
It becomes. Here, if n = 4 and m = 3,
[0052]
[Expression 4]

[0053]
Thus, in the case of point set A (3 points) and point set B (4 points) as shown in FIG. 5B, the number of generated combinations is 35.
(3) Correspondence between partially associated point sets or ordered point sets
In the case of (1) or (2) above, points that are partially associated may be determined. In this case, the elements of each point set are associated with the remaining points in the same way as in the methods (1) and (2) while referring to the information of the points that are partially associated beforehand. All combinations can be generated by sequentially associating the points in the set and creating a tree structure as shown in FIG.
[0054]
The crosses in FIG. 7 represent parts that are pruned by partial association. In the figure, element a of point set A₁And element b of point set B₂Represents the association in a case where and are associated with each other. In addition, when performing these correspondences as in (1) and (2), the geometric relationships and threshold values in each point set shown in (4), (5), and (6) described later are used. An optimum combination can be generated by considering the conditions and attributes of points.
[0055]
(4) Narrowing candidates by geometric relationship
By associating the elements of the point set based on the geometric relationship, it is possible to prevent generation of useless combinations, and thus it is possible to efficiently associate the point sets.
[0056]
(a) Narrowing candidates by distance
The element a in the point set A is used for matching_iAnd distance relationship which holds between s (1 ≦ s ≦ m−1, n−1) adjacent points | a_i-A_is| And element b in point set B_jDistance relationship between s elements in close proximity to | b_j-B_jsIs the allowable error range Δd (|| a_i-A_is|-| B_j-B_jsThe number of candidates to be associated can be narrowed down by selecting only points having a relationship of || ≦ Δd) and associating them.
[0057]
FIG. 8 shows an element a of the point set A._iPoint b in the point set B corresponding to_jAn example of using the geometric relationship when selecting is shown. The numerical value in the figure represents the distance.
As shown in (A1) and (A2) of FIG._iS = 2 points a close to_i-1, A_i-2Distance relationship between | a_i-A_i-1| = 2.0, | a_i-A_i-2For || 3.0, element b in point set B_p, B_q, B_rDistance between two adjacent elements | b_j-B_jsOnly the points where | is in the allowable error range Δd = 0.5 are selected and associated. In this figure, as a result of comparing the mutual distance between the points as a geometric relationship, the point b_p(| B_p-B_j-1| = 2.2, | b_p-B_j-2Since | = 3.3) satisfies the distance relationship, the point b_pIs b_jSelected as a candidate.
[0058]
(b) Narrowing candidates by angle
When the three-dimensional structure is similar, it can be considered that the angle relationship between the points forming the three-dimensional structure is also similar. In the three-dimensional object, as shown in (B1) of FIG. 8, there is an angle θ between three points and an angle φ between surfaces formed from three points among the four points. In the following, a method for narrowing down the points to be associated will be described using the angle θ between the three points as an example.
[0059]
The element a in the point set A is used for matching_iAnd an element b in the point set B with respect to an angle established between s (2 ≦ s ≦ m−1, n−1) adjacent points._jThe number of candidates to be matched is narrowed down by selecting only points where the angle between the adjacent s elements is within the allowable error range Δθ.
[0060]
FIG. 8 (B2) shows an example in which the angle between each element is considered as a geometric relationship established between the point sets A, and the points of the point set B are associated based on the angles.
Element a in point set A_iS = 2 points a close to_i-1, A_i-2The angle between them is θ_a, Element b in point set B_p, B_q, B_r2 elements b adjacent to each point in_j-1, B_j-2The angle between each is θ_b1, Θ_b2, Θ_b3In the case of, only the points whose angle difference is within the allowable error range Δθ are selected and associated. In this figure, point b_qError range only for_a−θ_b1In order to satisfy | ≦ Δθ, b_jAs a candidate for b_qIs selected.
[0061]
(c) Narrowing down candidates by distance and angle from the center of gravity
If the three-dimensional structures are similar, the distance and angle from the center of gravity are considered to be similar. Accordingly, by calculating the center of gravity between the selected points and comparing the distance and angle by the same method as in the above (a) and (b), the candidates to be matched can be narrowed down.
[0062]
(5) Narrowing candidates by threshold conditions
In the above methods (1) to (4), a predetermined threshold value is set, and if the candidate attribute value has a value larger than the threshold value, the search is pruned, so Efficiency can be improved. As this threshold value, for example, the limit of the nil number or the limit of the r.m.s.d. value can be used.
[0063]
(a) Limit on the number of nil
If the total number of nil in the generated combination becomes too large, a meaningless combination candidate is generated as a result. Therefore, when the correspondence between the elements of the point set A and the point set B is performed, if the total number of nil exceeds a certain threshold value, by eliminating it from the combination candidates, It is possible to avoid the generation and perform the association efficiently.
[0064]
FIG. 9 shows a point set A = {a₁, A₂, A_Three}, B = {b₁, B₂, B_Three, B_Four} Shows an example of pruning when the total number of nil is limited to zero. In the figure, the part marked with x in the tree structure is the part to be pruned.
[0065]
(b) r.m.s.d.value restrictions
Element a of point set A_iElement b of point set B_jIf the r.m.s.d. value between all the points associated so far becomes extremely worse by associating, it is desirable to exclude that point from the candidates. Therefore, element a_iElement b_jIf the rmsd value between all points is calculated, if the rmsd value is below a certain threshold, that point is taken as a candidate, otherwise it is excluded from the candidate and the candidate for the point is efficiently generated can do.
[0066]
(6) Narrowing candidates by point attributes
Element a of point set A_iElement b of point set B_jWhen associating, the point candidates can be narrowed down by using point attributes. Examples of point attributes include the types of atoms, atomic groups, and molecules, hydrophilicity, hydrophobicity, and positive and negative charges. Determine if they should be added to the candidates by checking if they match.
[0067]
For example, when associating protein constituent elements, candidates for association can be narrowed down by using the type of amino acid residue (corresponding to an atomic group) as a point attribute. For the types of amino acid residues, etc., refer to reference materials such as “Basics of Biochemistry” (Tokyo Kagaku Doujinshi) p.21-26.
[0068]
In addition, by applying a restriction to a specific element, it is possible to narrow down candidate points to be associated in the same manner. For example, by restricting not inserting nil for a certain point, or by specifying a point attribute for a certain point, it becomes possible to narrow down more finely the search target.
[0069]
  Next, an example will be described in which protein is used as the three-dimensional structure of a substance. However, since the object is basically not particularly limited as long as it is a three-dimensional coordinate, a general molecular structure can be applied by the same method.
[Main departure(Ming example)
  (1) Example of processing equipment for superimposing molecular structures
  When investigating the properties of a substance, the properties of each substance can be analyzed or predicted by overlapping each molecule and discriminating a common part or a specific part. Since these operations are conventionally performed manually, a device for automatically superimposing and displaying each molecular structure is required.
[0070]
The system of the molecular structure overlay display device that realizes this is the data input process that reads the database 21 in which information related to the three-dimensional structure of the substance is registered, the registered data, and the input command from the user in the device configuration shown in FIG. Means 17, combination generation processing means 14 for associating the elements of the three-dimensional structure to be superposed, and superposition for superimposing the three-dimensional structures so as to minimize the rmsd value based on the three-dimensional structure (three-dimensional coordinates) of the substance read from the database 21. It is configured using the alignment calculation processing means 15 and the result output processing means 18 that displays the three-dimensional structures superimposed on the basis of the calculated results.
[0071]
(a) Database 21
It is the database 21 which stored the information regarding the solid structure of a substance. The database 21 stores substance names, three-dimensional coordinates of atoms constituting the substances, and the like.
[0072]
(b) Data input processing means 17
The data input processing means 17 performs processing for reading the material data (three-dimensional coordinates) to be superimposed from the database 21 based on the user input command and sending them to the combination generation processing means 14 and the overlay calculation processing means 15.
[0073]
(c) Combination generation processing means 14
When associating each element, narrow down candidates based on geometric relationships, narrow down candidates based on predetermined threshold conditions, or narrow down candidates based on point attributes. Alternatively, a combination of elements satisfying the point attribute is generated.
[0074]
The association here provides a function of associating spatially similar parts based on the amino acid sequence order constituting the protein and a function of associating spatially similar parts regardless of the amino acid sequence order. When searching for spatially similar parts based on the amino acid sequence order, each amino acid constituting the protein can be regarded as an ordered set ordered by the amino acid sequence number. (2) Similar parts can be calculated by the method described in (6). Also, by regarding each amino acid as a simple set, spatially similar parts can be calculated regardless of the amino acid sequence order by the method described in (1), (3) to (6) above.
[0075]
(d) Overlay calculation processing means 15
In the overlay calculation processing means 15, the three-dimensional structure (three-dimensional coordinates) of the substance is associated with the elements constituting the substance so that the rmsd value takes the optimum value, the coordinate conversion information is obtained, and the result Is sent to the result output processing means 18.
[0076]
(e) Result output processing means 18
In the graphic display by the result output processing means 18, the three-dimensional structure of the substance is superimposed and displayed based on the result calculated by the overlay calculation processing means 15. By making it possible to see the display result while rotating it, it is possible to further easily determine which part is overlapped and how by the three-dimensional graphic.
[0077]
The amino acid residue sequence of the protein Calmodulin is shown in FIG. 10 (A), and the amino acid residue sequence of TroponinC is shown in FIG. 10 (B). FIG. 10C shows the three-dimensional structure of TroponinC. 10A and 10B are excerpts of amino acid residue sequences registered in the protein data bank (PDB).
[0078]
The amino acid residue sequence shown in FIG. 10A is deviated from the original amino acid residue sequence because the amino acids corresponding to amino acid sequence numbers 1-4 and 148 are missing. In the description, the amino acid sequence numbers shown in the figure are used.
[0079]
Calmodulin is based on the results of biochemical experiments.²⁺Is known to combine. Ca²⁺There are four binding sites (sites) in the amino acid sequence, among which amino acid sequence numbers 81-108 and 117-143 are two sites in Troponin C.²⁺It is known to take a skeleton similar to each binding site. It is known that proteins are composed of amino acids, but their skeletons can be represented by the coordinates of one atom (Cα) constituting each amino acid.
[0080]
So Calmodulin's Ca²⁺FIG. 11 shows the result of searching for a spatially similar portion (single site) based on the amino acid sequence order using the binding site 81-108 as a search key (the search key is also referred to as a probe). From the results of FIG. 11, Calmodulin's Ca²⁺It can be seen that the amino acid sequence numbers in Troponin C associated with the binding sites 81-108 are 96-123. This result is consistent with the biochemical experimental results.
[0081]
Fig. 12 shows Calmodulin's Ca.²⁺The result of having searched the spatially similar part (multiple site | part) based on the amino acid sequence order using the binding site 81-108 and 117-143 of this as a probe is shown. From Fig. 12, Calmodulin's Ca²⁺It can be seen that the amino acid sequence numbers in TroponinC associated with the binding sites 81-108 and 117-143 are 96-123 and 132-158, respectively. This result is also consistent with biochemical experimental results.
[0082]
In this way, if this device is used, the rmsd values of the three-dimensional structure between the substances are associated with each other so that the constituent elements of the substances are associated with each other. , Optimal overlay display of substances can be realized.
[0083]
(2) Examples of 3D structure search device and function database generation device
In order to develop a substance with a new function, such as the development of a new drug, or to enhance the function of a substance that already exists, it is essential to elucidate the correlation between the function and structure of the substance. In proceeding with such operations, it is necessary to refer to many substances having similar three-dimensional structures. This requires a 3D structure search device that can easily retrieve materials with similar 3D structures from a database (and with such a device, it is possible to create a function database that collects 3D structures related to functions. (The function database will be described later in (3) below).
[0084]
A three-dimensional structure search apparatus that realizes the above is a database 21 in which information relating to a three-dimensional structure of a substance is registered, data input processing means 17 that reads registered data and an input command from a user, and a comparison. Combination generation processing means 14 for associating three-dimensional structure elements, similarity calculation processing means 16 for searching for a similar structure having a minimum rmsd value for the three-dimensional structure (three-dimensional coordinates) of the substance read from the database 21, and The result output processing means 18 for displaying the search result is used.
[0085]
Similarly, the function database generation device is configured using a database 21, data input processing means 17, combination generation processing means 14, similarity calculation processing means 16, function database generation processing means 19, and the like.
[0086]
(a) Database 21
It is a database that stores information on the three-dimensional structure of a substance. The database stores the names of substances, the three-dimensional coordinates of atoms constituting the substances, and the like.
[0087]
(b) Data input processing means 17
Based on the data of the three-dimensional structure and the input command from the user, the three-dimensional structure which is a search key and the three-dimensional structure data registered in the database 21 to be referred to at the time of retrieval are read, and the combination generation processing means 14 and the similarity calculation processing means are read. Send to 16.
[0088]
(c) Combination generation processing means 14 and similarity calculation processing means 16
When associating each element for similarity determination, narrow down candidates based on geometric relationships, narrow down candidates based on predetermined threshold conditions, or narrow down candidates based on point attributes. Generate element combinations that satisfy constraints, threshold conditions, or point attributes. At this time, a function of searching for a spatially similar portion based on the amino acid sequence order constituting the protein and a function of searching for a spatially similar portion regardless of the amino acid sequence order are provided. When searching for spatially similar parts based on the amino acid sequence order, each amino acid constituting the protein can be regarded as an ordered set ordered by the amino acid sequence number. (2) Similar parts can be calculated by the method described in (6). Also, by regarding each amino acid as a simple set, spatially similar parts can be calculated regardless of the amino acid sequence order by the method described in (1), (3) to (6) above. Thereby, the similarity calculation processing means 16 selects a highly similar three-dimensional structure from the database 21.
[0089]
(d) Result output processing means 18
The result output processing means 18 represents similar parts by amino acid sequence names and amino acid numbers based on the result of the similarity calculation processing means 16, and displays the r.m.s.d. value as a measure of similarity.
[0090]
(e) Function database generation processing means 19
Further, in the case of the function database generation device, the function database generation processing unit 19 has the same three-dimensional structure as the probe three-dimensional structure based on the result of the similarity calculation processing unit 16 as the function of the three-dimensional structure of the probe. It shall have function. Then, the information is stored in the function database 24.
[0091]
The results of searching similar three-dimensional structures from PDB using the coordinates of Cα corresponding to amino acid residues Nos. 7 to 14 which are phosphate binding sites of GTP (guanosine triphosphate) of the protein elongation factor as a probe are shown in FIG. Shown in
[0092]
In this example, the search target is 744 protein three-dimensional structures among 905 data registered in the protein data bank (PDB). As a search result, as shown in FIG. 13, information such as the amino acid residue number of the searched target protein, the amino acid residue sequence, the amino acid residue sequence of the probe, and the r.m.s.d. value of the three-dimensional structure of the target and the probe is output. Although the output on the way is not shown, as a result of the search, eight three-dimensional structures are searched (including the probe itself).
[0093]
By protein type, there were 3 adenylate kinases, 2 elongation factors (of which 1 was the probe itself) and 3 ras proteins, all of which were ATP or GTP phosphate binding sites. From this, the function of the binding of ATP or GTP to phosphate and the three-dimensional structure are very closely related, and since it does not coincide with the structure unrelated to other phosphate binding sites, it is very specific. You can see that it has a structure.
[0094]
In this way, by using this apparatus, a similar structure can be searched from the database 21 storing the three-dimensional structure of the substance by designating the three-dimensional structure of the substance that is a probe (search key). Further, the function database 24 can be automatically generated by using the search result.
[0095]
(3) Function prediction device
As inferred from the results shown in FIG. 13, it is considered that a protein has a three-dimensional structure specific to its function in order to express a certain function. Therefore, if there is a three-dimensional structure database specific to each function (function database 24 shown in FIG. 1) for each function, when a three-dimensional structure of a substance is newly determined by a technique such as X-ray crystal analysis or NMR, By examining whether the structure registered in the function database 24 is in the three-dimensional structure, what function the substance has and which function in the three-dimensional structure (hereinafter referred to as functional part) You can predict what is governed by.
[0096]
The function predicting apparatus for realizing this is the three-dimensional structure to be compared with the data input processing means 17, the function database 24 in which the three-dimensional structure related to the function is registered, and the elements of the three-dimensional structure read from the function configuration shown in FIG. The combination generation processing means 14 for associating the elements with each other, the similarity calculation processing means 16 for examining the similarity, the function prediction processing means 20 for predicting the function and the functional part from the result, and the like.
[0097]
(a) Data input processing means 17
The data of the three-dimensional structure constituting the substance is read and sent to the combination generation processing means 14.
[0098]
(b) Function database 24
It is a database that stores information on the function of a substance and the three-dimensional structure specific to that function. The function database 24 stores function names, three-dimensional coordinates of atoms constituting a three-dimensional structure specific to the function, and the like.
[0099]
(c) Combination generation processing means 14 and similarity calculation processing means 16
Here, the optimum overlay between the three-dimensional structure registered in the function database 24 and the input three-dimensional structure is calculated. At this time, a function of searching for a spatially similar portion based on the amino acid sequence order constituting the protein and a function of searching for a spatially similar portion regardless of the amino acid sequence order are provided. When searching for spatially similar parts based on the amino acid sequence order, each amino acid constituting the protein can be regarded as an ordered set ordered by the amino acid sequence number. (2) Similar parts can be calculated by the method described in (6). Also, by regarding each amino acid as a simple set, spatially similar parts can be calculated regardless of the amino acid sequence order by the method described in (1), (3) to (6) above.
[0100]
  (d) Function prediction processing means 20
  In the function prediction processing unit 20, the function name, the amino acid sequence name of the functional site, and the amino acid residue number registered in the function database 24 based on the result of the similarity calculation processing unit 16 are used, and the rmsd value is used as a measure of similarity. Is displayed.
[Technology related to the present inventionExample of
  In the retrieval of similar structures in the structural analysis of chemical substances and proteins, the similarity must be calculated by comparing two three-dimensional structures. Therefore, it is necessary to automate the association between the points to be formed. In this embodiment, in order to facilitate and speed up the correspondence between the points forming the three-dimensional structure, the point set is divided into a subset of points corresponding to structurally meaningful substructures, The similarity with the substructure is examined, and the entire point set is associated only when the substructure is similar.
[0101]
A specific method for associating the constituent elements will be described below.
(1) Dividing point sets into subsets
Structure A has a point set A = {a₁, A₂, A_Three, ..., a_i, ..., a_m}, 1 ≦ i ≦ m, B = {b₁, B₂, B_Three, ..., b_j, ..., b_n}, 1 ≦ j ≦ n, and each point is a_i= (X_i, Y_i, Z_i), B_j= (X_j, Y_j, Z_j) Is represented by three-dimensional coordinates.
[0102]
In order to facilitate the correspondence between points, the structure is divided into structurally meaningful substructures, and the point set is divided into subsets. Examples of structurally meaningful partial structures include chemical substances, functional groups and partial structures with functions, and proteins, secondary structures such as helix and sheet structures, and partial structures necessary to express functions. Is mentioned.
[0103]
The coordinates of the partial structure are obtained by using known data or by analyzing from three-dimensional coordinates. A point set A divided into subsets is denoted by A = {{a₁, A₂, ..., a_k}, {A_{k + 1}, A_{k + 2}, ..., a_l}, ..., {a_{l + 1}, A_{l + 2}, ..., a_m}}, 1 ≦ k ≦ l ≦ m. Where SA1 = {a₁, A₂, ..., a_k}, SA2 = {a_{k + 1}, A_{k + 2}, ..., a_l}, ..., SAp = {a_{l + 1}, A_{l + 2}, ..., a_m}, The set SA is a subset constituting the point set A, and A is represented by SA as A = {SA1, SA2,..., SAp}. Similarly, the point set B is also expressed as B = {SB1, SB2,..., SBq} by dividing it into SB, which is a subset of B.
[0104]
(2) Mapping between subsets
Assume that the structure A = {SA1, SA2,..., SAp} and the elements of the structure B = {SB1, SB2,. In this case, the association between elements can be described by sequentially associating the elements in each set and creating a tree structure representing the associated state. The node of the root of the tree is the starting point. Leaf nodes represent possible matching results, and intermediate nodes represent partial results. If there is no corresponding element, nil is associated.
[0105]
If state trees corresponding to all combinations are generated, the number of nodes becomes enormous, so we consider pruning. When adding a node by associating two subsets, matching is performed between the subsets. If the result satisfies a constraint condition, a node is added. The constraints will be described in (4) below. The matching between the subsets is performed by a three-dimensional structure matching method that associates each element of two ordered point sets that form the three-dimensional structure according to the above-described embodiment.
[0106]
A diagram showing the association of the subsets is shown in FIG.
(3) Partially associated or ordered subset correspondence
In the case of (2) above, when the subsets that are partially associated with each other are determined, the associated subsets are removed from the candidates for generating the nodes and associated by generating a tree structure. In this case, the same pruning as in (2) is performed.
[0107]
(4) Narrowing candidates by similarity between subsets
In the above methods (2) and (3), pruning is performed based on the similarity between two candidate subsets, and association can be performed efficiently. As the similarity, consider the attribute of the candidate and the two structural similarities. The attributes of subsets include the types of functional groups and functions for chemical substances, and the types of secondary structure components and functions for proteins. In order to determine the structural similarity between two subsets, the matching of the three-dimensional structure that associates the elements of the two ordered point sets that form the three-dimensional structure of the three-dimensional structure search apparatus described in the previous embodiment. Use the method. Then, the square root (r.m.s.d.) of the mean square distance between points obtained when optimal matching is performed by this method is calculated.
[0108]
Candidates can be narrowed down by generating nodes that associate them only when the attributes of the two subsets that are candidates are the same and the r.m.s.d. value is less than or equal to the threshold value. FIG. 15 shows an algorithm for associating subsets of sets A and B in consideration of the above constraint conditions.
[0109]
A subset is extracted from the point set A and is designated as SA. Also, an element SB not included in an ancestor or sibling in the tree structure is extracted from the point set SB d_jAnd D if no element is available_j= Nil.
[0110]
And SA and d_jCheck if the attributes of are the same, if not, reject the combination and prune. If the attributes are the same, each point set is matched and the r.m.s.d. value at the optimal matching is calculated. If this is within a predetermined threshold, SA and d_jD in the mapping tree structure_j-1Is registered as a child node of, and the optimum point mapping is stored in the array. The above process is repeated for all subsets.
[0111]
A search system based on secondary structural similarity of protein tertiary structures that can be realized using the above method will be described.
(1) Retrieval system based on secondary structural similarity of protein tertiary structure
FIG. 16 shows the configuration of the search processing mechanism. This apparatus has a database 160 (corresponding to the database 21 shown in FIG. 1) in which three-dimensional structure information of proteins is registered, and a secondary structure that determines a secondary structure from the three-dimensional structure information in the database and divides it into partial structures. A secondary unit that stores the result obtained by the calculation unit 161 (corresponding to the partial structure calculation processing means 12 shown in FIG. 1) and the secondary structure calculation unit 161 as the type of secondary structure and the three-dimensional coordinates of the constituent points. Structure coordinate table 162 (corresponding to the partial structure coordinate table 13 shown in FIG. 1), input unit 163 for reading a user input command (corresponding to the data input processing means 17 shown in FIG. 1), input command and Based on the data of the secondary structure coordinate table, a search unit 164 (similarity calculation processing means 16 shown in FIG. 1) that searches for a similar structure by the above-described method. Those corresponding), and search results constituted a display unit 165 for displaying graphically (equivalent to the result output processing unit 18 shown in FIG. 1). Details of each part are described below.
[0112]
(a) Database 160
It is a database in which protein tertiary structure information is stored. For each protein, the name and three-dimensional coordinate data of the constituent atoms are registered. The three-dimensional structure of a protein consists of a single chain of amino acids, and the constituent amino acids are ordered. The position of each amino acid is represented by the coordinates of Cα, which is one of the constituent atoms of the amino acid, and if one end of the sequence of the ordered amino acid is the first, a protein consisting of n amino acids is ordered n Expressed as a point set of individual coordinates. The coordinates of the i-th (1 ≦ i ≦ n) amino acid correspond to the i-th coordinate.
[0113]
(b) Secondary structure calculation unit 161
Based on the 3D coordinates of the database, the protein structure is divided into secondary structure types, and the point set is divided into subsets. Examples of secondary structure types and their definitions are shown in FIG. According to the definition shown in FIG. 17, it is determined which type the i-th amino acid belongs in order from i = 1, and a series of coordinate groups is set as one subset. The determined secondary structure type and the coordinate data of the constituent amino acids are stored in the secondary structure coordinate table 162. This operation is repeated to divide all n amino acids into subsets. FIG. 18 shows the flow of processing related to the determination of the secondary structure and the division into subsets.
[0114]
(c) Secondary structure coordinate table 162
A configuration example of the secondary structure coordinate table 162 is shown in FIG. In this, the secondary structure type determined by the secondary structure calculation unit 161 and the coordinate data of amino acids constituting the secondary structure are stored. In this example, the subsets S1, S2 belong to the α helix type, and the subsets S3,... Belong to the β sheet type.
[0115]
(d) Input unit 163
The input unit 163 reads a protein name serving as a search key based on the secondary structure coordinate table 162 and an input command from the user. It is sent to the search unit 164.
[0116]
(e) Search unit 164
The search unit 164 reads the data stored in the secondary protein coordinate table 162 of the key protein sent from the input unit 163, associates the subsets, and calculates the mean square distance between the two structures. A structure with high similarity is searched by calculating a square root (rmsd) and selecting one having an rmsd value smaller than a threshold value. The method for associating the subsets described above is used for the association. In this case, the subset attribute is of secondary structure type. Matching is performed only when the types of two subsets that are candidates for matching match and the r.m.s.d. value when the structure is optimally matched is equal to or less than the threshold value.
[0117]
Next, the associated points are matched to calculate the r.m.s.d. value of the entire structure. If the r.m.s.d. value is less than or equal to the threshold, it is registered in the search result as a similar structure. This operation is performed for all the proteins stored in the secondary structure coordinate table 162, and a three-dimensional structure similar to the secondary structure is searched from all the data.
[0118]
An example of processing in the search unit 164 is shown in FIG.
(f) Display unit 165
Based on the search result obtained by the search unit 164, the name of the protein having a similar structure, the secondary structure of the key protein and the similar structure protein, and the amino acids constituting the secondary structure are displayed.
[0119]
FIG. 21 shows an output example. FIG. 22 shows the three-dimensional structure of the searched key protein A and protein B, which is the search result having a similar structure.
In FIG. 22, the partial structure of the α helix is hung with a ribbon, the partial structure of the β strand is indicated by an arrow, and the partial structure of a loop or a turn is indicated by a tube. From this result, it can be seen that the key protein is divided into four partial structures of α helix, β strand, loop and β strand in order of amino acid sequence, and corresponds to the subsets SA1, SA2, SA3 and SA4, respectively.
[0120]
  As shown in FIG. 21, SA1, SA2, and SA4 in A are similar to the partial structures SB10, SB1, and SB3 indicated by arrows in B, respectively, and the spatial positional relationships of the three partial structures are also similar. Yes. The absence of an arrow in the loop portion SA3 in A indicates that there was no similar partial structure. The similar part in the similar structural protein B is a hatched part in the diagram of FIG.
[Technology related to the present inventionExample of
  In the three-dimensional structure search system described in the first embodiment, the element association between the point sets forming the three-dimensional structure is automated by sequentially associating the points in each set. In this method, when there is no point to be associated, nil is associated so that the optimum association can be generated even when the number of elements in the point set to be compared is different. In this way, the best correspondence is generated by selecting the combination with the smallest r.m.s.d. value from the generated combinations.
[0121]
Here, when pruning of searches related to combinations is not performed, if the number of components of each point set is m and n, the number of combinations generated is mⁿIt becomes a problem that becomes practically impossible to calculate. Therefore, when performing these associations, geometrical relationships such as the distance between elements of each point set, threshold conditions such as the rmsd value, the number of nil, and the attributes of the constituent elements (in the case of proteins, The optimum combination is generated by taking into consideration the types of amino acids). Although it is difficult to establish a high-speed processing method under any conditions, in some cases, the calculation time can be further increased.
[0122]
In the present embodiment, attention is paid to the shape of a three-dimensional structure that is a key for extraction and retrieval of similar structures, and the processing such as retrieval can be further speeded up.
FIG. 23 shows an example of a linear structure and a non-linear structure for explaining an object to which this embodiment is applied.
[0123]
As shown in FIG. 23A, a structure in which two points at both ends of the three-dimensional structure are at the farthest distance is called a linear structure. On the other hand, as shown in FIG. 23B, a structure in which two points at both ends are not the farthest distance is called a non-linear structure. This embodiment is a method that can be applied to a three-dimensional structure having a linear structure as shown in FIG. 23A, and enables a higher-speed search process or the like.
[0124]
In this embodiment, when associating elements between the point sets A and B forming the three-dimensional structure, the point set B is divided according to the spatial size of the point set A, the number of components, and the like. A combination is efficiently generated by obtaining a subset of points that are candidates for association and then performing association. In the following, means for obtaining a subset that is a candidate for association will be described.
[0125]
(1) Division of ordered point set B according to the number of components of point set A
FIG. 24 is a diagram for explaining an example of division of the ordered point set B according to the number of components of the point set A.
[0126]
The size of the search space corresponding to the number m of elements in the point set A is set, and the point set B ordered by the size is divided to reduce the search space, thereby speeding up the calculation time. In the example of FIG. 24, the processing is performed by setting the size 10 which is twice the number of elements 5 of the point set A as the size of the search space.
[0127]
FIG. 25 shows a division algorithm of the point set B.
Ordered point set A = {a₁, ..., a_m}, B = {b₁, ..., b_i, ..., b_j, ..., b_n} And the subset B ′ of the point set B, the following processing is performed.
[0128]
Process 1: The number m of elements of the point set A is obtained.
Process 2: The size of B ′ (f (m)) is set by the function f (x) that sets the size of the point set B ′.
[0129]
Process 3: The point set B is divided.
(a) j = i + f (m) −1
(b) Point set B ′ = {b_i, B_{i + 1}, ..., b_j-1, B_j}
Process 4: Point a₁And b_iAre associated with each other, the remaining elements of the point sets A and B ′ are associated with each other.
[0130]
Process 5: b_jEnds when is the last element of point set B.
b_jIs not the last element of the point set B, i = i + 1 is set, and the processing returns to step 3.
[0131]
(2) Division of the ordered point set B according to the spatial size of the point set A 1
As shown in FIG. 26, the distance d between the two ends of the point set A is obtained, and the point set B is divided by this distance d to reduce the search space, thereby speeding up the calculation time. In particular, in this method, when moving to the next search space, the next search space is set in consideration of the position of the solution obtained in the previous search space. This is a technique that avoids the calculation.
[0132]
FIG. 27 is a diagram showing a division algorithm of the point set B that is ordered according to the spatial size of the point set A.
Ordered point set A = {a₁, ..., a_m}, B = {b₁, ..., b_i, ..., b_j, ..., b_n} And the subset B ′ of the point set B, the following processing is performed.
[0133]
Process 1: The distance between each point of point sets A and B is calculated, and a distance table (not shown) is created.
Process 2: First and last points (a₁, A_m) Is obtained from the distance table and is defined as d.
[0134]
Process 3: The point set B is divided.
(a) b_iThe distance to (from i = 1) is d ± α and m ≦ j−i ≦ 2m is satisfied b_jAmong them, the one having the largest j is obtained from the distance table.
[0135]
(b) Point set B ′ = {b_i, B_{i + 1}, ..., b_j-1, B_j}
Process 4: The elements of the point sets A and B ′ are associated with each other.
Process 5: b_iEnds when is the last element of point set B.
[0136]
Process 6: b_iIs not the last element of point set B
(1) When the points of point sets A and B ′ are associated,
a₁The point associated with is b_kThen, i = k + 1 and the process returns to step 3.
[0137]
(2) When the points of point sets A and B 'are not matched,
Return to process 3 with i = i + 1.
(3) Division of ordered point set B according to the spatial size of point set A 2
As in the algorithm shown in FIG. 28, the ordered point set B can be divided according to the spatial size of the point set A. In this example as well, the distance between two points at both ends of the point set A is obtained, and the point set B is divided by this distance to reduce the search space, thereby speeding up the calculation time. Also, when moving to the next search space, the next search space is set in consideration of the number of elements of the point set A that is the key of the search, so that the search space overlaps and the same solution is calculated many times. Avoid.
[0138]
Ordered point set A = {a₁, ..., a_m}, B = {b₁, ..., b_i, ..., b_j, ..., b_n} And a subset B ′ of the point set B,
Process 1: The distance between each point of point sets A and B is calculated, and a distance table (not shown) is created.
[0139]
Process 2: First and last points (a₁, A_m) Is obtained from the distance table and is defined as d.
Process 3: The point set B is divided.
[0140]
(a) b_iThe distance to (from i = 1) is d ± α and m ≦ j−i ≦ 2m is satisfied b_jAmong them, the one having the largest j is obtained from the distance table.
(b) Point set B ′ = {b_i, B_{i + 1}, ..., b_j-1, B_j}
Process 4: The elements of the point sets A and B ′ are associated with each other.
[0141]
Process 5: b_iEnds when is the last element of point set B.
b_iIs not the last element of the point set B, i = j−m + 1 is set and the processing returns to step 3.
[0142]
As described above, when the points forming the three-dimensional structure are associated with each other, the points are associated with each other in a short time because the points are associated with each other after the search space for the three-dimensional structure is divided.
[0143]
The system for displaying the molecular structure in an overlapping manner according to this embodiment can also be realized with the same configuration as in the first embodiment described above. However, the association method by the combination generation processing means 14 shown in FIG. 1 is different.
[0144]
In order to explain a specific example, the amino acid (residue) sequence of the protein Trypsin is shown in FIG. 29 (A), and the amino acid sequence of Elastase is shown in FIG. 29 (B). FIG. 29 is an excerpt of the amino acid sequence registered in the PDB. The amino acid sequence number shown in FIG. 29 is different from the original amino acid number because it is simply assigned a number from 1 to the amino acid described in the PDB. We will use the amino acid number.
[0145]
Trypsin and Elastase shown in FIG. 29 are members of a proteolytic enzyme called serine protease, and histidine, serine and aspartic acid are indispensable enzymes in the active site. Although the substrate specificities of these enzymes are completely different, they are considered to be a group of enzymes evolutionarily because they are similar in terms of structure and catalytic mechanism.
[0146]
FIG. 30 (A) shows the results of searching for the histidine active site of Elastase using the histidine active site (36-41) of Trypsin as a probe. According to this result, it can be seen that 41-46 of Elastase is associated with the active site 36-41 of Trypsin.
[0147]
FIG. 30B shows the results of searching for the serine active site of Elastase using the trypsin serine active site (175-179) as a probe. According to this result, it can be seen that 186-190 of Elastase is associated with the active site 175-179 of Trypsin. These results are consistent with those obtained from biochemical experiments.
[0148]
In this way, by specifying the three-dimensional structure of the substance to be used as a probe by this device, the correspondence that minimizes the rmsd value can be calculated from the database storing the three-dimensional structure of the substance. Display, it is possible to realize an optimal overlay display of substances.
[0149]
For example, when developing a substance having a desired function, such as the development of a new drug, it is necessary to refer to many substances having similar three-dimensional structures in order to clarify the correlation between the function and structure of the substance. For this reason, a three-dimensional structure retrieval system that can easily extract substances having a similar three-dimensional structure from a database is required. However, a high-speed retrieval system can be configured as in the above-described example.
[0150]
The combination generation processing unit 14 efficiently generates a combination of elements by the method of the embodiment described above, and the similarity calculation processing unit 16 extracts a similar three-dimensional structure from the database 21. Then, based on the result of the similarity calculation processing means 16, the result output processing means 18 represents the similar part with the amino acid sequence name and the amino acid number, and displays the r.m.s.d. value as a measure of similarity.
[0151]
In this way, by designating the three-dimensional structure of a substance to be a probe (search key) with this apparatus, a similar structure having the smallest r.m.s.d. value can be retrieved from the database 21 storing the three-dimensional structure of the substance.
[0152]
【The invention's effect】
As described above, according to the present invention, since the points forming the three-dimensional structure can be automatically overlapped, the three-dimensional structure can be automatically superimposed and displayed by the graphic system. Similar structures can be automatically retrieved from the database. In addition, a function database can be created to predict the function of new substances. Therefore, it greatly contributes to the development of new drugs and protein research.
[Brief description of the drawings]
FIG. 1 is a diagram illustrating the principle of the present invention.
FIG. 2 is a diagram showing a method for calculating an r.m.s.d. value related to the present invention.
FIG. 3 is an explanatory diagram of correspondence between point sets A and B that are not ordered;
FIG. 4 is a diagram illustrating an example of an association algorithm for point sets A and B that are not ordered;
FIG. 5 is an explanatory diagram for associating ordered point sets A and B;
FIG. 6 is a diagram illustrating an example of an association algorithm between ordered point sets A and B;
FIG. 7 is an explanatory diagram of association between point sets A and B partially associated with each other;
FIG. 8 is a diagram for explaining candidate narrowing down due to geometric constraints;
FIG. 9 is an explanatory diagram of association between point sets A and B with a limited number of nil.
FIG. 10 shows examples of proteins.
FIG. 11 is a diagram illustrating an example of a search result according to the embodiment of the present invention.
FIG. 12 is a diagram illustrating an example of a search result according to the embodiment of the present invention.
FIG. 13 is a diagram illustrating an example of a three-dimensional structure search result.
FIG. 14 is an explanatory diagram of a correspondence between subsets of sets A and B.
FIG. 15 is a diagram illustrating an example of an association algorithm for subsets of sets A and B;
FIG. 16 is an explanatory diagram of a search processing mechanism according to an embodiment of the present invention.
FIG. 17 is an example of a secondary structure type of protein and its definition explanatory diagram.
FIG. 18 is a diagram illustrating an example of a process of determining a secondary structure and dividing into subsets.
FIG. 19 is a diagram illustrating a configuration example of a secondary structure coordinate table.
FIG. 20 is an explanatory diagram of processing in the search unit shown in FIG. 16;
FIG. 21 is a diagram illustrating an output example of a similar structure search using a protein A key.
22 is a diagram showing the three-dimensional structure of the searched protein shown in FIG. 21. FIG.
FIG. 23 is a diagram showing an example of a linear structure and a non-linear structure for explaining an object to which the present embodiment is applied.
FIG. 24 is a diagram for explaining an example of division of an ordered point set B according to the number of components of the point set A;
FIG. 25 is a diagram illustrating an algorithm for dividing point set B in accordance with the number of components of point set A;
FIG. 26 is a diagram for explaining an example of division of an ordered point set B according to the spatial size of the point set A;
FIG. 27 is a diagram showing a division algorithm of an ordered point set B according to the spatial size of the point set A;
FIG. 28 is a diagram showing another division algorithm of the ordered point set B according to the spatial size of the point set A;
FIG. 29 is a diagram showing examples of amino acid sequences.
FIG. 30 is a diagram illustrating an example of a search result according to the present embodiment.
[Explanation of symbols]
10 Processing device
11 Control unit
12 Partial structure calculation processing means
13 Partial structure coordinate table
14 Combination generation processing means
15 Overlay calculation processing means
16 Similarity calculation processing means
17 Data input processing means
18 Result output processing means
19 Function database generation processing means
20 Function prediction processing means
21 Database
22 Input device
23 Display device
24 Function database

Claims (4)

Data relating to two three-dimensional structures of proteins were treated by computer, a three-dimensional structure processing apparatus for superimposing these two three-dimensional structures,
A database (21) in which data on the three-dimensional structure of proteins are registered;
Data input processing means (17) for reading data registered in the database (21) and instruction information from the user;
Based on said data input processing means (17) is data read, the two three-dimensional structure of the protein, has a respective amino acids constituting the protein with the unit sequential relationship in accordance with the amino acid sequence numbers have the attribute of the amino acid and each acquires the data described as a set of elements having the coordinates of a point, when associating each element among a set of two three-dimensional structure of the protein, with respect to newly associate candidate elements from the collecting case , already angular relationships or association according to the difference between the set of both of them between a plurality elements and candidate element distance relationship or previously associated between the multiple-element and the candidate elements eclipsed with corresponding Narrowing candidates by constraining geometric constraints , and limiting or pairing the average value of the distance between each associated element and the distance between candidate elements Performs response element exists and nil for the limited number of predetermined related candidate by threshold condition refine indicating that no, and the candidate by attributes amino narrowing, these geometrical constraints and threshold condition and amino acids A combination generation processing means (14) for generating a combination of elements that correspond to each other by incorporating a newly-corresponding element that satisfies the attribute of
And out looking for the average smallest such that the combination of the distance between the elements associated between collection from among a plurality of combinations of said associated generated by combining generation processing means (14) Element , Overlay calculation processing means (15) for calculating the position and direction for the best matching of the two conformations of the protein;
Stereostructure processing apparatus comprising the result output processing means for superposing the two stereoscopic structure of the protein to display based on the result calculated (18) by the superimposition calculation processing means (15) . Includes a database of data concerning the three-dimensional structure of the protein is stored (21), by searching the database (21) the specified three-dimensional structure as a search key, a similar conformation from in said database (21) A three-dimensional structure processing device for extraction,
Data input processing means (17) for reading data registered in the database (21) and three-dimensional structure instruction information serving as a search key from the user;
Based on the data read from the database (21) by the data input processing means (17), the three-dimensional structure of the protein three-dimensional structure registered in the database (21) and the three-dimensional structure serving as the search key. For the determination of similarity, as a set of elements having the three-dimensional structure as a unit, each amino acid constituting the protein as a unit, an amino acid attribute, an order relationship according to the amino acid sequence number, and a coordinate as a point each acquired data described, when associating each element among a set of two three-dimensional structure of the protein, with respect to newly associate candidate elements from the current case, a plurality elements already kicked with corresponding candidate depending on the angular relationship or difference between a set of both of them between a plurality elements and candidate element distance relationship or previously associated between the elements Indicates that respond with a constraint geometric constraints due to the pruning, and limits or corresponding elements of the overall mean of the values of the distance between the distance and the candidate elements between corresponding Tagged each element does not exist performed the number of candidates of the narrowing down based on a predetermined threshold condition on the limits, and the candidate narrowing by attributes of amino acids nil, a new correspondence with satisfying attributes of these geometrical constraints and threshold condition and amino acids A combination generation processing means (14) for generating a combination of associated elements as an associated element by incorporating
And out looking for the average smallest such that the combination of the distance between the elements associated between collection from among a plurality of combinations of said associated generated by combining generation processing means (14) elements, the results of searches to calculate the similarity of the two three-dimensional structures on the basis of the said search key from the three-dimensional structure of the protein that is registered the database (21) using the calculated similarity results Similarity calculation processing means (16) for selecting the three- dimensional structure having the highest similarity to the three-dimensional structure;
The similarity calculation processing means (16) three-dimensional structure processing apparatus characterized by comprising retrieval is output as a result result output processing means (18) with high conformational similarity was singled out by. Comprises a database (21) containing the data regarding the three-dimensional structure of the protein, based on the three-dimensional structure expressing certain specified functions, the conformation expressing similar functions from the in the database (21) to it A three-dimensional structure processing device that extracts and collects and generates a function database (24) in which data on three-dimensional structures related to protein functions is stored ,
Data input processing means (17) for reading data registered in the database (21) and three-dimensional structure instruction information expressing a certain function from the user;
Based on the data read by the data input processing means (17) , the determination of the similarity between the three-dimensional structure of the three-dimensional structure of the protein registered in the database (21) and the three-dimensional structure expressing the certain function is performed . Therefore, for the two three-dimensional structures, data described as a set of elements having amino acid attributes as a unit, having an amino acid attribute in the amino acid sequence number, and having coordinates as points each acquired when associating each element among a set of two three-dimensional structure of the protein, with respect to newly associate candidate elements from the current case, already between the multiple-element and the candidate elements eclipsed with corresponding constraining the correspondence according to the angular relationship or difference between a set of both of them between the distance relationship or already the associated multiple-element and candidate elements What biological constraints of the pruning, and between corresponding Tagged each element distance and the overall average value of the distance between the candidate elements limit or nil indicating that the corresponding element is not present the number of restriction performs predetermined narrowing of the candidate by the threshold condition, and attribute by narrowing the candidate amino acid related, incorporate elements newly corresponding is attached to meet the attributes of these geometrical constraints and threshold condition and amino acids A combination generation processing means (14) for generating a combination of associated elements as associated elements;
And out looking for the average smallest such that the combination of the distance between the elements associated between collection from among a plurality of combinations of said associated generated by combining generation processing means (14) elements, The similarity between the two structures is calculated based on the found result, and the function is expressed from each structure of the protein registered in the database (21) using the calculated similarity result. similarity calculation processing means of selecting a high conformational similarity to the three-dimensional structure (16),
The collect high have steric structure of similarity was singled out by the similarity calculation processing means (16), data relating to the collection conformation, corresponding to the designated function by the instruction information from the user A three-dimensional structure processing apparatus comprising: function database generation processing means (19) for generating the function database (24) by storing. A function database data regarding the three-dimensional structure associated with the function of the protein is stored (24), based on the three-dimensional structure of a protein is given, the three-dimensional structure processing apparatus for predicting the function of the three-dimensional structure is expressed Because
Data input processing means (17) for reading the data relating to the three-dimensional structure of the protein registered in the function database (24) and the instruction information of the three-dimensional structure of the protein designated by the user;
Based on the data read by the data input processing means (17) , determination of similarity between two three-dimensional structures of the three-dimensional structure of the protein registered in the function database (24) and the three-dimensional structure of the designated protein For the above three-dimensional structure, the data described as a set of elements having the amino acid attribute as a unit, having the order of amino acid sequence number according to the amino acid sequence number, and having the coordinates as a point. respectively acquires, when associating each element among a set of two three-dimensional structure of the protein, with respect to newly associate candidate elements from the current case, already between the multiple-element and the candidate elements eclipsed with corresponding the angular relationship or correspondence according to the difference between the set of both of them between the distance relationship or already the associated multiple-element and the candidate elements of the Promises geometrical constraints by the candidate narrowing, and the number of nil showing that limits or corresponding elements of the overall mean of the values of the distance between the distance and the candidate elements between corresponding Tagged each element does not exist Refine limitations given regarding the candidate by the threshold condition, and to narrow down the candidates by attributes of amino acids, the elements newly corresponding is attached to meet the attributes of these geometrical constraints and threshold condition and amino acids A combination generation processing means (14) for generating a combination of elements that are associated and incorporated as elements ,
And out looking for the average smallest such that the combination of the distance between the elements associated between collection from among a plurality of combinations of said associated generated by combining generation processing means (14) elements, The similarity between the two three-dimensional structures is calculated based on the found result, and the designated protein is calculated from each three-dimensional structure of the protein registered in the function database (24) using the calculated similarity result. and the high affinity conformation out select beauty similarity calculation processing means (16) to the three-dimensional structure,
Get the role of high conformational similarity was singled out by the similarity calculation processing means (16) is expressed from the function database (24), as a three-dimensional structure of the specified protein is a function that expresses A three-dimensional structure processing apparatus comprising: a function prediction processing means (20) for predicting and outputting information on the function and functional part.

Images