(57)【要約】【課題】塩基配列、アミノ酸配列等の生物学的配列情報の解析処理を高速化する。【解決手段】コンパレータ２８は、配列情報を参照配列と並列照合処理により比較する。配列処理制御部３０は、コンパレータ２８を制御し、参照配列をコンパレータ２８に供給し、比較結果をコンパレータ２８から取得する。配列処理制御部３０は、参照配列の一部に相当する部位にワイルドカードが設定された並列照合処理をコンパレータ２８に行わせて、配列情報の処理結果を得る。配列処理制御部３０は、一部にワイルドカードが設定された参照配列をコンパレータに提供する。ワイルドカードが設定された参照配列を使って、類似性検索が行われる。アミノ酸種類に対応する塩基が不特定な部位にワイルドカードが設定された参照配列を使ってアミノ酸配列コード領域が検索される。【選択図】  図４
2004234297.tif 000002
【特許請求の範囲】
【請求項１】
塩基配列、アミノ酸配列等の多数の配列要素の配列情報を処理する生物学的配列情報処理装置であって、
前記配列情報が書き込まれ、前記配列情報を参照配列と並列照合処理により比較するコンパレータと、
前記コンパレータを制御して、前記参照配列を前記コンパレータに供給し、比較結果を前記コンパレータから取得する制御手段と、
を含み、
前記制御手段は、参照配列の一部に相当する部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせて、前記配列情報の処理結果を得ることを特徴とする生物学的配列情報処理装置。
【請求項２】
請求項１に記載の生物学的配列情報処理装置であって、
前記制御手段は、参照配列の一部に相当する部位にワイルドカードが設定された並列照合処理を類似性検索のために前記コンパレータに行わせることを特徴とする生物学的配列情報処理装置。
【請求項３】
請求項１に記載の生物学的配列情報処理装置であって、
前記制御手段は、アミノ酸配列の検索を前記コンパレータに行わせるものであり、アミノ酸種類に対応する塩基が不特定な部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせることを特徴とする生物学的配列情報処理装置。
【請求項４】
請求項１に記載の生物学的配列情報処理装置であって、
前記制御手段は、コード領域ホモログ検索のために、３番目の塩基に相当する部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせることを特徴とする生物学的配列情報処理装置。
【請求項５】
塩基配列、アミノ酸配列等の多数の配列要素の配列情報を処理する生物学的配列情報処理方法であって、
前記配列情報を参照配列と並列照合処理により比較するコンパレータへと前記配列情報を書き込む書込ステップと、
前記コンパレータへ前記参照情報を供給して、配列情報と参照配列を比較させる並列照合ステップと、
を含み、
前記並列照合ステップは、参照配列の一部に相当する部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせることを特徴とする生物学的配列情報処理方法。
【請求項６】
請求項５に記載の生物学的配列情報処理方法であって、
参照配列の一部に相当する部位にワイルドカードが設定された並列照合処理を類似性検索のために前記コンパレータに行わせることを特徴とする生物学的配列情報処理方法。
【請求項７】
請求項５に記載の生物学的配列情報処理方法であって、
前記並列照合ステップは、アミノ酸配列の検索を前記コンパレータに行わせるものであり、アミノ酸種類に対応する塩基が不特定な部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせることを特徴とする生物学的配列情報処理方法。
【請求項８】
請求項５に記載の生物学的配列情報処理方法であって、
コード領域ホモログ検索のために、３番目の塩基に相当する部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせることを特徴とする生物学的配列情報処理方法。
【請求項９】
塩基配列、アミノ酸配列等の多数の配列要素の配列情報を処理をコンピュータに実行させるプログラムであって、
前記プログラムは、
前記配列情報を参照配列と並列照合処理により比較するコンパレータへと前記配列情報を書き込む書込ステップと、
前記コンパレータへ前記参照情報を供給して、配列情報と参照配列を比較させる並列照合ステップであって、参照配列の一部に相当する部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせるステップと、
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１０】
請求項９に記載のプログラムであって、
参照配列の一部に相当する部位にワイルドカードが設定された並列照合処理を類似性検索のために前記コンパレータに行わせる処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１１】
請求項９に記載のプログラムであって、
前記並列照合ステップでは、アミノ酸配列の検索を前記コンパレータに行わせるために、アミノ酸種類に対応する塩基が不特定な部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせる処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１２】
請求項９に記載のプログラムであって、
コード領域ホモログ検索のために、３番目の塩基に相当する部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせる処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１３】
請求項９〜１２のいずれかに記載のプログラムを格納した、コンピュータにて読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、塩基配列、アミノ酸配列等の生物学的な配列情報を解析のために処理する方法および装置に関し、特に、処理の高速化に関する。
【０００２】
【従来の技術】
多くの高等真核生物のゲノム配列が明らかになりつつある中で、高速に配列を探索できるコンピュータの需要が増している。このようなバイオインフォマティクスの分野では、配列情報から特徴的な部位を検索する処理が頻繁に行われる。例えば、ブラスト法は、従来、ギャップの挿入を行わずに局所的によく一致する部位を探索する。このような部位を高スコア断片と呼ぶ。そして、高スコア断片が前後に伸長される。
【０００３】
コンピュータを使った従来の配列解析手法については、例えば、非特許文献１、２に解説されている。
【０００４】
【非特許文献１】
「遺伝子とコンピュータ」（小長谷明彦、共立出版株式会社、２０００年１月２５日発行）
【０００５】
【非特許文献２】
「分子生物学のためのバイオインフォマティクス入門」（Ｓｅｔｕｂａｌ  ＪＣ，  Ｍｅｉｄａｎｉｓ  Ｊ、共立出版株式会社、２００１年１２月２０日発行）
【０００６】
【発明が解決しようとする課題】
これまでのｖｏｎ  Ｎｅｕｍａｎｎ型コンピュータ、要するに従来型の通常のコンピュータは、配列を数値アドレスによりＣＰＵレジスタ内に読み込み、レジスタ内で順次比較演算するという機構である。この機構では、時間計算量がＯ（ｍｎ）で表され、すなわち、時間計算量は、クエリ配列の長さｍと対象テキスト配列の長さｎに比例して増大するという制約がある。そのため、大規模ゲノム配列を処理するには、並列スーパーコンピュータを用いてもかなりの計算時間と費用を要するのが現状である。そこで、より小型のコンピュータで、より高速に大量の配列情報を処理できることが望まれる。
【０００７】
本発明は上記背景の下でなされたものであり、その目的は、配列情報の処理を高速化する装置および方法を提供することにある。
【０００８】
本発明の一つの目的は、類似性検索を高速で行うことが可能な装置および方法を提供することにある。
【０００９】
本発明の一つの目的は、アミノ酸配列を参照配列に設定してＤＮＡ配列検索を高速で行うことが可能な装置および方法を提供することにある。
【００１０】
本発明の一つの目的は、コード領域ホモログ検索を高速に行うことが可能な装置および方法を提供することにある。
【００１１】
本発明の一つの目的は、パーソナルコンピュータにて配列検索、処理にともなう複雑な連続操作を簡便かつ高速に行う装置および方法を提供することにある。
【００１２】
【課題を解決するための手段】
上記目的を達成するため、本発明の生物学的配列情報処理装置は、塩基配列、アミノ酸配列等の多数の配列要素の配列情報を処理する。本装置は、前記配列情報が書き込まれ、前記配列情報を参照配列と並列照合処理により比較するコンパレータと、前記コンパレータを制御して、前記参照配列を前記コンパレータに供給し、比較結果を前記コンパレータから取得する制御手段と、を含み、前記制御手段は、参照配列の一部に相当する部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせて、前記配列情報の処理結果を得る。好ましくは、前記制御手段は、一部にワイルドカードが設定された参照配列をコンパレータに提供する参照配列提供手段を含み、ワイルドカードを含んだ参照配列を使った並列照合処理をコンパレータに行わせる。
【００１３】
本発明によれば、ワイルドカードを使って、参照配列の一部が配列情報と一致するか否かを無視する検索を高速に行える。これにより、参照配列全体が一致するかどうかだけでは分からない情報が得られる。
【００１４】
好ましくは、前記制御手段は、参照配列の一部に相当する部位にワイルドカードが設定された並列照合処理を類似性検索のために前記コンパレータに行わせることを特徴とする生物学的配列情報処理装置。好ましくは、前記制御手段は、一部にワイルドカードを含んだ類似性検索用の参照配列を前記コンパレータに提供する。
【００１５】
従来のブラスト検索では、典型的には、１１の連続する塩基が参照配列として用いられる。これに対して、本発明では、例えば、７塩基＋ワイルドカード＋８塩基といった参照配列が使用可能である。これにより、途中の塩基の変異を許容した類似性検索を高速で行うことが可能になる。
【００１６】
好ましくは、前記制御手段は、アミノ酸配列の検索、より詳細には塩基配列上でのアミノ酸配列のコード領域の検索を前記コンパレータに行わせるものであり、アミノ酸種類に対応する塩基が不特定な部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせる。対象のアミノ酸配列に対応するコドン配列において塩基が特定されない部位にワイルドカードが設定される。好ましくは、前記制御手段は、ワイルドカードが設定された参照配列を、アミノ酸配列検索のための参照配列として前記コンパレータに提供する。
【００１７】
アミノ酸配列は、３塩基からなるコドンの配列でコードされる。各アミノ酸をコードするコドンは複数個あるので、特定のアミノ酸列をコードするＤＮＡの組み合わせは莫大な数となる。本発明では、例えば、「ＦＡＰＱＲＴＭ」を検索するために、「ｔｔ＊ｇｃ＊ｃｃ＊ｃａ＊＊ｇ＊ａｃ＊ａｔｇ」というように、塩基が不特定な部位にワイルドカード（＊）を設定することで、検索対象のアミノ酸配列の候補領域が求められる。アミノ酸配列の検索が簡単になり、高速化する。
【００１８】
好ましくは、前記制御手段は、コード領域ホモログ検索のために、３番目の塩基に相当する部位にワイルドカードが設定された並列照合処理を前記コンパレータに行わせる。好ましくは、前記制御手段は、コード領域ホモログ検索のために、３番目の塩基に相当する部位にワイルドカードが設定された参照配列を前記コンパレータに提供する。
【００１９】
ホモログのアミノ酸配列をコードする領域での当該読み枠においては第３番目の塩基は変異していることが多い。そこで、それに対応する並列照合処理を行うことによりホモログ検出率を上げることが可能である。このため、本発明では、３塩基目にワイルドカード（＊）を用いて、例えば、「ｔｔ＊ｔｇ＊ｃａ＊ａｃ＊＊ｃｃ」というような参照配列を作成し、検索を高速化する。
【００２０】
本発明の装置は、単独で配置されてもよい。本発明の装置は、ネットワークを経由してアクセスされるシステムを構成してもよい。分散配置された複数のコンピュータにより本発明の装置が実現されてもよい。制御するプログラムは、関数ライブラリとして提供され、使用者はそれら関数をインタープリタ型高級言語などの環境下で適切に組み合わせて、より複雑な実行命令列を構成することができる。
【００２１】
本発明は、上述の装置の態様には限定されない。本発明の別の態様は、例えば、配列情報処理方法である。また、本発明の別の態様は、例えば、上記処理方法をコンピュータに実現させるプログラムであり、また例えば、そのようなプログラムを記録した媒体である。
【００２２】
【発明の実施の形態】
上述したように、これまでのｖｏｎ  Ｎｅｕｍａｎｎ型コンピュータは配列を数値アドレスによりＣＰＵレジスタ内に読み込み、  レジスタ内で順次比較演算するという機構のため  時間計算量がＯ（ｍｎ）  であり、すなわち、クエリ配列の長さｍと対象テキスト配列の長さｎに比例して増大する。そのため、大規模ゲノム配列を処理するには、並列スーパーコンピュータを用いてもかなりの計算時間と費用を要する。
【００２３】
そこで、本実施の形態は、ｃｏｎｔｅｎｔ  ａｄｄｒｅｓｓａｂｌｅ  ｍｅｍｏｒｙ（ＣＡＭ）を用いることにより  Ｏ（１）マシン、すなわち，配列の長さに計算時間が依存しないハードウェアとその制御アルゴリズムを提供する。ＣＡＭとはストーレージビット単位の比較ロジックを有するメモリである。クエリ配列はＣＡＭ内の全てのテキストに対してブロードキャストされ、その場で比較が行われて、一致するテキスト位置が一挙にＣＰＵに対して戻される。すなわち、これは理想的  ｄａｔａ  ｐａｒａｌｌｅｌ  ｐｒｏｃｅｓｓｏｒ  （ＳＩＭＤ，  ｓｉｎｇｌｅ  ｉｎｓｔｒｕｃｔｉｏｎ  ｓｔｒｅａｍ，  ｍｕｌｔｉｐｌｅ  ｄａｔａ  ｓｔｒｅａｍ）として動作する。
【００２４】
さらにこの基本機構にワイルドカード検索機構を組み込むことにより検索の柔軟性が増し、さらにマスキング演算機構を組み込むことにより、各塩基において条件分岐演算を行うことが可能になる。
【００２５】
従来型コンピュータは、レジスタ内に配列を読み込んで（すなわち関数にデータを入力して）演算を行う。一方、本実施の形態の構成は、演算子（オペレータ）をブロードキャストすることによりオペランドである各塩基配列が存在するその場にて演算を同時に行って、演算結果をＣＰＵに対し一斉に報告させるという機構である（ｉｎ  ｓｉｔｕ  ｐｒｏｃｅｓｓｉｎｇ）。この機構はこれまでのｖｏｎ  Ｎｅｕｍａｎｎ型コンピュータでは実現できない機能の付加を提供する。これにより、例えば、従来のＢＬＡＳＴを質と速度の両面ではるかに凌駕する類似性検索が可能になるばかりではなく、数百万個以上の一致部位があるｒｅｐｅａｔ配列やＯＲＦサーチをゲノム規模で効果的に処理できる。
【００２６】
以下、本発明の好適な実施の形態を図面を参照して説明する。
【００２７】
本実施の形態では、配列情報の一形態である塩基配列が処理される。ただし、アミノ酸配列等の他の任意の生物学的配列情報にも本発明は適用可能である。
【００２８】
以下においては、本発明を分かりやすく説明するため、塩基配列を表現するのに通常用いられる文字「ａ、ｔ、ｃ、ｇ」を使用する。しかし、本発明の範囲内で、塩基等の要素を表すものであれば、他のコードが用いられてもよいことはもちろんである。
【００２９】
図１は、本実施の形態の生物学的配列情報処理装置を含んだコンピュータシステムを示している。このコンピュータシステム１０では、複数のクライアント１２と複数のコンパレータ１４がネットワーク１６を介して接続される。
【００３０】
クライアント１２は、パーソナルコンピュータで構成されており、ＣＰＵ、ＲＯＭ、ＲＡＭ、ＣＡＭ、ハードディスク、入力装置、出力装置および通信装置といった各種構成を含む。また、本システムは、インターネット上の生物学的配列データベースとネットワークを介して接続され、探索結果を手動もしくは自動的にそれらのデータベースと照合し、新たな操作を連続的に行う環境も含んでよい。
【００３１】
クライアント１２において、ハードディスクは、配列情報処理装置の機能を実現するためのプログラムを記憶している。このプログラムがＣＰＵにより実行される。また、ハードディスクは、解析対象の配列情報を記憶している。ＣＰＵは、ハードディスクから配列情報を取得する。配列情報は、他の構成から取得されてもよい。例えば、配列情報は、記録媒体装着部を介してＣＤ−ＲＯＭ、ＤＶＤ等の記録媒体から取得されてもよい。また、配列情報は、通信装置を介して取得されてもよい。通信装置は、インターネット等のネットワークから配列情報を取得してもよい。
【００３２】
入力装置は、キーボード、ポインティングデバイス等である。ユーザは、入力装置を操作して、各種の指示を入力し、また、配列情報処理装置が要求する情報等を入力する。
【００３３】
出力装置は、ディスプレイ、プリンタ等である。出力装置には、解析結果の情報が表示される。また、ディスプレイには、ユーザへの案内画面、例えば入力装置を操作するのに必要な画面が表示される。上述のように配列情報を通信装置で取得する場合には、通信装置を出力装置として機能させ、解析結果等の情報も通信装置を介して出力することが好適である。
【００３４】
クライアント１２は、コンパレータ１４に命令を出す。また、処理対象の配列情報等もクライアント１２からコンパレータ１４に供給される。コンパレータ１４は、クライアント１２からの命令に従って処理を行い、処理結果をクライアント１２に返す。１つのクライアント１２は、複数のコンパレータ１４に命令を出すことができる。
【００３５】
上述のように、クライアント１２の側でもソフトウエアが動作する。そして、コンパレータ１４の処理とクライアント１２の処理の両方で、ユーザが目的とする処理が達成される。
【００３６】
すなわち、図１のシステムでは、クライアント１２が、コンパレータ１４の制御手段として機能する。そして、コンパレータ１４とクライアント１２により本発明の生物学的配列情報処理装置が構成される。典型的には、複数のコンパレータ１４が、本発明の生物学的配列情報処理装置を構成するコンパレータとして機能する。処理対象の配列情報が膨大な長さを持っているとき、複数のコンパレータ１４に配列情報を処理させることが特に有効である。ただし、本発明の範囲内で、一つのコンパレータ１４が、本発明の生物学的配列情報処理装置を構成するコンパレータとして機能してもよい。
【００３７】
図２は、コンパレータ１４の構成を示している。コンパレータ１４は、複数のＣＡＭ１８、ＣＰＵ２０およびメモリ２２を有し、これらがバス２４で接続されている。本実施の形態では、図示のように、一つのコンパレータ１４に複数のＣＡＭ１８が設けられている。これは、膨大な長さの配列情報を高速に処理するためである。ただし、本発明の範囲内で、コンパレータ１４は一つのＣＡＭで構成されてもよい。
【００３８】
ＣＡＭ１８は、本発明の並列照合機能をもつ記憶装置の典型的かつ好適な一形態である。ＣＡＭは連想記憶装置ともいわれる。ＣＡＭは、名前、アドレス、相対位置ではなく、情報内容により記憶場所が識別されるデータ記憶装置であり、これにより高速なデータ検索ができる。ＣＡＭは、通常はインターネットのルータにて用いられている。
【００３９】
図３は、インターネットのルータにおけるＣＡＭの機能を示している。ＣＡＭは、ルーティングテーブルを記憶する。ルーティングテーブルは、複数のＩＰアドレスとルータ名を対応付ける。各ＩＰアドレスは、そのＩＰアドレスが付されたデータが転送されるべきルータ名と対応づけられる。照合データとしてＩＰアドレスが入力されたとき、ＣＡＭは、照合データと一致するＩＰアドレスを検索する。この検索は、並列処理にて行われる。そして、ＣＡＭは、照合データと一致するＩＰアドレスと対応付けられたルータ名を出力する。
【００４０】
このように、ＣＡＭは、照合データと被照合データの照合を並列処理にて行い、照合結果を出力することができる。この機能を本発明では並列照合機能という。一方、配列処理では、配列に関する多数のデータ比較が行われる。この種の処理にはＣＡＭの機能が適している。本発明はこの点に着目し、配列に関する多数のデータの比較をＣＡＭに行わせる。これにより、配列解析処理のうちで大きなウエイトを占める部分が、ＣＡＭにより大幅に高速化され、配列解析の高速化が可能となる。
【００４１】
さらに、ＣＡＭは、インターネットのルータ用の部品として普及しており、比較的安価に入手できる。また、通常のパーソナルコンピュータとの接続が容易な点でもＣＡＭは有利である。したがって、本発明によれば、通常はルータに用いられるＣＡＭの特性が配列情報の処理に適していることに着目し、ＣＡＭを使って配列情報処理装置を構成したことで、高速性という利点に加えて、低コストで容易に配列情報処理装置を提供できるという利点も得られる。
【００４２】
ＣＡＭは、並列照合機能をもつ記憶装置の典型的かつ好適な一形態である。並列照合機能をもつ他の記憶装置が適用されてもよく、同様の高速化が可能である。従来は大量のデータの比較をＲＡＭ上でソフトウエアによって実現していたのと比較して、大幅な高速化が可能となる。
【００４３】
本実施の形態においては、本発明を分かりやすく説明するため、通常のＣＡＭ等を表現する形式に従い、四角形の図に基づいて本発明を説明する。しかし、実際のＣＡＭ上での物理的なデータの位置は、図示のかたちには限定されないことはもちろんである。
【００４４】
図４は、配列情報処理装置の機能ブロック図である。図４において、コンパレータ２８は、図１のコンパレータ１４と対応する。ただし、既に述べたように、物理的には複数のコンパレータ１４が、図４のコンパレータ２８として機能してもよい。
【００４５】
また、図４において、配列処理制御部３０は、図１のクライアント１２に相当し、クライアント１２がプログラムを実行することにより実現される。配列処理制御部３０は、コンパレータを制御する制御手段に相当する。配列処理制御部３０は、配列情報取得部３２、被照合データ投入部３４、照合データ投入部３６、照合結果取得部３８、照合結果処理部４０、解析情報出力部４２を有する。
【００４６】
配列情報取得部３２は、解析対象の配列情報を取得する。配列情報は、上述のようにハードディスク等から取得される。被照合データ投入部３４は、コンパレータ２８に被照合データを投入する。被照合データはコンパレータ２８に記憶される。照合データ投入部３６は、照合データをコンパレータ２８に投入する。コンパレータ２８は、照合データと被照合データを照合し、照合結果を出力する。照合結果は、照合結果取得部３８により取得される。照合結果処理部４０は、照合結果に基づく各種判定等の配列解析のための処理を行う。解析情報出力部４２は、照合結果処理部４０によって得られた配列解析に関する情報を出力するための処理を行う。
【００４７】
また、照合データ投入部３６には、ワイルドカード設定部４４が設けられている。照合データ投入部３６は、ワイルドカード設定部４４の機能を用いて、ワイルドカードが設定された参照配列を、照合データとして、コンパレータ２８に提供する。
【００４８】
さらに、配列処理制御部３０は、マスク処理部４６を有する。マスク処理部４６は、照合結果処理部４０の指示に従い、コンパレータ２８に書き込まれた被照合データである配列情報の少なくとも一部にマスクをかける機能をもつ。マスクがかけられた部分は、配列要素（本実施の形態では塩基）が区別されない状態になる。後述するように、本実施の形態では、マスク処理部４６は、コンパレータ２８の比較結果に基づき、必要部位にマスクをかける。
【００４９】
図５は、ワイルドカードが設定された参照配列を示している。図中の塩基ａ、ｔ、ｇ、ｃは、アデニン、チミン、グアニンおよびシトシンである。また、＊はワイルドカードである。以下の説明では、適宜、ワイルドカードは、Ｄｏｎ’ｔ
Ｃａｒｅ  ｂｉｔ（以下、ＤＣｂｉｔ）とも呼ぶ。
【００５０】
ワイルドカードは、特定の位置のデータを無視したデータによって一致検索を行うためのものである。ワイルドカードは、無視されるべき文字の位置、または、文字そのものである。この無視により、配列が部分的に照合から外される。
【００５１】
なお、ワイルドカードは、被照合データに設定することも可能である。これによっても、ワイルドカードを使った並列照合処理が可能であり、このような構成も本発明に含まれてよい。被照合データへのワイルドカードの設定には、後述のマスクのビットを利用可能である。
【００５２】
図６は、マスク処理部４６によりマスクがかけられた配列を示している。図示のように、本実施の形態では、マスクを「ｏ」で表現する。ｏが付された部分は、ａ、ｃ、ｇ、ｔの塩基種別がなくなる。
【００５３】
図７は、配列情報が書き込まれたコンパレータの一部をより詳細に示している。図示のように、一つの塩基に対して３ビットが割り当てられる。そして、３ビットのうちの２ビットは、塩基の種類を表すために用いられる。すなわち、ａ、ｃ、ｇ、ｔの４種の塩基が、２ビットを用いて表される。残りの１ビットは、マスクに使われる。
【００５４】
ただし、ビット割り当ては図７の形態に限定されない。すなわち、例えば、塩基の種類に４ビットを割り当て、マスクに１ビットを割り当て、全部で５ビットを１塩基に割り当てることができる。このとき、各塩基に１ビットが割り当てられてよい。そして、この場合、ａ、  ｃ、  ｇ、ｔの他に、ｍ  （ａ／ｃ）、  ｓ  （ｇ／ｃ）、  ｗ  （ａ／ｔ）、  ｋ  （ｇ／ｔ）、  ｖ  （ａ／ｃ／ｇ）、  ｈ  （ａ／ｃ／ｔ）、  ｄ  （ａ／ｇ／ｔ）、  ｂ  （ｇ／ｃ／ｔ）、  ｒ  （ａ／ｇ）、  ｙ  （ｃ／ｔ）、  ｎ  （ａ／ｃ／ｇ／ｔ）  などの不定塩基を指定するため  ４  ビットに加えて各ビットにビット論理演算が可能な付加ビットを指定することも可能である。
【００５５】
図８は、上記のビット割当ての例を示している。例えば、Ｓ（Ｓｔｒｏｎｇ）に着目すると、Ｓは不定塩基であり、その意味は「ｇまたはｃ」である。このＳは、図８では、Ｇ欄（＝ｇ）とＣ欄（＝ｃ）の「１」により表現される。
【００５６】
図８のようなコードを採用すれば、（１）塩基一致  Ｉ１  ａｎｄ  Ｉ２は、ｂｉｔ論理積であり、（２）塩基の  Ｉ１  ｏｒ  Ｉ２  はｂｉｔ論理和であり、（３）塩基の  ｎｏｔ（Ｉ）はｂｉｔ補数であり、（４）相補的塩基は、ｂｉｔ配列の単純反転である、というようにビット単位の演算（ｂｉｔｗｉｓｅ  ｏｐｅｒａｔｉｏｎ）が可能な閉じたコード系を作成することができる。このようなコード系は類似性検索においてより柔軟な対応を可能にするので、ＣＡＭに投入できる配列の量の減少を補って余りある利点が存在する。また、ビット単位のマスクを可能にすることにより、一塩基多型（ＳＮＰｓ）解析などにおいて塩基の種類が個人により異なるようなバリアント配列を効率的に処理できる。
【００５７】
また、実際の処理では、ある塩基に関して、マスクのビットに１を書き込むと、その塩基にマスクがかかる。このとき、塩基の種類を表すデータ、例えば図７の２ビットのデータは、書き換えられなくてもよい。
【００５８】
また、マスクビットは上記のように１ビットに限定されない。例えば、マスクビットを２ビットにした場合には、２重のマスクやマスクの履歴、マスクの内容を指定可能になり、すなわち条件分岐の数を増やすことが可能である。例えば、マスクが００、０１、１０、１１の４種の場合、以下のような指定が考えられる。
【００５９】
（１）００はマスクなしの通常状態、０１は比較せず一致しないマスク、１０は比較せずに一致とみなすマスク、１１は通常どうり比較するが、位置をマークするためのマスク。これによりマスク検索の柔軟性が増す。
【００６０】
（２）００はマスクなしの通常状態、０１は塩基の００、０１、１０、１１の下１桁のビットをマスク、１０は上１桁のビットをマスク、１１は両方のビットをマスクすることにより、プリン塩基ａ／ｇとピリミジン塩基ｃ／ｔを区別しない検索などが可能となる。
【００６１】
（３）００、０１、１０、１１とマスクを受けた回数を記録することに利用することによって、マスキングによる条件分岐に２回以上の一致をみた配列のみを次の命令により処理するなどの多様性を付加することが可能である。
【００６２】
また、マスクのかけ方は、目的の処理が達成される範囲で任意である。例えば、あるコドンにマスクをかけるとする。そのコドンの３つの塩基すべてにマスクがかけられてもよい。また、場合によっては、１つ目の塩基のみにマスクがかけられてもよい。後者の処理でも、マスクがかかったコドンの検索は可能であり、また、マスクがかかったコドンが検索されないようにすることも可能である。
【００６３】
また、図７のような細かなレベルで見たときには、ＤＣｂｉｔがいろいろな形で使われる。例えば、マスクに無関係な検索においては、マスクのビットの位置にＤＣｂｉｔが適用されてよい。また、マスクがかかった部位を検索するときは、ＤＣｂｉｔの適用により、塩基種類を表す２ビットが無視されてよい。
【００６４】
また、上記のように、コンパレータを細かく見ると、各塩基に複数ビットが使われ、それら複数ビットのデータが処理される（図７では各塩基に３ビット）。しかし、以下の既述では、説明を分かりやすくするため、塩基を単位に用いて本発明を説明する。
【００６５】
次に、参照配列の検索処理の基本動作を説明する。
【００６６】
図９に示されるように、検索処理では、コンパレータ２８のＣＡＭに、被照合データである配列情報が書き込まれる。ＣＡＭの幅は、例えば、７２ビット、１４４ビットまたは２８８ビットである。これに対して、配列情報は、ＣＡＭの照合方向の幅よりも長いことが多い。そこで、図示のように、配列は分割され、ＣＡＭの複数の列を使って配列情報が記憶される。すなわち、配列が複数の分割配列に分割され、各分割配列がＣＡＭの一つの列に記憶される。これにより、本発明は、長い配列をＣＡＭで処理可能としている。
【００６７】
そして、並列照合処理においては、参照配列がＣＡＭの配列情報に含まれるか否か、すなわち、参照配列と一致する配列がＣＡＭ中に存在するかが検索される。
【００６８】
この処理では、参照配列が、照合データとして、コンパレータ２８に投入される。コンパレータ２８のＣＡＭは、照合データと各列の被照合データとを並列処理にて比較する。照合データと被照合データが一致するとき、コンパレータ２８は「１」を出力し、一致しなければ、コンパレータ２８は「０」を出力する。この出力が、照合結果として配列処理制御部３０に返される。この照合結果より、検索対象の配列に参照配列が含まれるか否かが分かる。
【００６９】
参照配列を照合データとして用いる照合処理は、コンパレータ２８のＣＡＭの特性に基づき、ワイルドカードすなわちＤＣｂｉｔを用いて行われる。
【００７０】
図１０を参照すると、本実施の形態では、照合データの参照配列の前後に、図示のようなＤＣｂｉｔ（＊）が設定される。すなわち、参照配列の長さに相当する部分を除いた残りの部分にＤＣｂｉｔが与えられる。ＤＣｂｉｔが与えられた部分は、照合の対象から除外される。ＤＣｂｉｔが与えられない部分が、照合の対象になる。
【００７１】
ＤＣｂｉｔの位置は、順次ずらされていく。言い換えれば、ＤＣｂｉｔが与えられない部分（照合対象部分）が順次、１文字ずつシフトされる。このようにして、照合除外部分の位置を異ならせた複数回の照合処理が行われて、被照合データのどの部分が参照配列と一致するときでも、その一致を検出できる。また、参照配列と一致する場所を特定することも可能である。
【００７２】
ＤＣｂｉｔをずらした複数回の照合結果は、論理演算を用いて好適に処理される。論理演算により、複数回の照合結果のいずれかにおいて一致の結果が得られたか否かが判定される。また、複数の配列情報をコンパレータ２８に投入したとき、それら複数の配列情報に参照配列が含まれているか否かも、論理演算を使って求められる。
【００７３】
本実施の形態は、ＣＡＭの並列処理を好適に利用したことで、参照配列の検索処理を高速化可能である。この点について、通常の処理の計算量と本発明の処理の計算量を概略的に比較する。
【００７４】
ここでは、数万から数十万といった大量の遺伝子配列を格納したデータベースを用いて検索を行う場合を考える。データベースの遺伝子配列の数をＮｃ、一つの配列の塩基数をＬｃ、参照配列の塩基数をＲｌとすると、従来の処理の計算量は、Ｎｃ＊（Ｌｃ−Ｒｌ）で表される。
【００７５】
一方、本発明においては、各分割配列のデータ長をＣｃとし、参照配列の塩基数をＲｌとすると、計算量は、Ｃｃ−Ｒｌで表される。この式には、配列全体のデータ長Ｌｃが含まれていない。遺伝子配列を分割した分割配列が検索対象となるからである。また、上記の式には、配列の数Ｎｃが含まれていない。これは以下の理由による。
【００７６】
ＣＡＭは、通常はインターネットのルータの部品として用いられ、大量のＩＰアドレスを並列検索が可能な状態で記憶するように構成される。したがって、ＣＡＭは、照合方向の幅は比較的短いが、それに交差する方向には非常に長い。この点を利用することにより、数万以上の遺伝子配列を、交差方向に並べて同時に記憶し、同時に並列処理できる。したがって、ＣＡＭを使うときの計算量の式には、遺伝子配列の数Ｎｃは含まれていない。
【００７７】
上述のように、概略的には、従来の処理の計算量は、Ｎｃ＊（Ｌｃ−Ｒｌ）で表され、本実施の形態の処理の計算量はＣｃ−Ｒｌで表される。遺伝子配列の数Ｎｃは、通常、数万から数十万である。また、一配列の塩基数Ｌｃは、１０００〜１００００個程度である。また、参照配列の塩基数Ｒｌは２０程度である。さらに、分割配列のデータ長Ｃｃは１００程度とする。この場合、両者の計算量を比較すると、本実施の形態の処理の計算量は、概略的には、例えば約１００００分の１である。
【００７８】
このようにして、本実施の形態では、配列検索の高速化が可能である。そして、上記説明から明らかなように、本実施の形態は、ＣＡＭの特性を好適に利用している。すなわち、照合方向と交差する方向の長さを利用して、大量の遺伝子が同時に被照合データとして格納される。さらに、照合方向の幅が短いことを不利とせずに、むしろ、複数の分割配列を並列にて処理することで計算量を削減している。こうして、上述の大幅な高速化が可能となる。
【００７９】
ところで、本実施の形態は、上述のように、一つの配列を複数の分割配列に分けている。したがって、分割箇所にて、参照配列と同じ配列が複数の分割配列に跨ることがあり得る。このような配列は、以下の処理により好適に検出される。
【００８０】
図１１を参照する。本実施の形態では、参照配列の端の部分を照合データとして用いた照合処理が行われる。参照配列の後方の部分が、被照合データである分割配列の前方部分と一致するか否かが、求められる。図示のように、参照配列の後方の１文字を使う照合、２文字を使う照合・・・ｉ−１文字を使う照合が行われる。ｉは、参照配列の文字数である。照合対象以外の部分には、上述の処理で説明したのと同様に、ＤＣｂｉｔが設定される。実際の処理では、ＤＣｂｉｔのパターンを増やせばよい。すなわち、参照配列が被照合データの前方部分からはみ出る場合についてもＤＣｂｉｔのパターンが設定されればよい。これにより、上述の照合処理をそのまま適用可能となる。
【００８１】
また、同様にして、参照配列の前方の部分が、被照合データである分割配列の前方部分と一致するか否かが、求められる。
【００８２】
そして、上記の処理により、第ｎ＋１列の前方部分に、参照配列の後方部分があったとする。また、第ｎ列の後方部分に、参照配列の前方部分があったとする。両部分を連結すると、参照配列が得られるか否かが判定される。ここでは、２つの部分の文字数が参照配列の文字数と一致するか否かが判定されてもよい。参照配列が得られるとき、参照配列と同じ部分配列がサンプル配列に含まれると判定される。
【００８３】
この判定処理は、実際のプログラムでは、以下のようにして論理演算を利用して好適に行われる。参照配列の一部を使った照合により、被照合データと照合データが一致するとき、コンパレータ２８は「１」を出力し、そうでなければコンパレータ２８は「０」を出力する。以下の２つの照合結果が論理演算にかけられる。
【００８４】
（１）第ｎ列の後方部分を、参照配列の前方のｋ文字と照合した結果
（２）第ｎ＋１列の前方部分を、参照配列の後方のｉ−ｋ文字と照合した結果
論理演算は、１＊１＝１、１＊０＝０、０＊１＝０、０＊０＝０である。演算結果が１であれば、参照配列と同じ部分配列がサンプル配列に含まれる。演算結果が０であれば、参照配列と同じ部分配列はサンプル配列に含まれない。１≦ｋ≦ｉ−１の範囲で、上記の処理が行われる。このようにして、２つの分割配列に跨る参照配列が好適に検出される。
【００８５】
なお、分割箇所の配列は、他の処理により検出されてもよい。例えば、コンパレータ２８に被照合データである配列情報を書き込むときに、分割箇所では配列情報を部分的に重複させることが考えられる。すなわち、ある列の後端部分と、次の列の前端部分に、配列が重複して書かれる。これにより、分割箇所での検出の漏れを回避できる。この手法は、参照配列が比較的短い場合に適している。
【００８６】
以上、参照配列の基本的な検索処理を説明した。次に、参照配列の一部に相当する部位にワイルドカードが設定された本実施の形態の検索処理を説明する。
【００８７】
本実施の形態では、以下のように、参照配列にワイルドカードが設定され、コンパレータ２８に投入される。しかし、コンパレータ２８側の配列情報にワイルドカードが設定されてもよい。この処理でも同様の結果が得られ、本発明の範囲に含まれる。また、後者の処理も、参照配列の一部にワイルドカードが設定された処理と見ることができる。
【００８８】
（１）類似性検索
まず、従来のブラスト検索を説明する。ブラスト検索は、ホモロジー検索の一つである。ブラスト検索では、ギャップの挿入を行わずに局所的によく一致する部位が探索される。このような部位を高スコア断片と呼ぶ。そして、高スコア断片が前後に伸長される。
【００８９】
図１２を参照すると、ブラストでは、一般に１１ベースといわれる処理が行われる。１１ベースは、１１の連続した塩基配列を検索する処理である。すなわち、検索クエリーとして、１１塩基の配列が使用される。
【００９０】
これに対して、本実施の形態では、図１２に例示されるように、参照配列の一部にワイルドカードが設定される。
【００９１】
第１の例では、７＊８の参照配列（ｃａｇｔａｔｃ＊ｇａｔｔｇｃｃｇ）が検索クエリーとして用いられる。すなわち、７つの塩基配列と８つの塩基配列の間にワイルドカードが設定される。また、第２の例では、４＊５＊４の参照配列（ａｔｃｇ＊ｃｇｔａｃ＊ａａｔｔ）が検索クエリーとして用いられる。すなわち、４つの塩基配列、ワイルドカード、５つの塩基配列、ワイルドカード、４つの塩基配列が並んだ参照配列が使用される。これらの参照配列を使うと、変異を許容した検索ができる。
【００９２】
ＣＡＭの検索では、任意の位置に、任意の数のワイルドカードを設定することが可能である。ワイルドカードは、照合データ投入部３６のワイルドカード設定部４４により設定される。参照配列の前後にもワイルドカードが設定され、この点は前述の通りである（図１０）。そして、ワイルドカードを含む参照配列がコンパレータ２８に投入され、コンパレータ２８から結果が返される。この情報は、照合結果取得部３８に取得され、照合結果処理部４０に渡される。照合結果処理部４０は、検索された配列の位置を示す情報を、解析情報出力部４２に出力させる。
【００９３】
従来のブラスト検索は、上述のように、連続した塩基配列が検索される。仮に、従来のゲノム配列処理用のデータベースシステムで、本実施の形態のようにワイルドカードを含んだ検索、または変異を許容した類似性検索を行うとする。これは、データベースシステムの改造等により不可能とはいえないが、ワイルドカードを含む検索の膨大な計算処理を従来型のデータベースシステムに行わせることは現実問題として困難である。
【００９４】
これに対し、本実施の形態は、ＣＡＭを使っており、ワイルドカードを容易に設定できるような構成を実現している。そして、ワイルドカードの利用により、変異を許容した類似性検索を高速で行うことが可能となっている。そして、このような検索により、従来のブラストでは見つからなかった類似性検索が可能となる。
【００９５】
（２）アミノ酸配列検索
アミノ酸はコドンによってコードされ、したがってアミノ酸配列は、コドンの配列によりコードされる。
【００９６】
図１３は、コドン表の一部を示している。アミノ酸Ｐは、４種類のコドン（ｃｃｔ、ｃｃｃ、ｃｃａ、ｃｃｇ）と対応する。また、アミノ酸Ｆは、２種類のコドン（ｔｔｔ、ｔｔｃ）と対応する。また、アミノ酸Ｌは、６種類のコドン（ｔｔａ、ｔｔｇ、ｃｔｔ、ｃｔｃ、ｃｔａ、ｃｔｇ）と対応する。
【００９７】
このように、各アミノ酸には複数種類のコドンが対応するので、アミノ酸配列をコードする塩基配列のパターンは膨大な数になる。そのため、ＤＮＡ配列から特定のアミノ酸配列をコードする領域を検出しようとすると、情報処理量が非常に多くなり、このような検索は従来は容易でなかった。本実施の形態は、特定のアミノ酸配列の候補領域を容易に検索する技術を提供する。
【００９８】
図１４を参照すると、この例では、アミノ酸配列ＦＡＰＱＲＴＭを検索するために、「ｔｔ＊ｇｃ＊ｃｃ＊ｃａ＊＊ｇ＊ａｃ＊ａｔｇ」という参照配列が使用される。この参照配列では、アミノ酸種類に対して塩基が不特定な部位にワイルドカードが設定されている。すなわち、各コドンに対応する部位で、アミノ酸種類に複数の塩基が対応する部位にワイルドカードが設定されている。
【００９９】
より詳細には、検索対象のアミノ酸配列において、第１のアミノ酸はＦである。Ｆは、２種類のコドン（ｔｔｔ、ｔｔｃ）と対応する（図１３）。１番目と２番目の塩基が特定されるが、３番目の塩基が不特定なので、参照配列では、ｔｔ＊というように、３番目にワイルドカードが設定されている。
【０１００】
同様に、第２のアミノ酸Ａは、コドン（ｇｃｔ、ｇｃｃ、ｇｃａ、ｇｃｇ）と対応するので、参照配列は、ｇｃ＊というように、不特定な３番目の塩基にワイルドカードが設定される。第３のアミノ酸Ｐは、コドン（ｃｃｔ、ｃｃｃ、ｃｃａ、ｃｃｇ）に対応するので、ｃｃ＊というように、不特定な３番目の塩基にワイルドカードが設定される。さらに、第４のアミノ酸Ｑは、コドン（ｃａａ、ｃａｇ）に対応するので、ｃａ＊というように、不特定な３番目の塩基にワイルドカードが設定される。
【０１０１】
次に、第５のアミノ酸Ｒは、コドン（ｃｇｔ、ｃｇｃ、ｃｇａ、ｃｇｇ、ａｇａ、ａｇｇ）と対応する。２番目の塩基ｇは特定されるが、１番目と３番目の塩基が不特定なので、参照配列においても、＊ｇ＊というように、１番目と３番目にワイルドカードが設定される。
【０１０２】
第６のアミノ酸Ｔは、コドン（ａｃｔ、ａｃｃ、ａｃａ、ａｃｇ）と対応するので、参照配列は、ａｃ＊というように、不特定の３番目の塩基にワイルドカードが設定される。
【０１０３】
第７のアミノ酸Ｍは、１種類のコドン（ａｔｇ）と対応する。不特定な塩基がないので、図示のように、ワイルドカードは設定されない。
【０１０４】
以上のようにして、本実施の形態では、検索対象のアミノ酸配列に応じて、塩基が特定されない部位にワイルドカードが設定される。ＣＡＭの検索では、任意の位置に、任意の数のワイルドカードを設定することが可能である。ワイルドカードは、照合データ投入部３６のワイルドカード設定部４４により設定される。参照配列の前後にもワイルドカードが設定され、この点は前述の通りである（図１０）。そして、ワイルドカードを含む参照配列がコンパレータ２８に投入され、コンパレータ２８から結果が返される。この情報は、照合結果取得部３８に取得され、照合結果処理部４０に渡される。照合結果処理部４０は、検索された配列の位置を示す情報を、解析情報出力部４２に出力させる。
【０１０５】
なお、本実施の形態において、上記の処理だけでは、対象のアミノ酸配列をコードする領域のみが検索されない。すなわち、対象でないアミノ酸配列も検索されてしまう。
【０１０６】
例えば、図１４においては、１番目のアミノ酸Ｆに対応するコドン（ｔｔｔ、ｔｔｃ）を検索するために、参照配列は、ｔｔ＊と設定される。しかし、図１０にも示したように、このｔｔ＊を使うと、アミノ酸Ｌに対応するコドン（ｔｔａ、ｔｔｇ）も検索される。
【０１０７】
このように、上記の処理では、検索対象でないアミノ酸配列をコードする領域も検索されてしまう。しかし、対象のアミノ酸配列の領域は漏れることなく検索される。そこで、得られた結果を候補の情報として用いればよい。そして、この候補を選別して、対象のアミノ酸配列をコードする領域を求めればよい。この選別処理では、上記のアミノ酸Ｆ、Ｌの区別のようなコドンとアミノ酸の対応関係を考慮して、候補領域内の各コドンが目的のアミノ酸に対応するか否かを順次判定し、確認する処理を行えばよい。
【０１０８】
以上に説明したように、本実施の形態によれば、ワイルドカードを利用することにより、アミノ酸配列の検索を容易かつ短時間で行うことを可能にする。アミノ酸配列を構成し得る膨大な数の配列パターンの検索処理を、短時間で行える。
（３）コード領域ホモログ検索
【０１０９】
上述の実施の形態は、さらに、コード領域ホモログ検索に応用可能である。
【０１１０】
ホモログのアミノ酸配列をコードする領域での読み枠においては、各コドンの第３番目の塩基が変異していることが多い。そこで、３番目にワイルドカードが設定された参照配列を用いることで、ホモログ検出率を向上可能である。すなわち、例えば、「ｔｔ＊ｔｇ＊ｃａ＊ａｃ＊＊ｃｃ」というような参照配列が使われる。
【０１１１】
ＣＡＭの検索では、任意の位置に、任意の数のワイルドカードを設定することが可能である。そこで、ワイルドカードは、検索対象のホモログのアミノ酸配列に応じて設定される。ワイルドカードは、照合データ投入部３６のワイルドカード設定部４４により設定される。参照配列の前後にもワイルドカードが設定され、この点は前述の通りである（図１０）。そして、ワイルドカードを含む参照配列がコンパレータ２８に投入され、コンパレータ２８から結果が返される。この情報は、照合結果取得部３８に取得され、照合結果処理部４０に渡される。照合結果処理部４０は、検索された配列の位置を示す情報を、解析情報出力部４２に出力させる。
【０１１２】
以上のようにして、本実施の形態によれば、高速に、かつ、高確率でのホモログ検索ができる。
【０１１３】
ここで、探索したい類似遺伝子がＥＳＴ配列もしくはアミノ酸配列／ｃＤＮＡとしてわかっている場合にはイントロンにより分割された配列からホモログの断片とそのつながりを検出することが必要である。しかし、イントロンは  数  ｋｂに及ぶような長大なものもあり、ｇａｐ  ｐｅｎａｌｔｙを低く設定したｇｌｏｂａｌ  ａｌｉｇｎｍｅｎｔでは限界がある。このために特殊関数ｅｎｃｏｍｐａｓｓを導入する。これは  ｅｎｃｏｍｐａｓｓ（ｔａｇ，  ｐｒｅｆｉｘ，  ｓｕｆｆｉｘ，  ｓｔａｒｔ，  ｓｔｏｐ，  ｓｈｉｆｔ，  ｏｐｔｉｏｎ）の入力形式をとるものでｐｒｅｆｉｘとｓｕｆｆｉｘによりはさまれる文字数がｓｈｉｆｔ幅のｓｔａｒｔ倍からｓｔｏｐ倍の等差数列である場合に検出するものである。ｓｈｉｆｔ幅は１または３を設定することができる。例えば、・・・ＥＮＣＥＡＭＩＮＱＡＣＩＤＳＳＥＱＵ・・・というアミノ酸列が与えられた場合，イントロンで１つのアミノ酸が分断されることを考慮し、１つの空白を入れｐｒｅｆｉｘ＝’ｇｃ＊ａｔｇａｔ＊ａａ＊’  （’ＡＭＩＮ’），  ｓｕｆｆｉｘ＝’ｇｃ＊ｔｇ＊ａｔ＊ｇａ’  （’ＡＣＩＤ’）  のようなｗｏｒｄ  ｐａｉｒを全長にわたって作成し、ｅｎｃｏｍｐａｓｓ（ｔａｇ，  ｐｒｅｆｉｘ，  ｓｕｆｆｉｘ，  １，  １００００，  ０）のサーチを施行すればよい。ｓｕｆｆｉｘは’ｓｔｒ１／ｓｔｒ２／ｓｔｒ３…／ｓｔｒＮのように複数個指定できるので変異を考慮に入れたサーチも可能である。関数ｅｎｃｏｍｐａｓｓを用いなくても数値セル配列から所定範囲内にある数列を抽出するアルゴリズムを用いれば、次のように遺伝子同定が可能である。
【０１１４】
１）アミノ酸配列を小さなｗｏｒｄにｓｈｉｆｔ幅１で連続分解
２）各ｗｏｒｄをＤＮＡに逆翻訳してワイルドカードサーチ
３）サーチ結果から数ｋｂ幅の処理にてｔｏｐｏｌｏｇｉｃａｌ  ｏｒｄｅｒ順に整列する数列を抽出
４）抽出された塩基位置領域のＯＲＦを探索  （後述）
５）各ＯＲＦのｄｅｄｕｃｅｄ  ａｍｉｎｏ  ａｃｉｄｓと元のアミノ酸配列をアラインメント
６）アラインメントの結果一致するＯＲＦのみを選択
７）ＧＴ−ＡＧ  ｒｕｌｅとアミノ酸連続性により各ＯＲＦにおけるｅｘｏｎ−ｉｎｔｒｏｎ境界を検出
８）遺伝子構造を決定し、ｃＤＮＡおよびｄｅｄｕｃｅｄ  ａｍｉｎｏ  ａｃｉｄｓを決定
本アルゴリズムは領域検出がアラインメントに依存しない新しいアルゴリズムであり、これまでの遺伝子探索を大幅に効率化するものである。
【０１１５】
ここで、上述のアルゴリズムに含まれるＯＲＦ検索の好適な処理を説明する。遺伝子の探索においては、ＯＲＦの探索が最初のステップとして行われる。ＯＲＦは、ストップコドン（ｔａｇ、ｔｇａ、ｔａａ）で挟まれたコドンの配列である。このＯＲＦ探索においては、ある程度以上の長さ（通常は５０〜１００以上の長さ）をもつＯＲＦが探索される。しかし、巨大配列では、非常に多数のＯＲＦがあるので、このようなＯＲＦを探索するといった処理も容易ではない。本実施の形態は、マスクの利用によって、ＯＲＦ探索を容易にし、かつ、高速化する。
【０１１６】
図１５を参照すると、この例では、ストップコドン間の塩基数が５０以上のコドンが検索される。以下、両端のストップコドンに挟まれる部分を「窓」という。
【０１１７】
図１５では、まず、窓の塩基数が０〜４８（コドンの数が０〜１６）のＯＲＦ（以下、短ＯＲＦという）が検索される。ここでは、ワイルドカードを含む参照配列が使われる。参照配列は、両端にストップコドンをもち、それらの間にワイルドカードを有する。ワイルドカードの数は、０、３、、、、４８と順次変えられる。また、両端のストップコドン（ｔａｇ、ｔｇａ、ｔａａ）の組合せは９通りである。これら９通りのすべてに対応する参照配列がコンパレータ２８に投入される。
【０１１８】
このような参照配列が次々とコンパレータ２８に投入され、一致する配列が検索される。検索は、下流から上流に向かって行われる。検索の結果は、配列処理制御部３０に返され、照合結果取得部３８に取得される。そして、照合結果処理部４０の指示に従い、検索された配列の上流側のストップコドンに、マスク処理部４６によりマスクがかけられる。このとき、本実施の形態のＯＲＦ検索では、上流側のストップコドンの先頭の塩基にマスクがかけられる。
【０１１９】
上記の処理により、短ＯＲＦにマスクがかかる。本実施の形態では、検索された短ＯＲＦに次々とマスクがかけられる。そのため、短ＯＲＦが連続する場合に、次の短ＯＲＦのストップコドンにマスクがかかってしまい、その結果、次の短ＯＲＦが見逃される可能性がある。そこで、さらに次の検索が行われる。
【０１２０】
すなわち、図１６に示されるように、ストップコドンとマスク「ｏ」の組合せを用いて、上述と同様の処理が行われる。マスク「ｏ」は、ストップコドンの先頭に付いているので、この処理も、ストップコドンに挟まれた短ＯＲＦの検索である。図示のように、ストップコドンとマスク「ｏ」の間にワイルドカードをもつ参照配列がコンパレータ２８に投入される。ワイルドカードの数は、０、３、６、、、と変えられる。また、上流側のストップコドンは３通りである。そして、検索された配列の上流側のストップコドンに、マスク処理部４６によりマスクがかけられる。ここでも、マスクは、ストップコドンの先頭の塩基にかけられる。
【０１２１】
図１７に例示されるように、上記の処理が終わると、窓の塩基数が５０未満のすべてのＯＲＦにおいて、上流側のストップコドンの先頭塩基にマスクがかかっている。
【０１２２】
そこで、参照配列としてストップコドンを使って、ストップコドンが検索される。３種のストップコドン（ｔａｇ、ｔｇａ、ｔａａ）が各々検索される。検索されたストップコドンは、窓の塩基数が５０以上のＯＲＦの先頭を示している。
【０１２３】
このようにして、本実施の形態によれば、ストップコドン間の塩基数が所定数以上のＯＲＦの位置情報が得られる。この情報は、解析情報出力部４２により出力される。この情報は遺伝子の探索に利用可能である。
【０１２４】
なお、上記の処理では、マスクは、ストップコドンの先頭の塩基にのみ付けられている。このように、処理の目的が達せられる限り、本発明の範囲内で、マスクがかけられるのは、検索された部位の一部でもよい。なお、上記の処理の変形例では、３つの塩基すべてにマスクがかけられてもよい。この処理でも同様の結果を得ることができる。
【０１２５】
また、上記においては、図１５に示す１段階目の検索において、検索された短ＯＲＦに順次マスクがかけられる。そのために、上述したように、短ＯＲＦが連続する場合を考慮して、図１６に示す２段階目の検索で、ストップコドンとマスクで挟まれる短ＯＲＦが検索された。しかし、図１５に示す１段階目の検索で、すべての検索が終わってからマスク処理が行われてもよい。こうすれば、２段階目の検索は省略可能である。
【０１２６】
以上に説明したように、本実施の形態によれば、目的最小ＯＲＦ長Ｌ未満の長さの配列を挟むストップコドンが前記コンパレータに検索される。目的最小ＯＲＦ長Ｌは、上記例では、５０である。これにより、目的最小ＯＲＦ長Ｌ未満の長さの短ＯＲＦが検索される。そして、検索された短ＯＲＦが再度検索されないように、コンパレータの配列情報にマスクが施される。次に、ストップコドンの検索がコンパレータにより行われと、目的最小ＯＲＦ長Ｌ以上の長さをもつＯＲＦが検索される。このようにして、目的最小ＯＲＦ長Ｌ以上の長さのすべてのＯＲＦを見つける処理を簡単にできる。非常に長いＯＲＦも簡単な処理で見つけることができる。
【０１２７】
以上にＯＲＦ検索について説明した。このＯＲＦ検索は、上述のコード領域ホモログ検索の過程で好適に利用可能である。
【０１２８】
以上、本発明の好適な各種の実施の形態を説明した。上述のように、本発明では、コンパレータでのワイルドカードを使う比較処理により、配列情報の処理を好適に行える。
【０１２９】
従来技術では、配列検索はあくまでＤＮＡ配列をクエリとして用いている。ところが、生物種が異なる相同遺伝子間ではアミノ酸をコードする配列のうち、アミノ酸の指定に関与しない第３番目の塩基などが高率に変異を起こしていることなどから、相同遺伝子の同定には高スコア断片自体を同定しえない場合も多く、ここに従来技術の限界があった。本発明では、アミノ酸配列自体をワイルドカードをいれて同義のＤＮＡ配列に置き換えて検索できるので、生物種を超えたオルソログ遺伝子や同一ゲノム中のパラログ遺伝子を非常に高ヒット率で検索することが可能になった。
【０１３０】
アミノ酸配列で検索できるという技術の進歩は、これにとどまらない。すなわち、（１）たんぱく質のドメインまたはモチーフとよばれる類似機能をもつアミノ酸配列をゲノム中に探索することを許し、ある特定のドメイン・モチーフすなわち機能を持つ未知の遺伝子（たんぱく質）群を探索可能となる。（２）２つの生物種におけるゲノムの比較において、コード領域の候補すなわち、ある一定以上の長さをもつＯＲＦをアミノ酸に翻訳した上で、クエリを形成し、それをもって対比するゲノムを検索することにより、ゲノム同士の比較が、既知遺伝子のｃＤＮＡ配列（ｍＲＮＡ配列）を使うことなく可能になる。（３）ショウジョウバエ・線虫・酵母・細菌などゲノム配列と対応する遺伝子産物が完全に同定されたもののうち遺伝子のより高等な生物における類似遺伝子を探索することは重要な研究手法であるが、こうした研究が加速されることが期待できる。
【０１３１】
また、従来のブラストでは、検索時間を効率化するため、サーチ回数をできる限り制限して、高スコア断片のヒット部位を前後に伸ばしてゆくという方法がとられる。これに対して、本発明のコンパレータでは１回のサーチに時間がかからないため、高スコア断片を連続的に同定して、高スコア断片が一定範囲にクラスターを形成する部分を同定するという手法が可能である。すなわち、従来のブラスト探索ではヒットしないような３塩基ごとに変異が入っているというような配列においても、２＊２＊２＊２（＊はワイルドカード）のようなワイルドカード探索を参照配列全長にわたり行って、各断片のヒットする位置を同定して、それが参照配列と同等の長さの領域に集中して現れる領域を同定することが可能である。これにより、高スコア断片ヒット部位全てを伸長して、アラインメントするという操作を省略でき、高速な類似性検索が可能となる。
【０１３２】
以上に本発明の好適な実施の形態を説明したが、本実施の形態は、本発明の範囲内で変形可能なことはもちろんである。例えば、本実施の形態では、塩基配列が処理された。これに対し、本発明の範囲内で、既に述べたように、アミノ酸等の他の配列が処理されてもよい。
【０１３３】
【発明の効果】
以上に説明したように、本発明によれば、本発明によれば、ワイルドカードを使って、参照配列の一部が配列情報と一致するか否かを無視する検索を高速に行える。これにより、参照配列全体が一致するかどうかだけでは分からない情報が得られる。
【図面の簡単な説明】
【図１】本発明の好適な本実施の形態の全体構成を示す図である。
【図２】コンパレータの構成を示す図である。
【図３】インターネットのルータに用いるときのＣＡＭの通常の機能を示す図である。
【図４】本実施の形態の生物学的配列情報処理装置の機能ブロック図である。
【図５】ワイルドカードを示す図である。
【図６】マスクを示す図である。
【図７】ＣＡＭ上での塩基およびマスクの情報を示す図である。
【図８】ＣＡＭ上での塩基およびマスクの情報の別の例を示す図である。
【図９】参照配列の検索処理を示す図である。
【図１０】参照配列の検索処理を示す図である。
【図１１】参照配列の端の部分を照合データとして用いることにより、複数の分割配列に跨る参照配列を求める処理を示す図である。
【図１２】ワイルドカードを使った類似性検索を示す図である。
【図１３】コドン表の一部を示す図である。
【図１４】ワイルドカードを使ったアミノ酸配列検索を示す図である。
【図１５】マスクを用いてＯＲＦを検索する実施の形態を示す図である。
【図１６】マスクを用いてＯＲＦを検索する実施の形態を示す図である。
【図１７】短いＯＲＦの上流側にあるストップコドンの先頭塩基にマスクがかかった状態を示す図である。
【符号の説明】
２６  生物学的配列情報処理装置
２８  コンパレータ
３０  配列処理制御部
３２  配列情報取得部
３４  被照合データ投入部
３６  照合データ投入部
３８  照合結果取得部
４０  照合結果処理部
４２  解析情報出力部
４４  ワイルドカード設定部
４６  マスク処理部
【図１】
2004234297.tif 000003
【図２】
2004234297.tif 000004
【図３】
2004234297.tif 000005
【図４】
2004234297.tif 000006
【図５】
2004234297.tif 000007
【図６】
2004234297.tif 000008
【図７】
2004234297.tif 000009
【図８】
2004234297.tif 000010
【図９】
2004234297.tif 000011
【図１０】
2004234297.tif 000012
【図１１】
2004234297.tif 000013
【図１２】
2004234297.tif 000014
【図１３】
2004234297.tif 000015
【図１４】
2004234297.tif 000016
【図１５】
2004234297.tif 000017
【図１６】
2004234297.tif 000018
【図１７】
2004234297.tif 000019