大規模化学構造データベースから高速に化学構造を検索するシステム及び方法
【課題】高速かつ安価な化学構造検索手法を開発すること。
【解決手段】コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化する手段と、
該木構造を基に、該化合物を構成する全ての部分構造を文字列化する手段と、
得られた化合物の化学構造の文字列化表現及び化合物の部分構造の文字列化表現を、該化合物を識別するユニークなＩＤと共に、化学構造データベースとして記録保存するための記憶媒体と
を備える、所定の部分構造を有する化合物を検索するための化学構造検索システム、ならびに、該システムを用いる化学構造の検索方法。
【解決手段】コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化する手段と、
該木構造を基に、該化合物を構成する全ての部分構造を文字列化する手段と、
得られた化合物の化学構造の文字列化表現及び化合物の部分構造の文字列化表現を、該化合物を識別するユニークなＩＤと共に、化学構造データベースとして記録保存するための記憶媒体と
を備える、所定の部分構造を有する化合物を検索するための化学構造検索システム、ならびに、該システムを用いる化学構造の検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模な化学構造データベースから高速に化学構造を検索するシステム及び方法に関する。
【背景技術】
【０００２】
化学構造データベースは、現代の化学・創薬研究において欠くことのできない重要なツールとなっているばかりでなく、特許情報や試薬管理などにおいても必要不可欠なツールとなっている。例えば、Ｃｈｅｍｉｃａｌ Ａｂｓｔｒａｃｔｓ Ｓｙｓｔｅｍに対する化学構造検索では、ＳｃｉＦｉｎｄｅｒ［ｈｔｔｐ：／／ｗｗｗ．ｊａｉｃｉ．ｏｒ．ｊｐ／ｓｃｉ／ＳＣＨＯＬＡＲ／ｉｎｄｅｘ．ｈｔｍｌ］が、企業内データベースに対する化学構造検索では、ＩＳＩＳ［ｈｔｔｐ：／／ｗｗｗ．ｍｄｌｉ．ｃｏｍ／］などが広く利用されている。
【０００３】
化学構造検索アルゴリズムの開発は、１９６０年以来、多くの科学者が徹底的な研究を行ってきた。部分構造検索は、指定したクエリー構造が、与えられた標的構造の中に含まれているかどうかを判定する作業である。グラフ理論の用語を用いれば、部分構造検索はクエリーグラフ（ＧＱ）が、標的グラフ（ＧＴ）の部分グラフと同形であるかどうかを調べる作業であり、ＧＱとＧＴの部分グラフ間の同形を探すことは、ＮＰ完全問題であることが知られている［非特許文献１］。したがって、一般的に、同形をすばやく判定することは非常に困難な作業であるが、多くの部分構造検索手法は、バックトラッキング法を効率的に利用して、この問題を解決している［非特許文献２］。
【０００４】
しかしながら、５０，０００以上の化学構造データベースから化学構造検索を実施するには、バックトラッキング法だけでは、多くの検索時間（数十秒〜）を必要とし、実用的ではない。そこで、バックトラッキング法を行う前に、明らかに同形ではないグラフ（化学構造）を高速に除去する“スクリーニング”と呼ばれる手法が開発された。
通常、スクリーニング手法は、化学構造をビット文字列で表現する。各ビットは、任意のフラグメント（ベンゼン環、アミド基など）を意味し、１は、そのフラグメントが化学構造中に存在することを、０は存在しないことを示す。化学構造データベース中の標的構造は、事前にこのビット文字列を生成させ、データベースに保持しておく、クエリー構造のビット文字列は、検索時に生成させる。次に、クエリー構造のビット文字列と標的構造のビット文字列を順次比較し、クエリー構造のビット文字列中に存在する少なくとも１つの１の立ったビットが標的構造のビット文字列中に存在しなければ、同形の可能性はないとして除去される。この計算は、ビット演算子（ＡＮＤ、ＯＲ、ＸＯＲ）を用いて計算できるので、非常に高速に処理できる［非特許文献３］。一般的に、ビット文字列を用いたスクリーニング手法、及びその改良型を用いることで、全体として１０倍〜２０倍の高速化が実現されるため、現在、多くの構造検索システムで利用されている。
【０００５】
通常、データベースに対する検索の高速化は、インデックス（本の索引に相当する）を用いて実現されている。インデックスは、数値や文字列を対象としているため、ビット文字列同士の演算を必要とする既存の化学構造検索においては、有効に利用することができない。したがって、化学構造検索の多くは、データベースの最初から最後まで順次、ビット演算を繰り返す必要があり、高速化のもっとも大きなボトルネックとなっている。
【０００６】
一方、近年、大規模データベースに対する検索システムとして、もっとも利用されているものは、ＧｏｏｇｌｅやＹａｈｏｏ！の検索エンジンに代表される“大量の文書の中から特定の文字列を含む文書を検索する”全文検索システムである。全文検索システムの検索速度の速さは、検索エンジンを利用する誰しもが納得するレベルであり、自明である。通常、全文検索システムでは、形態素解析［非特許文献４］やＮ−ｇｒａｍ法［非特許文献５］を用いて文書を単語に分解し、次に、この単語を転置インデックス法などでインデックス化する。この作業により、どの単語がどの文書内に存在するかを高速に検索可能としている。
【非特許文献１】Ｍ． Ｇａｒｅｙ， Ｄ．Ｊｏｈｎｓｏｎ， Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｉｎｔｒａｃｔａｂｉｌｉｔｙ； Ａ Ｇｕｉｄｅ ｔｏ ｔｈｅ Ｔｈｅｏｒｙ ｏｆ ＮＰ−Ｃｏｍｐｌｅｔｅｎｅｓｓ： Ｗ．Ｈ． Ｆｒｅｅｍａｎ， Ｎｅｗ Ｙｏｒｋ， １９７９．
【非特許文献２】Ｊ． Ｘｕ， Ｊ． Ｃｈｅｍ． Ｉｎｆ． Ｃｏｍｐｕｔ．Ｓｃｉ． １９９６， ３６， ２５−３４．
【非特許文献３】Ｍ．Ｆ． Ｌｙｎｃｈ， Ｃｈｅｍｉｃａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ， Ｊ．Ｅ． Ａｓｈ， Ｅ． Ｈｙｄｅ ｅｄｓ．， Ｅｌｌｉｓ Ｈｏｒｗｏｏｄ， Ｃｈｉｃｈｅｓｔｅｒ， １９８５， ８８−９３．
【非特許文献４】久光徹、新田義彦、「日本語形態素解析における効率的な動詞活用処理」 情報処理学会研究会報告、９４−ＮＬ−１０３， １９９４年９月， １−７．
【非特許文献５】踊堂憲道、伊藤克亘、鹿野清宏、中村哲、「Ｎ−ｇｒａｍモデルのエントロピーに基づくパラメータ削減に関する検討」 情報処理学会論文誌 ２００１年２月 Ｖｏｌ．４２ Ｎｏ．２， ３２７−３３３
【発明の開示】
【発明が解決しようとする課題】
【０００７】
化学構造検索において、複数ユーザーによるＷｅｂ経由での同時アクセス要求及びデータベースに登録されている化合物の数は、年々増加（肥大化）傾向にあり、これまで以上の高速な化学構造検索手法が求められている。さらに、データベース自体においても商用の高価なデータベースに依存せず、かつスーパーコンピュータなど特殊なハードウェアを利用せずとも、高速化を実現可能とする検索手法の開発は、いわゆる「チープ革命」の恩恵（コンピュータの急激な高性能化と低価格化、及びオープンソースとして提供される高機能なフリーソフトウェアの出現により、安価に高機能なアプリケーションを開発できるようになったこと。「チープ革命」の詳細は、梅田望夫著「ウェブ進化」ちくま新書を参照。）をダイレクトに受けることができ、コストパフォーマンスの圧倒的に高い化学構造検索システムの開発を可能とする。
以上のことから、高速かつ安価な化学構造検索手法の開発は、大規模データベースに対する複数ユーザーの同時アクセス要求を満たすばかりでなく、これまで未開拓であった化学構造検索を利用したＷｅｂアプリケーションシステムの提供を可能にすると期待されている。
【課題を解決するための手段】
【０００８】
上記課題に鑑み、鋭意検討を重ねた結果、化学構造を“文書”とし、その部分構造を“単語”として表現することができれば、既存の全文検索システムをそのまま利用することができ、ＧｏｏｇｌｅやＹａｈｏｏ！レベルの高速な検索システムが化学構造検索においても実現できることを見出し、化学構造検索における“スクリーニング”を全文検索で実現可能とするＩＴＭＣｈｅｍＳｔｒｉｎｇ（ＩＴＣＳ）法を開発した。
本発明の要旨は以下のとおりである。
〔１〕 コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化する手段と、
該木構造を基に、該化合物を構成する全ての部分構造を文字列化する手段と、
得られた化合物の化学構造の文字列化表現及び化合物の部分構造の文字列化表現を、該化合物を識別するユニークなＩＤと共に、化学構造データベースとして記録保存するための記憶媒体と
を備える、所定の部分構造を有する化合物を検索するための化学構造検索システム。
〔２〕 １）コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化すること、及び、２）該木構造を基に、該化合物を構成する全ての部分構造を文字列化すること、によって得られた該化合物の部分構造の文字列化表現をクエリーとして上記〔１〕に記載の化学構造検索システムに対して検索要求を投げる工程と、
該化学構造検索システムに含まれる化学構造データベースを利用して、コンピュータが投げかけられた検索要求を全文検索処理し、検索結果として化合物を識別するユニークなＩＤとそれに該当する標的化合物の化学構造の文字列化表現を返す工程と、
得られた該ＩＤと標的化合物の化学構造の文字列化表現を化学構造検索処理して、検索結果として該部分構造を有する化合物のＩＤを提示する工程と
を含む、所定の部分構造を有する化合物を検索する方法。
【発明の効果】
【０００９】
本発明の化学構造検索では、化学構造を“文書”とし、その部分構造を“単語”として表現しているので、既存の全文検索システムをそのまま利用することができ、好適には、ＧｏｏｇｌｅやＹａｈｏｏ！レベルの高速な検索システムを化学構造検索においても実現できる。
【発明を実施するための最良の形態】
【００１０】
本明細書において化学構造検索は、化合物の部分構造検索及び完全構造検索を意味する。
【００１１】
本発明は、上述のような所定の部分構造を有する化合物を検索するための化学構造検索システムを提供する。上記各手段によって行われる処理の詳細は、後述するとおりである。
【００１２】
それぞれの文字列化に用いる手段は、手動であっても、コンピュータなどの情報処理手段を用いてもよいが、処理の効率化を考慮すると、コンピュータなどの情報処理手段を用い、最初に化合物の化学構造の入力を行えばその後の処理はコンピュータによって自動で行われるようなプログラム又はシステムを構築するのが好ましい。
【００１３】
化学構造データベースを記録保存するための記憶媒体としては、化合物の化学構造の文字列化表現、及び、化合物の部分構造の文字列化表現を、該化合物を識別するユニークなＩＤと共にデータベース化して記録保存することができるものであれば、いかなる記憶媒体であってもよい。例えば、そのような記憶媒体としては、コンピュータ内外に配置されたハードディスク、不揮発性メモリ、磁気ディスク、光ディスク、磁気テープなどが挙げられる。
【００１４】
化学構造データベースには、化合物を識別するユニークなＩＤ、化合物の化学構造の文字列化表現、及び、化合物の部分構造の文字列化表現以外にも、該化合物に関するこれら以外の諸情報を、化合物を識別するユニークなＩＤに関連づけて記録保存させておいてもよい。そのような情報としては、融点、沸点、分子量、ｌｏｇＰ、分子表面積など化合物が持つ固有の物性や、反応性、構造及び反応経路情報などが挙げられる。
【００１５】
本発明のＩＴＣＳ法の概要を図１に示す。
【００１６】
ＩＴＣＳ法において、標的化合物は、まず「ＩＴＣＳ生成プロセス」（詳細は後述）により、ＩＴＣＳが生成される。ＩＴＣＳとは化合物の化学構造を示す文字列（通常の全文検索における文書に相当する）である。
次に、「ＩＴＣＳ ＷＯＲＤ生成プロセス」（詳細は後述）により、ＩＴＣＳ ＷＯＲＤが生成される。ＩＴＣＳ ＷＯＲＤとは、化学構造を構成する全ての部分構造を列挙し、それらを文字列化したものである（通常の全文検索における単語に相当する）。
生成されたＩＴＣＳとＩＴＣＳ ＷＯＲＤはＩＤとその他付加情報と共にデータベースに格納される。ここで格納される標的化合物数は１〜数千万化合物であり、ＰｏｓｔｇｒｅＳＱＬ、ＭｙＳＱＬ、Ｏｒａｃｌｅなどのリレーショナルデータベースが利用できる。
【００１７】
クエリー化合物は、一般的な化学構造入力手段（例えば、汎用コンピュータ上で動く当該分野で慣用の化学構造描画ソフトウェア（例えば、ＣｈｅｍＤｒａｗ、ＩＳＩＳ／Ｄｒａｗなど）から、ｓｄｆ形式、ｍｏｌ２形式などの汎用の分子構造インターチェンジフォーマット形式で、入力され、標的化合物と同様にＩＴＣＳとＩＴＣＳ ＷＯＲＤが生成される。
次に、クエリー化合物のＩＴＣＳ ＷＯＲＤをクエリーとして、データベースに検索要求を投げる。データベースにおいては、投げられた検索要求（ＩＴＣＳ ＷＯＲＤ）に該当するデータを「全文検索プロセス」に対し、検索要求を出し、返答（ＩＤ）を得る。ここでの「全文検索プロセス」は、当業者に公知の手法であり、その手法は特に限定されず、全文検索に通常用いられているシステムを適宜利用することができる。例えば、データベース外部で利用するのであればＮａｍａｚｕ、Ｒａｓｔ、Ｅｓｔｒａｉｅｒなどを利用することができ、データベース内部で利用するのであれば、ＰｏｓｔｇｒｅＳＱＬにおいてはＴＳｅａｒｃｈ２などを利用することができる。
「全文検索プロセス」により得られたＩＤとそれに該当するＩＴＣＳをデータベースは、クエリーの返答として返す。
【００１８】
ここまでのプロセスが“スクリーニング”である。
【００１９】
最後に、スクリーニングにより得られたＩＤ ＋ ＩＴＣＳと、クエリー化合物のＩＴＣＳを「化学構造検索プロセス」により構造検索を実施し、ヒット化合物のＩＤ及び諸情報（例えば、融点、沸点、分子量、ｌｏｇＰ、分子表面積など化合物が持つ固有の物性や、反応性、構造及び反応経路情報など）を提示する。
ここでの「化学構造検索プロセス」は公知のバックトラッキング法を利用することができる。「化学構造検索プロセス」はデータベースの外部で利用するだけではく、データベースの内部に組み込んで利用することもできる。
【００２０】
以上のプロセスにより、大規模データベースから高速に化学構造を検索することが実現可能となる。
【００２１】
「ＩＴＣＳ生成プロセス」
化学構造の文字列（線形）表記は、公知のものとしてＷＬＮ、ＳＭＩＬＥＳ、ＲＯＳＤＡＬなどが知られており、広く利用されている。本発明では、拡張性の観点から公知の手法を利用するのではなく、独自にＩＴＣＳ表記を開発するに至った。ＩＴＣＳ生成プロセスを図２に示す。
【００２２】
ステップ１：
化学構造をｓｄｆ形式、ｍｏｌ２形式などの汎用の分子構造インターチェンジフォーマットで準備する。ここで、ヒュッケル則を用いて、芳香族としての性質をもつ結合の特定を行う。
【００２３】
ステップ２：
化学構造を木構造として取り扱い、ノードは原子に、エッジは結合に対応させる。ルートノードは任意の原子から始めることができ、ノードは、原子種、原子ＩＤ番号、訪問番号を、エッジは結合次数を保持している。ここで、原子ＩＤ番号は、化学構造を作成する際に任意の割り振り方で各原子に番号を割り振ってもよいが、通常は、分子構造インターチェンジフォーマットを準備する際に用いるソフトウェアに依存して割り振られる。
【００２４】
ステップ３：
ステップ２で作成した木のルートノードから、深さ優先探索によりルート決定を行う。「深さ優先探索」は公知のアルゴリズムである。この際、訪問するノードの順番（訪問番号）に従い、０から番号づけを行い、ノードに保持させる。
【００２５】
ステップ４：
ステップ３で作成したルートに従いＩＴＣＳを作成する。
ＩＴＣＳ化のルール：
・原子は原子名（Ｃ、Ｎ、Ｏなどの文字列）で表現する。
・結合は二重結合を‘ｄ’、三重結合を‘ｔ’、芳香族性の結合を‘ａ’、単結合は‘’（何もなし）で表現する。
・ルート上すでに訪問した原子は、原子名ではなく、訪問番号で表現する。この際、次に訪問するエッジの始まりのノードと現在訪問中のエッジの終わりのノードが異なれば、次のエッジの始まりの原子は‘＜訪問番号＞’で表現する。さらに、次のエッジの終わりの原子がすでに訪問されていれば、この原子は‘［訪問番号］’で表現する。例えば、図２のステップ３を参照して、現在訪問中のエッジがＮ（１）−Ｃ（２）とすると、次に訪問するエッジはＮ（１）−Ｃ（３）となる。この場合、現在訪問中の終わりのエッジはＣ（２）であり、次に訪問するエッジの始まりはＮ（１）となる。従って、同一ノードではないかつＮ（１）はすでに訪問されているノードなので＜１＞となる。
なお、[ ]を使うケースを、シクロヘキサンを例として以下に説明する。
【００２６】
【化１】
【００２７】
現在訪問中のエッジがＣ（４）−Ｃ（５）であり、次に訪問するエッジがＣ（０）−Ｃ（５）とすると、次のエッジの始まりと現在のエッジの終わりは異なりかつＣ（０）はすでに訪問しているので＜０＞となる。さらに次のエッジの終わりのノードＣ（５）もすでに訪問しているので、次のエッジは＜０＞［５］と表現される。
・最後に、‘／’（スラッシュ）を付加し、訪問番号の順序に従い原子ＩＤ番号を‘，’（コンマ）区切りで付加する。通常、化学構造を文字列化した場合、文字化後は、変換元になった化学構造ファイル上の原子ＩＤ番号を保持できない。そこで、本発明では、スラッシュ後にそれを付加することにより、原子ＩＤ番号の保持を可能としている。これにより、ＩＴＣＳを用いた化学構造検索で一致した原子と変換元の化学構造ファイル上の原子を一致させることができ、一致した原子の強調表示などを変換元の化学構造ファイル上で行うことができる。
【００２８】
「ＩＴＣＳ ＷＯＲＤ生成プロセス」
本プロセスの目的は、任意の化学構造を構成する全ての部分構造を列挙し、文字列（通常の全文検索における「単語」に相当）化することである。ＩＴＣＳ ＷＯＲＤ生成プロセスの主となる部分を図３及び４に示す。
【００２９】
ステップ１：
ＩＴＣＳ生成プロセスで作成した木を、“基本木”とする。
【００３０】
ステップ２：
基本木を基に、下記“成長木”構築ルールに基づき“成長木”を構築する。
“成長木”構築ルールに基づき木がこれ以上成長しなくなるまで実施する。ただし、木の深さは事前に設定する（ｎ＿ｄｅｐｔｈとして設定する）必要があり、１〜化学構造を構成する結合の数、まで設定できる。現在のコンピュータ資源の性能を考慮し、通常は、４〜７として設定する。
“成長木”構築ルール
・ベースノードの選択は、成長木に対する深さ優先探索の順序に基づき行い、初期のベースノードは、“基本木”上のルートノードとする。
・ベースノードへのノードとエッジの付加は、ベースノードに対応する“基本木”上のノードとその子ノード及びそれらが属するエッジ、さらに、祖先ノードが存在する場合には、祖先ノードとその子ノード及びそれらが属するエッジをベースノードにコピーすることにより実施する。ただし、祖先ノードとその子ノード及びそれらが属するエッジが、すでに成長木上のルートノードからベースノードまでの経路上に存在していれば、付加しない。ここで祖先ノードとは、ベースノードからルートノードまでの経路上に位置するノードを示す。
【００３１】
ステップ３：
ステップ２で構築された成長木のルートノードから末端ノードまでの全ての経路を列挙する。そして、各々の経路をルートノードから、深さ１，２，…，ｎ＿ｄｅｐｔｈ−１とそれぞれ切断することにより、部分構造に対応する経路が生成される。
ここで生成された全ての経路は、「ＩＴＣＳ生成プロセス」と同じアルゴリズムを用いて文字列化される。ここで生成された文字列をＩＴＣＳ ＷＯＲＤと呼ぶ。
【００３２】
ステップ４：
ステップ１〜ステップ３の処理は、化合構造を構成する全ての原子をルートノードとして、繰り返し実施される。この処理により、化学構造中のｎ＿ｄｅｐｔｈ長までで構成される全ての部分構造をＩＴＣＳ ＷＯＲＤとして文字列化することができる。
【００３３】
ステップ５：
ある１つの化学構造は、複数のＩＴＣＳ ＷＯＲＤによる表現が可能となるため、それらＩＴＣＳ ＷＯＲＤを辞書式にアルファベット順に並べ最も大きいものを代表として用いる。例えば、ＣＣＮとＮＣＣは同じ構造を示すが、これを辞書式にアルファベット順に並べるとＮＣＣ ＞ ＣＣＮとなり、その代表はＮＣＣとなる。これにより１つの構造は１つのＩＴＣＳ ＷＯＲＤに対応することになる。
【００３４】
ステップ６：
ある１つの化学構造の中に、同じ部分構造（ＩＴＣＳ ＷＯＲＤ）が複数存在するとき、そのＩＴＣＳ ＷＯＲＤの後ろに数値を付加する。ただし、数値の最大値は６とし、１は省略する。例えば、ＳＣＯ＜１＞Ｎが３つ存在するとき生成されるＩＴＣＳ ＷＯＲＤは、ＳＣＯ＜１＞Ｎ、ＳＣＯ＜１＞Ｎ２、ＳＣＯ＜１＞Ｎ３、となる。さらに設定したｎ＿ｄｅｐｔｈ長では表現できない特殊な部分構造もこのステップで外部ＩＴＣＳ ＷＯＲＤとして付加することができる。例えば、ＣＣＣＣＣＣＣＣＣＣＣＣＣＣやＣＣＮＣＣＮＣＣＮＣＣＮＣＣＮＣＣＮなど連続した炭素の繋がりや、連続した繰り返し構造など。
ただし、クエリーとして用いるＩＴＣＳ ＷＯＲＤはｎ＿ｄｅｐｔｈ長のＩＴＣＳ ＷＯＲＤと外部ＩＴＣＳ ＷＯＲＤのみで十分である（それ以下の部分構造は、ｎ＿ｄｅｐｔｈ長のＩＴＣＳ ＷＯＲＤ内に含まれているため）。
化学構造を構成する結合の数にｎ＿ｄｅｐｔｈを設定した場合、原理的には、全ての部分構造をＩＴＣＳ ＷＯＲＤとして文字列化することができるため、スクリーニングのみで化学構造検索が完結する。したがって、バックトラック法などの既存の化学構造検索を利用しなくてもよくなる。しかしながら、ｎ＿ｄｅｐｔｈを大きくすればするほど、ＩＴＣＳ ＷＯＲＤが指数関数的に増加するため、現在のコンピュータ資源の性能を考慮すると、現状では４〜７が適切である。しかしながら、コンピュータ性能が向上すれば、ｎ＿ｄｅｐｔｈをより大きくすることが可能である。
【実施例】
【００３５】
化学構造検索事例
化学構造の検索事例として、以下に示すクエリー構造を用いて実施した。
【００３６】
【化２】
【００３７】
クエリー構造のＩＴＣＳとＩＴＣＳ ＷＯＲＤを以下に示す。
ＩＴＣＳ：
ＣＮＣＣＮＣＣ＜４＞Ｃ＜１＞［６］＜０＞ＣａＣａＣＣ＜１０＞ａＣａＣａＣ＜８＞ａ［１４］＜０＞ｄＯ／１，２，７，１０，４，９，８，１３，３，６，１１，１６，１５，１４，１２，５
ＩＴＣＳ ＷＯＲＤ：
“ＣａＣａＣａＣａＣａＣａ［０］ ＮＣＣａＣａＣ ＮＣＣａＣ＜２＞ａＣ ＮＣＣａＣ＜０＞Ｃ ＮＣＣ＜０＞ＣＣ ＮＣＣ＜０＞Ｃ＜０＞Ｃ ＮＣＣＮＣ ＣａＣａＣＣ＜０＞Ｃ ＣａＣａＣａＣａＣ ＣａＣａＣａＣ＜２＞Ｃ ＣａＣａＣａＣＣ ＯｄＣＮＣＣ ＯｄＣＮＣ＜２＞Ｃ ＯｄＣＮＣ＜１＞Ｃ ＯｄＣＮ＜１＞ＣａＣ ＯｄＣＣａＣａＣ ＯｄＣＣａＣ＜２＞ａＣ ＮＣＣａＣａＣ２ ＮＣＣａＣ＜０＞Ｃ４ ＮＣＣ＜０＞ＣＣ４ ＮＣＣ＜０＞Ｃ＜０＞Ｃ５ ＮＣＣＮＣ６ ＣａＣａＣａＣａＣ６ ＣａＣａＣａＣ＜２＞Ｃ４ ＣａＣａＣａＣＣ４ ＯｄＣＮＣＣ２ ＯｄＣＮＣ＜１＞Ｃ２ ＯｄＣＮ＜１＞ＣａＣ２ ＯｄＣＣａＣａＣ２”
【００３８】
ＩＴＣＳ法を用いた場合と用いない場合において、データベースに含まれる化合物のデータ数と検索時間にどの程度の差が生じるかを調べることによりＩＴＣＳ法の有効性を検証した。ここで、ＩＴＣＳ法を用いない場合というのは、バックトラック法による化学構造検索のみでの検索を示す。結果を以下の表及び図５に示す。また、ヒットした化合物の例も以下に示す。
【００３９】
【表１】
【００４０】
【化３】
【００４１】
これらの結果から、ＩＴＣＳ法を用いた場合、バックトラック法のみと比較して１００倍以上（保存データ数１０００００の場合）の検索速度の向上が見られた。従って、本発明によれば、大規模な化学構造データベースから所定の部分構造を有する化合物を高速に検索することが可能となる。
【図面の簡単な説明】
【００４２】
【図１】本発明の化学構造検索方法に基づくシステムの概要図である。
【図２】ＩＴＣＳ生成プロセスを説明する図である。
【図３】ＩＴＣＳ ＷＯＲＤ生成プロセスを説明する図である。
【図４】図３の続きである。
【図５】ＩＴＣＳ法を用いた場合と用いない場合において、データベースに含まれる化合物のデータ数と検索時間にどの程度の差が生じるかを調べた結果を示すグラフである。
【技術分野】
【０００１】
本発明は、大規模な化学構造データベースから高速に化学構造を検索するシステム及び方法に関する。
【背景技術】
【０００２】
化学構造データベースは、現代の化学・創薬研究において欠くことのできない重要なツールとなっているばかりでなく、特許情報や試薬管理などにおいても必要不可欠なツールとなっている。例えば、Ｃｈｅｍｉｃａｌ Ａｂｓｔｒａｃｔｓ Ｓｙｓｔｅｍに対する化学構造検索では、ＳｃｉＦｉｎｄｅｒ［ｈｔｔｐ：／／ｗｗｗ．ｊａｉｃｉ．ｏｒ．ｊｐ／ｓｃｉ／ＳＣＨＯＬＡＲ／ｉｎｄｅｘ．ｈｔｍｌ］が、企業内データベースに対する化学構造検索では、ＩＳＩＳ［ｈｔｔｐ：／／ｗｗｗ．ｍｄｌｉ．ｃｏｍ／］などが広く利用されている。
【０００３】
化学構造検索アルゴリズムの開発は、１９６０年以来、多くの科学者が徹底的な研究を行ってきた。部分構造検索は、指定したクエリー構造が、与えられた標的構造の中に含まれているかどうかを判定する作業である。グラフ理論の用語を用いれば、部分構造検索はクエリーグラフ（ＧＱ）が、標的グラフ（ＧＴ）の部分グラフと同形であるかどうかを調べる作業であり、ＧＱとＧＴの部分グラフ間の同形を探すことは、ＮＰ完全問題であることが知られている［非特許文献１］。したがって、一般的に、同形をすばやく判定することは非常に困難な作業であるが、多くの部分構造検索手法は、バックトラッキング法を効率的に利用して、この問題を解決している［非特許文献２］。
【０００４】
しかしながら、５０，０００以上の化学構造データベースから化学構造検索を実施するには、バックトラッキング法だけでは、多くの検索時間（数十秒〜）を必要とし、実用的ではない。そこで、バックトラッキング法を行う前に、明らかに同形ではないグラフ（化学構造）を高速に除去する“スクリーニング”と呼ばれる手法が開発された。
通常、スクリーニング手法は、化学構造をビット文字列で表現する。各ビットは、任意のフラグメント（ベンゼン環、アミド基など）を意味し、１は、そのフラグメントが化学構造中に存在することを、０は存在しないことを示す。化学構造データベース中の標的構造は、事前にこのビット文字列を生成させ、データベースに保持しておく、クエリー構造のビット文字列は、検索時に生成させる。次に、クエリー構造のビット文字列と標的構造のビット文字列を順次比較し、クエリー構造のビット文字列中に存在する少なくとも１つの１の立ったビットが標的構造のビット文字列中に存在しなければ、同形の可能性はないとして除去される。この計算は、ビット演算子（ＡＮＤ、ＯＲ、ＸＯＲ）を用いて計算できるので、非常に高速に処理できる［非特許文献３］。一般的に、ビット文字列を用いたスクリーニング手法、及びその改良型を用いることで、全体として１０倍〜２０倍の高速化が実現されるため、現在、多くの構造検索システムで利用されている。
【０００５】
通常、データベースに対する検索の高速化は、インデックス（本の索引に相当する）を用いて実現されている。インデックスは、数値や文字列を対象としているため、ビット文字列同士の演算を必要とする既存の化学構造検索においては、有効に利用することができない。したがって、化学構造検索の多くは、データベースの最初から最後まで順次、ビット演算を繰り返す必要があり、高速化のもっとも大きなボトルネックとなっている。
【０００６】
一方、近年、大規模データベースに対する検索システムとして、もっとも利用されているものは、ＧｏｏｇｌｅやＹａｈｏｏ！の検索エンジンに代表される“大量の文書の中から特定の文字列を含む文書を検索する”全文検索システムである。全文検索システムの検索速度の速さは、検索エンジンを利用する誰しもが納得するレベルであり、自明である。通常、全文検索システムでは、形態素解析［非特許文献４］やＮ−ｇｒａｍ法［非特許文献５］を用いて文書を単語に分解し、次に、この単語を転置インデックス法などでインデックス化する。この作業により、どの単語がどの文書内に存在するかを高速に検索可能としている。
【非特許文献１】Ｍ． Ｇａｒｅｙ， Ｄ．Ｊｏｈｎｓｏｎ， Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｉｎｔｒａｃｔａｂｉｌｉｔｙ； Ａ Ｇｕｉｄｅ ｔｏ ｔｈｅ Ｔｈｅｏｒｙ ｏｆ ＮＰ−Ｃｏｍｐｌｅｔｅｎｅｓｓ： Ｗ．Ｈ． Ｆｒｅｅｍａｎ， Ｎｅｗ Ｙｏｒｋ， １９７９．
【非特許文献２】Ｊ． Ｘｕ， Ｊ． Ｃｈｅｍ． Ｉｎｆ． Ｃｏｍｐｕｔ．Ｓｃｉ． １９９６， ３６， ２５−３４．
【非特許文献３】Ｍ．Ｆ． Ｌｙｎｃｈ， Ｃｈｅｍｉｃａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ， Ｊ．Ｅ． Ａｓｈ， Ｅ． Ｈｙｄｅ ｅｄｓ．， Ｅｌｌｉｓ Ｈｏｒｗｏｏｄ， Ｃｈｉｃｈｅｓｔｅｒ， １９８５， ８８−９３．
【非特許文献４】久光徹、新田義彦、「日本語形態素解析における効率的な動詞活用処理」 情報処理学会研究会報告、９４−ＮＬ−１０３， １９９４年９月， １−７．
【非特許文献５】踊堂憲道、伊藤克亘、鹿野清宏、中村哲、「Ｎ−ｇｒａｍモデルのエントロピーに基づくパラメータ削減に関する検討」 情報処理学会論文誌 ２００１年２月 Ｖｏｌ．４２ Ｎｏ．２， ３２７−３３３
【発明の開示】
【発明が解決しようとする課題】
【０００７】
化学構造検索において、複数ユーザーによるＷｅｂ経由での同時アクセス要求及びデータベースに登録されている化合物の数は、年々増加（肥大化）傾向にあり、これまで以上の高速な化学構造検索手法が求められている。さらに、データベース自体においても商用の高価なデータベースに依存せず、かつスーパーコンピュータなど特殊なハードウェアを利用せずとも、高速化を実現可能とする検索手法の開発は、いわゆる「チープ革命」の恩恵（コンピュータの急激な高性能化と低価格化、及びオープンソースとして提供される高機能なフリーソフトウェアの出現により、安価に高機能なアプリケーションを開発できるようになったこと。「チープ革命」の詳細は、梅田望夫著「ウェブ進化」ちくま新書を参照。）をダイレクトに受けることができ、コストパフォーマンスの圧倒的に高い化学構造検索システムの開発を可能とする。
以上のことから、高速かつ安価な化学構造検索手法の開発は、大規模データベースに対する複数ユーザーの同時アクセス要求を満たすばかりでなく、これまで未開拓であった化学構造検索を利用したＷｅｂアプリケーションシステムの提供を可能にすると期待されている。
【課題を解決するための手段】
【０００８】
上記課題に鑑み、鋭意検討を重ねた結果、化学構造を“文書”とし、その部分構造を“単語”として表現することができれば、既存の全文検索システムをそのまま利用することができ、ＧｏｏｇｌｅやＹａｈｏｏ！レベルの高速な検索システムが化学構造検索においても実現できることを見出し、化学構造検索における“スクリーニング”を全文検索で実現可能とするＩＴＭＣｈｅｍＳｔｒｉｎｇ（ＩＴＣＳ）法を開発した。
本発明の要旨は以下のとおりである。
〔１〕 コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化する手段と、
該木構造を基に、該化合物を構成する全ての部分構造を文字列化する手段と、
得られた化合物の化学構造の文字列化表現及び化合物の部分構造の文字列化表現を、該化合物を識別するユニークなＩＤと共に、化学構造データベースとして記録保存するための記憶媒体と
を備える、所定の部分構造を有する化合物を検索するための化学構造検索システム。
〔２〕 １）コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化すること、及び、２）該木構造を基に、該化合物を構成する全ての部分構造を文字列化すること、によって得られた該化合物の部分構造の文字列化表現をクエリーとして上記〔１〕に記載の化学構造検索システムに対して検索要求を投げる工程と、
該化学構造検索システムに含まれる化学構造データベースを利用して、コンピュータが投げかけられた検索要求を全文検索処理し、検索結果として化合物を識別するユニークなＩＤとそれに該当する標的化合物の化学構造の文字列化表現を返す工程と、
得られた該ＩＤと標的化合物の化学構造の文字列化表現を化学構造検索処理して、検索結果として該部分構造を有する化合物のＩＤを提示する工程と
を含む、所定の部分構造を有する化合物を検索する方法。
【発明の効果】
【０００９】
本発明の化学構造検索では、化学構造を“文書”とし、その部分構造を“単語”として表現しているので、既存の全文検索システムをそのまま利用することができ、好適には、ＧｏｏｇｌｅやＹａｈｏｏ！レベルの高速な検索システムを化学構造検索においても実現できる。
【発明を実施するための最良の形態】
【００１０】
本明細書において化学構造検索は、化合物の部分構造検索及び完全構造検索を意味する。
【００１１】
本発明は、上述のような所定の部分構造を有する化合物を検索するための化学構造検索システムを提供する。上記各手段によって行われる処理の詳細は、後述するとおりである。
【００１２】
それぞれの文字列化に用いる手段は、手動であっても、コンピュータなどの情報処理手段を用いてもよいが、処理の効率化を考慮すると、コンピュータなどの情報処理手段を用い、最初に化合物の化学構造の入力を行えばその後の処理はコンピュータによって自動で行われるようなプログラム又はシステムを構築するのが好ましい。
【００１３】
化学構造データベースを記録保存するための記憶媒体としては、化合物の化学構造の文字列化表現、及び、化合物の部分構造の文字列化表現を、該化合物を識別するユニークなＩＤと共にデータベース化して記録保存することができるものであれば、いかなる記憶媒体であってもよい。例えば、そのような記憶媒体としては、コンピュータ内外に配置されたハードディスク、不揮発性メモリ、磁気ディスク、光ディスク、磁気テープなどが挙げられる。
【００１４】
化学構造データベースには、化合物を識別するユニークなＩＤ、化合物の化学構造の文字列化表現、及び、化合物の部分構造の文字列化表現以外にも、該化合物に関するこれら以外の諸情報を、化合物を識別するユニークなＩＤに関連づけて記録保存させておいてもよい。そのような情報としては、融点、沸点、分子量、ｌｏｇＰ、分子表面積など化合物が持つ固有の物性や、反応性、構造及び反応経路情報などが挙げられる。
【００１５】
本発明のＩＴＣＳ法の概要を図１に示す。
【００１６】
ＩＴＣＳ法において、標的化合物は、まず「ＩＴＣＳ生成プロセス」（詳細は後述）により、ＩＴＣＳが生成される。ＩＴＣＳとは化合物の化学構造を示す文字列（通常の全文検索における文書に相当する）である。
次に、「ＩＴＣＳ ＷＯＲＤ生成プロセス」（詳細は後述）により、ＩＴＣＳ ＷＯＲＤが生成される。ＩＴＣＳ ＷＯＲＤとは、化学構造を構成する全ての部分構造を列挙し、それらを文字列化したものである（通常の全文検索における単語に相当する）。
生成されたＩＴＣＳとＩＴＣＳ ＷＯＲＤはＩＤとその他付加情報と共にデータベースに格納される。ここで格納される標的化合物数は１〜数千万化合物であり、ＰｏｓｔｇｒｅＳＱＬ、ＭｙＳＱＬ、Ｏｒａｃｌｅなどのリレーショナルデータベースが利用できる。
【００１７】
クエリー化合物は、一般的な化学構造入力手段（例えば、汎用コンピュータ上で動く当該分野で慣用の化学構造描画ソフトウェア（例えば、ＣｈｅｍＤｒａｗ、ＩＳＩＳ／Ｄｒａｗなど）から、ｓｄｆ形式、ｍｏｌ２形式などの汎用の分子構造インターチェンジフォーマット形式で、入力され、標的化合物と同様にＩＴＣＳとＩＴＣＳ ＷＯＲＤが生成される。
次に、クエリー化合物のＩＴＣＳ ＷＯＲＤをクエリーとして、データベースに検索要求を投げる。データベースにおいては、投げられた検索要求（ＩＴＣＳ ＷＯＲＤ）に該当するデータを「全文検索プロセス」に対し、検索要求を出し、返答（ＩＤ）を得る。ここでの「全文検索プロセス」は、当業者に公知の手法であり、その手法は特に限定されず、全文検索に通常用いられているシステムを適宜利用することができる。例えば、データベース外部で利用するのであればＮａｍａｚｕ、Ｒａｓｔ、Ｅｓｔｒａｉｅｒなどを利用することができ、データベース内部で利用するのであれば、ＰｏｓｔｇｒｅＳＱＬにおいてはＴＳｅａｒｃｈ２などを利用することができる。
「全文検索プロセス」により得られたＩＤとそれに該当するＩＴＣＳをデータベースは、クエリーの返答として返す。
【００１８】
ここまでのプロセスが“スクリーニング”である。
【００１９】
最後に、スクリーニングにより得られたＩＤ ＋ ＩＴＣＳと、クエリー化合物のＩＴＣＳを「化学構造検索プロセス」により構造検索を実施し、ヒット化合物のＩＤ及び諸情報（例えば、融点、沸点、分子量、ｌｏｇＰ、分子表面積など化合物が持つ固有の物性や、反応性、構造及び反応経路情報など）を提示する。
ここでの「化学構造検索プロセス」は公知のバックトラッキング法を利用することができる。「化学構造検索プロセス」はデータベースの外部で利用するだけではく、データベースの内部に組み込んで利用することもできる。
【００２０】
以上のプロセスにより、大規模データベースから高速に化学構造を検索することが実現可能となる。
【００２１】
「ＩＴＣＳ生成プロセス」
化学構造の文字列（線形）表記は、公知のものとしてＷＬＮ、ＳＭＩＬＥＳ、ＲＯＳＤＡＬなどが知られており、広く利用されている。本発明では、拡張性の観点から公知の手法を利用するのではなく、独自にＩＴＣＳ表記を開発するに至った。ＩＴＣＳ生成プロセスを図２に示す。
【００２２】
ステップ１：
化学構造をｓｄｆ形式、ｍｏｌ２形式などの汎用の分子構造インターチェンジフォーマットで準備する。ここで、ヒュッケル則を用いて、芳香族としての性質をもつ結合の特定を行う。
【００２３】
ステップ２：
化学構造を木構造として取り扱い、ノードは原子に、エッジは結合に対応させる。ルートノードは任意の原子から始めることができ、ノードは、原子種、原子ＩＤ番号、訪問番号を、エッジは結合次数を保持している。ここで、原子ＩＤ番号は、化学構造を作成する際に任意の割り振り方で各原子に番号を割り振ってもよいが、通常は、分子構造インターチェンジフォーマットを準備する際に用いるソフトウェアに依存して割り振られる。
【００２４】
ステップ３：
ステップ２で作成した木のルートノードから、深さ優先探索によりルート決定を行う。「深さ優先探索」は公知のアルゴリズムである。この際、訪問するノードの順番（訪問番号）に従い、０から番号づけを行い、ノードに保持させる。
【００２５】
ステップ４：
ステップ３で作成したルートに従いＩＴＣＳを作成する。
ＩＴＣＳ化のルール：
・原子は原子名（Ｃ、Ｎ、Ｏなどの文字列）で表現する。
・結合は二重結合を‘ｄ’、三重結合を‘ｔ’、芳香族性の結合を‘ａ’、単結合は‘’（何もなし）で表現する。
・ルート上すでに訪問した原子は、原子名ではなく、訪問番号で表現する。この際、次に訪問するエッジの始まりのノードと現在訪問中のエッジの終わりのノードが異なれば、次のエッジの始まりの原子は‘＜訪問番号＞’で表現する。さらに、次のエッジの終わりの原子がすでに訪問されていれば、この原子は‘［訪問番号］’で表現する。例えば、図２のステップ３を参照して、現在訪問中のエッジがＮ（１）−Ｃ（２）とすると、次に訪問するエッジはＮ（１）−Ｃ（３）となる。この場合、現在訪問中の終わりのエッジはＣ（２）であり、次に訪問するエッジの始まりはＮ（１）となる。従って、同一ノードではないかつＮ（１）はすでに訪問されているノードなので＜１＞となる。
なお、[ ]を使うケースを、シクロヘキサンを例として以下に説明する。
【００２６】
【化１】
【００２７】
現在訪問中のエッジがＣ（４）−Ｃ（５）であり、次に訪問するエッジがＣ（０）−Ｃ（５）とすると、次のエッジの始まりと現在のエッジの終わりは異なりかつＣ（０）はすでに訪問しているので＜０＞となる。さらに次のエッジの終わりのノードＣ（５）もすでに訪問しているので、次のエッジは＜０＞［５］と表現される。
・最後に、‘／’（スラッシュ）を付加し、訪問番号の順序に従い原子ＩＤ番号を‘，’（コンマ）区切りで付加する。通常、化学構造を文字列化した場合、文字化後は、変換元になった化学構造ファイル上の原子ＩＤ番号を保持できない。そこで、本発明では、スラッシュ後にそれを付加することにより、原子ＩＤ番号の保持を可能としている。これにより、ＩＴＣＳを用いた化学構造検索で一致した原子と変換元の化学構造ファイル上の原子を一致させることができ、一致した原子の強調表示などを変換元の化学構造ファイル上で行うことができる。
【００２８】
「ＩＴＣＳ ＷＯＲＤ生成プロセス」
本プロセスの目的は、任意の化学構造を構成する全ての部分構造を列挙し、文字列（通常の全文検索における「単語」に相当）化することである。ＩＴＣＳ ＷＯＲＤ生成プロセスの主となる部分を図３及び４に示す。
【００２９】
ステップ１：
ＩＴＣＳ生成プロセスで作成した木を、“基本木”とする。
【００３０】
ステップ２：
基本木を基に、下記“成長木”構築ルールに基づき“成長木”を構築する。
“成長木”構築ルールに基づき木がこれ以上成長しなくなるまで実施する。ただし、木の深さは事前に設定する（ｎ＿ｄｅｐｔｈとして設定する）必要があり、１〜化学構造を構成する結合の数、まで設定できる。現在のコンピュータ資源の性能を考慮し、通常は、４〜７として設定する。
“成長木”構築ルール
・ベースノードの選択は、成長木に対する深さ優先探索の順序に基づき行い、初期のベースノードは、“基本木”上のルートノードとする。
・ベースノードへのノードとエッジの付加は、ベースノードに対応する“基本木”上のノードとその子ノード及びそれらが属するエッジ、さらに、祖先ノードが存在する場合には、祖先ノードとその子ノード及びそれらが属するエッジをベースノードにコピーすることにより実施する。ただし、祖先ノードとその子ノード及びそれらが属するエッジが、すでに成長木上のルートノードからベースノードまでの経路上に存在していれば、付加しない。ここで祖先ノードとは、ベースノードからルートノードまでの経路上に位置するノードを示す。
【００３１】
ステップ３：
ステップ２で構築された成長木のルートノードから末端ノードまでの全ての経路を列挙する。そして、各々の経路をルートノードから、深さ１，２，…，ｎ＿ｄｅｐｔｈ−１とそれぞれ切断することにより、部分構造に対応する経路が生成される。
ここで生成された全ての経路は、「ＩＴＣＳ生成プロセス」と同じアルゴリズムを用いて文字列化される。ここで生成された文字列をＩＴＣＳ ＷＯＲＤと呼ぶ。
【００３２】
ステップ４：
ステップ１〜ステップ３の処理は、化合構造を構成する全ての原子をルートノードとして、繰り返し実施される。この処理により、化学構造中のｎ＿ｄｅｐｔｈ長までで構成される全ての部分構造をＩＴＣＳ ＷＯＲＤとして文字列化することができる。
【００３３】
ステップ５：
ある１つの化学構造は、複数のＩＴＣＳ ＷＯＲＤによる表現が可能となるため、それらＩＴＣＳ ＷＯＲＤを辞書式にアルファベット順に並べ最も大きいものを代表として用いる。例えば、ＣＣＮとＮＣＣは同じ構造を示すが、これを辞書式にアルファベット順に並べるとＮＣＣ ＞ ＣＣＮとなり、その代表はＮＣＣとなる。これにより１つの構造は１つのＩＴＣＳ ＷＯＲＤに対応することになる。
【００３４】
ステップ６：
ある１つの化学構造の中に、同じ部分構造（ＩＴＣＳ ＷＯＲＤ）が複数存在するとき、そのＩＴＣＳ ＷＯＲＤの後ろに数値を付加する。ただし、数値の最大値は６とし、１は省略する。例えば、ＳＣＯ＜１＞Ｎが３つ存在するとき生成されるＩＴＣＳ ＷＯＲＤは、ＳＣＯ＜１＞Ｎ、ＳＣＯ＜１＞Ｎ２、ＳＣＯ＜１＞Ｎ３、となる。さらに設定したｎ＿ｄｅｐｔｈ長では表現できない特殊な部分構造もこのステップで外部ＩＴＣＳ ＷＯＲＤとして付加することができる。例えば、ＣＣＣＣＣＣＣＣＣＣＣＣＣＣやＣＣＮＣＣＮＣＣＮＣＣＮＣＣＮＣＣＮなど連続した炭素の繋がりや、連続した繰り返し構造など。
ただし、クエリーとして用いるＩＴＣＳ ＷＯＲＤはｎ＿ｄｅｐｔｈ長のＩＴＣＳ ＷＯＲＤと外部ＩＴＣＳ ＷＯＲＤのみで十分である（それ以下の部分構造は、ｎ＿ｄｅｐｔｈ長のＩＴＣＳ ＷＯＲＤ内に含まれているため）。
化学構造を構成する結合の数にｎ＿ｄｅｐｔｈを設定した場合、原理的には、全ての部分構造をＩＴＣＳ ＷＯＲＤとして文字列化することができるため、スクリーニングのみで化学構造検索が完結する。したがって、バックトラック法などの既存の化学構造検索を利用しなくてもよくなる。しかしながら、ｎ＿ｄｅｐｔｈを大きくすればするほど、ＩＴＣＳ ＷＯＲＤが指数関数的に増加するため、現在のコンピュータ資源の性能を考慮すると、現状では４〜７が適切である。しかしながら、コンピュータ性能が向上すれば、ｎ＿ｄｅｐｔｈをより大きくすることが可能である。
【実施例】
【００３５】
化学構造検索事例
化学構造の検索事例として、以下に示すクエリー構造を用いて実施した。
【００３６】
【化２】
【００３７】
クエリー構造のＩＴＣＳとＩＴＣＳ ＷＯＲＤを以下に示す。
ＩＴＣＳ：
ＣＮＣＣＮＣＣ＜４＞Ｃ＜１＞［６］＜０＞ＣａＣａＣＣ＜１０＞ａＣａＣａＣ＜８＞ａ［１４］＜０＞ｄＯ／１，２，７，１０，４，９，８，１３，３，６，１１，１６，１５，１４，１２，５
ＩＴＣＳ ＷＯＲＤ：
“ＣａＣａＣａＣａＣａＣａ［０］ ＮＣＣａＣａＣ ＮＣＣａＣ＜２＞ａＣ ＮＣＣａＣ＜０＞Ｃ ＮＣＣ＜０＞ＣＣ ＮＣＣ＜０＞Ｃ＜０＞Ｃ ＮＣＣＮＣ ＣａＣａＣＣ＜０＞Ｃ ＣａＣａＣａＣａＣ ＣａＣａＣａＣ＜２＞Ｃ ＣａＣａＣａＣＣ ＯｄＣＮＣＣ ＯｄＣＮＣ＜２＞Ｃ ＯｄＣＮＣ＜１＞Ｃ ＯｄＣＮ＜１＞ＣａＣ ＯｄＣＣａＣａＣ ＯｄＣＣａＣ＜２＞ａＣ ＮＣＣａＣａＣ２ ＮＣＣａＣ＜０＞Ｃ４ ＮＣＣ＜０＞ＣＣ４ ＮＣＣ＜０＞Ｃ＜０＞Ｃ５ ＮＣＣＮＣ６ ＣａＣａＣａＣａＣ６ ＣａＣａＣａＣ＜２＞Ｃ４ ＣａＣａＣａＣＣ４ ＯｄＣＮＣＣ２ ＯｄＣＮＣ＜１＞Ｃ２ ＯｄＣＮ＜１＞ＣａＣ２ ＯｄＣＣａＣａＣ２”
【００３８】
ＩＴＣＳ法を用いた場合と用いない場合において、データベースに含まれる化合物のデータ数と検索時間にどの程度の差が生じるかを調べることによりＩＴＣＳ法の有効性を検証した。ここで、ＩＴＣＳ法を用いない場合というのは、バックトラック法による化学構造検索のみでの検索を示す。結果を以下の表及び図５に示す。また、ヒットした化合物の例も以下に示す。
【００３９】
【表１】
【００４０】
【化３】
【００４１】
これらの結果から、ＩＴＣＳ法を用いた場合、バックトラック法のみと比較して１００倍以上（保存データ数１０００００の場合）の検索速度の向上が見られた。従って、本発明によれば、大規模な化学構造データベースから所定の部分構造を有する化合物を高速に検索することが可能となる。
【図面の簡単な説明】
【００４２】
【図１】本発明の化学構造検索方法に基づくシステムの概要図である。
【図２】ＩＴＣＳ生成プロセスを説明する図である。
【図３】ＩＴＣＳ ＷＯＲＤ生成プロセスを説明する図である。
【図４】図３の続きである。
【図５】ＩＴＣＳ法を用いた場合と用いない場合において、データベースに含まれる化合物のデータ数と検索時間にどの程度の差が生じるかを調べた結果を示すグラフである。
【特許請求の範囲】
【請求項１】
コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化する手段と、
該木構造を基に、該化合物を構成する全ての部分構造を文字列化する手段と、
得られた化合物の化学構造の文字列化表現及び化合物の部分構造の文字列化表現を、該化合物を識別するユニークなＩＤと共に、化学構造データベースとして記録保存するための記憶媒体と
を備える、所定の部分構造を有する化合物を検索するための化学構造検索システム。
【請求項２】
１）コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化すること、及び、２）該木構造を基に、該化合物を構成する全ての部分構造を文字列化すること、によって得られた該化合物の部分構造の文字列化表現をクエリーとして請求項１に記載の化学構造検索システムに対して検索要求を投げる工程と、
該化学構造検索システムに含まれる化学構造データベースを利用して、コンピュータが投げかけられた検索要求を全文検索処理し、検索結果として化合物を識別するユニークなＩＤとそれに該当する標的化合物の化学構造の文字列化表現を返す工程と、
得られた該ＩＤと標的化合物の化学構造の文字列化表現を化学構造検索処理して、検索結果として該部分構造を有する化合物のＩＤを提示する工程と
を含む、所定の部分構造を有する化合物を検索する方法。
【請求項１】
コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化する手段と、
該木構造を基に、該化合物を構成する全ての部分構造を文字列化する手段と、
得られた化合物の化学構造の文字列化表現及び化合物の部分構造の文字列化表現を、該化合物を識別するユニークなＩＤと共に、化学構造データベースとして記録保存するための記憶媒体と
を備える、所定の部分構造を有する化合物を検索するための化学構造検索システム。
【請求項２】
１）コンピュータに入力された化合物の化学構造を、原子に対応するノードと、原子間の結合に対応するエッジからなる木構造として表現し、ノードの１つからルートノードを選択し、該ルートノードから深さ優先探索により経路決定を行い、該決定された経路に従い該化合物の化学構造を文字列化すること、及び、２）該木構造を基に、該化合物を構成する全ての部分構造を文字列化すること、によって得られた該化合物の部分構造の文字列化表現をクエリーとして請求項１に記載の化学構造検索システムに対して検索要求を投げる工程と、
該化学構造検索システムに含まれる化学構造データベースを利用して、コンピュータが投げかけられた検索要求を全文検索処理し、検索結果として化合物を識別するユニークなＩＤとそれに該当する標的化合物の化学構造の文字列化表現を返す工程と、
得られた該ＩＤと標的化合物の化学構造の文字列化表現を化学構造検索処理して、検索結果として該部分構造を有する化合物のＩＤを提示する工程と
を含む、所定の部分構造を有する化合物を検索する方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００７−３２３１８２（Ｐ２００７−３２３１８２Ａ）
【公開日】平成１９年１２月１３日（２００７．１２．１３）
【国際特許分類】
【出願番号】特願２００６−１５０３４２（Ｐ２００６−１５０３４２）
【出願日】平成１８年５月３０日（２００６．５．３０）
【出願人】（５０４３６５１４６）株式会社理論創薬研究所 (9)
【Ｆターム（参考）】
【公開日】平成１９年１２月１３日（２００７．１２．１３）
【国際特許分類】
【出願日】平成１８年５月３０日（２００６．５．３０）
【出願人】（５０４３６５１４６）株式会社理論創薬研究所 (9)
【Ｆターム（参考）】
[ Back to top ]