(57)【要約】シーケンス配列とシーケンス・データベース類似検索が、バイオ情報科学において最も重要でチャレンジングなタスクの内にあり、そしてたんぱく質関数予測を含むいくつかの目的のために用いられる。ＳＩＭＤ（単一インストラクション、多重データ）技術の形で並列処理を用いるスミス−ウォターマンのシーケンス配列アルゴリズムの効率的な並列処理が呈示される。その方法は、インテルの最新のマイクロプロセッサに埋め込まれるＭＭＸ（マルチメディア拡張）およびＳＳＥ（ストリーミングＳＩＭＤ拡張）技術を用いる実装であるが、しかしその方法はまた、他の最新のマイクロプロセッサに存在する同様の技術を用いて実装することもできる。最適化された８通りの並列処理アプローチのこれまで達成された最速のものに関して８倍近くのスピードアップが、同じハードウェアに非並列のスミス−ウォターマンを実装することで認められる。毎秒約２億個のセルの更新というスピードが、単一の５００ＭＨｚのインテル・ペンティアム　ＩＩＩ（Ｒ）マイクロプロセッサで得られている。
2004510265.tif 000002
【特許請求の範囲】
【請求項１】
それぞれがＭ個およびＮ個の要素の２つの生物学上のシーケンスＡとＢとの間のスミス−ウォターマン最適局部配列類似スコアを測定し、長さＭの前記１つのシーケンスＡと長さＮの前記１つのシーケンスＢとの比較に対応するＭ×Ｎの要素のスミス−ウォターマン行列および置換スコア値行列Ｚにおける値、ならびに開放罰金ギャップｑとギャップ拡張罰金ｒとを計算することによって、２つの生物学上のシーケンスが進化論的に関係するか否かまたはどれだけ近く関係するかを同定するために、それらの類似を測定する方法であって、
前記１つのＭ×Ｎ行列の同じ行または列で連続して位置するＫ個の要素にＫ個の要素のベクトルが対応する前記Ｋ個のベクトル要素を用いて前記１つのＭ×Ｍ行列における値を計算する
ステップを備える方法。
【請求項２】
前記１つのベクトルにおける前記Ｋ個の要素のいずれか１つの値の計算が、前記１つのベクトルの前のＫ−１個の要素のいずれかの値または前のベクトルの要素の値に依存するかどうかを調査するステップが、
依存性が検出されないならばベクトルの方向における潜在的なギャップを考慮することなく正しいベクトル要素値を計算し、そして
依存性が検出されるならばベクトルの方向における潜在的なギャップを考慮することによって正しい値を続けて計算する
ステップを更に備える請求項１に記載の方法。
【請求項３】
前記依存性の測定を行うステップが、
前記１つのベクトルの方向のシーケンスにおける潜在的なギャップから結果として得ることができていたはずの効果を無視することによって、前記ベクトルのＫ個の要素について最初のスコア値を計算し、そして
前のベクトルの最後の要素または前記最初の値の最後以外のいずれかが、ギャップ開放罰金パラメータとギャップ拡張罰金パラメータとの和として形成される制限を超えるか否かチェックすることによって依存が可能か否か測定する
ステップを更に備える請求項２に記載の方法。
【請求項４】
前記１つのベクトルのＫ個の要素の最後のスコア値を測定するステップが、
依存性が検出されないならば、前記計算された最初のスコア値を最後のスコア値として用い、および
依存性が検出されるならば、可能なギャップを考慮して依存するベクトル要素を連続して再計算する
ステップを更に備える請求項３に記載の方法。
【請求項５】
前記Ｋ個の要素に前記同時演算における非負値および符号の付かない算数のみを適用することによって前記Ｋ個の要素の１つを表す蓄積要素の値の最大範囲を用い、開始値が負であるならばバイアスを加え、前記１つのＫ要素を蓄積する要素における負の値を最大に表す絶対値に等しいバイアスを用いて後に同じバイアスを減算し、それによって、Ｋ個の要素の各々の値を表すのに必要である最小の蓄積量を用い（または、要素の最大数を蓄積スペースの固定量内で表すことを可能とし）、そしてそれによって、スミス−ウォターマンの計算における反復を可能な限り少なくする
ステップを更に備える請求項１乃至４に記載の方法。
【請求項６】
オーバーフローが生じたことを認識することによって、前記１つのＫ要素を表す１つの蓄積要素における前記演算の算数においてオーバーフローを取り扱い、そしてそれによって前記１つのＫ要素を表す蓄積要素におけるより大きな値の範囲を取り扱うよう演算を繰り返す
ステップを更に備える請求項１乃至５に記載の方法。
【請求項７】
値を調整する飽和算数を前記１つのＫ要素を表す蓄積要素の値を最大に表すことに適用し、それが、そのデータ型のオーバーフローが起こるときであることによって、前記算数演算におけるオーバーフローを検出し、それによって、前記１つの蓄積要素のこの最大値を認識することでオーバーフローを検出する
ステップを更に備える請求項６に記載の方法。
【請求項８】
ＭおよびＮ要素それぞれの２つの生物学上のシーケンスＡとＢとの間のスミス−ウォターマン最適局部配列類似スコアを測定するコンピュータ・インストラクションを含み、長さＭの前記１つのシーケンスＡと長さＮの前記１つのシーケンスＢとの比較に対応するＭ×Ｎ要素のスミス−ウォターマン行列および減算スコア値行列Ｚにおける値ならびに開放罰金ギャップｑおよびギャップ拡張罰金ｒを計算するコンピュータ読み取り可能装置であって、
前記１つのＭ×Ｎ行列の同じ行または列で連続して位置するＫ個の要素にＫ個の要素のベクトルが対応する前記Ｋ個のベクトル要素を用いて前記１つのＭ×Ｍ行列における値を計算する
コンピュータ・インストラクションを更に含む装置。
【請求項９】
前記Ｋ個の要素の全てについて同じ算数または論理演算を備える１つ以上のインストラクションを用いることによって、これらの要素が同時に演算され、前記Ｋ個の要素の１つの前記演算が前記Ｋ個の要素の別のものの同じく同時に行われる前記演算の結果に影響を及ぼさないものとされる、前記Ｋ個の要素にマイクロプロセッサのレジスタを分割する
インストラクションを更に備える請求項８に記載のコンピュータ読み取り可能装置。
【請求項１０】
前記ベクトルにおける前記Ｋ個の要素のいずれか１つの値の計算が、前記１つのベクトルの前のＫ−１個の要素のいずれかの値または前のベクトルの要素の値に依存するかどうかを調査するインストラクションが、
依存性が検出されないならばベクトルの方向における潜在的なギャップを考慮することなく正しいベクトル要素値を計算し、そして
依存性が検出されるならばベクトルの方向における潜在的なギャップを考慮することによって正しい値を続けて計算する
ステップを更に備える請求項８および９に記載のコンピュータ読み取り可能装置。
【請求項１１】
前記依存性の測定を行うインストラクションが、
前記１つのベクトルの方向のシーケンスにおける潜在的なギャップから結果として得ることができていたはずの効果を無視することによって、前記ベクトルのＫ個の要素について最初のスコア値を計算し、そして
前のベクトルの最後の要素または前記最初の値の最後以外のいずれかが、ギャップ開放罰金パラメータとギャップ拡張罰金パラメータとの和として形成される制限を超えるか否かチェックすることによって依存が可能か否か測定する
ステップを更に備える請求項１０に記載のコンピュータ読み取り可能装置。
【請求項１２】
前記１つのベクトルのＫ個の要素の最後のスコア値を測定するインストラクションが、
依存性が検出されないならば、前記計算された最初のスコア値を最後のスコア値として用い、および
依存性が検出されるならば、可能なギャップを考慮して依存するベクトル要素を連続して再計算する
インストラクションを更に備える請求項１１に記載のコンピュータ読み取り可能装置。
【請求項１３】
オーバーフローが生じたことを認識することによって、前記１つのＫ要素を表す１つの蓄積要素における前記演算の算数においてオーバーフローを取り扱い、そしてそれによって前記１つのＫ要素を表す蓄積要素におけるより大きな値の範囲を取り扱うよう演算を繰り返す
インストラクションを更に含む請求項８乃至１２のいずれかに記載のコンピュータ読み取り可能装置。
【請求項１４】
値を調整する飽和算数を前記１つのＫ要素を表す蓄積要素の値を最大に表すことにそのデータ型のオーバーフローが起こるとき適用することによって、前記算数演算におけるオーバーフローを検出し、それによって前記１つの蓄積要素のこの最大値を認識することでオーバーフローを検出する
インストラクションを更に含む請求項１３に記載のコンピュータ読み取り可能装置。
【請求項１５】
コンピュータ・インストラクションをインストラクションとして適用できるいずれのところもＳＩＭＤ（単一インストラクション多重データ）プログラム・コードで最適化する方法を更に備える
請求項８乃至１４に記載のコンピュータ読み取り可能装置。
【請求項１６】
ＭおよびＮ要素それぞれの２つの生物学上のシーケンスＡとＢとの間のスミス−ウォターマン最適局部配列類似スコアを測定し、長さＭの前記１つのシーケンスＡと長さＮの前記１つのシーケンスＢとの比較に対応するＭ×Ｎ要素のスミス−ウォターマン行列および減算スコア値行列Ｚにおける値ならびに開放罰金ギャップｑおよびギャップ拡張罰金ｒを計算する電子回路を備えるＡＳＩＣ（専用集積回路）またはＶＬＳＩ（完全カスタム集積回路）またはＦＰＧＡ（フィールド・プログラム可能ゲート・アレイ）型の電子装置またはその他の型のプログラム可能電子装置であって、
前記１つのＭ×Ｎ行列の同じ行または列で連続して位置するＫ個の要素にＫ個の要素のベクトルが対応する前記Ｋ個のベクトル要素を用いて前記１つのＭ×Ｍ行列における値を計算する
手段を備える装置。
【請求項１７】
前記Ｋ個の要素の全てについて同じ算数または論理演算を備える１つ以上の回路を用いることによって、これらの要素が同時に演算され、前記Ｋ個の要素の１つの前記演算が前記Ｋ個の要素の別のものの同じく同時に行われる前記演算の結果に影響を及ぼさないものとされる、前記Ｋ個の要素の最適な個数のＫ電子レジスタ
を更に備える請求項１６に記載の電子装置。
【請求項１８】
前記ベクトルにおける前記Ｋ個の要素のいずれか１つの値の計算が、前記１つのベクトルの前のＫ−１個の要素のいずれかの値または前のベクトルの要素の値に依存するかどうかを調査する回路、
依存性が検出されないならばベクトルの方向における潜在的なギャップを考慮することなく正しいベクトル要素値を計算する回路、および
依存性が検出されるならばベクトルの方向における潜在的なギャップを考慮することによって正しい値を続けて計算する回路
を更に備える請求項１６および１７に記載の電子装置。
【請求項１９】
依存性の測定を行う回路が、
前記１つのベクトルの方向のシーケンスにおける潜在的なギャップから結果として得ることができていたはずの効果を無視することによって、前記ベクトルのＫ個の要素について最初のスコア値を計算し、そして
前のベクトルの最後の要素または前記最初の値の最後以外のいずれかが、ギャップ開放罰金パラメータとギャップ拡張罰金パラメータとの和として形成される制限を超えるか否かチェックすることによって依存が可能か否か測定する
手段を更に備える請求項１８に記載の電子装置。
【請求項２０】
前記１つのベクトルのＫ個の要素の最後のスコア値を測定する回路が、
依存性が検出されないならば、請求項１９に記載されるように計算された前記最初のスコア値を前記最後のスコア値として用いる手段と、
依存性が検出されるならば、可能なギャップを考慮して依存するベクトル要素を連続して再計算する手段と
を更に備える請求項１９に記載の電子装置。
【請求項２１】
オーバーフローが生じたことを認識することによって、前記１つのＫ要素を表す１つの蓄積要素における前記演算の算数においてオーバーフローを取り扱い、そしてそれによって前記１つのＫ要素を表す蓄積要素におけるより大きな値の範囲を取り扱うよう演算を繰り返す手段
を更に備える請求項１６乃至１９に記載の電子装置。
【請求項２２】
値を調整する飽和算数を前記１つのＫ要素を表す蓄積要素の値を最大に表すことにそのデータ型のオーバーフローが起こるとき適用することによって、前記算数演算におけるオーバーフローを検出し、それによって前記１つの蓄積要素のこの最大値を認識することでオーバーフローを検出する手段
を更に備える請求項２１に記載の電子装置。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明は、生物学上のシーケンスの比較に関し、より詳しくは、本発明は、特許請求の範囲第１、８および１６項にそれぞれ記載の最適局部シーケンス類似スコアの測定方法、コンピュータ読み取り可能装置および電子装置に関する。
【０００２】
（発明の背景）
利用可能な遺伝子シーケンス情報の量が急速に増大するために、データベース検索および取り扱いハードウェアおよびソフトウェアの開発者に絶え間なく課題が与えられることとなる。ＧｅｎＢａｎｋ／ＥＭＢＬ／ＤＤＢＪヌクレオチド・データベースの大きさは、今のところ少なくとも１５ヶ月毎に２倍になっている（ベンソン（Ｂｅｎｓｏｎ）らによる、２０００年）。遺伝子シーケンス情報の急速な拡大は、計算源もまた永年指数関数的に増大しているという事実があるにも関わらず、一定のコストで利用可能な計算力の成長をおそらくは凌いでいる。この傾向が続くならば、データベース全体を検索するのにずっと長い時間またはずっと高価なコンピュータが必要とされることとなるであろう。
【０００３】
所定のシーケンスに類似するシーケンスをデータベースから検索することは、特性の決定されていないたんぱく質の構造および機能特性を予測するのに最も基本的かつ重要なツールのひとつである。それ故、これらの検索を行うための良好なツールが利用可能であることが重要である。所定の問い合わせシーケンスに類似するデータベースにおいてシーケンスを探すとき、検索プログラムはそのデータベースにおける全てのシーケンスについて配列スコアを計算する。このスコアは、その問い合わせシーケンスとデータベース・シーケンスとの類似の度合いを表す。スコアは、２つのシーケンスの配列から計算され、そして置換スコア行列およびギャップ罰金関数に基づいている。最適局部配列スコアを計算するダイナミック・プログラミング・アルゴリズムは、最初にスミス（Ｓｍｉｔｈ）およびウォターマン（Ｗａｔｅｒｍａｎ）によって記述され（１９８１年）、ギャップ罰金関数についてゴトウ（Ｇｏｔｏｈ）によって改良され（１９８２年）、そしてグリーン（Ｇｒｅｅｎ）によって最適化された（１９９３年）。
【０００４】
最適なアルゴリズムを用いるデータベース検索は、残念なことに通常のコンピュータではかなり遅いので、ＦＡＳＴＡ（ピアソン（Ｐｅａｒｓｏｎ）およびリップマン（Ｌｉｐｍａｎ）１９８８年）やＢＬＡＳＴ（アルトシュール（Ａｌｔｓｃｈｕｌ）ら、１９９０年；アルトシュールら、１９９７年）のようなヒューリスティック（ｈｅｕｒｉｓｔｉｃ）な代替法が非常に多く開発されている。これらの方法は、最も良く知られている非並列汎用コンピュータでのスミス−ウォターマンの実装に比べて４０までの係数だけ実行時間を低減しているが、しかしながら感度が犠牲になっている。感度が損失しているために、ヒューリスティックなアルゴリズムを用いる検索においては、関係が遠く隔たるシーケンスによっては、検出されないものもある。
【０００５】
高速でもあり、かつ感度も高い検索が求められているために、スミス−ウォターマン方法並みの高速実装を生成するべく多大な努力がなされている。いくつかの専用ハードウェアでの解決策が、パラセル（Ｐａｒａｃｅｌ）のジーンマッチャー（ＧｅｎｅＭａｔｃｈｅｒ）、コンピュゲン（Ｃｏｍｐｕｇｅｎ）のバイオクセラレータ（Ｂｉｏｃｃｅｌｅｒａｔｏｒ）およびタイムロジック（ＴｉｍｅＬｏｇｉｃ）のディサイファー（ＤｅＣｙｐｈｅｒ）のような並列処理能力（フーゲイ、１９９６年）をもって開発されている。これらの機械は毎秒２０億個を超えるマトリックス・セルを処理することができ、そしてより高速に達するよう拡張することができる。しかしながら、そのような機械は非常に高価であって、通常のユーザーが直ちに利用することはできない。スミス−ウォターマンのアルゴリズムをハードウェアで実装するものがいくつか、例えば、米国特許５５５３２７２、５６３２０４１、５７０６４９８、５９６４８６０および６１１２２８８のような特許公報に記述されている。
【０００６】
並列処理能力のより一般的な形態は、単一インストラクション多重データ（ＳＩＭＤ）技術を用いて利用可能である。ＳＩＭＤコンピュータは、同じ演算（論理、算術その他）をいくつかの独立したデータ源で並列に行うことができる。広いレジスタをより小さな単位へと分割することによってマイクロ・パラレリズム（レジスタ内でのＳＩＭＤ−ＳＷＡＲとしても知られる）の形態でこれを利用することが可能である。しかしながら、近ごろのマイクロプロセッサは、特別なレジスタおよびインストラクションを加えてＳＩＭＤ技術をより使いやすいものとしている。１９９７年にペンティアム　ＭＭＸ（Ｒ）（マルチメディア拡張（ＭｕｌｔｉＭｅｄｉａ　ｅＸｔｅｎｓｉｏｎｓ）マイクロプロセッサ）を導入することで、インテル（Ｒ）はＳＩＭＤ技術での計算が最も広く用いられるコンピュータ・アーキテクチャ−産業基準ＰＣ−の汎用マイクロプロセッサにおいて利用可能なものとした。その技術はまた、ペンティアムＩＩ（Ｒ）においてもまた利用可能であり、ＳＳＥ（Ｒ）（Ｓｔｒｅａｍｉｎｇ　ＳＩＭＤ　Ｅｘｔｅｎｓｉｏｎｓ）という名の下でペンティアム　ＩＩＩ（Ｒ）において拡張されている（インテル（Ｒ）、１９９０年）。この技術のさらなる拡張が、ＳＳＥ２（Ｒ）（Ｓｔｒｅａｍｉｎｇ　ＳＩＭＤ　Ｅｘｔｅｎｓｉｏｎｓ　２）という名の下でペンティアム４（Ｒ）プロセッサ（ウィラメッテ（Ｗｉｌｌａｍｅｔｔｅ）としても知られている）として発表されている（インテル（Ｒ）、２０００年）。ＭＭＸ／ＳＳＥ／ＳＳＥ２（Ｒ）のインストラクションの組には、整数または浮動小数点数で演算する算術（加算、減算、乗算、最小、最大、平均、比較）、論理（ａｎｄ、ｏｒ、ｘｏｒ、ｎｏｔ）およびその他のインストラクション（シフト、パック、アンパック）が含まれている。この技術は、音、映像およびビデオのようなデジタル信号処理のアプリケーションをスピードアップするように主に設計されているが、遺伝子シーケンスを比較するのにもまた適切であるように思われる。ＳＩＭＤ技術を備える他のいくつかのマイクロプロセッサが表１に示されるように近い将来存在するか利用可能なものとされる（デュベイ（Ｄｕｂｅｙ）、１９９８年）。
【０００７】
【表１】
2004510265.tif 000003
【０００８】
何人かの調査員は、スミス−ウォターマンのアルゴリズムをスピードアップするのにＳＩＭＤ技術を用いたが、最善の非並列実装に関してはスピードの増大は限定されていた。
【０００９】
最適な局部配列スコアの計算についての一般的なダイナミックなプログラミング・アルゴリズムは、スミスおよびウォターマンによって最初に記述された（１９８１年）。
【００１０】
ゴトウは、擬似のギャップ罰金をもってこのアルゴリズムを実装することを記述した（１９８２年）が、ここで、ｑをギャップ開放罰金およびｒをギャップ拡張罰金とするとき、サイズｋのギャップのギャップ罰金はｑ＋ｒｋに等しい。これらの制限のもとでは、アルゴリズムの実行時間は、２つのシーケンスの長さの積に比例して低減された。
【００１１】
グリーンは、ＳＷＡＴプログラムを書き（１９９３年）、いくつかの最適化をゴトウのアルゴリズムに適用して真っ直ぐな実装に関して約２の係数のスピードアップを達成した。ＳＷＡＴ最適化もまた、ピアソンのＳＳＥＡＲＣＨプログラムに組み込まれている（１９９１年）。
【００１２】
スミス−ウォターマンのアルゴリズムは、いくつかの異なるＳＩＭＤコンピュータについて実装されている。スターロック（Ｓｔｕｒｒｏｃｋ）およびコリンズ（Ｃｏｌｌｉｎｓ）は、ＭＰｓｒｃｈと呼ばれるプログラムにおいて、並列コンピュータのＭａｓＰａｒファミリについてスミス−ウォターマンのアルゴリズムを実装した（１９９３年）。この解決策は、４０９６個のＣＰＵを備えるＭａｓＰａｒ　ＭＰ−１コンピュータで毎秒１億３０００万個のマトリックス・セルまでの、および１６３８４個のＣＰＵを備えるＭａｓＰａｒ　ＭＰ−２で毎秒１５億個のマトリックス・セルまでのスピードを達成した。ブラットラグ（Ｂｒｕｔｌａｇ）らはまた、ＢＬＡＺＥと呼ばれるプログラムにおいて、ＭａｓＰａｒコンピュータでスミス−ウォターマンのアルゴリズムを実装した（１９９３年）。
【００１３】
アルパーン（Ａｌｐｅｒｎ）らは、マイクロパラレリズムを使用する並列実装を含むスミス−ウォターマンのアルゴリズム、インテル・パラゴン（Ｐａｒａｇｏｎ）ｉ８６０プロセッサ（Ｒ）の６４ビットの広いＺバッファ・レジスタを４つの部分に分割することによってスピードアップするいくつかの方法を提示した（１９９５年）。このアプローチで、彼らは、問い合わせシーケンスを異なる４つのデータベースのシーケンスと同時に比較することができた。彼らは、通常の実装の５倍を超えるスピードアップを達成した。
【００１４】
ウォズニアック（Ｗｏｚｎｉａｋ）は、サン（Ｒ）のウルトラＳＰＡＲＣマイクロプロセッサのＶＩＳ（Ｖｉｓｕａｌ　Ｉｎｓｔｒｕｃｔｉｏｎ　Ｓｅｔ）技術を用いてスミス−ウォターマンのアルゴリズムを実装する方法を提示した（１９９７年）。この実装は、１６７ＭＨｚのウルトラＳＰＡＲＣマイクロプロセッサで毎秒１億８０００万個のマトリックス・セルを超えるスピードを達成した。ウォズニアックによると、これによって、同じ機械に整数のインストラクションで実装される同じアルゴリズムに関して約２の係数のスピードアップがなされるものとなる（１９９７年）。
【００１５】
テイラー（Ｔａｙｌｏｒ）は、ＭＭＸ技術をスミス−ウォターマンのアルゴリズムに適用して（１９９８年および１９９９年）、インテルの５００ＭＨｚペンティアムＩＩＩ（Ｒ）マイクロプロセッサで毎秒６６０万個のセルを更新するスピードを達成した。
【００１６】
スターロックおよびコリンズは、ＳＩＭＤを用いるスミス−ウォターマンのアルゴリズムをアルファ・マイクロプロセッサに実装した（２０００年）。しかしながら彼らの方法の詳細は公表されていない。ｈｔｔｐ：／／ｗｗｗ．ｅｂｉ．ａｃ．ｕｋ／ＭＰｓｒｃｈ／で利用可能なウェブのサービスから見る限り、彼らは擬似ギャップ罰金を用いて毎秒約５３００万個のセルを更新するスピードを達成している。このシステムが実装しているコンピュータがなんであるかは正確に知られていない。
【００１７】
最近バートン（Ｂａｒｔｏｎ）らは、ＭＭＸ技術を使用してスミス−ウォターマンのアルゴリズムを彼らのＳＣＡＮＰＳで実装したものをスピードアップした（２０００年）。彼らは、インテルの６５０ＭＨｚペンティアムＩＩＩ（Ｒ）マイクロプロセッサで毎秒７１００万個のセルの更新を行うスピードを主張する。彼らの実装の詳細を記述しない抽象的なポスターのみが今のところ利用可能である。
【００１８】
（発明の開示）
２つのシーケンスの最適局部シーケンス配列スコアを計算する方法に関しての効率的な並列化を記述する。全体の計算のスピードの増大はいくつかの演算を並列に行うことで達成される。
【００１９】
本発明によりスミス−ウォターマンに基づく検索を汎用コンピュータで以前可能であったよりもずっと速いスピードで行うことが可能となる。
【００２０】
５００ＭＨｚのインテル・ペンティアム　ＩＩＩ（Ｒ）マイクロプロセッサでＭＭＸ（Ｒ）およびＳＳＥ技術を用いると、たんぱく質をたんぱく質データベースのシーケンスと比較するとき、毎秒約２億個のセルの更新というスピードが達成された。知られている限り、これまでのところこれが単一マイクロプロセッサの汎用コンピュータで最速にスミス−ウォターマンのアルゴリズムを実装するものである。基準と実装であると考えられる、通常用いられるＳＳＥＡＲＣＨプログラムに関して、それは約８のスピードアップを表す。１．４ＧＨｚで作動する今度のインテル・ペンティアム　４（Ｒ）プロセッサに本発明を実装すると、毎秒１０億個のセルの更新を超えるスピードが得られると思われる。これらのスピードは、本質的に同じ計算を行うのに高価な専用のハードウェアでの解決策のスピードに近づくかまたはそれに等しいものとなる。
【００２１】
本発明を用いると、通常利用可能で高価ではないハードウェアで高スピードが達成され、そうして最適な局部配列ダイナミック・プログラミングアプローチを用いてシーケンス配列およびデータベース検索を行う費用および／または計算時間を大きく低減する。
【００２２】
本発明は、問い合わせシーケンスに平行なベクトル（「問い合わせに基づくベクトル」）を用いて全ての計算が行われるという原則に基づくものである（図２ｂ参照）。これは、行列におけるマイナーな対角線に平行であるベクトル（「対角線ベクトル」）を用いて計算が行われる伝統的なアプローチに対比するものである。双方の場合において、ベクトルは配列マトリックスにおいて異なるセルを表す２つ以上の要素を含む。ベクトルの要素の値はスコア値、例えば以下に記述される循環関係にあるｈ−、ｅ−またはｆ−変数である。
【００２３】
伝統的なアプローチの利点は、ベクトルの個々の要素の計算が完全に独立しているということである（図３ａ参照）。それ故、このアプローチを用いることは明らかであるように思える。伝統的なアプローチは、フーゲイ（Ｈｕｇｈｅｙ）（１９９６年）、ウォズニアック（１９９７年）およびテイラー（１９９８年、１９９９年）によって詳細が記述されており、詳細に知られているスミス−ウォターマン配列手順の全ての並列な実装に対してほとんど普遍的であるように思われる。しかしながら、このアプローチにはいくつかの不利益があり、最も顕著なのは置換スコア値のベクトルを形成する複雑さである。この問題は並列処理（パラレリズム）の度合いが高いと特に顕著である。問い合わせに基づくベクトルのアプローチは、スミス−ウォターマンのアルゴリズムを並列化しようという数多の試みにもかかわらず、先には記述されていない。本発明は、充分に新規であって、現在の「技術レベル」とは異なるものと思われる。
【００２４】
問い合わせに基づくベクトルのアプローチの不利益は、ある計算においての個々のベクトル要素間の依存である（図３ｂ参照）。しかしながら、ＳＷＡＴ最適化において用いられる原則のベクトル一般化を使用することによって、これらの依存は計算の小さな断片にしか影響しなくなり、そしてそれ故性能に大きな影響をもたらすものではない。問い合わせを基礎とするアプローチの利点は、問い合わせシーケンス・プロフィール（問い合わせ専用スコア行列としてもまた知られる）を用いるときメモリから置換スコア値のベクトルを非常に簡略化してロードすることである。
【００２５】
本発明の方法は、問い合わせプロフィールを用いており、それは問い合わせ位置と可能なシーケンス記号とのあらゆる組み合わせについてのスコアの行列である。スコアは、メモリに配列されており、単一のデータベース・シーケンス記号を問い合わせシーケンス記号の連続する範囲と整合させるスコアを表すベクトルがメモリから単一のインストラクションを用いるマイクロプロセッサへと容易にロードされるようになっている。これは、最初の可能なデータベース・シーケンス記号を問い合わせシーケンスの記号の各々と整合させるスコアをまず蓄積し、第２の可能なデータベース・シーケンス記号を各問い合わせ位置と整合させるスコアなどをそれに続けることによって達成される。
【００２６】
問い合わせプロフィールのスコアは、全ての値が非負となるように、全て固定量（例えばＢＬＯＳＵＭ６２行列の場合に４）だけバイアスされ、符号の付かない整数として蓄積される。これによってそれに続く計算を符号の付かない算数を用いて行うことが可能となる。符号の付かない整数減算演算を用いて一定のバイアスがその後減算される。
【００２７】
ベクトル要素は、数ビット（例えば８）で表され、そしてスコアの狭い範囲のみを表す。ベクトルの大きさの合計が特定数のビット（例えば６４）に制限されるとき、狭いベクトル要素によって、ベクトルを、より広い要素が用いられた場合よりも多くの要素（例えば８）へと分割することが可能となる。これによってより同時に計算を行わせることができ、さらにスピードを増大させる。
【００２８】
スコアがベクトル要素によって表すことのできるものよりも大きな場合においてさえ、狭いスコア範囲を有用なものとするために、スコア計算においてオーバーフローを検出するために飽和された算数を使用する。オーバーフローが検出されるならば、それに続いて全体の配列スコアがより広いスコア範囲、例えば１６ビットを備える実装を用いて再計算される。そのような高スコアは比較的珍しいので性能の影響が小さい。
【００２９】
スコアの計算が符号の無い値を用いて行われる。符号の無いスコア値によってできるだけ広いスコア範囲が可能となる。これによって、前述のように必要な再計算の数が低減される。
【００３０】
飽和した符号の付いていない算数を用いて計算が行われる。これによって、ゼロでの減算、すなわち頻繁に計算で行われる演算の負の結果を容易にクリップすることができる。
【００３１】
方法、コンピュータ読み取り可能装置および電子装置は、添付した特許請求の範囲第１、８および１６項にそれぞれ記述されるようなそれぞれの特徴を有しており、さらにそれらの実施例が特許請求の範囲第２乃至７項、９乃至１５項および１７乃至２２項にそれぞれ開示されている。
【００３２】
【表２】
2004510265.tif 000004
2004510265.tif 000005
2004510265.tif 000006
【００３３】
（発明の好ましい実施例）
好ましい実施例が図を参照して記述される。データベースにおける各シーケンスについて、シーケンス類似性検索プログラムが、問い合わせシーケンスとデータベース・シーケンスとの間の類似の度合いを表す配列スコアを計算する。問い合わせおよびデータベース・シーケンスの長さおよび組成を考慮することによってもまた、統計的なパラメータを計算し、問い合わせシーケンスに類似する順番にデータベース・シーケンスを整列するのに用いることができる。生の配列スコアは、置換スコア行列（例えば、ＢＬＯＳＵＭ６２）に基づいており、２つの記号の間の、ならびにギャップ解放に基づく擬似ギャップ罰金関数とギャップ拡張罰金との間の類似性を表す。
【００３４】
以下の説明においては、８つの要素のベクトルが各８ビット、合計６４ビットで用いられている。しかしながら、これは単に説明を容易くするために過ぎない。ベクトルおよび要素の大きさの多くの他の組み合わせが可能であり、以下の説明から容易に一般化することができる。１より大きな如何なる数のベクトル要素もかつ各要素について如何なるビット数も可能である。しかしながら、８ビットという要素の大きさおよび８、１６または３２の要素というベクトルの大きさがおそらくは最も有用である。
【００３５】
以下の説明においてインテルのマイクロプロセッサおよびそのＭＭＸおよびＳＳＥ技術を用いて可能な実装でもって方法が例示されている。しかしながら、これは説明を容易くするために過ぎない。他のマイクロプロセッサおよび他のＳＩＭＤ技術を用いる実装もまた可能である。
【００３６】
スミス−ウォターマンのアルゴリズム
最適の局部配列スコアを計算するために、スミスおよびウォターマンによるダイナミック・プログラミング・アルゴリズム（１９８１年）が、ゴトウによって一層良くされて（１９８２年）用いられている。長さｍの問い合わせシーケンスＡ、長さｎのデータベース・シーケンスＢ、置換スコア行列Ｚ、ギャップ開放罰金ｑおよびギャップ拡張罰金ｒが与えられて、最適局部配列スコアｔを以下の反復（ｒｅｃｕｒｓｉｏｎ）関係によって計算することができる。
ｅｉ，ｊ＝ｍａｘ｛ｅｉ，ｊ−１，ｈｉ，ｊ−１−ｑ｝−ｒ
ｆｉ，ｊ＝ｍａｘ｛ｆｉ−１，ｊ，ｈｉ−１，ｊ−ｑ｝−ｒ
ｈｉ，ｊ＝ｍａｘ｛ｈｉ−１，ｊ−１＋Ｚ［Ａ［ｉ］，Ｂ［ｊ］］，ｅｉ，ｊ，ｆｉ，ｊ，０｝
ｔ＝ｍａｘ｛ｈｉ，ｊ｝
ここで、ｅｉ，ｊおよびｆｉ，ｊは、Ａの最初のｉ個の記号およびＢの最初のｊ個の記号に関連し、シーケンスＢまたはＡにおけるギャップで終わる最大局部配列スコアをそれぞれ表す。Ａの最初のｉ個の記号およびＢの最初のｊ個の記号に関連する全体の最大局部配列スコアが、ｈｉ，ｊで表される。１からｍまで行くｉおよび１からｎまでのｊをもって全てのｉ＝０またはｊ＝０についてｅｉ，ｊ＝ｆｉ，ｊ＝ｈｉ，ｊ＝０で開始して反復（ｒｅｃｕｒｓｉｏｎ）が計算される。配列行列における値の計算の順序は厳しいものであり、それは、図１のデータ相互依存グラフに示されるように、如何なるセルの値もそれの左および上にある全てのセルの値が計算されるまで計算できないからである。ゴトウの説明するようなアルゴリズムの実装（１９８２年）はｍｎに比例する実行時間を有する。
【００３７】
並列処理（Ｐａｒａｌｌｅｌｉｓａｔｉｏｎ）
スミス−ウォターマンのアルゴリズムは２つのスケールで並列にすることができる。対称な多重処理（ＳＭＰ）マシーンにおいていくつかの独立したプロセッサにデータベースのシーケンスの各々の処理を分配するのはかなり容易い。しかしながら、より低いスケールでは、単一データベース・シーケンス内に関連する仕事を分配するのは少しだけより複雑である。図１は配列行列におけるデータ相互依存を示す。行列における如何なるセルの最終値ｈもその左およびその上の全てのセルの値が計算されるまで計算することはできない。しかしながら、マイナーな対角線（図２ａおよび図３ａ参照）に平行な対角に配置されるセルの値の計算は独立しており、並列実装において同時に行うことができる。この事実は、より容易いＳＩＭＤ実装において使用されている（フーゲイ１９９６年、ウォズニアック１９９７年）。
【００３８】
発明のアプローチ
本発明による実装の主な特長は以下の通りである。
・問い合わせシーケンスに平行なベクトル
・ＳＷＡＴ最適化のベクトル一般化
・８ビット値での８通りの並列処理
・問い合わせシーケンス・プロフィール
・符号の付かない算数
・飽和算数
・一般的なコード最適化
これらの概念は以下に詳細に説明される。説明を例示し例証するために、本方法の擬似コードが図４に示されている。
【００３９】
擬似コードにおいて、図４ａおよび図４ｂの本発明による方法は、８つの要素のベクトルを用いて例示されるが、しかしながら、本発明の方法は一般的なものであって如何なる数の要素のベクトルででも実装することができる。
【００４０】
擬似コードは、問い合わせシーケンス長（ｍ）がベクトルの大きさ８の倍数であると仮定する。これは、問い合わせシーケンスおよび問い合わせスコア・プロフィールを膨らますことによって達成できる。
【００４１】
全てのベクトル・インデックスは、プログラミング言語において通常そうであるようにゼロで（普通の数学表記において通常そうであるように１ではない）開始する。
【００４２】
ベクトルまたはアレイ変数または演算を表すのに大文字が一般に用いられ、一方、スカラー変数または演算を表すのに小文字が一般に用いられる。
【００４３】
Ｓ−行列はｎ問い合わせ専門スコア行列のｘ倍であって、ｘ個の異なる可能なデータベース・シーケンス記号のいずれかをｎ個の問い合わせポジションのいずれかで問い合わせ記号と置き換えるスコアを表す。一般にｘは、シーケンス記号が属するところからのアルファベットの大きさを表すに過ぎない。アミノ酸シーケンスについては、ｘは典型的には２０（２０の自然アミノ酸を表す）かまたはわずかに大きい（あいまいなその他の記号もまた含む）。ヌクレオチド・シーケンスについては、ｘは典型的には４（４つのヌクレオチド、アデニン、シトシン、グアニンおよびチミン／ウラシルを表す）またはそれより大きい（あいまいなその他の記号もまた含む）。Ｓ−行列は通常問い合わせシーケンスおよび置換スコア行列からあらかじめ計算されるが、また一般的な問い合わせプロフィールをも表し、それはたんぱく質シーケンス・ファミリの多重配列から計算されるスコアに基づく。
【００４４】
Ｈ−ベクトルはｈ−値をもち、所定の行列セルについて最適な局部配列スコアを表す。Ｈ−ベクトルはＨＨ−アレイの一部を表す。Ｅ−ベクトルはｅ−値を用い、データベース・シーケンス・ギャップと関連する配列からのスコアを表す。Ｅ−ベクトルはＥＥ−アレイの一部を表す。Ｆ−ベクトルは、ｆ−値および一時的なｆ−値をもち、問い合わせシーケンス・ギャップと関連する配列からのスコアを表す。
【００４５】
ＬＡＳＴＦベクトルにおいては唯一の要素のみ（インデックス０で）が用いられる。それは、問い合わせシーケンスにおけるギャップと関連する前のラウンドからの潜在的なスコアを表す。用いられる実際の値は、後の計算を簡略化するために追加されるギャップ開放罰金を有する。
【００４６】
問い合わせシーケンスに平行なベクトル
ベクトル要素の各々の計算の間の独立性が失われるにも関わらず、（図２ａおよび図３ａに示されるように）行列においてマイナーな対角線に平行なセルのベクトルの代わりに（図２ｂおよび図３ｂに示されるように）問い合わせシーケンスに平行なセルのベクトルを用いることが決定された。このアプローチの利点は、メモリからの置換スコアのベクトルのずっと簡略化され、かつより速いローディングである。不利な点は、ｆ−値の計算（図３ｂ参照）に関係するベクトル内のデータ依存性が取り扱われなければならないというものである。図２ｂに指示されるように、各列に沿って同時に８つのセルが処理される。問い合わせシーケンスに平行な８つの連続するセルのグループの反復関係におけるｈ−、ｅ−およびｆ−値を表すのにベクトルが用いられる。ゼロ、ｑ、ｒ、ｑ＋ｒおよびその他の係数を表すのにもまたベクトルが用いられる。ベクトル処理を用いて、８つのｈ−、ｅ−またはｆ−値の値が並列に計算される（第１１ページの等式において記述されるようなｈ、ｅおよびｆ）
【００４７】
ＳＷＡＴ最適化のベクトルの一般化
既に指示されたとおり、ベクトルの各要素は、図３ｂに示されるように、問い合わせシーケンスにおいてギャップを導入するのが可能であるために、その上の要素に依存することを考慮しなければならない。ＳＷＡＴ最適化およびその他の最適化のベクトルの一般化を使用して問い合わせ並行ベクトルの原則を効率的なものとする。図４の擬似コードに概念が例示されている。
【００４８】
ｆ−値は問い合わせシーケンスのギャップを備えるセルで終わる配列のスコアを表す。ｆ−値はその上のセルのｈ−およびｆ−値に依存する。それ故、Ｆ−ベクトルは、Ｈ−およびＦ−ベクトルに依存し、そして更には、そのベクトルの直ぐ上のセルにおけるｈ−およびｆ−値に依存する。これらの依存性は計算を複雑なものとし一般的な場合において並列に行うのを困難とする。
【００４９】
しかしながら、ｈ−値が単一の記号ギャップ（ｑ＋ｒ）のギャップ罰金に等しい閾値よりも大きいならば、セルのｈ値は他のセルのみに影響を及ぼすので、たいていの場合計算が簡略化される。実際上、相対的に少数のセルが閾値を超えるｈ−値を有し、たいていの場合簡略化された計算を用いることができることを意味する。これらの原則は、ｑ＋ｒの閾値よりも大きなベクトルの場合において一般化することができ、可能な依存性がある。ベクトルの上のセルにおけるｈ−値がｑ＋ｒの閾値よりも大きいかまたはベクトルの上のセルにおけるｆ−値がギャップ拡張罰金ｒよりも大きいならば、また可能な依存性がある。
【００５０】
実際、最初のＨ−ベクトルの最下の要素はベクトル内の依存性を引き起こすことができないが、しかしそれをチェックに含め、それは、それが、Ｅ−ベクトルおよび全体の最も高いスコアを含むベクトルに影響を与えるからである。
【００５１】
チェックが正であるならば最初のＨ−ベクトルもまた最後のＨ−ベクトルである。この場合、Ｅ−ベクトルもまたＨ−ベクトルに依存しておらず、そして、Ｅ−ベクトルの各要素からギャップ拡張罰金を単に推定することによって計算することができる。チェックが正であるならば、全体の最高のスコアを含むベクトルを更新するのを（ｑ＋ｒ未満の最後のスコアに興味が無ければ）省くこともできる。
【００５２】
チェックが負であるならば、最初のＨ−ベクトルおよび上のセルからのｈ−およびｆ−値に基づいて正しいＦ−ベクトルが計算されなければならない。この計算は、図４の擬似コードによって説明されるような大変長い一連の減算−、シフト−および最大−演算によって行われる。正しいＦ−値が計算されているとき、正しいＨ−およびＥ−ベクトルが更新されなければならない。加えて、全体で最高のスコアを含むベクトルもまた更新されなければならない。
【００５３】
８ビット値での８通りの並列処理
マイクロプロセッサは、ＳＩＭＤインストラクションについてより小さなユニットに分割することができる一組のレジスタ（通常６４ビット幅）を提供する。マイクロプロセッサのペンティアム（Ｒ）・ファミリには、単一の６４ビット（カッド語）ユニットか２つの３２ビット（ダブルワード）、４つの１６ビット（ワード）または８つの８ビット（バイト）ユニットかのいずれかとして取り扱うことのできるいくつかの６４ビットのレジスタが含まれる。これらのユニットでの演算は独立している。したがって、マイクロプロセッサは８つまでの独立した加算またはその他の演算を同時に行うことができる。
【００５４】
計算のスピードを最適化するために、マイクロプロセッサのＭＭＸレジスタは、できる限り多くのユニット、すなわち８つの８ビット・ユニットへと分割できる。これによって、８つの演算を同時に行うことが可能となる。ＭＭＸレジスタを８つの８ビット・レジスタに分割することで、並列演算の数が増大するが、計算の精度がゼロから２５５の範囲に限定される。シーケンスが長くて非常に類似するものでないならば、これによって問題が提起されることはない。このスコア制限が越えられるいくつかの場合においては、飽和算数の使用（以下参照）によって全体で最高のスコアが２５５にとどまることが確実となる。２５５というスコアに到達する全てのシーケンスについて、正しいスコアが後でより大きなスコア範囲をもつ異なる実装によって（例えばＳＩＭＤでない実装を用いて）再計算される。
【００５５】
問い合わせシーケンス・プロフィール
最初に、ｍ掛けるｘ行列である、Ｓと呼ばれる問い合わせプロフィール（問い合わせ専門スコア行列としてもまた知られている）を以下の値で計算する。
Ｓ［ｋ，ｉ］＝Ｚ［ｋ，Ａ［ｉ］］
ここで、ｋはシーケンスＢで生じる可能な記号のいずれかであり、かつｉは問い合わせポジションである。このプロフィールは、検索全体について一度のみしか計算されない。例えば、データベース・シーケンスＢにおける（アラニンの）記号Ａを問い合わせシーケンスにおける記号の各々とマッチングするスコアが連続して最初の行列の行に蓄積され、次の行の記号Ｂ（あいまいな）をマッチングするスコアがそれに続く等である。この問い合わせシーケンス・プロフィールは、アルゴリズムの内側のループに広範囲に用いられ、そして通常マイクロプロセッサの第一レベルのキャッシュに保たれるように充分に小さい。
【００５６】
符号の付かない算数
大抵のマイクロプロセッサにおいて、符号が付かないか符号の付くモードで加算および減算を行うことができる。アルゴリズムの内側ループにおいて、問い合わせプロフィールのスコアが符号の付かないｈ−値に加えられる。符号の付いた加算を用いるとｈ−値は０から１２７の範囲に制限されていたであろう。そうではなくて、問い合わせシーケンススコア・プロフィールにおける全ての値は、いずれの値も負とならないように固定量（例えば４）だけバイアスされた。そして、ひとつの符号の付いた演算が符号の付かない加算で置き換えられ、バイアスの符号の付かない減算がそれに続いた。それ故、有用なデータ範囲は８ビット近く（例えば０−２５１）に拡大された。
【００５７】
飽和算数
モジュラか（ラップアラウンドとしてもまた知られている）飽和モードかにおいて、ＳＩＭＤ技術を用いる符号の付かない算数を行うことができる。８ビット幅のレジスタを用いるとき、１０から２５を引くことによりモジュラ・モードで２４１という結果（１０−２５＝２４１−２５６であるから）が、飽和モードで０が与えられる。これは、スミス−ウォターマンのアルゴリズムの内側ループ計算において非常に有用であり、それはいくつかの計算においてゼロが負の結果に置き換わるからである。また、単一バイト値の制度が制限されるために、非常にスコアの高い計算において潜在的なオーバーフローを検出するのに飽和算数が有用である。
【００５８】
スミス−ウォターマンのアルゴリズムのコアは、２つの数の最大値を繰り返し計算する。したがって、この計算を高速にすることが重要である。ＳＳＥインストラクションの組には、２つの符号の付かないバイトの最大のものを計算する特別なインストラクション（ｐｍａｘｕｂ）が含まれている。このインストラクションは、元のＭＭＸインストラクションの組には含まれていなかったが、符号の付かない飽和減算（ｐｓｕｂｕｓｂ）で置き換えることができ、符号の付かない飽和加算（ｐａｄｄｕｓｂ）がそれに続けられる。
【００５９】
一般コードの適正化
コードの適正化を完全に制御するために、および高いレベルの言語においてＳＩＭＤインストラクションのための支援が制限されているので、アルゴリズムのコアは、アセンブリ言語で書くべきである。
【００６０】
マイクロプロセッサがジャンプすべきかいなか予測するのが困難であるとき、条件ジャンプの使用は避けるべきであり、それは、誤った予測にはさらなる時間が必要となるからである。加えて、ＭＭＸ／ＳＳＥ演算の結果に基づく条件ジャンプはインテルのアーキテクチャにおいて真っ直ぐなものではなく、それは、状態フラッグがこれらのインストラクションによって設定されないからである。
【００６１】
最高のスピードを達成するために、計算において繰り返し用いられるメモリは、好ましくはマイクロプロセッサの第一レベルのキャッシュに含まれるべきである。問い合わせシーケンス・スコア・プロフィールに加えて、最後の列からのｈおよびｅ値を蓄積するベクトルはまた、キャッシュにも合うものでなければならないが、これらは通常平均的なシーケンスについて各々約４００バイトに過ぎない。
【００６２】
ＭＭＸレジスタと共に用いられる６４ビットのメモリ・アクセスは、このましくはできる限り高速となるために８バイトの境界に置かれるべきである。データ構造を配列するときこのことを考慮している。コードの配列はまた、スピードに実質的な効果を有する。
【００６３】
コンピュータにデータベース全体を保持するのに十分な内部メモリが備えられるとき、メモリマップ型ファイルの使用がデータベースを読み取るのに有効な方法である。そしてシーケンス・ファイル全体をメモリにおける特定のアドレス範囲にマッピングすることができる。オペレーティング・システムは通常この方法で連続ファイルを読み取るのに最適化される。
【００６４】
（アプリケーション領域および産業上の利用）
本方法は一般に、一次元の信号、すなわち遺伝子のまたは生物の分子、音信号（例えば発話、音声、音楽）、あらゆる言語（人間、コンピュータ）のテキストまたはその他の現象を表す記号の２つの線形的なシーケンスをあらゆる形で比較するのに用いることができる。しかしながら、ヌクレオチドまたはアミノ酸のシーケンスの比較が最も明白なアプリケーションである。それは直接のペアとしてのシーケンスの比較（配列）およびデータベースの類似検索の双方に用いることができる。その方法は、２つのシーケンスの間の類似の量を定量化し、そしてデータベースのいずれのシーケンスが所定のシーケンスに最も類似するかを見出すのに用いることができる。最も類似するシーケンスは、しばしば問い合わせシーケンスと関係するか、一致する。
【００６５】
以下のタイプの比較およびデータベース検索が可能である。
−アミノ酸シーケンス（たんぱく質、酵素）の比較／配列。
−ヌクレオチド・シーケンス（ＤＮＡ、ＲＮＡ、ｍＲＮＡ、ｃＤＮＡ等）の比較／配列。
−ヌクレオチド問い合わせシーケンスがデータベースの全てのヌクレオチド・シーケンスと比較され、各データベース・シーケンスについてスコアが計算され、そして関係するスコアをもつデータベース・シーケンスが報告されるデータベース検索。
−アミノ酸問い合わせシーケンスがデータベースの全てのアミノ酸シーケンスと比較されるデータベース検索。
−データベース・シーケンスを全部で６つのフレームに変換した後の、可能なフレームシフトもまた考慮しての、たんぱく質問い合わせシーケンスとデータベースのヌクレオチド・シーケンスとの比較。
−問い合わせシーケンスを全部で６つのフレームに変換した後の、可能なフレームシフトもまた考慮しての、ヌクレオチド問い合わせシーケンスとデータベースのアミノ酸シーケンスとの比較。
−問い合わせシーケンスとデータベース・シーケンスとの双方を全部で６つのフレームに変換した後の、可能なフレームシフトもまた考慮しての、ヌクレオチド問い合わせシーケンスとデータベースのヌクレオチド・シーケンスとの比較。
【００６６】
本発明の方法の他の変形もまた可能である。
−問い合わせシーケンスが問い合わせプロフィール、例えば問い合わせポジションと可能なデータベース・シーケンス記号との全ての組み合わせについてのスコアの行列、で置き換えられるシーケンス配列またはデータベース検索。
−本方法がバンドもしくはそうでなければ配列マトリックスにおける制限領域に適用されるシーケンス配列。
−前置フィルタリング手順が全てのデータベース・シーケンスに適用された後に本方法がデータベースの部分集合に適用されるシーケンス・データベース類似検索。
−反復するシーケンスの領域、バイアスのかかった組成またはその他の低複雑性領域を除去するようにろ過され、マスクされている問い合わせシーケンスに本方法が適用されるシーケンス・データベース類似検索。
−各データベース・シーケンスについて結果として得られるスコアが各マッチの重要性を指示する統計上のパラメータの計算のための基礎であり、問い合わせおよびデータベース・シーケンスの長さおよび／または組成をスコアリングの構成（置換行列およびギャップ罰金関数の選択）に加えて考慮することにもよる発明の方法の実装。
−対称的な多重処理（ＳＭＰ）コンピュータへの発明の方法の実装。
−ネットワーク化されたコンピュータの一群への発明の方法の実装。
−ＳＩＭＤをレジスタ（ＳＷＡＲ）または他の形のマイクロパラレリズム内で用いることによる、ＳＩＭＤ演算のためのインストラクションが失われているか明確さが制限されるかするマイクロプロセッサへの発明の方法の実装。
−シーケンスのファミリからのシーケンス情報を用いて遠い関係にあるシーケンスを検出する、例えば、ＰＳＩＢＬＡＳＴ（アルトシュールらによる、１９９７年）に類似する双方向データベース同属検索アプリケーションの一部として
【００６７】
本方法は、バイオ情報科学内の以下のアプリケーションの一部として用いることができる。
−たんぱく質関数予測
−たんぱく質構造予測
−ＲＮＡ関数予測
−ＲＮＡ構造予測
−多重シーケンス配列
−シーケンス・クラスタリング
−たんぱく質ファミリ・グルーピング／クラスタリング
−ＤＮＡシーケンス・コンティグ（ｃｏｎｔｉｇ）アセンブリ
−ヌクレオチド・シーケンスにおける符号化シーケンス領域の検出
−系統発生ツリーの構築
−正確なシーケンス配列スコアの計算に関連するその他のあらゆるアプリケーション
【００６８】
発明の方法はまた、以下の製品において用いることができる。
−前述のアルゴリズムを実装するソフトウェアを含む汎用コンピュータ・システム
【００６９】
前記製品と等価のものは以下の通りである。
−前述の方法を実装するデジタル信号処理装置を用いる他のコンピュータ・システム
−前述の方法を内蔵する電子回路の形での専用ハードウェア解決策、例えば、専用集積回路（ＡＳＩＣ）、フィールド・プログラム可能ゲート・アレイ（ＦＰＧＡ）またはカスタム超大規模集積回路（ＶＬＳＩ）チップ。この発明の開示に概説された方法のＶＨＤＬハードウェア記述言語を用いると、当業者に良く知られているようにＶＨＤＬ合成ツールが選択された技術を支援する限り、本方法の電子装置実装のいかなる形をも達成することができる。
【００７０】
（参考文献）
アルパーン（Ａｌｐｅｒｎ）Ｂ、カーター（Ｃａｒｔｅｒ）Ｌおよびガトリン（Ｇａｔｌｉｎ）Ｋ．Ｓ（１９９５年）によるマイクロパラレリズムおよび構成のたんぱく質整合１９９５年ＡＣＭ／ＩＥＥＥスーパーコンピューティング会議、カリフォルニア州サンジエゴ、１９９５年１２月３日から８日の会報において。ｈｔｔｐ：／／ｗｗｗ．ｓｕｐｅｒｃｏｍｐ．ｏｒｇ／ｓｃ９５／ｐｒｏｃｅｅｄｉｎｇｓ／５４９＿ＬＣＡＲ／ＳＣ９５．ＨＴＭ
アルトシュール（Ａｌｔｓｃｈｕｌ）Ｓ．Ｆ、ギッシュ（Ｇｉｓｈ）Ｗ、ミラー（Ｍｉｌｌｅｒ）Ｗ、マイヤーズ（Ｍｙｅｒｓ）Ｅ．Ｗおよびリップマン（Ｌｉｐｍａｎ）Ｄ．Ｊ（１９９０年）による基礎局部配列検索ツールＪ．Ｍｏｌ．Ｂｉｏｌ、２１５、４０３−４１０。
アルトシュールＳ．Ｆ、メイドン（Ｍａｄｄｅｎ）Ｔ．Ｌ、シャファー（Ｓｃｈａｆｆｅｒ）Ａ．Ａ、ツァン（Ｚｈａｎｇ）Ｊ、ツァン（Ｚｈａｎｇ）Ｚ、ミラーＷおよびリップマンＤ．Ｊ（１９９７年）によるギャップのあるＢＬＡＳＴおよびＰＳＩ−ＢＬＡＳＴによる新しい世代のたんぱく質データベース検索プログラム。Ｎｕｃｌｅｉｃ．Ａｃｉｄｓ．Ｒｅｓ、２５、３３８９−３４０２。
バイローチ（Ｂａｉｒｏｃｈ）Ａおよびアプワイラー（Ａｐｗｅｉｌｅｒ）Ｒ（２０００年）による２０００年のＳＷＩＳＳ−ＰＲＯＴたんぱく質シーケンス・データベースおよびそのサプルメントＴｒＥＭＢＡ。Ｎｕｃｌｅｉｃ．Ａｃｉｄｓ．Ｒｅｓ、２８、４５−４８。
バートン（Ｂａｒｔｏｎ）Ｇ、ウェバー（Ｗｅｂｂｅｒ）Ｃ、サール（Ｓｅａｒｌｅ）Ｓ．Ｍ．Ｊ（２０００年）ＳＣＡＮＰＳの新しい開発：完全ダイナミック・プログラミングおよびオンザフライ統計での高性能並列反復たんぱく質シーケンス検索。分子生物学のためのインテリジェントなシステム（ＩＳＭＢ）２０００年。（ポスター）（未公刊）ｈｔｔｐ：／／ｉｓｍｂ２０００．ｓｄｓｃ．ｅｄｕ／９８ｐｄｆｓ／ＴｕｅｓＳＡ／Ｂａｒｔｏｎ．ｐｄｆ
ベンソン（Ｂｅｎｓｏｎ）Ｄ．Ａ、カーッシュ−ミズラッキ（Ｋａｒｓｃｈ−Ｍｉｚｒａｃｈｉ）Ｉ、リップマンＤ．Ｊ、オステル（Ｏｓｔｅｌｌ）Ｊ、ラップ（Ｒａｐｐ）Ｂ．Ａおよびウィーラー（Ｗｈｅｅｌｅｒ）Ｄ．Ｌ（２０００年）ＧｅｎＢａｎｋ。Ｎｕｃｌｅｉｃ．Ａｃｉｄｓ．Ｒｅｓ、２８、１５−１８。
ブラットラグ（Ｂｒｕｔｌａｇ）Ｄ．Ｌ、ドートリコート（Ｄａｕｔｒｉｃｏｕｒｔ）Ｊ．Ｐ、ディアス（Ｄｉａｚ）Ｒ、フィーア（Ｆｉｅｒ）Ｊ、モクソン（Ｍｏｘｏｎ）Ｂおよびスタム（Ｓｔａｍｍ）Ｒ（１９９３年）によるＢＬＡＺＥ：大量並列コンピュータへのスミス−ウォターマンのシーケンス比較アルゴリズムの実装。Ｃｏｍｐｕｔｅｒｓ＆Ｃｈｅｍｉｓｔｒｙ、１７、２０３−２０７。
デュベイ（Ｄｕｂｅｙ）Ｐ．Ｋ（１９９８年）によるメディアプロセッシングのアーキテクチャーおよびデザインの実装。ｈｔｔｐ：／／ｗｗｗ．ｒｅｓｅａｒｃｈ．ｉｂｍ．ｃｏｍ／ｐｅｏｐｌｅ／ｐ／ｐｒａｄｅｅｐ／ｔｕｔｏｒ．ｈｔｍｌ
ギッシュＷ（１９９６年）によるＷＵ−ＢＬＡＳＴ。ｈｔｔｐ：／／ｂｌａｓｔ．ｗｕｓｔｌ．ｅｄｕ／
ゴトウＯ（１９８２年）による生物学上のシーケンスに整合する改善アルゴリズム。Ｊ．Ｍｏｌ．Ｂｉｏｌ、１６２、７０５−７０８。
グリーン（Ｇｒｅｅｎ）Ｐ（１９９３年）によるＳＷＡＴ。ｈｔｔｐ：／／ｗｗｗ．ｇｅｎｏｍｅ．ｗａｓｈｉｎｇｔｏｎ．ｅｄｕ／ｕｗｇｃ／ａｎａｌｙｓｉｓｔｏｏｌｓ／ｓｗａｔ．ｈｔｍ
ヘニコフ（Ｈｅｎｉｋｏｆｆ）ＳおよびヘニコフＪ．Ｇ（１９９２年）によるたんぱく質ブロックからのアミノ酸置換行列。Ｐｒｏｃ．Ｎａｔｌ．Ａｃａｄ．ＳｃｉＵ．Ｓ．Ａ、８９、１０９１５−１０９１９。
フーゲイ（Ｈｕｇｈｅｙ）Ｒ（１９９６年）によるシーケンスの比較と配列のための並列ハードウェア。Ｃｏｍｐｕｔ．Ａｐｐｌｉｃ．Ｂｉｏｓｃｉ、１２、４７３−４７９。
インテル（１９９９年）によるインテル・アーキテクチャ・ソフトウェア開発者のマニュアル第２巻インストラクション・セット照会。ｈｔｔｐ：／／ｄｅｖｅｌｏｐｅｒ．ｉｎｔｅｌ．ｃｏｍ／ｄｅｓｉｇｎ／ｐｅｎｔｉｕｍｉｉ／ｍａｎｕａｌｓ／２４３１９１．ｈｔｍ
インテル（２０００年）による予備ウィリアメット（Ｗｉｌｌａｍｅｔｔｅ）アーキテクチャ情報付きＩＡ−３２インテル・アーキテクチャ・ソフトウェア開発者のマニュアル第２巻インストラクション・セット照会。ｈｔｔｐ：／／ｄｅｖｅｌｏｐｅｒ．ｉｎｔｅｌ．ｃｏｍ／ｄｅｓｉｇｎ／ｐｒｏｃｅｓｓｏｒ／ｆｕｔｕｒｅ／ｍａｎｕａｌｓ／２４５４７１．ｈｔｍ
カーリン（Ｋａｒｌｉｎ）ＳおよびアルトシュールＳ．Ｆ（１９９０年）による、一般的なスコアリング構成を用いることによる分子シーケンスの特長の統計的な重要性を査定する方法。Ｐｒｏｃ．Ｎａｔｌ．Ａｃａｄ．Ｓｃｉ．ＵＳＡ、８７、２２６４−２２６８。
モトローラ（１９９８年）によるＡｌｔｉＶｅｃテクノロジー・プログラミング環境マニュアル。ｈｔｔｐ：／／ｗｗｗ．ｍｏｔ．ｃｏｍ／ＳＰＳ／ＰｏｗｅｒＰＣ／ｔｅｋｓｕｐｐｏｒｔ／ｔｅｋｌｉｂｒａｒｙ／ｍａｎｕａｌｓ／ａｌｔｉｖｅｃ＿ｐｅｍ．ｐｄｆ
ピアソン（Ｐｅａｒｓｏｎ）Ｗ．Ｒ（１９９１年）による、検索たんぱく質シーケンス・ライブラリ：スミス−ウォターマンおよびＦＡＳＴＡアルゴリズムの感度および選択性の比較。Ｇｅｎｏｍｉｃｓ、１１、６３５−６５０。
ピアソンＷ．ＲおよびリップマンＤ．Ｊ（１９８８年）による、生物学上のシーケンスの比較のための改善ツール。Ｐｒｏｃ．Ｎａｔｌ．Ａｃａｄ．ＳｃｉＵ．Ｓ．Ａ、８５、２４４４−２４４８。
ログネス（Ｒｏｇｎｅｓ）Ｔおよびシーバーグ（Ｓｅｅｂｅｒｇ）Ｅ（２０００年）による、共通のマイクロプロセッサでの並列処理を用いるスミス−ウォターマンのシーケンス・データベース検索の６倍のスピードアップ。Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ。印刷中。
スミス（Ｓｍｉｔｈ）Ｔ．Ｆおよびウォターマン（Ｗａｔｅｒｍａｎ）Ｍ．Ｓ（１９８１年）共通分子シーケンスの識別。Ｊ．Ｍｏｌ．Ｂｉｏｌ、１４７、１９５−１９７。
スターロック（Ｓｔｕｒｒｏｃｋ）Ｓ．Ｓおよびコリンズ（Ｃｏｌｌｉｎｓ）Ｊ．Ｆ（１９９３年）による、ＭＰｓｒｃｈ　Ｖ１．３ユーザー・ガイド。バイオコンピューティング検索ユニット、エジンバラ大学、ＵＫ。
スターロックＳ．ＳおよびコリンズＪ．Ｆ（２０００年）による、ＭＰｓｒｃｈ　Ｖ４．０。バイオコンピューティング検索ユニット、エジンバラ大学、ＵＫ。未公刊。検索およびいくらかの情報がｈｔｔｐ：／／ｗｗｗ．ｅｂｉ．ａｃ．ｕｋ／ＭＰｓｒｃｈ／にて入手可能
テイラー（Ｔａｙｌｏｒ）Ｓ（１９９８年）による、単一インストラクション多重データ（ＳＩＭＤ）を用いるスミス−ウォターマンのアルゴリズムの最適化のためのアーキテクチャおよび実装。ｈｔｔｐ：／／ｗｗｗ．ｓｔａｎｆｏｒｄ．ｅｄｕ／〜ｓｎｔａｙｌｏｒ／ｂｉｏｃ２１８／ｆｉｎａｌ．ｈｔｍ
テイラーＳ（１９９９年）による、スミス−ウォターマンのアルゴリズムへのＭＭＸ技術の適用。ｈｔｔｐ：／／ｗｗｗ．ｓｔａｎｆｏｒｄ．ｅｄｕ／〜ｓｎｔａｙｌｏｒ／ｍｉｓ２９９／ｒｅｐｏｒｔ．ｈｔｍ
ウートン（Ｗｏｏｔｔｏｎ）Ｊ．Ｃおよびフェダーヘン（Ｆｅｄｅｒｈｅｎ）Ｓ（１９９３年）によるアミノ酸シーケンスおよびシーケンス・データベースにおける局部的な複雑さの統計。Ｃｏｍｐｕｔｅｒｓ＆Ｃｈｅｍｉｓｔｒｙ、１７、１４９−１６３。
ウォズニアック（Ｗｏｚｎｉａｋ）Ａによる、ビデオ適応のインストラクションを用いてのシーケンス比較のスピードアップ。Ｃｏｍｐｕｔ．Ａｐｐｌ．Ｂｉｏｓｃｉ、１３、１４５−１５０。
【図面の簡単な説明】
【図１】
スミス−ウォターマン配列行列における計算上の依存関係を例示し、矢印は、配列行列の各セルにおけるｈ−、ｅ−およびｆ−値の計算に関連する行列セル間の依存関係を指示する。
【図２ａ】
スミス−ウォターマンのアルゴリズムのＳＩＭＤ実装におけるベクトルの配列を例示し、各列はデータベース・シーケンスのひとつの記号を表し、かつ各列は問い合わせシーケンスのひとつの記号を表し、行列においてマイナーな対角線に平行なベクトルで伝統的なアプローチを表し、かつ
【図２ｂ】
同じく、問い合わせシーケンスに平行なベクトルで新規なアプローチを表す。
【図３ａ】
ベクトル計算の依存関係を例示し、矢印は、伝統的なベクトルの要素におけるｈ−、ｅ−およびｆ−値の計算に関連する行列セル間の相互関係を指示する図。
【図３ｂ】
同じく、新規なアプローチを用いる行列セル間の相互関係を指示する図。
【図４ａ】
新しいアプローチのための擬似コードを例示し、その擬似コードは、われわれの方法がどのようにコンピュータプログラムに実装されるのかを示す詳細な例に過ぎないものである。
【図４ｂ】
図４ａの擬似コードのフローチャートを例示する。
【図１】
2004510265.tif 000007
【図２ａ】
2004510265.tif 000008
【図２ｂ】
2004510265.tif 000009
【図３ａ】
2004510265.tif 000010
【図３ｂ】
2004510265.tif 000011
【図４ａ】
2004510265.tif 000012
【図４ｂ】
2004510265.tif 000013
【国際公開パンフレット】
2004510265.tif 000014
2004510265.tif 000015
2004510265.tif 000016
2004510265.tif 000017
2004510265.tif 000018
2004510265.tif 000019
2004510265.tif 000020
2004510265.tif 000021
2004510265.tif 000022
2004510265.tif 000023
2004510265.tif 000024
2004510265.tif 000025
2004510265.tif 000026
2004510265.tif 000027
2004510265.tif 000028
2004510265.tif 000029
2004510265.tif 000030
2004510265.tif 000031
2004510265.tif 000032
2004510265.tif 000033
2004510265.tif 000034
2004510265.tif 000035
2004510265.tif 000036
2004510265.tif 000037
2004510265.tif 000038
2004510265.tif 000039
2004510265.tif 000040
2004510265.tif 000041
2004510265.tif 000042
2004510265.tif 000043
2004510265.tif 000044
2004510265.tif 000045
2004510265.tif 000046
2004510265.tif 000047
2004510265.tif 000048
2004510265.tif 000049
【国際調査報告】
2004510265.tif 000050
2004510265.tif 000051