(57)【特許請求の範囲】
【請求項１】
並列照合機能をもつ記憶処理装置に、塩基配列、アミノ酸配列等の生物学的な複数の配列情報を、被照合データとして用いるために、照合方向と交差する方向を向けて、照合方向に並ぶように記憶させる被照合データ記憶ステップと、
照合方向に並んで隣接する前記複数の配列情報のデータを被照合データとして用いて、配列要素を表す文字等のコードとして同一のものが並ぶ同一コード列に対応するデータを照合データとして用いて、照合データと被照合データを並列処理にて前記記憶処理装置に照合させる照合ステップと、
を含むことを特徴とする生物学的配列情報処理方法。
【請求項２】
請求項１に記載の生物学的配列情報処理方法において、
前記並列照合機能をもつ記憶処理装置は、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）であり、一つの照合データと複数の被照合データを並列処理にて比較し、照合データと各被照合データの一致を示す情報を出力することを特徴とする生物学的配列情報処理方法。
【請求項３】
請求項１に記載の生物学的配列情報処理方法において、
配列情報を構成する複数種類のコードの各々について、同一コード列に対応するデータを照合データとして用いた照合を行い、複数回の照合結果を処理して、前記複数の配列情報の一致に関する情報を得ることを特徴とする生物学的配列情報処理方法。
【請求項４】
請求項１に記載の生物学的配列情報処理方法において、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、他の配列情報と一致しない配列情報を特定することを特徴とする生物学的配列情報処理方法。
【請求項５】
請求項１に記載の生物学的配列情報処理方法において、
照合データと被照合データが一致しないとき、多型により他の配列と異なる配列があると判定することを特徴とする生物学的配列情報処理方法。
【請求項６】
請求項５に記載の生物学的配列情報処理方法において、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、他の配列と異なる配列を特定することを特徴とする生物学的配列情報処理方法。
【請求項７】
請求項１に記載の生物学的配列情報処理方法において、
照合データと被照合データが連続して一致する部分と、照合データと被照合データが連続して一致しない部分とが隣接するとき、それら部分の境界に欠損または挿入があると判定することを特徴とする生物学的配列情報処理方法。
【請求項８】
請求項７に記載の生物学的配列情報処理方法において、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、欠損または挿入がある配列情報を特定することを特徴とする生物学的配列情報処理方法。
【請求項９】
請求項８に記載の生物学的配列情報処理方法において、
前記欠損または挿入がある配列情報を、前記照合方向と交差する方向にずらして記憶させて、照合処理を行うことにより、欠損と挿入のどちらがあるかを判定することを特徴とする生物学的配列情報処理方法。
【請求項１０】
請求項１に記載の生物学的配列情報処理方法において、
照合データと被照合データが連続して一致し、照合データと被照合データが一致しない部分があり、再び照合データと被照合データが連続して一致するとき、前記一致しない部分に置換があると判定することを特徴とする生物学的配列情報処理方法。
【請求項１１】
請求項１０に記載の生物学的配列情報処理方法において、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、置換がある配列情報を特定することを特徴とする生物学的配列情報処理方法。
【請求項１２】
請求項１〜１１のいずれかに記載の生物学的配列情報処理方法において、
ＳＮＰｓ解析に用いる情報を得ることを特徴とする生物学的配列情報処理方法。
【請求項１３】
塩基配列、アミノ酸配列等の生物学的な配列情報を処理する生物学的配列情報処理装置であって、
並列照合機能をもつ記憶処理装置と、解析対象の配列情報を取得する手段と、
前記記憶処理装置に被照合データを記憶させる手段と、前記記憶処理装置に照合データを投入して、前記記憶処理装置に照合データと被照合データを照合させる手段と、前記記憶処理装置から照合結果を取得する手段と、取得された照合結果を処理する手段と、
を含み、
前記並列照合機能をもつ記憶処理装置に、複数の配列情報を、被照合データとして用いるために、照合方向と交差する方向を向けて、照合方向に並ぶように記憶させ、照合方向に並んで隣接する前記複数の配列情報のデータを被照合データとして用いて、配列要素を表す文字等のコードとして同一のものが並ぶ同一コード列に対応するデータを照合データとして用いて、照合データと被照合データを並列処理にて前記記憶処理装置に照合させることを特徴とする生物学的配列情報処理装置。
【請求項１４】
請求項１３に記載の生物学的配列情報処理装置において、
前記並列照合機能をもつ記憶処理装置は、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）であり、一つの照合データと複数の被照合データを並列処理にて比較し、照合データと各被照合データの一致を示す情報を出力することを特徴とする生物学的配列情報処理装置。
【請求項１５】
請求項１３に記載の生物学的配列情報処理装置において、
配列情報を構成する複数種類のコードの各々について、同一コード列に対応するデータを照合データとして用いた照合を行い、複数回の照合結果を処理して、前記複数の配列情報の一致に関する情報を得ることを特徴とする生物学的配列情報処理装置。
【請求項１６】
請求項１３に記載の生物学的配列情報処理装置において、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、他の配列情報と一致しない配列情報を特定することを特徴とする生物学的配列情報処理装置。
【請求項１７】
請求項１３に記載の生物学的配列情報処理装置において、
照合データと被照合データが一致しないとき、多型により他の配列と異なる配列があると判定することを特徴とする生物学的配列情報処理装置。
【請求項１８】
請求項１７に記載の生物学的配列情報処理装置において、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、他の配列と異なる配列を特定することを特徴とする生物学的配列情報処理装置。
【請求項１９】
請求項１３に記載の生物学的配列情報処理装置において、
照合データと被照合データが連続して一致する部分と、照合データと被照合データが連続して一致しない部分とが隣接するとき、それら部分の境界に欠損または挿入があると判定することを特徴とする生物学的配列情報処理装置。
【請求項２０】
請求項１９に記載の生物学的配列情報処理装置において、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、欠損または挿入がある配列情報を特定することを特徴とする生物学的配列情報処理装置。
【請求項２１】
請求項２０に記載の生物学的配列情報処理装置において、
前記欠損または挿入がある配列情報を、前記照合方向と交差する方向にずらして記憶させて、照合処理を行うことにより、欠損と挿入のどちらがあるかを判定することを特徴とする生物学的配列情報処理装置。
【請求項２２】
請求項１３に記載の生物学的配列情報処理装置において、
照合データと被照合データが連続して一致し、照合データと被照合データが一致しない部分があり、再び照合データと被照合データが連続して一致するとき、前記一致しない部分に置換があると判定することを特徴とする生物学的配列情報処理装置。
【請求項２３】
請求項２２に記載の生物学的配列情報処理装置において、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、置換がある配列情報を特定することを特徴とする生物学的配列情報処理装置。
【請求項２４】
請求項１３〜２３のいずれかに記載の生物学的配列情報処理装置において、
ＳＮＰｓ解析に用いる情報を得ることを特徴とする生物学的配列情報処理装置。
【請求項２５】
塩基配列、アミノ酸配列等の生物学的な配列情報の処理をコンピュータに行わせる、コンピュータにて実行可能なプログラムであって、
並列照合機能をもつ記憶処理装置に、複数の配列情報を、被照合データとして用いるために、照合方向と交差する方向を向けて、照合方向に並ぶように記憶させる被照合データ記憶ステップと、
照合方向に並んで隣接する前記複数の配列情報のデータを被照合データとして用いて、配列要素を表す文字等のコードとして同一のものが並ぶ同一コード列に対応するデータを照合データとして用いて、照合データと被照合データを並列処理にて前記記憶処理装置に照合させる照合ステップと、
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項２６】
請求項２５に記載のプログラムにおいて、
前記並列照合機能をもつ記憶処理装置は、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）であり、前記ＣＡＭに、一つの照合データと複数の被照合データを並列処理にて比較させ、照合データと各被照合データの一致を示す情報を出力させることを特徴とするプログラム。
【請求項２７】
請求項２５に記載のプログラムにおいて、
配列情報を構成する複数種類のコードの各々について、同一コード列に対応するデータを照合データとして用いた照合を行い、複数回の照合結果を処理して、前記複数の配列情報の一致に関する情報を得る処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項２８】
請求項２５に記載のプログラムにおいて、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、他の配列情報と一致しない配列情報を特定する処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項２９】
請求項２５に記載のプログラムにおいて、
照合データと被照合データが一致しないとき、多型により他の配列と異なる配列があると判定する処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項３０】
請求項２９に記載のプログラムにおいて、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、他の配列と異なる配列を特定する処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項３１】
請求項２５に記載のプログラムにおいて、
照合データと被照合データが連続して一致する部分と、照合データと被照合データが連続して一致しない部分とが隣接するとき、それら部分の境界に欠損または挿入があると判定する処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項３２】
請求項３１に記載のプログラムにおいて、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、欠損または挿入がある配列情報を特定する処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項３３】
請求項３２に記載のプログラムにおいて、
前記欠損または挿入がある配列情報を、前記照合方向と交差する方向にずらして記憶させて、照合処理を行うことにより、欠損と挿入のどちらがあるかを判定する処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項３４】
請求項２５に記載のプログラムにおいて、
照合データと被照合データが連続して一致し、照合データと被照合データが一致しない部分があり、再び照合データと被照合データが連続して一致するとき、前記一致しない部分に置換があると判定する処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項３５】
請求項３４に記載のプログラムにおいて、
複数の配列情報の一部を照合対象から除外して、照合処理を行うことにより、置換がある配列情報を特定する処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項３６】
請求項２５〜３５のいずれかに記載のプログラムにおいて、
ＳＮＰｓ解析に用いる情報を得る処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項３７】
請求項２５〜３６のいずれかに記載のプログラムを格納した、コンピュータにて読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、塩基配列、アミノ酸配列等の生物学的な配列情報を解析のために処理する方法および装置に関し、特に、処理の高速化に関する。
【０００２】
【従来の技術】
分子生物学の分野では、ＤＮＡ、遺伝子、タンパク質等の解析のための情報処理技術の有用性が高まっている。この分野では、配列情報を解析するために情報処理技術が用いられる。この種の技術はバイオインフォマティクスといわれる。
【０００３】
例えば、ＳＮＰｓ（スニプッス、単一塩基多型）解析は、ほぼ同一の多数の塩基配列を解析して、局所的に異なる部分をもつ塩基配列を求める。
【０００４】
また例えば、ホモロジー検索は、複数の配列情報が似ているか、そしてどのように似ているかの情報を求める。ホモロジー検索方法としては、例えば、ブラスト（ＢＬＡＳＴ）法およびファスタ（ＦａｓｔＡ）法が知られている。
【０００５】
ブラスト法は、ギャップの挿入を行わずに局所的によく一致する部位を探索する。このような部位を高スコア断片と呼ぶ。そして、高スコア断片が前後に伸長される。
【０００６】
ファスタ法においては、配列が長く一致する部分を求める。この処理のために、従来は、複数の配列情報の一致する要素をプロットしたドットマトリックス情報が利用される。そして、一致部分の周囲に対して動的計画法によるアライメントが行われる。
【０００７】
【発明が解決しようとする課題】
配列解析では、大量の情報を高速に処理することが求められる。非常に長い配列が処理され、また、多数の配列が処理されるからである。しかし、従来は、配列解析の大量の情報処理は、専ら大型コンピュータの大きな処理能力に頼って実現されており、配列情報の高速処理技術は十分に確立していない。そして、配列解析の研究が進み、創薬および医療などの現場での分子生物学の実用化が進展するのにつれて、配列情報処理の高速化の重要性も高まると考えられる。また、大型コンピュータではなく、パーソナルコンピュータ程度の比較的小型なコンピュータによっても、大量の配列情報を高速に処理することが求められる。
【０００８】
本発明は上記課題に鑑みてなされたものであり、その目的は、配列情報の処理を高速化する方法および装置を提供することにある。
【０００９】
本発明の一つの目的は、ＳＮＰＳ解析で見られるような複数の配列情報の比較を高速に行うことが可能な方法および装置を提供することにある。
【００１０】
本発明の一つの目的は、ブラスト解析で見られるような配列情報中の特定配列の検索を高速に行うことが可能な方法および装置を提供することにある。
【００１１】
本発明の一つの目的は、ファスタ解析で見られるような複数の配列情報の連続一致部分の探索を高速に行うことが可能な方法および装置を提供することにある。
【００１２】
【課題を解決するための手段】
（１）上記目的を達成するため、本発明の配列情報処理方法は、並列照合機能をもつ記憶処理装置に、配列情報を被照合データとして用いるために記憶させて、照合データと被照合データを並列処理にて記憶処理装置に照合させて、照合データと被照合データの一致を示す情報を得ることにより、配列解析情報を得る。並列照合機能を利用することで、配列情報の処理における、大量のデータの比較を高速に行うことができ、配列解析を高速化できる。
【００１３】
好ましくは、並列照合機能をもつ記憶処理装置は、ＣＡＭである。従来、ＣＡＭは、インターネットルータの部品として用いられている。本発明は、ＣＡＭのもつ並列照合機能が配列情報の処理に適していることに着目し、大量のデータの比較をＣＡＭに行わせている。これにより、配列解析処理のうちで大きなウエイトを占める部分が、ＣＡＭにより大幅に高速化され、配列解析の高速化が可能となる。
【００１４】
また、ＣＡＭは、インターネットのルータ用の部品として普及しており、比較的安価に、容易に入手できる。さらに、通常のパーソナルコンピュータのようなコンピュータとの接続が容易な点でもＣＡＭは有利である。したがって、本発明は、ルータ用部品として普及しているＣＡＭの特性が、配列情報の処理にも適していることに着目し、ＣＡＭを使って配列情報処理装置を構成したことで、高速性という利点に加えて、低コストで容易に配列情報処理装置を提供できるという利点も得られる。
【００１５】
（２）本発明の特に中心となる一態様は、並列照合機能をもつ記憶処理装置に、複数の配列情報を、被照合データとして用いるために、照合方向と交差する方向を向けて、照合方向に並ぶように記憶させる。そして、本発明は、照合方向に並んで隣接する複数の配列情報のデータを被照合データとして用いて、配列要素を表す文字等のコードとして同一のものが並ぶ同一コード列に対応するデータを照合データとして用いて、照合データと被照合データを並列処理にて記憶処理装置に照合させる。
【００１６】
このように、本発明は、照合方向と交差する方向を向けて配列情報を記憶させるという、記憶処理装置の特徴的な使い方をしている。したがって、被照合データは、照合方向に並んだ複数配列のデータで構成される。そして、照合データとして、同一コード列に対応するデータが用いられる。これら被照合データと照合データの並列照合処理により、複数の配列が一致するか否かが高速に求められる。
【００１７】
本発明は、ＣＡＭで見られるように、記憶処理装置の照合方向の幅が、配列の長さより狭いときに、特に有利である。実際に処理される配列は長いことが多いので、このような場合は頻繁にあり得る。本発明によれば、記憶処理装置の照合方向と交差する方向に配列情報を記憶させるので、長大な配列も記憶処理装置に収容できる。そして、同一コード列に対応する照合データを用いることで、交差方向に記憶される配列の一致性を求められる。そして、この処理が、並列照合処理により高速に行われる。このようにして、本発明によれば、並列照合処理機能をもつ記憶処理装置を利用し、配列解析を好適に高速化できる。
【００１８】
好ましくは、本態様は、上述の処理により、ＳＮＰｓ解析に用いる情報を得る。ＳＮＰｓ解析では、多くの配列を迅速に処理することが求められる。特に、今後、ゲノム創薬およびオーダーメード医療が実用化され、多数のサンプルのＳＮＰｓ解析が必要になると考えられる。そして、大型コンピュータを使わないでも、高速にＳＮＰｓ解析を行えることが望ましい。本発明によれば、このようなニーズに適切に応えることが可能である。
【００１９】
（３）本発明の一態様は、並列照合機能をもつ記憶処理装置に、生物学的な配列情報を、被照合データとして用いるために、照合方向を向けて記憶させる。さらに本発明は、照合対象の配列情報を照合データとして用いて、照合データと被照合データを並列処理にて記憶処理装置に照合させる。この態様では、上述の態様と異なり、配列情報が照合方向を向けて記憶される。したがって、上述の態様に関して説明したような、記憶の方向を異ならせることによる利点は得られない。しかし、本態様でも、並列照合機能を利用した並列処理による高速化という利点が得られる。以下は、本発明のさらに詳細な態様である。
【００２０】
（４）本発明の一態様は、並列照合機能をもつ記憶処理装置に、塩基配列、アミノ酸配列等の生物学的な複数の配列情報を、被照合データとして用いるために、照合方向を向けて記憶させる。そして本発明は、参照配列を照合データとして用いて、照合データと被照合データを並列処理にて記憶処理装置に照合させる。典型的には、部分配列からなる参照配列を用いて、ブラスト検索で行われるような、局所的一致箇所が求められる。本発明によれば、並列照合機能を利用して、複数の配列の各々が参照配列を含むか否かが、高速に求められる。
【００２１】
好ましくは、本発明は、参照配列に相当する長さをもつ照合対象部分と残りの照合除外部分とを設定して照合処理を行い、照合除外部分の位置を異ならせた複数回の照合処理を行う。本発明によれば、照合除外部分を異ならせて照合処理を行うことで、参照配列が、被照合データたる配列のどの部分と一致する場合でも、その一致を適切に検出できる。また、一致する部分の特定も可能となる。
【００２２】
好ましくは、本発明は、一連の配列を複数の分割配列情報に分けて、複数の分割配列情報を、照合方向と交差する方向に並ぶように、並列照合機能をもつ記憶処理装置に記憶させて、各分割配列情報の一部が参照配列と一致するか否かを並列処理により求める。
【００２３】
本発明は、ＣＡＭで見られるように、記憶処理装置の照合方向の幅が狭く、交差方向の長さが大きいときに、特に有利である。本発明によれば、照合方向の幅が狭い場合でも、配列を分割することで、交差方向の長さを活かして、長い配列を記憶可能である。交差方向の長さを利用して、大量の配列を同時に記憶させ、並列して処理することもできる。
【００２４】
さらに、本態様の配列分割は、計算の高速化にとって有利である。分割により、照合方向の配列長さが小さくなる。これにより計算量が少なくなる。上述の複数種類の照合除外部分を設定するとき、照合方向の配列長さが小さい方が、計算量が少なくなる。したがって本発明は、記憶処理装置が照合方向に狭く、交差方向に長いとき、このことを障害とせず、むしろ、配列分割と並列処理により計算量を削減し、配列解析の一層の高速化を可能としている。
【００２５】
好ましくは、本態様は、上述の処理により、ブラスト法等のホモロジー解析に用いる情報を得る。例えば、データベースの大量の配列を使ってブラスト検索を行うような場合、本発明の高速化は特に有用と考えられる。
【００２６】
（５）本発明の一態様は、並列照合機能をもつ記憶処理装置に、同一の配列情報を少しずつずらして、被照合データとして用いるために、照合方向を向けて記憶させる。配列情報は所定文字数ずつ、通常は一文字ずつずらされる。そして、本発明は、比較対象の別の配列情報を照合データとして用いて、少しずつずらして記憶された同一の配列情報を被照合データとして用いて、照合データと被照合データを並列処理にて記憶処理装置に照合させる。
【００２７】
本発明によれば、複数の配列情報が連続して一致する部分が、並列処理を利用して高速に求められる。最長一致部分を求めることも可能であり、また、連続一致部分の位置を特定することも可能である。並列照合機能をもつ記憶処理装置を利用し、少しずつずらして配列を記憶させるという特徴的な使い方により、例えばファスタ検索においてドットマトリックスを用いて得られるのと同様の、連続一致部分の情報を得ることができる。
【００２８】
好ましくは、本態様は、上述の処理により、ファスタ法等のホモロジー解析に用いる情報を得る。例えば、データベースの大量の配列を使ってファスタ検索を行うような場合、本発明の高速化は特に有用と考えられる。
【００２９】
本発明は、上述の方法の態様には限定されない。本発明の別の態様は、例えば、配列情報処理装置である。この装置は、ネットワークを経由してアクセスされるシステムを構成してもよい。分散配置された複数のコンピュータにより本装置および上記方法が実現されてもよい。また、本発明の別の態様は、例えば、上記処理方法をコンピュータに実現させるプログラムであり、また例えば、そのようなプログラムを記録した媒体である。
【００３０】
【発明の実施の形態】
以下、本発明の好適な実施の形態（以下、実施形態という）を図面を参照して説明する。
【００３１】
本実施形態では、配列情報の一形態である塩基配列が処理される。ただし、アミノ酸配列等の他の任意の生物学的配列情報にも本実施形態は同様に適用可能である。
【００３２】
図１は、本実施形態の生物学的配列情報処理装置のハードウエア構成を示す。配列情報処理装置１０は、ＣＰＵ１２、ＲＯＭ１４、ＲＡＭ１６、ＣＡＭ１８、ハードディスク２０、入力装置２２および出力装置２４を含む。
【００３３】
ハードディスク２０は、配列情報処理装置１０の機能を実現するためのプログラムを記憶している。このプログラムがＣＰＵ１２により実行される。また、ハードディスク２０は、解析対象の配列情報を記憶している。ＣＰＵ１２は、ハードディスク２０から配列情報を取得する。配列情報は、他の構成から取得されてもよい。例えば、配列情報は、図示されない記録媒体装着部を介して、ＣＤ−ＲＯＭ、ＤＶＤ等の記録媒体から取得されてもよい。また、配列情報は、通信装置を介して取得されてもよい。通信装置は、インターネット等のネットワークから配列情報を取得してもよい。
【００３４】
入力装置２２は、キーボード、ポインティングデバイス等である。ユーザは、入力装置２２を操作して、各種の指示を入力し、また、配列情報処理装置１０が要求する情報等を入力する。出力装置２４は、ディスプレイ、プリンタ等である。出力装置２４には、解析結果の情報が表示される。また、ディスプレイには、ユーザへの案内画面、例えば入力装置２２を操作するのに必要な画面が表示される。上述のように配列情報を通信装置で取得する場合には、通信装置を出力装置として機能させ、解析結果等の情報も通信装置を介して出力することが好適である。
【００３５】
上述の説明からも明らかなように、配列情報処理装置１０は通常のパーソナルコンピュータの機能を備える。ただし、通常のパーソナルコンピュータとの相違点として、配列情報処理装置１０はＣＡＭ１８を備える。配列情報処理装置１０は、ＣＡＭ１８を好適に利用して、配列情報の解析を高速に行う。
【００３６】
ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）は、本発明の並列照合機能をもつ記憶処理装置の典型的かつ好適な一形態である。ＣＡＭは連想記憶装置ともいわれる。ＣＡＭは、名前、アドレス、相対位置ではなく、情報内容により記憶場所が識別されるデータ記憶装置であり、これにより高速なデータ検索ができる。ＣＡＭは、通常はインターネットのルータにて用いられている。
【００３７】
図２は、インターネットのルータにおけるＣＡＭの機能を示している。ＣＡＭは、ルーティングテーブルを記憶する。ルーティングテーブルは、複数のＩＰアドレスとルータ名を対応付ける。各ＩＰアドレスは、そのＩＰアドレスが付されたデータが転送されるべきルータ名と対応づけられる。照合データとしてＩＰアドレスが入力されたとき、ＣＡＭは、照合データと一致するＩＰアドレスを検索する。この検索は、並列処理にて行われる。そして、ＣＡＭは、照合データと一致するＩＰアドレスと対応付けられたルータ名を出力する。
【００３８】
このように、ＣＡＭは、照合データと被照合データの照合を並列処理にて行い、照合結果を出力することができる。この機能を本発明では並列照合機能という。一方、配列処理では、配列に関する多数のデータ比較が行われる。この種の処理にはＣＡＭの機能が適している。本発明はこの点に着目し、配列に関する多数のデータの比較をＣＡＭに行わせる。これにより、配列解析処理のうちで大きなウエイトを占める部分が、ＣＡＭにより大幅に高速化され、配列解析の高速化が可能となる。
【００３９】
さらに、ＣＡＭは、インターネットのルータ用の部品として普及しており、比較的安価に入手できる。また、通常のパーソナルコンピュータとの接続が容易な点でもＣＡＭは有利である。したがって、本発明によれば、通常はルータに用いられるＣＡＭの特性が配列情報の処理に適していることに着目し、ＣＡＭを使って配列情報処理装置を構成したことで、高速性という利点に加えて、低コストで容易に配列情報処理装置を提供できるという利点も得られる。
【００４０】
ＣＡＭは、並列照合機能をもつ記憶処理装置の典型的かつ好適な一形態である。並列照合機能をもつ他の記憶処理装置が適用されてもよく、同様の高速化が可能である。従来は大量のデータの比較をＲＡＭ上でソフトウエアによって実現していたのと比較して、大幅な高速化が可能となる。
【００４１】
図３は、配列情報処理装置１０の機能ブロック図である。配列処理制御部３０の各種機能は、図１のＣＰＵ１８がプログラムを実行することにより実現される。配列処理制御部３０は、配列情報取得部３２、被照合データ投入部３４、照合データ投入部３６、照合結果取得部３８、照合結果処理部４０、解析情報出力部４２を有する。
【００４２】
配列情報取得部３２は、解析対象の配列情報を取得する。配列情報は、上述のようにハードディスク２０等から取得される。被照合データ投入部３４は、ＣＡＭ１８に被照合データ（被参照データ）を投入する。被照合データはＣＡＭ１８に記憶される。照合データ投入部３６は、照合データ（参照データ）をＣＡＭ１８に投入する。ＣＡＭ１８は、照合データと被照合データを照合し、照合結果を出力する。照合結果は、照合結果取得部３８により取得される。照合結果処理部４０は、照合結果に基づく各種判定等の配列解析のための処理を行う。解析情報出力部４２は、照合結果処理部４０によって得られた配列解析に関する情報を出力するための処理を行う。
【００４３】
以下、配列情報処理装置１０による各種の配列情報処理を説明する。
【００４４】
（１−１）ＳＮＰｓ解析
図４は、本実施形態のＳＮＰｓ解析を示している。遺伝子配列は、平均して１０００個の塩基配列に１塩基の割合で、個人によって異なるといわれる。ＳＮＰｓは、複数のサンプル配列を比較して、この異なる配列があるのを検出する。
【００４５】
図４を参照すると、ＣＡＭ１８には、配列処理制御部３０から送られた複数の配列が記憶される。ここで、通常のインターネットルータ等におけるＣＡＭの使用法では、照合されるべきデータは、ＣＡＭの照合方向に記憶される（図２）。本発明では、図示のように、配列情報が、照合方向と交差する方向を向けて、照合方向に並ぶように記憶される。
【００４６】
なお、記憶の順番は任意である。１本目の配列の第１文字が記憶され、２本目の配列の第１文字が記憶され、というように照合方向に順次データが記憶されてもよい。また、１本目の配列の第１文字、第２文字、というように、交差方向に順次データが記憶されてもよい。結果的に、図４に示されるように、各配列が交差方向を向いていればよい。
【００４７】
現在提供されているＣＡＭの照合方向の幅には、１４４ｂｉｔタイプ、２８８ｂｉｔタイプというように、幾つかのタイプがある。一度に処理できる配列の数は、ＣＡＭの幅に制約される。通常のＣＡＭ、例えば上記の１４４ｂｉｔタイプのＣＡＭを用いる場合、１００程度の配列を入力可能である。
【００４８】
次に、照合データとして、同一文字列のデータが入力される。周知のように、塩基は、Ａ（アデニン）、Ｔ（チミン）、Ｇ（グアニン）、Ｃ（シトシン）の４文字で表される。まず、照合データ（ＡＡＡＡ・・・）が入力される。
【００４９】
ＣＡＭ１８は、照合データと各被照合データの照合を行う。被照合データは、照合方向に並んだ文字列である。上述のように、本実施形態では、照合方向と交差する方向を向けて配列が入力されている。したがって、被照合データは、各配列の一つの文字が並んだデータである。
【００５０】
ＣＡＭ１８は、照合データと被照合データが完全に一致したとき、一致を示す情報を出力する。本実施形態では「１」が出力される。本実施形態では、ＣＡＭ１８が、インターネットのルーティングテーブルのルータ名に相当する位置に「１」を記憶しており、この「１」が出力される。一致しない場合には、「０」が出力される。
【００５１】
ここでは、照合データが「ＡＡＡ・・・」であるから、被照合データの文字がすべて「Ａ」であるとき、「１」が出力される。他の文字「Ｔ」「Ｇ」「Ｃ」についても順次同様の処理が行われる。
【００５２】
図４の右側部分は、照合結果を示している。被照合データが同一文字のみで構成されるときは、いずれかの照合データ（Ａ、Ｔ、ＧまたはＣ）を用いた照合結果として「１」が出力される。しかし、被照合データが異なる文字を含むときは、すべての照合データを用いた処理にて「０」が出力される。これは、入力された複数の配列が、多型により異なる配列を含むことを意味する。このようにして、異なる配列の有無が検出される。
【００５３】
異なる配列の有無を判定するためには、照合結果の論理演算（ｂｉｔ演算）が好適に行われる。ここでの論理演算は、１＊０＝１、０＊１＝１、１＊１＝１、０＊０＝０である。この演算は、各列ごとに、４回の照合結果に対して行われる。２つの照合結果が演算され、それにもう一つの照合結果が加えられ、さらにもう一つの照合結果が加えられる。この演算結果は、図４の左方に示すように、被照合データが同一文字のみで構成されるときは「１」であり、異なる文字を含むときは「０」である。このようにして、異なる配列の有無が特定され、さらに、異なる塩基の位置が特定される。
【００５４】
次に、複数の塩基配列のどれが他の配列と異なるのかを特定する処理を説明する。この処理では、被照合データにＤｏｎ’ｔ  Ｃａｒｅ  ｂｉｔ（以下、ＤＣｂｉｔ）を設定する。
【００５５】
ここで、ＤＣｂｉｔは、被照合データのうちで特定の位置のデータを無視した部分データによって一致検索を行うためのものである。本実施形態では、ＤＣｂｉｔは、無視されるべき文字の位置、または、無視されるべき文字そのものである。この無視により、被照合データが部分的に照合から除外される。
【００５６】
図５は、ＤＣｂｉｔの設定のパターンを示している。ＤＣｂｉｔが設定された位置の配列は、照合対象から除外される。図示のように、ＤＣｂｉｔを順次ずらしていき、上述の図４の処理を行う。他の配列と異なる配列がある位置にＤＣｂｉｔが設定されたときは、図４の処理の結果として、すべての配列が完全に一致するとの判定が得られる。すなわち、左方の論理演算の結果が、すべて「１」になる。このとき、ＤＣｂｉｔが設定された位置の配列が、異なる配列として特定される。
【００５７】
例えば、図４の例では、３本目の配列が、他の配列と異なる。この場合、図５に矢印で示すように、３番目のｂｉｔをＤＣｂｉｔに設定したとき、すべての配列が完全一致する。これにより、３本目の配列が他と異なることが分かる。
【００５８】
図６は、上述したＳＮＰｓ解析の処理を示すフローチャートである。まず、配列処理制御部３０の被照合データ投入部３４は、配列情報取得部３２により取得された配列情報をＣＡＭ１８に投入する（Ｓ１０）。配列情報は、照合方向と交差する方向を向けて記憶される。次に、照合データが照合データ投入部３６により投入される（Ｓ１２）。ＡＡＡ・・・というように、同一文字列が投入される。
【００５９】
ＣＡＭでは、照合データと被照合データの照合が行われ、その結果が出力される。照合データと被照合データが完全に一致すれば「１」が出力され、そうでなければ「０」が出力される。照合結果は、照合結果取得部３８により取得される（Ｓ１４）。
【００６０】
次に、配列処理制御部３０は、全文字（Ａ、Ｔ、Ｇ、Ｃ）についての照合処理が行われたか否かを判定する（Ｓ１６）。終了していなければ、Ｓ１２に戻り、次の文字に関して、同一文字列を照合データとして用いた処理が行われる。
【００６１】
Ｓ１６がＹＥＳであれば、Ｓ１８に進み、照合結果処理部４０によりＳＮＰｓ判定が行われる。ここでは、図４の右側に示される演算処理が行われ、異なる配列の有無と、異なる塩基の位置が特定される。
【００６２】
次に、異なる配列があるか否かが判定され（Ｓ２０）、ＮＯであれば処理を終了する。ＹＥＳの場合、Ｓ２２に進んで、異なる配列がどれかが特定される。
【００６３】
Ｓ２２では、ＤＣｂｉｔが設定される。まず、被照合データの１番目のｂｉｔが、ＤＣｂｉｔに設定される（図５の最上段）。Ｓ２４、Ｓ２６、Ｓ２８の処理は、上述のＳ１２、Ｓ１４、Ｓ１６と同様でよい。すなわち、照合データとして同一文字列がＣＡＭ１８に投入され（Ｓ２４）、ＣＡＭ１８から照合結果が取得され（Ｓ２６）、全文字の照合処理が行われる（Ｓ２８）。
【００６４】
次に、図５に示されるＤＣｂｉｔの全パターンに関して、Ｓ２２〜Ｓ２８の処理が行われたか否かが判定される（Ｓ３０）。ＮＯであれば、Ｓ２２に戻り、ＤＣｂｉｔの設定が変更される。ＤＣｂｉｔの位置は、一つずつずらされる。このようにして、ＤＣｂｉｔを異なる位置に設定したときの照合結果が得られる。すなわち、配列を一つずつ照合対象から除外したときの照合結果が得られる。
【００６５】
Ｓ３０がＹＥＳであれば、Ｓ３２に進み、照合結果処理部４０により異なる配列が特定される。完全一致が得られたときのＤＣｂｉｔの位置が、異なる配列を示している。
【００６６】
以上においては、本発明を分かりやすく説明するため、塩基配列を表現するのに通常用いられる「文字Ａ、Ｔ、Ｇ、Ｃ」を使用した。しかし、本発明の範囲内で、塩基等の要素を表すものであれば、他のコードが用いられてもよいことはもちろんである。
【００６７】
実際のコンピュータでの処理では、文字そのものを扱わず、文字を少ないデータで表現するべきである。塩基は４種類であるので、少なくとも２ｂｉｔのデータによりすべての塩基が表現される。このとき、図４のＣＡＭ１８上では、交差方向に、１文字につき２ｂｉｔのデータが並ぶ。照合方向の列をｂｉｔレベルで考えると、２列が、ＡＡＡ・・・といった被照合データを表す。本発明では、照合処理において、この２列のデータがまとめて処理されてもよい。また、１列ずつ照合処理が行われ、その結果がさらに処理されてもよい。後者のデータ処理も、本発明の同一コード列に対応するデータを照合データとして用いる処理に含まれる。
【００６８】
ＤＣｂｉｔについても、上述の説明では、文字に対してＤＣｂｉｔが設定されていた。実際の処理では、例えば４種類の塩基が２ｂｉｔで表されるとき、上述の説明における１つのＤＣｂｉｔ（＊）がコンピュータ上の２ｂｉｔに対応することはもちろんである。
【００６９】
また、上記においては、本発明を分かりやすく説明するため、通常のＣＡＭ等を表現する形式に従い、図２、図４に示されるように、四角形の図に基づいて本発明を説明した。しかし、実際のＣＡＭ上での物理的なデータの位置は図４等には限定されないことはもちろんである。この点は、他の実施形態においても、もちろん同様である。
【００７０】
また、図６の処理では、異なる配列を見つけるために、ＤＣｂｉｔ設定の全パターンに関して照合処理が行われている。しかし、ＤＣｂｉｔの全パターンを使い終わる前に、異なる配列が見つかった時点で処理を終了してもよい。この場合、一つのパターンの処理を行うたびに、異なる配列が見つかったか否かが判定される。
【００７１】
また、上記の処理では、ＤＣｂｉｔを設定したときの照合は、最初の照合と同じであった。これに対して、より狭い部分を対象として、ＤＣｂｉｔを使った照合が行われてもよい。例えば、異なる塩基のある位置を対象として、照合が行われてもよい。異なる塩基のある位置は、図４の処理で特定可能である（演算結果が０）。
【００７２】
（１−２）欠損・挿入検出
次に、本実施形態の配列解析技術を利用した欠損・挿入検出処理を説明する。周知のように、欠損とは、複数の配列を比較したときに、ある配列に、欠けている塩基があることをいう。また、挿入とは、複数の配列を比較したときに、ある配列が、他の配列にない塩基をもつことをいう。
【００７３】
図７は、本実施形態の処理を示している。図７の処理は、全体的には図４のＳＮＰｓ解析と同様である。ただし、照合結果の判定処理が異なる。
【００７４】
すなわち、図７では、比較対象の複数の配列は、ＣＡＭ１８により、照合方向と交差する方向を向けて、照合方向に並ぶように、記憶される。したがって、被照合データは、各配列の一つの文字が並んだデータである。照合データは、ＡＡＡ・・・といった同一文字列である。照合データが、それぞれの被照合データと比較される。ＣＡＭ１８は、照合データと被照合データが一致すれば「１」を出力し、一致しなければ「０」を出力するようにプログラミングされている。
【００７５】
図７の例では、ｎ列において、３本目の配列に欠損がある。このとき、ｎ−１列およびその前の列では、４文字の照合処理のいずれかにおいて「１」が出力される。一方、ｎ列およびその後の列では、「０」が出力される。
【００７６】
このように、本実施形態の照合処理を行うと、欠損がある位置を境界として、照合データと被照合データが連続して一致する部分と、照合データと被照合データが連続して一致しない部分とが隣接する。挿入がある場合にも、同様の結果が得られる。
【００７７】
したがって、本実施形態によれば、上記のような結果が得られるとき、すなわち、照合データと被照合データが連続して一致する部分と、照合データと被照合データが連続して一致しない部分とが隣接するとき、欠損または挿入があることが分かる。
【００７８】
欠損または挿入に関する判定は、図７の左方に示す論理演算を使って好適に行われる。この論理演算も、図４と同様に、１＊０＝１、０＊１＝１、１＊１＝１、０＊０＝０である。欠損または挿入がある場合、図示のように、論理演算結果は、・・・１１１０００・・・となる。すなわち、照合データと被照合データの連続一致部分と、連続不一致部分とが隣接する。この境界部分に欠損または挿入があることが分かる。
【００７９】
どの配列が欠損または挿入をもつかは、ＤＣｂｉｔを用いて検出可能である。ＤＣｂｉｔを用いた処理は、ＳＮＰｓ解析と同様でよい。ＤＣｂｉｔを設定することにより、一つの配列が照合対象から除外される。ある位置にＤＣｂｉｔを設定したときに論理演算結果が変わり、連続一致部分が延長された場合、そのＤＣｂｉｔの位置に対応する配列が欠損または挿入を有する。
【００８０】
すなわち、図７の例では、被照合データの３番目のｂｉｔがＤＣｂｉｔに設定されたとき、論理演算結果が変わり、連続一致部分がｎ列を越えて延長される。これにより、３本目の配列が欠損または挿入をもつことが分かる。
【００８１】
さらに、欠損と挿入のどちらがあるかの判定も可能である。この判定を行うためには、欠損または挿入がある配列情報を、ＣＡＭ１８上で、照合方向と交差する方向に１文字分だけずらす。そして、上述の照合および論理演算を行う。
【００８２】
ここでは、１文字分だけ、図７の下方にシフトしたとする。このとき、ｎ＋１列以降では、照合結果として「１」が出力され、その演算結果も１になる。ｎ列およびその前の列は、結果が逆転し、「０」が得られる。仮に挿入がある場合、上記のような結果は得られない。すなわち、シフトした状態でも、照合結果としては、「１」は出力されない。演算結果も０が連続する。このようにして、シフト状態での照合結果から、欠損と挿入のいずれがあるのかが判明する。
【００８３】
上記の処理と反対に、配列が、図７の上方にシフトされてもよい。この場合、挿入があったとすると、演算結果が変わり、ｎ列以降で１が連続し、ｎ−１列およびその前では０が連続する。欠損の場合には、ｎ列以降も０が連続する。この結果の相違により、欠損と挿入のどちらが発生したかが分かる。
【００８４】
上記の２つのシフト処理では、配列全体がシフトされた。しかし、配列の一部がシフトされてもよい。欠損または挿入がある箇所およびその後の配列部分だけがシフトされてもよい。
【００８５】
また、上記の処理では、１文字の欠損または挿入が検出された。２文字以上の欠損または挿入も同様に検出可能である。文字数分だけ、配列が交差方向にずらされればよい。例えば２文字の欠損等を判定するためには、２文字分、配列が交差方向にずらされる。
【００８６】
図８は、上述の欠損・挿入検出処理のフローチャートを示している。基本的な処理は、図６のＳＮＰｓ解析と同様であるので、適宜、説明を簡略化する。被照合データ投入部３４が配列情報をＣＡＭ１８に投入する（Ｓ４０）。配列情報は、照合方向と交差する方向を向けて記憶される。そして、同一文字列に対応する照合データが照合データ投入部３６により投入される（Ｓ４２）。ＣＡＭ１８での照合結果が照合結果取得部３８により取得される（Ｓ４４）。そして、配列処理制御部３０は、全文字（Ａ、Ｔ、Ｇ、Ｃ）についての照合処理が行われたか否かを判定する（Ｓ４６）。終了していなければ、Ｓ１２に戻る。
【００８７】
Ｓ４６がＹＥＳであれば、Ｓ４８に進み、照合結果処理部４０により、欠損または配列があるか否かが判定される。ここでは、図７を用いて説明したように、照合結果処理部４０は、照合データと被照合データが連続して一致する部分と、照合データと被照合データが連続して一致しない部分とが隣接するとき、欠損または挿入があると判定する。欠損または挿入がないとき、Ｓ５０の判定がＮＯになり処理が終了する。
【００８８】
欠損または挿入があるとき、Ｓ５２に進んで、欠損または挿入をもつ配列が特定される。Ｓ５２では、ＤＣｂｉｔが設定される。Ｓ５４、Ｓ５６、Ｓ５８の処理は、上述のＳ４２、Ｓ４４、Ｓ４６と同様でよい。そして、ＤＣｂｉｔの全パターンに関して、Ｓ５２〜Ｓ５８の処理が行われたか否かが判定される（Ｓ６０）。ＮＯであれば、Ｓ５２に戻り、ＤＣｂｉｔの設定が変更される。Ｓ６０がＹＥＳであれば、Ｓ６２に進み、欠損または挿入をもつ配列が特定される。
【００８９】
なお、図６に関して説明した通り、すべてのＤＣｂｉｔのパターンに関して照合処理が行われなくてもよい。すなわち、１つのパターンに対する照合結果に基づき、欠損または挿入をもつ配列が見つかったか否かが判定され、見つかった時点でこの特定処理を終了してもよい。
【００９０】
次に、Ｓ６４に進み、欠損と挿入のどちらがあるのかが判定される。Ｓ６４では、欠損または挿入をもつ配列が、ＣＡＭ１８上で、照合方向と交差する方向にシフトされる。そして、Ｓ６６〜Ｓ７０の照合処理が行われる。Ｓ６６、Ｓ６８、Ｓ７０の処理は、それぞれ、Ｓ４２、Ｓ４４、Ｓ４６と同様でよい。この照合結果に基づき、上述のようにして、欠損と挿入のどちらがあるのかが判定される（Ｓ７２）。
【００９１】
（１−３）置換検出
図９は、本実施形態の配列解析技術を利用した置換検出処理のフローチャートを示している。この処理は、基本的にＳＮＰｓと同様である。元々、ＳＮＰｓは、複数の配列における１塩基の置換を求めるものである。したがって、ＳＮＰｓに関して説明した処理を適用することにより置換を検出できる。置換がある場合には、図４に示されるように、照合データと被照合データが連続して一致し、照合データと被照合データが一致しない部分があり、再び照合データと被照合データが連続して一致する。このような照合結果が得られたとき、置換があることと、その位置が特定される。以上のようにして、本発明によれば置換の検出が可能である。
【００９２】
図９は、基本的に図６とほぼ同様なので、その説明は省略する。ただし、置換検出の場合、あらかじめ、欠損などの配列長が異なるサンプルを特定し、データ中から排除することが好適である。そこで、Ｓ８０では、同じ配列長をもつ複数の配列が被照合データとして用いるためにＣＡＭ１８に投入される。
【００９３】
以上、ＳＮＰｓ解析および変異（欠損、挿入および置換）検出を取り上げて、ＣＡＭを有効に利用した本発明の配列解析処理を説明した。ＣＡＭは、通常、照合方向の幅が比較的狭い。例えば、１４４ｂｉｔおよび２８８ｂｉｔが、通常のＣＡＭの幅である。このような狭い幅には、遺伝子等の比較的長い配列情報は収まらない。そこで、本発明では、ＣＡＭに、照合方向と交差する方向を向けて配列情報を記憶させる。この交差方向の長さは、通常のＣＡＭでも非常に長い。これにより、長い配列をＣＡＭに収容することを可能としている。さらに、同一文字列に対応する照合データを用いることで、ＣＡＭによる配列比較を実現している。このようにして、本発明は、ＣＡＭの並列処理による高速照合機能の配列解析への活用を可能とし、配列解析の高速化を可能としている。
【００９４】
なお、本発明の配列処理は、本発明の範囲内で実現可能な限り、ＳＮＰｓ解析および変異検出以外の配列解析に適用されてもよい。
【００９５】
本発明の処理の計算量と、従来の配列処理の計算量を、単純化された例を使って比較する。塩基は４種類の文字で表される。ｎ文字の配列を比較するとき、従来の処理の計算量は、概略的には、４のｎ乗で表される。文字数ｎが増えると、大幅に計算量が増大する。
【００９６】
一方、本発明では、記憶処理装置（ＣＡＭを含む）の並列照合機能が適切に利用され、同一文字列に対応する照合データが記憶処理装置に投入される。４種類の文字に対応して、４つの照合データが順次、投入される。したがって、本発明の処理の計算量は、４回の照合に相当する。文字数ｎが増えたときにも計算量があまり増大しない。したがって、本発明は、従来の処理と比較して、計算量を大幅に低減できる。
【００９７】
ここで、本発明は、既に述べたように、塩基配列に限らず、アミノ酸配列等の、他の生物学的配列情報の処理にも同様に適用可能である。そして、本発明の利点は、特に、配列要素の種類（一般には文字の種類）が多い場合ほど、顕著に得られる。以下、この利点について詳細に説明する。
【００９８】
上記の単純化された例を再び用いる。塩基は４種類の文字で表され、天然のアミノ酸は２０種類の文字で表される。ｎ文字の配列を従来の処理で比較するとき、塩基配列比較の計算量は４のｎ乗で表される。アミノ酸配列比較の計算量は２０のｎ乗で表される。したがって、アミノ酸配列の計算量は、塩基配列の計算量の、「５のｎ乗」倍である。このように、従来の処理では、配列要素の種類が増えると、計算量が大幅に増加する。
【００９９】
一方、本発明は、記憶処理装置（ＣＡＭを含む）の並列照合機能を利用しているので、上記の例において、アミノ酸配列の計算量は、塩基配列の計算量の５倍（２０÷４）にしかならない。
【０１００】
すなわち、本発明では、同一文字列に対応するデータが照合データとして記憶処理装置に投入される。塩基の場合、４種類の文字に対応して、４つの照合データが投入される。アミノ酸の場合、２０種類の文字に対応して、２０の照合データが投入される。したがって、計算量は５倍にしかならない。このように、配列要素の種類数に応じた計算量の増大に関して、本発明の方が従来処理より明らかに増大の程度が小さい。
【０１０１】
上記の例は単純化されており、精密な計算量は表してはいない。それでも、上記の例から明らかなように、本発明の処理の計算量は従来の処理より大幅に少ない。したがって本発明は、従来の処理配列処理を有利に高速化できる。
【０１０２】
（２）ブラスト検索
次に、本発明のもう一つの実施形態を説明する。上述の実施形態では、配列情報が、ＣＡＭの照合方向と交差する方向を向けて、ＣＡＭに記憶された。本実施形態では、照合方向を向けて配列情報が記憶される。ただし、配列情報は、ＣＡＭの照合方向の幅よりも長いことが多い。そこで、このような場合に、本実施形態では、配列が複数に分割され、ＣＡＭの複数の列を使って配列情報が記憶される。これにより、本発明は、長い配列をＣＡＭで処理可能としている。
【０１０３】
本実施形態では、本発明の配列処理が、ブラスト検索へと適用される。ブラスト検索は、ホモロジー検索の一つである。ブラスト検索では、ギャップの挿入を行わずに局所的によく一致する部位が探索される。このような部位を高スコア断片と呼ぶ。そして、高スコア断片が前後に伸長される。本実施形態では、一連のブラスト検索のうちで、高スコア断片を検索する処理に、本発明が適用される。
【０１０４】
図１０は、ホモロジー検索の比較対象である２つの配列の例を示している。配列の全長は相当に長く、ＣＡＭの照合方向の幅を越えている。
【０１０５】
図１１は、ＣＡＭ１８に配列を記憶させた状態を示している。各配列は、複数の分割配列へと分割され、各分割配列が、ＣＡＭの１つの列に記憶されている。塩基は４種類であるから、２ｂｉｔで表現される。図１１の例では、一つの分割配列が６０の塩基を含むので、一つの分割配列の長さは１２０ｂｉｔである。したがって、例えば、１４４ｂｉｔの幅をもつＣＡＭを使うことで、図１１の状態での配列の記憶が可能である。
【０１０６】
ブラスト検索では、高スコア断片を探すとき、部分配列からなる参照配列が用いられる。参照配列は比較的短く、例えば図示のように９文字で構成される。参照配列と一致する部分配列が、サンプル配列に含まれるか否かが問い合わされる。この処理が、本実施形態では、ＣＡＭを用いて行われる。
【０１０７】
すなわち、図１１に示すように、本実施形態では、照合データとして、参照配列がＣＡＭ１８に投入される。ＣＡＭ１８は、照合データと各列の被照合データとを並列処理にて比較する。照合データと被照合データが一致するとき、ＣＡＭ１８は「１」を出力し、一致しなければ、ＣＡＭ１８は「０」を出力する。この照合結果より、検索対象の各配列に参照配列が含まれるか否かが分かる。
【０１０８】
参照配列を照合データとして用いる照合処理は、ＣＡＭ１８の特性に基づき、ＤＣｂｉｔを用いて行われる。
【０１０９】
図１２を参照すると、本実施形態では、被照合データに、図示のようなＤＣｂｉｔ（＊）が与えられる。すなわち、参照配列の長さに相当する部分を除いた残りの部分にＤＣｂｉｔが与えられる。ＤＣｂｉｔが与えられた部分は、照合の対象から除外される。ＤＣｂｉｔが与えられない部分が、照合の対象になる。
【０１１０】
ＤＣｂｉｔの位置は、順次ずらされていく。言い換えれば、ＤＣｂｉｔが与えられない部分（照合対象部分）が順次、１文字ずつシフトされる。このようにして、本発明によれば、照合除外部分の位置を異ならせた複数回の照合処理が行われて、被照合データのどの部分が参照配列と一致するときでも、その一致を検出できる。また、参照配列と一致する場所を特定することも可能である。
【０１１１】
ＤＣｂｉｔをずらしたときの複数回の照合結果は、論理演算を用いて好適に処理される。
【０１１２】
図１３の上方部分を参照する。本実施形態では、上述のように、ＤＣｂｉｔ設定の各パターンを使って複数回の照合が行われる。照合の度に、１または０がＣＡＭ１８から出力される。１は、照合データと被照合データが一致するとき、０は一致しないときに出力される。
【０１１３】
全パターンの照合結果に対して、論理演算が行われる。論理演算は、１＊０＝１、０＊１＝１、１＊１＝１、０＊０＝０である。２つの照合結果が演算され、さらにもう一つの演算結果が加えれば、これが繰り返される。最終的な演算結果が１であれば、いずれかのパターンを使った照合にて、完全一致が得られている。そうでなければ、最終的な演算結果は０である。したがって、演算結果が１であれば、被照合データに参照配列が含まれることが分かる。
【０１１４】
図１３の下方は、複数の参照配列がサンプル配列に含まれるか否かを判定するための好適な処理を示している。
【０１１５】
参照配列は、Ａ、Ｂ、Ｃの３つであるとする。各参照配列に関して、図１３の上方の処理により、ＣＡＭ１８の各列が参照配列と一致する部分配列をもつか否かの情報が得られる。一致部分があれば「１」、なければ「０」である。この各列の結果が、論理演算にかけられる。すなわち、図１３では、縦方向に演算が進められる。演算は、上述と同様に、１＊０＝１、０＊１＝１、１＊１＝１、０＊０＝０である。これにより、いずれか一つの列が参照配列を含むと、演算結果が１になる。そして、全部の参照配列の演算結果が１であれば、すなわち、図示のように１が並べば、すべての参照配列がサンプル配列に含まれる。演算結果として０が得られるとき、該当する参照配列は含まれない。
【０１１６】
上記の処理の利点を説明する。図１３の例では、参照配列が比較的少ない。しかし、ブラスト検索では、より多くの参照配列が使われることがある。このとき、多数の照合結果を、一連の処理途中で保持しておく必要が生じ、保持するデータが多くなる傾向がある。本発明によれば、上述の処理により、データ量が多くなるという問題に好適に対処できる。
【０１１７】
本発明は、並列処理を好適に利用したことで、参照配列の検索処理を高速化可能である。この点について、通常の処理の計算量と本発明の処理の計算量を概略的に比較する。
【０１１８】
ここでは、数万から数十万といった大量の遺伝子配列を格納したデータベースを用いてブラスト検索を行う場合を考える。データベースの遺伝子配列の数をＮｃ、一つの配列の塩基数をＬｃ、参照配列の塩基数をＲｌとすると、従来の処理の計算量は、Ｎｃ＊（Ｌｃ−Ｒｌ）で表される。
【０１１９】
一方、本発明においては、各分割配列のデータ長をＣｃとし、参照配列の塩基数をＲｌとすると、計算量は、Ｃｃ−Ｒｌで表される。この式には、配列全体のデータ長Ｌｃが含まれていない。本発明では、遺伝子配列を分割した分割配列が検索対象となるからである。また、上記の式には、配列の数Ｎｃが含まれていない。これは以下の理由による。ＣＡＭは、通常はインターネットのルータの部品として用いられ、大量のＩＰアドレスを並列検索が可能な状態で記憶するように構成される。したがって、ＣＡＭは、照合方向の幅は比較的短いが、それに交差する方向には非常に長い。この点を利用することにより、数万以上の遺伝子配列を、交差方向に並べて同時に記憶し、同時に並列処理できる。したがって、本発明の計算量の式には、遺伝子配列の数Ｎｃは含まれていない。
【０１２０】
上述のように、概略的には、従来の処理の計算量は、Ｎｃ＊（Ｌｃ−Ｒｌ）で表され、本発明の処理の計算量はＣｃ−Ｒｌで表される。遺伝子配列の数Ｎｃは、通常、数万から数十万である。また、一配列の塩基数Ｌｃは、１０００〜１００００個程度である。また、参照配列の塩基数Ｒｌは２０程度である。さらに、分割配列のデータ長Ｃｃは１００程度（図１１の例では６０）とする。この場合、両者の計算量を比較すると、本発明の処理の計算量は、概略的には、例えば約１００００分の１である。
【０１２１】
このようにして、本発明によれば、配列検索の高速化が可能になる。そして、上記説明から明らかなように、本発明は、ＣＡＭの特性を好適に利用している。すなわち、照合方向と交差する方向の長さを利用して、大量の遺伝子が同時に被照合データとして格納される。さらに、照合方向の幅が短いことを不利とせずに、むしろ、複数の分割配列を並列にて処理することで計算量を削減している。こうして、上述の大幅な高速化が可能となる。
【０１２２】
図１４は、上述のブラスト検索の処理を示すフローチャートである。まず、配列処理制御部３０の被照合データ投入部３４は、配列情報取得部３２により取得された配列情報をＣＡＭ１８に投入する（Ｓ１１０）。配列情報は、前述のように複数の分割配列情報に分割され、各分割配列情報がＣＡＭの一つの列に記憶される。ＤＣｂｉｔが設定され（Ｓ１１２）、照合データが照合データ投入部３６により投入される（Ｓ１１４）。ここでは、まず、一つ目のパターンのＤＣｂｉｔが設定される。また、照合データは、参照配列である。ＣＡＭ１８では、照合データと各列の被照合データの照合が行われ、その結果が出力される。照合データと被照合データが完全に一致すれば「１」が出力され、そうでなければ「０」が出力される。照合結果は、照合結果取得部３８により取得される（Ｓ１１６）。
【０１２３】
次に、配列処理制御部３０は、ＤＣｂｉｔの全パターンについての照合が行われたか否かを判定する（Ｓ１１８）。ＮＯであれば、Ｓ１１２に戻り、ＤＣｂｉｔのパターンが変更される。本実施形態では、前述のように、ＤＣｂｉｔの位置が順次シフトされる。
【０１２４】
Ｓ１１８がＹＥＳであれば、Ｓ１２０に進み、配列処理制御部３０は、すべての参照配列に関して照合処理が終了したか否かを判定する。例えば、図１３の参照配列Ａ、Ｂ、Ｃの全部が処理されたか否かが判定される。Ｓ１２０がＮＯであれば、Ｓ１１２に戻り、次の参照配列を使って照合が行われる。Ｓ１２０がＹＥＳであれば、Ｓ１２２に進む。Ｓ１２２では、図１３を用いて説明したように、照合結果処理部４０が、照合結果を使った論理演算を行い、各参照配列がサンプル配列に含まれるか、そして、全部の参照配列がサンプル配列に含まれるかを判定する。なお、上記の処理は、複数のサンプル配列の各々に対して行われる。
【０１２５】
好ましくは、本実施形態の配列情報処理装置１０は、上記の参照配列の問合せ結果を利用して、その後の処理、すなわちブラスト検索の残りの処理を行うように構成される。この残りの処理は、別の装置で行われてもよい。
【０１２６】
ところで、本実施形態は、上述のように、一つの配列を複数の分割配列に分けている。したがって、分割箇所にて、参照配列（参照配列と一致する部分配列を意味する）が複数の分割配列に跨ることがあり得る。このような参照配列は、以下の処理により好適に検出される。
【０１２７】
図１５を参照する。本実施形態では、参照配列の端の部分を照合データとして用いた照合処理が行われる。参照配列の後方の部分が、被照合データである分割配列の前方部分と一致するか否かが、求められる。図示のように、参照配列の後方の１文字を使う照合、２文字を使う照合・・・ｉ−１文字を使う照合が行われる。ｉは、参照配列の文字数である。照合対象以外の部分には、上述の処理で説明したのと同様に、ＤＣｂｉｔが設定される。実際の処理では、ＤＣｂｉｔのパターンを増やせばよい。すなわち、図２において、参照配列が被照合データの前方部分からはみ出る場合についてもＤＣｂｉｔのパターンが設定されればよい。これにより、上述の照合処理をそのまま適用可能となる。
【０１２８】
また、同様にして、参照配列の前方の部分が、被照合データである分割配列の前方部分と一致するか否かが、求められる。
【０１２９】
そして、上記の処理により、第ｎ＋１列の前方部分に、参照配列の後方部分があったとする。また、第ｎ列の後方部分に、参照配列の前方部分があったとする。両部分を連結すると、参照配列が得られるか否かが判定される。ここでは、２つの部分の文字数が参照配列の文字数と一致するか否かが判定されてもよい。参照配列が得られるとき、参照配列と同じ部分配列がサンプル配列に含まれると判定される。
【０１３０】
この判定処理は、実際のプログラムでは、以下のようにして好適に行われる。ここでも論理演算を利用する。参照配列の一部を使った照合により、被照合データと照合データが一致するとき、ＣＡＭ１８は「１」を出力し、そうでなければＣＡＭ１８は「０」を出力する。以下の２つの照合結果が論理演算にかけられる。
【０１３１】
（１）第ｎ列の後方部分を、参照配列の前方のｋ文字と照合した結果
（２）第ｎ＋１列の前方部分を、参照配列の後方のｉ−ｋ文字と照合した結果
論理演算は、１＊１＝１、１＊０＝０、０＊１＝０、０＊０＝０である。演算結果が１であれば、参照配列と同じ部分配列がサンプル配列に含まれる。演算結果が０であれば、参照配列と同じ部分配列はサンプル配列に含まれない。１≦ｋ≦ｉ−１の範囲で、上記の処理が行われる。このようにして、２つの分割配列に跨る参照配列が好適に検出される。
【０１３２】
図１６は、分割箇所の参照配列を検出するもう一つの処理を示している。この処理は、隣接する分割配列を部分的に重複させる。重複文字数は、ｉ−１である。ここで、ｉは、参照配列の文字数である。この状態で、上述の照合処理を行えば、分割箇所の参照配列が、漏れることなく検出される。
【０１３３】
図１６の処理では、参照配列の長さに応じて、重複部分の文字数を変更する必要がある。この点に関しては、ＤＣｂｉｔを利用することで対応可能である。すなわち、過剰な重複を避けるために、過剰な部分にＤＣｂｉｔを設定する。例えば、２０文字の参照配列Ａと、１５文字の参照配列を使うとする。重複部分の文字数は、適当に、例えば３０文字に設定される。参照配列Ａを使うときは、被照合データの後方部分の１１文字に対してＤＣｂｉｔが設定される。参照配列Ｂを使うときは、被参照データの後方部分の１６文字に対してＤＣｂｉｔが設定される。このようにして、参照配列の長さに応じた処理が実現される。
【０１３４】
ただし、上記のような対応が不要な点では、図１６の処理よりも、図１５の処理が有利と考えられる。
【０１３５】
以上、本実施形態の配列処理を説明した。本実施形態では、本発明が、ブラスト検索に適用された。本発明は、他の配列解析に適用されてもよい。本発明は、例えば、コンセンサス配列検索、遺伝子地図、ＳＮＰｓ配列検出に適用されてよい。各解析に応じて、上述の実施形態の処理が変更されることはもちろんである。例えば、ＳＮＰｓの場合、ＤＣｂｉｔは設定されなくてよい。
【０１３６】
（３）ファスタ検索
次に、本発明のもう一つの実施形態を説明する。本実施形態でも、上述の実施形態と同様、配列情報は、ＣＡＭの照合方向を向けて記憶される。本実施形態では、ＣＡＭの特性を利用し、並列処理により、複数の配列が連続して一致する部分を求める。この連続一致部分の検出は、ファスタ検索に適している。
【０１３７】
まず、従来のファスタ検索を概略的に説明する。
【０１３８】
図１７、図１８は、ドットマトリックス画像を示している。ドットマトリックス画像は、従来のファスタ検索において、複数の配列の連続一致部分を求めるために用いられる。図１７は概念図であり、図１８は実際のドットマトリックス画像の例である。
【０１３９】
ドットマトリックス画像では、２つの配列が直交して配置される。２つの配列の文字（要素）が一致する箇所には点が打たれる。４５度方向に点が連続するとき、その部分では、配列の文字が連続して一致している。この特徴を利用して、最も長く連続して一致する部分が求められる。そして、一致部分の周囲に対して動的計画法によるアライメントが行われる。
【０１４０】
本実施形態は、ＣＡＭを利用し、上述のドットマトリックス画像を利用したときと同様の情報を得る。
【０１４１】
図１９は、本実施形態の処理を示している。ここでは、説明を簡単にするために、配列は分割されていない。しかし、実際には、後述するように、ＣＡＭの幅が狭いことを考慮して、配列を複数に分割することが好適である。
【０１４２】
図１９の例では、比較対象の配列は２本、すなわち配列１および配列２である。配列１は、被照合データとしてＣＡＭ１８に記憶される。配列２は、照合データとしてＣＡＭ１８に投入される。
【０１４３】
配列１は、図示のように、ＣＡＭ１８の複数の列に記憶される。すなわち、同一の配列が、ＣＡＭ１８上の複数の列に記憶される。ただし、列によって、配列１が照合方向にずらされる。配列１は、１文字ずつずらされる。
【０１４４】
このように配列１が記憶された状態で、配列２が照合データとして入力される。ＣＡＭ１８は、照合データと、各列の被照合データとを比較する。両者が一致するとき、「１」が出力され、一致しないとき、「０」が出力される。
【０１４５】
上記の処理では、配列全体が一致する場合が検出される。各種の長さの連続一致部分は、以下のようにして検出される。
【０１４６】
図２０は、各種の長さの連続一致部分を検出する処理を示す。図示のように、ＤＣｂｉｔ（＊）が利用される。ＤＣｂｉｔは、照合除外部分をつくるために利用される。
【０１４７】
最上段では、ＤＣｂｉｔが設定されていない。２段目では、被照合データの後端にＤＣｂｉｔが１つ設定される。３段目では、被照合データの前端にＤＣｂｉｔが１つ設定される。２段目および３段目のパターンを用いて照合を行うと、配列の長さより１文字分短い連続一致部分の有無が検出される。
【０１４８】
同様にして、配列の長さよりｎ文字分短い連続一致部分を検出するためには、ｎ個のＤＣｂｉｔが設定される。ｎ個のＤＣｂｉｔは、図２０に示されるように、配列の両端に振り分けられる。振分けの全組合せが、ＤＣｂｉｔの設定パターンとして用いられる。
【０１４９】
このようにして、本実施形態によれば、配列を部分的に照合対象から除外することで、各種の長さの連続一致部分が検出される。そして、最も長く配列が連続する部分も求めることができる。
【０１５０】
上記の処理において、最長一致部分を見つけるためには、すべての種類の長さの連続一致部分を検出する処理が行われなくてもよい。ＤＣｂｉｔを順次変えていき、最長一致部分が見つかるまで、検出対象の一致長さを順次短縮していく。ここでは、図２０のＤＣｂｉｔのパターンを、上方から下方へ順番に使用する。そして、照合データと被照合データが一致したとき、最も長い配列が見つかったので、処理を終了する。このような処理も好適である。
【０１５１】
図２１は、配列を複数に分割するときの処理を示している。配列１は、ＣＡＭ１８の幅より短く分割され、そして、ＣＡＭ１８の複数の列に分けて記憶される。同一の配列が、１文字ずつずらして、ＣＡＭ１８上の複数の領域に記憶される。ずらし量の最大値は、（分割配列の長さ−１）に設定される。それ以上ずらすと、同じ被照合データが重複するからである。
【０１５２】
配列２は、配列１と同様に分割される。そして、各分割配列が、順次、照合データとしてＣＡＭ１８に入力される。したがって、ＣＡＭ１８は、配列２の各分割配列を用いて、照合処理を行う。一つの分割配列を用いるときの処理は、図１９および図２０を参照して説明した処理でよい。
【０１５３】
なお、図２１にＸ印で示すように、配列をずらすと、ＣＡＭの列上で、文字データのない部分が生じる。この部分は適当に処理対象から除外される。Ｘ印をもつ列全体が削除されてもよい。この削除を行ったとしても、図１８の隅の領域が検索対象から除外されるだけなので、問題はないと考えられる。
【０１５４】
また、分割処理に関しては、各分割配列に分けて処理が行われてもよい。すなわち、まず、配列１、２の一つ目の分割配列が選択される。配列１の分割配列が、図１９のようにＣＡＭ１８に配置される。配列２の分割配列を用いて、図１９に関して説明した処理が行われる。次に、配列１、２の２つ目の分割配列が選択され、同様の処理が行われる。このような処理でも同様の結果が得られる。
【０１５５】
ところで、配列の連続一致部分が、複数の分割配列に跨ることがある。この点については、以下のようにして対応する。
【０１５６】
図２２を参照すると、ｎ列の後方部分およびｎ＋１列の前方部分に、連続一致部分が存在するとき、それらが連結される。連結状態での配列部分が、配列１の最も長い連続一致部分であるか否かが判定される。この処理をより正確に行うためには、ある分割配列の端部が１文字のみ一致する場合も、その分割配列を連結の対象とすることが好適である。また、図示されないが、連続一致部分が、３本以上の分割配列に跨ることもあり得る。この場合には、それら分割配列がすべて連結される。両側の連続一致部分（分割配列長より短い、１本または０本の場合もある）と、それらの間の連続一致部分（分割配列長と同じ長さ、１本または複数本）とが連結される。
【０１５７】
図２３は、上述した本実施形態の処理を示すフローチャートである。まず、配列処理制御部３０の被照合データ投入部３４は、配列情報取得部３２により取得された配列情報をＣＡＭ１８に投入する（Ｓ１３０）。配列情報は、図２１に示されるように、複数に分割されて投入される。また、同一の配列が、少しずつずらして、投入される。次に、照合データが照合データ投入部３６により投入される（Ｓ１３２）。照合データは、配列２の分割配列である。そして、ＣＡＭ１８により、照合データと被照合データの照合が行われる。まず、ＤＣｂｉｔを設定しないで、照合が行われる。照合データと被照合データが完全に一致すれば「１」が出力され、そうでなければ「０」が出力される。照合結果は、照合結果取得部３８により取得される（Ｓ１３４）。
【０１５８】
次に、配列処理制御部３０は、全長さに関する照合を終了したか否かを判定する（Ｓ１３６）。そして、ＮＯであれば、長さを変更して（Ｓ１３８）、Ｓ１３２に戻る。Ｓ１３６では、図２０のＤＣｂｉｔの全パターンが処理されたか否かが判定される。全パターンが処理されていないとき、Ｓ１３８で、次のパターンが選択される。Ｓ１３６がＹＥＳであれば、Ｓ１４０に進む。
【０１５９】
なお、既に述べたように、本実施形態では、すべての長さに関して、連続一致の判定が行われなくてもよい。この場合、１文字ずつ、順次、検出対象の長さが短縮される。すなわち、図２０のＤＣｂｉｔのパターンが、上から順番に使用される。照合データと一致する被照合データが得られた時点で、Ｓ１４０へ進む。
【０１６０】
Ｓ１４０では、配列処理制御部３０が、配列２の全部の分割配列を処理したか否かを判定する。Ｓ１４０がＮＯであれば、Ｓ１３２に戻り、次の分割配列が処理される。Ｓ１４０がＹＥＳであれば、Ｓ１４２に進み、照合結果処理部４０が、これまでの照合結果を基に、最長一致部分（配列が最も長く一致する部分）を特定する。好ましくは、本実施形態の配列情報処理装置１０は、特定された最長一致部分を使って、その後の処理、すなわちファスタ検索の残りの処理を行うように構成される。この残りの処理は、別の装置で行われてもよい。
【０１６１】
以上のように、本実施形態によれば、ＣＡＭを使って、ドットマトリックスを使うのと同様に、配列の連続一致部分が検出可能であり、最長一致部分も検出可能である。そして、ＣＡＭの並列処理機能を利用して、高速な検索が可能である。
【０１６２】
本実施形態では、２つの配列が比較された。しかし、本発明の範囲内で３つ以上の配列が比較されてもよい。この場合、好ましくは、ＣＡＭの照合方向と交差する方向に、複数の配列が、並べられる。各配列については、図２１に示したように、同一の配列が、すこしずつシフトして、複数箇所に記憶される。そして、照合データとして用いる配列（図２１の配列２）が入力される。これにより、照合データの配列を、複数の配列と同時に比較することができる。
【０１６３】
また、本実施形態では、本発明の情報処理がファスタ解析に適用された。他の配列解析にも本発明が適用されてよい。他の解析においても、配列の連続一致部分を求めるときに、本発明が有利に適用可能である。
【０１６４】
以上、本発明の好適な各種の実施形態を説明した。本実施形態は、本発明の範囲内で変形可能なことはもちろんである。例えば、本実施形態では、塩基配列が処理された。これに対し、本発明の範囲内で、既に述べたように、アミノ酸等の他の配列が処理されてもよい。また、本発明の配列情報処理装置は、ネットワークを介してアクセスされるシステムを構成してもよい。
【０１６５】
【発明の効果】
（１）以上に説明したように、本発明は、並列照合機能をもつ記憶処理装置に、配列情報を被照合データとして用いるために記憶させて、照合データと被照合データを並列処理にて記憶処理装置に照合させて、照合データと被照合データの一致を示す情報を得ることにより、配列解析情報を得る。並列照合機能を利用することで、配列情報の処理における、大量のデータの比較を高速に行うことができ、配列解析を高速化できる。
【０１６６】
好ましくは、並列照合機能をもつ記憶処理装置は、ＣＡＭである。従来、ＣＡＭは、インターネットルータの部品として用いられている。本発明は、ＣＡＭのもつ並列照合機能が配列情報の処理に適していることに着目し、大量のデータの比較をＣＡＭに行わせている。これにより、配列解析処理のうちで大きなウエイトを占める部分が、ＣＡＭにより大幅に高速化され、配列解析の高速化が可能となる。
【０１６７】
また、ＣＡＭは、インターネットのルータ用の部品として普及しており、比較的安価に、容易に入手できる。さらに、通常のパーソナルコンピュータのようなコンピュータとの接続が容易な点でもＣＡＭは有利である。したがって、本発明は、ルータ用部品として普及しているＣＡＭの特性が、配列情報の処理にも適していることに着目し、ＣＡＭを使って配列情報処理装置を構成したことで、高速性という利点に加えて、低コストで容易に配列情報処理装置を提供できるという利点も得られる。
【０１６８】
本発明の並列照合機能付き記憶処理装置はＣＡＭには限定されない。また、通常のＣＡＭは、一つの照合データを、記憶された全部の被照合データと同時に比較するように構成されている。上述の実施形態でも、主としてこのような処理が行われた。これに対し、ＣＡＭまたは他の記憶処理装置は、複数の照合データを同時に利用するように構成されてもよい。そして、照合データによって、相手の被照合データを異ならせる処理が行われてもよい。この構成は、複数の照合データの同時処理を可能とすることでさらなる高速化に寄与する。例えば上述の実施形態のブラスト検索において複数の分割配列を照合データとして用いる場合に有利である。
【０１６９】
本発明の並列照合機能付き記憶処理装置（ＣＡＭを含む）は、プロセッサの一部であってもよい。このプロセッサを利用し、その記憶処理部に本発明の処理を行わせることも、本発明の範囲に含まれる。この種のプロセッサには、図３を用いて説明したような、記憶処理装置を利用するための本発明の処理機能の一部または全部が備えられてもよい。この場合には、プロセッサは本発明の配列情報処理装置（少なくとも一部）を構成する。
【０１７０】
（２）本発明の特に中心となる一態様は、並列照合機能をもつ記憶処理装置に、複数の配列情報を、被照合データとして用いるために、照合方向と交差する方向を向けて、照合方向に並ぶように記憶させる。そして、本発明は、照合方向に並んで隣接する複数の配列情報のデータを被照合データとして用いて、配列要素を表す文字等のコードとして同一のものが並ぶ同一コード列に対応するデータを照合データとして用いて、照合データと被照合データを並列処理にて記憶処理装置に照合させる。
【０１７１】
このように、本発明は、照合方向と交差する方向を向けて配列情報を記憶させるという、記憶処理装置の特徴的な使い方をしている。したがって、被照合データは、照合方向に並んだ複数配列のデータで構成される。そして、照合データとして、同一コード列に対応するデータが用いられる。これら被照合データと照合データの並列照合処理により、複数の配列が一致するか否かが高速に求められる。
【０１７２】
計算量を検討すると、本発明では並列処理機能が適切に利用され、同一文字列に対応する照合データが用いられるので、本発明の処理の計算量は従来の処理よりも大幅に低減される。塩基を想定した単純化された例では、ｎ文字の配列が処理されるとき、従来の処理の計算量は、「４のｎ乗」で表される。「４」は、塩基の種類数である。一方、本発明では、４つの同一文字列の各々を使って照合が行われる。したがって、本発明の処理の計算量は、４回の照合に相当し、従来の処理よりも大幅に少ない。文字数ｎが増大するほど、計算量の差が大きくなる。
【０１７３】
さらに、本発明の利点は、配列要素の種類が多いときに顕著である。上記の例において、天然のアミノ酸を想定したとき、従来の処理の計算量は「２０のｎ乗」で表される。２０は、アミノ酸の種類数である。塩基の例（「４のｎ乗」）と比べると、計算量は、「５のｎ乗」倍である。一方、本発明では、アミノ酸を想定したときは、同一文字列に対応する照合データの数が、２０である。塩基の例と比べると、計算量は、５倍（２０÷４）にしかならない。このように、配列要素の種類数に応じた計算量の増大に関して、本発明の方が従来処理より明らかに増大の程度が小さい。この点でも、本発明は、従来の処理配列処理を有利に高速化できる。
【０１７４】
本発明は、ＣＡＭの例を用いて説明したように、記憶処理装置の照合方向の幅が、配列の長さより狭いときに、特に有利である。実際に処理される配列は長いことが多いので、このような場合は頻繁にあり得る。本発明によれば、記憶処理装置の照合方向と交差する方向に配列情報を記憶させるので、長大な配列も記憶処理装置に収容できる。そして、同一コード列に対応する照合データを用いることで、交差方向に記憶される配列の一致性を求められる。そして、この処理が、並列照合処理により高速に行われる。このようにして、本発明によれば、並列照合処理機能をもつ記憶処理装置を利用し、配列解析を好適に高速化できる。
【０１７５】
好ましくは、本発明は、配列情報を構成する複数種類のコードの各々について、同一コード列に対応するデータを照合データとして用いた照合を行い、複数回の照合結果を処理して、複数の配列情報の一致に関する情報を得る。例えば、塩基配列の場合、上述の実施形態で説明したように、Ａ、Ｇ、Ｔ、Ｃの各コードが照合にかけられる。さらに、好ましくは、上述の実施形態で説明したように、論理演算を用いた処理が行われる。本発明によれば、複数種類の同一コード列を使って照合が行われ、いずれかの同一コード列を使ったときに被照合データと照合データが一致したか否かが判定される。したがって、配列中の各位置のコードが何であるかを意識することなく、同様の処理により、配列が一致するか否かを求められ、処理が簡単になる。
【０１７６】
好ましくは、本発明は、複数の配列情報の一部を照合対象から除外して、照合処理を行う。これにより、他の配列情報と一致しない配列情報を特定することができる。
【０１７７】
好ましくは、本発明は、照合データと被照合データが一致しないとき、多型により他の配列と異なる配列があると判定する。これにより、ＳＮＰｓ等の多型解析ができる。さらに、好ましくは、本発明は、複数の配列情報の一部を照合対象から除外して、照合処理を行う。これにより、ＳＮＰｓ等の多型解析にて、他の配列と異なる配列を特定できる。
【０１７８】
好ましくは、本発明は、照合データと被照合データが連続して一致する部分と、照合データと被照合データが連続して一致しない部分とが隣接するとき、それら部分の境界に欠損または挿入があると判定する。このようにして、本発明によれば、欠損または挿入を検出できる。さらに、好ましくは、本発明は、複数の配列情報の一部を照合対象から除外して、照合処理を行う。これにより、欠損または挿入がある配列情報を特定することができる。
【０１７９】
また、好ましくは、本発明は、欠損または挿入がある配列情報を、照合方向と交差する方向にずらして記憶させて、照合処理を行う。これにより、欠損と挿入のどちらがあるかを判定できる。上述の実施形態を用いて説明したように、欠損がある場合と、挿入がある場合では、シフト時の照合結果が特徴的に異なるからである。
【０１８０】
なお、本発明の範囲内で、欠損または挿入のいずれか一方を検出するために本発明が適用されてもよい。すなわち欠損または挿入のいずれか一方が配列情報処理により検出されてもよい。
【０１８１】
好ましくは、本発明は、照合データと被照合データが連続して一致し、照合データと被照合データが一致しない部分があり、再び照合データと被照合データが連続して一致するとき、一致しない部分に置換があると判定する。このようにして、本発明によれば、置換が検出できる。好ましくは、同一長さの配列のみが比較される。これにより正確な結果が得られる。さらに好ましくは、本発明は、複数の配列情報の一部を照合対象から除外して、照合処理を行う。これにより、置換がある配列情報を特定することができる。
【０１８２】
好ましくは、本態様、すなわち、交差方向に配列を記憶する態様において、並列照合機能をもつ記憶処理装置は、ＣＡＭである。ＣＡＭは、既に述べたように、並列照合機能をもつ点で、配列情報の処理に適した特性をもち、配列解析を高速化できる。また、ＣＡＭは、これまで配列情報処理には用いられていないが、インターネットルータ部品として普及しており、安価である。したがって、ＣＡＭを使うことで、低コストで高速な配列解析が可能となる。さらに、通常のＣＡＭは、照合方向の幅が比較的狭いにも拘わらず、本発明によれば、配列の記憶する方向を照合方向と交差させることで、そして、同一コード列に対応するデータを照合データとして用いることで、長い配列の照合を可能としている。しかも、ＣＡＭの並列照合機能が活かされ、高速な解析が可能となる。
【０１８３】
好ましくは、本態様、すなわち、交差方向に配列を記憶する態様は、上述の処理により、ＳＮＰｓ解析に用いる情報を得る。ＳＮＰｓ解析では、多くの配列を迅速に処理することが求められる。特に、今後、ゲノム創薬およびオーダーメード医療が実用化され、多数のサンプルのＳＮＰｓ解析が必要になると考えられる。そして、大型コンピュータを使わないでも、高速にＳＮＰｓ解析を行えることが望ましい。本発明によれば、このようなニーズに適切に応えることが可能である。
【０１８４】
（３）本発明の一態様は、並列照合機能をもつ記憶処理装置に、生物学的な配列情報を、被照合データとして用いるために、照合方向を向けて記憶させる。さらに本発明は、照合対象の配列情報を照合データとして用いて、照合データと被照合データを並列処理にて記憶処理装置に照合させる。この態様では、上述の態様と異なり、配列情報が照合方向を向けて記憶される。したがって、上述の態様に関して説明したような、記憶の方向を異ならせることによる利点は得られない。しかし、本態様でも、並列照合機能を利用した並列処理による高速化という利点が得られる。以下は、本発明のさらに詳細な態様である。
【０１８５】
（４）本発明の一態様は、並列照合機能をもつ記憶処理装置に、塩基配列、アミノ酸配列等の生物学的な複数の配列情報を、被照合データとして用いるために、照合方向を向けて記憶させる。そして本発明は、参照配列を照合データとして用いて、照合データと被照合データを並列処理にて記憶処理装置に照合させる。典型的には、部分配列からなる参照配列を用いて、ブラスト検索で行われるような、局所的一致箇所が求められる。本発明によれば、並列照合機能を利用して、複数の配列の各々が参照配列を含むか否かが、高速に求められる。
【０１８６】
好ましくは、本発明は、参照配列に相当する長さをもつ照合対象部分と残りの照合除外部分とを設定して照合処理を行い、照合除外部分の位置を異ならせた複数回の照合処理を行う。上述の実施形態では、ＤＣｂｉｔを用いて、照合除外部分が設定された。本発明によれば、照合除外部分を異ならせて照合処理を行うことで、参照配列が、被照合データたる配列のどの部分と一致する場合でも、その一致を適切に検出できる。また、一致する部分の特定も可能となる。
【０１８７】
好ましくは、本発明は、一連の配列を複数の分割配列情報に分けて、複数の分割配列情報を、照合方向と交差する方向に並ぶように、並列照合機能をもつ記憶処理装置に記憶させて、各分割配列情報の一部が参照配列と一致するか否かを並列処理により求める。
【０１８８】
本発明は、ＣＡＭの例を用いて説明したように、記憶処理装置の照合方向の幅が狭く、交差方向の長さが大きいときに、特に有利である。本発明によれば、照合方向の幅が狭い場合でも、配列を分割することで、交差方向の長さを活かして、長い配列を記憶可能である。交差方向の長さを利用して、大量の配列を同時に記憶させ、並列して処理することもできる。
【０１８９】
さらに、本態様の配列分割は、計算の高速化にとって有利である。分割により、照合方向の配列長さが小さくなる。これにより計算量が少なくなる。上述の複数種類の照合除外部分を設定するとき、すなわち、上述の実施形態ではＤＣｂｉｔの複数のパターンを用いるとき、照合方向の配列長さが小さい方が、計算量が少なくなる。したがって本発明は、記憶処理装置が照合方向に狭く、交差方向に長いとき、このことを障害とせず、むしろ、配列分割と並列処理により計算量を削減し、配列解析の一層の高速化を可能としている。
【０１９０】
なお、本発明の範囲内で、連続する分割配列は、記憶処理装置上で隣合わせに並べられなくてもよい。それらが離れていても構わない。
【０１９１】
好ましくは、本発明は、複数の分割配列情報の照合結果を処理して、配列情報が参照配列を含むか否かを判定する。ここでは、典型的には、上述の実施形態で説明したような論理演算が行われる。これにより、簡単な処理で、参照配列が含まれるか否かが求められる。
【０１９２】
好ましくは、本発明は、参照配列の端の部分を照合データとして用いた照合を行って、隣接する分割配列情報に跨る参照配列を検出する。これにより、複数の分割配列に、参照配列と一致する部分配列が跨るときでも、すなわち、記憶処理装置上の複数の列に、参照配列と一致する部分配列が跨るときでも、そのような部分配列を検出できる。また、そのような部分配列の位置を特定することも可能となる。
【０１９３】
好ましくは、本発明は、隣接する分割配列情報を部分的に重複させる。この処理によっても、分割箇所の参照配列を、漏らすことなく検出可能である。
【０１９４】
好ましくは、本態様、すなわち、照合方向に配列を記憶させる態様において、並列照合機能をもつ記憶処理装置は、ＣＡＭである。ＣＡＭは、既に述べたように、並列照合機能をもつ点で、配列情報の処理に適した特性をもち、配列解析を高速化できる。また、ＣＡＭは、これまで配列情報処理には用いられていないが、インターネットルータ部品として普及しており、安価である。したがって、ＣＡＭを使うことで、低コストで高速な配列解析が可能となる。さらに、通常のＣＡＭは、照合方向の幅が比較的狭いにも拘わらず、本発明によれば、配列の分割記憶により、長い配列をＣＡＭに記憶できる。ＣＡＭの長さを利用して、大量の配列を記憶させて同時に処理することもできる。さらに、配列分割により照合方向の配列長さを縮めることで、計算量を実質的に削減し、さらなる高速化も図れる。このようにして、本発明によれば、ＣＡＭの特性を利用して、配列解析を好適に高速化できる。
【０１９５】
好ましくは、本態様、すなわち、照合方向に配列を記憶させる態様において、上述の処理により、ブラスト法等のホモロジー解析に用いる情報が得られる。例えば、データベースの大量の配列を使ってブラスト検索を行うような場合、本発明の高速化は特に有用と考えられる。
【０１９６】
（５）本発明の一態様は、並列照合機能をもつ記憶処理装置に、同一の配列情報を少しずつずらして、被照合データとして用いるために、照合方向を向けて記憶させる。配列情報は所定文字数ずつ、通常は一文字ずつずらされる。そして、本発明は、比較対象の別の配列情報を照合データとして用いて、少しずつずらして記憶された同一の配列情報を被照合データとして用いて、照合データと被照合データを並列処理にて記憶処理装置に照合させる。本発明によれば、複数の配列情報が連続して一致する部分が、並列処理を利用して高速に求められる。最長一致部分を求めることも可能であり、また、連続一致部分の位置を特定することも可能である。並列照合機能をもつ記憶処理装置を利用し、少しずつずらして配列を記憶させるという特徴的な使い方により、例えばファスタ検索においてドットマトリックスを用いて得られるのと同様の、連続一致部分の情報を得ることができる。
【０１９７】
好ましくは、本発明は、配列情報の部分的な照合を行うことで、配列の部分一致を求める。好ましくは、本発明は、配列情報の部分的な照合を行うために、照合除外部分を設定する。上述の実施形態では、ＣＡＭの特性に基づき、ＤＣｂｉｔを設定することで、照合除外部分が好適に設定された。さらに、好ましくは、本発明は、配列情報の部分的な照合を、複数種類の部分照合パターンで行うことにより、複数種類の長さの配列一致部分を検索する。複数種類の部分照合パターンは、図２０に例示されている。本発明によれば、各種の長さの連続一致部分の情報が得られる。最長一致部分も適切に検出される。
【０１９８】
好ましくは、本発明は、同一の配列情報を、並列処理機能をもつ記憶処理装置の異なる領域に、少しずつずらして記憶させる。これにより、少しずつずらされた同一配列が並列処理され、高速に検索結果が得られる。
【０１９９】
好ましくは、本発明は、一連の配列を複数の分割配列情報に分ける。本発明は、複数の分割配列情報を、照合方向と交差する方向に並ぶように、並列照合機能をもつ記憶処理装置に記憶させる。記憶処理装置の照合方向の幅が狭い場合でも、長い配列を記憶処理装置に記憶させて、並列処理による配列解析ができる。
【０２００】
なお、本発明の範囲内で、連続する分割配列は、記憶処理装置上で隣合わせに並べられなくてもよい。それらが離れていても構わない。
【０２０１】
好ましくは、本発明は、隣接する分割配列情報に跨って配列が一致する部分を、連続して配列が一致する部分として求める。本発明によれば、連続一致部分が複数の分割配列、すなわち記憶処理装置の複数の列に跨るときでも、そのような連続一致部分を検出できる。
【０２０２】
好ましくは、本態様において、並列照合機能をもつ記憶処理装置は、ＣＡＭである。ＣＡＭは、既に述べたように、並列照合機能をもつ点で、配列情報の処理に適した特性をもち、配列解析を高速化できる。また、ＣＡＭは、これまで配列情報処理には用いられていないが、インターネットルータ部品として普及しており、安価である。したがって、ＣＡＭを使うことで、低コストで高速な配列解析が可能となる。さらに、通常のＣＡＭは、照合方向の幅が比較的狭いにも拘わらず、本発明によれば、配列の分割記憶により、長い配列をＣＡＭに記憶できる。また、ＣＡＭの長さを利用して、大量の配列を記憶させて同時に処理することもできる。このようにして、本発明によれば、ＣＡＭの特性を利用して、配列解析を好適に高速化できる。
【０２０３】
好ましくは、本態様において、上述の処理により、ファスタ法等のホモロジー解析に用いる情報が得られる。例えば、データベースの大量の配列を使ってファスタ検索を行うような場合、本発明の高速化は特に有用と考えられる。
【図面の簡単な説明】
【図１】本発明の好適な本実施形態における生物学的配列情報処理装置のハードウエア構成を示す図である。
【図２】インターネットのルータに用いるときのＣＡＭの通常の機能を示す図である。
【図３】本実施形態の生物学的配列情報処理装置の機能ブロック図である。
【図４】図３の装置によるＳＮＰｓ解析処理を示す図である。
【図５】ＳＮＰｓ解析におけるＤＣｂｉｔの設定のパターンを示す図である。
【図６】図４の処理に対応するフローチャートである。
【図７】図３の装置による欠損または挿入の検出処理を示す図である。
【図８】図７の処理に対応するフローチャートである。
【図９】図３の装置による置換検出処理のフローチャートである。
【図１０】図３の装置によるブラスト検索の対象になる配列の例を示す図である。
【図１１】図３の装置によるブラスト検索処理を示す図であり、図１０の配列をＣＡＭに記憶させた状態を示す図である。
【図１２】図１１の処理で設定されるＤＣｂｉｔを示す図である。
【図１３】図１１の照合結果を処理して参照配列の有無の判定を行う論理演算処理を示す図である。
【図１４】図１１の処理に対応するフローチャートである。
【図１５】参照配列の端の部分を照合データとして用いることにより、複数の分割配列に跨る参照配列を求める処理を示す図である。
【図１６】隣接する分割配列を重複させることにより、分割箇所の参照配列を検出可能とした形態を示す図である。
【図１７】ファスタ検索で用いられるドットマトリックスを概念的に示す図である。
【図１８】ファスタ検索で実際に用いられるドットマトリックスの例を示す図である。
【図１９】図３の装置によるファスタ検索処理を示す図である。
【図２０】図１９の処理にて、各種の長さの連続一致部分を検出する処理を示す図であって、ＤＣｂｉｔの各種の設定パターンを示す図である。
【図２１】図１９の処理で配列を複数に分割するときの処理を示す図である。
【図２２】図２１の処理に関して、複数の分割配列に跨った連続一致部分の検出処理を示す図である。
【図２３】図２１の処理に対応するフローチャートである。
【符号の説明】
１０  配列情報処理装置
１２  ＣＰＵ
１８  ＣＡＭ
２０  ハードディスク
３０  配列処理制御部
３２  配列情報取得部
３４  被照合データ投入部
３６  照合データ投入部
３８  照合結果取得部
４０  照合結果処理部
４２  解析情報出力部
【図１】
0003723767.tif 000002
【図２】
0003723767.tif 000003
【図３】
0003723767.tif 000004
【図４】
0003723767.tif 000005
【図５】
0003723767.tif 000006
【図６】
0003723767.tif 000007
【図７】
0003723767.tif 000008
【図８】
0003723767.tif 000009
【図９】
0003723767.tif 000010
【図１０】
0003723767.tif 000011
【図１１】
0003723767.tif 000012
【図１２】
0003723767.tif 000013
【図１３】
0003723767.tif 000014
【図１４】
0003723767.tif 000015
【図１５】
0003723767.tif 000016
【図１６】
0003723767.tif 000017
【図１７】
0003723767.tif 000018
【図１８】
0003723767.tif 000019
【図１９】
0003723767.tif 000020
【図２０】
0003723767.tif 000021
【図２１】
0003723767.tif 000022
【図２２】
0003723767.tif 000023
【図２３】
0003723767.tif 000024