(57)【要約】本発明は、二次元構造の問合せに関する。各構造は、一つの根又は還元末端から延びる一以上の枝もしくは子を形成するリンケージでまとめて連結されるノードの配列からなる。各枝の遠位端又は葉から始まり、根まで延びる構造のすべての経路を表すために作成するシーケンスコードを用いて、各構造を表す。シーケンスコードは、どの構造にもひとつの固有な表現をもつようにする規則に従う。具体的に、発明のある側面は、炭水化物の分子構造などの二次元構造のデータベースに関係する。別の側面では、発明はこのようなデータベースを構築するためのプロセスに関係する。おそらく最も重要なさらに別の側面では、発明はこのようなデータベースを検索して、その中に所定の部分構造が含まれるすべての構造を探すためのプロセスに関係する。【特許請求の範囲】
【請求項１】
複数の物質に関する二次元構造についてのデータベースであって、
各前記二次元構造は、起点となる単位である根及び還元末端のいずれかから延びる一以上の枝と、前記根及び前記還元末端のいずれかから延びる一以上の子とのいずれかを形成する結合によって、まとめて連結されるノードの配列を備え、
各前記二次元構造は、各前記枝の長鎖端及び各前記枝の末端である葉のいずれかから始まり前記根まで戻る構造のすべての経路を表すために作成されたシーケンスコードを用いて表され、
前記シーケンスコードは、どの前記二次元構造にも単一の固有な表現がもたされるようにする固有規則に従う、
データベース。
【請求項２】
前記物質に関する前記二次元構造は、炭水化物の分子構造である、
請求項１に記載のデータベース。
【請求項３】
前記ノードは、単糖類である、
請求項２に記載のデータベース。
【請求項４】
前記シーケンスコードは、n進ツリーのコンピュータモデルに変換されることが可能である、
請求項１から３のいずれか１項に記載のデータベース。
【請求項５】
前記固有規則では、所定の構造の子が、結合の多さが低次から高次のものへ順番に並べられ、長さが最長のものから最短のものへ順番に並べられ、アルファベット順に「a」から「z」まで順番に並べられ、子の数が最も数の多いものから順番に並べられる、
請求項１から４のいずれか１項に記載のデータベース。
【請求項６】
前記構造の前記経路は、構造の葉から根まで導かれるように定義される、
請求項１から５のいずれか１項に記載のデータベース。
【請求項７】
炭水化物の分子を表すために使用される、
請求項１から６のいずれか１項に記載のデータベース。
【請求項８】
糖類を表すために使用される、
請求項１から７のいずれか１項に記載のデータベース。
【請求項９】
糖鎖の構造を表すために使用される、
請求項１から８のいずれか１項に記載のデータベース。
【請求項１０】
複数の物質の二次元構造についてのデータベースが構築される構築方法であって、
所望の部分構造を含むことが可能な1組の候補構造が選択される第１ステップと、
各前記候補構造が、起点となる単位である根まで各枝の長鎖端から導かれる一連の経路として表される第２ステップと、
各前記二次元構造のすべての前記経路が表されるようにされつつ、各前記二次元構造に単一の固有な表現がもたされるようにする固有規則に従うように作成されるシーケンスコードを用いて前記二次元構造が表される第３ステップと、
を備えた、
構築方法。
【請求項１１】
複数の物質に関する二次元構造についてのデータベースにおいて、所定の部分構造が含まれるすべての二次元構造が検索される検索方法であって、
クエリー部分構造が、起点となる単位である根まで枝の長鎖端から延ばされている各線形クエリー経路に構文解析される第１ステップと、
前記線形クエリー経路がデータベースに挿入される第２ステップと、
前記線形クエリー経路と同じ線形経路を含むデータベース内の候補構造のリストが、各前記二次元構造のすべての前記経路が表されるようにされつつ、各前記二次元構造に単一の固有な表現がもたされるようにする固有規則に従うように作成されるシーケンスコードを介して同定される第３ステップと、
を備えた、
検索方法。
【請求項１２】
前記第３ステップは、
第１クエリー経路と同じ線形経路が含まれる第１組の前記候補構造が同定され、前記第１組から、第２クエリー経路と同じ線形経路も含む第２組の前記候補構造が同定され、すべてのクエリー経路が含まれる前記候補構造の前記リストが同定されるまでこのように同定され続けられる第３１ステップと、
クエリー構造と同じトポロジーが内部に含まれているか判定するためのアルゴリズムであるツリー構造検索アルゴリズムを用いて各前記候補構造がテストされることにより前記候補構造の前記リストが検査され、前記トポロジーで配列される前記クエリー構造と同じ線形経路が含まれる前記候補構造の検査済みの前記リストが作成される第３２ステップと、
を有する、
請求項１１に記載の検索方法。
【請求項１３】
前記第３２ステップは、
リスト化された前記候補構造と前記クエリー構造とが構文解析されて、オブジェクトが作成される第３２１ステップと、
各前記候補構造の前記オブジェクトに対して順番にテストが開始される第３２２ステップと、
前記根から始めて、前記テストが行われている前記候補構造の各ノードがトラバースされる第３２３ステップと、
各前記ノードにおいて、前記ノードの種類が前記クエリー構造の前記根の種類と同じであるかどうかが判断される第３２４ステップと、
クエリーツリーの前記根のノードに子がないと判断される場合、前記クエリー構造が前記候補構造に存在しないと決定され、前記クエリーツリーの前記根の前記ノードが現在の前記ノードよりも多くの枝又は子をもつと判断される場合、前記クエリー構造が前記ノードに結合している前記候補構造に存在しないと決定され、前記クエリーツリーの前記根の前記ノードと前記根の前記ノードの子との結合が現在の前記ノードと前記現在の前記ノードの子との間に存在しないと判断される場合、前記クエリー構造が前記現在の前記ノードに結合して存在しないと決定される第３２５ステップと、
を含む、
請求項１２に記載の検索方法。
【請求項１４】
前記第３２４ステップでは、
前記結合について、低次の非還元末端の前記結合から高次の非還元末端の前記結合への順番で、未知の前記結合が他の前記結合よりも高次であるとして判断されるとともに、前記枝について、最大の前記枝が必ず最初の順番に検索される、
請求項１３に記載の検索方法。
【請求項１５】
前記第３２４ステップでは、
前記候補構造と前記クエリー構造との前記結合が一致しているかが判断され、前記候補構造と前記クエリー構造との前記結合が一致していると判断される場合、前記結合の前記候補構造と前記クエリー構造との両方の子について判断される、
請求項１４に記載の検索方法。
【請求項１６】
前記第３２４ステップでは、
前記子及び前記結合及び名前のいずれかが全く一致しないと判断される場合、２つの枝の前記結合が一致しないと判断される、
請求項１５に記載の検索方法。
【請求項１７】
前記第３２４ステップでは、
前記子及び前記結合及び名前のいずれかが全く一致しないと判断される場合、前記２つの枝の前記結合が一致すると判断され、すでに判断された前記結合に除去済みとマークされ、再び判断されない、
請求項１６に記載の検索方法。
【請求項１８】
前記第３２４ステップでは、
どの値とも整合するワイルドカードが前記クエリー経路内に用意されることによって未知の前記結合が処理され、枝が未知の前記結合に付く場合、前記枝がまず既知の前記枝のリストに存在するかが判断されてから、未知の前記枝のリストに存在するかが判断される、
請求項１７に記載の検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二次元構造についてのクエリー（ｑｕｅｒｙ）に関する。特に、本発明の１つの側面では、炭水化物の分子構造などの二次元構造についてのデータベースに関する。本発明の別の側面では、このようなデータベースを構築する方法に関する。本発明においておそらく最も重要なさらに別の側面では、データベースを検索して、その中に所定の部分構造を含むすべての構造を探す方法に関する。
【背景技術】
【０００２】
現在の技術水準において、枝分かれした糖鎖構造の解明を研究しているバイオテクノロジーの研究者たちは、次のような手順を踏むアプローチを採用している。糖鎖構造のデータベースに保持されている糖鎖の分岐構造を、線形シーケンス形式で表す。これによって、糖鎖内に存在しうる所望の構造をテキストベースで検索できる。このように非分岐の部分構造の検索も実行できる。代わりに、限られた枝構造のシーケンシングも行えるだろう（線形テキスト形式の制限内で）。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、ある所定の部分構造をもつ構造をすべて探せないという検索の限界がある。検索対象の部分構造から出る他の枝又は検索対象の部分構造を含む他の枝は、部分構造を連続的に検索するシーケンスを妨げる入れ子状の枝シーケンスがあるために、隠されてしまうことがある。そのため、ある部分構造はある生物資源内に存在しないと認識されることがある。こうして糖鎖の部分構造の評価が不正確になる可能性がある。
【０００４】
本発明の目的は、物質の部分構造の評価を正確に行うことができるデータベース、構築方法及び検索方法を提供することにある。
【課題を解決するための手段】
【０００５】
本発明の第１の側面に係るデータベースは、複数の物質に関する二次元構造についてのデータベースであって、各二次元構造は、ノードの配列を備える。ノードの配列は、一以上の枝と一以上の子とのいずれかを形成する結合によって、まとめて連結される。枝は、根及び還元末端のいずれかから延びる。根は、起点となる単位である。子は、根及び還元末端のいずれかから延びる。各二次元構造は、シーケンスコードを用いて表される。シーケンスコードは、各枝の長鎖端及び葉のいずれかから始まり根まで戻る構造のすべての経路を表すために作成される。葉は、各枝の末端である。シーケンスコードは、固有規則に従う。固有規則は、どの二次元構造にも単一の固有な表現がもたされるようにする。
【０００６】
このデータベースでは、二次元構造に複数の経路を有するものが含まれる。二次元構造がシーケンスコードを用いて表される。シーケンスコードが、各枝の長鎖端及び葉のいずれかから始まり根まで戻る構造のすべての経路を表すために作成される。例えば、２つの枝が同一なら、大きい方の枝が必ず作成するシーケンスの左にくるように枝が順番付けられて、シーケンスコードが作成される。シーケンスコードが、固有規則に従う。このため、構文解析アルゴリズムを用いて所望の部分構造を含む二次元構造を検索することができる。
【０００７】
したがって、所望の部分構造が入れ子状の枝シーケンスがある場合であっても、物質の部分構造の評価を正確に行うことができる。
本発明の第２の側面に係る構築方法は、複数の物質の二次元構造についてのデータベースが構築される構築方法であって、第１ステップと第２ステップと第３ステップとを備える。第１ステップでは、所望の部分構造を含むことが可能な1組の候補構造が選択される。第２ステップでは、各候補構造が、根まで各枝の長鎖端から導かれる一連の経路として表される。根は、起点となる単位である。第３ステップでは、シーケンスコードを用いて二次元構造が表される。シーケンスコードは、各二次元構造のすべての経路が表されるようにされつつ、固有規則に従うように作成される。固有規則は、各二次元構造に単一の固有な表現がもたされるようにする。
【０００８】
この構築方法では、二次元構造に複数の経路を有するものが含まれ得る。二次元構造がシーケンスコードを用いて表される。シーケンスコードが、各二次元構造のすべての経路を表すために作成される。例えば、２つの枝が同一なら、大きい方の枝が必ず作成するシーケンスの左にくるように枝が順番付けられて、シーケンスコードが作成される。シーケンスコードが、固有規則に従う。このため、構文解析アルゴリズムを用いて所望の部分構造を含む二次元構造を検索することができる。
【０００９】
したがって、所望の部分構造が入れ子状の枝シーケンスがある場合であっても、物質の部分構造の評価を正確に行うことができる。
本発明の第３の側面に係る検索方法は、複数の物質に関する二次元構造についてのデータベースにおいて、所定の部分構造が含まれるすべての二次元構造が検索される検索方法であって、第１ステップと第２ステップと第３ステップとを備える。第１ステップでは、クエリー部分構造が、各線形クエリー経路に構文解析される。線形クエリー経路は、根まで枝の長鎖端から延ばされている。根は、起点となる単位である。第２ステップでは、線形クエリー経路がデータベースに挿入される。第３ステップでは、線形クエリー経路と同じ線形経路を含むデータベース内の候補構造のリストが、シーケンスコードを介して同定される。シーケンスコードは、各二次元構造のすべての経路が表されるようにされつつ、固有規則に従うように作成される。固有規則は、各二次元構造に単一の固有な表現がもたされるようにする。
【００１０】
この検索方法では、二次元構造に複数の経路を有するものが含まれる。二次元構造がシーケンスコードを用いて表される。シーケンスコードが、各枝の長鎖端及び葉のいずれかから始まり根まで戻る構造のすべての経路を表すために作成される。例えば、２つの枝が同一なら、大きい方の枝が必ず作成するシーケンスの左にくるように枝が順番付けられて、シーケンスコードが作成される。シーケンスコードが、固有規則に従う。このため、構文解析アルゴリズムを用いて所望の部分構造を含む二次元構造を検索することができる。
【００１１】
したがって、所望の部分構造が入れ子状の枝シーケンスがある場合であっても、物質の部分構造の評価を正確に行うことができる。
【発明の効果】
【００１２】
本発明の第１の側面に係るデータベースでは、所望の部分構造が入れ子状の枝シーケンスがある場合であっても、物質の部分構造の評価を正確に行うことができる。
本発明の第２の側面に係る構築方法では、所望の部分構造が入れ子状の枝シーケンスがある場合であっても、物質の部分構造の評価を正確に行うことができる。
本発明の第３の側面に係る検索方法では、所望の部分構造が入れ子状の枝シーケンスがある場合であっても、物質の部分構造の評価を正確に行うことができる。
【発明を実施するための最良の形態】
【００１３】
［第１実施形態］
本発明の実施形態を、ＧｌｙｃｏＳｕｉｔｅＤＢデータベース内に保持される２つの構造について、構造のクエリーを実行するための技術を参照しながら説明する。
＜候補構造＞
解の空間を定義する２つの構造、つまり候補は次のとおりである。
【００１４】
候補１：
【００１５】
【化１】
2005527012.tif 000002
【００１６】
候補２：
【００１７】
【化２】
2005527012.tif 000003
【００１８】
候補３：
【００１９】
【化３】
2005527012.tif 000004
【００２０】
候補４：
【００２１】
【化４】
2005527012.tif 000005
【００２２】
＜各候補構造における経路＞
解の空間は、データベースに保持されているすべての候補構造における経路が計算及び比較されて作成される。各候補構造における経路は、二次元構造の葉（枝の末端）から根（起点となる単位）まで導かれる経路として定義される。このことから、候補１の構造における経路は、次のとおりである。
【００２３】
【化５】
2005527012.tif 000006
【００２４】
において、
経路１−候補１：
【００２５】
【化６】
2005527012.tif 000007
【００２６】
経路２−候補１：
【００２７】
【化７】
2005527012.tif 000008
【００２８】
経路３−候補１：
【００２９】
【化８】
2005527012.tif 000009
【００３０】
が見つけられる。
経路１は、（６の結合につながれている）最上位の「Ｍａｎ」葉ノードからツリー構造をさかのぼる経路をたどって見つけられる。
経路２は、（３の結合につながれている）中間の「Ｍａｎ」葉ノードからツリー構造をさかのぼる経路をたどって見つけられる。
【００３１】
経路３は、（６の結合につながれている）「Ｆｕｃ」葉ノードからツリー構造をさかのぼる経路をたどって見つけられる。
候補２の構造
【００３２】
【化９】
2005527012.tif 000010
【００３３】
における経路は次のとおりである。
経路１−候補２：
【００３４】
【化１０】
2005527012.tif 000011
【００３５】
経路２−候補２：
【００３６】
【化１１】
2005527012.tif 000012
【００３７】
候補３の構造には以下の経路が１つだけあり、
【００３８】
【化１２】
2005527012.tif 000013
【００３９】
候補４の構造には以下の経路が１つだけある。
【００４０】
【化１３】
2005527012.tif 000014
【００４１】
ＧｌｙｃｏＳｕｉｔｅＤＢデータベースに保持されているすべての候補構造における経路が、計算され、今後のクエリー実行のために保存される。
＜シーケンスコード＞
二次元構造はシーケンスコードを用いてデータベースに保存される。シーケンスコードを作成する規則は、どの構造にも一つの固有の表現がもたされるようにされる。シーケンスコードは、基本的にn進ツリーのコンピュータモデルに変換可能である。
【００４２】
シーケンスコードを作成する規則により、未知の枝の結合を表すのにどの内部結合が用いられるべきかが決定される。一般的に、単糖類の子に対して、単糖類の枝分かれした子は、結合の多さ、結合の長さ、アルファベット順（単糖類の種名に基づく）および子の数（の優先順位で）により並べられている。この順序付けにより、未知の構造が固有に表される。また、この順序付けの結果として生成されるシーケンスコードにより、余分な単糖類すなわち枝が（端に又は枝に沿って）存在する場合を除き、２つの枝が同じであれば大きい方の枝が必ずシーケンスコードの左に生成されるように、枝（「[]」を用いて表す）が順序付けられる。
【００４３】
例えば、以下の枝
枝１：
【００４４】
【化１４】
2005527012.tif 000015
【００４５】
枝２：
【００４６】
【化１５】
2005527012.tif 000016
【００４７】
枝３：
【００４８】
【化１６】
2005527012.tif 000017
【００４９】
枝４：
【００５０】
【化１７】
2005527012.tif 000018
【００５１】
枝５：
【００５２】
【化１８】
2005527012.tif 000019
【００５３】
枝６：
【００５４】
【化１９】
2005527012.tif 000020
【００５５】
について、
枝６
枝５
枝２
枝３
枝４
枝１
と順序付けられる。
【００５６】
また、この枝のシーケンスコードは、（すべての枝が残基「Ｘ」に結合し、長い構造のどこかに別の枝があると仮定すると）次のようになる。
Ｍａｎ（ａ１−３）［Ｍａｎ（ａ１−４）］［Ｇｌｃ（ａ１−？）Ｇａｌ（ａ１−？）［Ｇｌｃ（ａ１−？）］ＧｌｃＮＡｃ（ａ１−？）］［Ｇｌｃ（ａ１−？）Ｇａｌ（ａ１−？）ＧｌｃＮＡｃ（ａ１−？）］［Ｇａｌ（ａ１−？）ＧｌｃＮＡｃ（ａ１−？）］［ＧｌｃＮＡｃ（ａ１−？）］Ｘ
＜検索手順＞
クエリー構造は、データベースで見つけようとしている構造である。この例では、クエリー構造は次の構造である。
【００５７】
【化２０】
2005527012.tif 000021
【００５８】
この構造を見つけるときの第1工程では、次のクエリー構造における経路が計算される。この例では、次の経路が計算される。
経路１−クエリー：
【００５９】
【化２１】
2005527012.tif 000022
【００６０】
経路２−クエリー：
【００６１】
【化２２】
2005527012.tif 000023
【００６２】
第２工程では、解の空間が予め細分化され、所望の部分構造を含むかもしれない1組の候補構造が調べられる。具体的には、すべてのクエリー経路が経路内で（「部分経路」として）見つけられるような候補構造が調べられることにより行われる。すなわち、照合される経路のリストを作成するために、構文解析アルゴリズムを用いてクエリー構造が処理される。次に、候補構造の各葉について、根となるノードに遡って経路がたどられる。これらの各経路がデータベースに挿入される。
【００６３】
検索アルゴリズムは、最初、データベースの構造と経路との完全な1組で始められる。第1のクエリー経路（経路１−クエリー）はクエリーのシーケンスコードから求められる。1組の構造は、クエリー経路を含む少なくとも1つの経路をもつ構造のみが残るようにふるいにかけられる。
第１候補（候補１）を見てみると、経路１（経路１−クエリー）は候補１の経路２（経路２−候補１）で見つかることが分かる。
【００６４】
【化２３】
2005527012.tif 000024
【００６５】
経路１（経路１−クエリー）は同様に候補３で見つかる。
候補２と候補４とを見てみると、クエリー経路のいずれ（経路１−クエリー及び経路２−クエリー）も、候補２と候補４との経路の部分経路として見つからない。
そのため、経路1（経路１−クエリー）を含む構造が検索されると、候補２と候補４とが経路１（経路１−クエリー）を含まないため、解の空間は次のようにふるいにかけられる。
【００６６】
【表１】
2005527012.tif 000025
【００６７】
この組の構造は、第２のクエリー経路（経路２−クエリー）を含む少なくとも1つの経路をもつ組の構造のみが残るように、さらにふるいにかけられる。
経路２（経路２−クエリー）は、第1候補（候補１）の経路1（経路１−候補１）で見つかる。
【００６８】
【化２４】
2005527012.tif 000026
【００６９】
このように経路２（経路２−クエリー）を含む構造が検索されると、候補３が経路２（経路２−クエリー）を含まないため、解の空間は次のようにふるいにかけられる。
【００７０】
【表２】
2005527012.tif 000027
【００７１】
以上の工程が、どの構造も一致しなくなるまで、又はすべてのクエリー経路が一致する構造が見つかるまで続けられる。この例では、候補1が、ふるいにかけられた後に残る唯一の候補である。
候補構造において見つけられた部分経路の右側のツリーに、余分なノードがあることは問題ではない。また、候補構造において見つけられた部分経路の左側の木に、余分なノードがあるかどうかも問題ではない。
【００７２】
未知の結合は、クエリー経路内にワイルドカードを用意して処理される。ワイルドカードはどの値とも符号する。
次に、組の中の各構造（つまり、所望の部分構造を含むかもしれない候補構造の組）を検査して、どれが所望の部分構造を含むか探されることが必要である。このためには、正確に一致しない結果（候補構造）をすべて除去するために、つまり誤って検出された結果（候補構造）をすべて除去するために、解の空間がふるいにかけられる必要がある。
【００７３】
＜構造同士の比較＞
クエリー構造において（同じ単糖類に結合する）２つの未知の結合の枝が存在する場合（ある枝が別の枝の部分集合であるか、又は別の枝と同じ場合）、誤って検出された結果（候補構造）が存在すると判断される。候補構造は、その枝の大きい方と同じ組成をもつ唯一の枝のみを含むようになる。例えば、
候補構造５：
【００７４】
【化２５】
2005527012.tif 000028
【００７５】
は、次の単一の経路を有する。
【００７６】
【化２６】
2005527012.tif 000029
【００７７】
クエリー構造２：
【００７８】
【化２７】
2005527012.tif 000030
【００７９】
は、次の２つの経路をもつ。
【００８０】
【化２８】
2005527012.tif 000031
【００８１】
【化２９】
2005527012.tif 000032
【００８２】
クエリー構造３：
【００８３】
【化３０】
2005527012.tif 000033
【００８４】
は、次の２つの経路をもつ。
【００８５】
【化３１】
2005527012.tif 000034
【００８６】
【化３２】
2005527012.tif 000035
【００８７】
クエリー構造２とクエリー構造３とはどちらも（経路だけで見れば）候補構造５に一致する。
しかし、クエリー構造２に同一の経路が２つあるのに対し、候補構造５には１つの経路しかなく、クエリー構造２が候補構造５に含まれるとするのは、明らかに有効な結果とは言えない。
【００８８】
また、クエリー構造３も２つの経路をもつが、候補構造５がクエリー構造３よりも小さいため、候補構造５はクエリー構造３に対して有効な（クエリー構造３を含んでいる）構造とはならない。
候補構造で見つかる経路が共通の点つまり候補構造におけるクエリー構造の結合点で合わない場合も、誤って検出された結果（候補構造）が存在すると判断される。例えば、
候補構造６：
【００８９】
【化３３】
2005527012.tif 000036
【００９０】
は、次の３つの経路を有する。
経路１−候補６：
【００９１】
【化３４】
2005527012.tif 000037
【００９２】
経路２−候補６：
【００９３】
【化３５】
2005527012.tif 000038
【００９４】
経路３−候補６：
【００９５】
【化３６】
2005527012.tif 000039
【００９６】
クエリー構造４：
【００９７】
【化３７】
2005527012.tif 000040
【００９８】
は、次の３つの経路を有する。
経路１−クエリー４
【００９９】
【化３８】
2005527012.tif 000041
【０１００】
経路２−クエリー４
【０１０１】
【化３９】
2005527012.tif 000042
【０１０２】
経路３−クエリー４
【０１０３】
【化４０】
2005527012.tif 000043
【０１０４】
候補６を見てみると、経路１（経路１−クエリー４）が経路２（経路２−候補６）で見つかり、
【０１０５】
【化４１】
2005527012.tif 000044
【０１０６】
経路２（経路２−クエリー４）が経路１（経路１−候補６）で見つかり、
【０１０７】
【化４２】
2005527012.tif 000045
【０１０８】
経路３（経路３−クエリー４）が経路３（経路３−候補６）で見つかる。
【０１０９】
【化４３】
2005527012.tif 000046
【０１１０】
クエリー構造のすべての経路（経路１−クエリー４、経路２−クエリー４及び経路３−クエリー４）が一致するが、クエリー構造（クエリー構造４）と候補構造（候補構造６）とを見てみると、クエリー構造（クエリー構造４）は候補構造（候補構造６）の中に見つからないことが分かる。
これらの問題を解決するために、クエリー構造と候補構造とで構造同士の比較が行われなければならない。候補構造がトラバースされることによりクエリー構造が作成され得るならば、クエリー構造が候補構造の中に存在すると判断される。このため、有効な結果を得ることが可能である。
【０１１１】
構造同士の比較では、候補構造における各単糖類がアクセスされて、その単糖類に結合しているクエリー構造があるかどうかが調べられる。単糖類がアクセスされるたびに、単糖類の種類と子の結合の数及び種類とが調べられる。
候補構造がクエリー構造を含んでいるかを検査するために、候補構造とクエリー構造との両方が、構文解析されて、糖類と単糖類をモデル化するためのオブジェクトを作成する際に用いられる。糖類は内部でツリー構造として表される。ツリー構造検索アルゴリズムを用いて、クエリー構造が候補構造内に含まれているかが検査される。
【０１１２】
例えば、次のクエリー構造
【０１１３】
【化４４】
2005527012.tif 000047
【０１１４】
が次の候補構造
【０１１５】
【化４５】
2005527012.tif 000048
【０１１６】
の中に含まれているかを検査したい場合、次のようなアルゴリズムが用いられる。
各ノード（単糖類）を候補構造でトラバースする。すべてのノードで、単糖類の種類（名前）がクエリー構造の根となる単糖類と同じであれば、クエリーツリーが現在のノードに結合するこのツリーで見つかるかどうかが調べられるような検索が開始される。
クエリーツリーの根となるノードが子をもっていなければ、クエリー構造は候補構造の中に存在すると判断される。クエリーツリーの根となるノードが現在のノードよりも多くの子をもっていれば、クエリー構造は現在のノードに結合して存在しないと判断される。そうでない場合、クエリーツリーの根となるノードとその子との結合が、現在のノードとその子との結合に存在するかが調べられる。結合のいずれも存在しない場合、クエリー構造は現在のノードに結合して存在しないと判断される。結合を点検する順番は、最も低位の非還元末端の結合から最も高位の非還元末端の結合への順番とする。再帰的除去の手法を用いて、クエリー構造が現在の単糖類に結合して存在するかが検査される。
【０１１７】
例えば、候補構造がトラバースされる順番を図1に示す。候補構造1が、第1単糖類１０、第2単糖類１１、第3単糖類１２の順番でアクセスされ検索される。クエリー構造がこのノード（単糖類）でのみ見つかる可能性があるので、他のノード（単糖類）は点検されない。ただし、検索が続けられるとすれば、検索される順番は、１３、１４、１５となるであろう。
【０１１８】
＜再帰的除去の手法＞
再帰的除去の手法が用いられて、クエリー構造が現在の単糖類に結合しているかが判断される。この手順は次のように進める。
クエリー構造の子と候補構造の子との結合が比較される場合、その結合は低次のものから高次のものへと順番に比較される。候補構造とクエリー構造との結合が一致したら、その結合のクエリー構造と候補構造との両方の子が、別の枝を除去する手順に採用される。
【０１１９】
別の枝を除去する手順では、単糖類の名前が合っているか調べられ、もう一度子が調べられる（上記と同様）。すなわち、すべての子にもう一度再帰的除去の手法が用いられる。
子、結合又は名前が全く一致しなかったら、この２つの枝は一致しないと考えられる。そうでなければ、枝は一致すると考えられ、手順の始めに用いられた結合は除去済みとマークされ、再び判断されない。
【０１２０】
例えば、次の構造
【０１２１】
【化４６】
2005527012.tif 000049
【０１２２】
が、次の候補構造
【０１２３】
【化４７】
2005527012.tif 000050
【０１２４】
の強調表示した単糖類に結合して存在するかどうかを点検したい場合を考える。
結合は、昇順（未知の結合は他の結合よりも上位に並べ替える）で枝が存在するかが調べられる。まず、次の枝
【０１２５】
【化４８】
2005527012.tif 000051
【０１２６】
が、候補構造に存在するかが調べられる。子の結合（ａ１−３）が強調表示した単糖類に存在し、結合（ａ１−３）がつながれた単糖類の名前が同じで、この単糖類の子も一致するので（両方とも子をもたない）、この枝は候補構造で見つかることになる。この枝はクエリー構造と候補構造とから除去される。
ここで、クエリー構造が
【０１２７】
【化４９】
2005527012.tif 000052
【０１２８】
であり、候補構造が、
【０１２９】
【化５０】
2005527012.tif 000053
【０１３０】
である場合を考える。この場合、次の枝
【０１３１】
【化５１】
2005527012.tif 000054
【０１３２】
が候補構造内に存在しているかが点検される必要がある。前述の枝と同様に、この枝は候補構造で見つかる。この枝が除去され、クエリー構造には1つのＭａｎ（単糖類）が残る。クエリー構造の残りの単糖類の子が全部見つかっているため、残りの単糖類のクエリー構造の部分ツリーを候補構造で見つけることが可能である。また、残りの単糖類がクエリーツリーの根となる単糖類であるため、クエリー構造全体を候補構造で見つけることが可能である。
【０１３３】
＜未知の結合の処理＞
未知の結合は、非還元末端の値を「＞９」且つ「＜１３」としてモデル化する。
クエリーの根から子への結合が未知の値を含んでいる場合、枝を除去する手順で、現在のノードから子への結合を１から１３まで点検する。未知の結合の枝を検索する場合、この順番が重要である。枝に未知の結合がつながれている場合、その枝は、最初に既知の枝のリストに存在するかが点検され、次に未知の枝のリストに存在するかが点検される。クエリー構造が有効なシーケンスをもって、枝が正しい順番で点検できるようにすることが極めて重要である。枝の順序付けでは、最も大きい枝が必ず最初に検索されるようにされる。
【０１３４】
例えば、次の候補構造
【０１３５】
【化５２】
2005527012.tif 000055
【０１３６】
は次のシーケンスコードをもつ。
Ａｒａ（ａ１−３）［Ｆｕｃ（ａ１−？）］ＧｌｃＮＡｃ（ａ１−２）Ｇｌｃ（ａ１−？）［Ａｒａ（ａ１−３）ＧｌｃＮＡｃ（ａ１−２）Ｇｌｃ（ａ１−？）］ＧｌｃＮＡｃ
ここで、クエリー構造
【０１３７】
【化５３】
2005527012.tif 000056
【０１３８】
が候補構造と同じ構造をもつ場合を考える。
（シーケンスコードが同一であるかを点検せずに）この２つの構造が同一であるかどうかを判断したい。まず、クエリー構造の一番下位の枝が候補構造に含まれているかどうかが調べられる必要がある。なぜなら、（内部的に表して）上位の枝よりも下位の枝に下位の結合が与えられている。上位の枝がまず調べられた場合、（候補構造のシーケンスコードによるが）候補構造における下位の枝が（以後の処理において除去される）上位の枝と一致する可能性があり、下位の枝は他のどの枝とも一致しないため、この２つの構造は一致しないと判断されてしまうからである。
【０１３９】
＜未知の結合を用いた枝除去の例＞
クエリー構造：
【０１４０】
【化５４】
2005527012.tif 000057
【０１４１】
候補構造：
【０１４２】
【化５５】
2005527012.tif 000058
【０１４３】
である場合を考える。
前述の例と同様に、根となる単糖類
【０１４４】
【化５６】
2005527012.tif 000059
【０１４５】
と同じ名前をもつ単糖類が見つかるまで、ツリーがトラバースされる。
ここで、結合の昇順に、クエリー構造の枝が調べられる。まず、次の枝
【０１４６】
【化５７】
2005527012.tif 000060
【０１４７】
が、候補構造に存在するかが調べられる。この枝は候補構造に存在するので、この枝が候補構造とクエリー構造とから除去される。その結果、次の構造
【０１４８】
【化５８】
2005527012.tif 000061
【０１４９】
と
【０１５０】
【化５９】
2005527012.tif 000062
【０１５１】
とが残る。
ここで、次の枝
【０１５２】
【化６０】
2005527012.tif 000063
【０１５３】
が、候補構造に存在するかが調べられる。結合が、１から１３まで昇順に、一致するか調べられる。結合（ａ１−６）で枝が一致するので、この枝が候補構造にあると分かる。候補構造とクエリー構造との両方の構造からこの枝が除去される。そして、前述の例と同様に、クエリー構造全体が候補構造に存在することが分かるようになる。
以上のようなアプローチは、糖鎖構造の検索に応用すると、生物的な重要性をもつ構造であり著しく枝分かれし固有のエピトープを含む糖鎖構造を、迅速且つ正確に同定できることは明らかである。
【０１５４】
生物学の研究者の助けを借りて、その後の薬物ターゲティングのために、疾病状態で存在する構造を同定評価することができる。あるいは、このアプローチは、可能性のある組換えシステムの同定を可能にしながら、ある構造が一定の種によって生成されるかどうかを突き止めることができる。
一般的に説明した発明の精神又は範囲を逸脱することなく、具体的な実施形態で示す本発明に多数の変形及び変更が行えることは当業者には理解されよう。そのため、この実施形態はあらゆる面において例示的なものと考え、制限的なものと考えてはならない。
【産業上の利用可能性】
【０１５５】
本発明にかかるデータベース、構築方法及び検索方法は、物質の部分構造の評価を正確に行うことができるという効果を有し、データベース、構築方法及び検索方法等として有用である。
【図面の簡単な説明】
【０１５６】
【図１】候補構造がトラバースされる順番を示す図。
【符号の説明】
【０１５７】
１  候補構造
１０，１１，１２，１３，１４，１５  単糖類
【図１】
2005527012.tif 000064
【国際調査報告】
2005527012.tif 000065
2005527012.tif 000066