(57)【特許請求の範囲】
【請求項１】
パターン辞書形成手段と探索手段とを含むコンピュータに対して、照会タンパク質Ｑとタンパク質のデータベースＤ内の複数のタンパク質との間のアミノ酸配列の相同性を検出させるための方法であって、該コンピュータに対して、
前記パターン辞書形成手段が、
前記データベースＤ内の配列Ｓの少なくとも部分集合を表す正規表現として、
式
Σ（Σ∪｛'．'｝）×Σ
（上記式中、Σは、タンパク質を構成するアミノ酸を表す文字の集合を示し、'．'が、Σ内の任意の文字によって占めることができるアミノ酸配列内の位置を示すドント・ケア文字を表す）
によって表されるパターンであって、前記データベースＤ内に含まれる少なくともＫmin個の配列と一致する統計的に有意なパターンＰを含むパターン辞書Πを形成するステップと、
前記探索手段が、
前記照会タンパク質Ｑに一致する全ての前記パターンＰを前記パターン辞書Πから識別し、識別した前記パターンＰに一致する前記データベースＤ内の配列Ｓの領域の全てについて、該配列Ｓの領域と前記パターンＰに一致する前記照会タンパク質Ｑの配列領域とを対にし、当該対にされた領域について、両者の相同性をスコアリングして評価する探索ステップと、
を実行させ、
前記パターン辞書形成手段が前記パターン辞書Πを形成するステップは、
パターンＰの統計的有意性を決定するＫminを導出するためのステップを含み、該ステップは、
バックボーン構造Ｂを有するパターンであって、前記データベースＤ内においてＫ個の対応する配列Ｓを有するパターンの数として定義されるＮB,Kを算出するステップと、
前記データベースＤ内の各配列Ｓの文字のランダムな置換を計算することによって、ランダム・データベースＤｉを生成することをＮ回（ｉ＝１、…、Ｎ）試行するステップと、
バックボーン構造Ｂを有するパターンであって、前記ランダム・データベースＤｉ（ｉ＝１、…、Ｎ）内においてＫ個の対応する配列を有するパターンの数として定義されるランダム変数ＸｉB,Kを算出するステップと、
前記ランダム変数ＸｉB,Kの平均値ｓB,Kおよび分散ｍB,Kを計算するステップと、
前記ＮB,Kと、前記平均値ｓB,Kおよび前記分散ｍB,Kを使用して、下記式を満足する定数値Ｃを計算し、前記定数値Ｃの自乗の逆数として、確率式Ｐｒ［ＸB,K＞ＮB,K］の上界ｐB,Kを計算するステップと、
【数１】
0004250339.tif 000011
信頼性のレベルを強制するための確率値として０と１の間の実数であるthresholdを設定するステップと、
下記不等式
【数２】
0004250339.tif 000012
を満足する最小の数ＫをＫminとして導出するステップとを含み
前記バックボーン構造Ｂは、前記パターンの文字を値「１」で置換し、前記ドント・ケア文字を値「０」で置換する時に得られる数値集合｛１、０｝上の文字列として定義される、
方法。
【請求項２】
コンピュータをして照会タンパク質Ｑとタンパク質のデータベースＤ内の複数のタンパク質との間のアミノ酸配列の相同性を検出させるための装置であって、前記コンピュータは、
前記データベースＤ内の配列Ｓの少なくとも部分集合を表す正規表現としてのパターンであって、
式
Σ（Σ∪｛'．'｝）×Σ
（上記式中、Σは、タンパク質を構成するアミノ酸を表す文字の集合を示し、'．'が、Σ内の任意の文字によって占めることができるアミノ酸配列内の位置を示すドント・ケア文字を表す）
によって表される、統計的に有意なパターンＰを収集して、パターン辞書Πを形成するパターン辞書形成手段と、
前記照会タンパク質Ｑに一致する全ての前記パターンＰを前記パターン辞書Πから識別し、識別した前記パターンＰに一致する前記データベースＤ内の配列Ｓの領域の全てについて、該配列Ｓの領域と前記パターンＰに一致する前記照会タンパク質Ｑの配列領域とを対にし、当該対にされた領域について、両者の相同性をスコアリングして評価する探索手段と、
を含み、
前記パターン辞書形成手段は、
パターンＰの統計的有意性を決定するＫminを導出するための手段を含み、該手段は、
バックボーン構造Ｂを有するパターンであって、前記データベースＤ内においてＫ個の対応する配列Ｓを有するパターンの数として定義されるＮB,Kを算出する手段と、
前記データベースＤ内の各配列Ｓの文字のランダムな置換を計算することによって、ランダム・データベースＤｉを生成することをＮ回（ｉ＝１、…、Ｎ）試行する手段と、
バックボーン構造Ｂを有するパターンであって、前記ランダム・データベースＤｉ（ｉ＝１、…、Ｎ）内においてＫ個の対応する配列を有するパターンの数として定義されるランダム変数ＸｉB,Kを算出する手段と、
前記ランダム変数ＸｉB,Kの平均値ｓB,Kおよび分散ｍB,Kを計算する手段と、
前記ＮB,Kと、前記平均値ｓB,Kおよび前記分散ｍB,Kを使用して、下記式を満足する定数値Ｃを計算し、前記定数値Ｃの自乗の逆数として、確率式Ｐｒ［ＸB,K＞ＮB,K］の上界ｐB,Kを計算する手段と、
【数１】
0004250339.tif 000013
信頼性のレベルを強制するための確率値として０と１の間の実数であるthresholdを設定する手段と、
下記不等式
【数２】
0004250339.tif 000014
を満足する最小の数ＫをＫminとして導出する手段とを含み
前記バックボーン構造Ｂは、前記パターンの文字を値「１」で置換し、前記ドント・ケア文字を値「０」で置換する時に得られる数値集合｛１、０｝上の文字列として定義される、
装置。
【請求項３】
請求項１の方法をコンピュータに対して実行させるための、コンピュータ実行可能なプログラムが記録されたコンピュータ可読な記憶媒体。
【発明の詳細な説明】
【０００１】
関連出願の相互参照
本出願は、米国特許出願第６０／１０６２９５号明細書に対する優先を請求し、参照によって本明細書に組み込まれる、本明細書と同時にA. FloratosおよびI. Rigoutsos名義で出願された米国特許出願書「Methods and Apparatus for Performing Sequence Homology Detection」に関する。
【０００２】
【発明の属する技術分野】
本発明は、全般的にはデータベース探索に関し、具体的には、たとえば遺伝子研究などの所与のアプリケーションに関連する、照会配列とデータベース内の配列との間の配列相同性を検出するための方法および装置に関する。
【０００３】
【従来の技術】
遺伝子研究の分野では、新しい遺伝子の配列決定の次の最初のステップは、その遺伝子の機能を同定する作業である。この目標を達成するための最も一般的で直裁な方法では、２つのペプチドの伸展が、配列レベルで十分な類似性を示す（すなわち、わずかな数の挿入、削除またはアミノ酸変異によって一方からもう一方を得ることができる）場合に、それらがおそらく生物学的に関連するという、生物学的事実を利用する。そのような手法の例が、A.M. Lesk著、「Computational Molecular Biology」、Encyclopedia of Computer Science and Technology、A.KentおよびJ.G. Williams編、31:101-165、Marcel Dekker刊、米国ニューヨーク州、１９９４年と、R.F. Doolittle著、「What we have learned and will learn from sequence databases」、Computers and DNA、G. BellおよびT. Marr編集、21-31、Addison-Wesley刊、1990年と、C. Caskey、R. Eisenberg、E. LanderおよびJ. Straus著、「Hugo statement on patenting of DNA」、Genome Digest、2:6-9、1995年と、W.R. Pearson著、「Protein sequence comparison and protein evolution」、Tutorial of Intelligent Systems in Molecular Biology、英国ケンブリッジ、1995年に記載されている。
【０００４】
この枠組みの中で、新しい遺伝子の機能に関するヒントを得るという問題は、アミノ酸の列を同定する相同の１つになる。一般に、相同とは、複数の配列または列の間の類似性または関係を指す。したがって、照会配列Ｑ（たとえば新しい遺伝子）と、明瞭に特徴を記述されたタンパク質の組Ｄを与えられ、Ｄに含まれる配列の領域に類似したＱのすべての領域を探すことになる。
【０００５】
この作業を実現するために最初に使用された手法は、動的計画法と称する技法に基づくものであった。この手法は、S.B. NeedlemanおよびC.D. Wunsch著、「A General Method Applicable To The Search For Similarities In The Amino Acid Sequence Of Two Proteins」、Journal Of Molecular Biology、48:443-453、1970年と、T.F. SmithおよびM.S. Waterman著、「Identification Of Common Molecular Subsequences」、Journal Of Molecular Biology、147:195-197、1981年に記載されている。残念ながら、この方法の計算要件は、特に現在の典型である巨大なデータベースを探索する時に、急速に非現実的になる。一般に、問題は、動的計画法の変形が、最終的に重要ではなくなる相同の計算にかなりの時間を費やすことである。
【０００６】
この問題を回避するための努力において、示量的局所類似性だけの発見に焦点を合わせた多数のアルゴリズムが提案されてきた。これらのアルゴリズムのうちで最もよく知られているのが、ＦＡＳＴＡおよびＢＬＡＳＴと称するアルゴリズムである。ＦＡＳＴＡアルゴリズムは、W.R. PearsonおよびD.J. Lipman著、「Improved tools for biological sequence comparison」、Proc.Natl.Acad.Sci.、85:2444-2448、1988年と、D.J. LipmanおよびW.R. Pearson著、「Rapid and sensitive protein similarity searches」、Science、227:1435-1441、1989年に記載されている。ＢＬＡＳＴアルゴリズムは、S. Altschul、W. Gish、W. Miller、E.W. MyersおよびD. Lipman著、「A basic local alignment search tool」、J.Mol.Biology、215:403-410、1990年に記載されている。大多数の場合に、性能向上は、まず「ギャップのない」相同すなわち、変異のみに起因し、挿入または削除に起因しない類似性を探すことによって達成される。この手法の背後にある理論的基礎は、２つのペプチド列の間の実質的に「ギャップのある」相同において、少なくとも、一致部分にギャップが含まれない部分列の対が存在する見込みがあるということである。これらの部分列（ギャップのない相同）の突きとめを、すべての（ギャップのある）相同を得るための第１ステップとして使用することができる。
【０００７】
しかし、照会配列とデータベース配列の間の類似する領域の同定は、この処理の最初の部分（計算的に最も過酷な）でしかない。第２の部分（生物学者にとって重要な部分）は、これらの類似性の評価すなわち、その類似性が、照会配列とそれに対応するデータ・ベース配列の間で推論された関係（機能的、構造的またはそれ以外）を是認するのに十分確実であるかどうかの判断である。このような評価は、通常は、生物学的情報と統計的推論を組み合わせることによって実行される。通常、類似性は、関係する領域の対のすべてについて計算されたスコアとして定量化される。このスコアの計算には、ギャップ・コスト（ギャップのある位置合せ）の使用と、所与のアミノ酸が別のアミノ酸に変化する進化的確率を与える適当な変異行列の使用が含まれる。これらの行列の例が、ＰＡＭ行列（M.O. Dayhoff、R.M. SchwartzおよびB.C. Orcutt著、「A model of evolutionary change in proteins」、Atlas of Protein Sequence and Structure、5:345-352、1978年を参照されたい）と、BLOSUM行列（S. HenikoffおよびJ.G. Henikoff著、「Amino acid substitution matrices from protein blocks」、Proc.Natl.Acad.Sci.、89:915-919、1992年を参照されたい）である。その後、このコストの統計的な重要性を、そのようなスコアが純粋に偶然によって発生する確率を（なんらかの統計モデルの下で）計算することによって評価する。たとえば、S. Karlin、A. DemboおよびT. Kawabata著、「Statistical composition of high-scoring segments from molecular sequences」、The Annals of Statistics、2:571-581、1990年と、S.KarlinおよびS.Altschul著、「Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes」、Proc.Natl.Acad.Sci.、87:2264-2268、1990年を参照されたい。使用される統計モデルに応じて、この確率は、照会配列の長さ、基礎になるデータベースのサイズなどの複数の要因に依存する可能性がある。しかし、どの従来の統計モデルを使用する場合であっても、いわゆる「グレー領域」すなわち、統計的に重要でないスコアが、実際には生物学的に重要な類似性を示す状況が必ず存在する。残念ながら、これは回避不能でもある。結局、統計モデルによって生物学的現実を近似できる程度には限界がある。
【０００８】
統計的重要さに弱い類似性を付加することに固有の困難に対する代替策が、進化的に離れた相同をモデル化する配列記述子の推論に生物学的知識を使用することである。ＢＬＯＣＫＳ（S. HenikoffおよびJ. Henikoff著、「Automatic Assembly of Protein Blocks for Database Searching」、Nucleic Acids Research、19:6565-6572、1991年を参照されたい）は、新しい遺伝子に機能的に注釈をつけるために、ＰＲＯＳＩＴＥ（S. HenikoffおよびJ. Henikoff著、「Protein Family Classification Based on Searching a Database of Blocks」、Genomics、Vol.19、pp.97-107、1994年を参照されたい）データベースで定義されたタンパク分類から得られるパターンによって誘導されたプロファイルを使用するシステムである。この場合の利益は、この分類が、関係することが既知のタンパクのファミリを扱う専門家によって編集されていることである。その結果、弱い類似性であっても認識でき、注釈付け処理に使用できる。その一方で、どのタンパクが実際に関係し、その結果、パターンによって表現可能であるかに関する知識はそれだけしかない。さらに、タンパクのファミリに、実際には現在要素であると見なされていない要素が含まれるという危険性が常に存在する。これらの要素を検討対象から排除することによって、ファミリに「オーバー・フィット（over fit）」したパターンが得られる可能性がある、すなわち、未同定のファミリ要素に対する外挿について厳密にすぎる。
【０００９】
したがって、改良された配列相同性検出を可能にする独自の辞書形成技法を介して改良されたパターン辞書を作成するための方法および装置の必要と、注釈付きの配列だけの探索に制限されない、配列相同性検出自体のための方法および装置の必要が存在することは明白である。
【００１０】
【発明が解決しようとする課題】
本発明は、以下で詳細に説明するように、改良されたパターン辞書形成技法および改良された配列相同性検出技法を提供することによって、上記および他の必要に対する解決策を提供する。
【００１１】
【課題を解決するための手段】
本発明の配列相同性検出態様では、データベース内の複数の配列と照会配列との間の相同性を検出する、コンピュータに基づく方法に、以下のステップが含まれる。まず、この方法には、データベースに関連するパターンにアクセスするステップが含まれ、各パターンは、データベース内の１つまたは複数の配列の少なくとも一部を表す。次に、照会配列をパターンと比較して、照会配列の１つまたは複数の部分が、パターンによって表されるデータベースの配列の部分に対して相同であるかどうかを検出する。その後、照会配列に対して相同であることが検出された配列のそれぞれについてスコアを生成するが、配列スコアは、検出された配列の相同部分のそれぞれに従って生成された個々のスコアに基づき、配列スコアは、照会配列と検出された配列との間の相同性の度合を表す。
【００１２】
本発明の辞書形成態様では、データベース内の複数の配列を処理する、コンピュータに基づく方法に、以下のステップが含まれる。まず、この方法には、各配列を形成する文字を含む複数の配列のそれぞれを評価するステップが含まれる。次に、データベース内の配列の少なくとも部分集合を表す文字のパターンを少なくとも１つ生成する。このパターンは、統計的有意性を関連付けられており、パターンの統計的有意性は、そのパターンがデータベース内でサポートする配列の最小の個数を表す値によって決定される。
【００１３】
したがって、従来技術の手法からの重要な離反において、本発明の方法論は、データベースの以前の区分を必要としない、任意のデータ・ベースに対して実行される監督されないパターン発見に基づく。ＢＬＯＣＫＳ手法では、データベースが、生物学的に関連する配列の部分集合に（外部の専門家によって）区分されていることが前提である。その後、プロファイルが、各部分集合を個別に処理することによって得られる。この手法の結果として、ＢＬＯＣＫＳは、任意のデータベースを扱うことができない。というのは、そのようなデータベースのすべてが、関係する部分集合に区分されてはいないからである。実際、ＢＬＯＣＫＳは、本明細書で言及するＰＲＯＳＩＴＥデータベースに記述されたタンパク・グループを使用して、やはり本明細書で言及するSwissProtデータベースに関してのみ機能する。その一方で、本発明は、その入力としてデータベース全体を使用することが好ましく、どのパターンが重要でありどれが重要でないかを判断するための自動化された方法論を提供する。
【００１４】
さらに、本発明は、発見されたパターンの統計的重要性を評価するための新しい統計的枠組みを提供する。既存の枠組みとは異なり、本発明の手法では、その計算においてメモリの概念が導入される。すなわち、たとえば照会配列の領域Ａが、あるデータベース配列の領域Ｂと比較される時に、結果の類似性スコアは、データベース内の他のすべての配列に対するＡの類似性を考慮することによって評価される。
【００１５】
本明細書で説明する機能強化された統計モデルを使用することによって、既存の手法を使用した場合には未検出になるはずの重要な局所類似性の検出が可能になる。これによって、本発明のシステムが、従来技術のシステムで可能なレベルより高いレベルの感度で類似性探索を実行できるようになる。
【００１６】
さらに、本発明は、基礎になるデータベースＤで使用可能な部分的な注釈情報を利用するための自動化された方法を提供する。この方法論を用いると、ユーザは、重要でないように見える類似性をより詳細に利用できるようになる。たとえば、パターンが照会配列領域Ａと一致する時に、そのパターンに一致するデータベース領域のすべてを検査することができる。これらのデータベース領域のすべて（またはより多く）が、同一の形で注釈を付けられている場合、この注釈を、照会領域Ａに転送することができる。上の形で照会配列に部分的に注釈を付けることが、総合的な配列注釈に対して有用であることを証明できる。
【００１７】
本発明は、データベースを非常に相同性の高い配列のグループにクラスタ化するための詳細な方法論も提供する。遺伝子データ処理アプリケーションでは、この方法論によって、複数領域タンパクの正しい扱いが可能になる。
【００１８】
本明細書に記載の発明的概念は、たとえばインターネットなどのネットワーク上で、クライアント／サーバ関係で実施できることも諒解されたい。これによって、ユーザは、リモート位置のクライアント装置で照会配列を入力でき、この照会配列は、ネットワークを介してサーバに送信され、サーバで処理される。その後、サーバは、相同性探索の結果を、ネットワークを介してユーザのクライアント装置に返す。
【００１９】
本発明の上記および他の目的、特徴および長所は、添付図面と共に読まれるべき、以下の実施例の詳細な説明から明白になる。
【００２０】
【発明の実施の形態】
本発明を、例の遺伝子データ処理アプリケーションに関連して下で説明する。しかし、本発明は、そのような特定のアプリケーションに制限されないことを理解されたい。そうではなくて、本発明は、一般に、任意のデータベースからのパターン辞書の作成（データベース・レコードを同等の配列表現に適宜変換した後の）と、データベース内のデータに対する所与の照会レコードの制限されない相同性探索の実行に適用可能である。
【００２１】
まず図１を参照すると、本発明の実施例による配列相同性検出システムのブロック図が示されている。例のシステム１００には、探索エンジン・モジュール１１０、パターン辞書１２０、辞書形成モジュール１３０およびソース・データベース１４０が含まれる。下で詳細に説明するように、探索エンジン１１０は、ユーザから照会配列を受け取り、パターン辞書１２０の探索を実行して、何らかの形で照会配列に類似する、データベース１４０からの配列を表す辞書に格納されたパターンを突きとめることを試みる。照会の前に、辞書形成モジュール１３０が、データベース１４０からパターン辞書１２０を作成する。この辞書形成処理を、情報収集または情報マイニングと称する。探索エンジン１１０は、照会結果（たとえば、データベースからの相同配列）の一部またはすべてをユーザに返す。
【００２２】
図２は、配列相同性検出システム１００の例のハードウェア実施形態のブロック図である。図からわかるように、システム１００は、プロセッサ２１０、メモリ２２０および入出力装置２３０に従って実施することができる。本明細書で使用する用語「プロセッサ」は、たとえばＣＰＵ（中央処理装置）を含むものなど、すべての処理装置を含むことが意図されていることを諒解されたい。本明細書で使用する用語「メモリ」は、たとえばＲＡＭ、ＲＯＭ、固定メモリ装置（たとえばハード・ドライブ）、取外し可能メモリ装置（たとえばディスケット）、フラッシュ・メモリなど、プロセッサまたはＣＰＵに関連するメモリを含むことが意図されている。さらに、本明細書で使用する用語「入出力装置」は、たとえばキーボードなどの、照会を行うか処理装置にデータを入力するための１つまたは複数の入力装置と、たとえばＣＲＴ表示装置またはプリンタなどの、照会結果または処理装置に関連する他の結果を提示するための１つまたは複数の出力装置とを含むことが意図されている。また、用語「プロセッサ」が複数の処理装置を指す場合があり、処理装置に関連するさまざまな要素が、他の処理装置によって共用される場合があることを理解されたい。したがって、本明細書で説明する、本発明の方法論を実行するための命令またはコードを含むソフトウェア構成要素は、関連するメモリ装置（たとえばＲＯＭ、固定メモリまたは取外し可能メモリ）のうちの１つまたは複数に格納することができ、利用の準備ができた時に、部分的にまたは全体を（たとえばＲＡＭに）ロードでき、ＣＰＵによって実行できる。
【００２３】
図３は、本発明の配列相同性検出システムのネットワークベースの実施形態のブロック図である。図からわかるように、クライアント・コンピュータ・システム３１０は、たとえばインターネットなどのネットワーク３３０を介して、サーバ・コンピュータ・システム３２０と通信している。しかし、このネットワークは、私有ネットワークまたはローカル・ネットワークとすることもできる。図３の実施形態によれば、図１に示されたシステム１００の要素のすべてまたは一部が、サーバ３２０に常駐し、サーバ３３０によって実行される。たとえばパーソナル・コンピュータ、ラップトップ機または他の種類のパーソナル処理装置などの自分のクライアント・コンピュータ・システムでリモートに操作するユーザは、たとえばウェブ・ブラウジング・ソフトウェアまたは探索エンジンに関連するグラフィカル・ユーザ・インターフェースなど、そのコンピュータ・システム上で走行するアプリケーション・ソフトウェアを介して照会配列を入力する。この照会は、ネットワーク３３０を介して通常の形で渡され、サーバ３２０によって処理される。サーバ３２０は、照会を受け取り、格納されたパターン辞書に従って、本発明の探索エンジン方法論を実行する。辞書は、ソース・データベースに従って、本発明の辞書形成モジュールによって形成しておくことができる。サーバは、照会結果（たとえばデータベースからの相同配列）の一部またはすべてを、ネットワークを介してクライアントに返す。サーバは、複数のコンピュータ・システムを表す場合があることを理解されたい。すなわち、図１の要素のうちの１つまたは複数が、たとえば独自のプロセッサ、メモリおよび入出力装置を有する、独自のコンピュータ・システムに常駐し、それによって実行される場合がある。
【００２４】
本発明の配列相同性検出システムおよびさまざまな例のハードウェア実施形態の要素の全般的な説明を示したので、これから、さまざまな発明的方法論を詳細に説明する。
【００２５】
探索エンジン・モジュール１１０および辞書形成モジュール１３０に関連するめいめいの方法論を、下で、配列相同性検出システム１００に関連する例の実施形態において、一緒に説明する。しかし、探索エンジン・モジュールに関連する発明的方法論は、他の既知のパターン辞書と共に使用することができることを理解されたい。同様に、辞書形成モジュールに関連する発明的方法論は、他の既知の探索エンジンと共に使用するためのパターン辞書作成に使用することができる。
【００２６】
参照を容易にするために、残りの詳細な説明は、（Ｉ）定義、（ＩＩ）探索エンジン、（ＩＩＩ）辞書形成および（ＩＶ）実験結果の４節に分割する。
【００２７】
Ｉ．定義
この節では、以下で本発明のさまざまな態様の説明に使用される表記の一部を示す。
【００２８】
Σは、配列構成に使用される文字の集合を指す。生物学的設定（本明細書で好ましく対処される設定）では、扱われる配列は、タンパクであり、集合Σは、２０個のアミノ酸の集合である。用語「プロテイン」および「配列」は、以下では交換可能に使用され、用語「文字」および「アミノ酸」についても同様である。
【００２９】
Ｄは、パターンの集合（パターン辞書またはバイオ辞書）がそれに基づいて作成される、基礎となるタンパクのデータベースを指す。この説明全体を通じて使用される例のデータベースは、次の通りである（３つの配列が含まれる）。
Ｄ＝｛ｓ1、ｓ2、ｓ3｝、ここで
ｓ1＝ＡＲＱＳＴＬＵＭＮＰＱ
ｓ2＝ＦＤＳＡＬＱＦＴＧＭＲＡ
ｓ3＝ＲＫＭＦＰＱＤＤＳＬＡ
【００３０】
Πは、パターンの集合すなわち、本明細書でバイオ辞書またはパターン辞書１２０と称するものを指す。Πを得る正確な方法は、下の、「辞書形成」と題した節で説明する。パターンは、ペプチドのファミリを記述した正規表現である。単一のパターンによって表現されるポリペプチド・ファミリには、関連する（構造的、機能的、進化的に）アミノ酸の伸展が含まれると期待される。具体的に言うと、アミノ酸のアルファベットΣに対して、Πに含まれるパターンＰを、次の形の正規表現として定義する。
Σ（Σ∪｛'．'｝）×Σ
ここで、'．'（「ドント・ケア文字」と称する）は、任意の残留物が占めることのできる位置を表す。正規表現であるから、すべてのパターンＰが、ドント・ケア文字のそれぞれをΣからの任意の残留物によって置換することによってＰから得ることのできるすべての列からなるポリペプチドの言語を定義する。また、Πに含まれるＰのそれぞれが、Ｄに含まれる少なくともＫmin個の配列と一致する。Ｋminは、整数であり、その計算は、下の「辞書形成」の節で説明する。下の説明では、特定の値を仮定する。データベース配列の、パターンＰに一致する領域が、パターンＰのオフセット・リストＬD（Ｐ）に記録される。これは、パターンＰがデータベースのｊ番目の配列のオフセットｋで一致するすべての対（ｊ、ｋ）を含むリストである。
【００３１】
上で導入した例のデータベースについて、Ｋmin＝２と仮定すると、パターンの集合は、Ｐ＝｛Ａ．Ｑ．Ｔ、Ｍ．ＰＱ｝である。この集合の２つのパターンは、次の入力配列に現れる（一致する位置を太字で示す）。
【表１】
0004250339.tif 000002
【００３２】
この２つのパターンのオフセット・リストは次のようになる。
ＬD（Ａ．Ｑ．Ｔ）＝｛（１，１），（２，４）｝
ＬD（Ｍ．ＰＱ）＝｛（１，８），（３、３）｝
【００３３】
それぞれの小括弧内の最初の項が、配列番号であり、第２項が、オフセットであることを諒解されたい。配列内のいずれかの文字に対応するオフセットは、配列の先頭からのその文字の距離である。たとえば、（２、４）は、配列がｓ2であり、パターンＡ．Ｑ．Ｔが、配列ｓ2の先頭から４文字の距離から始まることを示す。
【００３４】
Ｑは、照会タンパクを指す。本発明の探索エンジンの目的は、Ｄのデータベース配列と、ユーザが供給することのできる照会配列Ｑとの間の配列相同性を識別することである。１例として、照会Ｑ＝ＪＬＡＮＱＦＴＬＭＤＰＱＤＬＡを使用する。この配列は、データベース配列との複数の相同領域を有する。下に、その一部を示す（やはり、類似領域の対を太字で示す）。
【表２】
0004250339.tif 000003
【００３５】
したがって、探索エンジンは、上で示したものなどの類似性を識別する。等しい長さの２つの領域が類似するのは、一方を他方の下に置いた時に、複数の一致する文字がそろう場合である。類似性の正確な概念は、以下で正確に示すが、ここでは、可能な文字のすべての対のスコアが使用されると述べれば十分である。そのようなスコアのすべてが、適応度の尺度であり、２つの文字がそろうことの生物学的な確率がどの程度であるかが識別される。
【００３６】
パターンＰに対して、Ｐの「バックボーン」は、Ｐのすべての残留物を文字「１」で置換し、すべてのドント・ケア文字を文字「０」で置換することによってＰから得られるアルファベット｛１、０｝上の文字列として定義される。たとえば、パターンＰ＝「Ａ．．ＤＦＥ」のバックボーンは、文字列「１００１１１」である。バックボーンによって、パターンの集合が、同一のバックボーンを共用するすべてのパターンが各クラスに含まれる同等のクラスに区分される。
【００３７】
本発明に従って使用することのできるもう１つの概念が、パターンの「密度」である。一般に、密度は、Ｇ（Ｐ）の２つの要素の間の相同性の最小量を表し（Ｇ（Ｐ）は、ドント・ケア文字のそれぞれをΣからの任意の残留物によって置換することによってＰから得ることのできるすべての文字列からなるポリペプチドの言語を指す）、２つの整数ＬおよびＷ（Ｌ≦Ｗ）によって定義される。パターンＰは、アミノ酸で始まり、アミノ酸で終わり、少なくともＷの長さを有するＰの部分列のすべてにＬ個以上の残留物が含まれる場合に、＜Ｌ、Ｗ＞の密度を有する。そのようなパターンのすべてにおいて、パターンの長さに対する残留物の数の比率は、少なくともＬ／Ｗである。整数ＬおよびＷは、本発明の好ましい方法のパラメータであり、その値によって、実行される探索で許容される類似性の量が制御される。これらのパラメータは、参照によってその開示を本明細書に組み込まれる米国特許出願第６０／０４９４６１号明細書に対する優先権を請求されている、「ＴＥＩＲＥＳＩＡＳ」アルゴリズムに対処する米国特許出願第０９／０２３７５６号明細書に詳細に記載されている。定義により、＜Ｌ、Ｗ＞パターンは、少なくともＬ個の残留物を有することに留意されたい。
【００３８】
さらに、パターンＰと配列Ｓに対して、Ｇ（Ｐ）に属するＳの部分列を、Ｐの整合部位と呼ぶ。Ｐのオフセット・リストには、Ｐのすべての整合部位の最初の文字のオフセットが含まれる。
【００３９】
上の定義を仮定すれば、たとえばシステム１００（図１）に関連する、本発明による改良された配列相同性検出に対する好ましい手法の一般的な説明を提供することができる。配列相同性検出には、２つの別個の相すなわち、情報収集と探索が含まれる。
【００４０】
まず、探索を実行する前に、基礎となるデータベースＤをマイニングする。このマイニング手順を、情報収集または辞書形成とも称する。このステップの間に、有意の＜Ｌ、Ｗ＞パターンのすべてが収集され、そのようなパターンＰのそれぞれが、そのオフセット・リストＬD（Ｐ）に関連付けられる（パターンが有意であるか否かを判断するのに使用される特定の判断基準は、探索エンジンの節で詳細に説明する）。
【００４１】
第２ステップは、実際の探索である。照会配列Ｑに対して、Ｑに一致するすべてのパターンＰ（この処理の第１相で収集されたものの中から）を識別する。そのようなＰのすべてについて、Ｐと一致するＱの領域を、やはりＰと一致するすべてのデータベース配列の対応する領域と対にする（これらの領域は、オフセット・リストＬD（Ｐ）を介して簡単にアクセスできる）。最後に、対にされた領域を、両方向に拡張し、位置合せし、（ユーザ定義の）変異行列の使用によってスコアを付け、最も高いスコアを有する一致を、暗示される位置合せと共に報告する。
【００４２】
ここで、情報収集相が、Ｄに対する１回の計算であることを指摘する価値がある。得られる結果は、ファイル（図１のパターン辞書１２０）に格納され、データベースＤに対する探索セッションが実行されるたびに使用される。
【００４３】
関連するポリペプチドの記述にパターンを使用することの背後にある動機は、生物学的事実にある。具体的に言うと、タンパクがそれらから作られる基本構成要素である多数の基本的要素（α螺旋、β鎖、ループなどの構造的性質であるか、モチーフ、モジュール、領域などのより大きい機能的単位のいずれか）が存在することが既知である。種の区別のために進化論によって使用される主要な機構の１つが、タンパク配列内のアミノ酸の位置の変異である。しかし、機能的または構造的に重要な領域は、そのような変異に対してより強く抵抗する。したがって、そのような生物学的に関連するポリペプチドを、（ａ）主構造での保存された位置と、（ｂ）再利用性の度合の高さとを発見することによって同定できると期待することが合理的である。本明細書の用語法では、これらの特性は、予期されない高さのサポートを有するパターンに対応する。
【００４４】
しかし、重要なことなので繰り返すが、本明細書に記載の発明的探索エンジン方法論を、他の既知のパターン辞書と共に使用することができる。同様に、発明的辞書形成方法論を使用して、他の既知の探索エンジンと共に使用されるパターン辞書を作成することができる。
【００４５】
この両方の方法論を、それぞれ下の節ＩＩおよび節ＩＩＩで説明することを諒解されたい。辞書形成方法は、探索方法の前に適用されるが、説明を簡単にするために、この処理を逆の順序で説明し、探索エンジン方法から始めて、辞書形成方法を後に回す。
【００４６】
ＩＩ．探索エンジン
ここで図４を参照すると、本発明の１実施例による、探索エンジン方法論を示す高水準流れ図が示されている。この方法論は、図１の探索エンジン１１０によって使用することができる。探索エンジンの動作は、２つの別個の相すなわち、（ｉ）パターン照合および連鎖（ブロック４０２）と、（ｉｉ）スコアリング（ブロック４０６）に分解できる。
【００４７】
第１相では、ΠのすべてのパターンＰ（Πが、上で述べたパターン辞書１２０を指すことを想起されたい）を照会配列Ｑに対して検査して、Ｑと一致するすべてのパターンを分離する。下で、この「一致に関する検査」処理を実行する特定のアルゴリズムを説明するが、どのような照合アルゴリズムでも使用することができる。図４の相１の「複雑性検査」（ブロック４０４）に留意されたい。場合によっては、パターンＰが照会Ｑと一致し、なおかつこの一致を考慮に入れることが望ましくないことがありえる。そのような例が、いわゆる「低複雑性」パターンである。そのようなパターンは、生物学的配列の性質に起因して時々生じる。低複雑性パターンは、たとえばパターン「Ａ．Ａ．．ＡＡＡ．Ａ．Ａ」のように、ほぼ完全に同一のアミノ酸だけから構成され、現れる。というのは、いくつかのタンパクが、反復するアミノ酸の長い領域を有するからである。しかし、そのようなパターンは、相同性検出の目的からは重要とみなされず、これらのパターンによって誘導される一致のすべてを無視することがよくなる可能性がある。それを行うか否かの判断は、システム・ユーザに探索エンジン内の「複雑性検査」構成要素を「オン」または「オフ」状態に設定させることによって、システム・ユーザに委ねられる。ここでは、この構成要素が「オン」に設定されている場合に、Ｐの一部のパターンが、照会配列Ｑに一致する場合であっても無視されることを覚えておけば十分である。下で、複雑性検査が「オン」の時にＱに一致するパターンＰが無視される正確な条件の説明を行う。
【００４８】
相１の説明を続けると、Ｑに一致するすべてのパターンＰによって、Ｑと、やはりＰに一致するデータベース領域のすべてとの間の局所相同性が生成される。この後者の領域は、Ｐのオフセット・リストＬD（Ｐ）を介して簡単にアクセス可能である。ＰがオフセットｉでＱに一致すると仮定すると、ＬD（Ｐ）のすべての領域（ｊ、ｋ）が、セグメント（ｉ、ｊ、ｋ、ｌ）を生じる。ここで、ｌはパターンＰの長さである。これを、下で詳細に説明する。最後に、照合処理が進行するにつれて、互換性のあるセグメントが、互いに連鎖され、より長いセグメントが形成される（互換性のあるセグメントの概念ならびに連鎖の動作は、下で説明する）。相１の終りに、Πの少なくとも１つのパターンＰと一致する、データベースＤのすべての配列を含む集合Ｒが残され、このＰもＱと一致する。Ｒに含まれる配列Ｓのそれぞれには、ＱとＳの間のパターンによって誘導された相同性を記述したセグメントが付随する。
【００４９】
上で導入した例を検討されたい。照会配列Ｑ＝ＪＬＡＮＱＦＴＬＭＤＰＱＤＬＡは、ΠのパターンＰ１＝「Ａ．Ｑ．Ｔ」およびＰ２＝「Ｍ．ＰＱ」の両方と一致する。Ｐ１がオフセット３でＱと一致し、Ｐ２がオフセット９でＱと一致するので、これらの２つの一致は、次の４つのセグメントを生じる。
（３，１，１，５）（３，２，４，５）  ＬD（Ｐ１）から
（９，１，８，４）（９，３，３，４）  ＬD（Ｐ２）から
また、集合Ｒは、
Ｒ＝｛ｓ1−−（３，１，１，５）（９，１，８，４）
ｓ2−−（３，２，４，５）
ｓ3−−（９，３，３，４）｝
であり、Ｒの各配列ｓiは、セグメントのリストを伴う。この特定の例では、可能な連鎖がないことに留意されたい。
【００５０】
図４に示された探索エンジン方法論の相の２番目では、Ｒのすべての配列Ｓにスコアを割り当てる。所与のＳjについてこのスコアを計算するための手法は複数存在する。しかし、どの手法も、Ｓjに伴うすべてのセグメントのスコアリングから開始される。各セグメントは、スコアを受け取る（これらのスコアを「セグメント・スコア」と称する）。スコアリングは、変異行列Ｍに基づいて実行される。変異行列は、実数の２０×２０行列である。そのような行列の第（ｉ、ｊ）項目は、ｉ番目のアミノ酸が、進化中にｊ番目のアミノ酸に変化した確率を示す。ここでの目的のためには、Ｍが、Σ×Σ→Ｒからの関数であり、入力として２つのアミノ酸Ａ１およびＡ２を与えられた時に、実数を返す関数であると仮定すれば十分である。使用することのできる変異行列は多数存在するので、ユーザは、使用する特定の行列Ｍを選ぶ選択権を与えられる。
【００５１】
たとえば、単項変異行列Ｍすなわち、すべてのアミノ酸Ａに対してＭ（Ａ、Ａ）＝１であり、すべての別個のアミノ酸ＡおよびＢに対してＭ（Ａ、Ｂ）＝０である行列を使用すると仮定する。上の集合Ｒの最初の配列すなわち、セグメント（３、１、１、５）および（９、１、８、４）を伴う配列ｓ1を検討されたい。これら２つのセグメントのうちの最初のセグメントのスコアリングの方法を示す（もう一方および集合Ｒのすべてのセグメントは、同様にスコアリングされる）。このセグメントによって暗示される長さ５の２つのタンパク領域すなわち、Ｑのオフセット３とｓ1のオフセット１から始まる領域を位置合せした（一方を他方の下に）と想像されたい。
ＡＮＱＦＴＬ  （Ｑから）
ＡＲＱＳＴＬ  （ｓ1から）
その後、位置合せされたすべての列に対して、値Ｍ（Ｘ、Ｙ）を合計することによって、セグメントのスコアが計算される。ここで、Ｘ、Ｙは、所与の列の下で互いに位置合せされた２つのアミノ酸である。上のセグメントの場合、スコアは次のようになる。
Ｍ(Ａ，Ａ)＋Ｍ(Ｎ，Ｒ)＋Ｍ(Ｑ，Ｑ)＋Ｍ(Ｆ，Ｓ)＋Ｍ(Ｔ，Ｔ)＋Ｍ(Ｌ，Ｌ)
＝１＋０＋１＋０＋１＋１＝４
【００５２】
セグメントについて上で説明したスコアリング方式は、基本的なスコアリング方式である。すなわち、システム・ユーザは、複数のオプションを設定して、セグメント・スコアを計算する方法を変更することができる。たとえば、システム・パラメータextend（整数であり、下で説明する）に０より大きい値がセットされている場合には、スコアリングで、セグメントによって記述されるタンパク領域だけではなく、２つの領域の左右のextend個のアミノ酸の区域も考慮される（スコアリングは正確に上で説明した通りに進行するが、より長い領域が検討される）。さらに、gapped_alignmentオプションがセットされている場合には、拡張領域（すなわち、基本セグメントの左右の領域）の位置合せで、位置合せスコアを最大にするためにギャップも使用する。
【００５３】
上の処理の終りに（どのスコアリング変形形態を使用するかに無関係に）、セグメント・スコアが、集合Ｒのすべてのセグメントについて計算されていることになる。これらのセグメント・スコアは、その後、スコアリング相の最終ステップすなわち、ＱとＲのすべての配列Ｓjとの間の類似性の量の定量化に使用される。この定量化は、ＲのすべてのＳjにスコアを割り当てることによって実行される。このスコアを、Ｓの「配列スコア」と呼ぶ（セグメント・スコアと区別するために）。理想的には、配列Ｓjの配列スコアが高いほど、このＳjがＱに類似するはずである。
【００５４】
Ｓjのスコアリングでは、Ｓjに伴うセグメントのセグメント・スコアだけを考慮した。ここでもいくつかのオプションがある。最も単純な場合には、Ｓjの配列スコアは、Ｓjのセグメントの全セグメント・スコアの間の最大値として定義される。第２の、より複雑な手法を下で説明する。ここでは、まず、スコアリングされる配列Ｓjについて、有向グラフを作成する。このグラフの頂点は、Ｓjに伴う全セグメントである。すべての頂点に、その頂点に対応するセグメントのセグメント・スコアを割り当てる。セグメント（ｉ、ｊ、ｋ、ｌ）からセグメント（ｉ'、ｊ、ｋ'、ｌ'）への辺は、
ｉ≦ｉ'  かつ  ｋ≦ｋ'
すなわち、２つのセグメントによって記述される２つの照会領域（領域Ｑ［ｉ．．ｉ＋ｌ−１］とＱ［ｉ'．．ｉ'＋ｌ'−１］）の相対順序が、２つのセグメントによって記述されるＳjの２つの領域（領域Ｓj［ｋ．．ｋ＋ｌ−１］とＳj［ｋ'．．ｋ'＋ｌ'−１］）の相対順序と同一である場合に配置される。頂点と同様に、すべての辺にも、照会内の領域の変位（すなわち差ｉ'−ｉ）がＳj上の領域の変位（すなわち差ｋ'−ｋ）に対して相対的にどの程度規則的であるかを表すスコアが割り当てられる。変位の間の差（すなわち数｜（ｉ'−ｉ）−（ｋ'−ｋ）｜）が大きいほど、辺のスコアは小さくなる。グラフを作成した後に、標準的な最長経路アルゴリズムを適用して、最高のスコアを有する経路を識別することができる（経路のスコアは、その経路に含まれるすべての頂点および辺のスコアの合計として定義される）。このスコアが、Ｓjの配列スコアになる。
【００５５】
上では、セグメント・スコアと配列スコアの両方を計算する複数の方法を説明した。一般に、他の「生物学的に合理的な」スコアリング方式を、その代わりに使用することができる。
【００５６】
ここで図５、６および７を参照して、探索エンジン方法論４００のパターン照合処理、連鎖処理およびスコアリング処理のより具体的な例を説明する。やはり、探索エンジン１１０によって実施される探索相中に、照会タンパクＱが、システムに供給され、Ｑに類似するデータベース配列Ｓ∈Ｄが、識別され、ユーザに報告される。この探索相では、入力データベースＤのマイニングによって得られたパターンの集合Πを利用する。この例の目的のためには、Πが、上の「定義」の節で説明した形の＜Ｌ、Ｗ＞パターンの集合であると仮定すれば十分である。各パターンＰ∈Πは、そのオフセット・リストＬD（Ｐ）が付随し、Ｄ内で少なくともＫminのサポートを有する。数Ｌ、ＷおよびＫminは、本発明の好ましい方法のパラメータであり、これらを設定する方法は、下の「辞書形成」の節で説明する。
【００５７】
照会配列Ｑがシステムに供給された時に最初に行うべきことは、Ｑと一致するすべてのＰ∈Πを突きとめることである。これは、D. Gusfield著、「Algorithms on strings, trees and sequences: Computer Science and Computational Biology」、Cambridge University Press刊、62-63、1997年に提示された技法のハッシュ変形形態を使用することによって非常に高速に行うことができる。具体的に言うと、Ｑ内のすべての位置について、その位置から始まる長さ２、３、…、（Ｗ＋１）の部分列のすべてについて１つのＷ個のハッシュ値を生成する。そのような部分列のすべてについて、対応するハッシュ値は、部分列の最初の文字と最後の文字ならびにこれら２つの文字の間の残留物の数だけに依存する。
【００５８】
図５に、所与の照会配列に対する処理の例を示す。この例では、配列Ｑの位置６から始まるＷ＝４部分列について生成されたハッシュ値が示されている。部分列ｓのハッシュ値は、
H(s)=((av(first_char)-av('A'))+(av(last_char)-av('A'))*26)*W+gap
である。ここで、ａｖ（ｃ）は、文字ｃのＡＳＣＩＩ値、first_charは、ｓの最初の文字、last_charは、ｓの最後の文字、gapは、ｓの最初の文字と最後の文字の間の残留物の数である。＜Ｌ、Ｗ＞密度制約があるので、gapが必ずＷより小さいことに留意されたい。
【００５９】
特定の値ｈに対応するハッシュ項目には、ｐから始まる部分列（長さが多くともＷ＋１の）が値ｈにハッシュされる、照会配列Ｑのオフセットｐのすべてが格納される。図６に、特定の照会配列について生成されたハッシュ・テーブルの例を示す。図６には、配列Ｑ＝ＡＦＧＨＩＫＬＰＮＭＫＡＭＧＨについて生成されたハッシュ・テーブルのスナップショットが示されている。テーブル項目にラベルを付けるために実際の数値のハッシュ値を使用する代わりに、特定のハッシュ値にハッシュ化されるすべての文字列を記述するパターンを使用する。各ハッシュ項目は、オフセットのリストをポイントする。そのリストのすべてのオフセットが、関連するハッシュ項目にハッシュ化されるＱの部分列の先頭をマークしている。
【００６０】
パターンＰ∈ΠがＱに一致するかどうかを検査するために、Ｑの長さに等しいサイズのカウンタの配列Ｃ［１．．｜Ｑ｜］を使用する。当初は、この配列のすべての要素に０をセットする。Ｐのオフセット１から始めて、最後の残留物に対応するオフセットを除いて、残留物に対応するＰ内のすべてのオフセットｊを突きとめる。そのようなｊのすべてについて、Ｆが、ｊから始まり、正確に２つの残留物を含むＰの最短の部分列であるものとする。ＯＬが、Ｆに対応するハッシュ・テーブル項目によってポイントされるＱのオフセットのリストを表すものとする。ＯＬが空でない場合には、すべてのオフセットｐ∈ＯＬについて、カウンタＣ［ｐ−ｊ＋１］を１つ増分する。パターンＰに、正確にｎ個の残留物が含まれる場合には、この処理の最後に、ＱがオフセットｉでＰと一致する場合に限って、カウンタＣ［ｉ］が値（ｎ−１）を有する。上で説明した照合技法の長所は、この技法に必要な時間が、通常は、照会配列Ｑのサイズに対してほぼ線形であり、パターンＰ内の残留物の個数だけに依存することである。
【００６１】
Ｑのオフセットｉから始まる部分列に一致するパターンＰ∈Πが見つかった後に、Ｑのその部分列を、やはりＰと一致するすべてのデータベース領域と関連させる必要がある。これは、これらの領域を正確に含むオフセット・リストＬD（Ｐ）を操作することによって簡単に行われる。具体的に言うと、各項目（ｊ、ｋ）∈ＬD（Ｐ）は、ｊ番目のデータベース配列Ｓjのオフセットｋから始まる部分列がＧ（Ｐ）の要素であることを示す。その後、照会配列Ｑとデーターベース配列Ｓjの間の局所類似性が、セグメントと称する４つ組（ｉ、ｊ、ｋ、ｌ）として登録され、この４つ組がＳjに関連付けられる。数ｌ＝｜Ｐ｜は、局所類似性の長さである。
【００６２】
時には、両方ともＱと一致する２つの別個のパターンＰおよびＰ'とデータベース配列Ｓjが、ＱとＳjの間の同一の局所類似性に対応する。そのような状況の例を、図７に示す。そのような場合には、２つのパターンに対応する個々のセグメントを、１つに連鎖しなければならない。具体的に言うと、Ｓjに関連する２つのセグメント（ｉ、ｊ、ｋ、ｌ）および（ｉ'、ｊ、ｋ'、ｌ'）は、
ｋ≦ｋ'  かつ  ｋ＋ｌ＋ｗ＿ｌｅｎ＞ｋ'  かつ  ｋ'−ｋ＝ｉ'−ｉ
である場合に限って、互換性があるといわれる。ここで、w_lenは、ユーザによって定義される整数パラメータであり、w_lenによって、一方のセグメントが他方の末尾の後、w_len位置を超えない位置から始まる限り、交差しないセグメントの連鎖が可能になる。（ｉ、ｊ、ｋ、ｌ）と（ｉ'、ｊ、ｋ'、ｌ'）を互いに連鎖することから生じるセグメントは次の通りである。
（ｉ，ｊ，ｋ，ｍａｘ（ｌ，ｋ'−ｋ＋ｌ'））
【００６３】
互換性のあるセグメントの連鎖は、ＱとＳjの両方に一致するパターンＰ∈Πを突きとめた結果として、新しいセグメントがデータベース配列Ｓjに関連付けられるたびに行われる。新たに到着したセグメントと互換性を有する、すでにＳjに関連するセグメントがある場合には、新しいセグメントと既存セグメントの関連する対が、破棄され、その連鎖の結果によって置換される。
【００６４】
Ｑとデータベース配列の間の局所類似性のすべてを識別し終えたところで、これらの類似性を評価する作業が残されている。これは、少なくとも１つのセグメントに関連するデータベース配列Ｓjのすべてにスコアを割り当てる（ユーザ定義のスコアリング行列を使用して）ことによって行われる。スコアリング機能について、複数のオプションが使用可能である。当業者は、本明細書に記載の発明的教示を与えられれば、他のスコアリング方法を理解するであろう。
【００６５】
上で述べたように、１つの手法は、Ｓjの各セグメントを個別にスコアリングし、それらのスコアのうちの最高のものをＳjに割り当てることである。セグメント（ｉ、ｊ、ｋ、ｌ）のスコアリングは、次の２つのいずれかの形で行うことができる。
【００６６】
「ギャップを許容しない」：この場合、スコアは、セグメントによって暗示されるギャップのない位置合せすなわち、照会の領域Ｑ［ｉ、ｉ＋ｌ−１］と配列の領域Ｓj［ｋ、ｋ＋ｌ−１］の位置合せから計算される。さらに、ユーザは、変数extendをセットすることによって、セグメントの「前後」に位置合せを拡張するオプションを与えられる。この変数の値が０より大きい場合には、スコアは、領域Ｑ［ｉ−extend、ｉ＋ｌ−１＋extend］およびＳj［ｋ−extend、ｋ＋ｌ−１＋extend］のギャップのない位置合せから計算される。
【００６７】
「ギャップを許容する」：このオプションは、extend＞０である時に限って使用可能であり、位置合せの領域内のギャップを許容することによって、セグメントの前後の区域のより微細なスコアリングを可能にする。
【００６８】
上で述べたように、現在スコアリング中のデータベース配列Ｓjに関連するセグメントの相対順序を考慮に入れる、他のスコアリング・オプションも提供される。上で述べたように各セグメントを個別にスコアリングした後の手法の１つが、図８に示された重みつき有向グラフを作成することである。このグラフの頂点Ｖは、Ｓjに関連するセグメントであり、セグメント（ｉ、ｊ、ｋ、ｌ）と（ｉ'、ｊ、ｋ'、ｌ'）の間には、
ｉ≦ｉ'  かつ  ｋ≦ｋ'
の場合に有向線分が存在する。すべての頂点に、対応するセグメントのスコアと等しい重みが割り当てられ、すべての辺Ｅは、（ａ）２つのセグメントの近さすなわち（ｉ'−ｉ−１）の値と、（ｂ）２つのセグメントの間の変位の規則正しさすなわち、（ｉ'−ｉ）が（ｋ'−ｋ）とどれだけ違うかに基づいて重みが付けられる。このグラフ内の経路のスコアは、その経路の頂点と辺のすべての重みの合計である。その後、最大のスコアを有する経路が計算され、そのスコアがＳjに割り当てられる。
【００６９】
ここで図９および１０を参照すると、それぞれの流れ図に、本発明の探索エンジン・モジュールによって実行される２つの相の実施形態が要約して示されている。図９は、照合および連鎖相の実施形態９００を示し、図１０は、スコアリング相の実施形態１０００を示す。
【００７０】
図９では、データベースＤのすべての配列Ｓjが、関連するセグメント・リストＳｅｇＬ（Ｓj）を有すると仮定する。当初、これらのリストは、すべてが空である。集合Ｒも、当初は空である。図９の流れ図によって説明される計算が進行するにつれて、配列ＳjがＲに加えられる。そのような配列がＲに挿入される際に、その配列にセグメント・リストＳｅｇＬ（Ｓj）が伴う。
【００７１】
したがって、ΠのすべてのパターンＰについて（ブロック９０２）、探索エンジンは、以下の動作を実行する。ステップ９０４で、探索エンジンは、ＰがＱと一致するかどうかを判定する。そうでない場合には、辞書の次のＰに移る。そうである場合には、ステップ９０６で、探索エンジンは、複雑性検査構成要素がユーザによって使用可能にされたかどうかを判定する。それが使用可能にされている場合には、ステップ９０８で、エンジンは、Ｑに対するＰの一致が低複雑性一致（後で詳細に説明する）であるかどうかを判定する。そうである場合には、エンジンは、辞書の次のＰに移る。そうでない場合には、ＰがＱに一致するすべてのオフセットｉについて（ブロック９１０）、また、ＬD（Ｐ）のすべての（ｊ、ｋ）について（ブロック９１２）、エンジンは以下の動作を実行する。ステップ９１４で、エンジンは、セグメント（ｉ、ｊ、ｋ、｜Ｐ｜）を、ＳｅｇＬ（Ｓj）のすべての互換性のあるセグメントと連鎖する。その後、エンジンは、結果をＳｅｇＬ（Ｓj）に追加する。
【００７２】
ステップ９１６で、エンジンは、ＳjがＲに含まれるかどうかを判定する。そうである場合には、エンジンはステップ９１４に戻る。そうでない場合には、エンジンは、ＳjとＳｅｇＬ（Ｓj）をＲに追加する。ＰがＱに一致するすべてのオフセットｉについて、また、ＬD（Ｐ）のすべての（ｊ、ｋ）について、ステップ９１４ないし９１６を実行する。処理全体（ステップ９０４ないし９１６）が、パターン辞書のすべてのＰについて反復される。
【００７３】
照合と連鎖を実行したので、検索エンジンは、図１０のスコアリング動作を実行する。したがって、Ｒのすべての配列Ｓjについて（ブロック１００２）、また、Ｓjのすべてのセグメントｓについて（ブロック１００４）、エンジンは、ステップ１００６でｓのセグメント・スコアを計算する。その後、Ｒのすべての配列Ｓjについて（ブロック１００８）、エンジンは、ステップ１０１０でＳjの配列スコアを計算する。最後に、ステップ１０１２で、エンジンは、Ｒに含まれるＳjの最高のスコアを、めいめいの配列スコアによって暗示される局所位置合せと共に報告する。
【００７４】
もう一度図４を参照すると、前に述べたように、探索エンジン・モジュール１１０には、複雑性検査構成要素（たとえば図９のステップ９０６）を含めることができる。複雑性検査構成要素は、低複雑性領域が原因で生成される局所相同性を破棄する責任を負う。まず、低複雑性検査は、２つの相すなわち、辞書作成相（「辞書形成」の節）の間ならびに探索相（この節）の両方で発生する。
【００７５】
辞書作成相の間に、低複雑性領域は、２つの形で扱われる。まず、入力データベースでパターンを探す時に、同一のアミノ酸のＬ回以上の連続する出現からなるタンパク領域のすべてを無視（すなわち入力から除去）する（Ｌは、辞書作成相の間に設定される整数のパラメータである。ここでの目的のためには、Ｌがなんらかの固定された値を有すると仮定すれば十分である）。これは、下の太字で示されたものなどの低複雑性領域を処理する（ピリオドは、示された文字列の左右にアミノ酸があることを示す）。
【表３】
0004250339.tif 000004
しかし、これは、低複雑性領域の１例にすぎない。さらに多くのケースが存在する。たとえば、次の領域の太字部分を検討されたい。
【表４】
0004250339.tif 000005
この種の（すなわち、一般化された反復組成の）領域を処理するために、所与のパターンＰのオーバーラップする外見もすべて無視する。言い換えると、パターンＰが、データベース配列Ｓjにオフセットｋ1およびｋ2で一致し（ここで、ｋ2＞ｋ1）、ｋ2−ｋ1がＰの長さより小さい場合には、どちらのオフセットも、パターンＰのオフセット・リストＬD（Ｐ）には配置されない。たとえば、上に示した領域では、６の長さを有するパターン「Ｐ．Ｐ．ＰＡ」は、他の位置にもあるが、オフセット１２および１４すなわち、１４ー１２＝２で２＜６なのでオーバーラップする位置に現れる。
【００７６】
探索エンジン相の間に、低複雑性相同性を捕捉し、破棄する方法が２つある。第１は、上で示した例の一般化である。手短に言うと、「言語的に豊か」でない、すなわち、１つの特定のアミノ酸の多数の表現を示すすべてのパターンを破棄したい。その目的のために、ユーザが、パラメータＶ（０と１の間の実数）の値をセットできるようにする。照会配列Ｑに一致するパターンＰは、Ｐの変異性ｖ（Ｐ）が値Ｖを超えない場合に限ってさらに検討される。具体的に言うと、パターンＰのそれぞれについて、その変異性ｖ（Ｐ）を次の形で定義する。
【数５】
0004250339.tif 000006
上で述べた変異性テストに合格した後であっても、第２レベルの検査が続く。この第２レベルは、低複雑性のより捉えにくい概念を捕捉することが目的である。その動作方法を理解するために、次の例を検討されたい。照会タンパクＱが、次の単純な文字列であると仮定する。
Ｑ＝ＦＲＧＤＳＡＡＡＢＢＢＢＡＡＢＢＳＪＩＥＫＬ
また、パターンＰ＝「Ａ．．．Ｂ．．ＡＢ」であると仮定する。このパターンは、下に示すように、オフセット７で照会と一致する。
【表５】
0004250339.tif 000007
一致とその直前および直後の領域は、低複雑性領域である（「Ａ」と「Ｂ」だけからなる）。しかし、パターンＰは、０．５の変異性を有する。この文字の低複雑性領域を扱うために、ユーザが、整数marginおよびｍｉｎ＿ｍ（ｍｉｎ＿ｍ≦２×margin）ならびに比率ｐｅｒｃを定義できるようにする。その後、実際の整合部位（ここでは照会のオフセット７）の左側margin文字と右側margin文字で、検討中のパターン（ここではパターン「Ａ．．．Ｂ．．ＡＢ」）の近似的な一致を検査する。パターンＰが照会の所与のオフセットで近似的に一致するのは、そのオフセットに配置された時に、パターンの通常文字の少なくともｐｅｒｃ％が、下にある照会の文字と一致する場合である。たとえば、ｐｅｒｃ＝７５％の場合、パターン「Ａ．．．Ｂ．．ＡＢ」は、下からわかるように、オフセット６および８でＱに近似的に一致する。
【表６】
0004250339.tif 000008
というのは、これらのオフセットのそれぞれで、パターンの通常文字の７５％（すなわち、４文字のうちの３文字）が、対応する照会文字と一致するからである。パラメータmargin、ｍｉｎ＿ｍおよびｐｅｒｃを定義したことによって、このレベルの検査中に、照会とデータベース領域の間のパターンによって誘導された局所相同性が、低複雑性と見なされる時を言う準備ができた。パターンＰが、照会ＱにオフセットＸで一致し、データベース配列ＳにオフセットＹで一致すると想定されたい。この一致は、（ｉ）パターンが、Ｘの左右２×margin文字のうちの少なくともｍｉｎ＿ｍ文字で近似的に照会Ｑと一致するか、（ｉｉ）パターンが、Ｙの左右２×margin文字のうちの少なくともｍｉｎ＿ｍ文字で近似的に配列Ｓと一致する、のいずれかが真である場合に、低複雑性であるとみなされる。
【００７７】
ＩＩＩ．辞書形成
前に述べたように、好ましい実施例では、探索エンジンがユーザから照会配列を受け取る前に、辞書形成方法論が実行される。これは、もう一度図１を参照すると、探索エンジン・モジュール１１０が、辞書形成モジュール１３０によって形成されたパターン辞書１２０を利用することが好ましいからである。辞書形成モジュール１３０は、下で説明する発明的データベース処理方法論を実施して、パターン辞書（またはバイオ辞書）を形成する。しかし、やはり前に述べたように、パターン辞書１２０を、本明細書に記載のもの以外の探索エンジンが使用することができる。すなわち、既存の探索エンジンが、本発明に従ってソース・データベースからマイニングされたパターンを利用することができる。それにもかかわらず、好ましい実施例によれば、本明細書に記載の発明的方法論に従って形成されたパターン辞書が、やはり本明細書に記載の発明的探索エンジンによって使用されることが仮定される。
【００７８】
辞書形成相（情報収集相とも称する）の間に、検討中のデータベースＤで見つかった有意な＜Ｌ、Ｗ＞パターンのすべての集合Πが決定される。それは、本質的に、本発明を用いてＤを探索してＤの配列の中の隠された関係を発見するデータ・マイニング手順である。要点は、予想されないと考えられる関係に焦点を合わせることであり、その質のおかげで、それらの関係はおそらくは生物学的に適切でもある。本発明の目的のために、パターンの有意性を、Ｄ内でのサポートによって記述する。具体的に言うと、少なくともＫminのサポートを有するすべてのパターンが統計的に重要であることを示すことができる、数Ｋmin（最少サポート）の定義を探す。そのようなパターンのすべて（最少サポート要件を守らない少数の例外と共に）は、集合Πすなわち探索相への入力に含まれる。
【００７９】
Ｋminの概念が、まず「定義」の節で導入されたことを想起されたい。「密度」の概念も導入された。密度は、Ｇ（Ｐ）の２つの要素の間の相同性の最小量を記述し（Ｇ（Ｐ）は、ドント・ケア文字のそれぞれをΣからの任意の残留物によって置換することによってＰから得ることのできるすべての文字列からなるポリペプチドの言語を指す）、２つの整数ＬおよびＷ（Ｌ≦Ｗ）によって定義されることを想起されたい。パターンＰが＜Ｌ、Ｗ＞の密度を有するのは、あるアミノ酸で始まり、終わり、少なくともＷの長さを有するＰのすべての部分列に、Ｌ個以上の残留物が含まれる場合である。やはり、これらのパラメータは、「ＴＥＩＲＥＳＩＡＳ」アルゴリズムを対象とする、上で組み込まれた米国特許出願第０９／０２３７５６号明細書に記載されている。
【００８０】
本発明の好ましい方法論では、パターン辞書Πの形成にパラメータＬおよびＷを使用するが、配列のグループの２つの要素の間の相同性の最小量を判定するための他の既知の技法を使用することができることを諒解されたい。
【００８１】
パラメータＬ、ＷおよびＫminの値の設定には、複数の、時には衝突する、相互に連結された要因の検討が含まれる。たとえば、比Ｌ／Ｗによって、探索相の間に、照会配列とＤのタンパクの間で許容される相同性の量が記述される。Ｌ／Ｗが小さいと、弱い類似性の検出が可能になる。複数の値の対（Ｌ、Ｗ）が同一の比Ｌ／Ｗにつながるので、ＬとＷの正確な設定はどうすべきか？  大きい値のＬの選択は、通常は、情報収集相の長い実行時間をもたらす（Ｌ／Ｗが１に近い場合を除いて）。さらに、大きいＬを選択すると、対象のアミノ酸のうちの少数のアミノ酸だけを有する（すなわち、通常は既存の類似性探索ツールによって見落とされる）弱いパターンが無視される。その一方で、あまりに小さいＬを選択すると（たとえば２または３）、その場合には、入力データベースＤの、Ｌ＋ｉ個の残留物（小さいｉの場合）を有する＜Ｌ、Ｗ＞パターンの分布が、Ｄのアミノ酸組成を有するランダム・データベースの対応する分布との有意な差を有しなくなるので、有用ではない。ほとんどの一般的な場合には、値Ｌ、ＷおよびＫminは、完全に任意に選択することができることを諒解されたい。しかし、発見されるパターンが、統計的雑音のレベルより十分に上であることを実質的に保証するために、統計的枠組みを用いるパターン発見処理（すなわち、上で述べたパラメータを設定する方法）を説明する。
【００８２】
上の点をより明瞭にするために、図１１ないし１４を検討されたい。図１１ないし１４は、SwissProt Rel.34またはＳＰ３４として既知のテスト・データベース（A. BairochおよびR. Apweiler著、「The SWISS-PROT protein sequence data bank and its supplement TrEMBL in 1998」、Nucleic Acids Res.、26:38-42、1998年を参照されたい）のパターンの分布と、対応するランダム分布を比較した図である。図１１ないし１４には、ＳＰ３４の所与のバックボーン構造を有するパターンの分布（この分布は「ｏ」記号によって示される）と、同一のバックボーンのランダム分布（この分布は「＋」記号によって示される）との比較が示されている。バックボーンの概念が、まず上の「定義」の節で導入されたことを想起されたい。曲線上の点（Ｘ、Ｙ）は、正確にＹ個のパターン（所与のバックボーン構造の）があり、これらのパターンのそれぞれが、サポートＸを有する、すなわち、正確にＸ個の別個のデータベース配列に一致することを示す。ここに示した結果は、ＳＰ３４の「クリーンアップ」された版（データベースのクリーン・アップは下で説明する）を使用して得られた。SwissProtについて、正確にＬ個の残留物を有する各＜Ｌ、Ｗ＞パターンのサポートを計算した（図１１ないし１４に示されたＬ、Ｗの値について）。その後、結果を表にし、可能なバックボーンのそれぞれについて１行を作成した。所与のバックボーンＢに対応する行の第ｉ列は、SwissProt内でサポートｉを有する（バックボーン構造の）パターンの数を示す。ランダム分布は、Ｎ＝２０００のランダムにシャッフルされた版のSwissProtについて正確に同一の手法に従うことによって得られた（図１６に、シャッフルされた版のそれぞれを得るのに用いたシャッフル処理が記載されている）。この場合、所与のバックボーンＢの行は、２０００個の表のすべてのＢに対応する行の平均をとることによって得られた。その結果、第ｉ列は、SwissProtの残留物組成を有するランダム・データ・ベース内の正確にｉ個の配列に現れるバックボーンＢ内のパターンの平均数の十分に正確な推定値を与える。図１１ないし１４では、選択されたバックボーンのSwissProt結果を、同一のバックボーンの平均値の分布に対してプロットした。提示される結果には特定のバックボーンが用いられているが、他のバックボーンを使用した場合の質的な変化はない。
【００８３】
２０００個のサンプリング・ポイント（入力データベースのランダムにシャッフルされた版）を使用することに留意されたい。これは、例示のみの目的である。サンプリング・ポイントの実際の数は、一般原則として、任意に設定することができる。一般に、そのようなポイントの数が増えるにつれて、得られる推定値が、その真の値により正確に集束する。計算される推定値の所望の信頼性レベルを与えられれば、標準的な統計理論を使用して、使用するサンプリング・ポイントの数を決定することができる。
【００８４】
図１１ないし１４からわかるように、まず、Ｌが５以上になる時に限って、SwissProtの組成バイアス（パターンに関する）をランダム・データベースに対して区別する。一般に、Ｌの値は、基礎となるデータベースＤのサイズに依存し、データベースが大きいほど、この値を高くしなければならない。SwissProtについて図示されている結果は、値Ｌ＝６を使用して得られた。Ｗについては、値１５を選択し、その結果、比Ｌ／Ｗ（すなわち許容される最小の相同性）は４０％になる。
【００８５】
ＬとＷの値を設定したので、残りは最少サポートＫminの値の決定である。より大きいパターンのすべてに、正確に多数のアミノ酸を有する少なくとも１つの部分パターンが含まれるので、正確にＬ個の残留物を有するパターンだけに焦点を合わせる。１つの手法は、Ｋmin以上の別個の配列にパターンが現れる確率が小さくなるようにＫminを選択することである。しかし、図１４をよく観察すると、この手法が厳密すぎる可能性があることが明らかになる。具体的には、Ｋ＝１５のサポート・レベルを検討されたい。ランダム分布から、偶然だけによって、サポートＫを有する１個と２個の間のパターンが期待されることが示される。したがって、前述の判断基準によれば、SwissProt内でサポート１５を有するパターンは、重要でないとみなされるはずである。しかし、この２つの分布は、そのサポート・レベルでは著しい相違を有する。具体的に言うと、Ｋ＝１５でのランダム分布の平均値は約１．５の値を有するが、SwissProtには、サポート１５を有する約１８０個のパターンがある。
【００８６】
したがって、パターンの確率を分離して検討する場合には、その結果は、上の分布によれば雑音のレベルを超える多数のパターンを無視することになると思われる。この観察から、有意性に関して異なる判断基準を使用することが発案された。
【００８７】
ここで図１５ないし１８を参照すると、有意性判断基準を決定するための好ましい手法を示す流れ図が示されている。すなわち、Ｋminの値を計算するための方法論が提供されている。Ｋminの値を与えられれば、パターン辞書Πは、サポートとして少なくともその値Ｋminを有する、ソース・データベースＤ内のすべてのパターンをそれに含めることによって形成される。したがって、図１の辞書形成モジュール１３０は、図１５ないし１８に示された処理を実行することができることを理解されたい。
【００８８】
一般に、本発明の手法では、個々のパターンを調べるのではなく、特定のバックボーン構造のすべてのパターンを一緒に検討する。具体的に言うと、所与のバックボーンＢと基礎になるデータベースＤに対して、ＮB,Kが、
ＮB,K＝Ｄ内でサポートＫを有する、バックボーンＢを有するパターンの数
であるものとする。また、ＸB,Kが、ＮB,Kに対応するランダム変数（Ｄのすべてのシャッフルされた版の空間上で定義される）であるものとする。最小サポートＫminは、次の不等式が真になる最初の数Ｋである。
【数６】
0004250339.tif 000009
ここで、thresholdは、上の不等式から得られる最小サポートＫminに対する信頼性のレベルを強制する、ユーザ定義の確率である。小さいthresholdは、大きい値のＫminにつながり、最終的に選択されるパターンのより大きい統計的重要性につながる。
【００８９】
したがって、有意性判断基準Ｋminを決定するための処理への入力として、ソース・データベースＤ、整数パラメータＬおよびＷ、サンプルの数を表す整数Ｎ、および、０と１の間の実数であるthresholdがある。もちろん、この処理の出力として、サポートＫmin以上を有するＤ内のすべてのパターンが、統計的に重要になり、したがって、ユーザ照会の受取時に探索されるパターン辞書に含まれるようになる整数Ｋminが得られる。
【００９０】
以下の流れ図の説明では、さまざまな表記が使用されるが、そのうちの一部は上で導入した。しかし、明瞭にするために、以下の定義を適用する。パターンＰに対して、ＰのバックボーンＢ（Ｐ）は、Ｐのすべての通常文字を「１」と置換し、Ｐのすべてのドント・ケア文字を「０」と置換したときに得られる｛１、０｝上の文字列として定義され、たとえばＰ＝Ａ．．Ｆ．Ｇ．．Ｒの場合には、Ｂ（Ｐ）＝１００１０１００１である。Ｂが任意のバックボーンであり、ＰがＢ（Ｐ）＝Ｂになるパターンである場合には、ＰはＢパターンであると言う。その場合、ＮB,Kは、ＤでのサポートＫを有するＢパターンの数と言い、ＸiB,Kは、ｉ番目のランダム・データベースでサポートＫを有するＢパターンの数である。ｍB,Kは、すべてのＸiB,Kの平均であり、ｓB,Kは、すべてのＸiB,Kの分散である。ランダム変数ＸB,Kの分布に関する分析的記述を有しないので、標準的なサンプリング技法を使用することを諒解されたい。したがって、所与のデータベースＤについて、ランダム変数ＸB,Kの平均ｍB,Kと分散（偏差）ｓB,Kの両方について、正確な点推定値を実験的に計算することができる。
【００９１】
まず図１５を参照すると、全体的な処理１２００は、ステップ１２０２で、Ｄに対してＴＥＩＲＥＳＩＡＳアルゴリズム（すなわち、上で組み込まれた米国特許出願第０９／０２３７５６号明細書に記載のアルゴリズム）を走行させ、ＮB,Kを計算することによって開始される。ＴＥＩＲＥＳＩＡＳアルゴリズムが好ましいが、ＮB,Kは、他の従来の技法を使用して計算することができることを理解されたい。その後、ｉ＝１  ｔｏ  Ｎについて（ブロック１２０４）、以下のステップを実行する。
【００９２】
ステップ１２０６で、ランダム・データベースＲ＿Ｄiを生成する。このステップを、図１６に関連してさらに説明する。処理１３００に示されているように、Ｒ＿Ｄi（ブロック１３０２）は、Ｄの配列Ｓのそれぞれについて（ブロック１３０４）、Ｓの文字のランダムな置換を計算する（ステップ１３０６）ことによって生成される。Ｓの文字のランダムな置換を、Ｓ'と称する。Ｓ'は、Ｒ＿Ｄiに追加される（ステップ１３０８）。この処理は、Ｄのすべての配列Ｓが処理されるまで繰り返される（ブロック１３１０）。したがって、Ｒ＿Ｄiには、すべてのランダムな置換Ｓ'が含まれる。図１５に戻って、ステップ１２０８で、ＸiB,Kを計算するためにＲ＿Ｄiに対してＴＥＩＲＥＳＩＡＳを走行させる。ステップ１２０６および１２０８は、すべてのｉに対してすなわち、ｉ＝Ｎになるまで実行される（ブロック１２１０）。
【００９３】
その後、すべてのＢおよびＫについて（ブロック１２１２）、ＸiB,Kを使用してｍB,KおよびｓB,Kを計算する。このステップを、図１７に関連してさらに説明する。処理１４００に示されているように、ｓB,Kには、まず０がセットされる（ステップ１４０２）。その後、ｉ＝１  ｔｏ  Ｎについて（ブロック１４０４）、ｓB,KとＸiB,Kの和としてｓB,Kを計算する（ステップ１４０６）。この処理を、すべてのｉについて繰り返し（ブロック１４０８）、最終的に、ｓB,KをＮで割ることによって、ｓB,Kが計算される（ステップ１４１０）。その後、偏差ｍB,Kを、ステップ１４１２ないし１４２０で計算する。まず、ステップ１４１２で、まずｍB,Kに０をセットする。その後、ｉ＝１  ｔｏ  Ｎについて（ブロック１４１４）、ｍB,Kと（ＸiB,K−ｓB,K）2の和としてｍB,Kを計算する（ステップ１４１６）。この処理を、すべてのｉについて繰り返し（ブロック１４１８）、最終的に、ｍB,KをＮで割ることによって偏差ｍB,Kを計算する（ステップ１４２０）。
【００９４】
図１５に戻って、ステップ１２１６で、ｍB,KとｓB,Kを使ってｐB,Kを計算する。このステップを、図１８に関連してさらに説明する。処理１５００に示されているように、ステップ１５０２で、
【数７】
0004250339.tif 000010
となるように実数Ｃを定義する。ここで、Ｎは、サンプルまたは試行の具体的な数、たとえば２０００を表す。したがって、ステップ１５０４で、１／Ｃ2に等しいものとしてｐB,Kを計算する。ｐB,Kは、確率Ｐｒ［ＸB,K＞ＮB,K］の上界であることを理解されたい。したがって、要約すると、サンプルの平均とＸB,Kの偏差を使用して、考慮中のＮB,Kの値のためのＣを計算する。定数Ｃは、統計の分野で周知の通り、チェビシェフの不等式に関連することを諒解されたい。定数Ｃは、９５％の信頼性レベルを使用して計算されるが、これが必須ではないことに留意されたい。すなわち、他のどのような値でも適用可能である。
【００９５】
図１５に戻って、ステップ１２１４（図１７）および１２１６（図１８）を、すべてのＢおよびＫについて繰り返す。その後、ステップ１２２０で、ｍａｘB｛ｐB,K｝≦thresholdになる最小のＫとして、Ｋminを決定する。次の節で提示するテスト・ケース（SwissProt.Rel.34）では、thresholdの値は、Ｋmin＝１５すなわち、所与のバックボーン構造の１．５パターンだけが偶然によって期待されるサポート・レベルになるように選択された。SwissProt内に存在する同一のサポート・レベルの他のパターンによって暗示されるより多くの統計的に重要な類似性を捕捉することができるようにするために、偶然の結果（上では１．５パターン）になることのできる、少数のパターンによって誘導される局所相同性を許容したいというトレード・オフが存在する。
【００９６】
次の節で実験結果を提供する前に、まず、本発明の辞書形成方法論を実行する前のデータベースのクリーン・アップの概念を説明する。この処理は、図１９に示されており、図１の辞書形成モジュール１３０によって実施することもできる。複数のデータベースに、非常に相同性の高い配列のグループ（たとえば、ヘモグロビンα鎖タンパク）が含まれる。そのようなグループは、膨大な数のパターンを導入することによってパターン発見処理の速度を低下させるだけではなく、パターンの有意性を見掛け上高める可能性もある。これは、非常に相同性の高い配列のファミリ内に何度も現れ、その外部ではほんの時折しか現れないパターンの場合に発生する。
【００９７】
この問題を処理するために、パターン発見処理を開始する前に、データベースＤを「クリーン・アップ」することができる。図１９に示されているように、クリーン・アップ処理１６００には、非常に似たタンパクの識別とグループ化が含まれる（ステップ１６０２）。２つの配列が同一のグループに配置されるのは、最適に位置合せされた後に、短い方の配列の位置のＸ％（たとえば５０％）が、長い方の配列の位置と同一である場合である。結果のグループを、冗長グループと称する。情報収集処理が実行される対象の集合Ｄ'は、（ａ）他のタンパクと十分に相同であることが発見されなかった、Ｄの配列と、（ｂ）冗長グループのそれぞれからの最長の配列からなる（ステップ１６０４）。最後に、冗長グループのそれぞれを、ＴＥＩＲＥＳＩＡＳアルゴリズムによって別々に処理して（ステップ１６０６）、グループのすべての配列がこれらのパターンのうちの少なくとも１つと一致するまでパターンを収集する。この手法では、領域ごとに少なくとも１つのパターンを生成することによって、複数領域タンパクを含むグループであっても正しく扱われることが保証される。冗長グループの処理から生じるパターンは、通常は、非常に密（残留物の数が、ドント・ケア文字の数よりはるかに多くなる）であり、長いことを指摘する価値がある。これは、グループ配列の高い相同性の結果である。そのようなパターンについて、探索相の間の近似的な一致を許容する。
【００９８】
ＩＶ．実験結果
この節では、本発明の好ましい実施例に関連する実験結果を論ずる。すなわち、以下の結果は、上で詳細に説明した、本発明の辞書形成（情報収集）方法論および探索エンジン方法論の両方を、テスト・データベースとしてSwissProt Rel.34に関連して実施することによって生成された。情報収集相で発見されたパターンの定量的および定性的な記述は、下の最初の副節（Ａ）で、これらのパターンがSwissProtに関した達成したカバレッジを分析することと、それらの最も頻繁な発生に注釈を付けることによって与える。下の第２の副節（Ｂ）では、複数の照会配列に対する探索相の結果を提示する。
【００９９】
Ａ．情報収集
SwissProtの処理は、前の節で説明したクリーン・アップから始まる。この処理の結果を、図２０に詳細に示す。SwissProtに対するクリーンアップ処理では、非常に類似性の高い配列の９１６５個の冗長グループが生成される。クリーンアップされたデータベース（情報収集相の操作対象になるデータベース）は、元の入力から非常に類似した配列を除去し、各冗長グループから最長の配列を追加することによって結果の集合を増補することによって形成される。
【０１００】
クリーン・アップされたデータベースを使用可能にした後に、それに対してＴＥＩＲＥＳＩＡＳを使用できるようにするために必要なことは、パラメータＬ、ＷおよびＫminの値の設定である。すでに説明したように、Ｌ＝６およびＷ＝１５の設定を使用する。さらに、ここで報告する結果では、偏差の計算で、１０-11のthreshold値と９５％の信頼性レベルを選択した。この設定について計算されたＫminの値は、１５になることがわかった。上で指定したＬ、ＷおよびＫminの値を用いて、クリーンアップされたデータベースに対してＴＥＩＲＥＳＩＡＳを走行させることによって、５３４１８５パターンの集合Π（パターン辞書）が生成された。
【０１０１】
クリーンアップされたデータベースのマイニングは、情報収集相の第１ステップにすぎない。９１６５個の冗長グループに対してパターン発見処理を適用することも必要である。やはり、ＴＥＩＲＥＳＩＡＳを使用して、そのようなグループのそれぞれを処理し、グループの各配列が少なくとも１つのパターンと一致することを確実にするのに十分な＜６、１５＞パターンを収集する。これらのパターンは、その後、探索相によって使用される最終的なパターンの集合Πを形成するために、集合Πに追加される。図２１に、SwissProt Rel.34全体に対してこれらのパターンによって達成されたカバレッジに関する情報を示す。パターンによって「カバー」されるデータベース領域は、正確に、そのパターンに一致する部分列である。密で長いパターン（ほとんどは冗長グループの処理からもたらされる）について、近似的な一致が許容され、パターンの「ほとんど」（具体的にはパターンの残留物の８０％）が、領域に一致することに留意されたい。カバーされない配列のほとんどが、断片であることを指摘する価値がある。具体的に言うと、２３１個だけが、５０を超えるサイズを有する。図２２および２３に、（ｉ）SwissProt Rel.34パターンの長さと、（ｉｉ）アミノ酸または残留物の数という、Πのパターンの特性に関する分布を示す。
【０１０２】
図２１に例示したように、探索相の成功が後に続くための主要な目標の１つ（すなわち、SwissProtのよい集束）が、達成された。解かなければならない残りの問題は、発見されたパターンが生物的に適切であるかどうかである。これに対処するための労力において、これらのパターンの間で最も頻繁に発生するものを分析した。結果の注釈を、図２４および２５に示す。この分析から、パターン発見処理が、生物学的に重要な配列特徴を識別することは（少なくとも試験されたパターンについて）明白である。
【０１０３】
図２４および２５には、最も高いサポートを有する１００個のパターンが示されている。可能な場合には、カテゴリ内のパターンを互いに位置合せした。小文字の斜体は、便宜上使用されたものであり、以下の括弧付きの表現のプレースホルダである。すなわち、ａ：［ＳＴＧＤＡＲ］、ｂ：［ＳＴＧＤＫ］、ｃ：［ＳＴＧＤＫＹ］、ｄ：［ＳＴＧＫ］、ｅ：［ＧＡＳＭＤＬ］、ｆ：［ＧＩＳＥＴＶ］、ｇ：［ＬＩＶＭＦＹ］、ｈ：［ＬＩＶＭＦ］、ｉ：［ＬＩＶＭＡ］、ｊ：［ＬＩＶＭＣ］、ｋ：［ＬＩＶＭＦ］、ｌ：［ＩＬＶＭＦ］、ｍ：［ＱＫＣＳ］、ｎ：［ＫＲＱＡ］、ｏ：［ＩＶＴＮＦ］、ｐ：［ＱＫＣＡＳＮ］、ｑ：［ＱＫＩＡＧＮ］、ｒ：［ＲＫＡＨＱＮ］、ｓ：［ＫＲＱＮＥ］、ｔ：［ＫＲＱＭＮ］、ｕ：［ＬＦＹＩＭＳ］、ｖ：［ＡＧＳＰＥ］。括弧は、括弧内の残留物のうちのいずれか１つによって占められる可能性がある位置を示す。
【０１０４】
発見されたパターンのすべてが、そのような明瞭な機能的特異性を示すわけではないことを諒解されたい。発見されたパターンのうちのいくつかは、少なくともタンパクの機能的注釈の目的には重要でないと従来考えられていた領域（たとえばループ、コイルドコイル、膜貫通）に対応する。しかし、時には、そのような弱い類似性であっても、タンパク領域の特性記述の有用なヒントを提供する可能性がある。この可能性を利用できるようにする機構を２つ実施した。まず、ユーザは、照会配列に一致するすべてのパターンのリストを与えられる。専門家のユーザは、ほとんどの場合に、どのパターンが生物学的に重要であるかを識別することができる。特定のパターンを選択すると、スコアリングが改善され、このパターンによってカバーされるデータベースの区域だけに焦点を合わせるようになる。第２に、基礎になるデータ・ベースに、さまざまなデータベース配列領域の注釈が含まれる時には、有用な情報を抽出するために、この注釈をパターンと併用する。これら２つの機構の使用の例を、次の副節で示す。
【０１０５】
Ｂ．探索
探索相を例示する（および、それを使用する方法を説明する）ために、２つの照会配列を選択した。第１の配列は、十分に調査され、注釈を付けられたコア・ヒストン３タンパク（SwissProt ID:H31_HUMAN）であり、第２の配列は、まだ特徴を明らかにされていない、Methanococcus JannaschiiのＯＲＦ（SwissProt ID:YZ28_METJA）である。
【０１０６】
Ｈ３１＿ＨＵＭＡＮ
コア・ヒストンは、細胞内のＤＮＡのパッケージングにおける中心的な役割に起因して、広範囲の研究の対象になってきた。これらの小さいタンパクは、負に帯電したＤＮＡ二重螺旋への結合を助ける正に帯電したアミノ酸に富む。J.D. Watson、N.H. Hopkins、J.W. Roberts、J. SteitzおよびA.M. Weiner著、「Molecular Biology of the Gene」、The Benjamin/Cummings Publishing Company刊、Fourth Edition、1987年を参照されたい。４つのコア・ヒストン（Ｈ２Ａ、Ｈ２Ｂ、Ｈ３およびＨ４）は、互いに結合して八量体構造（円筒形のくさびを思わせる）になり、これが、１４６ｂｐｓ長のＤＮＡセグメントが巻き付く基質をもたらし、したがって、細胞クロマチン内のヌクレオソーム複合体を作る。
【０１０７】
SwissProt Rel.34データベースには、Histones 3として注釈される３３個の配列があり、その中に、ヒトに見られるコア・ヒストン３タンパクであるＨ３１＿ＨＵＭＡＮが含まれる。本発明による相同性検出ツールを用いるこの配列の探索の上位スコア結果を、図２６の表に示す。各配列の隣に、その配列とＨ３１＿ＨＵＭＡＮの間での最高のスコアの局所位置合せの類似性スコアを示す。図２６のスコアは、ＰＡＭ１３０行列（M.O. Dayhoff、R.M. SchwartzおよびB.C. Orcutt著、「A model of evolutionary change in proteins」、Atlas of Protein Sequence and Structure、5:345-352、1978年を参照されたい)を使用して得たものであり、データベースからの一致する配列のすべてに、最も高いスコアを有するセグメントのスコアが割り当てられている。
【０１０８】
SwissProt Rel.34の３３個のコアHistones 3のすべてが、Ｈ３１＿ＨＵＭＡＮに対する相同性を有するものとして正しく同定された。さらに、複数の他のタンパク（ＹＢ２１＿ＣＡＥＥＬ、ＣＥＮＡ＿ＨＵＭＡＮ、ＣＳＥ４＿ＹＥＡＳＴ、ＹＬ８２＿ＣＡＥＥＬ、ＣＥＮＡ＿ＢＯＶＩＮ、ＹＭＨ３＿ＣＡＥＥＬ）が、Ｈ３１＿ＨＵＭＡＮとの示量的局所類似性を有することがわかった。これらのタンパクに関する注釈の観察から、それらが既知のヒストン３様タンパクであることが示される。最後に、Ｈ３＿ＮＡＲＰＳ（既知のヒストン３）は、断片としてのみSwissProtのリリース３４に現れ、それが、結果のリストでＨ３＿ＮＡＲＰＳが最低のスコアを有する理由である。
【０１０９】
図２７に、照会配列Ｈ３１＿ＨＵＭＡＮについて生成された位置合せの選択された表示（高スコアと低スコアの両方の）を示す。図２７では、非常に類似するタンパク（Ｈ３＿ＹＥＡＳＴ）と適度に類似するタンパク（ＣＥＮＡ＿ＨＵＭＡＮ）とのＨ３１＿ＨＵＭＡＮの局所位置合せが示されている。すべての配列について、複数の局所類似性が報告されている。そのような類似性のすべてにおいて、関連する照会領域（「Query」）とデータ・ベース配列領域（「Seq」）は、結果の一致領域を間に挟んで上下にリストされている。文字「＋」を使用して、化学的に類似するアミノ酸を示す。
【０１１０】
ＹＺ２８＿ＭＥＴＪＡ
Ｈ３１＿ＨＵＭＡＮは、それに対する非常に高い相同性を有する複数の配列がデータベースに含まれるので、ある意味では簡単なテスト・ケースである。興味深い質問は、「ボーダーライン」配列すなわち、既知の相同性が存在しない配列を提示された時に、本発明の方法論がどうなるかである。この質問に対処する労力において、システムに、まだ注釈を付けられていない、M. jannaschiiの遺伝子からの１２７２個の残留物を有する開いた読み枠である配列ＹＺ２８＿ＭＥＴＪＡを提示した。
【０１１１】
照会配列ＹＺ２８＿ＭＥＴＪＡを提示された時に本発明のシステムによって作られた最高スコアの位置合せを、図２８に示す。使用された変異行列は、ＰＡＭ１３０である。
【０１１２】
ＹＺ２８＿ＭＥＴＪＡの機能的注釈の目的のためには、上で述べた結果は、非常に啓発的ではない。というのは、データベース・ヒットに全く異なるタンパクが含まれるからであり、最初の２つのタンパク（ＮＴＮＯ＿ＨＵＭＡＮ、ＮＴＮＯ＿ＢＯＶＩＮ）は、ナトリウム依存のノルアドレナリン輸送体であり、最後の１つ（ＫＡＰＬ＿ＡＰＬＣＡ）は、キナーゼである。
【０１１３】
これらの質問を念頭において、ＹＺ２８＿ＭＥＴＪＡとデータベースの配列の間の類似性の詳細な検査に進んだ。この分析のために、ＹＺ２８＿ＭＥＴＪＡに一致するすべてのパターンを、個別に細かく調べた。本発明の探索相では、ユーザが、考慮中の照会配列と照合されるパターンを選択でき、その特定のパターンだけによって誘導される局所位置合せに焦点を合わせ、他のパターンのすべてを無視することができることを諒解されたい。この機能が、ＹＺ２８＿ＭＥＴＪＡによって照合されるパターンのそれぞれについて使用された。本発明は、そのようなパターンが１特定のタンパク・ファミリに固有であるかどうかを発見し、したがって、ＹＺ２８＿ＭＥＴＪＡの機能性に関するいとぐちを与えるためのものである。
【０１１４】
判明したところによれば、キナーゼ・ファミリに非常に固有の３つのパターン（すなわち、パターン「Ｙ．．Ｓ．．Ｉ．．．ＤＬＫ」、「ＮＩＬ．．．．．．ＩＫＬ」および「Ｉ．Ｈ．ＤＬＫ．．．．．．Ｄ」）が存在する。図２９に、これらのうちの最初の１つについて作られた最高のスコアを有する位置合せのうちのいくつか、すなわち、パターン「Ｙ．．Ｓ．．Ｉ．．．ＤＬＫ」によって誘導される、照会配列ＹＺ２８＿ＭＥＴＪＡに関する最高のスコアを有する局所位置合せを示す。使用された変異行列は、ＰＡＭ１３０である。図３０に、その特定のパターンを含むデータベース配列のすべての完全なリストが含まれる。図３１および３２に、残りの２つのパターンの対応するリストを示す。図３３は、（ａ）ＹＺ２８＿ＭＥＴＪＡに一致するすべてのパターンの分布と、（ｂ）３つのキナーゼ固有のパターンによってカバーされる区域とのグラフィック表現である。
【０１１５】
パターン「Ｙ．．Ｓ．．Ｉ．．．ＤＬＫ」は、SwissProt内で２４ヒットを生成する。これらのタンパクのすべて（ナトリウム／胆汁酸共輸送体であるＮＡＢＡ＿ＲＡＴを除く）が、大多数がセリン／スレオニン・キナーゼ・ファミリに属するか、それに対する類似性を示す、タンパク質キナーゼ（そのうちの２つ「ＫＤ８２＿ＳＣＨＰＯ」と「ＫＫＫ１＿ＹＥＡＳＴ」は、推定上／有望なキナーゼとして特徴を表される）として注釈されている。さらに、「Ｙ．．Ｓ．．Ｉ．．．ＤＬＫ」は、これらのタンパクのキナーゼ領域に属するだけではなく、実際にその領域の活性部位（アミノ酸Ｄ）を含む。
【０１１６】
図３０に、パターン「Ｙ．．Ｓ．．Ｉ．．．ＤＬＫ」を含むSwissProt Rel.34配列が示されている。これらのすべてが、タンパク質キナーゼまたは推定上の／有望なタンパク質キナーゼ（ほぼすべてがセリン／スレオニンの変種）として注釈されている。唯一の例外が、ナトリウム／胆汁酸共輸送体として注釈されているタンパク「ＮＡＢＡ＿ＲＡＴ」である。
【０１１７】
図３１に示されているように、同様の結果が、３つのパターンのうちの第２のパターンである「ＮＩＬ．．．．．．ＩＫＬ」について得られた。この場合、データベース・ヒットの数は３４であり、そのすべて（YeastとMycoplasma Hominisからの注釈されていない２つのＯＲＦを除く）が、既知の（または有望な）タンパク質キナーゼである。やはり、セリン／スレオニン・キナーゼが大多数である。
【０１１８】
最後に、第３のパターン「Ｉ．Ｈ．ＤＬＫ．．．．．．Ｄ」は、３０個のSwissProt Rel.34ヒットを生成し、そのすべてが、既知のまたは推定上のタンパク質キナーゼである。これを図３２に示す。さらに、３つのパターンのうちの第１のパターンの場合と同様に、パターン「Ｉ．Ｈ．ＤＬＫ．．．．．．Ｄ」には、キナーゼ領域の活性部位が含まれる。
【０１１９】
前述の３つのパターンのすべてが、以下の一般的なパターンの特定の実例（一部）であることに留意することが興味深い。
[LIVMFYC].[HY].D[LIVMFY]K..N[LIVMFYCT][LIVMFYCT][LIVMFYCT]
ここで、表記［ＸＹＺ］は、残留物Ｘ、ＹおよびＺのいずれかによって占められる可能性がある位置を示す。このより一般的なパターンは、受入番号ＰＳ００１０８を有するＰＲＯＳＩＴＥデータベース項目すなわち、セリン／スレオニン・タンパク質キナーゼ活性部位のサインである。このＰＲＯＳＩＴＥサインは、上で試験した３つのパターンによってカバーされるＹＺ２８＿ＭＥＴＪＡの区域内のキナーゼ触媒部位を選択するためには具体的にすぎることに留意されたい。この状況（人工知能の用語で、トレーニング・セットの「オーバーリプリゼンテーション（overrepresentation）」として既知）は、全宇宙の有限な部分集合によってトレーニングされた学習システムに典型的なものである。実例の集合（この場合、ＰＲＯＳＩＴＥによって使用される既知のセリン／スレオニン・キナーゼの特定の集合）が偏っており、その結果、観察を説明する間に学習される特徴（この場合はキナーゼのサイン）が、検討中のファミリの新しい実例に効果的に外挿するのに十分に一般的でない（すなわち、「誤った否定（false negatives）」がある）危険性が常に存在する。この問題の矯正法は、できる限り大きいトレーニング・セットを使用することであり、これが、本明細書に提示される手法の最重要点である。
【０１２０】
前に述べたように、図３３には、（ａ）ＹＺ２８＿ＭＥＴＪＡに一致するすべてのパターンの分布と、（ｂ）３つのキナーゼ固有パターンによってカバーされる区域のグラフィック表現が示されている。
【０１２１】
図３３の（ａ）には、ＹＺ２８＿ＭＥＴＪＡと一致する４１０個のパターンがある（情報収集相で発見されたパターンのうちの）。パターンが残留物位置を「カバー」するのは、パターンがその位置またはその前から始まり、その位置またはその後で終わる場合である。グラフには、残留物位置（ｘ軸）のそれぞれについて、その位置をカバーするパターンの数（ｙ軸）が示されている。図３３（ｂ）からわかるように、本明細書で論じた３つのキナーゼ・パターンは、オフセット３５（パターン「Ｙ．．Ｓ．．Ｉ．．．ＤＬＫ」）、１１２（パターン「ＮＩＬ．．．．．．ＩＫＬ」）および１０５２（パターン「Ｉ．Ｈ．ＤＬＫ．．．．．．Ｄ」）で配列に一致する。これらのオフセットは、図３３（ａ）のパターン分布のスパイクに対して相対的に図示されている。
【０１２２】
既存の注釈の使用
ＹＺ２８＿ＭＥＴＪＡと一致した４１０パターンのうちで、上で分析した３つのパターンだけが、そのような明瞭な機能的特異性を示す。これは、残りの４０７パターンが有用でないことを意味するものではない。２つの配列の局所類似性から引き出すことのできる生物学的推論の種類は、必ずしも機能的性質を有するものではない。時には、相同性が、構造の保存を示し、別の場合には、相同性が、比較される配列の総合的機能の指示的役割（たとえばＤＮＡ結合領域）の機能単位に対応する場合がある。そのような弱い類似性を調査する労力において、基礎となるデータベースで使用可能な注釈を利用する方法を設けた。下の説明では、SwissProt注釈フォーマットを前提とする。
【０１２３】
SwissProtデータ・ベースでは、その配列の大半と、配列領域の注釈が関連付けられる（ＦＴ行、A. BairochおよびR. Apweiler著、「The SWISS-PROT protein sequence data bank and its supplement TrEMBL in 1998」、Nucleic Acids Res.、26:38-42、1998年を参照されたい）。通常の領域記述は次のようになる。
FT  DOMAIN   528   779   PROTEIN KINASE
ここで、キーワード「ＦＴ」は、これが領域記述行であることを示し、残りの行は、その先頭位置および末尾位置（関連するデータ・ベース配列の残留物５２８から残留物７７９まで）とその注釈（タンパク質キナーゼ領域）を与えることによって、その領域を記述する。
【０１２４】
パターンＰを提示された時に、（すでに述べたように）オフセット・リストＬD（Ｐ）を使用して、Ｐと一致するデータベース内のすべての配列を突きとめることができる。Ｓがそのような配列であり、Ｓ内のオフセットｊから、Ｐと一致する部分列が始まると仮定する。Ｐが、Ｓの注釈付きの領域（全体的または部分的のいずれか）に含まれる場合には、この領域をＰに関連付けることができる。Ｐに一致するすべての配列Ｓに関してこの処理を実行すると、Ｐに関連する領域の集合ＲＳD（Ｐ）がもたらされる。図３４に、上で説明した３つのキナーゼ・パターンのうちの１つについて本発明のシステムによって作られた出力の一部の例を示す。すなわち、図３４は、パターン「Ｉ．Ｈ．ＤＬＫ．．．．．．Ｄ」に一致するデータベース配列の一部の、SwissProtの注釈を使用する個々のパターンの分析を示す。そのような配列のすべてについて、そのＩＤ行とＤＥ行が報告され（A. BairochおよびR. Apweiler著、「The SWISS-PROT protein sequence data bank and its supplement TrEMBL in 1998」、Nucleic Acids Res.、26:38-42、1998年を参照されたい）、配列のSwissProt名と、その機能性の短い記述が与えられる。その次に、一致が始まる配列内のオフセットがある。最後に、パターンによってカバーされる領域との交差を有する、注釈付きの領域のすべてのＦＴ行がある。
【０１２５】
照会配列Ｑの部分配列Ａに一致するパターンＰを与えられた場合、問題は、Ａの特徴を表す際にＲＳD（Ｐ）を使用する方法になる。複数の手法を使用することができる。たとえば、ＲＳD（Ｐ）が十分に大きく、その要素の大多数が、機能性で一致する場合には、Ａが同一の機能性を有する可能性が非常に高いと推論することができる。もう１つの検討事項は、パターンＰと、ＦＴ行によって記述される領域の相対的な長さである。たとえば、パターンＰが、１５残留物の広がりを有し、Ｐを含む注釈付きの配列領域が、３００アミノ酸の長さを有する場合には、その領域の注釈をＰに転送しようと思う者はいないであろう。結論として、エンド・ユーザは、システムによって提供される情報を最もよく利用する方法を決定する際に、自分の専門知識を適用することが期待される。
【０１２６】
図３５は、ＹＺ２８＿ＭＥＴＪＡの領域に注釈を付けるために集合ＲＳD（Ｐ）を使用し、したがって、図３３（ｂ）に示された絵を拡張するための、２つの方法を示す図である。すなわち、図３５には、ＹＺ２８＿ＭＥＴＪＡのさまざまなセグメントの、これらのセグメントと一致するパターンの注釈からの特徴の記述が示されている。パターンの注釈は、やはりこれらのパターンに一致するデータベース配列のさまざまな領域について使用可能な情報を利用することによって得られる。セグメントは、やはり、ＹＺ２８＿ＭＥＴＪＡ全体に対するパターンの分布のスパイクに対して相対的に示されている。最初の手法（図３５の（ｂ））では、（ｉ）ＲＳD（Ｐ）のサイズが少なくとも１５であり、（ｉｉ）ＲＳD（Ｐ）内の領域の大多数（８０％）がＸとして注釈を付けられており、（ｉｉｉ）Ｘとして注釈を付けられたＲＳD（Ｐ）のすべての領域のうちの少なくとも５０％が、Ｐによってカバーされる場合に、注釈Ｘ（たとえばＸ＝膜貫通領域）をパターンＰに割り当てる。第２の手法（図３５の（ｃ））では、上の必要条件（ｉ）および（ｉｉ）を共用するが、パターンによってカバーされる注釈付き領域の比率を３０％以上とすることによって、（ｉｉｉ）を緩和している。
【０１２７】
性能
照会配列Ｑの相同性探索の実行時間は、（ｉ）使用されるパターンの集合Πのサイズと、（ｉｉ）Ｑとデータベース配列の間の局所類似性（Ｑに一致するパターンによって誘導される）の実際の数とに依存する。本明細書で使用したSwissProt Rel.34の場合、約１０００個の残留物のサイズの照会タンパクに関する典型的な探索は、２５６ＭＢのメモリを有するPentium 266MHzコンピュータで４ないし６秒を要する。上で報告した実行時間は、すべてのプログラム・データ（パターンとそのオフセット・リスト）をメモリ内に保持することによって達成されたことに言及する必要がある。SwissProtの場合、このデータは、約２００ＭＢを占める。
【０１２８】
本発明のさまざまな態様によれば、基礎となるタンパクのデータベースＤに対するパターンの発見と、照会配列と考慮中のデータベースのタンパクとの間の相同性の識別のためのこれらのパターンの使用とに基づく配列類似性探索を実行するための方法論が提供される。本明細書では、統計的な議論を使用して、探索されるパターンの集合を正確に定義する方法を説明し、メモリを統計的計算に導入することによって有意な相同性を識別する際の感度をパターンによって高める方法を述べた。最後に、本方法論の使用を、テスト・ベッドとしてSwissProt Rel.34データベースを使用して示し、本システムを照会配列の注釈付けに使用する方法を示した。これに関連して、照会配列とデータ・ベース配列の間の弱い類似性の特徴記述に向かって、基礎となるデータベースの注釈と共に発見されたパターンを利用する可能性も論じた。
【０１２９】
有利なことに、本発明の配列相同性検出システムの、従来技術のパターン・ベースの相同性検出用ツール（たとえばＢＬＯＣＫＳ）とそれを区別する１態様は、使用されるパターンの集合の完全性である。パターンは、基礎となるデータベースＤ内のすべてのタンパクの、非常に大きいトレーニング・セットから監督されない形で学習される。配列を同一のファミリの要素とみなさ「なければならない」従来の偏りを生じる前提はない。その結果、発見されるパターンは、より敏感であることが期待される。さらに、別個の機能性を持つ配列を一緒に検討することによって、ファミリの境界をまたぐ弱い類似性（たとえば、膜貫通領域を記述したパターン）を発見することができる。そのような類似性は、機能的注釈の推論には不十分であるが、それでも、検査中の照会配列の異なる部分の役割に関する有用な情報を与える。
【０１３０】
本発明のシステムのもう１つの長所は、相同性探索について達成される実行時間である。すべての探索についてデータベース全体を走査するのではなく、パターンを使用することによって得られる速度向上は、遺伝子データベースのサイズの増大がさらに速くなるにつれて（特に、公開サーバを使用するのではなく、インハウス・テストを走行したいユーザにとって）１つの要因になる。
【０１３１】
本発明の実施例を、添付図面を参照して本明細書で説明したが、本発明がこれらの正確な実施形態に制限されず、本発明の範囲または主旨から逸脱せずに、当業者がさまざまな他の変更および修正を行うことができることを理解されたい。
【図面の簡単な説明】
【図１】  本発明の実施例による、配列相同性検出システムのブロック図である。
【図２】  本発明の配列相同性検出システムの例のハードウェア実施形態のブロック図である。
【図３】  本発明の配列相同性検出システムのネットワークベースの実施形態のブロック図である。
【図４】  本発明の１実施例による、探索エンジン方法論を示す高水準流れ図である。
【図５】  本発明の１実施例による、所与の照会配列のためのパターン照合処理の例を示す図である。
【図６】  本発明の１実施例による、特定の照会配列について生成されるハッシュ・テーブルの例を示す図である。
【図７】  本発明の１実施例による、所与の照会配列に関する連鎖処理の例を示す図である。
【図８】  本発明の１実施例による、所与の照会配列に関するスコアリング処理に従って生成される重みつき有向グラフの例を示す図である。
【図９】  本発明の探索エンジン方法論の照合および連鎖相の実施形態を示す流れ図である。
【図１０】  本発明の探索エンジン方法論のスコアリング相の実施形態を示す流れ図である。
【図１１】  ＳＰ３４での所与のバックボーン構造を有するパターンの分布と、同一のバックボーンのランダム分布との比較を示す図である。
【図１２】  ＳＰ３４での所与のバックボーン構造を有するパターンの分布と、同一のバックボーンのランダム分布との比較を示す図である。
【図１３】  ＳＰ３４での所与のバックボーン構造を有するパターンの分布と、同一のバックボーンのランダム分布との比較を示す図である。
【図１４】  ＳＰ３４での所与のバックボーン構造を有するパターンの分布と、同一のバックボーンのランダム分布との比較を示す図である。
【図１５】  本発明の１実施例による辞書形成方法論を示す流れ図である。
【図１６】  本発明の１実施例による辞書形成方法論を示す流れ図である。
【図１７】  本発明の１実施例による辞書形成方法論を示す流れ図である。
【図１８】  本発明の１実施例による辞書形成方法論を示す流れ図である。
【図１９】  本発明の１実施例による、データベース・クリーン・アップ処理を示す流れ図である。
【図２０】  本発明に関連する実験結果を示す図である。
【図２１】  本発明に関連する実験結果を示す図である。
【図２２】  本発明に関連する実験結果を示す図である。
【図２３】  本発明に関連する実験結果を示す図である。
【図２４】  本発明に関連する実験結果を示す図である。
【図２５】  本発明に関連する実験結果を示す図である。
【図２６】  本発明に関連する実験結果を示す図である。
【図２７】  本発明に関連する実験結果を示す図である。
【図２８】  本発明に関連する実験結果を示す図である。
【図２９】  本発明に関連する実験結果を示す図である。
【図３０】  本発明に関連する実験結果を示す図である。
【図３１】  本発明に関連する実験結果を示す図である。
【図３２】  本発明に関連する実験結果を示す図である。
【図３３】  本発明に関連する実験結果を示す図である。
【図３４】  本発明に関連する実験結果を示す図である。
【図３５】  本発明に関連する実験結果を示す図である。
【図１】
0004250339.tif 000015
【図２】
0004250339.tif 000016
【図３】
0004250339.tif 000017
【図４】
0004250339.tif 000018
【図５】
0004250339.tif 000019
【図６】
0004250339.tif 000020
【図７】
0004250339.tif 000021
【図８】
0004250339.tif 000022
【図９】
0004250339.tif 000023
【図１０】
0004250339.tif 000024
【図１１】
0004250339.tif 000025
【図１２】
0004250339.tif 000026
【図１３】
0004250339.tif 000027
【図１４】
0004250339.tif 000028
【図１５】
0004250339.tif 000029
【図１６】
0004250339.tif 000030
【図１７】
0004250339.tif 000031
【図１８】
0004250339.tif 000032
【図１９】
0004250339.tif 000033
【図２０】
0004250339.tif 000034
【図２１】
0004250339.tif 000035
【図２２】
0004250339.tif 000036
【図２３】
0004250339.tif 000037
【図２４】
0004250339.tif 000038
【図２５】
0004250339.tif 000039
【図２６】
0004250339.tif 000040
【図２７】
0004250339.tif 000041
【図２８】
0004250339.tif 000042
【図２９】
0004250339.tif 000043
【図３０】
0004250339.tif 000044
【図３１】
0004250339.tif 000045
【図３２】
0004250339.tif 000046
【図３３】
0004250339.tif 000047
【図３４】
0004250339.tif 000048
【図３５】
0004250339.tif 000049