(57)【要約】関連するオブジェクトのセットを多次元空間にマップする方法、システム、およびプログラム。提供されたオブジェクト間の関係のセットから、近傍のオブジェクト間の局所的な関係を保持しながら（図４、エレメント４１４）、最小限の分離を維持するように（図４、エレメント４１２）、上限と下限が抽出される。
2006504159.tif 000002
【特許請求の範囲】
【請求項１】
２つあるいはそれ以上のオブジェクトが関連付けられたペアごとの関係によって関連付けられているオブジェクトのセットに対するマッピング座標を生成するためのコンピュータ化された方法であって、
（１）１つまたは複数の関連付けられた関係に関する境界のセットを指定するステップと、
（２）マップ上に、オブジェクトの初期座標を割り当てるステップと、
（３）オブジェクトのペアを選択するステップと、
（４）マップ上の前記選択されたオブジェクトの間の距離ｄを計算するステップと、
（５）マップ上の前記選択されたオブジェクト間の前記距離ｄと、それらの関連付けられた関係ｒの境界とを比較するステップと、
（６）マップ上の前記選択されたオブジェクト間の前記距離ｄが前記対応する関係ｒの前記境界外にある場合に、マップ上の前記選択されたオブジェクトの距離ｄが前記対応する関係ｒの前記境界内でより近付いて収まるように、マップ上の前記選択されたオブジェクトの座標を調整するステップと、
（７）追加のオブジェクトのペアについて（３）から（６）のステップを繰り返すステップと、
（８）１つまたは複数のオブジェクトの座標をマップ上に出力するステップと
を備えることを特徴とする方法。
【請求項２】
ステップ（１）は、
（ａ）近傍の半径ｒｃを特定するステップと、
（ｂ）オブジェクトのペアを選択するステップと、
（ｃ）前記選択されたオブジェクトの関係ｒを前記近傍の半径ｒｃと比較するステップと、
（ｄ）前記選択されたオブジェクトの前記関係ｒが前記近傍の半径ｒｃと同じかそれより小さい場合に、前記近傍の半径ｒｃに等しい前記選択されたオブジェクトの前記関係ｒの下限と上限を割り当てるステップと、
（ｅ）前記選択されたオブジェクトの前記関係ｒが前記近傍半径ｒｃより大きい場合に、前記近傍の半径ｒｃに等しい前記選択されたオブジェクトの前記関係ｒの下限および前記選択されたオブジェクトの前記関係ｒの無限大に等しい上限を割り当てるステップと、
追加のオブジェクトのペアについて（ａ）から（ｅ）のステップを繰り返すステップと、
を備えることを特徴とする請求項１に記載の方法。
【請求項３】
２つのオブジェクトのペアごとの関係が前記オブジェクト間の類似性／相違性を表すことを特徴とする請求項１に記載の方法。
【請求項４】
２つのオブジェクトのペアごとの関係が前記オブジェクト間の距離を表すことを特徴とする請求項１に記載の方法。
【請求項５】
ステップ（６）は、マップ上の前記選択されたオブジェクト間の前記距離ｄが前記対応する関係ｒの前記境界外にある場合に、マップ上の前記選択されたオブジェクトの距離ｄが前記対応する関係ｒの前記境界内でより近付いて収まるように、マップ上の前記選択されたオブジェクトの座標を訂正因子によって調整するステップを備えることを特徴とする請求項１に記載の方法。
【請求項６】
複数の訂正因子について、ステップ（３）から（７）を反復するステップをさらに備えることを特徴とする請求項５に記載の方法。
【請求項７】
ステップ（３）から（７）を反復するたびに訂正因子の値を減じるステップをさらに備えることを特徴とする請求項６に記載の方法。
【請求項８】
複数の近傍半径ｒｃについて、ステップ（１）から（７）を反復することを特徴とする請求項２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にデータ分析に関し、より詳細には多次元空間におけるオブジェクトの関係（object relationships）を表す方法、システム、およびコンピュータ・プログラム製品に関する。
【背景技術】
【０００２】
実験的な観測結果（experimental observations）のセット（集合）を十分に説明できる独立変数の最小数を抽出することは、科学において極めて重要な問題である。多くの物理プロセスでは相関性の高い入力が生成され、平滑化された低次元の多様体（smooth low-dimensional manifold）上またはその近くに存在する観測結果が導かれる。
【０００３】
【非特許文献１】Borg, I. & Groenen, P. J. F.,"Modern Multidimensional Scaling: Theory and Applications," (Springer, New York、1997)
【非特許文献２】Tenenbaum, J. B., de Silva, V. & Langford, J. C., "A Global Geometric Framework for Nonlinear Dimensionality Reduction," Science 290, 2319-2323, (2000)
【非特許文献３】Rowels and Saul、 "Nonlinear Dimensionality Reduction by Locally Linear Embedding," Science 290,2323-2326, (2000)
【非特許文献４】Agrafiotis, D. K., Lobanov, V. S. & Salemme, F. R., "Combinatorial Informatics in the Post-Genomics Era," Nature Reviews Drug Discovery 1,337-346, (2002)
【非特許文献５】Robbins, H. & Monroe, S., "A Stochastic Approximation Method," Annals of Mathematical Statistics 22,400-407 (1951)
【非特許文献６】Rumelhart, et al., "Learning Representations by Back-Propagating Errors," Nature 323, 533-536, (1986)
【非特許文献７】Tenenbaum, J. B., "The ISOMAP Algorithm and Topological Stability," Science 295, 7a (2002)
【非特許文献８】Spellmeyer, et al., "Conformational Analysis Using Distance Geometry Methods," Journal of Molecular Graphics and Modelling 15, 18-36 (1997)
【非特許文献９】Haver, T. F. & Kurt, W., "An Evaluation of the Combined Use of Nuclear Magnetic Resonance and Distance Geometry for the Determination of Protein Conformations in Solution," Journal of Molecular Biology 182, 281-294, (1985)
【非特許文献１０】Crippen, G. M. & Haver T. F., "Distance Geometry and Molecular Conformation," Research Studies Press, Somerset, UK, (1988)
【発明の開示】
【発明が解決しようとする課題】
【０００４】
このような多様体（manifold）の次元ならびに非線形の幾何図形的配列（dimensionality and nonlinear geometry）は、しばしばデータ・ポイント間の類似性として具体化されるので、一般的なアプローチは、システムについての内在する構造（intrinsic structure）が、結果として得られるマップに反映されることを期待して、こうした類似性を最も維持しやすい低次元空間にデータを埋め込むことである。参照により全体として本明細書に組み込まれている非特許文献１を参照されたい。しかしながら、ユークリッド距離のようなこれまでの類似性の尺度（measures）では、非線形多様体上の各ポイントの近接性（proximity）が過小評価され、誤った埋め込み（embeddings）をもたらす傾向がある。
【０００５】
この問題を改善するために、参照により全体として本明細書に組み込まれている非特許文献２で説明されている既知のＩＳＯＭＡＰという方法では、従来のユークリッド距離を、推定された測地距離（estimated geodesic distance）の推定値に置き換え、伝統的な多次元尺度構成法（ＭＤＳ：multidimensional scaling）を使用して、最適な低次元構（low- dimensional configuration）を検出する。無限のトレーニング・サンプルの極限において、データがユークリッド多様体の特定のクラスに分類される場合は、ＩＳＯＭＡＰがデータの真の次元と幾何図形的配列構造（geometric structure）を復元することがわかっているが、埋め込み手順についての少なくとも２次の複雑性（quadratic complexity）が、膨大なデータ・セットに関してその使用を排除するために、その検査（proof）は、あまり実用的ではない。
【０００６】
同様のスケーリングの問題は、各データ・ポイント間に局所的線形関係を構築することにより、大域的に順序付けられたマップを作成する関連のアプローチである局所的線形埋め込み（ＬＬＥ：locally linear embedding）にも影響を与える。ＬＬＥについては、参照により全体として本明細書に組み込まれている非特許文献３の中で説明されている。
【０００７】
必要となるのは、データ・セットを完全に説明できる独立変数の最小数を抽出するための改良された方法、システム、およびコンピュータ・プログラム製品である。より詳細には、必要なのは、関係のセットによって互いに関連付けられたオブジェクトのセットを、こうした関係についての内在する構造を維持する方法で、多次元空間にマッピングするための改良された方法、システム、およびコンピュータ・プログラム製品である。
【課題を解決するための手段】
【０００８】
本発明は、関連のある観測結果（related observations）のセットをｎ次元空間に埋め込むための、そのデータにつての内在する次元構造とメトリック構造を維持する自己組織型方法（self-organizing method）を対象とする。本発明は、ここに確率論的近接性埋め込み（ＳＰＥ：stochastic proximity embedding）と呼ぶ。埋め込みは、離れたオブジェクト間の最小限の分離を維持しながら局所的な幾何図形的配列（local geometry）を維持しようとする反復型の（たとえばペアごとの）精密化戦略（refinement strategy）を使用して実行される。実際に、本発明はリモート・オブジェクト間の近接性を真の測地的距離の下限と見なし、大域的な構造（global structure）を割り当てる手段として使用する。
【０００９】
本方法には以下のステップが含まれる。  
（１）１つまたは複数の関連付けられた関係に関する境界（bound）のセットを指定するステップ  
（２）ｎ次元マップ上に、オブジェクトの初期座標を割り当てるステップ  
（３）オブジェクトのペアを選択するステップ  
（４）ｎ次元マップ上の前記選択されたオブジェクト間の距離ｄを計算するステップ  
（５）ｎ次元マップ上の前記選択されたオブジェクト間の前記距離ｄと、それらの関連付けられた関係ｒの境界を比較するステップ  
（６）ｎ次元マップ上の前記選択されたオブジェクト間の前記距離ｄが前記対応する関係ｒの前記境界外にある場合に、ｎ次元マップ上の前記選択されたオブジェクトの前記距離ｄが前記対応する関係ｒの前記境界内でより近付いて収まるように、ｎ次元マップ上の前記選択されたオブジェクトの座標を調整するステップ  
（７）追加のオブジェクトのペアについて（３）から（６）のステップを繰り返すステップ  
（８）１つまたは複数のオブジェクトの座標をマップ上に出力するステップ
本発明の付加的な機能と利点について、以下に記述する。さらに詳しい機能と利点は、以下の記述に基づけば当業者には明らかであり、本発明を実施することによって理解できる。本発明の利点は、ここに記述する実施の形態、特許請求の範囲に、および添付の図面で特に指摘する構造により、実現され、達成される。
【００１０】
以上の解決するための手段と以下の実施の形態は、いずれも例示的なもので、説明のみを目的としたものであり、特許請求の範囲に示す本発明を詳細に説明するものであることを理解されたい。
【００１１】
本発明について添付の図面に関連付けながら詳細に説明するが、説明の中で参照番号が似かよっているものは同類の要素すなわち類似の機能を果たす要素を示している。また、参照番号の上位桁は、該当する要素を初めて図示する図面の番号を示している。
【発明を実施するための最良の形態】
【００１２】
はじめに
現代科学は、人間の遺伝子の何千にも及ぶ発現プロファイル（expression profiles）や、マルチメディア文書、消費者向け製品や政治候補者に関する主観的判断、貿易指標（trade indices）、世界の気象パターンなど、大量のデータに直面している。このようなデータは多くの場合に高度に構造化されているが、その構造は、各関係や高次元の抽象化概念の複雑な集合（セット）に隠されている。
【００１３】
本発明は、関連のある観測結果のセット（set of related observations）を、データについての内在する次元構造とメトリック構造を維持する低次元空間に埋め込むための自己組織化方法（self-organizing method）を対象とする。本発明は、ここでは確率論的近接性埋め込み（ＳＰＥ：stochastic proximity embedding）と呼ぶ。埋め込みは、離れたオブジェクト間の最小限の分離を維持しながら局所的幾何図形的配列（local geometry）を維持しようとする反復型の（たとえばペアごとの）精密化戦略（refinement strategy）を使用して実行される。要するに、本方法は、リモート・オブジェクト間の近接性を、真の測地的距離の下限と見なし、それらを大域的な構造（global structure）を与える手段として使用する。
【００１４】
これまでのアプローチとは異なり、本発明は、最隣接（nearest neighbour）または最短経路（shortest-path）による負荷のかかる計算を使用せずに、多様体の内在的な幾何図形的配列（distance geometry）を明らかにし、低次元の埋め込みにおけるデータ・ポイントの真の測地的距離を、このような距離をデータ・サンプルから推定することなく、再現できる。本発明は、ポイント数に線形に比例して拡張性があるので、これまでの埋め込み手順では困難であった膨大なデータ・セットに適用することができる。
【００１５】
ＳＰＥアルゴリズムは、測地的距離が入力の近接性より常に大きいかこれに等しいという事実を利用している。前述のＩＳＯＭＡＰと同様に、本発明は、ポイントが比較的近い場合は、入力の近接性が真の測地的距離についての合理的な近似を提供することを想定している。このことは、多様体の局所的曲率（local curvature）がそれほど大きくない場合は、たいていの場合にあてはまる。しかしＩＳＯＭＡＰとは異なり、本発明は、リモート・ポイント間の測地的距離についての近似値の計算を回避する。その結果、低次元マップ上のそれらの距離が、それぞれの近接性を下回らないことをだけを必要条件とする。
【００１６】
確率論的近接性埋め込み（ＳＰＥ：Stochastic Proximity Embedding）
この埋め込みは、以下のストレス関数（stress function）のようなエラー関数を最小化することによって実行される。
【００１７】
【数１】
2006504159.tif 000003
【００１８】
ただし、
ｒｉｊはｉ番目のポイントとｊ番目のポイント間の入力の近接性である。  
ｄｉｊは、低次元空間のユークリッド距離であり、ｒｃは近傍の半径（neighbourhood radius）である。  
ｆ（ｄｉｊ，ｒｉｊ）は以下に定義されるようなペアごとのストレス関数である。  
ｆ（ｄｉｊ，ｒｉｊ）＝（ｄｉｊ−ｒｉｊ）２  （ｒｉｊ≦ｒｃ  または  ｒｉｊ＞ｒｃ  かつ  ｄｉｊ＜ｒｉｊの場合）、および  
ｆ（ｄｉｊ，ｒｉｊ）＝０  （ｒｉｊ＞ｒｃ  かつ  ｄｉｊ≧ｒｉｊの場合）
ストレス関数は各項ｆ（ｄｉｊ，ｒｉｊ）を、急速に０の状態に至らせる自己組織化アルゴリズムを使用して最小化される。本方法では、まず初期設定を行い、ランダムに２つのポイントを繰り返し選択し、ペアごとのストレスｆ（ｄｉｊ，ｒｉｊ）を減少させるようにそれらの座標を調整することにより、反復して精密化（refine）する。
【００１９】
補正は、不一致の程度（disparity）
【００２０】
【数２】
2006504159.tif 000004
【００２１】
に比例する。ただし、λは、振動の挙動を避けるために、精密化（refinement）の過程で減少する学習率パラメータである。ｒｉｊ＞ｒｃ  かつ  ｄｉｊ≧ｒｉｊの場合、すなわち各ポイントが非局所的でマップ上のそれらの距離がすでにそれらの近接性ｒｉｊより大きい場合、それらの座標は変化しない。
【００２２】
好ましい実施形態においては、多様体についての内在する次元は、より低次元の空間にデータを埋め込み、ストレス（stress）が効果的に消滅するポイントを特定することによって、明らかになる。
【００２３】
スイス・ロールに適用した場合、ＳＰＥによって２という真の次元が確実に明らかになった。図１Ａから１Ｄを参照しながら以下に説明するように、２次元マップ上の各ポイント間の距離は、分析的に導かれた実際の測地的距離に、０．９９９９の相関係数で適合しており、この相関係数は事実上完全な埋め込みを示している。
【００２４】
図１Ａから図１Ｄは、スイス・ロールのデータ・セットの確率論的近接性埋め込み（stochastic proximity embedding）を表している。図１Ａは、３次元空間におけるオリジナルのデータ・セットを示している。図１Ｂは、ＳＰＥによって得られた２次元の埋め込みを示している。図１Ｃは、ＳＰＥ（３０を超える独立実行の平均ならびに標準偏差、標準偏差は非常に小さいのでほとんど目に見えない）とＭＤＳによって得られた最終的なストレスを、埋め込みの次元の関数として示す。図１Ｄは、ＳＰＥによって得られた２次元の埋め込みの最終的なストレス（３０を超える独立実行の平均ならびに標準偏差）を、１０３、１０４、１０５、１０６のポイントを収容する４つのデータ・セットのシミュレーション長の関数として示す。以下に説明するとおり、図１Ｃと図３Ｄは、ＳＰＥの線形のスケーリングを示している。つまり、サンプルのサイズが１０倍増加した場合、同等のストレスを達成するために必要な精密化のステップ数もおよそ１０倍となっている。
【００２５】
同様に、本方法では、平方根平均二乗変位（ＲＭＳＤ：root mean square deviation）を使用して比較したメチルプロピルエーテル（methylpropylether）の配座（conformations:立体構造）全体についての内在する２次元構造を検出することができた。結果として得られたマップ上の座標軸は、分子の真の配座の自由度との相関が極めて強く、立体構造の障害（steric hindrance）によって手が届かない（inaccessible ）配座空間の領域を明らかにしている。
【００２６】
たとえば図２Ａおよび図２Ｂは、距離幾何図形的配列（distance geometry）アルゴリズムにより生成され、ＲＭＳＤによって比較されたメチルプロピルエーテルＣ１Ｃ２Ｃ３Ｏ４Ｃ５の１０００の配座の確率論的近接性埋め込みを示す図である。図２Ａは、ＳＰＥによって得られた２次元の埋め込みを示している。代表的な配座は、マップのさまざまな部分の強調表示されたポイントの横に、かっこ内に対応するねじれ角（φＣ２Ｃ３Ｏ４Ｃ５とφＣ１Ｃ２Ｃ３Ｏ４）を加えて、表示している。水平方向と垂直方向は、それぞれＣ３〜Ｏ４とＣ２〜Ｃ３の連結を軸とした回転を示している。空いている左上と右下のコーナーは、Ｃ１とＣ５の２つの末端炭素原子間の立体構造の障害のために、手が届かない（inaccessible）配座を表している。図２Ｂは、埋め込み次元関数として、ＳＰＥ（３０を超える独立実行の平均および標準偏差）とＭＤＳによって得られた最終ストレスを示している。
【００２７】
ＳＰＥは、明確な多様体幾何図形的配列（manifold geometry）を有さない、さらに複雑なデータ・セットについての有意の低次元表現を作り出すこともできる。図３Ａから図３Ｃに示した組合せライブラリの埋め込みは、本方法が、密接に関連する複合物についての局所的な近傍（neighbourhoods）を保持しながら、化学的に有意な大域的な構造を維持できることを示す。
【００２８】
たとえば、図３Ａから図３Ｃは、ジアミン（diamine）の組合せライブラリの確率論的近接性埋め込みを示している。図３Ａは、ＳＰＥによって得られた２次元の埋め込みを示している。図３Ｂは、（３０を超える独立実行の平均および標準偏差）ＳＰＥとＭＤＳによって得られた最終ストレスを、埋め込み次元の関数として示している。図３Ｃは、ＳＰＥ（３０を超える独立実行の平均および標準偏差）によって得られた２次元埋め込みの最終ストレスを、１０３、１０４、１０５、１０６の複合物を収容する４つのデータ・セットのシミュレーション長の関数として示している。
【００２９】
このデータ・セットについての内在する次元が実質的には２より上としても、２次元のマップは、大域的な順序と連続性を、分子量（molecular weight）の中心的なロール（role）で表されるとおりに示し、鎖長（chain length）、リング構造、ハロゲン含有量のような化学的に顕著な特徴に対応する変動パターン（variation patternｓ）が存在することを示している。参照により全体として本明細書に組み込まれている非特許文献４を参照されたい。
【００３０】
ＳＰＥは、必ずしもＩＳＯＭＡＰまたはＬＬＥの大域的な最適性を保証しないが、実際は非常によく動作する。たとえば、図１Ｃと２Ｂの分散で示されるように、データが、内在する次元空間（および、より低い次元の低ストレス構成）に埋め込まれた場合、本方法では開始時の構成や初期条件にかかわらず、大域的な最小値（global minimum）に確実に収束する。さらに重要なのは、同一の確率分布から抽出されたサイズの増大するデータ・セットに適用した場合（したがって、同等のストレスを持つことが期待される場合）、特定のストレスに達するのに必要なサンプリング・ステップの数が直線的に増大することである（図１Ｄ、図３Ｃ）。近接性は必要に応じて計算でき、明示的に格納する必要がないため、本方法で必要とするメモリもまた直線的に増大する。
【００３１】
これらの特性は、この精密化スキーム（refinement scheme）の確率論的性質（stochastic nature）と、距離マトリックス（distance matrix）の広大な冗長性によるものである。実際に、ＳＰＥは、参照により全体として本明細書に組み込まれている非特許文献５で紹介され、またＲａｍｅｌｈａｒｔの逆プロパゲーション・アルゴリズム（Rumeihart's back-propagation algorithm）によって普及された確率論的近似アプローチを思い出させる。これについては、参照により全体として本明細書に組み込まれている非特許文献６を参照されたい。
【００３２】
ペアごとの精密化の方向は、瞬間的な勾配（instantaneous gradient）、ストレス関数の真の勾配の確率論的近似、と考えることができる。λが十分に小さな数の場合は、こうした精密化の方向の平均により、最も急な角度の方向に近似される。本方法では、伝統的な勾配最小化スキームとは異なり、確率論的な勾配の使用によって各ステップの有効なエラー関数（effective error function）が変更されるので、局所的な最小からの影響を受けにくくなる。さらに、本方法は確率サンプリングを介してインターポイント距離における冗長性を利用している。Ｄ次元空間におけるＮ個の点の相対的な構成は、（Ｎ−Ｄ／２−１）／（Ｄ＋１）の距離を使用するだけで十分に説明でき、これがＳＰＥの線形の複雑性に一致することはよく知られている。時間とメモリの線形スケーリングは、膨大なデータ・セットが山積みされている現代のデータ・マイニング（data mining）にとって不可欠である。
【００３３】
ＩＳＯＭＡＰやＬＬＥと同様に、ＳＰＥも近傍半径ｒｃの選び方に左右される。ｒｃが大きすぎると、局所的な近傍は他の多様体のブランチのデータ・ポイントを含み、それらをショートカットするため、最終的な埋め込みにおける実質的なエラーにつながる。小さすぎる場合は不連続の原因となり、多様体は膨大な数の切断されたクラスタの断片となる。参照により全体として本明細書に組み込まれている非特許文献７で説明するように、近傍半径（neighbourhood radii）の範囲でアルゴリズムの安定度を検討することにより、最適なしきい値が決定される。
【００３４】
ｒｃを無限大に設定することにより、ＳＰＥは、伝統的なＭＤＳから導き出されるのと本質的に同等の非線形のマップを作成できる。この場合、ランダムに選択された事実上すべてのペアが「生産的」な作業を結果として生じさせるため、アルゴリズムの効率はより高くなる。アイソメトリック・ＳＰＥ（isometric SPE）では、一度マップの全体構造が確立されると、ほとんどのリモート・ポイントはすでに下限を超えて分離されているため、ペアごとの比較の大部分はいかなる精密化ももたらさない。この状況は、精密化の過程で近傍をキャッシングならびに再サンプリングすることによって改善することができる。
【００３５】
非線形性が、ＰＣＡやＭＤＳといったこれまでの方法の使用を複雑にしていた問題でも前述のように、かなりの近接性の測定値が定義可能である問題にも、ＳＰＥは、実質的に適用することができる。本方法は、実装に対して計算量的に負荷が重いものではなく、初歩的なデータ分析や視覚化のツールとして利用することができる。ＳＰＥが作成する座標は、観測結果（observation）と埋め込み空間の間の明示的なマッピング機能を導き出すためのパラメータ学習機能への入力として利用できる。
【００３６】
ＳＰＥは基本的に、距離の上限と下限のセット（近傍のポイントの近接性は、同一の下限および上限を持つ変性した距離範囲として見なすことができる）に適合する埋め込みを探すため、ＳＰＥは、配座分析（参照により全体として本明細書に組み込まれている非特許文献８を参照）、ＮＭＲ構造の決定、プロテイン構造の予測（参照により全体として本明細書に組み込まれている非特許文献９を参照）を含む距離幾何図形的配列（distance geometry）についての他のクラスにも適用できる。
【００３７】
図４は、ＳＰＥアルゴリズムを実装するための方法の例４００を示すプロセス流れ図である。このプロセスは、ステップ４０２から始まる。このステップには、Ｎポイント｛ｙｉｋ，  ｉ＝１，２，．．．，Ｎ，  ｋ＝１，２，．．．，ｎ｝のｎ次元座標を初期化するステップが含まれる。
【００３８】
ステップ４０４には、カットオフｒｃ距離を選択することが含まれる。
【００３９】
ステップ４０６には、λ＞０の学習率（learning rate）λを選択することが含まれる。
【００４０】
ステップ４０８には、各ポイントのサブセット（たとえば２つのポイント、ｉとｊ）を選択することが含まれる。各ポイントのサブセットは、ランダムに選択できる。
【００４１】
ステップ４１０には、入力空間内の各ポイントの選択されたサブセットの近接性、ｒｉｊ、を取得することまたは評価することと、ｎ次元マップ上のユークリッド距離
【００４２】
【数３】
2006504159.tif 000005
【００４３】
を計算することが含まれる。
【００４４】
ステップ４１２では、決定が行われる。ｒｉｊ≦ｒｃまたはｒｉｊ＞ｒｃかつｄｉｊ＜ｒｉｊの場合、処理はステップ４１４に進む。このステップには座標ｙｉｋとｙｊｋの更新、訂正が含まれる。ただし、εはゼロによる除算を回避するために使用される小さな数値である。
【００４５】
【数４】
2006504159.tif 000006
【００４６】
【数５】
2006504159.tif 000007
【００４７】
処理は、下記のステップ４１６の繰り返しの決定に進む。
【００４８】
ステップ４１２に戻って、ｒｉｊ＞ｒｃかつｄｉｊ≧ｒｉｊの場合は座標を変更せずにステップ４１６に進む。
【００４９】
ステップ４０８からステップ４１４は、指定の回数だけ繰り返される。こうして、ステップ４０８から４１４を指定の回数だけ実行したかどうかに関して、ステップ４１６で決定される。
【００５０】
ステップ４０８から４１４が指定の回数だけ反復された場合、処理はステップ４１８に進み、このステップは学習率λを所定のδλだけ減少させることを含む。ここで処理はステップ４０８に進む。ステップ４０８から４１４は、減少した学習率λでもう一度指定の回数だけ実行される。この反復処理は、任意の回数実行することができる。さまざまな学習率λでステップ４１０から４１８を実行する場合に、反復回数は同じでも異なっていてもよい。さまざまな学習率λで指定の回数だけ繰り返した後、プロセスはステップ４２０で終了する。
【００５１】
ある研究対象について、埋め込みは、確率サンプリングにより決定されたとおり、１００回の精密化サイクル、２．０から０．０１まで直線的に減少する学習率、サンプルに含まれるすべてのペアごとの近接性について１０％しきい値による近傍半径、を使用して実行された。λ＞１の学習率の初期値λは、ランダムな初期設定の展開（unfolding）を迅速化するために使用された。別の学習スケジュールを使用すること可能である。
【００５２】
スイス・ロール（Swiss roll）のデータ・ポイントは、３次元座標｛ｘ＝φｃｏｓφ，ｙ＝φｓｉｎφ，ｚ｝を生成することによって取得できた。ただし、φとｚは、それぞれ、区間［５，１３］および［０，１０］内のランダムな数値である。
【００５３】
メチルプロピルエーテルの配座は、距離幾何図形的配列アルゴリズムを使用して生成される。このアルゴリズムでは、共役結合の制約（covalent constraints）を使用して原子間距離の上限と下限を確立し、さらにこうした境界に適合する配座の生成を試みる。参照により全体として本明細書に組み込まれている非特許文献１０を参照されたい。
【００５４】
各配座間の近接性は、（２つの配座に対して、この２つの配座が変換と回転によって重ね合わせられる場合、ＲＭＳＤは、各原子座標のベクトル間の最小のユークリッド距離として定義される）ＲＭＳＤによって測定される。ＲＭＳＤは、正（positive）であり、対称（symmetric）であり、三角不等式（triangular inequality）を満たしているので、ＳＰＥの有効な近似測定値となる。
【００５５】
３つのコンポーネントから成る仮想的な組合せライブラリは、２つのアルデヒドのビルディング・ブロックを、還元アミノ化反応（reductive amination reaction）に応じてジアミン・コア（diamine core）に体系的に付加することによって、生成されている。各生成物は、１１７の計算されたトポロジカルなインデックスによって特徴付けされた後、区間［０，１］内に正規化され、主要な要素の分析によって相互の関連が解除されて、これはデータにおける全体の分散の９９％を占める直交する２６の変数になる。  結果として得られた２６次元のＰＣ空間におけるユークリッド距離は、２つの複合物間の近接性の測定値として使用された。ＰＣＡ前処理のステップによって、典型的なグラフ理論記述子（graph-theoretic descriptors）である強力な線形の相関関係が除去され、近接性の計算が高速化される。大規模なデータ・セットに関しては、報告されたストレス値は、１，０００，０００のペアごとの距離のランダム・サンプリングにより計算されている。これらの確率論的ストレス値は、真のストレスを正確に近似するように示されている。
【００５６】
本発明は、ここで述べた機能を実行できる１つまたは複数のコンピュータ・システムに実装できる。たとえば、プロセス・フローチャート４００またはその一部は、コンピュータ・システムに制限なく実装できる。
【００５７】
図５は、例となるコンピュータ・システム５００を示している。この例となるコンピュータ・システム５００におけるさまざまなソフトウェアの実施形態について以下に説明する。この説明を参照すれば、他のコンピュータ・システムおよび／またはコンピュータ・アーキテクチャを使用して本発明を実装する方法は当業者には明らかである。
【００５８】
例となるコンピュータ・システム５００には、１つまたは複数のプロセッサ５０４が含まれる。プロセッサ５０４は、通信インフラストラクチャ５０２に接続する。
【００５９】
コンピュータ・システム５００には、さらにメイン・メモリ５０８が含まれており、これはランダム・アクセス・メモリ（ＲＡＭ）であるのが好ましい。
【００６０】
コンピュータ・システム５００には、さらに補助メモリ５１０が含まれる。補助メモリには、たとえばハードディスク・ドライブ５１２および／またはフロッピー（登録商標）ディスク・ドライブ、磁気テープ・ドライブ、光ディスク・ドライブなどのリムーバブル・ストレージ・ドライブ５１４を含めてもよい。リムーバブル・ストレージ・ドライブ５１４は、既知の方法でリムーバブル・ストレージ・ユニット５１８の読み出しおよび／または書き込みを行う。リムーバブル・ストレージ・ユニット５１８は、リムーバブル・ストレージ・ドライブ５１４を介して読み込みおよび／または書き込みが行われるフロッピー（登録商標）ディスク、磁気テープ、光ディスクなどを表す。リムーバブル・ストレージ・ユニット５１８には、コンピュータ・ソフトウェアおよび／またはデータが格納されるコンピュータで使用可能な記憶媒体が含まれる。
【００６１】
別の実施形態では、補助メモリ５１０にコンピュータ・プログラムまたは他の命令をコンピュータ・システム５００にロードするための他のデバイスを含めてもよい。こうしたデバイスには、たとえば、リムーバブル・ストレージ・ユニット５２２とインターフェース５２０を含めることができる。こうした例には、リムーバブル・ストレージ・ユニット５２２からコンピュータ・システムに５００にソフトウェアおよびデータを転送することを可能にするプログラム・カートリッジならびにカートリッジ・インターフェース（ビデオ・ゲームデ・バイスに見られるような）、リムーバブル・メモリ・チップ（ＥＰＲＯＭやＰＲＯＭなど）、ならびに関連するソケット、他のリムーバブル格納ユニット５２２およびインターフェース５２０を含めてもよい。
【００６２】
コンピュータ・システム５００には、さらにコンピュータ・システム５００と外部機器の間のソフトウェアやデータ転送を可能にする通信インターフェース５２４を含めることができる。通信インターフェース５２４の例には、モデム、ネットワーク・インターフェース（Ｅｔｈｅｒｎｅｔ（登録商標）カードなど）、通信ポート、ＰＣＭＣＩＡスロットやカード等が含まれるがこれらに限定はされない。通信インターフェース５２４を経由して転送されるソフトウェアおよびデータは、通信インターフェース５２４から受信できる電子、電磁気、光学、その他の信号である信号５２８の形態をとる。これらの信号５２８は、信号パス５２６を経由して通信インターフェース５２４に提供される。信号経路５２６は、信号５２８を運び、ワイヤー、ケーブル、光ファイバー、電話線、携帯電話リンク、ＲＦリンク、ならびに他の通信チャネルを使用して実装できる。
【００６３】
本明細書において、「コンピュータ・プログラム媒体」ならびに「コンピュータ使用可能媒体」という用語は、一般的にリムーバブル・ストレージ・ユニット５１８、ハードディスク・ドライブ５１２にインストールされたハードディスク、信号５２８のことを言う。これらのコンピュータ・プログラム製品は、コンピュータ・システム５００にソフトウェアを提供する手段である。
【００６４】
コンピュータ・プログラム（コンピュータ制御ロジックともいう）は、メイン・メモリ５０８および／または補助メモリ５１０に格納される。コンピュータ・プログラムは、通信インターフェース５２４を経由して受信することもできる。こうしたコンピュータ・プログラムにより、コンピュータ・システム５００はここで述べてきた本発明の機能を実行時に実現できる。特に、こうしたコンピュータ・プログラムは実行時に、（１つまたは複数の）プロセッサ５０４が本発明の機能を実行できるようにする。したがって、こうしたコンピュータ・プログラムはコンピュータ・システム５００の制御機能を表現する。
【００６５】
一実施形態では、本発明がソフトウェアによって実装されており、ソフトウェアはコンピュータ・プログラム製品として格納でき、コンピュータ・システム５００にリムーバブル格納ドライブ５１４、ハードディスク・ドライブ５１２、または通信インターフェース５２４を使用してロードできる。制御ロジック（ソフトウェア）は、（１つまたは複数の）プロセッサ５０４の実行時に、（１つまたは複数の）プロセッサ５０４がここで述べてきた本発明の機能を実行できるようにする。
【００６６】
別の実施形態では、たとえばアプリケーション専用集積回路（ＡＳＩＣ）などのハードウェア・コンポーネントを使用して基本的にハードウェアとして本発明を実装してもよい。ハードウェア・ステート・マシンを実装してここに記載する機能を実現できることは、当業者には言うまでもない
さらに別の実施形態では、本発明はハードウェアとソフトウェアの組合せによって実装されている。
【００６７】
結論
以上、本発明について、その指定された機能の実行およびそれらの関係を表す機能上のビルディング・ブロックの補助を使用して説明してきた。これらの機能上のビルディング・ブロックの境界は、ここでは説明しやすいように適宜定義したが、本発明の指定された機能および関係が適切に実現される限り、別の境界を定義してもよい。したがって、こうした別の境界はいかなるものも特許請求の範囲に示す本発明の範囲と精神を逸脱しない。こうした機能上のビルディング・ブロックは、個別のコンポーネント、アプリケーション専用集積回路、適切なソフトウェアを実行するプロセッサなどのいずれでも、あるいはそれらの組合せによっても実装できることを、当業者は認めるであろう。
【００６８】
以上、本発明のさまざまな実施形態について説明してきたが、こうした実施形態は例示のみを目的とするものであり、限定を意味しないことを理解されたい。したがって、本発明の広がりと範囲は前述の実施形態のいずれによっても限定されず、添付の請求項とその均等なものによってのみ定義されるべきである。
【図面の簡単な説明】
【００６９】
【図１Ａ】３次元空間におけるスイス・ロール・データ・セットを示す図である。
【図１Ｂ】ＳＰＥによって取得したスイスロール・データ・セットの２次元の埋め込みを示す図である。
【図１Ｃ】ＳＰＥおよびＭＤＳによって取得したスイスロール・データ・セットの埋め込みの最終ストレスを、埋め込みの次元の関数として示す図である。
【図１Ｄ】ＳＰＥで取得したスイス・ロール・データ・セットの２次元の埋め込みの最終ストレスを、１０３、１０４、１０５、１０６ポイントを収容する４つのデータ・セットのシミュレーション長の関数として示した図である。
【図２Ａ】距離幾何図形的配列（distance geometry）アルゴリズムにより生成され、ＲＭＳＤによって比較されたメチルプロピルエーテルＣ１Ｃ２Ｃ３Ｏ４Ｃ５の１０００の配座の２次元確率論的近接性についての埋め込みを示す図である。
【図２Ｂ】ＳＰＥおよびＭＤＳによって取得したメチルプロピルエーテルの１０００の配座の埋め込みの最終ストレスを、埋め込みの次元の関数として示す図である。
【図３Ａ】ＳＰＥによって取得したジアミンの組合せライブラリについての２次元の埋め込みを示す図である。
【図３Ｂ】ＳＰＥおよびＭＤＳによって取得したジアミンの組合せライブラリについての埋め込みの最終ストレスを、埋め込みの次元の関数として示す図である。
【図３Ｃ】ＳＰＥで取得した２次元埋め込みの最終ストレスを、１０３、１０４、１０５、１０６の複合物を収容する４つのデータ・セットのシミュレーション長の関数として示す図である。
【図４】ＳＰＥの方法を実装するためのプロセス流れ図４００である。
【図５】本発明を実装できるコンピューティング・システムの例を示すブロック図である。
【図１Ａ】
2006504159.tif 000008
【図１Ｂ】
2006504159.tif 000009
【図１Ｃ】
2006504159.tif 000010
【図１Ｄ】
2006504159.tif 000011
【図２Ａ】
2006504159.tif 000012
【図２Ｂ】
2006504159.tif 000013
【図３Ａ】
2006504159.tif 000014
【図３Ｂ】
2006504159.tif 000015
【図３Ｃ】
2006504159.tif 000016
【図４】
2006504159.tif 000017
【図５】
2006504159.tif 000018