(57)【要約】  生物学的配列類似検索を実行するためのシステムおよび方法を開示する。マッチングステージを備えるパイプラインを含むように構成されたプログラム可能論理デバイスを含み、マッチングステージは複数の生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の可能な複数のマッチを含むデータストリームを受け取るように構成されている。パイプラインは、さらに、マッチングステージの下流のところに配置されている無ギャップ伸長前置フィルタステージを備えることができ、前置フィルタステージは生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の複数のパターンマッチを次から次へと見ていって、ユーザー定義スコアを超えるパターンマッチのみが前置フィルタステージの下流を通るようにスコアを付けるように構成されている。マッチングステージは、少なくとも１つのＢｌｏｏｍフィルタを備えることができる。
2008532177.tif 000002
【特許請求の範囲】
【請求項１】
生物学的配列類似検索を実行するためのデジタル論理回路であって、
Ｂｌｏｏｍフィルタステージを備えるパイプラインを含むように構成されたプログラム可能論理デバイスを含み、Ｂｌｏｏｍフィルタステージは複数の生物学的配列データ文字列を含むデータストリームを受け取り、生物学的配列データストリームをフィルタ処理して、配列データ文字列と問い合わせ文字列の複数の部分文字列との間の可能な複数のマッチを識別するように構成されている、デジタル論理回路。
【請求項２】
プログラム可能論理デバイスが、ＦＰＧＡを含む、請求項１に記載の回路。
【請求項３】
生物学的配列類似検索パイプラインが、ＢＬＡＳＴ用の第１のステージを備える、請求項２に記載の回路。
【請求項４】
ＢＬＡＳＴ第１ステージが、ＢＬＡＳＴＮ用の第１のステージを含む、請求項３に記載の回路。
【請求項５】
ＢＬＡＳＴ第１ステージが、ＢＬＡＳＴＰ、ＢＬＡＳＴＸ、ＴＢＬＡＳＴＮ、およびＴＢＬＡＳＴＸからなる群から選択されたもの用の第１のステージを含む、請求項３に記載の回路。
【請求項６】
Ｂｌｏｏｍフィルタステージが、複数の並列Ｂｌｏｏｍフィルタを備える、請求項３に記載の回路。
【請求項７】
複数の並列Ｂｌｏｏｍフィルタが、パイプラインを通して生物学的配列データストリームを処理するのに先立って複数の問い合わせで部分文字列でプログラムされる、請求項６に記載の回路。
【請求項８】
複数の並列Ｂｌｏｏｍフィルタのそれぞれが、同じ問い合わせ部分文字列でプログラムされる、請求項７に記載の回路。
【請求項９】
それぞれのＢｌｏｏｍフィルタが、ＦＰＧＡ上のデュアルポートＢＲＡＭにアクセスするように構成され、デュアルポートＢＲＡＭは、４ポートＢＲＡＭを複製するためにダブルクロック化される、請求項８に記載の回路。
【請求項１０】
それぞれのデュアルポートＢＲＡＭへのアクセスが、４つの並列Ｂｌｏｏｍフィルタにより共有される、請求項９に記載の回路。
【請求項１１】
それぞれのＢｌｏｏｍフィルタが、ＦＰＧＡ上のデュアルポートＢＲＡＭにアクセスするように構成され、デュアルポートＢＲＡＭが、６ポートＢＲＡＭを複製するためにトリプルクロック化される、請求項８に記載の回路。
【請求項１２】
それぞれのデュアルポートＢＲＡＭへのアクセスが、少なくとも６つの並列Ｂｌｏｏｍフィルタにより共有される、請求項１１に記載の回路。
【請求項１３】
それぞれのＢｌｏｏｍフィルタが、ｋ個のハッシュ関数とｋ（１×ｍ）ビットメモリユニットを使用するように構成され、それぞれのメモリユニットはそのＢｌｏｏｍフィルタのハッシュ関数のうちの１つに対応し、それぞれのハッシュ関数は受け取った配列文字列をその対応するメモリユニット内のビットにマップして可能なマッチが存在するかどうかを判定するように構成されている、請求項８に記載の回路。
【請求項１４】
それぞれのメモリユニットが、デュアルポートＢＲＡＭユニットを含む、請求項１３に記載の回路。
【請求項１５】
それぞれのデュアルポートＢＲＡＭユニットへのアクセスが、複数のＢｌｏｏｍフィルタにより共有される、請求項１３に記載の回路。
【請求項１６】
それぞれのデュアルポートＢＲＡＭユニットが、複数のＢｌｏｏｍフィルタのうちの少なくとも４つにより共有されるようにダブルクロック化される、請求項１５に記載の回路。
【請求項１７】
パイプラインは、さらに、Ｂｌｏｏｍフィルタステージの下流にハッシングステージを備え、ハッシングステージは可能なマッチを問い合わせ文字列内の少なくとも１つの位置にマップするように構成されている、請求項７に記載の回路。
【請求項１８】
さらに、ハッシングステージと連絡しているメモリを備え、メモリはハッシュテーブルを格納するように構成され、ハッシュテーブルは可能なマッチについて問い合わせ文字列内の位置への少なくとも１つのポインタを格納する、請求項１７に記載の回路。
【請求項１９】
ハッシングステージが、完全ハッシングステージを含む、請求項１７に記載の回路。
【請求項２０】
ハッシングステージが、完全に近いハッシングステージを含む、請求項１７に記載の回路。
【請求項２１】
完全に近いハッシングステージが、ハッシュ関数のＨ３ファミリから選択された関数ＡおよびＢとともに構成され、ＡおよびＢが、完全階数を持つことが保証される、請求項２０に記載の回路。
【請求項２２】
さらに、ハッシングステージの下流に冗長性フィルタを備え、冗長性フィルタはハッシングステージから可能なマッチを表すデータを受け取り、選択可能な冗長度の範囲内で前の可能なマッチに関して冗長である可能なマッチを除去するように構成されている、請求項１７に記載の回路。
【請求項２３】
冗長性フィルタが、ＦＰＧＡ上に実装される、請求項２２に記載の回路。
【請求項２４】
さらに、ＦＰＧＡと連絡するデータベースを備え、データベースはＦＰＧＡを通してストリーミングされる生物学的配列を格納するように構成されている、請求項３に記載の回路。
【請求項２５】
シードアライメント検索を実行するシステムであって、
シードアライメント検索パイプラインを実装するように構成されたプログラム可能論理デバイスを備え、パイプラインはＢｌｏｏｍフィルタステージを備え、Ｂｌｏｏｍフィルタステージは複数のデータ文字列を含むデータストリームを受け取り、データストリームをフィルタ処理してストリームデータ文字列と問い合わせ文字列の複数の部分文字列との間の可能な複数のマッチを識別するように構成されている、システム。
【請求項２６】
プログラム可能論理デバイスが、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）を含む、請求項２５に記載のシステム。
【請求項２７】
生物学的配列類似検索を実行するための方法であって、
プログラム可能論理デバイス上に実装されたＢｌｏｏｍフィルタステージを通して生物学的配列データストリームを処理することと、生物学的配列データストリームは複数の生物学的配列データ文字列を含み、Ｂｌｏｏｍフィルタステージは問い合わせ文字列の複数の部分文字列によりプログラムされ、生物学的配列データ文字列と問い合わせ部分文字列との間の可能な複数のマッチを識別するように構成されているＢｌｏｏｍフィルタを備えることとを含む、方法。
【請求項２８】
Ｂｌｏｏｍフィルタが、さらに、生物学的配列データストリーム内でそれぞれの可能なマッチの位置を識別するように構成される、請求項２７に記載の方法。
【請求項２９】
プログラム可能論理デバイスが、ＦＰＧＡを含む、請求項２８に記載の方法。
【請求項３０】
さらに、ＢＬＡＳＴ用の第１のステージの一部として処理ステップを実行することを含む、請求項２９に記載の方法。
【請求項３１】
ＢＬＡＳＴ第１ステージが、ＢＬＡＳＴＮ用の第１のステージを含む、請求項３０に記載の方法。
【請求項３２】
ＢＬＡＳＴ第１ステージが、ＢＬＡＳＴＰ、ＢＬＡＳＴＸ、ＴＢＬＡＳＴＮ、およびＴＢＬＡＳＴＸからなる群から選択されたもの用の第１のステージを含む、請求項３０に記載の方法。
【請求項３３】
Ｂｌｏｏｍフィルタステージが、複数の並列Ｂｌｏｏｍフィルタを備える、請求項３０に記載の方法。
【請求項３４】
さらに、
Ｂｌｏｏｍフィルタステージを通して生物学的配列データストリームを処理するのに先立って複数の問い合わせ部分文字列で並列Ｂｌｏｏｍフィルタをプログラムすることを含む、請求項３３に記載の方法。
【請求項３５】
プログラムステップが、並列Ｂｌｏｏｍフィルタのそれぞれを同じ問い合わせ部分文字列でプログラムすることを含む、請求項３３に記載の方法。
【請求項３６】
Ｂｌｏｏｍフィルタステージが、複数のデュアルポートＢＲＡＭユニットを備え、この方法は４ポートＢＲＡＭユニットを複製するためにＢＲＡＭユニットをダブルクロック化することを含む、請求項３５に記載の方法。
【請求項３７】
それぞれのデュアルポートＢＲＡＭユニットが、４つの並列Ｂｌｏｏｍフィルタによりアクセスされる、請求項３６に記載の方法。
【請求項３８】
Ｂｌｏｏｍフィルタステージが、複数のデュアルポートＢＲＡＭユニットを備え、この方法は６ポートＢＲＡＭユニットを複製するためにＢＲＡＭユニットをトリプルクロック化することを含む、請求項３５に記載の方法。
【請求項３９】
それぞれのデュアルポートＢＲＡＭユニットが、６つの並列Ｂｌｏｏｍフィルタによりアクセスされる、請求項３８に記載の方法。
【請求項４０】
さらに、ハッシングステージを介してＢｌｏｏｍフィルタステージからのそれぞれの可能なマッチを可能なマッチを引き起こした問い合わせ部分文字列に対応する問い合わせ文字列内の位置にマップすることを含む、請求項３４に記載の方法。
【請求項４１】
マッピングステップが、ＦＰＧＡにより少なくとも部分的に実行される、請求項４０に記載の方法。
【請求項４２】
マッピングステップが、完全ハッシングステージを介してマッピングを実行することを含む、請求項４１に記載の方法。
【請求項４３】
マッピングステップが、完全に近いハッシングステージを介してマッピングを実行することを含む、請求項４１に記載の方法。
【請求項４４】
完全に近いハッシングステージが、ハッシュ関数のＨ３ファミリから選択された関数ＡおよびＢとともに構成され、ＡおよびＢが、完全階数を持つことが保証される、請求項４３に記載の方法。
【請求項４５】
さらに、選択可能な冗長度の範囲内で他の可能なマッチについて冗長である可能なマッチを除去することを含む、請求項４０に記載の方法。
【請求項４６】
除去ステップが、ＦＰＧＡにより少なくとも部分的に実行される、請求項４５に記載の方法。
【請求項４７】
一組の文字列をキーにマップする際に使用するハッシュテーブルを生成するためのシステムであって、
それぞれの文字列に対応する、ハッシュ関数のＨ３ファミリを使用して、ハッシュテーブル内の位置を識別するため一組の文字列に対し完全に近いハッシングを実行し、ハッシュテーブルを生成するように構成され、ハッシュテーブルはそこのそれぞれの識別された位置でキーを格納するように構成されている、プロセッサと、
ハッシュテーブルを格納するためにプロセッサと連絡しているメモリとを備え、プロセッサは、完全階数を持つことが保証されている、ハッシュ関数のＨ３ファミリを使用する、ハッシュ関数を介して完全に近いハッシングを行うように構成されている、システム。
【請求項４８】
一組の部分文字列をより大きな文字列内の位置にマップする際に使用するハッシュテーブルを生成するためのシステムであって、
それぞれの部分文字列に対応する、ハッシュテーブル内の位置を識別するため一組の部分文字列に対し完全に近いハッシングを実行し、ハッシュテーブルを生成するように構成され、ハッシュテーブルはそこのそれぞれの識別された位置で、より大きな文字列内のそれぞれの部分文字列の位置へのポインタを格納するように構成されている、プロセッサと、
ハッシュテーブルを格納するためプロセッサと連絡しているメモリとを備える、システム。
【請求項４９】
生物学的配列類似検索を実行するためのデジタル論理回路であって、
マッチングステージを含むパイプラインを備えるように構成されたプログラム可能論理デバイスを備え、マッチングステージは複数の生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の可能な複数のマッチを含むデータストリームを受け取るように構成され、パイプラインは、さらに、マッチングステージの下流のところに配置されている前置フィルタステージを備え、無ギャップ伸長前置フィルタステージは生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の複数のパターンマッチを次から次へと見ていって、ユーザー定義スコアを超えるパターンマッチのみが無ギャップ伸長前置フィルタステージの下流を通るようにスコアを付けるように構成されている、デジタル論理回路。
【請求項５０】
プログラム可能論理デバイスが、ＦＰＧＡを含む、請求項４９に記載の回路。
【請求項５１】
マッチングステージが、ＢＬＡＳＴ用の第１のステージの少なくとも一部を含み、無ギャップ伸長前置フィルタステージが、ＢＬＡＳＴ用の第２のステージの少なくとも一部を含む、請求項４９に記載の回路。
【請求項５２】
ＢＬＡＳＴ第１ステージが、ＢＬＡＳＴＮ、ＢＬＡＳＴＰ、ＢＬＡＳＴＸ、ＴＢＬＡＳＴＮ、およびＴＢＬＡＳＴＸ用の第１のステージからなる群から選択され、ＢＬＡＳＴ第２ステージが、ＢＬＡＳＴＮ、ＢＬＡＳＴＰ、ＢＬＡＳＴＸ、ＴＢＬＡＳＴＮ、およびＴＢＬＡＳＴＸ用の第２のステージからなる群から選択される、請求項５１に記載の回路。
【請求項５３】
ワードマッチングステージが、さらに、Ｂｌｏｏｍフィルタステージを含む、請求項４９に記載の回路。
【請求項５４】
Ｂｌｏｏｍフィルタステージが、複数のＢｌｏｏｍフィルタを備える、請求項５３に記載の回路。
【請求項５５】
ワードマッチングステージが、さらに、Ｂｌｏｏｍフィルタステージの下流にハッシングステージを備え、ハッシングステージは可能なマッチを問い合わせ文字列内の少なくとも１つの位置にマップするように構成されている、請求項５３に記載の回路。
【請求項５６】
さらに、ハッシングステージの下流に冗長性フィルタを備え、冗長性フィルタはハッシングステージから可能なマッチを表すデータを受け取り、選択可能な冗長度の範囲内で前の可能なマッチに関して冗長である可能なマッチを除去するように構成されている、請求項５５に記載の回路。
【請求項５７】
無ギャップ伸長前置フィルタステージが、伸長コントローラ、ウィンドウルックアップモジュール、およびスコアリングモジュールを備える、請求項４９に記載の回路。
【請求項５８】
無ギャップ伸長前置フィルタステージが、マッチングスコア、ミスマッチングスコア、およびカットオフ閾値からなる群から選択されたパラメータを使用する、請求項４９に記載の回路。
【請求項５９】
無ギャップ伸長前置フィルタステージが、伸長コントローラを備える、請求項４９に記載の回路。
【請求項６０】
伸長コントローラが、ハードウェア、ファームウェア、およびソフトウェアのうちの少なくとも１つを備える、請求項５９に記載の回路。
【請求項６１】
伸長コントローラが、複数の生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の所定の長さの複数の可能なパターンマッチに対する少なくとも１つの第１の入力および生物学的配列データに対する少なくとも１つの第２の入力を含む複数のデータ入力を備える、請求項５９に記載の回路。
【請求項６２】
少なくとも１つの第２の入力が、マッチスコア、ミスマッチスコア、またはカットオフ閾値からなる群から選択されたパラメータを制御するためのコマンドを受信することができる、請求項６１に記載の回路。
【請求項６３】
伸長コントローラが、少なくとも１つの第２の入力により受け取った生物学的データを解析して、共有コマンドおよび所定の長さのパターンマッチを逆多重化してから、ウィンドウルックアップモジュールに送る、請求項５７に記載の回路。
【請求項６４】
無ギャップ伸長前置フィルタステージが、ウィンドウルックアップモジュールを備える、請求項４９に記載の回路。
【請求項６５】
ウィンドウルックアップモジュールが、生物学的配列データの少なくとも１つの部分文字列および問い合わせ文字列の少なくとも１つの部分文字列を取り込み、分析に使用できる生物学的データの定義済みウィンドウを形成することができる、請求項６４に記載の回路。
【請求項６６】
ウィンドウルックアップモジュールが、データベースバッファ内の生物学的配列データの少なくとも１つの部分文字列、問い合わせバッファ内の問い合わせ文字列の少なくとも１つの部分文字列、生物学的配列データの少なくとも１つの部分文字列に対するオフセット、および問い合わせ文字列の少なくとも１つの部分文字列に対するオフセットを受け取り、ウィンドウルックアップモジュールが、複数のバッファモジュールに渡されるウィンドウの先頭を計算し、複数のバッファモジュールが、問い合わせ文字列の少なくとも１つの部分文字列および生物学的配列データの少なくとも１つの部分文字列を出力ステージに移動して、分析に使用できる生物学的データの少なくとも１つの定義済みウィンドウを作成する、請求項６４に記載の回路。
【請求項６７】
生物学的配列データの少なくとも１つの部分文字列および問い合わせ文字列の少なくとも１つの部分文字列が、複数のＢＲＡＭ上にバッファリングされる、請求項６５に記載の回路。
【請求項６８】
無ギャップ伸長前置フィルタステージが、スコアリングモジュールを備える、請求項４９に記載の回路。
【請求項６９】
スコアリングモジュールが、定義済みウィンドウ内で生物学的データを取り込むことができる、請求項６８に記載の回路。
【請求項７０】
スコアリングモジュールが、アルゴリズム命令の少なくとも１つの反復を使用する、請求項６９に記載の回路。
【請求項７１】
スコアリングモジュールが、さらに、塩基比較器、複数のスコアリングステージ、および閾値比較器を備える、請求項６８に記載の回路。
【請求項７２】
スコアリングモジュールが、さらに、塩基比較器を備える、請求項６８に記載の回路。
【請求項７３】
塩基比較器が、生物学的配列データの部分文字列および問い合わせ文字列の部分文字列の少なくとも１つのペアを受け取り、これらの値同士を比較し、少なくとも１つの比較スコアを得る、請求項７２に記載の回路。
【請求項７４】
少なくとも１つの比較スコアが、それぞれのマッチするペアに対しては正の値、それぞれのミスマッチのペアに対しては負のスコアを含む、請求項７３に記載の回路。
【請求項７５】
少なくとも１つの比較スコアが、ルックアップテーブル上に配置されている値で置換される、請求項７３に記載の回路。
【請求項７６】
スコアリングモジュールが、さらに、複数のスコアリングステージを備える、請求項６８に記載の回路。
【請求項７７】
さらに、複数のスコアリングステージのうちのそれぞれの後の下流スコアリングステージからの少なくとも１つの比較スコアを破棄することを含む、請求項７６に記載の回路。
【請求項７８】
複数のスコアリングステージのうちの少なくとも１つのスコアリングステージが、生物学的配列データベースおよび所定のデータウィンドウ内の問い合わせ位置に加えて生物学的配列データの比較結果の群から選択された入力を受け取り、複数のスコアリングステージのうちの少なくとも１つのスコアリングステージが、複数のスコアリングステージのうちの少なくとも１つの他のスコアリングステージからの入力を受け取り、入力は、高スコアリング領域ペアのスコアおよび高スコアリング領域ペアの端点からなる群から選択される、請求項７６に記載の回路。
【請求項７９】
スコアリングモジュールが、さらに、閾値比較器を備える、請求項６８に記載の回路。
【請求項８０】
閾値比較器が、少なくとも１つのスコアを含む所定の長さのパターンマッチを取得し、少なくとも１つのスコアが所定の閾値を超えたかどうかを判定し、パターンマッチを下流に渡す、請求項７９に記載の回路。
【請求項８１】
閾値比較器が、所定の長さのパターンマッチを取得し、高スコアリング部分文字列が所定のデータウィンドウの境界を交差するかどうかを判定する、請求項７９に記載の回路。
【請求項８２】
生物学的配列類似検索を実行するための方法であって、
マッチングステージを備えるパイプラインを含むように構成されたプログラム可能論理デバイスで生物学的配列データストリームを処理し、マッチングステージは複数の生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の複数の可能なマッチを含むデータストリームを受け取るように構成されていることと、
パイプライン内のマッチングステージの下流のところに配置されている無ギャップ伸長前置フィルタステージを使用し、無ギャップ伸長前置フィルタステージは生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の複数のパターンマッチを次から次へと見ていって、ユーザー定義スコアを超えるパターンマッチのみが無ギャップ伸長前置フィルタステージの下流を通るようにスコアを付けるように構成されていることとを含む、方法。
【請求項８３】
プログラム可能論理デバイスが、ＦＰＧＡを含む、請求項８２に記載の方法。
【請求項８４】
マッチングステージが、ＢＬＡＳＴ用の第１のステージの少なくとも一部を使用することを含み、無ギャップ伸長前置フィルタステージが、ＢＬＡＳＴ用の第２のステージの少なくとも一部を使用することを含む、請求項８２に記載の回路。
【請求項８５】
ＢＬＡＳＴ第１ステージが、ＢＬＡＳＴＮ、ＢＬＡＳＴＰ、ＢＬＡＳＴＸ、ＴＢＬＡＳＴＮ、およびＴＢＬＡＳＴＸ用の第１のステージからなる群から選択され、ＢＬＡＳＴ第２ステージが、ＢＬＡＳＴＮ、ＢＬＡＳＴＰ、ＢＬＡＳＴＸ、ＴＢＬＡＳＴＮ、およびＴＢＬＡＳＴＸ用の第２のステージからなる群から選択される、請求項８４に記載の方法。
【請求項８６】
パイプラインのマッチングステージにおいてＢｌｏｏｍフィルタステージを使用することを含む、請求項８２に記載の方法。
【請求項８７】
Ｂｌｏｏｍフィルタステージが、複数のＢｌｏｏｍフィルタを備える、請求項８６に記載の方法。
【請求項８８】
さらに、Ｂｌｏｏｍフィルタステージの下流でハッシングステージを使用することと、ハッシングステージで可能なマッチを問い合わせ文字列内の少なくとも１つの位置にマップすることとを含む、請求項８６に記載の方法。
【請求項８９】
さらに、ハッシングステージの下流で冗長性フィルタを使用し、冗長性フィルタはハッシングステージから可能なマッチを表すデータを受け取るように構成されることを含み、さらに、選択可能な冗長度の範囲内で前の可能なマッチに関して冗長である可能なマッチを除去することを含む、請求項８８に記載の方法。
【請求項９０】
無ギャップ伸長前置フィルタステージが、伸長コントローラ、ウィンドウルックアップモジュール、およびスコアリングモジュールを備える、請求項８２に記載の方法。
【請求項９１】
さらに、無ギャップ伸長前置フィルタステージとともにマッチスコア、ミスマッチスコア、またはカットオフ閾値からなる群から選択されたパラメータを使用することを含む、請求項８２に記載の方法。
【請求項９２】
無ギャップ伸長前置フィルタステージが、伸長コントローラを備える、請求項８２に記載の方法。
【請求項９３】
伸長コントローラが、ハードウェア、ファームウェア、およびソフトウェアのうちの少なくとも１つを備える、請求項９２に記載の方法。
【請求項９４】
さらに、複数の生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の所定の長さの複数の可能なパターンマッチを少なくとも１つの第１の入力として受け取ることと、生物学的配列データを少なくとも１つの第２の入力で受け取ることとを含む、請求項９２に記載の方法。
【請求項９５】
さらに、マッチスコア、ミスマッチスコア、またはカットオフ閾値からなる群から選択されたパラメータを制御するためのコマンドを少なくとも１つの第２の入力で受け取ることを含む、請求項９４に記載の方法。
【請求項９６】
さらに、少なくとも１つの第２の入力により受け取ったデータを解析して、共有コマンドおよび所定の長さのパターンマッチを逆多重化してから、ウィンドウルックアップモジュールに送ることを含む、請求項９０に記載の方法。
【請求項９７】
無ギャップ伸長前置フィルタステージが、ウィンドウルックアップモジュールを備える、請求項８２に記載の方法。
【請求項９８】
さらに、生物学的配列データの少なくとも１つの部分文字列および問い合わせ文字列の少なくとも１つの部分文字列を取り込み、ウィンドウルックアップモジュールで分析用の生物学的データの定義済みウィンドウを形成することを含む、請求項９７に記載の方法。
【請求項９９】
さらに、
ウィンドウルックアップモジュールでデータベースバッファ内の生物学的配列データの少なくとも１つの部分文字列を受け取ることと、
ウィンドウルックアップモジュールで問い合わせバッファ内の問い合わせ文字列の少なくとも１つの部分文字列を受け取ることと、
生物学的配列データの少なくとも１つの部分文字列に対するオフセットおよびウィンドウの先頭を計算するために使用される問い合わせ文字列の少なくとも１つの部分文字列に対するオフセットを受け取ることと、
生物学的配列データの少なくとも１つの部分文字列に対するオフセットおよび問い合わせ文字列の少なくとも１つの部分文字列に対するオフセットを複数のバッファモジュールで移動することと、
生物学的配列データの少なくとも１つの部分文字列、問い合わせ文字列の少なくとも１つの部分文字列、生物学的配列データの少なくとも１つの部分文字列に対するオフセット、および問い合わせ文字列の少なくとも１つの部分文字列に対するオフセットに基づいて分析のため生物学的データの少なくとも１つの定義済みウィンドウを作成することとを含む、請求項９７に記載の方法。
【請求項１００】
さらに、生物学的配列データの少なくとも１つの部分文字列および問い合わせ文字列の少なくとも１つの部分文字列を複数のＢＲＡＭ上にバッファリングすることを含む、請求項９８に記載の方法。
【請求項１０１】
無ギャップ伸長前置フィルタステージが、スコアリングモジュールを備える、請求項８２に記載の方法。
【請求項１０２】
さらに、スコアリングモジュールで定義済みウィンドウ内に生物学的データを取り込むことを含む、請求項１０１に記載の方法。
【請求項１０３】
さらに、スコアリングモジュールでアルゴリズム命令の少なくとも１つの反復を使用することを含む、請求項１０１に記載の方法。
【請求項１０４】
スコアリングモジュールが、さらに、塩基比較器、複数のスコアリングステージ、および閾値比較器を備える、請求項１０１に記載の方法。
【請求項１０５】
スコアリングモジュールが、さらに、塩基比較器を備える、請求項１０１に記載の方法。
【請求項１０６】
さらに、生物学的配列データの部分文字列および問い合わせ文字列の部分文字列の少なくとも１つのペアを受け取ることと、塩基比較器でこれらの値同士を比較し、少なくとも１つの比較スコアを取得することとを含む、請求項１０５に記載の方法。
【請求項１０７】
少なくとも１つの比較スコアが、それぞれのマッチするペアに対しては正の値、それぞれのミスマッチのペアに対しては負のスコアを含む、請求項１０６に記載の方法。
【請求項１０８】
さらに、少なくとも１つの比較スコアをルックアップテーブル上に配置されている値で置換する、請求項１０６に記載の方法。
【請求項１０９】
スコアリングモジュールが、さらに、複数のスコアリングステージを備える、請求項１０１に記載の方法。
【請求項１１０】
さらに、複数のスコアリングステージのうちのそれぞれのステージに対する少なくとも１つの比較スコアを破棄することを含む、請求項１０９に記載の方法。
【請求項１１１】
さらに、複数のスコアリングステージの少なくとも１つのスコアリングステージで生物学的配列データおよび生物学的配列データベースおよび所定のデータウィンドウ内の問い合わせ位置の比較結果の群から選択された入力を受け取ることを含み、さらに、複数のスコアリングステージのうちの少なくとも１つの他のスコアリングステージからの高スコアリング領域ペアのスコアおよび高スコアリング領域ペアの端点からなる群から選択された入力を受け取ることを含む、請求項１０９に記載の方法。
【請求項１１２】
スコアリングモジュールが、さらに、閾値比較器を備える、請求項１０１に記載の方法。
【請求項１１３】
さらに、少なくとも１つのスコアを含む所定の長さのパターンマッチを取得し、少なくとも１つのスコアが所定の閾値を超えたかどうかを閾値比較器で判定し、パターンマッチを下流に渡すことを含む、請求項１１２に記載の方法。
【請求項１１４】
さらに、所定の長さのパターンマッチを取得し、高スコアリング部分文字列が所定のデータウィンドウの境界を交差するかどうかを閾値比較器で判定することを含む、請求項１１２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００５年３月３日に出願した米国仮出願第６０／６５８，４１８号の優先権を主張するものであり、また２００５年１１月１１日に出願した米国仮出願第６０／７３６，０８１号の優先権を主張するものである。
【０００２】
本発明は、生物学的配列類似検索の分野に関する。特に、本発明は、生物学的配列の大データベースから問い合わせ配列とマッチする文字列を検索する分野に関する。
【背景技術】
【０００３】
毎年作り出される生物学的配列データの量は、指数関数的に増大している。この膨大な量のデータから有用な情報を効率的に抽出することは、ますます困難な仕事になってきている。ゲノムＤＮＡとタンパク質配列のデータベースは、近代分子生物学に必須の情報源である。これは、これらのデータベースのコンピュータによる検索を行うことで、実験室において得られたＤＮＡ配列が知られている生物学的機能を持つ他の配列に類似していることを証明し、細胞内における役割と進化的時間にわたる歴史の両方を明らかにできる場である。１０年間のＤＮＡ配列決定法の改良の結果、ＮＣＢＩ  ＧｅｎＢａｎｋなどの生物学的配列データベースが指数関数的に増大し、ここ１０年間は１２ヶ月から１６ヶ月毎にサイズが倍になり、今や、文字数は４５０億個を超えるに至っている。こうした技術面の成果は、哺乳類のゲノム全体を含む、さらに多くの新しい配列ももたらし、検索エンジンは多忙を極めている。
【０００４】
この種類の検索の実施例は、Ｐ．Ｋｒｉｓｈｎａｍｕｒｔｈｙ、Ｊ．Ｂｕｈｌｅｒ、Ｒ．Ｄ．Ｃｈａｍｂｅｒｌａｉｎ、Ｍ．Ａ．Ｆｒａｎｋｌｉｎ、Ｋ．Ｇｙａｎｇ、およびＪ．Ｌａｎｃａｓｔｅｒらによる論文「Ｂｉｏｓｅｑｕｅｎｃｅ  Ｓｉｍｉｌａｒｉｔｙ  Ｓｅａｒｃｈ  Ｏｎ  Ｔｈｅ  Ｍｅｒｃｕｒｙ  Ｓｙｓｔｅｍ」（Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １５ｔｈ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｓｙｓｔｅｍｓ，Ａｒｃｈｉｔｅｃｔｕｒｅｓ，ａｎｄ  Ｐｒｏｃｅｓｓｏｒｓ  （ＡＳＡＰ０４）、２００４年９月、３６５〜３７５頁（２００４））で取りあげられている。他の実施例は、Ｋｗａｍｅ  Ｇｙａｎｇによる論文「ＮＣＢＩ  ＢＬＡＳＴＮ  ＳＴＡＧＥ  １  ＩＮ  ＲＥＣＯＮＦＩＧＵＲＡＢＬＥ  ＨＡＲＤＷＡＲＥ」（Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｅｎｇｉｎｅｅｒｉｎｇ、Ｗａｓｈｉｎｇｔｏｎ  Ｕｎｉｖｅｒｓｉｔｙ、２００４年８月、Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＷＵＣＳＥ−２００５−３０）である。他の実施例は、Ｃ．Ｂｅｈｒｅｎｓ、Ｊ．Ｌａｎｃａｓｔｅｒ、およびＢ．Ｗｕｎらによる論文「ＢＬＡＳＴＮ  Ｒｅｄｕｎｄａｎｃｙ  Ｆｉｌｔｅｒ  ｉｎ  Ｒｅｐｒｏｇｒａｍｒｎａｂｌｅ  Ｈａｒｄｗａｒｅ」（Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｅｎｇｉｎｅｅｒｉｎｇ、Ｗａｓｈｉｎｇｔｏｎ  Ｕｎｉｖｅｒｓｉｔｙ、Ｆｉｎａｌ  Ｐｒｏｊｅｃｔ  Ｓｕｂｍｉｓｓｉｏｎ、２００３年秋）である。これらの論文は、それぞれ、参照により本明細書に組み込まれている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
生物学的配列データから有用な情報を抽出するための高速で、費用効果の高い機構の必要性が高まってきている。
【課題を解決するための手段】
【０００６】
本発明の一態様では、生物学的配列類似検索を実行するためのデジタル論理回路が開示されている。このデジタル論理回路は、Ｂｌｏｏｍフィルタステージを備えるパイプラインを含むように構成されたプログラム可能論理デバイスを含み、Ｂｌｏｏｍフィルタステージは複数の生物学的配列データ文字列を含むデータストリームを受け取り、その生物学的配列データストリームをフィルタ処理して、配列データ文字列と問い合わせ文字列の複数の部分文字列との間の可能な複数のマッチを識別するように構成されている。
【０００７】
本発明の他の態様では、シードアライメント検索を実行するためのシステムが開示されている。このシステムは、シードアライメント検索パイプラインを実装するように構成された再構成可能ハードウェアを備え、パイプラインはＢｌｏｏｍフィルタステージを備え、Ｂｌｏｏｍフィルタステージは複数のデータ文字列を含むデータストリームを受け取り、そのデータストリームをフィルタ処理してデータストリームデータ文字列と問い合わせ文字列の複数の部分文字列との間の可能な複数のマッチを識別するように構成されている。
【０００８】
本発明のさらに他の態様では、生物学的配列類似検索を実行するための方法が開示されている。この方法は、プログラム可能論理デバイス上に実装されたＢｌｏｏｍフィルタステージを通して生物学的配列データストリームを処理することを含み、生物学的配列データストリームは複数の生物学的配列データ文字列を含み、Ｂｌｏｏｍフィルタステージは問い合わせ文字列の複数の部分文字列によりプログラムされ、生物学的配列データ文字列と問い合わせ部分文字列との間の可能な複数のマッチを識別するように構成されているＢｌｏｏｍフィルタを備える。
【０００９】
本発明のさらに他の態様では、生物学的配列類似検索を実行するためのデジタル論理回路が開示されている。このデジタル論理回路は、マッチングステージを含むパイプラインを備えるように構成されたプログラム可能論理デバイスを含み、マッチングステージは複数の生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の可能な複数のマッチを含むデータストリームを受け取るように構成され、パイプラインは、さらに、マッチングステージの下流のところに配置されている前置フィルタステージを備え、前置フィルタステージは生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の複数のパターンマッチを次から次へと見ていって、ユーザー定義スコアを超えるパターンマッチのみが前置フィルタステージの下流を通るようにスコアを付けるように構成されている。
【００１０】
本発明のさらに他の態様では、生物学的配列類似検索を実行するための方法が開示されている。この方法は、マッチングステージを含むパイプラインを備えるように構成されたプログラム可能論理デバイスにより生物学的配列データストリームを処理し、マッチングステージは複数の生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の可能な複数のマッチを含むデータストリームを受け取るように構成されることと、パイプライン内のマッチングステージの下流に配置されている前置フィルタステージを使用し、前置フィルタステージは生物学的配列データ文字列と問い合わせ文字列の複数の部分文字列との間の複数のパターンマッチを次から次へと見ていって、ユーザー定義スコアを超えるパターンマッチのみが前置フィルタステージの下流を通るようにスコアを付けるように構成されることとを含む。
【００１１】
これらは、本発明の無数の態様のうちの一部にすぎず、本発明に関連する無数の態様の包括的一覧とみなすべきではない。
【００１２】
本発明をよく理解するために、付属の図面を参照することができる。
【発明を実施するための最良の形態】
【００１３】
以下の詳細な説明では、本発明を完全に理解できるように、多数の具体的詳細が述べられている。しかし、当業者によって、本発明はこれらの具体的詳細がなくても実施されうることが理解されるであろう。他の場合には、よく知られている方法、手順および構成要素については、本発明をわかりにくくするような詳しさでは説明されていない。
【００１４】
生物学的類似検索の速度を改善することを目的として、発明者らはここで、当業でＢＬＡＳＴ（Ｂａｓｉｃ  Ｌｏｃａｌ  Ａｌｉｇｎｍｅｎｔ  Ｓｅａｒｃｈ  Ｔｏｏｌ）として知られているソフトウェアパイプラインのステージ１、より具体的にはＢＬＡＳＴアプリケーションＢＬＡＳＴＮが、限定はしないがＦＰＧＡ（フィールドプログラマブルゲートアレイ）などのプログラム可能論理デバイス、例えば、再構成可能ハードウェアを介して実装される新規性と独自性のある方法およびシステムを開発した。それに加えて、本発明では、ソフトウェアパイプラインのステージ２、無ギャップ伸長において、ワードマッチングから吐き出されるそれぞれのｗ−ｍｅｒが、問い合わせとデータベースとの間でパターンマッチを次から次へと見ていくことにより計算量の多い、ギャップ伸長による検査に値するかどうかを決定する。後のステージほど、ますます複雑になるため、ＢＬＡＳＴパイプラインのできる限り早い段階に偽のｗ−ｍｅｒを識別して破棄することが重要である。
【００１５】
ＢＬＡＳＴは、問い合わせ配列と生物学的配列データベースとを比較し、少ない回数の編集（単一文字の挿入、削除、または置換）で、その配列と異なる他の配列を見つける。配列間の編集距離の直接測定は、計算量が多くなるため、ＢＬＡＳＴでは、さまざまな発見的手法を用いて、生物学的配列問い合わせと慎重に比較するのに値する、大きなデータベースの小さないくつかの部分を識別する。
【００１６】
ＢＬＡＳＴは、データベースからの文字のストリームをフィルタ処理して問い合わせとの意味のあるマッチを識別する計算のパイプラインを備える。データベースおよび問い合わせ増大速度に合わせるために、このストリームのフィルタ処理速度を次第に高めてゆかなければならない。パフォーマンスを高める筋道の１つは、ＢＬＡＳＴの計算の一部を汎用プロセッサ、例えばＣＰＵから肩代わりする専用プロセッサを開発することである。ＢＬＡＳＴを高速化するか、または置き換えることが知られているプロセッサの例示的な、ただし限定されない実施例としては、ＡＳＩＣベースのＰａｒａｃｅｌ（登録商標）  ＧｅｎｅＭａｔｃｈｅｒ（商標）およびＦＰＧＡベースのＴｉｍｅＬｏｇｉｃ  ＤｅｃｙｐｈｅｒＢＬＡＳＴ（商標）エンジンがある。
【００１７】
また、アクセラレータ、ＦＰＧＡベースのＭＥＲＣＵＲＹ  ＢＬＡＳＴエンジンに、新しい設計が近年開発されている。このＭＥＲＣＵＲＹ  ＢＬＡＳＴエンジンは、ＢＬＡＳＴのアルゴリズムにおいてきめの細かい並列処理、および現在市販されているコンピューティングシステムの高い入出力（１１０）帯域幅を利用して、実験室に配置されている標準的なプロセッサに配備可能なソフトウェアＢＬＡＳＴよりも少なくとも１桁から２桁ほど高速化を図っている。
【００１８】
ＭＥＲＣＵＲＹ  ＢＬＡＳＴエンジンは、多段パイプラインであり、本発明は、ワードマッチング、つまり、第１のステージ（ステージ１）と無ギャップ伸長ステージ、つまり、第２のステージ（ステージ２）を伴う。本発明は、ワードマッチングステージと、問い合わせ配列と生物学的データベース配列との間のパターンマッチを篩いにかけ、より正確だが、計算コストの高い、それら配列同士の比較を実行するかどうかを決定する無ギャップ伸長ステージとの間に前置フィルタステージを備える。本発明は、さらに、文字置換に対し強固な可変長文字列マッチングを高速化し、より実り多いものとしている。この例示的な、ただし限定されない好ましい実装は、コンパクトであり、高いクロック速度で動作し、クロックサイクル毎に１パターンマッチを処理することができる。
【００１９】
図１は、全体として番号５０で示されている３段パイプラインの高水準の概要のブロック図を示している。データベース配列５２は、パイプライン５０に入るように示されている。第１のステージ（ステージ１）５４には、ワードマッチング機能があり、ＤＮＡについて問い合わせの部分文字列、例えば、ｗ＝１１と完全マッチするストリーム内の固定長「ｗ」の部分文字列を検出する。これらの短いマッチは、「ｗ−ｍｅｒ」とも呼ばれる。それぞれのマッチするｗ−ｍｅｒは、第２のステージ（ステージ２）に送られるが、これは、無ギャップ伸長５６であり、いずれかの側のｗ−ｍｅｒを伸長し、せいぜい少数のミスマッチ文字とマッチするｗ−ｍｅｒの周りの配列のより長いペアを識別する。これらのより長いマッチは、高スコア領域ペア（「ＨＳＰ」）、または無ギャップアライメントとして識別される。
【００２０】
最後に、マッチが十分にあり、ミスマッチが十分に少ないすべての高スコア領域ペア（ＨＳＰ）は、好ましくはＳｍｉｔｈ−Ｗａｔｅｒｍａｎ動的計画アルゴリズムを使用して、高スコア領域ペア（ＨＳＰ）をギャップアライメント内に伸長する、ギャップ伸長５８である、第３のステージ（ステージ３）に渡される。ギャップアライメントは、ごく少数の任意の編集により異なる可能性のある類似領域のペアである。ソフトウェア、例えばＢＬＡＳＴは、マッチが多数あり、編集６０が少ししかない最終ギャップアライメントのみを報告する。
【００２１】
研究により、標準的なＮＣＢＩ  ＢＬＡＳＴＮソフトウェアプログラムの場合、計算時間の８３．９％は、第１のステージ（ステージ１）５４で費やされ、１５．９％は、第２のステージ（ステージ２）５６で費やされることがわかった。したがって、意味のあるスピードアップを達成するには、例えば、ＢＬＡＳＴＮの６倍を超えるスピードアップを達成するには、第１のステージ（ステージ１）５４と第２のステージ（ステージ２）５６の両方の高速化を必要とする。ＮＣＢＩは、全米バイオテクノロジー情報センター（Ｎａｔｉｏｎａｌ  Ｃｅｎｔｅｒ  ｆｏｒ  Ｂｉｏｔｅｃｈｎｏｌｏｇｙ  Ｉｎｆｏｒｍａｔｉｏｎ）の略であり、コンピュータ科学者、分子生物学者、数学者、生化学者、基礎医学研究者、およびさまざまなソフトウェアデータベースおよびツールを使用する計算分子生物学の基礎および応用研究に重点を置く構造生物学者からなる、学際的研究グループである。
【００２２】
図１で参照されている第１のステージ（ステージ１）５４のブロック図概要は、図２に示されており、これは、本発明の好ましい一実施形態によるパイプライン１００、例えば、ＢＬＡＳＴＮステージ１である。入力処理ユニット１０４、Ｂｌｏｏｍフィルタステージ１０６、文字列バッファユニット１０８、ハッシングステージ１１０、ハッシュ（ルックアップ）テーブル１１２、および冗長性フィルタ１１４は、好ましくは、プログラム可能を論理デバイス上に実装される。プログラム可能論理デバイス１０２の例示的な、ただし限定されない、実施例は、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）を含むことができる。ハッシュテーブル１１２は、好ましくは、プログラム可能論理デバイス１０２とは別のチップであってよい、メモリユニット、例えば、スタティックランダムアクセスメモリ（ＳＲＡＭ）１１８上に実装される。
【００２３】
ハッシュテーブル１１２をチップの外部にあるものとして配置することは任意選択であり、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）のメモリ制約条件の結果にすぎず、容易に利用可能なＦＰＧＡは、ハッシュテーブルを格納し、さまざまなパイプラインステージ機能を実現する十分な容量を持たない。しかし、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）の容量が、将来十分に大きくなるのであれば、ハッシュテーブル１１２も、ＦＰＧＡに実装することができる。
【００２４】
パイプライン１００に対する好ましいハードウェアプラットフォームは、図３に開示されているものであり、全体として、番号８００で示されている。このハードウェアプラットフォームに関する詳細は、（１）「Ａｓｓｏｃｉａｔｉｖｅ  Ｄａｔａｂａｓｅ  Ｓｃａｎｎｉｎｇ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ」という表題の米国特許第６，７１１，５５８号、（２）２００２年５月２１日に出願された「Ａｓｓｏｃｉａｔｉｖｅ  Ｄａｔａｂａｓｅ  Ｓｃａｎｎｉｎｇ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ  Ｕｓｉｎｇ  ＦＰＧＡ  Ｄｅｖｉｃｅｓ」という表題の係属中の米国特許出願第１０／１５３，１５１号（米国特許出願公開第２００３／００１８６３０号）、（３）２００４年５月２１日に出願された「Ｉｎｔｅｌｌｉｇｅｎｔ  Ｓｔｏｒａｇｅ  ａｎｄ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｓｉｎｇ  ＦＰＧＡ  Ｄｅｖｉｃｅｓ」という表題の係属中のＰＣＴ出願ＰＣＴ／ＵＳ０４／１６３９８、および（４）２００４年１０月、マサチューセッツ州ボストンで開催時の「Ｐｒｏｃ．  ｏｆ  １ｓｔ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｂｕｉｌｄｉｎｇ  Ｂｌｏｃｋ  Ｅｎｇｉｎｅ  Ａｒｃｈｉｔｅｃｔｕｒｅｓ  ｆｏｒ  Ｃｏｍｐｕｔｅｒｓ  ａｎｄ  Ｎｅｔｗｏｒｋｓ」で発表されたＣｈａｍｂｅｒｌａｉｎらの論文「Ａｃｈｉｅｖｉｎｇ  Ｒｅａｌ  Ｄａｔａ  Ｔｈｒｏｕｇｈｐｕｔ  ｆｏｒ  ａｎ  ＦＰＧＡ  Ｃｏ−Ｐｒｏｃｅｓｓｏｒ  ｏｎ  Ｃｏｍｍｏｄｉｔｙ  Ｓｅｒｖｅｒ  Ｐｌａｔｆｏｒｍｓ」で開示されており、Ｌａｎｃａｓｔｅｒらの論文「Ａｃｃｅｌｅｒａｔｉｏｎ  ｏｆ  Ｕｎｇａｐｐｅｄ  Ｅｘｔｅｎｓｉｏｎ  ｉｎ  Ｍｅｒｃｕｒｙ  ＢＬＡＳＴ」は２００５年１１月１２日にスペイン、バルセロナで開催された「ｔｈｅ  Ｓｅｖｅｎｔｈ  （７ｔｈ）  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｍｅｄｉａ  ａｎｄ  Ｓｔｒｅａｍｉｎｇ  Ｐｒｏｃｅｓｓｏｒｓ  ｈｅｌｄ  ｉｎ  ｃｏｎｊｕｎｃｔｉｏｎ  ｗｉｔｈ  ｔｈｅ  Ｔｈｉｒｔｙ−Ｅｉｇｈｔｈ  （３８ｔｈ）  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ  （ＭＩＣＲＯ−３８）」において発表された論文であり、すべて参照により本明細書に組み込まれている。
【００２５】
入力処理ユニット１０４は、好ましくは、図２に示されている、配列データベースからの入力として生物学的配列データストリーム１２０を受け取るように構成される。データベースストリーム１２０は、複数の部分文字列に分けることができるデータベース配列を表し、それぞれの部分文字列は塩基長「ｗ」を有する。このような部分文字列は、ここではデータベースｗ−ｍｅｒと呼ばれる。入力処理ユニット１０４は、好ましくは、ｑ個のデータベースｗ−ｍｅｒ（または配列ｗ−ｍｅｒ）１２２ｉの並列ストリームを出力するが、ただし、ｑは、Ｂｌｏｏｍフィルタステージ１０６により同時に処理することができるデータベースｗ−ｍｅｒの総数を表す。
【００２６】
生物学的配列データストリームのサンプル部分の説明は、図４に示されている、番号１２０により示される。ストリーム１２０は、塩基配列を含む（この実施例では、Ａ、Ｃ、Ｇ、またはＴであり、ＤＮＡ配列の塩基に対応する）。この実施例では、それぞれ塩基は、当業で知られているように、２または４ビットで表すことができる。ｗが１１に等しく、ｑが８に等しい場合、このストリーム１２０は、図５に示されているように入力処理ユニット１０４により８個の並列ｗ−ｍｅｒに変換されうる。
【００２７】
Ｂｌｏｏｍフィルタステージ１０６は、図２に示されているように、問い合わせｗ−ｍｅｒとの可能なマッチがあるかどうかを判定するためにそれぞれのデータベースｗ−ｍｅｒを処理する動作をする。問い合わせｗ−ｍｅｒは、問い合わせ配列から導かれる塩基長「ｗ」の部分文字列である。定義により、Ｂｌｏｏｍフィルタは、データベースｗ−ｍｅｒと問い合わせｗ−ｍｅｒとの間では偽陰性を生じないが、Ｂｌｏｏｍフィルタは、データベースｗ−ｍｅｒと問い合わせｗ−ｍｅｒとの間ではある数の偽陽性を生じる可能性が高い。これらの偽陽性が存在するため、データベースｗ−ｍｅｒに対するＢｌｏｏｍフィルタの「ｙｅｓ」の応答は、可能なマッチと呼ばれるのが一番よい。
【００２８】
データベースｗ−ｍｅｒを処理する前に、Ｂｌｏｏｍフィルタステージ１０６内のＢｌｏｏｍフィルタは、問い合わせ配列（または問い合わせ文字列）から問い合わせｗ−ｍｅｒでプログラム／キーイングされる必要がある。問い合わせ配列は、マッチを見つけるため生物学的データベース配列と比較したい塩基の何らかの文字列である。問い合わせ配列は、データベース配列に関して図５に示されているように複数のｗ−ｍｅｒに分割されうる。与えられた検索について、ｗの値は、問い合わせｗ−ｍｅｒとデータベースｗ−ｍｅｒの両方に対し同じである。Ｂｌｏｏｍフィルタステージ１０６内のそれぞれのＢｌｏｏｍフィルタは、好ましくは、問い合わせ配列から作成された問い合わせｗ−ｍｅｒのすべてでプログラムされる。例示的な、ただし限定されない、好ましい実施形態では、Ｂｌｏｏｍフィルタステージ１０６は、複数の並列Ｂｌｏｏｍフィルタを含む。さらに、並列Ｂｌｏｏｍフィルタが、互いのコピーであることが好ましいが、必須というわけではない。Ｂｌｏｏｍフィルタが他のＢｌｏｏｍフィルタと並列であると言われるのは、これらのＢｌｏｏｍフィルタの両方が、ｗ−ｍｅｒを同時に処理するように構成されているときである。Ｂｌｏｏｍフィルタステージ１０６のプログラミングは、入力処理ユニット１０４によりアサートされる適切な制御コマンドを介して実行されうる（パイプライン１００への制御入力への応答として）。
【００２９】
Ｂｌｏｏｍフィルタステージ１０６内の好ましいＢｌｏｏｍフィルタアーキテクチャは、図６Ａ〜６（ｃ）に示されている。図６Ａは、例示的なＢｌｏｏｍフィルタ４００を示している。Ｂｌｏｏｍフィルタ４００内では、データベースｗ−ｍｅｒが、「ｋ」個のハッシュ関数４０２により処理され、それぞれのハッシュ関数「ｉ」はデータベースｗ−ｍｅｒを、そのハッシュ関数ｉに対応する１×ｍデュアルポートブロックＲＡＭ（ＢＲＡＭ）ユニット４０４ｉ内の１ビットにマップする動作をする。そのデータベースｗ−ｍｅｒがＢＲＡＭ  ４０４１から４０４ｋ内でマップするビットのすべてが、セットされている場合（例えば、１に等しい場合）、論理ユニット４０６、例えば、ＡＮＤ論理ユニットは、入力線ですべて１を受け取り、これにより、そのデータベースｗ−ｍｅｒが問い合わせｗ−ｍｅｒとの可能なマッチであるかどうかに関して「ｙｅｓ」応答を発生する。
【００３０】
１×ｍデュアルポートＢＲＡＭ  ４０４内の複数のビットは、Ｂｌｏｏｍフィルタのプログラミングプロセスにおいて、問い合わせｗ−ｍｅｒがそのビット位置にマップする場合にセットされる。Ｂｌｏｏｍフィルタは、問い合わせ配列からの問い合わせｗ−ｍｅｒのすべてでプログラムされるため、論理ユニット４０６、例えば、ＡＮＤ論理ユニットからの出力は、決して、偽陰性を生じないが、偽陽性を生じうる。
【００３１】
ハッシュ関数４０２は、好ましくは、ハッシングステージ１１０で使用されているのと同じ、ハッシュ関数のＨ３ファミリから選択されたハッシュ関数である。図６Ａの例示的な、ただし限定されない実施例では、ハッシュ関数４０２のマップ先である１×ｍメモリユニット４０４は、デュアルポート付きブロックランダムアクセスメモリ（ＢＲＡＭ）を含むことができる。しかし、デュアルポート化されているおかげで、複数のＢｌｏｏｍフィルタが、同じＢＲＡＭ４０４へのアクセスを共有することができ、これにより、Ｂｌｏｏｍフィルタステージ１０６を実装する際にプログラム可能論理デバイス１０２、例えば、ＦＰＧＡ上で消費されるリソースを実質的節減することができる。
【００３２】
Ｂｌｏｏｍフィルタの動作の説明は、参照により本明細書に組み込まれている、米国特許出願第２００５／００８６５２０号としても公開され、２００３年８月１４日に出願された、米国特許出願第１０／６４０，５１３号にある。
【００３３】
リソースの消費をさらに認識したものとして、デュアルポートＢＲＡＭ  ４０４は、好ましくは、４つのＢｌｏｏｍフィルタ１０６が同じデュアルポートＢＲＡＭ  ４０４を共有できるようにダブルクロック化されることが挙げられる。そこで、所定のクロックサイクルで、それぞれのデュアルポートＢＲＡＭ  ４０４ｉに対し４回アクセスすることができ、これにより、それぞれのデュアルポートＢＲＡＭは、クロックサイクル毎に４つのＢｌｏｏｍフィルタ１０６をサポートすることができる。
【００３４】
同じｋ個のＢＲＡＭ  ４０４１から４０４ｋを共有するように構成されている４つのＢｌｏｏｍフィルタ１０６の配置４１０が、図６Ｂに示されている。さらに、ＢＲＡＭ  ４０４をトリプルクロック化することが可能な場合には、それぞれのデュアルポートＢＲＡＭ  ４０４が６つのＢｌｏｏｍフィルタをサポートすることが可能になることは注目に値する。
【００３５】
少なくとも１６個のＢｌｏｏｍフィルタを含むＢｌｏｏｍフィルタステージ１０６は、図６Ｃに示されており、図６Ｂに示されている４つのＢｌｏｏｍフィルタ配置４１０から形成される。このようなＢｌｏｏｍフィルタステージ１０６は、それぞれの並列Ｂｌｏｏｍフィルタを通して異なるデータベースｗ−ｍｅｒを同時に処理することができる。そのようなものとして、Ｂｌｏｏｍフィルタステージ１０６は、複数の（好ましい、ただし限定されない実施形態では１６個の）データベースｗ−ｍｅｒについて可能なマッチが同時に存在するかどうかを判定することができる。Ｂｌｏｏｍフィルタステージ１０６は、好ましい一実施形態では、１６個の並列Ｂｌｏｏｍフィルタを含むが、当業者であれば本明細書に記載されている教示に従って理解するように、本発明を実施する際に使用されうる並列Ｂｌｏｏｍフィルタの個数は加減できることに留意されたい。
【００３６】
Ｂｌｏｏｍフィルタステージ１０６内にあるか、またはＢｌｏｏｍフィルタステージ１０６と関連付けられている制御論理は、問い合わせｗ−ｍｅｒとの可能なマッチであるデータベースｗ−ｍｅｒのデータベース配列内の開始位置を識別するように容易に構成されうる。この制御論理が例示的な流れ図でどのように構成されうるかを示す例示的な、ただし限定されない実施例は、図７に示されており、全体として番号９００で示される。第１のステップは、新しいクロックサイクルが受け取られる毎にカウンタが更新され、番号９０２で示されているように、そのクロックサイクルに対するｗ−ｍｅｒのデータベース配列内の新しい開始位置を反映させることである。どの論理ユニット４０６ｉ（または複数のユニット）、例えば、ＡＮＤ論理ユニットが可能なマッチ９０４を見つけるのかにより、可能なマッチングｗ−ｍｅｒに対する適切な開始位置が記録されることができる。可能なマッチが見つかった場合、ｉは記録され（９０６）、ｉの記録された値毎に、開始点（ＳＰ）とｉの値をデータベース配列９０８内の可能なマッチに対する新しい開始位置のポインタとして返す。次いで、このプロセスは、新しいクロックサイクル９１０があるかどうかを判定する。その答えが否定的であれば、この判定は、肯定的判定が現れるまで繰り返され、開始点（ＳＰ）はプロセスステップ９１２により示されているｑだけ増やされることができ、ただし、ｑは、Ｂｌｏｏｍフィルタステージ１０６により同時に処理できるデータベースｗ−ｍｅｒの総数を表す。次いで、このプロセスは、ステップ９０４に戻り、可能なマッチがあるかどうかを判定する。
【００３７】
プロセスステップ９０４でマッチが見つからない場合、このプロセスは、次に、新しいクロックサイクル９１０があるかどうかを判定する。その答えが否定的であれば、この判定は、肯定的判定が現れるまで繰り返され、開始点（ＳＰ）はプロセスステップ９１２により示されているｑだけ増やされることができ、ただし、ｑは、Ｂｌｏｏｍフィルタステージ１０６により同時に処理できるデータベースｗ−ｍｅｒの総数を表す。次いで、このプロセスは、ステップ９０４に戻り、可能なマッチがあるかどうかを判定する。
【００３８】
可能なマッチに対するこれらの開始位置のそれぞれは、好ましくは、次に、Ｂｌｏｏｍフィルタステージ１０６からの出力として、図２に示されているように、文字列バッファユニット１０８に渡される。適宜、Ｂｌｏｏｍフィルタステージからの出力１２４ｉは、開始位置ポインタに加えて、またはその代わりに、可能なマッチをトリガした実際のデータベースｗ−ｍｅｒを含むことができる。
【００３９】
ｗに対する値の好ましい範囲は、５から１５までであり、１１が最も好ましい値である。しかし、この範囲を外れた値も、本発明の実施者が望めば、使用することもできることに留意されたい。ｑに対する好ましい値は１６である。ｋに対する好ましい値は６である。ｍに対する好ましい値は、３２ｋｂｉｔまたは６４ｋｂｉｔである。しかし、ｑ、ｋ、およびｍに対する他の値は、本発明の実施者が望めば、使用することができる。好ましいＢｌｏｏｍフィルタステージ１０６とともに、代替え実施形態に関する詳細は、すでに参照により組み込まれている刊行物において説明されている。
【００４０】
文字列バッファユニット１０８は、問い合わせｗ−ｍｅｒとの可能なマッチであるそれぞれのデータベースｗ−ｍｅｒおよび／または場合によってはマッチするデータベースｗ−ｍｅｒ自体に対するデータベース配列内の（複数の）開始位置を識別するポインタを含む並列出力１２４１から１２４ｑまでを受け取る動作をする。文字列バッファユニット１０８は、出力１２６として、これらの開始位置および／または場合によってはマッチするデータベースｗ−ｍｅｒへのポインタのシリアル化されたストリームを生成する。好ましい文字列バッファユニット１０８に関する詳細は、すでに参照により組み込まれている刊行物において説明されている。
【００４１】
ストリーム１２６内の受け取ったデータベースｗ−ｍｅｒポインタまたはデータベースｗ−ｍｅｒ毎に、ハッシングステージ１１０は、データベースｗ−ｍｅｒと問い合わせｗ−ｍｅｒとの間に可能なマッチが存在することを確認し、データベースｗ−ｍｅｒとマッチする可能性のある、図２に示されている問い合わせｗ−ｍｅｒへのポインタを決定する動作をする。ストリーム１２６がポインタのみを含み、データベースｗ−ｍｅｒ自体を含まない場合、ハッシングステージ１１０も、ストリーム１２０を受け取り、ハッシングステージがストリーム１２６内の開始位置ポインタを使用して適切な、マッチしている可能性のあるデータベースｗ−ｍｅｒをストリーム１２０から抽出できることが好ましい。ハッシュステージ内のハッシュ関数は、それぞれのマッチしている可能性のあるデータベースｗ−ｍｅｒをハッシュテーブル１１２内のある位置にマップする動作をする。
【００４２】
本発明の好ましい実施形態による例示的なハッシングステージ１１０およびハッシュテーブル１１２は、図８に示されている。ハッシュテーブル１１２は、好ましくは、一次テーブル６０２、二次テーブル６０４、および複製テーブル６０６を含む。一次テーブル６０２においてそれぞれのアドレスのところに格納されているのは、好ましくは、ハッシングステージ１１０のハッシュ関数によりそのアドレスにマップされた問い合わせｗ−ｍｅｒに対する問い合わせ配列内の開始位置へのポインタを含むエントリである。問い合わせ配列内の複数の場所で複製される問い合わせｗ−ｍｅｒにおいて、一次テーブル６０２内のその問い合わせｗ−ｍｅｒの対応するエントリ内の重複ビットが好ましくはセットされる。
【００４３】
ハッシュテーブル１１２を構築するために、それぞれの問い合わせｗ−ｍｅｒをハッシングステージ１１０内のアドレスにマップするためにハッシュ関数が使用される。これらのハッシュ関数の作成は、好ましくは、パイプライン１００を通してデータベースｗ−ｍｅｒをストリーミングするのに先立ってソフトウェアにより実行される。ハッシュ関数がソフトウェアにより作成されると、これらのハッシュ関数は、好ましくは、パイプラインを通してデータベースｗ−ｍｅｒをストリーミングするのに先立ってプログラミングプロセスの際にハッシングステージ１１０にロードされる。ハッシングステージ１１０をプログラムするために新しい問い合わせ生物学的配列が使用されるときに、好ましくは新しい問い合わせｗ−ｍｅｒを反映するように更新されるハッシング関数により利用される変位テーブルがある。ハッシング関数自体は、同じままであってよい。これ以降、ハッシュテーブル１１２は、適切な制御コマンドがアサートされている間に、ハッシングステージ１１０を通して問い合わせｗ−ｍｅｒを処理することによりプログラムすることができる。必要ならば、ハッシュテーブル１１２を構築し、ハッシングステージ１１０内のデータベースｗ−ｍｅｒを処理するために、通常のハッシュ関数が使用できる。しかし、通常のハッシングは、典型的には、複数の衝突を生じ、またハッシュテーブル１１２は、プログラム可能論理デバイス１０２、例えばＦＰＧＡの外部、メモリ１１８、例えばＳＲＡＭに格納することができるため、通常のハッシング以外のハッシング技術を使用して、メモリ検索回数を最小限に抑え、それにより潜在的なパイプラインボトルネックを回避することが望ましい。ハッシングプロセスでは、ハッシュテーブル１１２を構築するときに、２つの異なる問い合わせｗ−ｍｅｒが一次テーブル６０２内の同じアドレスにマップすると衝突が生じる。通常のハッシングでは、このような衝突は希ではない。このような衝突を解決するために、よく知られているように、一次テーブル６０２内の同じアドレスにマップされた異なるｗ−ｍｅｒに対し異なるアドレスを与える二次テーブル６０４が、好ましくは使用される。次いで、衝突が発生した一次テーブル６０２のアドレス内の衝突ビットがセットされ、そのｗ−ｍｅｒを適切にマップするために二次テーブルにアクセスする必要があることを示す。
【００４４】
ハッシュ関数の二次的な集合体は、好ましくは、データベースｗ−ｍｅｒを二次テーブル６０４にマップするハッシングステージ１１０により使用される。ハッシュ関数の二次的な集合体は、本発明の実施者の好みに応じて、通常のハッシュ関数か、または完全ハッシュ関数か、または完全に近いハッシュ関数のいずれかとすることができる。好ましいハッシング演算において、データベースｗ−ｍｅｒを一次テーブル６０２にマップするハッシュ関数およびデータベースｗ−ｍｅｒを二次テーブル６０４にマップするハッシュ関数は、受け取ったすべてのデータベースｗ−ｍｅｒを同時に処理する。データベースｗ−ｍｅｒのマップ先の一次テーブル６０２内のアドレスで衝突ビットがセットされている場合、ハッシングステージの論理では、そのデータベースｗ−ｍｅｒのマップ先となった二次テーブル６０４内のアドレスを使用し、これにより、そのデータベースｗ−ｍｅｒが衝突の生じたアドレスにマップする場合にデータベースｗ−ｍｅｒをハッシングステージで再ハッシュする必要がなくなる。
【００４５】
ハッシュテーブル検索回数を最小限に抑えようとする第１の代替え実施形態では、完全ハッシング関数が、ハッシュテーブル１１２を構築し、ハッシングステージ１１０のマッピングを実行するために使用される。ハッシュテーブル１１２を構築するために、完全ハッシングが使用される場合、二次テーブル６０４は不要である。完全ハッシング関数は、参照により本明細書に組み込まれているいくつかの刊行物においてさらに詳しく説明されている。
【００４６】
第２の代替え実施形態では、ハッシュテーブル１１２を構築し、ハッシングステージ１１０のマッピングを実行するために完全に近いハッシング関数が使用されるようにハッシュテーブル検索回数を減らす必要がある。完全に近いハッシングは、通常のハッシング関数により生じる衝突の確率に関して衝突の確率を減らすように動作するハッシングとして定義することができ、ハッシングは、実行時間が長いほど完全ハッシュに近づく。完全に近いハッシング関数は、参照により本明細書に組み込まれているいくつかの刊行物においてさらに詳しく説明されている。好ましい完全に近いハッシング関数は、最大階数を持つように選択されたファミリＨ３内の関数である。「Ｈ３」と指定されたハッシング関数のファミリは、「最大階数」という概念とともに、この分野の多数の刊行物で詳しく説明され、開示されている。より一般的には、本明細書で説明されている完全に近いハッシングアルゴリズムは、ハッシュテーブルのインデックスへのキーと呼ばれるｎに等しい共通長の２進数列の集まりのマッピングを生成するために使用することができ、これにより、テーブル内の同じ場所にマップされるキーのペアはほとんど、または全くない。ハッシングステージ１１０のハッシング論理は、好ましくは、マッチしている可能性のあるデータベースｗ−ｍｅｒを問い合わせ配列内のそれぞれの位置にマップするようにプログラム可能論理デバイス１０２、例えば、ＦＰＧＡ上に実装される。
【００４７】
ハッシングステージ１１０が、マッチしている可能性のあるデータベースｗ−ｍｅｒをハッシュテーブル１１２内の空のエントリにマップする場合、そのデータベースｗ−ｍｅｒは、偽陽性として破棄されうる。ハッシングステージ１１０が、マッチしている可能性のあるデータベースｗ−ｍｅｒを、問い合わせ配列内の位置へのポインタを含むハッシュテーブル１１２内のエントリにマップする場合、重複ビットも衝突ビットもセットされない。次いで、そのポインタは、そのデータベースｗ−ｍｅｒとの可能なマッチである問い合わせｗ−ｍｅｒに対する問い合わせ配列内の開始位置のみを指す。
【００４８】
ハッシングステージ１１０が、マッチしている可能性のあるデータベースｗ−ｍｅｒを衝突ビットがセットされているハッシュテーブル１１２内のエントリにマップする場合、ハッシングステージ１１０は、二次ハッシュ関数がそのマッチしている可能性のあるデータベースｗ−ｍｅｒをマップした二次テーブル６０４内のアドレスを見る。データベースｗ−ｍｅｒに対する二次テーブル６０４内の適切なエントリが識別された後、二次テーブルエントリが、一次テーブル（衝突ビットがセットされていない）内のエントリと同じようにして処理される。
【００４９】
ハッシングステージ１１０が、マッチしている可能性のあるデータベースｗ−ｍｅｒを、問い合わせ配列内の位置へのポインタを含むハッシュテーブル１１２内のエントリにマップし、重複ビットがセットされる場合、そのポインタは、そのデータベースｗ−ｍｅｒとの可能なマッチである問い合わせｗ−ｍｅｒに対する問い合わせ配列内の複数の開始位置のうちの１つを指す。それぞれの重複問い合わせｗ−ｍｅｒに対する（複数の）開始位置を取得するために、次いで、重複テーブル６０６が、好ましくはアクセスされる。さらに、重複ビットがセットされているそれぞれの一次テーブルエントリには、その問い合わせｗ−ｍｅｒに対する重複テーブル６０６内のアドレスへのポインタが含まれる。そのアドレスにおいて、重複テーブルアドレスは、好ましくは、与えられた問い合わせｗ−ｍｅｒに対する重複テーブル６０６内に存在する重複問い合わせｗ−ｍｅｒの総数を示すエントリを含む。この総数の後に、好ましくは、問題の問い合わせｗ−ｍｅｒの重複であるｗ−ｍｅｒ毎に、その重複問い合わせｗ−ｍｅｒに対する問い合わせ配列内の開始位置へのポインタを含む隣接アレイが続く。それとは別に、重複ｗ−ｍｅｒポインタをつないで１本にするためにリンクリスト技術が使用されうる。さらに、システムは、ハッシュテーブル１１０のプログラミング中、問い合わせ配列内の重複ｗ−ｍｅｒの数が十分に大きく、重複テーブル６０６の容量を超える場合に、問い合わせ配列検索をキャンセルするように構成されうる。
【００５０】
したがって、ハッシングステージ１１０は、問い合わせｗ−ｍｅｒとの可能なマッチであるデータベースｗ−ｍｅｒ毎に、その可能なマッチである問い合わせｗ−ｍｅｒ毎に問い合わせ配列内の開始位置を識別する動作をする。ハッシングステージ１１０からの好ましい出力１２８は、順序付きペアのストリームであり、それぞれの順序付きペアは、問い合わせｗ−ｍｅｒとの可能なマッチであるデータベースｗ−ｍｅｒのデータベース配列内の開始位置へのポインタおよびデータベースｗ−ｍｅｒとマッチしている可能性のある問い合わせｗ−ｍｅｒの問い合わせ配列内の開始位置へのポインタを含む。必要ならば、比較論理（図に示されていない）は、適宜、偽陽性を排除するためにそれぞれの順序付きペアについてデータベースｗ−ｍｅｒと問い合わせｗ−ｍｅｒとを比較する動作をするハッシングステージの後に、プログラム可能論理デバイス１０２、例えばＦＰＧＡ上で実装されうる。
【００５１】
重複テーブル６０６の役割は、ハッシュテーブル１１２から取り除かれ、本発明の実施者が望めば、ハッシングステージ１１０の下流の専用パイプラインステージとして、別のメモリ、例えばＳＲＡＭ、またはプログラム可能論理デバイス１０２、例えばＦＰＧＡに入れられることができることは注目に値する。
【００５２】
冗長性フィルタステージ１１４は、好ましくは、ストリーム１２８内の他の順序付きペアで冗長状態にあるとみなされる順序付きペアをストリーム１２８から取り除くように構成される。ユーザー指定冗長性閾値Ｎとさらに冗長性フィルタステージ１１４の好ましい設計に基づいて冗長および非冗長であるとみなされているデータベース−問い合わせｗ−ｍｅｒは、すでに参照により本明細書に組み込まれた文献において説明されている。冗長性フィルタステージ１１４からの出力１３０は、好ましくは、ストリーム１２８の場合のように順序付きペアのストリームであるが、ただし、他の順序付きペアが冗長であるとみなされているマッチに対する順序付きペアは、ここには存在していないという点を除く。
【００５３】
さらに、本明細書で説明されているプログラム可能論理デバイス１０２用のＦＰＧＡパイプラインステージのＦＰＧＡへの実装は、本明細書の教示および参照により本明細書に組み込まれている（１）「Ａｓｓｏｃｉａｔｉｖｅ  Ｄａｔａｂａｓｅ  Ｓｃａｎｎｉｎｇ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ」という表題の米国特許第６，７１１，５５８号、（２）２００２年５月２１日に出願された、「Ａｓｓｏｃｉａｔｉｖｅ  Ｄａｔａｂａｓｅ  Ｓｃａｎｎｉｎｇ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ  Ｕｓｉｎｇ  ＦＰＧＡ  Ｄｅｖｉｃｅｓ」という表題の係属中の米国特許出願第１０／１５３，１５１号（米国特許出願公開第２００３／００１８６３０号として公開）、および（３）２００４年５月２１日に出願された「Ｉｎｔｅｌｌｉｇｅｎｔ  Ｓｔｏｒａｇｅ  ａｎｄ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｓｉｎｇ  ＦＰＧＡ  Ｄｅｖｉｃｅｓ」という表題の係属中のＰＣＴ出願ＰＣＴ／ＵＳ０４／１６３９８の教示に従い、当業者の技能の範囲内にあることは注目に値する。例えば、ＰＣＴ出願ＰＣＴ／ＵＳＯ４／１６３９８の図８の説明を参照されたい。
【００５４】
すでに説明され、図１に示されているように、ワードマッチング５４の第１のステージ（ステージ１）が高速化された後、無ギャップ伸長５６に関係する第２のステージ（ステージ２）のパフォーマンスにより、パイプライン化されているアプリケーション全体のパフォーマンスが決まる。
【００５５】
ｗ−ｍｅｒを伸長する目的は、ｗ−ｍｅｒが偶然だけで生じたかどうか、または有意なマッチを示しうるかどうかを、できる限り迅速に、また正確に決定することである。第２のステージ（ステージ２）５６における無ギャップ伸長では、ワードマッチング機構から放出されたそれぞれのｗ−ｍｅｒが計算量の多いギャップ伸長による検査に値するかどうかを判定しなければならない。後のステージほど、ますます複雑になるため、ＢＬＡＳＴパイプラインのできる限り早い段階に偽のｗ−ｍｅｒを識別して破棄することが重要である。フィルタの厳密性とその感度、つまり見つかる生物学的に有意なアライメントの個数との間にデリケートなバランスが存在する。無益なギャップ伸長で費やされる時間を最小にするために非常に厳密性の高いフィルタが必要であるが、フィルタでは、少しだけ相違点がある長い問い合わせ−データベースマッチを合法的に識別するｗ−ｍｅｒを破棄しなければならない。プログラム可能論理デバイス１０２、例えばＦＰＧＡの実装の例示的な、ただし限定されない実施形態では、このフィルタ演算の計算は、さらに、並列化可能で、限られた領域に収められる十分な単純さを有していなければならない。
【００５６】
第２のステージ（ステージ２）５６の実装は、上で説明され、参照により本明細書に組み込まれているＰ．Ｋｒｉｓｈｎａｍｕｒｔｈｙ、Ｊ．Ｂｕｈｌｅｒ、Ｒ．Ｄ．Ｃｈａｍｂｅｒｌａｉｎ、Ｍ．Ａ．Ｆｒａｎｋｌｉｎ、Ｋ．Ｇｙａｎｇ、およびＪ．Ｌａｎｃａｓｔｅｒらによる論文「Ｂｉｏｓｅｑｕｅｎｃｅ  Ｓｉｍｉｌａｒｉｔｙ  Ｓｅａｒｃｈ  Ｏｎ  Ｔｈｅ  Ｍｅｒｃｕｒｙ  Ｓｙｓｔｅｍ」（Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １５ｔｈ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｓｙｓｔｅｍｓ，Ａｒｃｈｉｔｅｃｔｕｒｅｓ，ａｎｄ  Ｐｒｏｃｅｓｓｏｒｓ（ＡＳＡＰ０４）、３６５〜３７５頁（２００４））で開示されている第１のステージ（ステージ１）５４の実装において利用される概念に基づく。
【００５７】
第２のステージ（ステージ２）５６では、前置フィルタステージとして動作するプログラム可能論理デバイス、例えばＦＰＧＡ  ７４を使用して無ギャップ伸長ステージを展開する。この設計では、プログラム可能論理デバイス、例えばＦＰＧＡ  ７４の実装の速度を利用して、ソフトウェアに渡されるｗ−ｍｅｒの個数を大幅に減らし、その一方で、パイプライン７０に入るｗ−ｍｅｒにおけるソフトウェア実装の柔軟性を保持する。
【００５８】
好ましくは、ただし必ずというわけではないが、ｗ−ｍｅｒは、第３のステージ（ステージ３）ギャップ伸長５８に放出される前に、ハードウェアとソフトウェアの両方を使用することができる、第２のステージ（ステージ２）５６の無ギャップ伸長を通らなければならない。待ち時間ではなく総スループットを伴うアプリケーションのデータストリーミングに関する性質に注目すると、他の処理ステージを加えることは非常に有用である。
【００５９】
次に、第１の例示的ソフトウェアプログラム、例えば、ＮＣＢＩ  ＢＬＡＳＴＮを使用する第２のステージ（ステージ２）５６について、説明する。ＨＳＰへのｗ−ｍｅｒの無ギャップ伸長は、ＮＣＢＩ  ＢＬＡＳＴＮを使用して２つのステップで実行される。ｗ−ｍｅｒは、２つの配列の先頭に向かって遡り、次いで、その末尾に向かって進行する。ＨＳＰがそれぞれの文字ペアに広がると、そのペアは、文字がマッチした場合に報酬＋αを受け取り、ミスマッチの場合はペナルティ−βを受け取る。ＨＳＰのスコアは、すべてのペアに渡るこれらの報酬とペナルティの総和である。それぞれの方向のＨＳＰの末尾は、その方向の伸長の総スコアを最大にするように選択される。最終的なＨＳＰのスコアがユーザー定義閾値を超えると、これは第３のステージ（ステージ３）のギャップ伸長５８に渡される。
【００６０】
長い生物学的配列では、特に高スコアＨＳＰが見つかる可能性のない場合に、配列の終わりに達する前に無ギャップ伸長を終了させると都合がよい。例示的なソフトウェアでは、ＢＬＡＳＴＮは、Ｘドロップ機構による早期終了を実装する。このアルゴリズムは、ある程度までｗ−ｍｅｒの伸長により達成された最高スコアを追跡し、現在の伸長のスコアがこの最大値よりも少なくともＸだけ低い場合に、その方向のさらなる伸長は終了する。Ｘドロップを使用する無ギャップ伸長により、ＢＬＡＳＴＮソフトウェアは、与えられたｗ−ｍｅｒに対する平均検索空間を制限しつつ、任意長のＨＳＰを復元することができる。しかし、伸長の領域は原理上極めて長くなりうるため、この発見的手法は、典型的なプログラム可能論理デバイス７４、例えばＦＰＧＡでの高速実装には適していない。両方向の伸長は平行して行えるとしても、これは処理の所望のスピードアップを果たすのには十分でなかったことに留意されたい。
【００６１】
無ギャップ伸長を使用する第２のステージ（ステージ２）５６の前処理は、ＮＣＢＩ  ＢＬＡＳＴを利用するものとして図９に示されている。ここで使用されるパラメータは、ｗ＝５、α＝１、β＝−３、およびＸ−ｄｒｏｐ＝１０である。ｗは、部分文字列の長さであり、αは、文字マッチに対する正の報酬値であり、βは、文字ミスマッチに対する負のペナルティ値であり、Ｘ−ｄｒｏｐは、さらなる伸長が終了させられる現在の伸長スコアの最大レベルを下回る減少である。Ｘドロップを使用することで、このソフトウェアは、与えられたｗ−ｍｅｒに対する平均検索空間を制限しつつ、任意長のＨＳＰを復元することができるが、それでもあまり高速でも効率的でもない。
【００６２】
好ましいソフトウェアプログラム、つまりＮＣＢＩ  ＢＬＡＳＴを使用する無ギャップ伸長分析は、全体として番号６２により示されており、ｗ−ｍｅｒの終わりに始まり、左に伸長する。ランニングスコアが最大スコアよりも１０だけ落ちた場合に伸長は停止する（矢印により示されている方向）。これは、さらに、ユーザー修正可能な「Ｘ−ｄｒｏｐ」パラメータとしても示されている。次いで、同じ計算が他の方向で実行される。最終的な文字列は、左および右伸長からの最良の部分文字列の連接である。
【００６３】
本発明では、前置フィルタは、処理効率を改善するために使用される。与えられたｗ−ｍｅｒに対する伸長アルゴリズムは、固定サイズウィンドウ上の単一順方向パスで実行される。この伸長は、問い合わせおよびデータベースストリームの両方においてｗ−ｍｅｒを中心とする、長さＬｗの固定ウィンドウの限界を計算することから始まる。その後、問い合わせおよびデータベースストリームの適切な部分文字列がバッファ内に取り込まれる。これらの部分文字列がバッファ内に取り込まれた後、伸長アルゴリズムが開始する。疑似コードで書かれた伸長アルゴリズムが、図１２に示されており、全体として番号６６で表され、関連する流れ図は、図２０上に示されており、全体として番号５００で表されている。このアルゴリズム６６は、計算が連続的に現れるにも関わらず、ハードウェア実装に適している。
【００６４】
この前置フィルタ伸長アルゴリズムは、所定のウィンドウ内の最良の高スコア領域ペア（ＨＳＰ）の始めと終わりを同時に計算する動的計画再帰法を実装する。第１のステップ５０２では、所定のウィンドウ境界を計算する。ウィンドウ内の現在位置は、変数「ｉ’」で示される。次いで、ウィンドウの位置ｉで終わる最良の高スコア領域ペア（ＨＳＰ）のスコア「γ」およびｉのところで、またはｉの前で終わる最良高スコア領域ペア（ＨＳＰ）のスコア「Γ」を０にリセットする作業がある。この後に、変数「Ｂ」とともにｉのところで、またはｉの前で終わる最良高スコア領域ペア（ＨＳＰ）の２つの端点ＢｍａｘおよびＥｍａｘを値０にリセットする。
【００６５】
第１に、ウィンドウの長さＬｗまでのウィンドウ内のすべての位置ｉについて、ウィンドウ内の文字がマッチするかどうか（５０４）が判定され、パターンマッチに対する報酬およびパターンミスマッチに対するペナルティをそれぞれ与える実装として、番号５０６で示される報酬＋αおよび番号５０８で示されるペナルティ−βを使用することにより、ウィンドウ内のそれぞれの文字ペアのスコア寄与分が計算される。これらの寄与分は、ペア毎に並列に独立して計算することができる。報酬＋αがある場合、これは、スコアγに加えられる、つまり、γ＝γ＋αとなり、ペナルティ−βがある場合、スコアから差し引かれる、つまり、γ＝γ−βとなる。
【００６６】
次いで、このアルゴリズムは、最良高スコア領域ペア（ＨＳＰ）のスコアγが０よりも大きいかどうかを判定する（５１０）。この判定結果が肯定的である場合、ウィンドウの位置ｉで終わる最良の高スコア領域ペア（ＨＳＰ）のスコア「γ」が、ｉのところで、またはｉの前で終わる最良高スコア領域ペア（ＨＳＰ）のスコア「Γ」よりも大きいかどうか、およびｉ（ウィンドウ内の位置）がショートワードマッチｗ−ｍｅｒの終わり（ＷｍｅｒＥｎｄ）よりも大きいかどうかの判定５１１が行われる。
【００６７】
ステップ５１０のこの判定が否定的である場合、ｉがショートワードマッチｗ−ｍｅｒの先頭（ＷｍｅｒＳｔａｒｔ）よりも小さいかどうかの判定５１２が行われる。ｉがショートワードマッチｗ−ｍｅｒの先頭よりも小さい場合、変数Ｂは、１だけインクリメントされたウィンドウｉ内の現在位置に設定され、最良高スコア領域ペア（ＨＳＰ）のスコア「γ」は、０に設定される（５１６）。次いで、次のステップは、ｉがウィンドウの長さＬｗに等しいかどうかの判定５１９である。ステップ５１１での判定結果が肯定的である場合、ｉのところで、またはｉの前で終わる最良高スコア領域ペア（ＨＳＰ）のスコア「Γ」は、ｉのところで終わる最良高スコア領域ペア（ＨＳＰ）のスコア「γ」に設定され、ｉのところで、またはｉの前で終わる最良高スコア領域ペア（ＨＳＰ）「Γ」の端点Ｂｍａｘは、変数Ｂに設定され、最良高スコア領域ペア（ＨＳＰ）の端点Ｅｍａｘは、ｉ（ウィンドウ内の位置）に設定される（５１４）。次いで、次のステップは、ｉがウィンドウの長さＬｗに等しいかどうかの判定５１９である。さらに、ステップ５１１での判定結果が否定的である場合、ｉがウィンドウの長さＬｗに等しいかどうかの判定５１９もある。
【００６８】
ステップ５１９での判定結果が否定的である場合、変数ｉは、ステップ５１７で１だけインクリメントされ、プロセスはステップ５０４に戻る。ステップ５１９でのこの判定結果が肯定的である場合、ソフトウェアプログラムは、次のプログラムステップ５１８に進み、そこで、最良高スコア領域ペア（ＨＳＰ）のスコア「Γ」がステップ５１８の変数Ｔよりも大きいかどうかの判定が行われる。この判定結果が肯定的である場合、「真」の値が返され（５２０）、ソフトウェアプログラムは終了する（５２７）。
【００６９】
ステップ５１８での判定結果が否定的である場合、この後に、最良高スコア領域ペア（ＨＳＰ）の端点ＢＭａｘの位置が０に等しいかどうかの判定が行われる（５２２）。この判定結果が肯定的である場合、「真」の値が返され（５２６）、ソフトウェアプログラムは終了する（５２７）。
【００７０】
最後に、ステップ５２２での判定結果が否定的である場合、最良高スコア領域ペア（ＨＳＰ）の端点Ｅｍａｘがウィンドウの長さＬｗに等しいかどうかの判定が行われる（５２４）。この判定結果が肯定的である場合、「真」の値が返され（５２６）、アルゴリズムは終了し（５２７）、この判定結果が否定的である場合、「偽」の値が返され（５２８）、アルゴリズムは、やはり、終了する（５２７）。
【００７１】
まとめると、アルゴリズムは、端点ＢｍａｘおよびＥｍａｘとともに、ｉの前で終わる最高スコアＨＳＰのスコアであるΓを追跡する。したがって、ΓＬＷがユーザー定義閾値スコアよりも大きい場合、ｗ−ｍｅｒは、前置フィルタを通り、無ギャップ伸長のため（ステージ２ｂ）８４に送られる。
【００７２】
この前置フィルタアルゴリズムには２つの態様がある。第１の態様は、再帰は、アルゴリズムによって見つけられたＨＳＰがそのオリジナルのマッチするｗ−ｍｅｒを通過し、このｗ−ｍｅｒを含まないウィンドウ内のより高いスコアのＨＳＰは無視されることを必要とする。この制約条件があるため、必ず、２つの異なる生物学的特徴が単一ウィンドウ内に現れた場合に、それぞれから生成されるｗ−ｍｅｒには、２つの独立のＨＳＰを生成するチャンスがある。そうでない場合、両方のｗ−ｍｅｒは、スコアの高いＨＳＰを持つ特徴のみを識別し、他の特徴は無視される可能性がある。
【００７３】
第２の態様は、最高スコアＨＳＰがウィンドウの境界を交差した場合に、スコアに関係なくソフトウェアに渡されるという点である。この発見的手法により、必ず、ウィンドウ境界を十分に越える可能性のあるＨＳＰは、早期に排除されるのではなく、固定サイズウィンドウ限界を持たないソフトウェアにより適切に発見される。
【００７４】
例示的なＭｅｒｃｕｒｙ  ＢＬＡＳＴを使用する無ギャップ伸長前置フィルタの例示的な実施例は、図１０に示されている。所定のウィンドウの長さである新しいパラメータＬｗを加えて図９の同じパラメータを使用すると、Ｌｗ＝１９、ｗ＝５、α＝１、β＝−３であり、全体として番号６５で示されているような、本発明、例えば、Ｍｅｒｃｕｒｙ  ＢＬＡＳＴ、無ギャップ伸長は、ウィンドウの一番左の塩基（角括弧で示されている）から始まり、右に移動し、ウィンドウ内の最良スコア部分文字列を計算して行く。この実施例では、アルゴリズムは、図９と１０の両方で同じ結果を出した。しかし、これは、一般的に必ずしもその状況とはならない。
【００７５】
本発明の例示的なシステムは、アプリケーションパイプラインとして略図形態で示されており、全体として番号７０で示され、図１１Ａに示されている。このシステムは、好ましくは、ディスクベースの計算を高速化するように設計されたインフラであり、ディスク媒体から直接、データ５２を限定はしないがＦＰＧＡ（フィールドプログラマブルゲートアレイ）７４などのプログラム可能論理デバイスにストリーミングすることにより現在のディスクで利用可能な高入出力（Ｉ／Ｏ）帯域幅を使用する。
【００７６】
ストリーミングデータは、ステージ１ａとして指定されている、ハードウェアワードマッチング前置フィルタ７６に配送される。データストリームは、前置フィルタで処理された後、上ですでに説明されているようにワードマッチングモジュール８０に入り、これはステージ１ｂとして指定されている。ワードマッチングモジュール８０は、メモリ７８、例えばＳＲＡＭ（電力が供給されている限り、メモリ内にデータビットを保持し、定期的にリフレッシュされる必要のないスタティックランダムアクセスメモリ）を使用する。ステージ１ａおよび１ｂ、７６および８０の組み合わせは、図１にすでに示されている、すでに説明されている第１のステージ（ステージ１）５４を形成する。
【００７７】
次いで、データは、ステージ２ａと指定されている、専用ハードウェアおよび／またはファームウェアを含む無ギャップ伸長前置フィルタ８２に入る。次いで、前置フィルタの出力は、ステージ２ｂとして指定され、ソフトウェアを含む、無ギャップ伸長８４である、ステージ２の残り部分の中に入る。ステージ２ａおよび２ｂ、８２および８４の組み合わせは、図１にすでに示されている、すでに説明されている第２のステージ（ステージ２）５６を形成する。
【００７８】
代替えとして、ハードウェア／ファームウェアリソースが十分利用可能である場合、ステージ２ｂとして指定されている、ソフトウェア無ギャップ伸長８４は、ステージ２として指定され、図１１Ｂに示されている、単独の無ギャップ伸長として機能するハードウェア／ファームウェア無ギャップ伸長前置フィルタ８２によりなくすことができる。この方法は、無ギャップ伸長のソフトウェア部分が生物学的配列類似検索計算、例えばＢＬＡＳＴ検索を利用してなくすことができるため、スループットを高めることができる。
【００７９】
データストリームは、最終的に、ステージ３として指定されている、ギャップ伸長５８に入る。無ギャップ伸長およびギャップ伸長は、限定はしないが、プロセッサ８８を含む、さまざまな計算機構により操作することができる。前置フィルタ（ステージ２ａ）８２は、図１２の計算が連続的に現れるにも関わらず、ハードウェア実装に適している。
【００８０】
無ギャップ伸長前置フィルタ設計８２は、内部的に完全パイプライン化されており、１クロック毎に１マッチを受け付ける。前置フィルタは、多数の設計特有の制約条件に基づいて選択されたパラメータでパラメータ化可能である。コマンドは、マッチスコア、ミスマッチスコア、およびカットオフ閾値などのパラメータを構成するようにサポートされる。したがって、感度とスループットとの間にトレードオフの関係があり、これは、ユーザーの裁量に任される。
【００８１】
ｗ−ｍｅｒマッチングステージで生成するのは、入力よりも出力のほうが多いため、全体として番号８２で示され、図１３Ａに示されている、無ギャップ伸長、つまりステージ２ａへの入力には、２つの独立のデータパスが使用される。ｗ−ｍｅｒ／コマンドおよびデータは、解析され、一方のパス９２上で受け取られ、データベースからのデータは、他方のパス９３上に受け取られる。コマンドは、アクティブ制御有効信号でサポートされており、さらに、これらのコマンドは、所定フォーマットで送信される。また、コマンドは、図１１Ａに示されている、プログラム可能論理デバイス７４、例えばＦＰＧＡが、再構成される必要のないように設計されている。
【００８２】
モジュールは、３つのパイプラインステージに編成されている。これは、伸長コントローラ９４、ウィンドウルックアップモジュール９５、およびスコアリングモジュール９８を備える。入力を解析して、共有されているｗ−ｍｅｒコマンド９２およびデータベースストリーム９３を逆多重化する伸長コントローラ９４がある。すべてのｗ−ｍｅｒマッチおよびデータベースストリームは、伸長コントローラ９４を通って、ウィンドウルックアップモジュール９５内に流れ込む。ウィンドウルックアップモジュール９５は、データベースストリームおよび問い合わせの適切な部分文字列を取り込んで、アライメントウィンドウを形成する役割を持つモジュールである。
【００８３】
ウィンドウルックアップモジュール９５は、図１３Ｂにさらに構造に関する詳細がわかるように例示されている。好ましくは、ただし必ずというわけではないが、問い合わせは、図１１Ａに示されている、プログラム可能論理デバイス７４、例えばＦＰＧＡ上のデュアルポートランダムアクセスメモリ（ＲＡＭ）を使用してチップ上に格納される。問い合わせは、それぞれの生物学的配列類似検索計算、例えばＢＬＡＳＴ検索の始めにストリーミングされ（２０２）、データベースの終わりに達するまで固定される。問い合わせストリーム２０２のサイズは、メモリ量、例えば問い合わせバッファ２０４内に用意されるブロックランダムアクセスメモリ（ＲＡＭＳ）で制限される。データベースは、さらに、問い合わせストリーム２０２と同様にしてストリーミングされ（２０６）、データベースバッファ２０８に送られる。データベースバッファ２０８は、好ましくは、必ずというわけではないが、循環バッファである。循環バッファの使用は、到着しているｗ−ｍｅｒから形成されるウィンドウが必要とすると思われるデータベースストリーム２０６の必要なセクションを保持するのに役立つ。ｗ−ｍｅｒ生成は、図１に示されているように、第１のステージ５４で実行されるので、それぞれの伸長を要求を受け入れるためにデータベースストリーム２０６のごくわずかの部分をデータベースバッファ２０８内にバッファリングするだけでよい。
【００８４】
データベースバッファ２０８は、好ましくは、ただし必ずというわけではないが、順序の狂っている固定距離のｗ−ｍｅｒを正しく処理できるように構築される。前のほうで参照されているＢＬＡＳＴＰ実装では、図１１Ａに示されているように、ワードマッチングステージ８０内のｗ−ｍｅｒの順序が狂っている可能性があるため、これは重要である。
【００８５】
ウィンドウルックアップモジュール９５は、好ましくは、ただし必ずというわけではないが、図１３Ｂに示されている６段パイプラインとして編成される。これは、第１のステージ２１０、第２のステージ２１２、第３のステージ２１４、第４のステージ２１６、第５のステージ２１８、および第６のステージ２２０を含む。１クロックパルス毎に１回出てくる、前のステージ、つまり、図１３Ａに示されている伸長コントローラ９４からの要求に追随するために広範なパイプライン化が必要になることがある。
【００８６】
パイプライン２１０の第１のステージでは、入ってくるｗ−ｍｅｒおよび構成可能ウィンドウサイズに基づいて問い合わせおよびデータベースウィンドウの先頭を計算する。問い合わせ２２２のオフセットおよびデータベース２２４のオフセットが、第１のステージ２１０に送られる。パイプライン２１０のこの第１のステージでは、入ってくるｗ−ｍｅｒおよび構成可能ウィンドウサイズに基づいて問い合わせウィンドウおよびデータベースウィンドウの先頭を計算する。次いで、ウィンドウの先頭のオフセットが、バッファモジュール、つまり、第２のステージ２１２、第３のステージ２１４、第４のステージ２１６、さらには第５のステージ２１８に渡され、メモリ、例えばブロックＲＡＭからウィンドウのスーパーセットを読み込むタスクを開始する。ウィンドウ境界がワード境界上にあるという保証はないため、メモリ、例えばブロックＲＡＭから余分に１ワード分のデータが取り出されなければならない。したがって、データと余分なワードに相当するウィンドウサイズを保持する一時バッファから正確なウィンドウが構築されるように余分なワードがそれぞれのルックアップで取り込まれる。次の４つのステージ、つまり、第２のステージ２０２、第３のステージ２１４、第４のステージ２１６、および第５のステージ２１８は、バッファルックアッププロセスで入力データロックステップを移動し、パイプラインのストールが必ず正しい方法で取り扱われるようにする。最後に、問い合わせおよびデータベースウィンドウのスーパーセットが、フォーマット出力２２０のため最終ステージまたは第６のステージに到達する。出力は、シードアウト２２６、問い合わせウィンドウ２２８、およびデータベースウィンドウ２３０を含み、これによりバッファの正しいウィンドウが抽出され、出力として登録される。
【００８７】
例示的な、ただし限定されない、実施形態では、問い合わせは、チップ上で、デュアルポートブロックランダムアクセスメモリ（ＢＲＡＭ）を使用し、限定はしないが、図１１Ａに示されているようなＦＰＧＡ（フィールドプログラマブルゲートアレイ）７４などのプログラム可能論理デバイスにバッファリングされる。好ましくは、ただし必ずというわけではないが、データベースストリームは、好ましくはＢＲＡＭから形成されうる、循環バッファ内にバッファリングされる。すでに述べたように、ｗ−ｍｅｒ生成は、伸長コントローラ９４の第１のステージにおいて実行される。データベースストリーム９３に関して、それぞれの入力ｗ−ｍｅｒが順番にステージ１ａ、７６およびステージ１ｂ、８０から到着するので、それぞれの入力ｗ−ｍｅｒを受け入れるためにわずかな量のデータベースストリーム９３がバッファリングされるだけでよい。
【００８８】
例示的な、ただし限定されない、デュアルポートブロックランダムアクセスメモリ（ＢＲＡＭ）は、ステージ１ａ、７６およびステージ１ｂ、８０において非常に有用なリソースであるため、メモリ、例えば、デュアルポートブロックランダムアクセスメモリＢＲＡＭは、時間多重化され、これによりクワッドポートＢＲＡＭ構造を形成する。ウィンドウは、取り込まれた後、スコアリングモジュール９８に渡され、レジスタに格納される。スコアリングモジュール９８は、図１２の伸長アルゴリズム６６の再帰を実装する。計算は複雑すぎて単一サイクルでは実行できないため、スコアラーは広範にわたってパイプライン化される。
【００８９】
スコアリングパイプライン９８の第１のステージは、図１３Ａに示されている。塩基比較器９６は、それぞれ図１３Ａおよび１４に示されているように、番号３０２および３０４で示されているような並列レジスタ内にすべての塩基ペアを受け取る。これらのペアは、比較スコアをウィンドウ内のそれぞれの塩基ペアに割り当てる複数の比較器３０６に送り込まれる。例示的であるが、好ましい実施形態では、ＤＮＡ配列、例えば、ＢＬＡＳＴＮについて、塩基比較器９６は、番号３１０で全体として示されている報酬＋αをそれぞれのマッチした塩基ペアに割り当て、番号３１２で全体として示されているペナルティ−βをそれぞれのミスマッチしたペアに割り当てる。スコア計算は、そのスコアについて選択肢がさらに多くある点を除き、タンパク質配列分析、例えば、ＢＬＡＳＴＰの場合と同じである。ＢＬＡＳＴＰでは、報酬＋αおよびペナルティ−βは、２つのシンボル３０２、３０４の連接によりインデックス付けされたルックアップテーブルからの値で置き換えられる。比較スコアのすべての計算は、Ｌｗ比較器を使用して単一サイクルで実行される。スコアが計算された後、計算されたスコアが、後のスコアリングステージ３０９に送られる。
【００９０】
スコアリングモジュール９８は、好ましくは、ただし必ずというわけではないが、古典的なシストリックアレイとして配置される。前のステージからのデータは、クロックパルス毎に読み取られ、結果が、次のクロックパルスで続くステージに出力される。連続パイプラインステージ９７における比較スコアの格納は、連続するステージ毎に減少し、これは図１３Ａに示されている。この減少は、ウィンドウ位置「ｉ」に対する比較スコアがｉ番目のパイプラインステージで消費されるためあり得ることであり、次いで、後のステージではｉよりも大きいウィンドウ位置のみを検査するので、破棄されてもよい。
【００９１】
データ移動のこの構造は、図１５にさらに詳しく示されており、スコアリングステージのシストリックアレイとして全体的に番号９７で示されている。暗くなっているレジスタ３２６は、それぞれのパイプラインステージにおいて処理されるｗ−ｍｅｒに対する必要な比較スコアを保持する。図１５は、説明が簡単になるようにそれぞれのスコアラーステージに対し単一比較スコアが落とされることを示しているが、好ましい実施形態は、ステージ毎に２つの比較スコアを落とすことを含む。また、複数のパイプラインスコアリングステージ３３０もある。図１５では、データは左から右に流れる。明るいレジスタ３２８は、パイプライン計算レジスタであり、前のスコアリングステージから、パイプライン７０内の異なるｗ−ｍｅｒを含むレジスタのそれぞれの列を持つ次のステージへ再帰の状態を転送するために使用される。初期設定３２２は、明るいレジスタ３２８、暗いレジスタ３２６、およびスコアリングステージ３３０に与えられる。
【００９２】
個々のスコアリングステージのインターフェイスは、全体として番号３３０で示され、図１６に示されている。スコアリングステージ３３０の上に入るように示されている値は、前のスコアリングステージから伝播された動的計画再帰の状態である。これらの値は、第１のレジスタ３４２への入力として読み込まれ、結果が、右に示されている出力レジスタ３６４に格納される。パイプライン９７内のそれぞれのスコアリングステージ３６２は、図１２で説明されているアルゴリズムの１２行目〜１９行目で示されている動的計画再帰を実行する組み合わせ論理を含む。これは、番号３４４で示されているγに対する値、番号３４６で示されているＢに対する値、番号３４８で示されているΓに対する値、番号３５０で示されているＢの最大値、つまりＢｍａｘ、および番号３５２で示されているＥの最大値、つまりＥｍａｘを含む。
【００９３】
第２のレジスタ３６０の左から入るデータは、比較スコア３５８、つまり、α／β、および与えられたｗ−ｍｅｒに対するデータベースオフセット３５４および問い合わせオフセット３５６であり、これらは、再帰の状態とは独立している。高クロック周波数設計を維持するために、それぞれのスコアリングステージは、１クロックサイクルにつきループの２回繰り返しのみを計算し、その結果、完全な計算に対しＬｗ／２のスコアリングステージが得られる。これは、番号３６１で示されているステップ１、および番号３６３で示されているステップ２となっており、図１２に示されているアルゴリズム６６の１２行目から１９行目の２回繰り返しを実行する。これは、ループの繰り返しは何回でも使用できるので、単に例示的な、ただし限定されない数の単一ステージ内でのループの繰り返しである。このトレードオフの関係は、好ましい、例示的な、ただし限定されないハードウェアを使用して面積と速度を対比したときに好ましいものといえる。したがって、パイプライン７０が満杯のときにプロセッサのスコアリングステージ３６２内で同時に処理されるＬｗ／２個の独立のｗ−ｍｅｒがある。
【００９４】
パイプライン計算では、その後のスコアリングステージ、例えばｉ＋１に供給される出力３６４をレジスタに格納する。これは、番号３６６で示されているγに対する値、番号３６８で示されているＢに対する値、番号３７０で示されているΓに対する値、番号３７２で示されているＢの最大値、つまりＢｍａｘ、および番号３７４で示されているＥの最大値、つまりＥｍａｘを含む。
【００９５】
スコアリングモジュールの最終パイプラインステージは、図１３Ａに示されている閾値比較器９９である。比較器は、完全スコアリング領域を取り、その領域を破棄するか、または保持するかを決定する。この決定は、ユーザー定義閾値Ｔだけでなく、最高スコアリング部分文字列の位置に関するアライメントのスコアに基づく。最高スコアが閾値よりも高い場合、その領域は通り渡される。さらに、最大スコアリング部分文字列がウィンドウのいずれかの境界を交差する場合、その領域も、スコアに関係なく、渡される。いずれの条件も成立しない場合、所定の長さの部分文字列、つまり領域は、破棄される。渡される領域は、図１３Ａにおいて番号１００で示されている。
【００９６】
任意選択の、例示的な実装では、図１３Ａに示されているような無ギャップ伸長前置フィルタ８２は、限定はしないが、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）７４などの再構成可能ハードウェア上で論理セルおよび２７個のＢＲＡＭの約３８％を使用する。例示的な、ただし限定されない実施例は、Ｘｉｌｉｎｘ（登録商標）Ｖｉｒｔｅｘ−ＩＩ  ６０００（登録商標）シリーズＦＰＧＡを含む。Ｘｉｌｉｎｘ，Ｉｎｃ．は、事業の所在地を２１００  Ｌｏｇｉｃ  Ｄｒｉｖｅ，Ｓａｎ  Ｊｏｓｅ，Ｃａｌｉｆｏｒｎｉａ  ９５１２４−３４００に置くＤｅｌａｗａｒｅ州の法人である。これは、再構成可能ハードウェア、例えばＦＰＧＡ自体との間でデータを出し入れするためのインフラストラクチャを備える。例示的な、ただし限定されない現在の設計は、９６ＭＨｚで動作し、１クロックで１つのｗ−ｍｅｒを処理する。完全なＭｅｒｃｕｒｙ  ＢＬＡＳＴＮ設計では、論理セルおよび１３４個のＢＲＡＭの約６５％を使用する。
【００９７】
図１３Ａに示されているように、無ギャップ伸長前置フィルタ８２のパフォーマンスには多くの側面がある。第１は、個別のステージスループットである。無ギャップ伸長ステージ（ステージ２ａ）８２は、パイプライン７０全体においてボトルネックとならないように十分高速に実行されなければならない。第２に、無ギャップ伸長ステージ（ステージ２ａ）８２は、下流ステージではなおいっそう計算量が多いので、できる限り多くのｗ−ｍｅｒを効果的にフィルタ処理しなければならない点である。最後に、上記は、有意なアライメントのうちの大きな割合をうっかり落としてしまうことなく達成されなければならない（つまり、偽陰性率は制限されなければならない）。
【００９８】
第１に、無ギャップ伸長ステージ単独のスループットパフォーマンスは、データ入力率の関数となっている。例示的な、ただし限定されない実施例では、無ギャップ伸長ステージは、１クロックに１つのｗ−ｍｅｒを受け付け、９６ＭＨｚで動作する。したがって、フィルタの最大スループットは、１入力マッチ／サイクル掛ける９６ＭＨｚ＝９６Ｍｍａｔｃｈｅｓ／秒である。これは、図１に示されているように、すでに説明されているベースラインシステム上で実行されるソフトウェア無ギャップ伸長８２に対し２５倍のスピードアップを実現する。この分析は、仮定されているパラメータおよび制約条件に基づくモデリングだけに基づいており、実際の結果は多様である。
【００９９】
図１７は、アプリケーションスループット（毎秒１００万塩基の単位で、完全なパイプライン７０の取り込み率により定量化されている）を、毎秒１００万マッチを単位として第２のステージ（ステージ２）５６単独の取り込み率により定量化されている、図１に示されているような、第２のステージ（ステージ２）５６で達成可能なパフォーマンスの関数として示している。図１７は、２５，０００塩基の二本鎖問い合わせおよび２０，０００塩基二本鎖問い合わせの両方に対する結果を含む。
【０１００】
図１８は、ソフトウェア実装に関して図１１Ａに示されているような前置フィルタステージ（ステージ２ａ）８２を備える本発明の好ましい実施形態に対する結果として得られるスピードアップ対スループット（両方の問い合わせサイズについて）をプロットしたグラフである。ここでも、この分析は、仮定されているパラメータおよび制約条件に基づくモデリングだけに基づいており、実際の結果は多様である。ソフトウェアプロファイリングは、２５，０００塩基の問い合わせについて、０．２６５μｓ／マッチの第２のステージ（ステージ２）５６単独に対する平均実行時間を示している。これは、図１７および１８の左に向かってプロットされている、３．８Ｍｍａｔｃｈｅｓ／ｓのスループットに対応する。第２のステージ（ステージ２）５６のパフォーマンスが高められると、パイプライン７０全体のパフォーマンスも、第２のステージ（ステージ２）５６がもはやボトルネックステージでなくなるまで比例して増大する。
【０１０１】
第２のステージ（ステージ２）５６におけるこのパフォーマンスがシステム全体に及ぼす影響を調べるために、図１７および１８のグラフに戻る。約３５Ｍｍａｔｃｈｅｓ／ｓを超えた場合、システム全体のスループットは、最大速度１４００Ｍｂａｓｅｓ／ｓであり、４８倍のスピードアップ（２５，０００塩基の問い合わせに対し、ソフトウェア、例えば、ＮＣＢＩ  ＢＬＡＳＴＮのそれの４８倍）および３８倍のスピードアップ（２０，０００塩基の問い合わせに対しソフトウェア、例えば、ＮＣＢＩ  ＢＬＡＳＴＮのそれの３８倍）となる。
【０１０２】
感度に影響を及ぼす無ギャップ伸長のパラメータは２つある。第１のパラメータは、使用されるスコア閾値であり、これは、生成されるＨＳＰの数に影響を及ぼす。第２のパラメータは、ウィンドウの長さであり、これは、生成される偽陰性の数に影響を及ぼし得る。ウィンドウ境界がスコア閾値よりも低くなる前に十分に多くのミスマッチを有するが、境界のすぐ外では多くのマッチを有するＨＳＰは、間違って拒絶される。
【０１０３】
ハードウェア無ギャップ伸長８２の機能的感度を評価するために、ソフトウェア、例えば、ＮＣＢＩ  ＢＬＡＳＴＮの計装バージョンを使用して測定が実行された。標準無ギャップ伸長ステージ、例えば、ＮＣＢＩの前に、新しい無ギャップ伸長アルゴリズムのソフトウェアエミュレータが置かれた。次いで、統計データが収集されたが、これは、無ギャップ伸長前置フィルタステージ８２にｗ−ｍｅｒがどれだけ到着したか、およびどれだけが通ったかを示している。
【０１０４】
これらの統計データは、無ギャップ伸長、第２のステージ（ステージ２）５６、図１、単独、例えば、ＮＣＢＩ  ＢＬＡＳＴＮについて、ハードウェアエミュレータを適所に置いて、収集された。ヒトとマウスのゲノムからデータセットが生成された。問い合わせは、さまざまなサイズ（例えば、１０ｋｂａｓｅ、１００ｋｂａｓｅ、および１Ｍｂａｓｅ）の統計的に有意なサンプルであった。データベースストリームは、低複雑度であり、反復配列が取り除かれたマウスゲノムであった。
【０１０５】
図１９は、番号３８０で全体として示されている表であり、例示的な、ただし限定されないハードウェア実装で使用されるウィンドウサイズである、６４塩基のウィンドウサイズに対する結果をまとめたものである。２０のスコア閾値は、無ギャップ伸長または第２のステージ（ステージ２）８２、図１１Ａ、例えば、ＮＣＢＩ  ＢＬＡＳＴＮにおける既定値に対応する。除去分画は、入力ｗ−ｍｅｒに対する出力ＨＳＰの測定された比率である。この値は、フィルタ処理ｗ−ｍｅｒにおける全体的な第２のステージ（ステージ２）８２、図１１Ａの有効性を定量化するものであり、（ステージ２ｂ）８４では処理される必要はない。見つかった割合は、図１９に示されているように、ＮＣＢＩ  ＢＬＡＳＴＮの出力に関するＭＥＲＣＵＲＹ  ＢＬＡＳＴの出力中に存在するギャップアライメントのパーセンテージである。
【０１０６】
６４塩基のウィンドウ長を使用することで、無ギャップ伸長前置フィルタ８２は、そのすべての入力の９９．５％から９９．９９％までの間でフィルタ処理で除去できる。例えば、１７のミスしたＨＳＰの閾値から、大半（９９．９５％）の有意なＨＳＰを維持しながら、高い除去分画の間の適切なトレードオフの関係が規定される。これは、結果として、ソフトウェアシステム、例えば、ＮＣＢＩ  ＢＬＡＳＴにより見つかった１０，３３４個のＨＳＰのうち５つのミスしたＨＳＰになる。
【０１０７】
したがって、生物学的配列類似検索は、パフォーマンスに厳しい無ギャップ伸長ステージ５６を使用して文字データの高速ストリームをフィルタ処理するように設計されたパイプライン７０により実用的に高速化されうる。本発明は、並列性が高く、パイプライン化実装は、２５倍以上高速に実行し、アクセラレータ全体を約４０から５０倍高速に実行できるようにしながら、ＢＬＡＳＴＮなどのソフトウェアから得られる結果と匹敵する結果をもたらす。
【０１０８】
例えば、本発明の技術は、生物学的配列類似検索以外のシードアライメント検索技術に対しワードマッチングを実行するために使用されうる。さらに、本発明の技術は、ＢＬＡＳＴＰ、ＢＬＡＳＴＸ、ＴＢＬＡＳＴＮ、およびＴＢＬＡＳＴＸなどのＢＬＡＳＴＮ以外のＢＬＡＳＴバージョンに適用することもできる。さらに、好ましい実施形態が説明されており、そこでは、データベース配列または問い合わせ配列内のそれぞれのマッチするｗ−ｍｅｒの開始位置は、さまざまなパイプラインステージにより決定される。しかし、これらの位置は、必ずしも、開始位置である必要はないことに留意されたい。例えば、データベースおよび問い合わせ配列内のマッチするｗ−ｍｅｒの位置を識別するために、終了位置または何らかの中間位置も使用されうる。これらの変更形態および修正形態は、本発明の代替え実施形態とみなすべきであり、本発明は、付属の請求項およびその法律上の等価物の範囲によってのみ制限されるものとみなすべきである。
【０１０９】
こうして、新規性のある発明のいくつかの実施形態について図示され、説明された。前記の説明から明らかなように、本発明のいくつかの態様は、本明細書に例示されている実施例の具体的詳細により限定されることはなく、したがって、当業者であれば他の修正形態および応用、またはその等価物を思いつくと考えられる。「持つ、有する、備える（ｈａｖｅ）」、「持っている、有している、備えている（ｈａｖｉｎｇ）」、「含む、備える（ｉｎｃｌｕｄｅｓ）」、および「含んでいる、備えている（ｉｎｃｌｕｄｉｎｇ）」という用語、および明細書において使用されているような類似の用語は、「任意選択（ｏｐｔｉｏｎａｌ）」または「含むことができる（ｍａｙ  ｉｎｃｌｕｄｅ）」という意味で使用され、「必要である、必須である（ｒｅｑｕｉｒｅｄ）」として使用されることはない。ただし、本発明の構成の多くの変更形態、修正形態、変形形態、ならびに他の用途および応用は、明細書および付属の図面を考察した後、当業者にとっては明白なことになるであろう。本発明の精神および範囲から逸脱しないこのような変更形態、修正形態、変形形態、ならびに他の用途および応用は、請求項によってのみ限定される本発明の対象範囲であるとみなされる。
【図面の簡単な説明】
【０１１０】
【図１】３つのメインステージに分けられた、本発明の好ましい、限定されない、例示的な実施形態による３段パイプラインのブロック図概略である。
【図２】本発明の好ましい、限定されない、例示的な実施形態によるステージ１パイプライン、例えば、ＢＬＡＳＴＮの例示的なブロック図である。
【図３】本発明の好ましい、限定されない、例示的な実施形態による、生物学的データパイプラインのハードウェアプラットフォームの概略図である。
【図４】生物学的配列データストリームのサンプル部分を示す図である。
【図５】問い合わせ配列が、図３に示されているデータベース配列に関する複数のｗ−ｍｅｒに分割できることを示す図である。
【図６Ａ】本発明の好ましい、限定されない、例示的な実施形態による例示的なＢｌｏｏｍフィルタストリームを示す図である。
【図６Ｂ】本発明の好ましい、限定されない、例示的な実施形態による同じデュアルポートブロックランダムアクセスメモリ（ＢＲＡＭ）を共有するように構成されたＢｌｏｏｍフィルタの配置を示す図である。
【図６Ｃ】本発明の好ましい、限定されない、例示的な実施形態による、図６Ｂに示されているような、４つのＢｌｏｏｍフィルタ配置から形成された１６個のＢｌｏｏｍフィルタを備えるＢｌｏｏｍフィルタステージを示す図である。
【図７】Ｂｌｏｏｍフィルタステージ内にあるか、または関連付けられ、問い合わせｗ−ｍｅｒとの可能なマッチであるデータベースｗ−ｍｅｒのデータベース配列内の開始位置を識別するように容易に構成される制御論理の概略および流れ図である。
【図８】本発明の好ましい、限定されない、例示的な実施形態による例示的なハッシングステージおよびハッシュテーブルを例示する図である。
【図９】データの所定のウィンドウ内の２つの方向の分析を含む無ギャップ伸長の分析と関連付けられている例示的なデータウィンドウを示す図である。
【図１０】本発明の好ましい、限定されない、例示的な実施形態による所定のデータウィンドウ内の単一方向の分析を含む無ギャップ伸長の分析と関連付けられている例示的なデータウィンドウを示す図である。
【図１１Ａ】第１および第２のステージがそれぞれ２つのサブステージに分けられている、図１の３段パイプラインのブロック図概略である。
【図１１Ｂ】第１ステージのみが２つのサブステージに分けられている、図１に示されている本発明の他の実施形態の３段パイプラインのブロック図概略である。
【図１２】本発明の好ましい、限定されない、例示的な実施形態による無ギャップ伸長アルゴリズムで使用される擬似コードの例示的な、ただし限定されない、リスティングである。
【図１３Ａ】本発明の好ましい、限定されない、例示的な実施形態による無ギャップ伸長の前置フィルタステージの例示的な、ただし限定されない、ブロック図である。
【図１３Ｂ】図１３Ａに示されているように、無ギャップ伸長に対する前置フィルタステージのウィンドウルックアップモジュールの例示的な、ただし限定されない、ブロック図である。
【図１４】本発明の好ましい、限定されない、例示的な実施形態による、図１３Ａに示されているような、塩基比較器の例示的な、ただし限定されない、ブロック図である。
【図１５】本発明の好ましい、限定されない、例示的な実施形態による、図１３Ａに示されているような、スコアリングステージのアレイの例示的な、ただし限定されない、ブロック図である。
【図１６】本発明の好ましい、限定されない、例示的な実施形態による、図１５に示されているような、単一の２ステップスコアリングステージの例示的な、ただし限定されない、ブロック図である。
【図１７】サイズ２０ｋｂａｓｅおよび２５ｋｂａｓｅの問い合わせに対する無ギャップ伸長のスループットの関数としてのパイプライン全体のスループットのグラフ表現である。
【図１８】本発明の好ましい、限定されない、例示的な実施形態による前置フィルタ処理を用いるサイズ２０ｋｂａｓｅおよび２５ｋｂａｓｅの問い合わせに対する無ギャップ伸長のスループットの関数としてのパイプライン全体のスピードアップのグラフ表現である。
【図１９】本発明の好ましい、限定されない、例示的な実施形態による無ギャップ伸長に対する例示的な、ただし限定されない、前置フィルタの感度の結果をまとめた表である。
【図２０】本発明の好ましい、限定されない、例示的な実施形態による無ギャップ伸長で使用される図１２に示されているアルゴリズムの流れ図である。
【図１】
2008532177.tif 000003
【図２】
2008532177.tif 000004
【図３】
2008532177.tif 000005
【図４】
2008532177.tif 000006
【図５】
2008532177.tif 000007
【図６Ａ】
2008532177.tif 000008
【図６Ｂ】
2008532177.tif 000009
【図６Ｃ】
2008532177.tif 000010
【図７】
2008532177.tif 000011
【図８】
2008532177.tif 000012
【図９】
2008532177.tif 000013
【図１０】
2008532177.tif 000014
【図１１Ａ】
2008532177.tif 000015
【図１１Ｂ】
2008532177.tif 000016
【図１２】
2008532177.tif 000017
【図１３Ａ】
2008532177.tif 000018
【図１３Ｂ】
2008532177.tif 000019
【図１４】
2008532177.tif 000020
【図１５】
2008532177.tif 000021
【図１６】
2008532177.tif 000022
【図１７】
2008532177.tif 000023
【図１８】
2008532177.tif 000024
【図１９】
2008532177.tif 000025
【図２０】
2008532177.tif 000026
【国際調査報告】
2008532177.tif 000027
2008532177.tif 000028
2008532177.tif 000029
2008532177.tif 000030
2008532177.tif 000031
2008532177.tif 000032
2008532177.tif 000033