生物学的な配列情報の検索装置、検索方法および検索プログラム
【課題】大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索する。
【解決手段】中央処理部２００と、中央処理部２００とは別個の素子に設けられている並列処理部３００と、を備え、生物学的配列情報に関する検索対象データベース１０２との間で通信可能に構成されている生物学的配列情報検索装置１００を提供する。中央処理部２００は、問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部２０４を含む。並列処理部３００は、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを行い、１次候補配列を抽出する１次候補配列抽出部３０２を含む。さらに、中央処理部２００は、問い合わせ配列と１次候補配列との間で配列マッチングを行い、２次候補配列を抽出する２次候補配列抽出部２１０を含む。
【解決手段】中央処理部２００と、中央処理部２００とは別個の素子に設けられている並列処理部３００と、を備え、生物学的配列情報に関する検索対象データベース１０２との間で通信可能に構成されている生物学的配列情報検索装置１００を提供する。中央処理部２００は、問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部２０４を含む。並列処理部３００は、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを行い、１次候補配列を抽出する１次候補配列抽出部３０２を含む。さらに、中央処理部２００は、問い合わせ配列と１次候補配列との間で配列マッチングを行い、２次候補配列を抽出する２次候補配列抽出部２１０を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、塩基配列、アミノ酸配列等の生物学的な配列情報の検索装置、検索方法および検索プログラムに関し、特に、検索処理の高速化に関する。
【背景技術】
【０００２】
分子生物学の分野では、ＤＮＡ、遺伝子、タンパク質等の解析のための情報処理技術の有用性が高まっている。この分野では、配列情報を解析するために情報処理技術が用いられる。この種の技術はバイオインフォマティクスといわれる。
【０００３】
例えば、ＳＮＰｓ（スニプッス、単一塩基多型）解析は、ほぼ同一の多数の塩基配列を解析して、局所的に異なる部分をもつ塩基配列を求める。
【０００４】
また例えば、ホモロジー検索は、複数の配列情報が似ているか、そしてどのように似ているかの情報を求める。ホモロジー検索方法としては、例えば、ブラスト（ＢＬＡＳＴ）法およびファスタ（ＦａｓｔＡ）法が知られている。
【０００５】
ブラスト法は、ギャップの挿入を行わずに局所的によく一致する部位を探索する。このような部位を高スコア断片と呼ぶ。そして、高スコア断片が前後に伸長される。
【０００６】
ファスタ法においては、配列が長く一致する部分を求める。この処理のために、従来は、複数の配列情報の一致する要素をプロットしたドットマトリックス情報が利用される。そして、一致部分の周囲に対して動的計画法によるアライメントが行われる。
【０００７】
これらの配列解析では、大量の情報を高速に処理することが求められる。非常に長い配列が処理され、また、多数の配列が処理されるからである。しかし、多くの場合には、配列解析の大量の情報処理は、専ら大型コンピュータの大きな処理能力に頼って実現されており、配列情報の高速処理技術は十分に確立していない。そして、配列解析の研究が進み、創薬および医療などの現場での分子生物学の実用化が進展するのにつれて、配列情報処理の高速化の重要性も高まると考えられる。また、大型コンピュータではなく、パーソナルコンピュータ程度の比較的小型なコンピュータによっても、大量の配列情報を高速に処理することが求められる。
【０００８】
このような小型コンピュータによっても、大量の配列情報を高速に処理することができる、従来の生物学的な配列情報の処理装置としては、例えば特許文献１に記載されたものがある。特許文献１に記載の装置では、並列照合機能をもつ記憶処理装置、典型的にはＣＡＭ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）が用いられる。
【０００９】
特許文献１に記載の装置では、この記憶処理装置に、配列情報が、被照合データとして用いるために記憶される。そして、照合データと被照合データを並列処理にて記憶処理装置に照合させて、照合データと被照合データの一致を示す情報を得ることにより、配列解析情報を得る。好ましい態様では、複数の配列が、記憶処理装置であるＣＡＭに、照合方向と交差する方向を向けて、照合方向に並ぶように記憶される。なお、照合データとしては同一文字列が用いられる。そして、ＣＡＭの照合により、複数の配列が一致するか否かが判定される。その結果、複数の配列を一つずつ照合対象から除外すると、どの配列が異なるのかが分かる。
【００１０】
【特許文献１】特開２００３−２１６６１５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記文献記載の従来技術は、生物学的な配列情報を高速かつ精度よく検索する上でさらなる改善の余地を有していた。
【００１２】
本発明は上記事情に鑑みてなされたものであり、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することを目的とする。
【課題を解決するための手段】
【００１３】
本発明によれば、生物学的配列情報に関する検索対象データベースとの間で通信可能に構成されている生物学的配列情報検索装置であって、中央処理部と、中央処理部とは別個の素子に設けられている並列処理部と、を備え、中央処理部は、生物学的情報についての問い合わせ配列を取得する問い合わせ配列取得部と、問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部と、を含み、並列処理部は、並列処理用問い合わせ配列と検索対象データベースとの間で、配列マッチングを行い、並列処理用問い合わせ配列にマッチングする１次候補配列または１次候補配列の検索対象データベース中の座標を抽出する１次候補配列抽出部を含み、さらに、中央処理部は、問い合わせ配列と、１次候補配列または検索対象データベース中の１次候補配列の座標の近傍領域との間で、配列マッチングを行い、問い合わせ配列にマッチングする２次候補配列を抽出する２次候補配列抽出部と、２次候補配列に基づく検索結果を出力する出力部と、を含む、ことを特徴とする生物学的配列情報検索装置が提供される。
【００１４】
この構成によれば、まず、中央処理部において問い合わせ配列から並列処理用問い合わせ配列を生成し、次いで、並列処理部において検索対象データベースから並列処理用問い合わせ配列にマッチングする１次候補配列の抽出を行い、再び、中央処理部において１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する形で、互いに別個の素子に設けられている中央処理部および並列処理部がそれぞれの役割を効率的に分担している。
【００１５】
このため、この構成によれば、並列処理部では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、この構成によれば、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００１６】
また、本発明によれば、生物学的配列情報に関する検索対象データベースとの間で通信可能に構成されている生物学的配列情報検索装置であって、中央処理部と、並列処理部と、を備え、中央処理部は、生物学的情報についての問い合わせ配列を取得する問い合わせ配列取得部と、問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部と、を含み、並列処理部は、並列処理用問い合わせ配列と検索対象データベースとの間で、配列マッチングを行い、並列処理用問い合わせ配列にマッチングする１次候補配列または１次候補配列の検索対象データベース中の座標を抽出する１次候補配列抽出部を含み、さらに、中央処理部は、問い合わせ配列と、１次候補配列または検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、問い合わせ配列にマッチングする２次候補配列を抽出する２次候補配列抽出部と、２次候補配列に基づく検索結果を出力する出力部と、を含む、ことを特徴とする生物学的配列情報検索装置が提供される。
【００１７】
なお、この構成においては、中央処理部および並列処理部は、互いに別個の素子に設けられてもよく、あるいは互いに同一の素子に設けられてもよい。
【００１８】
この構成においても、まず、中央処理部において問い合わせ配列から並列処理用問い合わせ配列を生成し、次いで、並列処理部において検索対象データベースから並列処理用問い合わせ配列にマッチングする１次候補配列の抽出を行い、再び、中央処理部において１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する形で、中央処理部および並列処理部がそれぞれの役割を効率的に分担している。
【００１９】
このため、この構成によれば、並列処理部では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、この構成によれば、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００２０】
なお、上記の装置は本発明の一態様であり、本発明の装置は、以上の構成要素の任意の組合せであってもよい。また、本発明の生物学的配列情報検索方法、生物学的配列情報検索システム、生物学的配列情報検索プログラム、そのプログラムを格納する記録媒体なども、同様の構成を有し、同様の作用効果を奏する。
【発明の効果】
【００２１】
本発明によれば、中央処理部および並列処理部がそれぞれの役割を効率的に分担しているため、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００２３】
図１は、実施の形態に係る生物学的配列情報検索装置の構成を説明するための機能ブロック図である。生物学的配列情報検索装置１００は、中央処理部２００と、中央処理部２００とは別個の素子に設けられている並列処理部３００と、出力部１２２と、を備えている。また、生物学的配列情報検索装置１００は、生物学的配列情報に関する検索対象データベース１０２との間で通信可能な形で接続している。
【００２４】
生物学的配列情報検索装置１００では、以下のような手順で生物学的な配列情報の検索が行われる。まず、中央処理部２００において問い合わせ配列から並列処理用問い合わせ配列を生成する。次いで、並列処理部３００において検索対象データベース１０２から並列処理用問い合わせ配列にマッチングする１次候補配列の抽出を行う。そして、再び、中央処理部２００において１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する。このような形で、互いに別個の素子に設けられている中央処理部２００および並列処理部３００がそれぞれの役割を効率的に分担している。
【００２５】
そのため、並列処理部３００は、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出することができる。そして、中央処理部２００は、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、生物学的配列情報検索装置１００では、大量の生物学的な配列情報を格納している検索対象データベース１０２から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００２６】
生物学的配列情報検索装置１００は、生物学的配列情報検索装置１００に対する操作を受け付ける操作部１０６を備える。また、生物学的配列情報検索装置１００は、外部ネットワーク１１２を介して別のＰＣ（パーソナルコンピュータ）１０８およびサーバ１１０に接続している。生物学的配列情報検索装置１００は、これらの操作部１０６、スキャナ１０４、外部ネットワーク１１２などから生物学的情報についての問い合わせ配列を取得することができる。
【００２７】
また、生物学的配列情報検索装置１００には、上記の検索結果を画像として表示する画像表示装置１０４が接続している。また、生物学的配列情報検索装置１００には、上記の検索結果を印刷するプリンタ１１４が接続している。さらに、生物学的配列情報検索装置１００には、上記の検索結果を外部ネットワーク１１６を介して取得する別のＰＣ（パーソナルコンピュータ）１２０およびサーバ１１８が接続している。そして、出力部１２２は、これらの画像表示装置１０４、プリンタ１１４、外部ネットワーク１１６などに検索結果を出力することができる。
【００２８】
図２は、実施の形態に係る生物学的配列情報検索装置を構成する個別の素子を説明するための機能ブロック図である。なお、図２は、図１の機能面に重心をおいた機能ブロック図と異なり、ハードウェア面に重心をおいた機能ブロック図である。もっとも、図１および図２のいずれも、観点が異なるだけであり、同一の生物学的配列情報検索装置１００を説明するための機能ブロック図である点では同様である。
【００２９】
図２に示すようにハードウェア面に重心をおいて説明すると、生物学的配列情報検索装置１００は、中央演算部に相当するＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１０と、ＣＰＵ１０とは別個の素子であり並列処理部に相当するＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ／Ｍｕｌｔｉｐｌｅ Ｄａｔａ）２０と、ゲノム配列に関する配列情報を格納しているゲノムデータベース４０と、これらを互いに接続するバス３０と、を備える。
【００３０】
また、ＳＩＭＤ２０内部には、複数のＰＥ（Ｐｒｏｃｅｓｓｉｎｇ Ｅｌｅｍｅｎｔ）２２が設けられている。そして、これらの複数のＰＥ２２は、互いの有する配列情報を互いに参照可能に構成されている。
【００３１】
本明細書において、ＣＰＵは、コンピュータの中で各装置の制御やデータの計算または加工を行なう中枢部分を意味する。すなわち、ＣＰＵは、メモリに記憶されたプログラムを実行する装置であり、入力装置や記憶装置からデータを受け取り、演算または加工した上で、出力装置や記憶装置に出力する機能を有する。なお、通常のパソコンでは、ＣＰＵの機能を一つのチップに集積されたマイクロプロセッサが利用され、例えばＩｎｔｅｌ社のｘ８６シリーズまたは各社の互換プロセッサを好適に使用可能である。
【００３２】
本明細書において、ＳＩＭＤは、１つの命令で、複数のデータを同時に並列的に処理する並列型情報処理装置、もしくはそのための命令を意味する。一般に、ＳＩＭＤに含まれる各演算器は、簡単な論理演算を大量かつ高速に処理することを得意とするため、マルチメディアデータを取り扱うマイクロプロセッサや、ＤＳＰ、スーパーコンピュータなどにおいて実装されている。
【００３３】
すなわち、ＳＩＭＤでは、音声や画像などのマルチメディアデータに対する処理や、３次元グラフィックス用途などでに用いるとき、固定的なフォーマットのデータに対して、同じ種類の演算を繰り返し適用することが多い。そこで、ＳＩＭＤにおいて、１つの命令で多量のデータに対して同じ種類の演算を一斉に並列的に行うようにして、データ処理能力を高めるために用意されるのがＳＩＭＤ命令である。
【００３４】
ＳＩＭＤ命令を実装するためには、データを格納するための比較的大量のレジスタ（データ供給が滞らないようにするため）と、複数のＰＥ（演算器）２２とを用いる必要があるため、ＳＩＭＤ２０内部には、多くのＰＥ（演算器）２２と、これらのＰＥ２２にそれぞれ対応する複数のレジスタ（不図示）とが設けられている。
【００３５】
なお、最近の高性能なＣＰＵの多くでは、ＣＰＵ全体の演算能力を飛躍的に増大させるため、このようなデータを格納するための比較的大量のレジスタ（データ供給が滞らないようにするため）と、複数のＰＥ（演算器）とをＣＰＵの内部に備えることもある。しかし、本実施形態では、ＣＰＵおよびＳＩＭＤの役割分担を明確にし、互いに異なる情報処理にＣＰＵによる配列情報処理およびＳＩＭＤによる並列処理の効率を向上させるため、ＳＩＭＤ２０は、ＣＰＵ１０とは別個の素子上に設けられている。
【００３６】
すなわち、生物学的配列情報検索装置１００は、ＣＰＵ１０と、並列処理回路であるＳＩＭＤ２０と、ゲノムデータが格納されたメモリであるゲノムデータベース４０とが、バス３０により互いに接続されて構成された装置である。また、生物学的配列情報検索装置１００は、ゲノムデータベース４０に格納されているゲノムデータ中から問い合わせ配列を検索して、その検索結果をネットワーク回線などによる通知などの形で出力することを目的とする装置でもある。
【００３７】
生物学的配列情報検索装置１００の特徴は、検索処理において、ＣＰＵ１０と、並列処理回路であるＳＩＭＤとに適切な機能分担を行わせている点である。
【００３８】
つまり、ＣＰＵ１０は、汎用的なプログラムコードにより動作し、そのプログラムコードにより複雑な処理も可能であるが、処理速度の面で改善の余地がある。一方、ＳＩＭＤ２０をはじめとする並列処理回路は、制限があるプログラムコードにより動作し、高速な処理が可能であるが、条件分岐等の制御処理の面で改善の余地がある（条件分岐等の制御処理をできないことはないが、実質的に困難である）。
【００３９】
これに対して、生物学的配列情報検索装置１００は、問い合わせ配列にマッチングする配列を検索するために、まず、ＳＩＭＤ２０で高速にスクリーニングを行い、そのスクリーニング結果をＣＰＵ１０で念入りに条件確認を行い、条件にあったものを最終結果とする方式をとっている。このため、大量の生物学的な配列情報を格納しているゲノムデータベース４０から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００４０】
図３は、実施の形態に係る生物学的配列情報検索装置を構成する個別の素子の機能の概要を説明するための概念図である。生物学的配列情報検索装置１００では、以下のような手順で生物学的な配列情報の検索が行われる。
【００４１】
まず、生物学的情報についての問い合わせ配列がＣＰＵ１０に入力される。続いて、ＣＰＵ１０は、問い合わせ配列からＳＩＭＤ２０での処理に適したＳＩＭＤ用問い合わせ配列を生成する。そして、ＳＩＭＤ用問い合わせ配列は、ＣＰＵ１０から出力されてＳＩＭＤ２０に入力される。
【００４２】
ＳＩＭＤ２０は、ゲノムデータベース４０からゲノムデータを取得して、ＳＩＭＤ用問い合わせ配列に対する１ｓｔスクリーニングを並列処理により行って、ＳＩＭＤ用問い合わせ配列にマッチングする１次候補配列を抽出する。そして、１次候補配列は、ＳＩＭＤ２０から出力されてＣＰＵ１０に入力される。
【００４３】
そして、ＣＰＵ１０は、ＳＩＭＤ２０から１次候補配列を取得して、問い合わせ配列に対する２ｎｄスクリーニングを行って、問い合わせ配列にマッチングする２次候補配列を抽出する。こうして得られた２次候補配列に基づく検索結果は、ＣＰＵ１０から出力される。このような形で、互いに別個の素子に設けられているＣＰＵ１０およびＳＩＭＤ２０がそれぞれの役割を効率的に分担している。
【００４４】
そのため、ＳＩＭＤ２０は、ＳＩＭＤ用問い合わせ配列に対応する１次候補配列を高速に抽出することができる。そして、ＣＰＵ１０は、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、生物学的配列情報検索装置１００では、大量の生物学的な配列情報を格納しているゲノムデータベース４０から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００４５】
図４は、実施の形態における中央処理部および並列処理部の内部構成を説明するため機能ブロック図である。なお、この図４は、上記の図１の中央処理部２００および並列処理部３００の内部構成を示している。
【００４６】
より詳細に説明すると、中央処理部２００では、生物学的情報についての問い合わせ配列は、問い合わせ配列取得部２０２により取得され、問い合わせ配列記憶部２０８に格納される。次いで、並列処理用問い合わせ配列生成部２０４が、問い合わせ配列記憶部２０８から問い合わせ配列を読み出し、問い合わせ配列に基づいて並列処理用問い合わせ配列を生成し、並列処理用問い合わせ配列記憶部２０６に格納する。
【００４７】
続いて、並列処理部３００では、１次候補配列抽出部３０２が、並列処理用問い合わせ配列記憶部２０６から並列処理用問い合わせ配列を読み出し、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを並列処理により行って、並列処理用問い合わせ配列にマッチングする１次候補配列を抽出し、１次候補配列記憶部３０４に格納する。
【００４８】
次いで、中央処理部２００では、２次候補配列抽出部２１０が、１次候補配列記憶部３０４から１次候補配列を読み出し、さらに、問い合わせ配列記憶部２０８から問い合わせ配列を読み出す。そして、２次候補配列抽出部２１０は、問い合わせ配列と１次候補配列との間で配列マッチングを行い、問い合わせ配列にマッチングする２次候補配列を抽出して、２次候補配列記憶部２１２に格納する。その後、出力部１２２は、２次候補配列記憶部２１２から２次候補配列を読み出し、２次候補配列に基づく検索結果を出力する。
【００４９】
一部の説明は繰り返しになるが、生物学的配列情報検索装置１００では、上記のような構成を用いて生物学的な配列情報の検索が行われる。すなわち、中央処理部２００の並列処理用問い合わせ配列生成部により、問い合わせ配列から並列処理用問い合わせ配列が生成される。次いで、並列処理部３００の１次候補配列抽出部３０２により、検索対象データベース１０２から並列処理用問い合わせ配列にマッチングする１次候補配列が抽出される。そして、中央処理部２００の２次候補配列抽出部２１０により、１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する。
【００５０】
このような形で、互いに別個の素子に設けられている中央処理部２００および並列処理部３００がそれぞれの役割を効率的に分担している。そのため、並列処理部３００は、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出することができる。そして、中央処理部２００は、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、生物学的配列情報検索装置１００では、大量の生物学的な配列情報を格納している検索対象データベース１０２から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００５１】
図５は、実施の形態に係る生物学的配列情報検索装置の動作を説明するためのフローチャートである。生物学的配列情報検索装置１００の一連の動作が開始すると、まず、中央処理部２００の問い合わせ配列取得部２０２は、外部から問い合わせ配列を取得する（Ｓ１０２）。次いで、中央処理部２００の並列処理用問い合わせ配列生成部２０４は、問い合わせ配列から並列処理用問い合わせ配列を生成する（Ｓ１０４）。
【００５２】
そして、並列処理部３００の１次候補配列抽出部３０２は、並列処理用問い合わせ配列と検索対象データベースとをマッチングさせて、問い合わせ配列に潜在的にマッチングする可能性を有する１次候補配列を抽出する（Ｓ１０６）。次に、中央処理部２００の２次候補配列抽出部２１０は、１次候補配列と問い合わせ配列とをマッチングさせて、問い合わせ配列にマッチングする２次候補配列を抽出し（Ｓ１０８）、一連の動作を終了する。
【００５３】
その後、中央処理部２００の出力部１２２は、２次配列候補に基づく検索結果を出力して（Ｓ１１０）、生物学的配列情報検索装置１００の一連の動作が終了する。
【００５４】
図６は、実施の形態における並列処理用問い合わせ配列生成部の内部構成を説明するため機能ブロック図である。並列処理用問い合わせ配列生成部２０４では、コドン変換部４１４は、問い合わせ配列記憶部２０８から問い合わせ配列を読み出して、問い合わせ配列の形式をアミノ酸配列から塩基配列に変換する。次に、ビット変換部４１６は、問い合わせ配列の形式をテキスト配列からビット配列に変換して得られる問い合わせビット列を、問い合わせビット列記憶部４１８に格納する。
【００５５】
続いて、部分配列生成部４０２は、問い合わせビット列を構成する複数の所定長の部分配列を生成し、部分配列記憶部４０４に格納する。なお、これらの部分配列は、互いに一部のビット列が重複していてもよい。そして、配列特異性指標計算部４０６は、問い合わせビット列に含まれる複数の所定長の部分配列について、その部分配列の配列特異性に基づく配列特異性指標を計算し、配列特異性指標記憶部４０８に格納する。
【００５６】
次いで、部分配列抽出部４１０は、配列特異性指標記憶部４０８から配列特異性指標を読み出し、部分配列記憶部４０４から部分配列を読み出し、さらに、あらかじめ配列特異性の閾値が格納されている閾値記憶部４１２から閾値を読み出して、複数の部分配列の中から、配列特異性指標が所定の閾値以上である部分配列を抽出する。その後、部分配列抽出部４１０は、抽出した部分配列に基づいた並列処理用問い合わせ配列を並列処理用問い合わせ配列記憶部２０６に格納する。
【００５７】
図７は、実施の形態における並列処理用問い合わせ配列生成部の機能の概要を説明するための概念図である。図７（ａ）および（ｂ）に示すように、コドン変換部４１４は、問い合わせ配列記憶部２０８から問い合わせ配列を読み出すと、問い合わせ配列の形式をアミノ酸配列から塩基配列に変換する。このとき、アミノ酸配列および塩基配列が一対多で対応するため、１つのアミノ酸配列から、複数の塩基配列（塩基配列１、塩基配列２、塩基配列３・・・）が生じる。
【００５８】
次いで、図７（ｂ）および図７（ｃ）に示すように、ビット変換部４１６は、コドン変換部４１４から塩基配列の形式の問い合わせ配列を受け取ると、これらの複数の問い合わせ配列の形式を塩基配列からビット列に変換して、複数のビット列（ビット列１、ビット列２、ビット列３・・・）を得る。
【００５９】
その後、図７（ｃ）および図７（ｄ）に示すように、ビット変換部４１６は、上述のようにアミノ酸および塩基配列が一対多で対応することにより生じる、問い合わせ配列であるアミノ酸配列を構成する複数の塩基配列における各塩基のバリエーションを一本化して、１つの問い合わせビット列を生成する。このとき、塩基（配列要素）単位でバリエーションを包含するようにＯＲ計算により問い合わせビット列が生成される。
【００６０】
すなわち、並列処理用問い合わせ配列生成部２０４では、１つのアミノ酸配列形式の問い合わせ配列に対応する１つの問い合わせビット列を生成する。なお、このようにして複数のビット列を一本化されたビット列を、本明細書では、最小公倍ビット列と呼ぶ。もっとも、この最小公倍ビット列の概念は、厳密に数学的な意味での最小公倍数の概念に縛られるものではない。
【００６１】
より詳しくは、問い合わせ配列であるアミノ酸配列を構成する塩基配列の各塩基（各配列要素）のバリエーションを、問い合わせビット列（最小公倍ビット列）の対応する各配列要素（４ビットからなる各ビット列単位）が包含するように、問い合わせビット列が生成される。なお、本明細書では、ビット列単位とは、例えば、１アミノ酸残基、１ヌクレオチド残基に対応する、所定長のビット列を意味する。
【００６２】
この実施形態では、Ａ、Ｔ、Ｇ、Ｃの４種類の塩基は、４ビットのビット列で表現可能であるため、ビット列単位は４ビット長であるものとする。もっとも、Ａ、Ｔ、Ｇ、Ｃの４種類の塩基は、厳密に数学的には２ビット以上であれば充分に表現可能である。なお、このような問い合わせビット列の具体例を後述により説明する。
【００６３】
そして、図７（ｄ）および図７（ｅ）に示すように、部分配列生成部４０２、配列特異性指標計算部４０６、部分配列抽出部４１０、閾値記憶部４１２は、互いに協働して、こうして得られた最小公倍ビット列を構成する複数の部分配列の中から、配列特異性指標が閾値以上である部分配列（特異性に優れる部分配列であり、本明細書では、特異ビット列と呼ぶ）を、並列処理用問い合わせビット列として抽出する。
【００６４】
上述のように、並列処理用問い合わせ配列生成部２０４では、問い合わせ配列はアミノ酸配列である場合、コドン変換部４１４、ビット変換部４１６、部分配列生成部４０２、配列特異性指標計算部４０６、部分配列抽出部４１０および閾値記憶部４１２が、互いに協働して、並列処理用問い合わせ配列としての特異ビット列を生成する。
【００６５】
すなわち、これらの働きにより、アミノ酸配列に対応する塩基配列を表しておりその塩基配列の各塩基を所定長の単位ビット列で構成した並列処理用問い合わせビット列が生成される。その結果、並列処理用問い合わせビット列は、問い合わせ配列の各アミノ酸残基を形成する各塩基のバリエーションを、並列処理用問い合わせビット列としての特異ビット列の単位ビット列が包含するように生成されることになる。
【００６６】
以下、並列処理用問い合わせ配列生成部２０４の処理を、より具体的に説明する。
並列処理用問い合わせ配列生成部２０４では、ＳＩＭＤなどの並列処理部３００の１ｓｔスクリーニングのために、生物学的特徴を考慮した前処理を問い合わせ配列に対して施している。まず、並列処理部３００にとって処理しやすいように問い合わせ配列を既知の方法により数値化している。
【００６７】
すなわち、問い合わせ配列が核酸（小文字表記）の場合、ビット変換部４１６により２進数表現に変換する。なお、代表的な核酸のコード表を下記の表１に示す。
【００６８】
【表１】
【００６９】
ａ → ０００１
ｔ → ００１０
ｃ → ０１００
ｇ → １０００
【００７０】
この場合、例えば、ｓは、ｃまたはｇを意味するが、数値化すると１１００となる。
ｓ＝ｃ ｏｒ ｇ＝０１００ ｏｒ １０００＝１１００
【００７１】
一方、問い合わせ配列がアミノ酸（大文字表記）の場合、コドン変換部４１４によりコドン表を用いてアミノ酸を核酸に変換した場合、通常は核酸３つで１つのアミノ酸を構成するが、１つのアミノ酸に対して複数の組み合わせがあるケースも存在する。なお、代表的なアミノ酸のコード表を下記の表２に示す。
【００７２】
【表２】
【００７３】
また、このときの注意事項として、アミノ酸のコドン表は、生物種によって多少異なる場合があり、また、同じ生物種でも、核とミトコンドリアとでは、異なることが多い。すなわち、コドン表は１種類ではなく、いくつもの種類が存在する。
【００７４】
ヒトの核のコドン表による場合
Ass =FFLLSSSSYY**CC*WLLLLPPPPHHQQRRRRIIIMTTTTNNKKSSRRVVVVAAAADDEEGGGG
Starts=---M---------------M---------------M----------------------------
Base1 =TTTTTTTTTTTTTTTTCCCCCCCCCCCCCCCCAAAAAAAAAAAAAAAAGGGGGGGGGGGGGGGG
Base2 =TTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGG
Base3 =TCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAG
なお、上記Assは、配列番号：１、Base1は、配列番号：２、Base2は、配列番号：３、Base3は、配列番号４に相当する。
【００７５】
ヒトのミトコンドリアのコドン表による場合
Ass =FFLLSSSSYY**CC*WLLLLPPPPHHQQRRRRIIIMTTTTNNKKSSRRVVVVAAAADDEEGGGG
Starts=---M---------------M------------MMMM---------------M------------
Base1 =TTTTTTTTTTTTTTTTCCCCCCCCCCCCCCCCAAAAAAAAAAAAAAAAGGGGGGGGGGGGGGGG
Base2 =TTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGG
Base3 =TCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAG
なお、上記Assは、配列番号：１、Base1は、配列番号：２、Base2は、配列番号：３、Base3は、配列番号４に相当する。
【００７６】
次に、再びアミノ酸配列を塩基配列に変換する処理についての説明に戻る。
たとえば、アミノ酸のＭは、
Ｍ → ａｔｇ
の唯一の組み合わせのみである。
【００７７】
一方、アミノ酸のＢは４通りあり、
Ｂ → ａａｃ、ｇａｔ、ａａｔ、ｇａｃ
である。
【００７８】
これを数値化すると、下記のようになる。
Ｍ → ａｔｇ → ０００１ ００１０ １０００
Ｂ → ０００１ ０００１ ０１００、１０００ ０００１ ００１０
０００１ ０００１ ００１０、１０００ ０００１ ０１００
【００７９】
なお、問い合わせ配列は、核酸、アミノ酸を要素とすることができる。
また、ワイルドカード（核酸（．）、アミノ酸（＊））も使用可能である。
さらに、ｏｒ記述（演算子 ｜ ）も使用可能である。
【００８０】
例としては、以下のような配列を問い合わせ配列として使用可能である。
ａｔｃｇＡＢＧａｔ 核酸、アミノ酸が混在していてもよい。
ａｔ．ｇ＊ＢＧ．ｔ ワイルドカードが混在していてもよい。
ａｔ｛ｃｇ｜ａｔ｝ｇｇ ｏｒ表現 ａｔｃｇｇｇまたはａｔａｔｇｇを意味する。
【００８１】
このとき、問い合わせ配列を、数値化するに際して、複数の数値列ではなく、単一の数値列にする。すなわち、すべての問い合わせ配列が漏れない形にしつつ、複数の数値列を一本化するように処理する。
【００８２】
例えば、Ｂは、
Ｂ → ０００１ ０００１ ０１００、１０００ ０００１ ００１０
０００１ ０００１ ００１０、１０００ ０００１ ０１００
であるが、１ｓｔスクリーニングのための前処理にあたり、
Ｂ → １００１ ０００１ ０１１０
に数値化する（ＯＲ演算を行っている）。これは、上述で説明した並列処理用問い合わせ配列の一本化のため、問い合わせ配列であるアミノ酸配列を構成する塩基配列の各塩基のバリエーションを、問い合わせビット列の対応する各配列要素が包含するように、問い合わせビット列を生成する処理である。
【００８３】
さらに、ＳＩＭＤをはじめとする並列処理部３００内部の各々の演算器５０４で扱える並列処理用問い合わせ配列の配列数には、処理能力の限界がある。その限界値を超えるケースでは、下記の処理を行う。
【００８４】
たとえば、
atcga****tacgactagcat***atcga（配列番号：５）
という並列処理用問い合わせ配列で、をはじめとする並列処理部３００内部の各々の演算器５０４で扱える配列数が１０以下だとすると、
atcga****tacgactagcat***atcga（配列番号：５）
|--------|
|--------|
|--------|
|--------|
という具合に、並列処理用問い合わせ配列の一部分（１０塩基）をＳＩＭＤをはじめとする並列処理部３００用の問い合わせ配列として、並列処理部３００で１ｓｔスクリーニングを行うことになる。
【００８５】
ここで、効率のよいスクリーニングを行うには、ワイルドカードを含まない、以下の３通りの抽出が最適である。
atcga****tacgactagcat***atcga（配列番号：５）
|--------|
|--------|
|--------|
【００８６】
なお、例としてワイルドカードを用いたケースを挙げたが、この場合には、並列処理用問い合わせ配列をＯＲ計算した数値例を元に計算によって、最適抽出箇所を判定可能である。具体的には、下記のｓｃｏｒｅ値が最大となる箇所を検索する。
【００８７】
Ｓｃｏｒｅ＝Πｆ（ｑ［ｉ］）
ｆ（ａ）＝単位ビット列を構成する４ｂｉｔ中１の数が、
１つの場合 → １
２つの場合 → ０．５
３つの場合 → ０．２５
４つの場合 → ０．１２５
【００８８】
図８は、実施の形態における並列処理用問い合わせ配列生成部の動作を説明するためのフローチャートである。まず、コドン変換部４１４が、問い合わせ配列記憶部２０８から問い合わせ配列を取得すると、問い合わせ配列の形式をアミノ酸配列から塩基配列に変換する（Ｓ２０２）。次いで、ビット変換部４１６が、問い合わせ配列の形式を塩基配列からビット配列に変換する（Ｓ２０４）。
【００８９】
さらに、同様にビット変換部４１６が、複数のビット配列の形式からなる問い合わせ配列をＯＲ計算により１本のビット配列にまとめて、問い合わせビット列を生成する（Ｓ２０６）。そして、部分配列生成部４０２が、問い合わせビット列から複数の部分配列を生成する。続いて、配列特異性指標計算部４０６が、これらの複数の部分配列について、特異性指標を計算する（Ｓ２０８）。その後、部分配列抽出部４１０が、こうして得られた配列特異性指標が所定の閾値以上である特異性の優れる部分配列を、並列処理用問い合わせ配列として抽出し（Ｓ２１０）、一連の動作を終了する。
【００９０】
この並列処理用問い合わせ配列生成部２０４の構成によれば、並列処理用問い合わせ配列は、問い合わせ配列を構成する各配列要素のバリエーションを対応する各配列要素において包含するため、問い合わせ配列の各配列要素のバリエーションを一本化して検索対象データベース１０２に投げかけることにより、１次候補配列のスクリーニングを行うことができる。そのため、並列処理部３００において、問い合わせ配列の各配列要素のバリエーションを漏れなく検索しながら、１次候補配列の抽出を高速化することができる。
【００９１】
上記の記載と一部重複するが、別の形で表現すると、この並列処理用問い合わせ配列生成部２０４の構成によれば、並列処理用問い合わせビット列は、問い合わせ配列のアミノ酸配列に対応する塩基配列を表しており、塩基配列の各塩基に対応する所定長の単位ビット列で構成されているため、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを一本化することができる。そして、並列処理部において、このように一本化された並列処理用問い合わせビット列を検索対象データベース１０２に投げかけることにより、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを漏れなく検索しながら、１次候補配列の抽出を高速化することができる。
【００９２】
また、この並列処理用問い合わせ配列生成部２０４の構成によれば、コドン変換部４１４により、問い合わせ配列を、テキスト配列からビット配列に変換した後に並列処理部３００に送ることができるため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００において、１次候補配列の抽出を高速化することができる。
【００９３】
また、この並列処理用問い合わせ配列生成部２０４の構成によれば、問い合わせ配列をアミノ酸配列から塩基配列に変換することができるため、問い合わせ配列としてアミノ酸配列を取得した場合にも、ゲノムデータベース１０２に対して１次候補配列のスクリーニングを行うことができる。
【００９４】
さらに、この並列処理用問い合わせ配列生成部２０４の構成によれば、問い合わせ配列に含まれる複数の所定長の部分配列の中から、配列特異性指標が所定の閾値以上である特異性に優れる部分配列を並列処理用問い合わせ配列として抽出することができる。そのため、並列処理部３００において行う１次候補配列の抽出の際に、最終的に目的の問い合わせ配列とマッチングする可能性が低い特異性に劣る配列を抽出することなく、最終的に目的の問い合わせ配列とマッチングする可能性が高い特異性に優れる１次候補配列を抽出することができる。
【００９５】
よって、この並列処理用問い合わせ配列生成部２０４の構成によれば、抽出される１次候補配列の数を絞り込むことができ、かつ、抽出される１次候補配列が最終的に目的の問い合わせ配列とマッチングする可能性を高めることができる。よって、１次候補配列の抽出が効率化されるので、並列処理部３００の処理速度が向上する。その結果、並列処理部において行う１次候補配列の抽出を高速化しつつ、精度を向上することができる。
【００９６】
なお、上述の処理では、問い合わせ配列がアミノ酸配列の場合に、アミノ酸配列が塩基配列に変換され、さらに、上述のような問い合わせビット列に変換された。より簡単には、各アミノ酸と、それに対応するビット列とのテーブルが予め作成され、記憶されていてもよい。このビット列は、上述の原理に従って該当するアミノ酸を構成する複数の塩基列のバリエーションを包含するように設定される。このようなテーブルが参照されて、アミノ酸配列が問い合わせビット列に変換されてもよい。
【００９７】
図９は、実施の形態における１次候補配列抽出部および１次候補配列記憶部の内部構成を説明するための機能ブロック図である。１次候補配列抽出部３０２には、同一の素子に設けられている複数の演算器５０４が設けられている。
【００９８】
まず、１次候補配列抽出部３０２では、検索対象データ取得部５１２が、検索対象データベース１０２中の生物学的配列情報を取得する。次いで、所定長区切部５１０が、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切り、区切って得られた所定長検索対象データを所定長検索対象データ記憶部５０８に格納する。
【００９９】
その後、データ割振部５０２が、並列処理用問い合わせ配列記憶部２０６から並列処理用問い合わせ配列を取得し、複数の演算器５０４のそれぞれに、同一の並列処理用問い合わせ配列を割り振る。一方では、データ割振部５０６が、所定長検索対象データ記憶部５０８から区切って得られた所定長検索対象データを読み出し、複数の演算器５０４のそれぞれに割り振ることにより、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを並列処理的に行う。
【０１００】
このとき、一次候補配列抽出部３０２は、同一の素子に設けられている複数の演算器５０４を含み、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切って、複数の演算器５０４のそれぞれに割り振ることにより、並列処理用問い合わせ配列と検索対象データベースとの間で、配列マッチングを並列処理的に行って１次候補配列を抽出するように構成されている。
【０１０１】
一次候補配列抽出部３０２の複数の演算器５０４により、並列処理的に配列マッチングされて抽出された複数の１次候補配列は、それぞれ１次候補配列記憶部３０４内の対応する記憶部５１４（記憶部５１４ａ、記憶部５１４ｂ、記憶部５１４ｃ・・・）に格納される。また、複数の演算器５０４のうち、互いに隣接する前記所定長の配列情報を割り振られた演算器５０４同士は、所定長の配列情報を互いに参照可能に構成されている。
【０１０２】
図１０は、実施の形態における１次候補配列抽出部および１次候補配列記憶部の機能の概要を説明するための概念図である。まず、図１０（ａ）および図１０（ｂ）に示すように、所定長区切部５１０が、検索対象データベース１０２から取得されたゲノムデータの一部（区分１、区分２、区分３・・・）を複数の所定長のゲノムデータに区切る。そして、このようにして所定長区切部５１０により区切られて得られた所定長ゲノムデータを、データ割振部５０６が、複数の演算器５０４（ＰＥ０、ＰＥ１、ＰＥ２、・・・・ＰＥ３５１）のそれぞれに割り振る。すなわち、データ割振部５０６は、ゲノムデータの一部を３５２個に区切って、３５２個のＰＥに割り振ることになる。
【０１０３】
一方では、図１０（ｂ）および図１０（ｃ）に示すように、データ割振部５０２が、並列処理用問い合わせ配列記憶部２０６から取得された並列処理用問い合わせ配列を、複数の演算器５０４のそれぞれに割り振る。すなわち、データ割振部５０２は、互いに同一の並列処理用問い合わせ配列を３５２個のＰＥに割り振ることになる。
【０１０４】
その後、複数の演算器５０４のそれぞれにおいて、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを並列処理的に行う。なお、複数の演算器５０４（３５２個のＰＥ）は、並列処理による配列マッチングを行うが、その際、並列処理用問い合わせ配列をＰＥ１つ分の領域内で１塩基相当分の幅ずつずらしながら、並列処理による配列マッチングを行う。
【０１０５】
以下、ＳＩＭＤなどからなる並列処理部３００における１ｓｔスクリーニングの動作について、より詳細に説明する。
【０１０６】
ＳＩＭＤなどからなる並列処理部３００における１ｓｔスクリーニングは、１次候補配列を抽出することを目的として、以下のような方法により行うことができる。つまり、ＳＩＭＤなどからなる並列処理部３００では、以下の例に示すような処理（演算）を行う。
【０１０７】
ＰＥをはじめとする演算器５０４とゲノムデータとの処理方法は、下記の様にして行った。なお、ＰＥとは、ＳＩＭＤ内部の小さなＣＰＵを指す。本発明者が、実験に用いたＳＩＭＤチップは、１ＳＩＭＤあたり３５２ＰＥ内蔵されているものを使った。
【０１０８】
| PE 0 || PE 1 || PE 2 |--------------------------------------|PE 351|
atcgatcgatacgacgtacgtacgatgc---------------------------------acgtacgta
atcgatcg
atcgatcg
atcgatcg
atcgatcg
atcgatcg
atcgatcg
atcgatcg
atcgatcg
なお、上記の長い方の配列の左側は、配列番号：６に相当する。
【０１０９】
上記の例では、並列処理用問い合わせ配列ａｔｃｇａｔｃｇを検索するために、ＰＥ２が担当する領域に対して、一致するかどうかをシフトしながら検出している。
【０１１０】
なお、並列処理用問い合わせ配列と、複数の演算器５０４に割り振られたゲノムデータとが一致するかどうかの検出の際には、例えば、下記のような論理演算を行う。
【０１１１】
例：
ゲノムデータ： １０００ ０００１ ０１００
問い合わせ配列： Ｂ １００１ ０００１ ０１１０
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
演算結果： １０００ ０００１ ０１００
この演算結果は、どの単位ビット列にも００００がないため「ヒット」である。
【０１１２】
ゲノムデータ： ００１０ ０００１ １０００
問い合わせ配列： Ｂ １００１ ０００１ ０１１０
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
演算結果： ００００ ０００１ ００００
この演算結果は、００００があるため、「ミス」である。
【０１１３】
本実施形態では、ＳＩＭＤなどからなる並列処理部３００において、このような条件分岐のない単純なスクリーニング処理を行い、その結果を元に並列処理用問い合わせ配列と合致するかどうかを確認する。そして、合致した場合、その合致したゲノム配列の一部の領域を、１次候補配列の検索結果とする。
【０１１４】
すなわち、これまで例として挙げた内容をまとめると、並列処理用問い合わせ配列と、複数の演算器５０４に割り振られたゲノムデータとが一致するかどうかの検出の際には、以下の手順を繰り返すことになる。
【０１１５】
処理の流れ
１．データ割振部５０６が、ゲノムデータの先頭から特定のデータ長分をＰＥをはじめとする演算器５０４に流し込む。データ長は、１つのＰＥをはじめとする演算器５０４が扱えるデータ数×ＰＥをはじめとする演算器５０４の数である。
【０１１６】
２．各ＰＥをはじめとする演算器５０４は、そのＰＥをはじめとする演算器５０４が担当する領域に対して先頭から順に並列処理用問い合わせ配列と合致するかをシフトしながら調べる。
【０１１７】
３．並列処理部３００は、並列処理用問い合わせ配列と、複数の演算器５０４に割り振られたゲノムデータとの合致箇所を、１ｓｔスクリーニングの結果（１次候補配列）として、ＣＰＵをはじめとする中央処理部２００に通知する。
【０１１８】
４．１．に戻り、後続のゲノムデータをＰＥに流し込み、処理を続ける。
【０１１９】
図１１は、実施の形態における１次候補配列抽出部および１次候補配列記憶部の動作を説明するためのフローチャートである。まず、所定長区切り部５１０が、検索対象データベース１０２から検索対象データ取得部５１２を介して取得した検索対象データベースの一部（１区分目、２区分目、３区分目・・・）をそれぞれ所定長ごとに区切る。そして、データ割振部５０６が、所定長に区切られたゲノムデータを演算器５０４（演算器１、演算器２、演算器３・・・）に割り振る（Ｓ３０２）。
【０１２０】
一方で、データ割振部５０２が、並列処理用問い合わせ配列記憶部２０６から取得した同一の並列処理用問い合わせ配列を、複数の演算器５０４（演算器１、演算器２、演算器３・・・）に割り振る（Ｓ３０４）。そして、並列処理用問い合わせ配列を１塩基分ずつずらしながら、それぞれの演算器５０４（演算器１、演算器２、演算器３・・・）で配列マッチングを並列的に行う（Ｓ３０６）。
【０１２１】
そして、それぞれの演算器５０４（演算器１、演算器２、演算器３・・・）の配列マッチングの結果得られる１次候補配列は、それぞれ１次候補配列候補記憶部３０４内の記憶部５１４（記憶部１、記憶部２、記憶部３・・・・）に格納される。そして、中央処理部２００からの求めに応じて、これらの配列マッチングの結果である１次候補配列は、中央処理部２００に送られる（Ｓ３０８）。
【０１２２】
その後、中央処理部２００において、ゲノムデータの全区分の配列マッチングが完了したか否かが判定される（Ｓ３１０）。未だ完了していないと判定された場合には、前回にゲノムデータのｎ区分目を割り振ったのであれば、今回は、データ割振部５０６は、ｎ＋１区分目を新たにそれぞれの演算器５０４（演算器１、演算器２、演算器３・・・）に割り振って、再度、上記のサイクルを繰り返す（Ｓ３１２）。一方、既に完了したと判定された場合には、１次候補配列抽出部３０２および１次候補配列記憶部３０４は、一連の動作を終了する。
【０１２３】
本実施形態における１次候補配列抽出部３０２および１次候補配列記憶部３０４の構成によれば、並列処理用問い合わせビット列と、検索対象ビット列とを複数の演算器５０４（演算器１、演算器２、演算器３・・・）により並列処理的に論理演算するため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００において、１次候補配列の抽出を高速化することができる。
【０１２４】
また、本実施形態における１次候補配列抽出部３０２および１次候補配列記憶部３０４の構成によれば、並列処理部３００において、複数の演算器５０４を用いて、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切って、複数の演算器５０４のそれぞれに割り振るため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００の複数の演算器５０４において、それぞれ割り振られた配列情報から１次候補配列を高速に抽出することができる。
【０１２５】
また、本実施形態における１次候補配列抽出部３０２および１次候補配列記憶部３０４の構成によれば、互いに隣接する所定長の配列情報を割り振られた演算器５０４同士は、所定長の配列情報を互いに参照可能であるため、これらの複数の演算器５０４は、複数の演算器５０４にまたがって割り振られている配列情報（割り振られた配列情報の区切り目にまたがって、存在する配列情報）からも、１次候補配列を抽出することができる。そのため、複数の演算器５０４に対して、区切り目にまたがって存在する配列情報を重複して割り振る必要が無いので、複数の演算器５０４に割り振られた配列情報の区切り目にまたがる配列情報からも、１次候補配列を高速かつ精度よく抽出することができる。
【０１２６】
図１２は、実施の形態における２次候補配列抽出部の内部構成を説明するため機能ブロック図である。２次候補配列抽出部２１０は、１次候補配列取得部６０２と、完全一致配列抽出部６０４とを備える。１次候補配列取得部６０２は、１次候補配列記憶部３０４に含まれる複数の記憶部５１４（記憶部１、記憶部２、記憶部３・・・）から、それぞれに格納されている１次候補配列を取得し、完全一致配列抽出部６０４に受け渡す。
【０１２７】
次いで、完全一致配列抽出部６０４は、問い合わせ配列記憶部２０８から、当初入力された問い合わせ配列を取得し、１次候補配列取得部６０２から受け取った１次候補配列と配列マッチングを行う。このとき、完全一致配列抽出部６０４は、複数の１次候補配列から、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するように構成されている。
【０１２８】
このような２次候補配列抽出が必要な理由を説明する。１次候補配列では、並列処理の特徴を活かして高速で配列マッチングを行える代わりに、下記に例示されるミスヒットも発生する可能性があり、問い合わせ配列以外の配列も含んでしまっている。
【０１２９】
１次候補配列のスクリーニングでミスヒットを出力する例を示す。
アミノ酸配列のｓは、塩基配列になおすと、ｔｃｎまたはａｇｙであり、具体的には、
ｔｃａ
ｔｃｔ
ｔｃｃ
ｔｃｇ
ａｇｃ
ａｇｔ
が該当する（ｎは、ａまたはｔまたはｃまたはｇであり、ｙは、ｃまたはｔ）。
【０１３０】
これを一本化して数値化すると、００１１ １１００ １１１１となる。
そのため、ミスヒットのケースとしては、
０００１ ０１００ ０００１ → ａｃａ
００１０ １０００ ０００１ → ｔｇａ
などがある。
【０１３１】
このように１次候補配列の抽出では、一部にミスヒットが含まれてしまう可能性があるので、２次候補配列の抽出が好適に行われて、これにより最終的に高精度のマッチングが可能になる。
【０１３２】
図１３は、実施の形態における２次候補配列抽出部の動作を説明するためのフローチャートである。まず、１次候補配列取得部６０２が、１次候補配列記憶部３０４に含まれる複数の記憶部５１４（記憶部１、記憶部２、記憶部３・・・）から、それぞれに格納されている１次候補配列を取得する（Ｓ４０２）。
【０１３３】
次いで、完全一致配列抽出部６０４は、問い合わせ配列記憶部２０８から、当初入力された問い合わせ配列を取得する（Ｓ４０４）。そして、完全一致配列抽出部６０４は、複数の１次候補配列から、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出し（Ｓ４０６）、一連の動作を終了する。
【０１３４】
本実施形態に係る２次候補配列抽出部２１０の構成によれば、２次候補配列抽出部２１０は、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するため、上述のように、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを一本化して並列処理用問い合わせ配列を生成した場合に、並列処理用問い合わせ配列に紛れ込むノイズ配列由来の１次候補配列を効率的に除去して２次候補配列を抽出することができる。
【０１３５】
以下、本実施形態に係る生物学的配列情報検索装置の作用効果について、説明する。
【０１３６】
本実施形態に係る生物学的配列情報検索装置１００の構成においては、まず、中央処理部２００において問い合わせ配列から並列処理用問い合わせ配列を生成し、次いで、並列処理部３００において検索対象データベース１０２から並列処理用問い合わせ配列にマッチングする１次候補配列の抽出を行い、再び、中央処理部２００において１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する形で、中央処理部２００および並列処理部３００がそれぞれの役割を効率的に分担している。
【０１３７】
このため、この構成によれば、並列処理部３００では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部２００では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、この構成によれば、大量の生物学的な配列情報を格納している検索対象データベース１０２から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【０１３８】
本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理用問い合わせ配列生成部２０４は、問い合わせ配列に含まれる複数の所定長の部分配列について、部分配列の配列特異性に基づく配列特異性指標を計算する配列特異性指標計算部４０６と、複数の部分配列の中から、配列特異性指標が所定の閾値以上である部分配列を抽出する部分配列抽出部４１０と、を含んでもよい。
【０１３９】
この構成によれば、問い合わせ配列に含まれる複数の所定長の部分配列の中から、配列特異性指標が所定の閾値以上である特異性に優れる部分配列を並列処理用問い合わせ配列として抽出することができる。そのため、並列処理部３００において行う１次候補配列の抽出の際に、最終的に目的の問い合わせ配列とマッチングする可能性が低い特異性に劣る配列を抽出することなく、最終的に目的の問い合わせ配列とマッチングする可能性が高い特異性に優れる１次候補配列を抽出することができる。
【０１４０】
よって、この構成によれば、抽出される１次候補配列の数を絞り込むことができ、かつ、抽出される１次候補配列が最終的に目的の問い合わせ配列とマッチングする可能性を高めることができる。よって、１次候補配列の抽出が効率化されるので、並列処理部３００の処理速度が向上する。その結果、並列処理部３００において行う１次候補配列の抽出を高速化しつつ、精度を向上することができる。
【０１４１】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理用問い合わせ配列生成部２０４は、並列処理用問い合わせ配列を、テキスト配列およびビット配列の間で変換するビット変換部４１６を含んでもよい。
【０１４２】
この構成によれば、問い合わせ配列を、テキスト配列からビット配列に変換した後に並列処理部３００に送ることができるため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００において、１次候補配列の抽出を高速化することができる。
【０１４３】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理用問い合わせ配列生成部２０４は、問い合わせ配列を、アミノ酸配列および塩基配列の間で変換するコドン変換部４１４を含んでもよい。
【０１４４】
この構成によれば、問い合わせ配列をアミノ酸配列から塩基配列に変換することができるため、問い合わせ配列としてアミノ酸配列を取得した場合にも、ゲノムデータベース１０２に対して１次候補配列のスクリーニングを行うことができる。一方、問い合わせ配列として塩基配列を取得した場合にも、タンパク質データベースに対して１次候補配列のスクリーニングを行うことができる。
【０１４５】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理用問い合わせ配列生成部２０４は、問い合わせ配列を構成する各配列要素のバリエーションを、並列処理用問い合わせ配列の対応する各配列要素が包含するように、並列処理用問い合わせ配列を生成するように構成してもよい。
【０１４６】
この構成によれば、並列処理用問い合わせ配列は、問い合わせ配列を構成する各配列要素のバリエーションを対応する各配列要素において包含するため、問い合わせ配列の各配列要素のバリエーションを一本化して検索対象データベース１０２に投げかけることにより、１次候補配列のスクリーニングを行うことができる。そのため、並列処理部３００において、問い合わせ配列の各配列要素のバリエーションを漏れなく検索しながら、１次候補配列の抽出を高速化することができる。
【０１４７】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の問い合わせ配列はアミノ酸配列であってもよく、上記の並列処理用問い合わせ配列生成部２０４は、並列処理用問い合わせ配列として、アミノ酸配列に対応する塩基配列を表しており塩基配列の各塩基を所定長の単位ビット列で構成した並列処理用問い合わせビット列を生成するように設けられてもよく、上記の並列処理用問い合わせビット列は、アミノ酸残基を形成するための各塩基のバリエーションを単位ビット列が包含するように生成されてもよい。
【０１４８】
この構成によれば、並列処理用問い合わせビット列は、問い合わせ配列のアミノ酸配列に対応する塩基配列を表しており、塩基配列の各塩基に対応する所定長の単位ビット列で構成されているため、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを一本化することができる。そして、並列処理部３００において、このように一本化された並列処理用問い合わせビット列を検索対象データベースに投げかけることにより、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを漏れなく検索しながら、１次候補配列の抽出を高速化することができる。
【０１４９】
本実施形態に係る生物学的配列情報検索装置１００において、上記の１次候補配列抽出部３０２は、並列処理用問い合わせビット列と、検索対象データベースにおける検索対象のアミノ酸配列に対応する検索対象ビット列とを論理演算することにより配列マッチングを行うように構成してもよい。
【０１５０】
この構成によれば、並列処理用問い合わせビット列と、検索対象ビット列とを論理演算するため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００において、１次候補配列の抽出を高速化することができる。
【０１５１】
本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理部３００は、同一の素子に設けられている複数の演算器５０４を含み、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切って、複数の演算器５０４のそれぞれに割り振ることにより、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを並列処理的に行うように構成されてもよい。なお、これらの複数の演算器５０４は、互いに同一の素子に設けられていてもよく、互いに個別の素子に設けられていてもよい。
【０１５２】
この構成によれば、並列処理部３００において、複数の演算器を用いて、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切って、複数の演算器のそれぞれに割り振るため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００の複数の演算器５０４において、それぞれ割り振られた配列情報から１次候補配列を高速に抽出することができる。
【０１５３】
本実施形態に係る生物学的配列情報検索装置１００において、上記の複数の演算器５０４のうち、互いに隣接する所定長の配列情報を割り振られた演算器５０４同士は、所定長の配列情報を互いに参照可能に構成されてもよい。
【０１５４】
この構成によれば、互いに隣接する所定長の配列情報を割り振られた演算器５０４同士は、所定長の配列情報を互いに参照可能であるため、これらの複数の演算器５０４は、複数の演算器５０４にまたがって割り振られている配列情報（割り振られた配列情報の区切り目にまたがって、存在する配列情報）からも、１次候補配列を抽出することができる。そのため、複数の演算器５０４に対して、区切り目にまたがって存在する配列情報を重複して割り振る必要が無いので、複数の演算器に割り振られた配列情報の区切り目にまたがる配列情報からも、１次候補配列を高速かつ精度よく抽出することができる。
【０１５５】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の２次候補配列抽出部２１０は、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するように構成されてもよい。
【０１５６】
この構成によれば、２次候補配列抽出部２１０は、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するため、上述のように、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを一本化して並列処理用問い合わせ配列を生成した場合に、並列処理用問い合わせ配列に紛れ込むノイズ配列由来の１次候補配列を効率的に除去して２次候補配列を抽出することができる。
【０１５７】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【０１５８】
例えば、上記実施の形態では、１次候補配列抽出部３０２は、並列処理用問い合わせ配列にマッチングする１次候補配列を抽出する構成としたが、特に限定する意図はなく、例えば、並列処理用問い合わせ配列にマッチングする１次候補配列の検索対象データベース１０２中の座標を抽出する構成としてもよい。
【０１５９】
このようにすれば、並列処理部３００から中央処理部２００に返す１次候補配列の配列情報の容量を、単なる１次候補配列の座標の容量に低減することができるため、生物学的配列情報検索装置１００の処理速度をさらに向上することができる。
【０１６０】
同様に、上記実施の形態では、２次候補配列抽出部２１０は、問い合わせ配列と１次候補配列との間で、配列マッチングを行う構成としたが、特に限定する意図はなく、例えば、問い合わせ配列と、検索対象データベース１０２中の１次候補配列の座標の近傍領域との間で、配列マッチングを行う構成としてもよい。
【０１６１】
このようにしても、並列処理部３００から中央処理部２００に返す１次候補配列の配列情報の容量を、単なる１次候補配列の座標の容量に低減することができるため、生物学的配列情報検索装置１００の処理速度をさらに向上することができる。
【０１６２】
また、上記実施の形態では、中央処理部２００および並列処理部３００は別個の素子に設けられているが、特に限定する意図はなく、中央処理部２００および並列処理部３００は同一の素子に設けられていてもよい。
【０１６３】
この場合にも、並列処理部３００では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部２００では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができるという作用効果は同様だからである。
【０１６４】
また、上記実施の形態では、２次候補配列抽出部２１０において、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出する構成としたが、特に限定する趣旨ではなく、例えば、問い合わせ配列に対して所定の条件をすべて満たす形でマッチングする２次候補配列を抽出してもよい。
【０１６５】
この場合には、例えば、２次候補配列抽出部２１０において、問い合わせ配列の全長に対してＢＬＡＳＴやＦＡＳＴなどをかけることにより、完全一致でなくても相同性の高い２次候補配列を抽出することができる。
【０１６６】
また、上記実施の形態では、問い合わせ配列として、アミノ酸配列を例に挙げたが、特に限定する趣旨ではなく、例えば、塩基配列（ＤＮＡ配列およびＲＮＡ配列）や糖鎖配列なども好適に用いることができる。
【０１６７】
いずれの場合にも、並列処理部３００では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部２００では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができるという作用効果は同様だからである。
【０１６８】
また、上記実施の形態では、問い合わせ配列を４ビット単位の単位ビット列からなる問い合わせビット列に変換したが、特に限定する趣旨ではなく、例えば、２ビット、８ビット、１６ビット、３２ビット、６４ビットなどの任意のビット数からなる問い合わせビット配列に変換してもよい。
【０１６９】
いずれにしても、問い合わせ配列を問い合わせビット列に変換して、１次スクリーニングにおける論理演算を効率化できる作用効果は同様だからである。
【０１７０】
また、上記実施の形態では、検索対象データベース１０２をゲノムデータベースとしたが、特に限定する趣旨ではなく、例えば、ＰＤＢ、ＳＷＩＳＳ ＰＲＯＴなどのプロテインデータベースや、糖鎖データベースなども好適に用いうる。
【０１７１】
いずれにしても、並列処理部３００では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部２００では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができるという作用効果は同様だからである。
【０１７２】
また、上記実施の形態では、３５２個のＰＥを備えるＳＩＭＤ２０を並列処理部３００として用いたが、特に限定する趣旨ではなく、ＰＥの数は２以上であれば変動してもよく、ＳＩＭＤ２０以外の並列処理装置を用いてもよい。
【０１７３】
例えば、近年開発された、ＩＮＴＥＬ（登録商標）のＣＯＲＥ ＤＵＯ（登録商標）や、ＳＯＮＹ（登録商標）のＣＥＬＬ（登録商標）なども用いることができる。いずれも、コア数２、コア数９、とコア数は少ないが、並列処理が可能な点では、ＳＩＭＤ２０と同様であるためである。
【産業上の利用可能性】
【０１７４】
以上のように、本発明にかかる生物学的な配列情報の検索装置は、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することができるという効果を有し、生物学的な配列情報の検索装置、検索方法および検索プログラム等として有用である。
【図面の簡単な説明】
【０１７５】
【図１】実施の形態に係る生物学的配列情報検索装置の構成を説明するための機能ブロック図である。
【図２】実施の形態に係る生物学的配列情報検索装置を構成する個別の素子を説明するための機能ブロック図である。
【図３】実施の形態に係る生物学的配列情報検索装置を構成する個別の素子の機能の概要を説明するための概念図である。
【図４】実施の形態における中央処理部および並列処理部の内部構成を説明するため機能ブロック図である。
【図５】実施の形態に係る生物学的配列情報検索装置の動作を説明するためのフローチャートである。
【図６】実施の形態における並列処理用問い合わせ配列生成部の内部構成を説明するため機能ブロック図である。
【図７】実施の形態における並列処理用問い合わせ配列生成部の機能の概要を説明するための概念図である。
【図８】実施の形態における並列処理用問い合わせ配列生成部の動作を説明するためのフローチャートである。
【図９】実施の形態における１次候補配列抽出部および１次候補配列記憶部の内部構成を説明するため機能ブロック図である。
【図１０】実施の形態における１次候補配列抽出部および１次候補配列記憶部の機能の概要を説明するための概念図である。
【図１１】実施の形態における１次候補配列抽出部および１次候補配列記憶部の動作を説明するためのフローチャートである。
【図１２】実施の形態における２次候補配列抽出部の内部構成を説明するため機能ブロック図である。
【図１３】実施の形態における２次候補配列抽出部の動作を説明するためのフローチャートである。
【符号の説明】
【０１７６】
１０ ＣＰＵ
２０ ＳＩＭＤ
２２ ＰＥ
３０ バス
４０ ゲノムデータベース
１００ 生物学的配列情報検索装置
１０２ 検索対象データベース
１０４ 画像表示装置
１０６ 操作部
１０８ ＰＣ
１１０ サーバ
１１２ 外部ネットワーク
１１４ プリンタ
１１６ 外部ネットワーク
１１８ サーバ
１２０ ＰＣ
１２２ 出力部
２００ 中央処理部
２０２ 問い合わせ配列取得部
２０４ 並列処理用問い合わせ配列生成部
２０６ 並列処理用問い合わせ配列記憶部
２０８ 問い合わせ配列記憶部
２１０ ２次候補配列抽出部
２１２ ２次候補配列記憶部
３００ 並列処理部
３０２ １次候補配列抽出部
３０４ １次候補配列記憶部
４０２ 部分配列生成部
４０４ 部分配列記憶部
４０６ 配列特異性指標計算部
４０８ 配列特異性指標記憶部
４１０ 部分配列抽出部
４１６ ビット変換部
４１４ コドン変換部
５０２ データ割振部
５０４ 演算器
５０６ データ割振部
５０８ 所定長検索対象データ記憶部
５１０ 所定長区切部
５１２ 検索対象データ取得部
５１４ 記憶部
６０２ １次候補配列取得部
６０４ 完全一致配列抽出部
【技術分野】
【０００１】
本発明は、塩基配列、アミノ酸配列等の生物学的な配列情報の検索装置、検索方法および検索プログラムに関し、特に、検索処理の高速化に関する。
【背景技術】
【０００２】
分子生物学の分野では、ＤＮＡ、遺伝子、タンパク質等の解析のための情報処理技術の有用性が高まっている。この分野では、配列情報を解析するために情報処理技術が用いられる。この種の技術はバイオインフォマティクスといわれる。
【０００３】
例えば、ＳＮＰｓ（スニプッス、単一塩基多型）解析は、ほぼ同一の多数の塩基配列を解析して、局所的に異なる部分をもつ塩基配列を求める。
【０００４】
また例えば、ホモロジー検索は、複数の配列情報が似ているか、そしてどのように似ているかの情報を求める。ホモロジー検索方法としては、例えば、ブラスト（ＢＬＡＳＴ）法およびファスタ（ＦａｓｔＡ）法が知られている。
【０００５】
ブラスト法は、ギャップの挿入を行わずに局所的によく一致する部位を探索する。このような部位を高スコア断片と呼ぶ。そして、高スコア断片が前後に伸長される。
【０００６】
ファスタ法においては、配列が長く一致する部分を求める。この処理のために、従来は、複数の配列情報の一致する要素をプロットしたドットマトリックス情報が利用される。そして、一致部分の周囲に対して動的計画法によるアライメントが行われる。
【０００７】
これらの配列解析では、大量の情報を高速に処理することが求められる。非常に長い配列が処理され、また、多数の配列が処理されるからである。しかし、多くの場合には、配列解析の大量の情報処理は、専ら大型コンピュータの大きな処理能力に頼って実現されており、配列情報の高速処理技術は十分に確立していない。そして、配列解析の研究が進み、創薬および医療などの現場での分子生物学の実用化が進展するのにつれて、配列情報処理の高速化の重要性も高まると考えられる。また、大型コンピュータではなく、パーソナルコンピュータ程度の比較的小型なコンピュータによっても、大量の配列情報を高速に処理することが求められる。
【０００８】
このような小型コンピュータによっても、大量の配列情報を高速に処理することができる、従来の生物学的な配列情報の処理装置としては、例えば特許文献１に記載されたものがある。特許文献１に記載の装置では、並列照合機能をもつ記憶処理装置、典型的にはＣＡＭ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）が用いられる。
【０００９】
特許文献１に記載の装置では、この記憶処理装置に、配列情報が、被照合データとして用いるために記憶される。そして、照合データと被照合データを並列処理にて記憶処理装置に照合させて、照合データと被照合データの一致を示す情報を得ることにより、配列解析情報を得る。好ましい態様では、複数の配列が、記憶処理装置であるＣＡＭに、照合方向と交差する方向を向けて、照合方向に並ぶように記憶される。なお、照合データとしては同一文字列が用いられる。そして、ＣＡＭの照合により、複数の配列が一致するか否かが判定される。その結果、複数の配列を一つずつ照合対象から除外すると、どの配列が異なるのかが分かる。
【００１０】
【特許文献１】特開２００３−２１６６１５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記文献記載の従来技術は、生物学的な配列情報を高速かつ精度よく検索する上でさらなる改善の余地を有していた。
【００１２】
本発明は上記事情に鑑みてなされたものであり、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することを目的とする。
【課題を解決するための手段】
【００１３】
本発明によれば、生物学的配列情報に関する検索対象データベースとの間で通信可能に構成されている生物学的配列情報検索装置であって、中央処理部と、中央処理部とは別個の素子に設けられている並列処理部と、を備え、中央処理部は、生物学的情報についての問い合わせ配列を取得する問い合わせ配列取得部と、問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部と、を含み、並列処理部は、並列処理用問い合わせ配列と検索対象データベースとの間で、配列マッチングを行い、並列処理用問い合わせ配列にマッチングする１次候補配列または１次候補配列の検索対象データベース中の座標を抽出する１次候補配列抽出部を含み、さらに、中央処理部は、問い合わせ配列と、１次候補配列または検索対象データベース中の１次候補配列の座標の近傍領域との間で、配列マッチングを行い、問い合わせ配列にマッチングする２次候補配列を抽出する２次候補配列抽出部と、２次候補配列に基づく検索結果を出力する出力部と、を含む、ことを特徴とする生物学的配列情報検索装置が提供される。
【００１４】
この構成によれば、まず、中央処理部において問い合わせ配列から並列処理用問い合わせ配列を生成し、次いで、並列処理部において検索対象データベースから並列処理用問い合わせ配列にマッチングする１次候補配列の抽出を行い、再び、中央処理部において１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する形で、互いに別個の素子に設けられている中央処理部および並列処理部がそれぞれの役割を効率的に分担している。
【００１５】
このため、この構成によれば、並列処理部では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、この構成によれば、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００１６】
また、本発明によれば、生物学的配列情報に関する検索対象データベースとの間で通信可能に構成されている生物学的配列情報検索装置であって、中央処理部と、並列処理部と、を備え、中央処理部は、生物学的情報についての問い合わせ配列を取得する問い合わせ配列取得部と、問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部と、を含み、並列処理部は、並列処理用問い合わせ配列と検索対象データベースとの間で、配列マッチングを行い、並列処理用問い合わせ配列にマッチングする１次候補配列または１次候補配列の検索対象データベース中の座標を抽出する１次候補配列抽出部を含み、さらに、中央処理部は、問い合わせ配列と、１次候補配列または検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、問い合わせ配列にマッチングする２次候補配列を抽出する２次候補配列抽出部と、２次候補配列に基づく検索結果を出力する出力部と、を含む、ことを特徴とする生物学的配列情報検索装置が提供される。
【００１７】
なお、この構成においては、中央処理部および並列処理部は、互いに別個の素子に設けられてもよく、あるいは互いに同一の素子に設けられてもよい。
【００１８】
この構成においても、まず、中央処理部において問い合わせ配列から並列処理用問い合わせ配列を生成し、次いで、並列処理部において検索対象データベースから並列処理用問い合わせ配列にマッチングする１次候補配列の抽出を行い、再び、中央処理部において１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する形で、中央処理部および並列処理部がそれぞれの役割を効率的に分担している。
【００１９】
このため、この構成によれば、並列処理部では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、この構成によれば、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００２０】
なお、上記の装置は本発明の一態様であり、本発明の装置は、以上の構成要素の任意の組合せであってもよい。また、本発明の生物学的配列情報検索方法、生物学的配列情報検索システム、生物学的配列情報検索プログラム、そのプログラムを格納する記録媒体なども、同様の構成を有し、同様の作用効果を奏する。
【発明の効果】
【００２１】
本発明によれば、中央処理部および並列処理部がそれぞれの役割を効率的に分担しているため、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００２３】
図１は、実施の形態に係る生物学的配列情報検索装置の構成を説明するための機能ブロック図である。生物学的配列情報検索装置１００は、中央処理部２００と、中央処理部２００とは別個の素子に設けられている並列処理部３００と、出力部１２２と、を備えている。また、生物学的配列情報検索装置１００は、生物学的配列情報に関する検索対象データベース１０２との間で通信可能な形で接続している。
【００２４】
生物学的配列情報検索装置１００では、以下のような手順で生物学的な配列情報の検索が行われる。まず、中央処理部２００において問い合わせ配列から並列処理用問い合わせ配列を生成する。次いで、並列処理部３００において検索対象データベース１０２から並列処理用問い合わせ配列にマッチングする１次候補配列の抽出を行う。そして、再び、中央処理部２００において１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する。このような形で、互いに別個の素子に設けられている中央処理部２００および並列処理部３００がそれぞれの役割を効率的に分担している。
【００２５】
そのため、並列処理部３００は、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出することができる。そして、中央処理部２００は、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、生物学的配列情報検索装置１００では、大量の生物学的な配列情報を格納している検索対象データベース１０２から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００２６】
生物学的配列情報検索装置１００は、生物学的配列情報検索装置１００に対する操作を受け付ける操作部１０６を備える。また、生物学的配列情報検索装置１００は、外部ネットワーク１１２を介して別のＰＣ（パーソナルコンピュータ）１０８およびサーバ１１０に接続している。生物学的配列情報検索装置１００は、これらの操作部１０６、スキャナ１０４、外部ネットワーク１１２などから生物学的情報についての問い合わせ配列を取得することができる。
【００２７】
また、生物学的配列情報検索装置１００には、上記の検索結果を画像として表示する画像表示装置１０４が接続している。また、生物学的配列情報検索装置１００には、上記の検索結果を印刷するプリンタ１１４が接続している。さらに、生物学的配列情報検索装置１００には、上記の検索結果を外部ネットワーク１１６を介して取得する別のＰＣ（パーソナルコンピュータ）１２０およびサーバ１１８が接続している。そして、出力部１２２は、これらの画像表示装置１０４、プリンタ１１４、外部ネットワーク１１６などに検索結果を出力することができる。
【００２８】
図２は、実施の形態に係る生物学的配列情報検索装置を構成する個別の素子を説明するための機能ブロック図である。なお、図２は、図１の機能面に重心をおいた機能ブロック図と異なり、ハードウェア面に重心をおいた機能ブロック図である。もっとも、図１および図２のいずれも、観点が異なるだけであり、同一の生物学的配列情報検索装置１００を説明するための機能ブロック図である点では同様である。
【００２９】
図２に示すようにハードウェア面に重心をおいて説明すると、生物学的配列情報検索装置１００は、中央演算部に相当するＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１０と、ＣＰＵ１０とは別個の素子であり並列処理部に相当するＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ／Ｍｕｌｔｉｐｌｅ Ｄａｔａ）２０と、ゲノム配列に関する配列情報を格納しているゲノムデータベース４０と、これらを互いに接続するバス３０と、を備える。
【００３０】
また、ＳＩＭＤ２０内部には、複数のＰＥ（Ｐｒｏｃｅｓｓｉｎｇ Ｅｌｅｍｅｎｔ）２２が設けられている。そして、これらの複数のＰＥ２２は、互いの有する配列情報を互いに参照可能に構成されている。
【００３１】
本明細書において、ＣＰＵは、コンピュータの中で各装置の制御やデータの計算または加工を行なう中枢部分を意味する。すなわち、ＣＰＵは、メモリに記憶されたプログラムを実行する装置であり、入力装置や記憶装置からデータを受け取り、演算または加工した上で、出力装置や記憶装置に出力する機能を有する。なお、通常のパソコンでは、ＣＰＵの機能を一つのチップに集積されたマイクロプロセッサが利用され、例えばＩｎｔｅｌ社のｘ８６シリーズまたは各社の互換プロセッサを好適に使用可能である。
【００３２】
本明細書において、ＳＩＭＤは、１つの命令で、複数のデータを同時に並列的に処理する並列型情報処理装置、もしくはそのための命令を意味する。一般に、ＳＩＭＤに含まれる各演算器は、簡単な論理演算を大量かつ高速に処理することを得意とするため、マルチメディアデータを取り扱うマイクロプロセッサや、ＤＳＰ、スーパーコンピュータなどにおいて実装されている。
【００３３】
すなわち、ＳＩＭＤでは、音声や画像などのマルチメディアデータに対する処理や、３次元グラフィックス用途などでに用いるとき、固定的なフォーマットのデータに対して、同じ種類の演算を繰り返し適用することが多い。そこで、ＳＩＭＤにおいて、１つの命令で多量のデータに対して同じ種類の演算を一斉に並列的に行うようにして、データ処理能力を高めるために用意されるのがＳＩＭＤ命令である。
【００３４】
ＳＩＭＤ命令を実装するためには、データを格納するための比較的大量のレジスタ（データ供給が滞らないようにするため）と、複数のＰＥ（演算器）２２とを用いる必要があるため、ＳＩＭＤ２０内部には、多くのＰＥ（演算器）２２と、これらのＰＥ２２にそれぞれ対応する複数のレジスタ（不図示）とが設けられている。
【００３５】
なお、最近の高性能なＣＰＵの多くでは、ＣＰＵ全体の演算能力を飛躍的に増大させるため、このようなデータを格納するための比較的大量のレジスタ（データ供給が滞らないようにするため）と、複数のＰＥ（演算器）とをＣＰＵの内部に備えることもある。しかし、本実施形態では、ＣＰＵおよびＳＩＭＤの役割分担を明確にし、互いに異なる情報処理にＣＰＵによる配列情報処理およびＳＩＭＤによる並列処理の効率を向上させるため、ＳＩＭＤ２０は、ＣＰＵ１０とは別個の素子上に設けられている。
【００３６】
すなわち、生物学的配列情報検索装置１００は、ＣＰＵ１０と、並列処理回路であるＳＩＭＤ２０と、ゲノムデータが格納されたメモリであるゲノムデータベース４０とが、バス３０により互いに接続されて構成された装置である。また、生物学的配列情報検索装置１００は、ゲノムデータベース４０に格納されているゲノムデータ中から問い合わせ配列を検索して、その検索結果をネットワーク回線などによる通知などの形で出力することを目的とする装置でもある。
【００３７】
生物学的配列情報検索装置１００の特徴は、検索処理において、ＣＰＵ１０と、並列処理回路であるＳＩＭＤとに適切な機能分担を行わせている点である。
【００３８】
つまり、ＣＰＵ１０は、汎用的なプログラムコードにより動作し、そのプログラムコードにより複雑な処理も可能であるが、処理速度の面で改善の余地がある。一方、ＳＩＭＤ２０をはじめとする並列処理回路は、制限があるプログラムコードにより動作し、高速な処理が可能であるが、条件分岐等の制御処理の面で改善の余地がある（条件分岐等の制御処理をできないことはないが、実質的に困難である）。
【００３９】
これに対して、生物学的配列情報検索装置１００は、問い合わせ配列にマッチングする配列を検索するために、まず、ＳＩＭＤ２０で高速にスクリーニングを行い、そのスクリーニング結果をＣＰＵ１０で念入りに条件確認を行い、条件にあったものを最終結果とする方式をとっている。このため、大量の生物学的な配列情報を格納しているゲノムデータベース４０から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００４０】
図３は、実施の形態に係る生物学的配列情報検索装置を構成する個別の素子の機能の概要を説明するための概念図である。生物学的配列情報検索装置１００では、以下のような手順で生物学的な配列情報の検索が行われる。
【００４１】
まず、生物学的情報についての問い合わせ配列がＣＰＵ１０に入力される。続いて、ＣＰＵ１０は、問い合わせ配列からＳＩＭＤ２０での処理に適したＳＩＭＤ用問い合わせ配列を生成する。そして、ＳＩＭＤ用問い合わせ配列は、ＣＰＵ１０から出力されてＳＩＭＤ２０に入力される。
【００４２】
ＳＩＭＤ２０は、ゲノムデータベース４０からゲノムデータを取得して、ＳＩＭＤ用問い合わせ配列に対する１ｓｔスクリーニングを並列処理により行って、ＳＩＭＤ用問い合わせ配列にマッチングする１次候補配列を抽出する。そして、１次候補配列は、ＳＩＭＤ２０から出力されてＣＰＵ１０に入力される。
【００４３】
そして、ＣＰＵ１０は、ＳＩＭＤ２０から１次候補配列を取得して、問い合わせ配列に対する２ｎｄスクリーニングを行って、問い合わせ配列にマッチングする２次候補配列を抽出する。こうして得られた２次候補配列に基づく検索結果は、ＣＰＵ１０から出力される。このような形で、互いに別個の素子に設けられているＣＰＵ１０およびＳＩＭＤ２０がそれぞれの役割を効率的に分担している。
【００４４】
そのため、ＳＩＭＤ２０は、ＳＩＭＤ用問い合わせ配列に対応する１次候補配列を高速に抽出することができる。そして、ＣＰＵ１０は、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、生物学的配列情報検索装置１００では、大量の生物学的な配列情報を格納しているゲノムデータベース４０から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００４５】
図４は、実施の形態における中央処理部および並列処理部の内部構成を説明するため機能ブロック図である。なお、この図４は、上記の図１の中央処理部２００および並列処理部３００の内部構成を示している。
【００４６】
より詳細に説明すると、中央処理部２００では、生物学的情報についての問い合わせ配列は、問い合わせ配列取得部２０２により取得され、問い合わせ配列記憶部２０８に格納される。次いで、並列処理用問い合わせ配列生成部２０４が、問い合わせ配列記憶部２０８から問い合わせ配列を読み出し、問い合わせ配列に基づいて並列処理用問い合わせ配列を生成し、並列処理用問い合わせ配列記憶部２０６に格納する。
【００４７】
続いて、並列処理部３００では、１次候補配列抽出部３０２が、並列処理用問い合わせ配列記憶部２０６から並列処理用問い合わせ配列を読み出し、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを並列処理により行って、並列処理用問い合わせ配列にマッチングする１次候補配列を抽出し、１次候補配列記憶部３０４に格納する。
【００４８】
次いで、中央処理部２００では、２次候補配列抽出部２１０が、１次候補配列記憶部３０４から１次候補配列を読み出し、さらに、問い合わせ配列記憶部２０８から問い合わせ配列を読み出す。そして、２次候補配列抽出部２１０は、問い合わせ配列と１次候補配列との間で配列マッチングを行い、問い合わせ配列にマッチングする２次候補配列を抽出して、２次候補配列記憶部２１２に格納する。その後、出力部１２２は、２次候補配列記憶部２１２から２次候補配列を読み出し、２次候補配列に基づく検索結果を出力する。
【００４９】
一部の説明は繰り返しになるが、生物学的配列情報検索装置１００では、上記のような構成を用いて生物学的な配列情報の検索が行われる。すなわち、中央処理部２００の並列処理用問い合わせ配列生成部により、問い合わせ配列から並列処理用問い合わせ配列が生成される。次いで、並列処理部３００の１次候補配列抽出部３０２により、検索対象データベース１０２から並列処理用問い合わせ配列にマッチングする１次候補配列が抽出される。そして、中央処理部２００の２次候補配列抽出部２１０により、１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する。
【００５０】
このような形で、互いに別個の素子に設けられている中央処理部２００および並列処理部３００がそれぞれの役割を効率的に分担している。そのため、並列処理部３００は、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出することができる。そして、中央処理部２００は、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、生物学的配列情報検索装置１００では、大量の生物学的な配列情報を格納している検索対象データベース１０２から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【００５１】
図５は、実施の形態に係る生物学的配列情報検索装置の動作を説明するためのフローチャートである。生物学的配列情報検索装置１００の一連の動作が開始すると、まず、中央処理部２００の問い合わせ配列取得部２０２は、外部から問い合わせ配列を取得する（Ｓ１０２）。次いで、中央処理部２００の並列処理用問い合わせ配列生成部２０４は、問い合わせ配列から並列処理用問い合わせ配列を生成する（Ｓ１０４）。
【００５２】
そして、並列処理部３００の１次候補配列抽出部３０２は、並列処理用問い合わせ配列と検索対象データベースとをマッチングさせて、問い合わせ配列に潜在的にマッチングする可能性を有する１次候補配列を抽出する（Ｓ１０６）。次に、中央処理部２００の２次候補配列抽出部２１０は、１次候補配列と問い合わせ配列とをマッチングさせて、問い合わせ配列にマッチングする２次候補配列を抽出し（Ｓ１０８）、一連の動作を終了する。
【００５３】
その後、中央処理部２００の出力部１２２は、２次配列候補に基づく検索結果を出力して（Ｓ１１０）、生物学的配列情報検索装置１００の一連の動作が終了する。
【００５４】
図６は、実施の形態における並列処理用問い合わせ配列生成部の内部構成を説明するため機能ブロック図である。並列処理用問い合わせ配列生成部２０４では、コドン変換部４１４は、問い合わせ配列記憶部２０８から問い合わせ配列を読み出して、問い合わせ配列の形式をアミノ酸配列から塩基配列に変換する。次に、ビット変換部４１６は、問い合わせ配列の形式をテキスト配列からビット配列に変換して得られる問い合わせビット列を、問い合わせビット列記憶部４１８に格納する。
【００５５】
続いて、部分配列生成部４０２は、問い合わせビット列を構成する複数の所定長の部分配列を生成し、部分配列記憶部４０４に格納する。なお、これらの部分配列は、互いに一部のビット列が重複していてもよい。そして、配列特異性指標計算部４０６は、問い合わせビット列に含まれる複数の所定長の部分配列について、その部分配列の配列特異性に基づく配列特異性指標を計算し、配列特異性指標記憶部４０８に格納する。
【００５６】
次いで、部分配列抽出部４１０は、配列特異性指標記憶部４０８から配列特異性指標を読み出し、部分配列記憶部４０４から部分配列を読み出し、さらに、あらかじめ配列特異性の閾値が格納されている閾値記憶部４１２から閾値を読み出して、複数の部分配列の中から、配列特異性指標が所定の閾値以上である部分配列を抽出する。その後、部分配列抽出部４１０は、抽出した部分配列に基づいた並列処理用問い合わせ配列を並列処理用問い合わせ配列記憶部２０６に格納する。
【００５７】
図７は、実施の形態における並列処理用問い合わせ配列生成部の機能の概要を説明するための概念図である。図７（ａ）および（ｂ）に示すように、コドン変換部４１４は、問い合わせ配列記憶部２０８から問い合わせ配列を読み出すと、問い合わせ配列の形式をアミノ酸配列から塩基配列に変換する。このとき、アミノ酸配列および塩基配列が一対多で対応するため、１つのアミノ酸配列から、複数の塩基配列（塩基配列１、塩基配列２、塩基配列３・・・）が生じる。
【００５８】
次いで、図７（ｂ）および図７（ｃ）に示すように、ビット変換部４１６は、コドン変換部４１４から塩基配列の形式の問い合わせ配列を受け取ると、これらの複数の問い合わせ配列の形式を塩基配列からビット列に変換して、複数のビット列（ビット列１、ビット列２、ビット列３・・・）を得る。
【００５９】
その後、図７（ｃ）および図７（ｄ）に示すように、ビット変換部４１６は、上述のようにアミノ酸および塩基配列が一対多で対応することにより生じる、問い合わせ配列であるアミノ酸配列を構成する複数の塩基配列における各塩基のバリエーションを一本化して、１つの問い合わせビット列を生成する。このとき、塩基（配列要素）単位でバリエーションを包含するようにＯＲ計算により問い合わせビット列が生成される。
【００６０】
すなわち、並列処理用問い合わせ配列生成部２０４では、１つのアミノ酸配列形式の問い合わせ配列に対応する１つの問い合わせビット列を生成する。なお、このようにして複数のビット列を一本化されたビット列を、本明細書では、最小公倍ビット列と呼ぶ。もっとも、この最小公倍ビット列の概念は、厳密に数学的な意味での最小公倍数の概念に縛られるものではない。
【００６１】
より詳しくは、問い合わせ配列であるアミノ酸配列を構成する塩基配列の各塩基（各配列要素）のバリエーションを、問い合わせビット列（最小公倍ビット列）の対応する各配列要素（４ビットからなる各ビット列単位）が包含するように、問い合わせビット列が生成される。なお、本明細書では、ビット列単位とは、例えば、１アミノ酸残基、１ヌクレオチド残基に対応する、所定長のビット列を意味する。
【００６２】
この実施形態では、Ａ、Ｔ、Ｇ、Ｃの４種類の塩基は、４ビットのビット列で表現可能であるため、ビット列単位は４ビット長であるものとする。もっとも、Ａ、Ｔ、Ｇ、Ｃの４種類の塩基は、厳密に数学的には２ビット以上であれば充分に表現可能である。なお、このような問い合わせビット列の具体例を後述により説明する。
【００６３】
そして、図７（ｄ）および図７（ｅ）に示すように、部分配列生成部４０２、配列特異性指標計算部４０６、部分配列抽出部４１０、閾値記憶部４１２は、互いに協働して、こうして得られた最小公倍ビット列を構成する複数の部分配列の中から、配列特異性指標が閾値以上である部分配列（特異性に優れる部分配列であり、本明細書では、特異ビット列と呼ぶ）を、並列処理用問い合わせビット列として抽出する。
【００６４】
上述のように、並列処理用問い合わせ配列生成部２０４では、問い合わせ配列はアミノ酸配列である場合、コドン変換部４１４、ビット変換部４１６、部分配列生成部４０２、配列特異性指標計算部４０６、部分配列抽出部４１０および閾値記憶部４１２が、互いに協働して、並列処理用問い合わせ配列としての特異ビット列を生成する。
【００６５】
すなわち、これらの働きにより、アミノ酸配列に対応する塩基配列を表しておりその塩基配列の各塩基を所定長の単位ビット列で構成した並列処理用問い合わせビット列が生成される。その結果、並列処理用問い合わせビット列は、問い合わせ配列の各アミノ酸残基を形成する各塩基のバリエーションを、並列処理用問い合わせビット列としての特異ビット列の単位ビット列が包含するように生成されることになる。
【００６６】
以下、並列処理用問い合わせ配列生成部２０４の処理を、より具体的に説明する。
並列処理用問い合わせ配列生成部２０４では、ＳＩＭＤなどの並列処理部３００の１ｓｔスクリーニングのために、生物学的特徴を考慮した前処理を問い合わせ配列に対して施している。まず、並列処理部３００にとって処理しやすいように問い合わせ配列を既知の方法により数値化している。
【００６７】
すなわち、問い合わせ配列が核酸（小文字表記）の場合、ビット変換部４１６により２進数表現に変換する。なお、代表的な核酸のコード表を下記の表１に示す。
【００６８】
【表１】
【００６９】
ａ → ０００１
ｔ → ００１０
ｃ → ０１００
ｇ → １０００
【００７０】
この場合、例えば、ｓは、ｃまたはｇを意味するが、数値化すると１１００となる。
ｓ＝ｃ ｏｒ ｇ＝０１００ ｏｒ １０００＝１１００
【００７１】
一方、問い合わせ配列がアミノ酸（大文字表記）の場合、コドン変換部４１４によりコドン表を用いてアミノ酸を核酸に変換した場合、通常は核酸３つで１つのアミノ酸を構成するが、１つのアミノ酸に対して複数の組み合わせがあるケースも存在する。なお、代表的なアミノ酸のコード表を下記の表２に示す。
【００７２】
【表２】
【００７３】
また、このときの注意事項として、アミノ酸のコドン表は、生物種によって多少異なる場合があり、また、同じ生物種でも、核とミトコンドリアとでは、異なることが多い。すなわち、コドン表は１種類ではなく、いくつもの種類が存在する。
【００７４】
ヒトの核のコドン表による場合
Ass =FFLLSSSSYY**CC*WLLLLPPPPHHQQRRRRIIIMTTTTNNKKSSRRVVVVAAAADDEEGGGG
Starts=---M---------------M---------------M----------------------------
Base1 =TTTTTTTTTTTTTTTTCCCCCCCCCCCCCCCCAAAAAAAAAAAAAAAAGGGGGGGGGGGGGGGG
Base2 =TTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGG
Base3 =TCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAG
なお、上記Assは、配列番号：１、Base1は、配列番号：２、Base2は、配列番号：３、Base3は、配列番号４に相当する。
【００７５】
ヒトのミトコンドリアのコドン表による場合
Ass =FFLLSSSSYY**CC*WLLLLPPPPHHQQRRRRIIIMTTTTNNKKSSRRVVVVAAAADDEEGGGG
Starts=---M---------------M------------MMMM---------------M------------
Base1 =TTTTTTTTTTTTTTTTCCCCCCCCCCCCCCCCAAAAAAAAAAAAAAAAGGGGGGGGGGGGGGGG
Base2 =TTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGGTTTTCCCCAAAAGGGG
Base3 =TCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAG
なお、上記Assは、配列番号：１、Base1は、配列番号：２、Base2は、配列番号：３、Base3は、配列番号４に相当する。
【００７６】
次に、再びアミノ酸配列を塩基配列に変換する処理についての説明に戻る。
たとえば、アミノ酸のＭは、
Ｍ → ａｔｇ
の唯一の組み合わせのみである。
【００７７】
一方、アミノ酸のＢは４通りあり、
Ｂ → ａａｃ、ｇａｔ、ａａｔ、ｇａｃ
である。
【００７８】
これを数値化すると、下記のようになる。
Ｍ → ａｔｇ → ０００１ ００１０ １０００
Ｂ → ０００１ ０００１ ０１００、１０００ ０００１ ００１０
０００１ ０００１ ００１０、１０００ ０００１ ０１００
【００７９】
なお、問い合わせ配列は、核酸、アミノ酸を要素とすることができる。
また、ワイルドカード（核酸（．）、アミノ酸（＊））も使用可能である。
さらに、ｏｒ記述（演算子 ｜ ）も使用可能である。
【００８０】
例としては、以下のような配列を問い合わせ配列として使用可能である。
ａｔｃｇＡＢＧａｔ 核酸、アミノ酸が混在していてもよい。
ａｔ．ｇ＊ＢＧ．ｔ ワイルドカードが混在していてもよい。
ａｔ｛ｃｇ｜ａｔ｝ｇｇ ｏｒ表現 ａｔｃｇｇｇまたはａｔａｔｇｇを意味する。
【００８１】
このとき、問い合わせ配列を、数値化するに際して、複数の数値列ではなく、単一の数値列にする。すなわち、すべての問い合わせ配列が漏れない形にしつつ、複数の数値列を一本化するように処理する。
【００８２】
例えば、Ｂは、
Ｂ → ０００１ ０００１ ０１００、１０００ ０００１ ００１０
０００１ ０００１ ００１０、１０００ ０００１ ０１００
であるが、１ｓｔスクリーニングのための前処理にあたり、
Ｂ → １００１ ０００１ ０１１０
に数値化する（ＯＲ演算を行っている）。これは、上述で説明した並列処理用問い合わせ配列の一本化のため、問い合わせ配列であるアミノ酸配列を構成する塩基配列の各塩基のバリエーションを、問い合わせビット列の対応する各配列要素が包含するように、問い合わせビット列を生成する処理である。
【００８３】
さらに、ＳＩＭＤをはじめとする並列処理部３００内部の各々の演算器５０４で扱える並列処理用問い合わせ配列の配列数には、処理能力の限界がある。その限界値を超えるケースでは、下記の処理を行う。
【００８４】
たとえば、
atcga****tacgactagcat***atcga（配列番号：５）
という並列処理用問い合わせ配列で、をはじめとする並列処理部３００内部の各々の演算器５０４で扱える配列数が１０以下だとすると、
atcga****tacgactagcat***atcga（配列番号：５）
|--------|
|--------|
|--------|
|--------|
という具合に、並列処理用問い合わせ配列の一部分（１０塩基）をＳＩＭＤをはじめとする並列処理部３００用の問い合わせ配列として、並列処理部３００で１ｓｔスクリーニングを行うことになる。
【００８５】
ここで、効率のよいスクリーニングを行うには、ワイルドカードを含まない、以下の３通りの抽出が最適である。
atcga****tacgactagcat***atcga（配列番号：５）
|--------|
|--------|
|--------|
【００８６】
なお、例としてワイルドカードを用いたケースを挙げたが、この場合には、並列処理用問い合わせ配列をＯＲ計算した数値例を元に計算によって、最適抽出箇所を判定可能である。具体的には、下記のｓｃｏｒｅ値が最大となる箇所を検索する。
【００８７】
Ｓｃｏｒｅ＝Πｆ（ｑ［ｉ］）
ｆ（ａ）＝単位ビット列を構成する４ｂｉｔ中１の数が、
１つの場合 → １
２つの場合 → ０．５
３つの場合 → ０．２５
４つの場合 → ０．１２５
【００８８】
図８は、実施の形態における並列処理用問い合わせ配列生成部の動作を説明するためのフローチャートである。まず、コドン変換部４１４が、問い合わせ配列記憶部２０８から問い合わせ配列を取得すると、問い合わせ配列の形式をアミノ酸配列から塩基配列に変換する（Ｓ２０２）。次いで、ビット変換部４１６が、問い合わせ配列の形式を塩基配列からビット配列に変換する（Ｓ２０４）。
【００８９】
さらに、同様にビット変換部４１６が、複数のビット配列の形式からなる問い合わせ配列をＯＲ計算により１本のビット配列にまとめて、問い合わせビット列を生成する（Ｓ２０６）。そして、部分配列生成部４０２が、問い合わせビット列から複数の部分配列を生成する。続いて、配列特異性指標計算部４０６が、これらの複数の部分配列について、特異性指標を計算する（Ｓ２０８）。その後、部分配列抽出部４１０が、こうして得られた配列特異性指標が所定の閾値以上である特異性の優れる部分配列を、並列処理用問い合わせ配列として抽出し（Ｓ２１０）、一連の動作を終了する。
【００９０】
この並列処理用問い合わせ配列生成部２０４の構成によれば、並列処理用問い合わせ配列は、問い合わせ配列を構成する各配列要素のバリエーションを対応する各配列要素において包含するため、問い合わせ配列の各配列要素のバリエーションを一本化して検索対象データベース１０２に投げかけることにより、１次候補配列のスクリーニングを行うことができる。そのため、並列処理部３００において、問い合わせ配列の各配列要素のバリエーションを漏れなく検索しながら、１次候補配列の抽出を高速化することができる。
【００９１】
上記の記載と一部重複するが、別の形で表現すると、この並列処理用問い合わせ配列生成部２０４の構成によれば、並列処理用問い合わせビット列は、問い合わせ配列のアミノ酸配列に対応する塩基配列を表しており、塩基配列の各塩基に対応する所定長の単位ビット列で構成されているため、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを一本化することができる。そして、並列処理部において、このように一本化された並列処理用問い合わせビット列を検索対象データベース１０２に投げかけることにより、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを漏れなく検索しながら、１次候補配列の抽出を高速化することができる。
【００９２】
また、この並列処理用問い合わせ配列生成部２０４の構成によれば、コドン変換部４１４により、問い合わせ配列を、テキスト配列からビット配列に変換した後に並列処理部３００に送ることができるため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００において、１次候補配列の抽出を高速化することができる。
【００９３】
また、この並列処理用問い合わせ配列生成部２０４の構成によれば、問い合わせ配列をアミノ酸配列から塩基配列に変換することができるため、問い合わせ配列としてアミノ酸配列を取得した場合にも、ゲノムデータベース１０２に対して１次候補配列のスクリーニングを行うことができる。
【００９４】
さらに、この並列処理用問い合わせ配列生成部２０４の構成によれば、問い合わせ配列に含まれる複数の所定長の部分配列の中から、配列特異性指標が所定の閾値以上である特異性に優れる部分配列を並列処理用問い合わせ配列として抽出することができる。そのため、並列処理部３００において行う１次候補配列の抽出の際に、最終的に目的の問い合わせ配列とマッチングする可能性が低い特異性に劣る配列を抽出することなく、最終的に目的の問い合わせ配列とマッチングする可能性が高い特異性に優れる１次候補配列を抽出することができる。
【００９５】
よって、この並列処理用問い合わせ配列生成部２０４の構成によれば、抽出される１次候補配列の数を絞り込むことができ、かつ、抽出される１次候補配列が最終的に目的の問い合わせ配列とマッチングする可能性を高めることができる。よって、１次候補配列の抽出が効率化されるので、並列処理部３００の処理速度が向上する。その結果、並列処理部において行う１次候補配列の抽出を高速化しつつ、精度を向上することができる。
【００９６】
なお、上述の処理では、問い合わせ配列がアミノ酸配列の場合に、アミノ酸配列が塩基配列に変換され、さらに、上述のような問い合わせビット列に変換された。より簡単には、各アミノ酸と、それに対応するビット列とのテーブルが予め作成され、記憶されていてもよい。このビット列は、上述の原理に従って該当するアミノ酸を構成する複数の塩基列のバリエーションを包含するように設定される。このようなテーブルが参照されて、アミノ酸配列が問い合わせビット列に変換されてもよい。
【００９７】
図９は、実施の形態における１次候補配列抽出部および１次候補配列記憶部の内部構成を説明するための機能ブロック図である。１次候補配列抽出部３０２には、同一の素子に設けられている複数の演算器５０４が設けられている。
【００９８】
まず、１次候補配列抽出部３０２では、検索対象データ取得部５１２が、検索対象データベース１０２中の生物学的配列情報を取得する。次いで、所定長区切部５１０が、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切り、区切って得られた所定長検索対象データを所定長検索対象データ記憶部５０８に格納する。
【００９９】
その後、データ割振部５０２が、並列処理用問い合わせ配列記憶部２０６から並列処理用問い合わせ配列を取得し、複数の演算器５０４のそれぞれに、同一の並列処理用問い合わせ配列を割り振る。一方では、データ割振部５０６が、所定長検索対象データ記憶部５０８から区切って得られた所定長検索対象データを読み出し、複数の演算器５０４のそれぞれに割り振ることにより、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを並列処理的に行う。
【０１００】
このとき、一次候補配列抽出部３０２は、同一の素子に設けられている複数の演算器５０４を含み、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切って、複数の演算器５０４のそれぞれに割り振ることにより、並列処理用問い合わせ配列と検索対象データベースとの間で、配列マッチングを並列処理的に行って１次候補配列を抽出するように構成されている。
【０１０１】
一次候補配列抽出部３０２の複数の演算器５０４により、並列処理的に配列マッチングされて抽出された複数の１次候補配列は、それぞれ１次候補配列記憶部３０４内の対応する記憶部５１４（記憶部５１４ａ、記憶部５１４ｂ、記憶部５１４ｃ・・・）に格納される。また、複数の演算器５０４のうち、互いに隣接する前記所定長の配列情報を割り振られた演算器５０４同士は、所定長の配列情報を互いに参照可能に構成されている。
【０１０２】
図１０は、実施の形態における１次候補配列抽出部および１次候補配列記憶部の機能の概要を説明するための概念図である。まず、図１０（ａ）および図１０（ｂ）に示すように、所定長区切部５１０が、検索対象データベース１０２から取得されたゲノムデータの一部（区分１、区分２、区分３・・・）を複数の所定長のゲノムデータに区切る。そして、このようにして所定長区切部５１０により区切られて得られた所定長ゲノムデータを、データ割振部５０６が、複数の演算器５０４（ＰＥ０、ＰＥ１、ＰＥ２、・・・・ＰＥ３５１）のそれぞれに割り振る。すなわち、データ割振部５０６は、ゲノムデータの一部を３５２個に区切って、３５２個のＰＥに割り振ることになる。
【０１０３】
一方では、図１０（ｂ）および図１０（ｃ）に示すように、データ割振部５０２が、並列処理用問い合わせ配列記憶部２０６から取得された並列処理用問い合わせ配列を、複数の演算器５０４のそれぞれに割り振る。すなわち、データ割振部５０２は、互いに同一の並列処理用問い合わせ配列を３５２個のＰＥに割り振ることになる。
【０１０４】
その後、複数の演算器５０４のそれぞれにおいて、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを並列処理的に行う。なお、複数の演算器５０４（３５２個のＰＥ）は、並列処理による配列マッチングを行うが、その際、並列処理用問い合わせ配列をＰＥ１つ分の領域内で１塩基相当分の幅ずつずらしながら、並列処理による配列マッチングを行う。
【０１０５】
以下、ＳＩＭＤなどからなる並列処理部３００における１ｓｔスクリーニングの動作について、より詳細に説明する。
【０１０６】
ＳＩＭＤなどからなる並列処理部３００における１ｓｔスクリーニングは、１次候補配列を抽出することを目的として、以下のような方法により行うことができる。つまり、ＳＩＭＤなどからなる並列処理部３００では、以下の例に示すような処理（演算）を行う。
【０１０７】
ＰＥをはじめとする演算器５０４とゲノムデータとの処理方法は、下記の様にして行った。なお、ＰＥとは、ＳＩＭＤ内部の小さなＣＰＵを指す。本発明者が、実験に用いたＳＩＭＤチップは、１ＳＩＭＤあたり３５２ＰＥ内蔵されているものを使った。
【０１０８】
| PE 0 || PE 1 || PE 2 |--------------------------------------|PE 351|
atcgatcgatacgacgtacgtacgatgc---------------------------------acgtacgta
atcgatcg
atcgatcg
atcgatcg
atcgatcg
atcgatcg
atcgatcg
atcgatcg
atcgatcg
なお、上記の長い方の配列の左側は、配列番号：６に相当する。
【０１０９】
上記の例では、並列処理用問い合わせ配列ａｔｃｇａｔｃｇを検索するために、ＰＥ２が担当する領域に対して、一致するかどうかをシフトしながら検出している。
【０１１０】
なお、並列処理用問い合わせ配列と、複数の演算器５０４に割り振られたゲノムデータとが一致するかどうかの検出の際には、例えば、下記のような論理演算を行う。
【０１１１】
例：
ゲノムデータ： １０００ ０００１ ０１００
問い合わせ配列： Ｂ １００１ ０００１ ０１１０
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
演算結果： １０００ ０００１ ０１００
この演算結果は、どの単位ビット列にも００００がないため「ヒット」である。
【０１１２】
ゲノムデータ： ００１０ ０００１ １０００
問い合わせ配列： Ｂ １００１ ０００１ ０１１０
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
演算結果： ００００ ０００１ ００００
この演算結果は、００００があるため、「ミス」である。
【０１１３】
本実施形態では、ＳＩＭＤなどからなる並列処理部３００において、このような条件分岐のない単純なスクリーニング処理を行い、その結果を元に並列処理用問い合わせ配列と合致するかどうかを確認する。そして、合致した場合、その合致したゲノム配列の一部の領域を、１次候補配列の検索結果とする。
【０１１４】
すなわち、これまで例として挙げた内容をまとめると、並列処理用問い合わせ配列と、複数の演算器５０４に割り振られたゲノムデータとが一致するかどうかの検出の際には、以下の手順を繰り返すことになる。
【０１１５】
処理の流れ
１．データ割振部５０６が、ゲノムデータの先頭から特定のデータ長分をＰＥをはじめとする演算器５０４に流し込む。データ長は、１つのＰＥをはじめとする演算器５０４が扱えるデータ数×ＰＥをはじめとする演算器５０４の数である。
【０１１６】
２．各ＰＥをはじめとする演算器５０４は、そのＰＥをはじめとする演算器５０４が担当する領域に対して先頭から順に並列処理用問い合わせ配列と合致するかをシフトしながら調べる。
【０１１７】
３．並列処理部３００は、並列処理用問い合わせ配列と、複数の演算器５０４に割り振られたゲノムデータとの合致箇所を、１ｓｔスクリーニングの結果（１次候補配列）として、ＣＰＵをはじめとする中央処理部２００に通知する。
【０１１８】
４．１．に戻り、後続のゲノムデータをＰＥに流し込み、処理を続ける。
【０１１９】
図１１は、実施の形態における１次候補配列抽出部および１次候補配列記憶部の動作を説明するためのフローチャートである。まず、所定長区切り部５１０が、検索対象データベース１０２から検索対象データ取得部５１２を介して取得した検索対象データベースの一部（１区分目、２区分目、３区分目・・・）をそれぞれ所定長ごとに区切る。そして、データ割振部５０６が、所定長に区切られたゲノムデータを演算器５０４（演算器１、演算器２、演算器３・・・）に割り振る（Ｓ３０２）。
【０１２０】
一方で、データ割振部５０２が、並列処理用問い合わせ配列記憶部２０６から取得した同一の並列処理用問い合わせ配列を、複数の演算器５０４（演算器１、演算器２、演算器３・・・）に割り振る（Ｓ３０４）。そして、並列処理用問い合わせ配列を１塩基分ずつずらしながら、それぞれの演算器５０４（演算器１、演算器２、演算器３・・・）で配列マッチングを並列的に行う（Ｓ３０６）。
【０１２１】
そして、それぞれの演算器５０４（演算器１、演算器２、演算器３・・・）の配列マッチングの結果得られる１次候補配列は、それぞれ１次候補配列候補記憶部３０４内の記憶部５１４（記憶部１、記憶部２、記憶部３・・・・）に格納される。そして、中央処理部２００からの求めに応じて、これらの配列マッチングの結果である１次候補配列は、中央処理部２００に送られる（Ｓ３０８）。
【０１２２】
その後、中央処理部２００において、ゲノムデータの全区分の配列マッチングが完了したか否かが判定される（Ｓ３１０）。未だ完了していないと判定された場合には、前回にゲノムデータのｎ区分目を割り振ったのであれば、今回は、データ割振部５０６は、ｎ＋１区分目を新たにそれぞれの演算器５０４（演算器１、演算器２、演算器３・・・）に割り振って、再度、上記のサイクルを繰り返す（Ｓ３１２）。一方、既に完了したと判定された場合には、１次候補配列抽出部３０２および１次候補配列記憶部３０４は、一連の動作を終了する。
【０１２３】
本実施形態における１次候補配列抽出部３０２および１次候補配列記憶部３０４の構成によれば、並列処理用問い合わせビット列と、検索対象ビット列とを複数の演算器５０４（演算器１、演算器２、演算器３・・・）により並列処理的に論理演算するため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００において、１次候補配列の抽出を高速化することができる。
【０１２４】
また、本実施形態における１次候補配列抽出部３０２および１次候補配列記憶部３０４の構成によれば、並列処理部３００において、複数の演算器５０４を用いて、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切って、複数の演算器５０４のそれぞれに割り振るため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００の複数の演算器５０４において、それぞれ割り振られた配列情報から１次候補配列を高速に抽出することができる。
【０１２５】
また、本実施形態における１次候補配列抽出部３０２および１次候補配列記憶部３０４の構成によれば、互いに隣接する所定長の配列情報を割り振られた演算器５０４同士は、所定長の配列情報を互いに参照可能であるため、これらの複数の演算器５０４は、複数の演算器５０４にまたがって割り振られている配列情報（割り振られた配列情報の区切り目にまたがって、存在する配列情報）からも、１次候補配列を抽出することができる。そのため、複数の演算器５０４に対して、区切り目にまたがって存在する配列情報を重複して割り振る必要が無いので、複数の演算器５０４に割り振られた配列情報の区切り目にまたがる配列情報からも、１次候補配列を高速かつ精度よく抽出することができる。
【０１２６】
図１２は、実施の形態における２次候補配列抽出部の内部構成を説明するため機能ブロック図である。２次候補配列抽出部２１０は、１次候補配列取得部６０２と、完全一致配列抽出部６０４とを備える。１次候補配列取得部６０２は、１次候補配列記憶部３０４に含まれる複数の記憶部５１４（記憶部１、記憶部２、記憶部３・・・）から、それぞれに格納されている１次候補配列を取得し、完全一致配列抽出部６０４に受け渡す。
【０１２７】
次いで、完全一致配列抽出部６０４は、問い合わせ配列記憶部２０８から、当初入力された問い合わせ配列を取得し、１次候補配列取得部６０２から受け取った１次候補配列と配列マッチングを行う。このとき、完全一致配列抽出部６０４は、複数の１次候補配列から、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するように構成されている。
【０１２８】
このような２次候補配列抽出が必要な理由を説明する。１次候補配列では、並列処理の特徴を活かして高速で配列マッチングを行える代わりに、下記に例示されるミスヒットも発生する可能性があり、問い合わせ配列以外の配列も含んでしまっている。
【０１２９】
１次候補配列のスクリーニングでミスヒットを出力する例を示す。
アミノ酸配列のｓは、塩基配列になおすと、ｔｃｎまたはａｇｙであり、具体的には、
ｔｃａ
ｔｃｔ
ｔｃｃ
ｔｃｇ
ａｇｃ
ａｇｔ
が該当する（ｎは、ａまたはｔまたはｃまたはｇであり、ｙは、ｃまたはｔ）。
【０１３０】
これを一本化して数値化すると、００１１ １１００ １１１１となる。
そのため、ミスヒットのケースとしては、
０００１ ０１００ ０００１ → ａｃａ
００１０ １０００ ０００１ → ｔｇａ
などがある。
【０１３１】
このように１次候補配列の抽出では、一部にミスヒットが含まれてしまう可能性があるので、２次候補配列の抽出が好適に行われて、これにより最終的に高精度のマッチングが可能になる。
【０１３２】
図１３は、実施の形態における２次候補配列抽出部の動作を説明するためのフローチャートである。まず、１次候補配列取得部６０２が、１次候補配列記憶部３０４に含まれる複数の記憶部５１４（記憶部１、記憶部２、記憶部３・・・）から、それぞれに格納されている１次候補配列を取得する（Ｓ４０２）。
【０１３３】
次いで、完全一致配列抽出部６０４は、問い合わせ配列記憶部２０８から、当初入力された問い合わせ配列を取得する（Ｓ４０４）。そして、完全一致配列抽出部６０４は、複数の１次候補配列から、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出し（Ｓ４０６）、一連の動作を終了する。
【０１３４】
本実施形態に係る２次候補配列抽出部２１０の構成によれば、２次候補配列抽出部２１０は、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するため、上述のように、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを一本化して並列処理用問い合わせ配列を生成した場合に、並列処理用問い合わせ配列に紛れ込むノイズ配列由来の１次候補配列を効率的に除去して２次候補配列を抽出することができる。
【０１３５】
以下、本実施形態に係る生物学的配列情報検索装置の作用効果について、説明する。
【０１３６】
本実施形態に係る生物学的配列情報検索装置１００の構成においては、まず、中央処理部２００において問い合わせ配列から並列処理用問い合わせ配列を生成し、次いで、並列処理部３００において検索対象データベース１０２から並列処理用問い合わせ配列にマッチングする１次候補配列の抽出を行い、再び、中央処理部２００において１次候補配列から問い合わせ配列にマッチングする２次候補配列を抽出する形で、中央処理部２００および並列処理部３００がそれぞれの役割を効率的に分担している。
【０１３７】
このため、この構成によれば、並列処理部３００では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部２００では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができる。その結果、この構成によれば、大量の生物学的な配列情報を格納している検索対象データベース１０２から、目的の生物学的な配列情報を高速かつ精度よく検索することができる。
【０１３８】
本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理用問い合わせ配列生成部２０４は、問い合わせ配列に含まれる複数の所定長の部分配列について、部分配列の配列特異性に基づく配列特異性指標を計算する配列特異性指標計算部４０６と、複数の部分配列の中から、配列特異性指標が所定の閾値以上である部分配列を抽出する部分配列抽出部４１０と、を含んでもよい。
【０１３９】
この構成によれば、問い合わせ配列に含まれる複数の所定長の部分配列の中から、配列特異性指標が所定の閾値以上である特異性に優れる部分配列を並列処理用問い合わせ配列として抽出することができる。そのため、並列処理部３００において行う１次候補配列の抽出の際に、最終的に目的の問い合わせ配列とマッチングする可能性が低い特異性に劣る配列を抽出することなく、最終的に目的の問い合わせ配列とマッチングする可能性が高い特異性に優れる１次候補配列を抽出することができる。
【０１４０】
よって、この構成によれば、抽出される１次候補配列の数を絞り込むことができ、かつ、抽出される１次候補配列が最終的に目的の問い合わせ配列とマッチングする可能性を高めることができる。よって、１次候補配列の抽出が効率化されるので、並列処理部３００の処理速度が向上する。その結果、並列処理部３００において行う１次候補配列の抽出を高速化しつつ、精度を向上することができる。
【０１４１】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理用問い合わせ配列生成部２０４は、並列処理用問い合わせ配列を、テキスト配列およびビット配列の間で変換するビット変換部４１６を含んでもよい。
【０１４２】
この構成によれば、問い合わせ配列を、テキスト配列からビット配列に変換した後に並列処理部３００に送ることができるため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００において、１次候補配列の抽出を高速化することができる。
【０１４３】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理用問い合わせ配列生成部２０４は、問い合わせ配列を、アミノ酸配列および塩基配列の間で変換するコドン変換部４１４を含んでもよい。
【０１４４】
この構成によれば、問い合わせ配列をアミノ酸配列から塩基配列に変換することができるため、問い合わせ配列としてアミノ酸配列を取得した場合にも、ゲノムデータベース１０２に対して１次候補配列のスクリーニングを行うことができる。一方、問い合わせ配列として塩基配列を取得した場合にも、タンパク質データベースに対して１次候補配列のスクリーニングを行うことができる。
【０１４５】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理用問い合わせ配列生成部２０４は、問い合わせ配列を構成する各配列要素のバリエーションを、並列処理用問い合わせ配列の対応する各配列要素が包含するように、並列処理用問い合わせ配列を生成するように構成してもよい。
【０１４６】
この構成によれば、並列処理用問い合わせ配列は、問い合わせ配列を構成する各配列要素のバリエーションを対応する各配列要素において包含するため、問い合わせ配列の各配列要素のバリエーションを一本化して検索対象データベース１０２に投げかけることにより、１次候補配列のスクリーニングを行うことができる。そのため、並列処理部３００において、問い合わせ配列の各配列要素のバリエーションを漏れなく検索しながら、１次候補配列の抽出を高速化することができる。
【０１４７】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の問い合わせ配列はアミノ酸配列であってもよく、上記の並列処理用問い合わせ配列生成部２０４は、並列処理用問い合わせ配列として、アミノ酸配列に対応する塩基配列を表しており塩基配列の各塩基を所定長の単位ビット列で構成した並列処理用問い合わせビット列を生成するように設けられてもよく、上記の並列処理用問い合わせビット列は、アミノ酸残基を形成するための各塩基のバリエーションを単位ビット列が包含するように生成されてもよい。
【０１４８】
この構成によれば、並列処理用問い合わせビット列は、問い合わせ配列のアミノ酸配列に対応する塩基配列を表しており、塩基配列の各塩基に対応する所定長の単位ビット列で構成されているため、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを一本化することができる。そして、並列処理部３００において、このように一本化された並列処理用問い合わせビット列を検索対象データベースに投げかけることにより、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを漏れなく検索しながら、１次候補配列の抽出を高速化することができる。
【０１４９】
本実施形態に係る生物学的配列情報検索装置１００において、上記の１次候補配列抽出部３０２は、並列処理用問い合わせビット列と、検索対象データベースにおける検索対象のアミノ酸配列に対応する検索対象ビット列とを論理演算することにより配列マッチングを行うように構成してもよい。
【０１５０】
この構成によれば、並列処理用問い合わせビット列と、検索対象ビット列とを論理演算するため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００において、１次候補配列の抽出を高速化することができる。
【０１５１】
本実施形態に係る生物学的配列情報検索装置１００において、上記の並列処理部３００は、同一の素子に設けられている複数の演算器５０４を含み、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切って、複数の演算器５０４のそれぞれに割り振ることにより、並列処理用問い合わせ配列と検索対象データベース１０２との間で、配列マッチングを並列処理的に行うように構成されてもよい。なお、これらの複数の演算器５０４は、互いに同一の素子に設けられていてもよく、互いに個別の素子に設けられていてもよい。
【０１５２】
この構成によれば、並列処理部３００において、複数の演算器を用いて、検索対象データベース１０２中の生物学的配列情報を複数の所定長の配列情報に区切って、複数の演算器のそれぞれに割り振るため、簡単な論理演算を大量かつ高速に処理することを得意とする並列処理部３００の複数の演算器５０４において、それぞれ割り振られた配列情報から１次候補配列を高速に抽出することができる。
【０１５３】
本実施形態に係る生物学的配列情報検索装置１００において、上記の複数の演算器５０４のうち、互いに隣接する所定長の配列情報を割り振られた演算器５０４同士は、所定長の配列情報を互いに参照可能に構成されてもよい。
【０１５４】
この構成によれば、互いに隣接する所定長の配列情報を割り振られた演算器５０４同士は、所定長の配列情報を互いに参照可能であるため、これらの複数の演算器５０４は、複数の演算器５０４にまたがって割り振られている配列情報（割り振られた配列情報の区切り目にまたがって、存在する配列情報）からも、１次候補配列を抽出することができる。そのため、複数の演算器５０４に対して、区切り目にまたがって存在する配列情報を重複して割り振る必要が無いので、複数の演算器に割り振られた配列情報の区切り目にまたがる配列情報からも、１次候補配列を高速かつ精度よく抽出することができる。
【０１５５】
また、本実施形態に係る生物学的配列情報検索装置１００において、上記の２次候補配列抽出部２１０は、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するように構成されてもよい。
【０１５６】
この構成によれば、２次候補配列抽出部２１０は、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するため、上述のように、問い合わせ配列のアミノ酸配列に対応する塩基配列のバリエーションを一本化して並列処理用問い合わせ配列を生成した場合に、並列処理用問い合わせ配列に紛れ込むノイズ配列由来の１次候補配列を効率的に除去して２次候補配列を抽出することができる。
【０１５７】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【０１５８】
例えば、上記実施の形態では、１次候補配列抽出部３０２は、並列処理用問い合わせ配列にマッチングする１次候補配列を抽出する構成としたが、特に限定する意図はなく、例えば、並列処理用問い合わせ配列にマッチングする１次候補配列の検索対象データベース１０２中の座標を抽出する構成としてもよい。
【０１５９】
このようにすれば、並列処理部３００から中央処理部２００に返す１次候補配列の配列情報の容量を、単なる１次候補配列の座標の容量に低減することができるため、生物学的配列情報検索装置１００の処理速度をさらに向上することができる。
【０１６０】
同様に、上記実施の形態では、２次候補配列抽出部２１０は、問い合わせ配列と１次候補配列との間で、配列マッチングを行う構成としたが、特に限定する意図はなく、例えば、問い合わせ配列と、検索対象データベース１０２中の１次候補配列の座標の近傍領域との間で、配列マッチングを行う構成としてもよい。
【０１６１】
このようにしても、並列処理部３００から中央処理部２００に返す１次候補配列の配列情報の容量を、単なる１次候補配列の座標の容量に低減することができるため、生物学的配列情報検索装置１００の処理速度をさらに向上することができる。
【０１６２】
また、上記実施の形態では、中央処理部２００および並列処理部３００は別個の素子に設けられているが、特に限定する意図はなく、中央処理部２００および並列処理部３００は同一の素子に設けられていてもよい。
【０１６３】
この場合にも、並列処理部３００では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部２００では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができるという作用効果は同様だからである。
【０１６４】
また、上記実施の形態では、２次候補配列抽出部２１０において、問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出する構成としたが、特に限定する趣旨ではなく、例えば、問い合わせ配列に対して所定の条件をすべて満たす形でマッチングする２次候補配列を抽出してもよい。
【０１６５】
この場合には、例えば、２次候補配列抽出部２１０において、問い合わせ配列の全長に対してＢＬＡＳＴやＦＡＳＴなどをかけることにより、完全一致でなくても相同性の高い２次候補配列を抽出することができる。
【０１６６】
また、上記実施の形態では、問い合わせ配列として、アミノ酸配列を例に挙げたが、特に限定する趣旨ではなく、例えば、塩基配列（ＤＮＡ配列およびＲＮＡ配列）や糖鎖配列なども好適に用いることができる。
【０１６７】
いずれの場合にも、並列処理部３００では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部２００では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができるという作用効果は同様だからである。
【０１６８】
また、上記実施の形態では、問い合わせ配列を４ビット単位の単位ビット列からなる問い合わせビット列に変換したが、特に限定する趣旨ではなく、例えば、２ビット、８ビット、１６ビット、３２ビット、６４ビットなどの任意のビット数からなる問い合わせビット配列に変換してもよい。
【０１６９】
いずれにしても、問い合わせ配列を問い合わせビット列に変換して、１次スクリーニングにおける論理演算を効率化できる作用効果は同様だからである。
【０１７０】
また、上記実施の形態では、検索対象データベース１０２をゲノムデータベースとしたが、特に限定する趣旨ではなく、例えば、ＰＤＢ、ＳＷＩＳＳ ＰＲＯＴなどのプロテインデータベースや、糖鎖データベースなども好適に用いうる。
【０１７１】
いずれにしても、並列処理部３００では、並列処理用問い合わせ配列に対応する１次候補配列を高速に抽出し、中央処理部２００では、問い合わせ配列に対応する２次候補配列を精度よく抽出することができるという作用効果は同様だからである。
【０１７２】
また、上記実施の形態では、３５２個のＰＥを備えるＳＩＭＤ２０を並列処理部３００として用いたが、特に限定する趣旨ではなく、ＰＥの数は２以上であれば変動してもよく、ＳＩＭＤ２０以外の並列処理装置を用いてもよい。
【０１７３】
例えば、近年開発された、ＩＮＴＥＬ（登録商標）のＣＯＲＥ ＤＵＯ（登録商標）や、ＳＯＮＹ（登録商標）のＣＥＬＬ（登録商標）なども用いることができる。いずれも、コア数２、コア数９、とコア数は少ないが、並列処理が可能な点では、ＳＩＭＤ２０と同様であるためである。
【産業上の利用可能性】
【０１７４】
以上のように、本発明にかかる生物学的な配列情報の検索装置は、大量の生物学的な配列情報を格納している検索対象データベースから、目的の生物学的な配列情報を高速かつ精度よく検索することができるという効果を有し、生物学的な配列情報の検索装置、検索方法および検索プログラム等として有用である。
【図面の簡単な説明】
【０１７５】
【図１】実施の形態に係る生物学的配列情報検索装置の構成を説明するための機能ブロック図である。
【図２】実施の形態に係る生物学的配列情報検索装置を構成する個別の素子を説明するための機能ブロック図である。
【図３】実施の形態に係る生物学的配列情報検索装置を構成する個別の素子の機能の概要を説明するための概念図である。
【図４】実施の形態における中央処理部および並列処理部の内部構成を説明するため機能ブロック図である。
【図５】実施の形態に係る生物学的配列情報検索装置の動作を説明するためのフローチャートである。
【図６】実施の形態における並列処理用問い合わせ配列生成部の内部構成を説明するため機能ブロック図である。
【図７】実施の形態における並列処理用問い合わせ配列生成部の機能の概要を説明するための概念図である。
【図８】実施の形態における並列処理用問い合わせ配列生成部の動作を説明するためのフローチャートである。
【図９】実施の形態における１次候補配列抽出部および１次候補配列記憶部の内部構成を説明するため機能ブロック図である。
【図１０】実施の形態における１次候補配列抽出部および１次候補配列記憶部の機能の概要を説明するための概念図である。
【図１１】実施の形態における１次候補配列抽出部および１次候補配列記憶部の動作を説明するためのフローチャートである。
【図１２】実施の形態における２次候補配列抽出部の内部構成を説明するため機能ブロック図である。
【図１３】実施の形態における２次候補配列抽出部の動作を説明するためのフローチャートである。
【符号の説明】
【０１７６】
１０ ＣＰＵ
２０ ＳＩＭＤ
２２ ＰＥ
３０ バス
４０ ゲノムデータベース
１００ 生物学的配列情報検索装置
１０２ 検索対象データベース
１０４ 画像表示装置
１０６ 操作部
１０８ ＰＣ
１１０ サーバ
１１２ 外部ネットワーク
１１４ プリンタ
１１６ 外部ネットワーク
１１８ サーバ
１２０ ＰＣ
１２２ 出力部
２００ 中央処理部
２０２ 問い合わせ配列取得部
２０４ 並列処理用問い合わせ配列生成部
２０６ 並列処理用問い合わせ配列記憶部
２０８ 問い合わせ配列記憶部
２１０ ２次候補配列抽出部
２１２ ２次候補配列記憶部
３００ 並列処理部
３０２ １次候補配列抽出部
３０４ １次候補配列記憶部
４０２ 部分配列生成部
４０４ 部分配列記憶部
４０６ 配列特異性指標計算部
４０８ 配列特異性指標記憶部
４１０ 部分配列抽出部
４１６ ビット変換部
４１４ コドン変換部
５０２ データ割振部
５０４ 演算器
５０６ データ割振部
５０８ 所定長検索対象データ記憶部
５１０ 所定長区切部
５１２ 検索対象データ取得部
５１４ 記憶部
６０２ １次候補配列取得部
６０４ 完全一致配列抽出部
【特許請求の範囲】
【請求項１】
生物学的配列情報に関する検索対象データベースとの間で通信可能に構成されている生物学的配列情報検索装置であって、
中央処理部と、前記中央処理部とは別個の素子に設けられている並列処理部と、を備え、
前記中央処理部は、
生物学的情報についての問い合わせ配列を取得する問い合わせ配列取得部と、
前記問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部と、
を含み、
前記並列処理部は、前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを行い、前記並列処理用問い合わせ配列にマッチングする１次候補配列または該１次候補配列の前記検索対象データベース中の座標を抽出する１次候補配列抽出部を含み、
さらに、
前記中央処理部は、
前記問い合わせ配列と、前記１次候補配列または前記検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、前記問い合わせ配列にマッチングする２次候補配列を抽出する２次候補配列抽出部と、
前記２次候補配列に基づく検索結果を出力する出力部と、
を含む、
ことを特徴とする生物学的配列情報検索装置。
【請求項２】
請求項１記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、
前記問い合わせ配列に含まれる複数の所定長の部分配列について、該部分配列の配列特異性に基づく配列特異性指標を計算する配列特異性指標計算部と、
前記複数の部分配列の中から、前記配列特異性指標が所定の閾値以上である部分配列を抽出する部分配列抽出部と、
を含む、
ことを特徴とする生物学的配列情報検索装置。
【請求項３】
請求項１または２に記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、前記並列処理用問い合わせ配列を、テキスト配列およびビット配列の間で変換するビット変換部を含む
ことを特徴とする生物学的配列情報検索装置。
【請求項４】
請求項１乃至３いずれかに記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、前記問い合わせ配列を、アミノ酸配列および塩基配列の間で変換するコドン変換部を含む
ことを特徴とする生物学的配列情報検索装置。
【請求項５】
請求項１乃至４いずれかに記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、
前記問い合わせ配列を構成する各配列要素のバリエーションを、前記並列処理用問い合わせ配列の対応する各配列要素が包含するように、前記並列処理用問い合わせ配列を生成する
ことを特徴とする生物学的配列情報検索装置。
【請求項６】
請求項５記載の生物学的配列情報検索装置において、
前記問い合わせ配列はアミノ酸配列であり、
前記並列処理用問い合わせ配列生成部は、前記並列処理用問い合わせ配列として、前記アミノ酸配列に対応する塩基配列を表しており該塩基配列の各塩基を所定長の単位ビット列で構成した並列処理用問い合わせビット列を生成するように設けられ、
前記並列処理用問い合わせビット列は、アミノ酸残基を形成するための各塩基のバリエーションを前記単位ビット列が包含するように生成される
ことを特徴とする生物学的配列情報検索装置。
【請求項７】
請求項６記載の生物学的配列情報検索装置において、
前記１次候補配列抽出部は、
前記並列処理用問い合わせビット列と、前記検索対象データベースにおける検索対象のアミノ酸配列に対応する検索対象ビット列とを論理演算することにより配列マッチングを行う
ことを特徴とする生物学的配列情報検索装置。
【請求項８】
請求項１乃至７いずれかに記載の生物学的配列情報検索装置において、
前記並列処理部は、
同一の素子に設けられている複数の演算器を含み、
前記検索対象データベース中の生物学的配列情報を複数の所定長の配列情報に区切って、前記複数の演算器のそれぞれに割り振ることにより、前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを並列処理的に行うように構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項９】
請求項８記載の生物学的配列情報検索装置において、
前記複数の演算器のうち、互いに隣接する前記所定長の配列情報を割り振られた演算器同士は、前記所定長の配列情報を互いに参照可能に構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項１０】
請求項１乃至９いずれかに記載の生物学的配列情報検索装置において、
前記２次候補配列抽出部は、前記問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するように構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項１１】
生物学的配列情報に関する検索対象データベースとの間で通信可能に構成されている生物学的配列情報検索装置であって、
中央処理部と、並列処理部と、を備え、
前記中央処理部は、
生物学的情報についての問い合わせ配列を取得する問い合わせ配列取得部と、
前記問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部と、
を含み、
前記並列処理部は、前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを行い、前記並列処理用問い合わせ配列にマッチングする１次候補配列または該１次候補配列の前記検索対象データベース中の座標を抽出する１次候補配列抽出部を含み、
さらに、
前記中央処理部は、
前記問い合わせ配列と、前記１次候補配列または前記検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、前記問い合わせ配列にマッチングする２次候補配列を抽出する２次候補配列抽出部と、
前記２次候補配列に基づく検索結果を出力する出力部と、
を含む、
ことを特徴とする生物学的配列情報検索装置。
【請求項１２】
請求項１１記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、
前記問い合わせ配列に含まれる複数の所定長の部分配列について、該部分配列の配列特異性に基づく配列特異性指標を計算する配列特異性指標計算部と、
前記複数の部分配列の中から、前記配列特異性指標が所定の閾値以上である部分配列を抽出する部分配列抽出部と、
を含む、
ことを特徴とする生物学的配列情報検索装置。
【請求項１３】
請求項１１または１２に記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、前記並列処理用問い合わせ配列を、テキスト配列およびビット配列の間で変換するビット変換部を含む
ことを特徴とする生物学的配列情報検索装置。
【請求項１４】
請求項１１乃至１３いずれかに記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、前記問い合わせ配列を、アミノ酸配列および塩基配列の間で変換するコドン変換部を含む
ことを特徴とする生物学的配列情報検索装置。
【請求項１５】
請求項１１乃至１４いずれかに記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、
前記問い合わせ配列を構成する各配列要素のバリエーションを、前記並列処理用問い合わせ配列の対応する各配列要素が包含するように、前記並列処理用問い合わせ配列を生成する
ことを特徴とする生物学的配列情報検索装置。
【請求項１６】
請求項１５記載の生物学的配列情報検索装置において、
前記問い合わせ配列はアミノ酸配列であり、
前記並列処理用問い合わせ配列生成部は、前記並列処理用問い合わせ配列として、前記アミノ酸配列に対応する塩基配列を表しており該塩基配列の各塩基を所定長の単位ビット列で構成した並列処理用問い合わせビット列を生成するように設けられ、
前記並列処理用問い合わせビット列は、アミノ酸残基を形成するための各塩基のバリエーションを前記単位ビット列が包含するように生成される
ことを特徴とする生物学的配列情報検索装置。
【請求項１７】
請求項１６記載の生物学的配列情報検索装置において、
前記１次候補配列抽出部は、
前記並列処理用問い合わせビット列と、前記検索対象データベースにおける検索対象のアミノ酸配列に対応する検索対象ビット列とを論理演算することにより配列マッチングを行う
ことを特徴とする生物学的配列情報検索装置。
【請求項１８】
請求項１１乃至１７いずれかに記載の生物学的配列情報検索装置において、
前記並列処理部は、
複数の演算器を含み、
前記検索対象データベース中の生物学的配列情報を複数の所定長の配列情報に区切って、前記複数の演算器のそれぞれに割り振ることにより、前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを並列処理的に行うように構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項１９】
請求項１８記載の生物学的配列情報検索装置において、
前記複数の演算器のうち、互いに隣接する前記所定長の配列情報を割り振られた演算器同士は、前記所定長の配列情報を互いに参照可能に構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項２０】
請求項１１乃至１９いずれかに記載の生物学的配列情報検索装置において、
前記２次候補配列抽出部は、前記問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するように構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項２１】
生物学的配列情報に関する検索対象データベースを検索する生物学的配列情報検索方法であって、
生物学的情報についての問い合わせ配列に基づいて並列処理用問い合わせ配列を生成するステップと、
前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを行い、前記並列処理用問い合わせ配列にマッチングする１次候補配列または該１次候補配列の前記検索対象データベース中の座標を抽出するステップと、
前記問い合わせ配列と、前記１次候補配列または前記検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、前記問い合わせ配列にマッチングする２次候補配列を抽出するステップと、
を含む、
ことを特徴とする生物学的配列情報検索方法。
【請求項２２】
生物学的配列情報に関する検索対象データベースの検索をコンピュータに実行させるための生物学的配列情報検索プログラムであって、
生物学的情報についての問い合わせ配列に基づいて並列処理用問い合わせ配列を生成するステップと、
前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを行い、前記並列処理用問い合わせ配列にマッチングする１次候補配列または該１次候補配列の前記検索対象データベース中の座標を抽出するステップと、
前記問い合わせ配列と、前記１次候補配列または前記検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、前記問い合わせ配列にマッチングする２次候補配列を抽出するステップと、
をコンピュータに実行させる
ことを特徴とする生物学的配列情報検索プログラム。
【請求項１】
生物学的配列情報に関する検索対象データベースとの間で通信可能に構成されている生物学的配列情報検索装置であって、
中央処理部と、前記中央処理部とは別個の素子に設けられている並列処理部と、を備え、
前記中央処理部は、
生物学的情報についての問い合わせ配列を取得する問い合わせ配列取得部と、
前記問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部と、
を含み、
前記並列処理部は、前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを行い、前記並列処理用問い合わせ配列にマッチングする１次候補配列または該１次候補配列の前記検索対象データベース中の座標を抽出する１次候補配列抽出部を含み、
さらに、
前記中央処理部は、
前記問い合わせ配列と、前記１次候補配列または前記検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、前記問い合わせ配列にマッチングする２次候補配列を抽出する２次候補配列抽出部と、
前記２次候補配列に基づく検索結果を出力する出力部と、
を含む、
ことを特徴とする生物学的配列情報検索装置。
【請求項２】
請求項１記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、
前記問い合わせ配列に含まれる複数の所定長の部分配列について、該部分配列の配列特異性に基づく配列特異性指標を計算する配列特異性指標計算部と、
前記複数の部分配列の中から、前記配列特異性指標が所定の閾値以上である部分配列を抽出する部分配列抽出部と、
を含む、
ことを特徴とする生物学的配列情報検索装置。
【請求項３】
請求項１または２に記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、前記並列処理用問い合わせ配列を、テキスト配列およびビット配列の間で変換するビット変換部を含む
ことを特徴とする生物学的配列情報検索装置。
【請求項４】
請求項１乃至３いずれかに記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、前記問い合わせ配列を、アミノ酸配列および塩基配列の間で変換するコドン変換部を含む
ことを特徴とする生物学的配列情報検索装置。
【請求項５】
請求項１乃至４いずれかに記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、
前記問い合わせ配列を構成する各配列要素のバリエーションを、前記並列処理用問い合わせ配列の対応する各配列要素が包含するように、前記並列処理用問い合わせ配列を生成する
ことを特徴とする生物学的配列情報検索装置。
【請求項６】
請求項５記載の生物学的配列情報検索装置において、
前記問い合わせ配列はアミノ酸配列であり、
前記並列処理用問い合わせ配列生成部は、前記並列処理用問い合わせ配列として、前記アミノ酸配列に対応する塩基配列を表しており該塩基配列の各塩基を所定長の単位ビット列で構成した並列処理用問い合わせビット列を生成するように設けられ、
前記並列処理用問い合わせビット列は、アミノ酸残基を形成するための各塩基のバリエーションを前記単位ビット列が包含するように生成される
ことを特徴とする生物学的配列情報検索装置。
【請求項７】
請求項６記載の生物学的配列情報検索装置において、
前記１次候補配列抽出部は、
前記並列処理用問い合わせビット列と、前記検索対象データベースにおける検索対象のアミノ酸配列に対応する検索対象ビット列とを論理演算することにより配列マッチングを行う
ことを特徴とする生物学的配列情報検索装置。
【請求項８】
請求項１乃至７いずれかに記載の生物学的配列情報検索装置において、
前記並列処理部は、
同一の素子に設けられている複数の演算器を含み、
前記検索対象データベース中の生物学的配列情報を複数の所定長の配列情報に区切って、前記複数の演算器のそれぞれに割り振ることにより、前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを並列処理的に行うように構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項９】
請求項８記載の生物学的配列情報検索装置において、
前記複数の演算器のうち、互いに隣接する前記所定長の配列情報を割り振られた演算器同士は、前記所定長の配列情報を互いに参照可能に構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項１０】
請求項１乃至９いずれかに記載の生物学的配列情報検索装置において、
前記２次候補配列抽出部は、前記問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するように構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項１１】
生物学的配列情報に関する検索対象データベースとの間で通信可能に構成されている生物学的配列情報検索装置であって、
中央処理部と、並列処理部と、を備え、
前記中央処理部は、
生物学的情報についての問い合わせ配列を取得する問い合わせ配列取得部と、
前記問い合わせ配列に基づいて並列処理用問い合わせ配列を生成する並列処理用問い合わせ配列生成部と、
を含み、
前記並列処理部は、前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを行い、前記並列処理用問い合わせ配列にマッチングする１次候補配列または該１次候補配列の前記検索対象データベース中の座標を抽出する１次候補配列抽出部を含み、
さらに、
前記中央処理部は、
前記問い合わせ配列と、前記１次候補配列または前記検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、前記問い合わせ配列にマッチングする２次候補配列を抽出する２次候補配列抽出部と、
前記２次候補配列に基づく検索結果を出力する出力部と、
を含む、
ことを特徴とする生物学的配列情報検索装置。
【請求項１２】
請求項１１記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、
前記問い合わせ配列に含まれる複数の所定長の部分配列について、該部分配列の配列特異性に基づく配列特異性指標を計算する配列特異性指標計算部と、
前記複数の部分配列の中から、前記配列特異性指標が所定の閾値以上である部分配列を抽出する部分配列抽出部と、
を含む、
ことを特徴とする生物学的配列情報検索装置。
【請求項１３】
請求項１１または１２に記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、前記並列処理用問い合わせ配列を、テキスト配列およびビット配列の間で変換するビット変換部を含む
ことを特徴とする生物学的配列情報検索装置。
【請求項１４】
請求項１１乃至１３いずれかに記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、前記問い合わせ配列を、アミノ酸配列および塩基配列の間で変換するコドン変換部を含む
ことを特徴とする生物学的配列情報検索装置。
【請求項１５】
請求項１１乃至１４いずれかに記載の生物学的配列情報検索装置において、
前記並列処理用問い合わせ配列生成部は、
前記問い合わせ配列を構成する各配列要素のバリエーションを、前記並列処理用問い合わせ配列の対応する各配列要素が包含するように、前記並列処理用問い合わせ配列を生成する
ことを特徴とする生物学的配列情報検索装置。
【請求項１６】
請求項１５記載の生物学的配列情報検索装置において、
前記問い合わせ配列はアミノ酸配列であり、
前記並列処理用問い合わせ配列生成部は、前記並列処理用問い合わせ配列として、前記アミノ酸配列に対応する塩基配列を表しており該塩基配列の各塩基を所定長の単位ビット列で構成した並列処理用問い合わせビット列を生成するように設けられ、
前記並列処理用問い合わせビット列は、アミノ酸残基を形成するための各塩基のバリエーションを前記単位ビット列が包含するように生成される
ことを特徴とする生物学的配列情報検索装置。
【請求項１７】
請求項１６記載の生物学的配列情報検索装置において、
前記１次候補配列抽出部は、
前記並列処理用問い合わせビット列と、前記検索対象データベースにおける検索対象のアミノ酸配列に対応する検索対象ビット列とを論理演算することにより配列マッチングを行う
ことを特徴とする生物学的配列情報検索装置。
【請求項１８】
請求項１１乃至１７いずれかに記載の生物学的配列情報検索装置において、
前記並列処理部は、
複数の演算器を含み、
前記検索対象データベース中の生物学的配列情報を複数の所定長の配列情報に区切って、前記複数の演算器のそれぞれに割り振ることにより、前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを並列処理的に行うように構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項１９】
請求項１８記載の生物学的配列情報検索装置において、
前記複数の演算器のうち、互いに隣接する前記所定長の配列情報を割り振られた演算器同士は、前記所定長の配列情報を互いに参照可能に構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項２０】
請求項１１乃至１９いずれかに記載の生物学的配列情報検索装置において、
前記２次候補配列抽出部は、前記問い合わせ配列の全長に完全一致の形でマッチングする２次候補配列を抽出するように構成されている
ことを特徴とする生物学的配列情報検索装置。
【請求項２１】
生物学的配列情報に関する検索対象データベースを検索する生物学的配列情報検索方法であって、
生物学的情報についての問い合わせ配列に基づいて並列処理用問い合わせ配列を生成するステップと、
前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを行い、前記並列処理用問い合わせ配列にマッチングする１次候補配列または該１次候補配列の前記検索対象データベース中の座標を抽出するステップと、
前記問い合わせ配列と、前記１次候補配列または前記検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、前記問い合わせ配列にマッチングする２次候補配列を抽出するステップと、
を含む、
ことを特徴とする生物学的配列情報検索方法。
【請求項２２】
生物学的配列情報に関する検索対象データベースの検索をコンピュータに実行させるための生物学的配列情報検索プログラムであって、
生物学的情報についての問い合わせ配列に基づいて並列処理用問い合わせ配列を生成するステップと、
前記並列処理用問い合わせ配列と前記検索対象データベースとの間で、配列マッチングを行い、前記並列処理用問い合わせ配列にマッチングする１次候補配列または該１次候補配列の前記検索対象データベース中の座標を抽出するステップと、
前記問い合わせ配列と、前記１次候補配列または前記検索対象データベース中の前記１次候補配列の座標の近傍領域との間で、配列マッチングを行い、前記問い合わせ配列にマッチングする２次候補配列を抽出するステップと、
をコンピュータに実行させる
ことを特徴とする生物学的配列情報検索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００７−２５７０２０（Ｐ２００７−２５７０２０Ａ）
【公開日】平成１９年１０月４日（２００７．１０．４）
【国際特許分類】
【出願番号】特願２００６−７６９１３（Ｐ２００６−７６９１３）
【出願日】平成１８年３月２０日（２００６．３．２０）
【新規性喪失の例外の表示】特許法第３０条第３項適用申請有り 博覧会名 ＣｅＢＩＴ ２００６ 主催者名 株式会社ドイツ見本市 開催日 ２００６年３月９日〜２００６年３月１５日
【出願人】（３０３０２６８８８）株式会社バイオマティクス (2)
【Ｆターム（参考）】
【公開日】平成１９年１０月４日（２００７．１０．４）
【国際特許分類】
【出願日】平成１８年３月２０日（２００６．３．２０）
【新規性喪失の例外の表示】特許法第３０条第３項適用申請有り 博覧会名 ＣｅＢＩＴ ２００６ 主催者名 株式会社ドイツ見本市 開催日 ２００６年３月９日〜２００６年３月１５日
【出願人】（３０３０２６８８８）株式会社バイオマティクス (2)
【Ｆターム（参考）】
[ Back to top ]