(57)【要約】  問合せ配列を対象配列と対比して前記対象配列における類似箇所を検索する際、従来よりも優れた精度で相同性検索を可能とする。問合せ配列とゲノムスケールの対象配列との配列情報を取得し、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列と圧縮対象配列とに圧縮変換し、両者を対比して、圧縮対象配列において圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索する。絞り込んだ圧縮候補配列と問合せ配列とについて、各々の圧縮前配列における同一塩基連続数の情報に基づき、両圧縮配列の間で対応塩基ごとに連続数を対比し、連続数の一致度または不一致度から前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する。この類似度から問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択することで、ホモポリマーの同一塩基連続数の影響を回避して精度良く相同性検索を行える。
2008108297.tif 000002
【特許請求の範囲】
【請求項１】
核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する部分配列を検索する相同性検索システムであって、
前記問合せ配列および対象配列の配列情報を取得する取得手段と、
取得された前記問合せ配列および前記対象配列について、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列および圧縮対象配列を準備する圧縮配列準備手段と、
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索手段と、
前記圧縮問合せ配列と前記検索手段で選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備手段と、
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算手段と、
前記類似度演算手段により演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択手段と、
前記選択手段により選択した前記任意数の候補配列の情報を出力する出力手段とを有する、相同性検索システム。
【請求項２】
前記取得手段が、前記問合せ配列の配列情報を入力する入力手段と、前記対象配列の配列情報が記憶されている対象配列記憶手段とを有する、請求の範囲１記載の相同性検索システム。
【請求項３】
前記取得手段により取得される配列情報が、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた前記圧縮問合せ配列および前記圧縮対象配列である、請求の範囲１記載の相同性検索システム。
【請求項４】
前記圧縮配列準備手段が、取得された前記問合せ配列および前記対象配列について、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列および圧縮対象配列に圧縮変換する圧縮変換手段である、請求の範囲１記載の相同性検索システム。
【請求項５】
前記連続数準備手段が、前記圧縮問合せ配列と前記検索手段で選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数を計数する計数手段である、請求の範囲１記載の相同性検索システム。
【請求項６】
前記類似度演算手段は、前記対応する塩基ごとの連続数の不一致度（ただし、前記圧縮問合せ配列の上流末端塩基または下流末端塩基における圧縮前の連続数が、前記圧縮候補配列の上流末端塩基または下流末端塩基における圧縮前の連続数よりも短い不一致を除く）をペナルティスコアとし、前記対応する塩基ごとのペナルティスコアを加算することによって、類似度を演算する、請求の範囲１記載の相同性検索システム。
【請求項７】
さらに、前記問合せ配列と前記選択手段により選択した任意数の候補配列との情報を記憶しておく記憶手段を有し、
前記選択手段は、前記類似度演算手段により、新たな候補配列の前記問合せ配列に対する新たな類似度が演算された際、前記新たな類似度と、前記問合せ配列記憶手段により先立って記憶された前記任意数の候補配列の前記問合せ配列に対する類似度とに基づいて、前記各候補配列から、再度、任意数の候補配列を選択する、請求の範囲１記載の相同性検索システム。
【請求項８】
前記圧縮対象配列は、圧縮後の対象配列を固定長に区切った部分配列群について、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮対象部分配列群である、請求の範囲１記載の相同性検索システム。
【請求項９】
前記検索手段は、ハッシュ検索手段であり、前記圧縮問合せ配列と前記圧縮対象部分配列群の各圧縮対象部分配列とをキーとし、同じハッシュ関数を用いて、ハッシュ検索を行うことにより、前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索する、請求の範囲８記載の相同性検索システム。
【請求項１０】
さらに、前記圧縮対象部分配列群の各圧縮対象部分配列をキーとし、同じハッシュ関数を用いて、対象配列用ハッシュテーブルを生成する対象配列用ハッシュテーブル生成手段を有し、
前記検索手段は、ハッシュ検索手段であり、前記圧縮問合せ配列をキーとし、前記対象配列用ハッシュテーブル生成手段と同じハッシュ関数を用いて、前記対象配列用ハッシュテーブル生成手段で生成した前記対象配列用ハッシュテーブルのハッシュ検索を行うことにより、前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索する、請求の範囲８記載の相同性検索システム。
【請求項１１】
さらに、２つ以上の前記圧縮問合せ配列をキーとし、同じハッシュ関数を用いて、問合せ配列用ハッシュテーブル生成する問合せ配列用ハッシュテーブル生成手段を有し、
前記検索手段は、ハッシュ検索手段であり、前記圧縮対象部分配列群の各圧縮対象部分配列をキーとし、前記問合せ配列用ハッシュテーブル生成手段と同じハッシュ関数を用いて、前記問合せ配列用ハッシュテーブル生成手段で生成した前記問合せ配列用ハッシュテーブルのハッシュ検索を行うことにより、前記各圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索する、請求の範囲８記載の相同性検索システム。
【請求項１２】
さらに、前記問合せ配列用ハッシュテーブルのデータを更新するハッシュテーブル更新手段を有し、
前記ハッシュテーブル更新手段は、前記選択手段により、１つの問合せ配列に対して、最も高い相同性を示す同じ類似度の候補配列が２つ以上選択された際、前記問合せ配列用ハッシュテーブルのデータから、前記問合せ配列と、それに対して選択された前記２つ以上の候補配列を削除する、請求の範囲１１記載の相同性検索システム。
【請求項１３】
核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する部分配列を検索する相同性検索システムであって、
端末とサーバーとを有し、
前記端末およびサーバーは、
システム外の通信網を介して接続可能であり、
前記端末は、
前記端末内の情報を前記通信網を介して前記サーバーに送信する端末側送信手段と、
前記サーバーから送信された情報を前記通信網を介して受信する端末側受信手段と、
前記端末内の情報を表示する表示手段と、
前記問合せ配列の配列情報を取得する取得手段とを有し、
前記サーバーは、
前記サーバー内の情報を前記通信網を介して前記端末に送信するサーバー側送信手段と、
前記端末から送信された情報を前記通信網を介して受信するサーバー側受信手段と、
対象配列が蓄積されている対象配列データベースと、
前記対象配列データベースにおける対象配列と、前記サーバー側受信手段により受信した前記問合せ配列とについて、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列と圧縮対象配列とを準備する圧縮配列準備手段と、
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索手段と、
前記圧縮問合せ配列と前記検索手段で選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備手段と、
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算手段と、
前記類似度演算手段により演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択手段とを有し、
前記問合せ配列の情報が、前記端末側送信手段から前記サーバー側受信手段に送信され、かつ、前記サーバーの前記選択手段により選択した前記任意数の候補配列の情報が、前記サーバー側送信手段から前記端末側受信手段に送信され、前記端末において、受信した前記任意数の候補配列の情報が、前記表示手段により表示される相同性検索システム。
【請求項１４】
請求の範囲１３記載の相同性検索システムに用いるサーバーであって、
前記サーバーは、
前記サーバー内の情報を前記通信網を介して端末に送信するサーバー側送信手段と、
前記端末から送信された情報を前記通信網を介して受信するサーバー側受信手段と、
対象配列が蓄積されている対象配列データベースと、
前記対象配列データベースにおける対象配列と、前記サーバー側受信手段により受信した前記問合せ配列とについて、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列と圧縮対象配列とを準備する圧縮配列準備手段と、
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索手段と、
前記圧縮問合せ配列と前記検索手段で選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備手段と、
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算手段と、
前記類似度演算手段により演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択手段とを有する、サーバー。
【請求項１５】
請求の範囲１３記載の相同性検索システムに用いる端末であって、
前記端末は、
前記端末内の情報を前記通信網を介して前記サーバーに送信する端末側送信手段と、
前記サーバーから送信された情報を前記通信網を介して受信する端末側受信手段と、
前記端末内の情報を表示する表示手段と、
前記問合せ配列の配列情報を取得する取得手段とを有し、
前記問合せ配列の情報が、前記端末側送信手段から前記サーバー側受信手段に送信され、かつ、前記サーバーの前記選択手段により選択した前記任意数の候補配列の情報が、前記サーバー側送信手段から前記端末側受信手段に送信され、前記端末において、受信した前記任意数の候補配列の情報が、前記表示手段により表示される、端末。
【請求項１６】
核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する部分配列を検索する相同性検索装置であって、請求の範囲１記載の相同性検索システムを含む、相同性検索装置。
【請求項１７】
核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する部分配列を検索する相同性検索方法であって、
前記問合せ配列および対象配列の配列情報を取得する取得ステップと、
取得された前記問合せ配列と前記対象配列について、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列と圧縮対象配列とを準備する圧縮配列準備ステップと、
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索ステップと、
前記圧縮問合せ配列と前記検索ステップで選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備ステップと、
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算ステップと、
前記類似度演算ステップにより演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択ステップと、
前記選択ステップにより選択した前記任意数の候補配列の情報を出力する出力ステップとを有する、相同性検索方法。
【請求項１８】
前記取得ステップが、前記問合せ配列を入力する入力ステップと、前記対象配列が記憶されている対象配列記憶ステップから前記対象配列の配列情報を呼び出す呼び出しステップとを有する、請求の範囲１７記載の相同性検索方法。
【請求項１９】
前記類似度演算ステップは、前記対応する塩基ごとの連続数の不一致度（ただし、前記圧縮問合せ配列の上流末端塩基または下流末端塩基における圧縮前の連続数が、前記圧縮候補配列の上流末端塩基または下流末端塩基における圧縮前の連続数よりも短い不一致を除く）をペナルティスコアとし、前記対応する塩基ごとのペナルティスコアを加算することによって、類似度を演算する、請求の範囲１７記載の相同性検索方法。
【請求項２０】
前記選択ステップにおいて、前記類似度演算ステップにより、新たな候補配列の前記問合せ配列に対する類似度が演算された際、前記新たな類似度と、先立っての前記選択ステップで選択された前記任意数の候補配列の前記問合せ配列に対する類似度とに基づいて、前記各候補配列から、再度、任意数の候補配列を選択する、請求の範囲１７記載の相同性検索方法。
【請求項２１】
請求の範囲１７記載の相同性検索方法をコンピュータ上で実行可能なコンピュータプログラム。
【請求項２２】
請求の範囲２１記載のコンピュータプログラムを格納した電子媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、相同性検索システム、相同性検索装置、相同性検索方法、および、前記相同性検索方法をコンピュータ上で実行可能なコンピュータプログラムならびにそれを格納した電子媒体に関する。
【背景技術】
【０００２】
近年、生命科学分野において、多くの生物種のゲノム配列全体が解明されている。塩基配列の配列読み取り技術も、オートラジオグラフィにより銀塩フィルムを露光させてラダーパターンを読み取ることによる初期の手法から、電気泳動レーン上の蛍光標識をレーザ光で励起することにより自動で読み取る形式の手法に置き換わり、格段に自動化が推進されている。そして、様々な高感度化、高速化の技術が導入され、スループットも向上している。しかしながら、これらの方法は、全てサンガー法と呼ばれる同じ原理に基づく手法であり、物理的な実泳動時間の制約により、性能に限界がある。そこで、新たにパイロシーケンシング技術が開発され、実用化されるに至っている。この技術は、従来のサンガー法と大きく原理が異なっており、電気泳動ではなく、相補鎖伸長の化学的反応による蛍光強度を、直接読み取る方法である。この原理によって、パイロシーケンシング技術は、サンガー法を遥かに超える配列決定速度を実現した。【０００３】
しかしながら、パイロシーケンシング技術では、配列中における同一塩基が複数個繋がった領域（以下、「ホモポリマー領域」という）の配列決定について、次のような問題がある。すなわち、パイロシーケンシング技術においては、配列の情報が、計測時に、ダイナミックレンジの飽和限度のある蛍光強度の比でしか観測されない。このため、同一塩基が連続して繋がっているホモポリマー領域に関しては、同一塩基の数を正確に決定し難く、結果的に、配列決定精度に問題が生じる。このようなホモポリマー領域に関する配列決定精度の問題は、前述のサンガー法においても、同様に技術的限界が潜在していた。しかしながら、パイロシーケンシング技術は、高いスループットであるがゆえに、サンガー法と比較して、前記ホモポリマー領域の問題がより顕著となっている。【０００４】
他方、例えば、ゲノム上の位置が不明な配列、機能や起源等が不明な配列（以下、「問合せ配列」という）について、解読されたゲノム等の配列（以下、「対象配列」という）において相同する部分配列を検索する相同性検索（類似性検索）が、遺伝子解析において行われている。この相同性検索の技術は、前述の配列決定法の飛躍的な進歩と較べて、従来と余り変化がなく、下記の手法が一般的である。【０００５】
（１）相同性検索を行う代表的なシステムとしてＢＬＡＳＴがある（非特許文献１）。このシステムは、生命科学分野で配列検索を行う際の標準として、広く普及、定着している。
（２）部分配列の不一致を配列の挿入・削除のスコアリングで最大限に許容する類似度検索法として、動的計画法（ダイナミックプログラミング）によるSmith−Waterman法がある（非特許文献２）。この方式は、複数のシステムの実装に用いられている。
（３）さらに、前記（２）の動的計画法の論理をハードウェアに組み込んで、超並列実行させることで、速度に関する問題の解決を試みる手法が報告されている（特許文献１）。
【非特許文献１】Altschul  S.  F.,  Gish  W.,  Miller  W.,  Myers  E.  W.,  and  Lipman  D.  J.  (1990)  Basic  local  alignment  search  tool.  J.  Mol.  Biol.  Vol.215，  pp.403-410.
【非特許文献２】Smith  TF,  Waterman  MS.  (1981)  Comparison  of  biosequences.  Adv.  Appl.  Math.  2:482-9.
【特許文献１】特開平０７−０９３３７０号公報
【発明の開示】
【０００６】
しかしながら、これらの相同性検索方法は、前述のような塩基配列決定法により決定された塩基配列情報に基づいて行われるが、前記塩基配列決定法によって生じるホモポリマー領域の配列決定精度の問題を回避できるものではない。つまり、相同性検索に使用するゲノム等の対象配列がホモポリマー領域を有する場合、塩基配列決定法によって決定された前記ホモポリマー領域の同一塩基の連続数は、前述のように精度に問題がある。しかし、前述の相同性検索方法は、このような問題に対応した手法とは言い難い。このため、例えば、問合せ配列に対して、ゲノム等の対象配列における部分配列が実際には相同性が高い場合でも、例えば、配列精度の影響によって、結果を抽出できなかったり、類似していないにも関わらず誤って結果を抽出するという問題がある。
【０００７】
前記（１）のＢＬＡＳＴは、例えば、長い問合せ配列と対象配列とを対比する場合、前記問合せ配列の内部において同一塩基連続数の不一致があると、この不一致を、塩基の挿入、削除として解析する。これによって、ある程度、完全には一致しないもの同士であっても、対応付けて検索することが可能である。しかし、問合せ配列が短い配列であったり、問合せ配列の両端付近に同一塩基連続数の不一致がある場合、相違を過大評価して、短い問合せ配列全体を不一致と判断したり、前記端の部分を不一致として、相同する配列の候補から除外するケースが多く観察される。
【０００８】
前記（２）のＳｍｉｔｈ−Ｗａｔｅｒｍａｎ法は、ＢＬＡＳＴと較べて、ホモポリマー領域の場所に依存して不一致を出す可能性は少なくなる。さらに、動的計画法のアルゴリズムによって最適な配列塩基の対応であるアライメントを探し出すことで、ＢＬＡＳＴと比較して、良好な探索ができる。しかしながら、ホモポリマー領域における塩基の連続数の不一致と、他の単一塩基の不一致とが、同一尺度で測定されてしまうため、相同性の順序付けの合理性に未だ問題がある。さらに、性能上、基本となっている動的計画法の実行に関して、問合せ配列と対象配列との積のオーダの計算量がかかるため、極端に検索性能が遅いという欠点がある。また、この方法は、例えば、配列決定法の進歩に伴い、問合せ配列として網羅的な量、例えば、1,000,000を超える超大量の数を扱う場合において、実用性に欠ける。
【０００９】
前記（３）の手法は、前記（２）と基本的なアルゴリズムが同じであり、動作精度上、同様の問題がある。また、専用のハードウェアを利用する必要があるため、性能的には相当の改善があるものの、計算機ソフトウェアによる方法と較べてコストがかかる。また、汎用計算機上で稼動するシステムと較べて、ハードウェアが固定されることで、信頼性を含む性能仕様が陳腐化するという問題がある。このため、現在では、利用が特定の範囲に限定されている。
【００１０】
このように、何れの相同性検索の手法も、対象配列と問合せ配列との対比において、ホモポリマー領域における同一塩基の塩基個数に不一致を含む場合、例えば、正確性や、性能上、コスト上等の問題がある。このため、両者の対応するホモポリマー領域において同一塩基の連続数に不一致がある場合に適した相同性検索が求められる。
【００１１】
そこで、本発明は、問合せ配列について、対象配列において相同する部分配列を検索する際に、前記両者の対応するホモポリマー領域において同一塩基の連続数に差が生じる場合であっても、従来よりも優れた精度で、迅速に、相同性検索を可能とすることを目的とする。
【００１２】
前記目的を達成するために、本発明の相同性検索システムは、核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する部分配列を検索する相同性検索システムであって、
前記問合せ配列および対象配列の配列情報を取得する取得手段と；
取得された前記問合せ配列および前記対象配列について、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列および圧縮対象配列を準備する圧縮配列準備手段と；
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索手段と；
前記圧縮問合せ配列と前記検索手段で選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備手段と；
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算手段と；
前記類似度演算手段により演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択手段と；
前記選択手段により選択した前記任意数の候補配列の情報を出力する出力手段とを有する。
【００１３】
本発明の相同性検索装置は、核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する対象部分配列を検索する相同性検索装置であって、本発明の相同性検索システムを含む。
【００１４】
本発明の相同性検索方法は、核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する対象部分配列を検索する相同性検索方法であって、
前記問合せ配列および対象配列の配列情報を取得する取得ステップと；
取得された前記問合せ配列と前記対象配列について、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列と圧縮対象配列とを準備する圧縮配列準備ステップと；
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索ステップと；
前記圧縮問合せ配列と前記検索ステップで選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備ステップと；
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算ステップと；
前記類似度演算ステップにより演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択ステップと；
前記選択ステップにより選択した前記任意数の候補配列の情報を出力する出力ステップとを有する。
【００１５】
本発明のコンピュータプログラムは、本発明の相同性検索方法をコンピュータ上で実行可能なコンピュータプログラムである。
【００１６】
本発明の電子媒体は、本発明のコンピュータプログラムを格納した電子媒体である。
【００１７】
本発明は、塩基配列の決定において生じるホモポリマー領域の同一塩基連続数の変動による問題を考慮して、まず、同一塩基連続数に影響されない圧縮配列（ホモポリマー領域を塩基１個に置き換えた圧縮配列）として、対象配列と問合せ配列を対比させた上で、つぎに、両者の相同性を、ホモポリマー領域の連続塩基数から判断している。従来法であれば、ホモポリマー領域の同一塩基連続数の変動が原因となり、合理的ではない不適切な相同性順位の結果となったり、または、ホモポリマー領域における同一塩基連続数の変動自体が見落とされるおそれがあったが、本発明は、このような問題を回避して、より正確に問合せ配列と相同する対象配列の部分配列を選択することが可能となった。したがって、本発明によれば、例えば、ホモポリマー領域における同一塩基連続数が、塩基配列の決定法や配列自身の多型のために、誤差や変位を含む場合であっても、その影響を回避して、より正確な相同性検索が可能となる。特に、塩基配列の情報が、従来のサンガー法による場合だけでなく、パイロシーケンシング技術によってハイスループットで決定されている場合であっても、ホモポリマー領域の同一塩基連続数の決定精度が低いことによる影響を回避できる。さらに、このように精度良く相同性検索が行えることから、例えば、問合せ配列と対象配列における部分配列とが、唯一の相同性（類似性）を示すものであるか否かの判断も精度良く行うことが可能になる。また、ホモポリマー領域の同一塩基連続数を考慮しない圧縮配列同士を対比し、一致した対象配列の部分配列を選択するため、従来と比較して、データ処理能力が格段に向上し、低コスト化の実現も可能である。したがって、本発明は、相同性検索（類似性検索）の分野において、これまで回避できなかったホモポリマー領域における同一塩基連続数の変動による影響を解決できることから、特に遺伝子解析の分野において極めて有用な技術であるといえる。
【図面の簡単な説明】
【００１８】
【図１】図１は、本発明の一実施形態における相同性検索装置のハードウェア構成の一例を示すブロック図である。
【図２】図２は、本発明のその他の実施形態における相同性検索システムを示す概略図である。
【図３】図３は、本発明のさらにその他の実施形態における相同性検索システムを示す概略図である。
【図４】図４は、本発明のさらにその他の実施形態における圧縮変換ならびに同一塩基の連続数の計数の概略を示す図である。
【図５】図５は、本発明のさらにその他の実施形態における相同性検索方法の処理の流れを示すフローチャートである。
【図６】図６は、本発明のさらにその他の実施形態における類似度の算出方法の概略を示す図である。
【図７】図７は、本発明のさらにその他の実施形態における問合せ配列用ハッシュテーブルの一例を示す概略図である。
【図８】図８は、本発明のシステムを用いたスタンドアローン型の装置の一例の全体構成図である。
【図９】図９は、本発明のシステムを用いたネットワーク利用型の装置の一例の全体構成図である。
【図１０】図１０は、前記スタンドアローン型の装置の機器構成の一例を示すブロック図である。
【図１１】図１１は、前記ネットワーク型の装置の機器構成の一例を示すブロック図である。
【発明を実施するための最良の形態】
【００１９】
本発明において「問合せ配列」は、特に制限されず、核酸塩基配列であればよい。前記塩基配列としては、例えば、各種生物のゲノム断片配列やオリゴキャップ法等によって得られた完全長や断片のトランスクリプトーム配列等が含まれる。本発明における問合せ配列の長さは、特に制限されないが、例えば、１２〜６０塩基であり、好ましくは１８〜２５塩基である。【００２０】
本発明において「ゲノムスケールの対象配列」は、特に制限されず、例えば、ゲノムとして解読された全核酸塩基配列や、染色体全体の核酸塩基配列、また、それらの１塩基多型やハプロタイプ等の変異配列、さらに、ゲノムからの核酸複製産物であるトランスクリプトームと呼ばれる転写物の網羅的な収集配列等があげられる。また、このようなゲノムスケールの対象配列は、例えば、各種データベース（例えば、ＤＤＢＪ、ＥＭＢＬ、ＥＮＳＥＭＢＬ、ＧｅｎＢａｎｋ、ＵＣＳＣ等）に登録されている配列が利用できる。前記対象配列の長さとしては、制限されず、例えば、ヒトゲノム３０億塩基対であっても可能であり、特に１００万塩基以上の配列について、本発明を適用することが好ましい。【００２１】
本発明において「ホモポリマー領域」とは、核酸塩基配列において、２個以上の同一核酸塩基(例えば、アデニン、グアニン、シトシンまたはチミン)が連続（反復）した領域を意味する。【００２２】
本発明において「圧縮配列」とは、問合せ配列および対象配列の配列情報を、同一塩基が２個以上連続した前記ホモポリマー領域を前記塩基１個に置き換えたそれぞれの配列をいう。つまり、問合せ配列および対象配列に関する、核酸塩基の種別の連なりを示す配列情報である。前記塩基１個への置き換えを、圧縮変換といい、問合せ配列を圧縮変換した配列を、圧縮問合せ配列、対象配列を圧縮変換した配列を、圧縮対象配列という。また、「圧縮対象部分配列」とは、前記圧縮問合せ配列と一致する、圧縮対象配列における部分配列である。【００２３】
本発明において「連続数の情報」とは、問合せ配列および対象配列の配列情報を、核酸塩基の種別の連なりではなく、同一塩基がいくつ連続して存在するのかを示す配列情報である。同一塩基が連続してｎ個存在する場合は、「ｎ」と計数できる。具体的には、例えば、核酸塩基配列において、同一塩基が１個存在する場合は「１」、同一塩基が連続して２個存在する場合は「２」というように計数できる。【００２４】
本発明において、対象配列は、前述のようにゲノムスケールの核酸塩基配列である。一般的な相同性検索では、ゲノムスケールの対象配列は、通常、部分配列に分解してから検索が行われる。具体的には、対象配列の先頭から、例えば、順次、１塩基ずつずらして複数の部分配列を作成し、これらの部分配列からなる部分配列群を使用する。本発明においても、対象配列は、部分配列に区切った対象部分配列群を用いた検索であることが好ましい。したがって、本発明において、前記圧縮対象配列は、例えば、対象配列について、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換える圧縮処理を施し、得られた圧縮後の圧縮対象配列を固定長に区切った圧縮対象部分配列からなる圧縮対象部分配列群であることが好ましい。前記固定長は、制限されず、例えば、１〜１００塩基であっても本発明を実施でき、特に８〜５０塩基の長さで、非常に有効な検索が可能である。前記固定長は、例えば、後述するハッシュの対象となる圧縮配列の塩基長（ハッシュ対象塩基長）であり、いわゆる、「ハッシュ幅」である。【００２５】
本発明において、問合せ配列と対比する対象配列の数は、制限されず、例えば、１つの問合せ配列に対して、目的とする１つの対象配列を対比してもよいし、２つ以上の対象配列を対比させてもよい。また、問合せ配列の数も制限されず、例えば、１つの対象配列に対して、１つまたは２つ以上の問合せ配列を対比させてもよい。圧縮後の圧縮対象配列は、前述のように固定長に区切って圧縮対象部分配列群とした後、各圧縮対象部分配列に対して、例えば、後述するハッシュ処理が行われる。この際、前記固定長は、例えば、圧縮した問合せ配列と同じ長さにすることが好ましい。そして、問合せ配列が複数存在する場合には、複数の圧縮問合せ配列の長さのバリエーションだけ、圧縮後の対象配列から圧縮対象部分配列群を生成し、各圧縮対象部分配列群について独立して相同性検索を多重に行うことが好ましい。【００２６】
本発明において、類似度に基づいて選択する候補配列の数は、制限されず、任意数を設定できる。例えば、最も相同性が高い結果を示す候補配列のみを選択してもよいし、相同性が高い順序を決定して、上位数個を前記順序に基づいて選択してもよい。また、相同性を示す候補配列が、設定した任意数に達しない場合、選択する候補配列の数は、任意数未満であってもよい。【００２７】
以下に、本発明の相同性検索システム、相同性検索装置、相同性検索方法、これをコンピュータ上で実行可能なコンピュータプログラム、および、前記プログラムを格納した電子媒体について説明する。本発明の相同性検索方法は、例えば、本発明の相同性検索システムや本発明の相同性検索装置、本発明のコンピュータプログラムの実行によって実現できる。【００２８】
本発明によれば、前述のように、ホモポリマー領域の同一塩基連続数の変動を考慮した上で、相同性検索を行うため、例えば、従来法では検索できなかった相同する部分配列を検索でき、また、従来法のように誤って相同性が判断されるおそれを回避できる。さらに、ホモポリマー領域の同一塩基連続数の影響をうけない圧縮配列同士を対比するため、データ処理速度を格段に向上できる。これらの効果を、例えば、本発明の相同性検索装置について着目すると、以下のようなことがいえる。問合せ配列をそのまま従来のＢＬＡＳＴ検索にかけた場合、特に、問合せ配列および対象配列の少なくとも一方において、複数の個所に、同一塩基が連続したホモポリマー領域が存在すると、ヒットしない場合がある。これを回避して全ての場合で検索を成功させるために、従来は、問合せ配列側で、ホモポリマー領域における同一塩基の連続数の誤差の許容範囲で、全ての組み合わせを生成し、ＢＬＡＳＴを実行する必要があった。しかし、この方法では、例えば、４塩基の出現確率が均等かつランダムであるという想定の下、同一塩基連続数の誤りの許容範囲を２倍未満で、モンテカルロ法による1,000,000回シミュレーションをした場合、問合せ配列長２５塩基で約１３５倍、問合せ配列長５０塩基で約２１，５００倍、問合せ配列長１００塩基で約84,000,000倍のパタンを検索する必要がある。そして、検索時間もそれにほぼ比例した時間が必要となる。これに対して、本発明によれば、問合せ配列長にかかわらず、何れも１回のＢＬＡＳＴサーチに相当する時間に、本発明独自のスコア計算時間（配列長に対して線形）を加算するだけの性能で検索処理が可能となる。【００２９】
＜相同性検索システム＞
本発明の第１の相同性検索システムは、前述のように、
前記問合せ配列および対象配列の配列情報を取得する取得手段と；
取得された前記問合せ配列および前記対象配列について、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列および圧縮対象配列を準備する圧縮配列準備手段と；
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索手段と；
前記圧縮問合せ配列と前記検索手段で選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備手段と；
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算手段と；
前記類似度演算手段により演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択手段と；
前記選択手段により選択した前記任意数の候補配列の情報を出力する出力手段とを有する。【００３０】
本発明のシステムは、問合せ配列と対象配列とについて、前述のように、圧縮配列および同一塩基連続数を対比して相同性を検索することが特徴であり、その他の条件や構成は特に制限されない。【００３１】
前記取得手段により取得される配列情報は、例えば、圧縮前の配列情報があげられる。また、前記配列情報としては、前記圧縮前の配列に代えて、または、加えて、例えば、圧縮配列、同一塩基の連続数等の情報が含まれてもよい。前記取得手段により、配列情報として圧縮配列が取得される場合、例えば、前記取得手段と、圧縮配列を準備する前記圧縮配列準備手段は、同じ手段ともいえる。また、前記取得手段により、配列情報として同一塩基の連続数の情報が取得される場合、例えば、前記取得手段と、同一塩基の連続数の情報を準備する前記連続数準備手段は、同じ手段ともいえる。また、問合せ配列および対象配列のいずれか一方の配列についてのみ、圧縮配列や同一塩基の連続数等の配列情報が取得され、他方の配列については、圧縮前の配列情報が取得されてもよい。この場合、前記他方の配列についてのみ、圧縮前の配列情報から、後述するような手段により圧縮配列や同一塩基の連続数の情報を取得してもよい。【００３２】
本発明のシステムにおいて、前記配列情報の取得手段は、特に制限されないが、例えば、対象配列および／または問合せ配列の配列情報を入力する入力手段があげられる。この場合、本発明のシステムは、さらに、入力された問合せ配列の配列情報を記憶する記憶手段（問合せ配列記憶手段）や、入力された対象配列の配列情報を記憶する記憶手段（対象配列記憶手段）を有することが好ましい。前記問合せ配列の配列情報としては、前述のように、圧縮前の配列の他に、例えば、圧縮配列や、同一塩基の連続数、起源等の情報があげられる。また、前記対象配列の配列情報としては、例えば、前述のように、圧縮前の他に、例えば、圧縮配列、同一塩基の連続数、起源、対象配列における各領域の機能の有無や機能の内容等があげられる。【００３３】
また、前記配列情報の取得手段としては、例えば、前記問合せ配列の配列情報を入力する入力手段と、前記対象配列の配列情報が記憶されている記憶手段（対象配列記憶手段）とを有してもよい。検索対象とする対象配列は、例えば、対象配列記憶手段に記憶された配列の中から所望の配列を指定することで、対象配列記憶手段から呼び出すことができる。また、さらに、入力した前記問合せ配列の配列情報を記憶する記憶手段（問合せ配列記憶手段）を有することが好ましい。【００３４】
前記対象配列記憶手段としては、例えば、前述のように、対象配列の配列情報が蓄積されたデータベース（対象配列データベース）があげられる。蓄積される対象配列の数は、何ら制限されない。このような対象配列データベースとしては、例えば、各種ゲノムや染色体の核酸塩基配列が蓄積された公知のデータベースが例示できる。また、前記対象配列データベースとしては、制限されず、例えば、通信網を介して接続されるデータベース、対象配列が記憶されたリムーバブル記録媒体等があげられる、前記データベースは、コンピュータシステムの記憶手段（記憶装置）に格納されていてもよい。【００３５】
前記対象配列記憶手段は、対象配列の情報として、例えば、圧縮前の配列情報の他に、さらに、前記圧縮対象配列、前記対象配列における同一塩基の連続数、起源、対象配列における各領域の機能の有無や機能の内容等が記憶されてもよい。このように、圧縮対象配列や同一塩基の連続数等の情報を前記記憶手段に蓄積すれば、例えば、さらに他の問合せ配列に対する相同性の検索を行う際、前記対象配列記憶手段から、圧縮配列や同一塩基の連続数等の必要な情報を呼び出すことができる。このようにすれば、再度、後述するような圧縮変換や同一塩基数の計数を行う手間を省くことができ、システムの検索能がさらに向上する。また、本発明のシステムにおいて、前記対象配列記憶手段に記憶されていない対象配列について検索を行う場合は、入力手段によって入力された前記対象配列情報を、前記対象配列記憶手段に追加していくことが好ましい。【００３６】
また、前記配列情報の取得手段は、例えば、前記対象配列の配列情報を入力する入力手段と、前記問合せ配列の配列情報が記憶されている記憶手段（問合せ配列記憶手段）とを有してもよい。前記記憶手段としては、前記問合せ配列の配列情報が蓄積されたデータベース（問合せ配列データベース）があげられる。検索対象とする問合せ配列は、例えば、前記問合せ配列記憶手段に記憶された配列の中から所望の配列を指定することで、問合せ配列記憶手段から呼び出すことができる。前記指定は、例えば、指定する配列と関連付けた情報（例えば、配列のＩＤ等）を前記入力手段で入力することによって行うこともできる。また、さらに、入力した前記対象配列の配列情報を記憶する記憶手段（対象配列記憶手段）を有することが好ましい。【００３７】
前記問合せ配列記憶手段は、問合せ配列の情報として、例えば、圧縮前の配列情報の他に、さらに、前記圧縮問合せ配列、前記問合せ配列における同一塩基の連続数、起源等が記憶されてもよい。このように、圧縮問合せ配列や同一塩基の連続数等の情報を蓄積すれば、例えば、他の対象配列に対する相同性の検索を行う際に、前記問合せ配列記憶手段から、圧縮配列や同一塩基の連続数等、必要な情報を呼び出すことができる。このようにすれば、再度、後述するような圧縮変換や同一塩基数の計数を行う手間を省くことができ、システムの検索能がさらに向上する。また、本発明のシステムにおいて、前記問合せ配列記憶手段に記憶されていない問合せ配列について検索を行う場合は、入力手段によって入力された前記問合せ配列の配列情報を、前記問合せ配列記憶手段に追加することが好ましい。【００３８】
また、前記配列情報の取得手段は、例えば、前記問合せ配列が記憶されている記憶手段（問合せ配列記憶手段）と、前記対象配列の配列情報が記憶されている記憶手段（対象配列記憶手段）とを有してもよい。前記各種記憶手段は、例えば、予め、各配列の配列情報が記憶されていてもよいし、さらに、前述の入力手段により入力された配列情報が記憶されてもよい。そして、検索対象とする問合せ配列および対象配列は、例えば、各記憶手段に記憶された配列の中から検索対象とする所望の配列を指定することで、各記憶手段から呼び出すことができる。【００３９】
前述のように、各種記憶手段（データベース）には、新たな情報を追加することが好ましいことから、本発明のシステムは、さらに、情報を追加するための情報更新手段（データベース更新手段）を有することが好ましい。【００４０】
前記圧縮問合せ配列および圧縮対象配列は、それぞれ、システム内での圧縮変換により得てもよいし、前記入力手段により入力してもよいし、予め配列情報として記憶されている場合には、前述の各記憶手段から呼び出してもよい。すなわち、本発明のシステムにおいて、前記圧縮配列準備手段としては、例えば、取得した問合せ配列および／または対象配列の配列情報に基づいて、圧縮問合せ配列および／または圧縮対象配列に圧縮変換する手段（圧縮変換手段）があげられる。また、前記圧縮配列準備手段は、前述の問合せ配列記憶手段および／または対象配列記憶手段にそれぞれの圧縮配列が記憶されている場合、圧縮問合せ配列が記憶されている問合せ配列記憶手段および／または圧縮対象配列が記憶されている対象配列記憶手段であってもよい。後者の場合、検索対象とする所望の配列を指定することで、各記憶手段からそれぞれの圧縮配列を呼び出すことができる。【００４１】
前記問合せ配列および対象配列における同一塩基の連続数は、それぞれ、システム内での計数処理によって得てもよいし、前記入力手段により入力してもよいし、予め記憶されている場合には、前述の各記憶手段から呼び出してもよい。すなわち、本発明のシステムにおいて、前記連続数準備手段として、例えば、取得した問合せ配列および／または対象配列の配列情報に基づいて、問合せ配列および／または対象配列について、それぞれの圧縮前の配列における同一塩基の連続数を計数（演算）する計数手段（連続数計数（演算）手段）があげられる。また、前記連続数準備手段は、前述の問合せ配列記憶手段および／または対象配列記憶手段にそれぞれの連続数の情報が記憶されている場合、問合せ配列の情報が記憶されている問合せ配列記憶手段および／または対象配列の情報が記憶されている対象配列記憶手段であってもよい。後者の場合、検索対象とする所望の配列を指定することで、各記憶手段からそれぞれの連続数の情報を呼び出すことができる。【００４２】
本発明において前記検索手段は、特に制限されないが、例えば、ハッシュ検索手段、二分木検索手段、Ｂ木（B-tree）検索手段等があげられる。前記ハッシュ検索手段は、例えば、前記圧縮問合せ配列と前記圧縮対象部分配列群の各圧縮対象部分配列とをキーとし、同じハッシュ関数を用いて、ハッシュ検索を行うことにより、前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索する。本発明においてハッシュ検索を行う際には、例えば、未圧縮の問合せ配列と未圧縮の部分配列群の各対象部分配列とをキー（要素）とするのではなく、例えば、前記圧縮問合せ配列および前記圧縮対象部分配列群の各圧縮対象部分配列をキー（要素）とし、同じハッシュ関数を用いてハッシュ検索を行う点がポイントとなる。このポイント以外、すなわち、例えば、ハッシュ関数の設定や、ハッシュ検索の手法自体は、従来公知の方法に基づいて行うことができる。【００４３】
本発明の相同性検索システムによりハッシュ検索を行う場合、例えば、さらに、前記圧縮対象部分配列群の各圧縮対象部分配列をキーとし、同じハッシュ関数を用いて、対象配列用ハッシュテーブルを生成する対象配列用ハッシュテーブル生成手段を有することが好ましい。この場合、前記検索手段は、ハッシュ検索手段であり、例えば、前記圧縮問合せ配列をキーとし、前記対象配列用ハッシュテーブル生成手段と同じハッシュ関数を用いて、前記対象配列用ハッシュテーブル生成手段で生成した前記対象配列用ハッシュテーブルのハッシュ検索を行うことにより、前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索すればよい。このように、対象配列用ハッシュテーブルを生成すれば、これにアクセスすることでハッシュ検索を実行できる。このため、対象配列がゲノムスケールの大規模な核酸塩基配列であっても、計算時間をさらに短縮できる。なお、ハッシュテーブルの生成方法は、圧縮配列をキーとする以外は、従来公知の方法に基づいて行うことができる（以下、同様）。【００４４】
また、ハッシュ検索を実行する場合、さらに、２つ以上の前記圧縮問合せ配列をキーとし、同じハッシュ関数を用いて、問合せ配列用ハッシュテーブル生成する問合せ配列用ハッシュテーブル生成手段を有することが好ましい。この場合、前記検索手段は、ハッシュ検索手段であり、例えば、前記圧縮対象部分配列群の各圧縮対象部分配列をキーとし、前記問合せ配列用ハッシュテーブル生成手段と同じハッシュ関数を用いて、前記問合せ配列用ハッシュテーブル生成手段で生成した前記問合せ配列用ハッシュテーブルのハッシュ検索を行うことにより、前記各圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索することができる。このように問合せ配列用のハッシュテーブルを生成すれば、例えば、各問合せ配列に順次アクセスすることでハッシュ検索が実行できるため、問合せ配列が大量であっても、計算時間をさらに短縮できる。【００４５】
本発明においては、このようにシステム内で各種ハッシュテーブルを生成してもよいが、システム外において予め作成されたハッシュテーブルを入力する形態であってもよい。また、対象配列用ハッシュテーブルは、前述の各種データベースに格納されてもよい。ハッシュテーブルについては後述する。【００４６】
前記類似度演算手段は、前記対応する塩基ごとの連続数の不一致度をペナルティスコアとし、前記対応する塩基ごとのペナルティスコアを加算することによって、類似度を演算することが好ましい。ただし、前記圧縮問合せ配列の上流末端塩基または下流末端塩基における圧縮前の同一塩基連続数が、前記圧縮候補配列の上流末端塩基または下流末端塩基における圧縮前の同一塩基連続数よりも短い不一致を除くことが好ましい。類似度の演算については、後述する。【００４７】
本発明の相同性検索システムは、さらに、前記問合せ配列と前記選択手段により選択した任意数の候補配列との情報を記憶する記憶手段を有することが好ましい。このように、前記問合せ配列とこれに相同性を示す候補配列との情報を順次記憶していくことが好ましい。この記憶手段は、例えば、前述の問合せ配列記憶手段や対象配列記憶手段であってもよい。前者の場合、問合せ配列に関連付けて、前記候補配列の情報を記憶させることが好ましく、後者の場合、対象配列に関連付けて前記問合せ配列の情報を記憶させることが好ましい。記憶する候補配列の数は制限されないが、所望の数（任意数）に設定することが好ましい。そして、記憶した候補配列の個数が前記任意数に達した際には、記憶された候補配列と、新たな候補配列とについて、類似度を比較して、再度、相同性が高い候補配列の順序を決定し、任意数の候補配列を記憶することが好ましい。したがって、このような場合、前記選択手段は、例えば、前記類似度演算手段によって新たな候補配列の前記問合せ配列に対する類似度が演算された際、前記新たな類似度と、前記記憶手段により記憶された前記任意数の候補配列の前記問合せ配列に対する類似度とに基づいて、前記各候補配列から、再度、任意数の候補配列を選択することが好ましい。そして、前記問合せ配列に相同する候補配列が複数存在する場合には、前記問合せ配列と候補配列の情報を記憶し、さらに、新たな候補配列が検索された場合には、複数の候補配列の中から、再度、任意数の候補配列を選択することが好ましい。このようにすれば、例えば、前記問合せ配列に相同する候補配列が多数検索された場合でも、特に相同する配列を選択していくことができる。【００４８】
本発明の相同性検索システムを用いて、問合せ配列が、対象配列のある部分配列にのみ特異的に相同するか否かを検索する場合には、さらに、問合せ配列用ハッシュテーブルのデータを更新するハッシュテーブル更新手段を有することが好ましい。このハッシュテーブル更新手段は、例えば、前記選択手段により、１つの問合せ配列に対して、最も高い相同性を示す同じ類似度の候補配列が２つ以上選択された際、前記問合せ配列用ハッシュテーブルのデータから、前記問合せ配列と、それに対して選択された前記２つ以上の候補配列を削除する機能を有する。前記問合せ配列について、最も高い相同性を示す同じ類似度の候補配列が２以上選択された場合、この問合せ配列は、これらの候補配列に対して特異的に相同するものではないと判断できる。したがって、対象配列のこれらの部分配列に特異的に相同する他の問合せ配列を検索するには、前述のようにハッシュテーブルから、特異性を示さなかった問合せ配列のデータを削除することが好ましい。これによって、検索効率をさらに向上することができる。【００４９】
＜ネットワーク型相同性検索システム＞
本発明の第２の相同性検索システムは、以下に示す端末とサーバーとを有するシステム、すなわちネットワーク型相同性検索システムであってもよい。なお、特に示さない限りは、前述の相同性検索システムと同様である。【００５０】
すなわち、本発明の相同性検索システムは、核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する対象部分配列を検索する相同性検索システムであって、端末とサーバーとを有し、
前記端末およびサーバーは、システム外の通信網を介して接続可能であり、
前記端末は、
前記端末内の情報を前記通信網を介して前記サーバーに送信する端末側送信手段と；
前記サーバーから送信された情報を前記通信網を介して受信する端末側受信手段と；
前記端末内の情報を表示する表示手段と；
前記問合せ配列の配列情報を取得する取得手段とを有し、
前記サーバーは、
前記サーバー内の情報を前記通信網を介して前記端末に送信するサーバー側送信手段と；
前記端末から送信された情報を前記通信網を介して受信するサーバー側受信手段と；
対象配列が蓄積されている対象配列データベースと、
前記対象配列データベースにおける対象配列と、前記サーバー側受信手段により受信した前記問合せ配列とについて、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列と圧縮対象配列とを準備する圧縮配列準備手段と；
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索手段と；
前記圧縮問合せ配列と前記検索手段で選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備手段と；
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算手段と；
前記類似度演算手段により演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択手段とを有し；
前記問合せ配列の情報が、前記端末側送信手段から前記サーバー側受信手段に送信され、かつ、前記サーバーの前記選択手段により選択した前記任意数の候補配列の情報が、前記サーバー側送信手段から前記端末側受信手段に送信され、前記端末において、受信した前記任意数の候補配列の情報が、前記表示手段により表示される。【００５１】
第２の相同性検索システムにおいて、各手段は、例えば、前述の第１の相同性検索システムと同様である。例えば、前記配列情報の取得手段は、例えば、前述の第１の相同性検索システムと同様に、入力手段でもよいし、問合せ配列が記憶されている記憶手段であってもよい。【００５２】
＜サーバー＞
本発明のサーバーは、本発明の第２の相同性検索システムに用いるサーバーである。なお、特に示さない限りは、前述の第１の相同性検索システムと同様である。【００５３】
本発明のサーバーは、
前記サーバー内の情報を前記通信網を介して端末に送信するサーバー側送信手段と；
前記端末から送信された情報を前記通信網を介して受信するサーバー側受信手段と；
対象配列が蓄積されている対象配列データベースと；
前記対象配列データベースにおける対象配列と、前記サーバー側受信手段により受信した前記問合せ配列とについて、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列と圧縮対象配列とを準備する圧縮配列準備手段と；
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索手段と；
前記圧縮問合せ配列と前記検索手段で選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備手段と；
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算手段と；
前記類似度演算手段により演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択手段とを有する。なお、サーバーにおいて、各手段は、前述のシステムにおける手段と同様である。【００５４】
＜端末＞
本発明の端末は、本発明の第２の相同性検索システムに用いる端末である。なお、特に示さない限りは、前述の第１の相同性検索システムと同様である。【００５５】
本発明の端末は、
前記端末内の情報を前記通信網を介して前記サーバーに送信する端末側送信手段と；
前記サーバーから送信された情報を前記通信網を介して受信する端末側受信手段と；
前記端末内の情報を表示する表示手段と；
前記問合せ配列の配列情報を取得する取得手段とを有し、
前記問合せ配列の情報が、前記端末側送信手段から前記サーバー側受信手段に送信され、かつ、前記サーバーの前記選択手段により選択した前記任意数の候補配列の情報が、前記サーバー側送信手段から前記端末側受信手段に送信され、前記端末において、受信した前記任意数の候補配列の情報が、前記表示手段により表示される。【００５６】
＜相同性検索装置＞
本発明の相同性検索装置は、核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する部分配列を検索する相同性検索装置であって、本発明の相同性検索システムを含む。前記相同性検索装置は、例えば、前記問合せ配列および対象配列の配列情報を取得する取得部と；取得された前記問合せ配列および前記対象配列について、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列および圧縮対象配列を準備する圧縮配列準備部と；前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索部と；前記圧縮問合せ配列と前記検索手段で選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備部と；前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算部と；前記類似度演算手段により演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択部と；前記選択手段により選択した前記任意数の候補配列の情報を出力する出力部とを有する。また、前述のシステムと同様に、対象配列の配列情報を記憶する、または、記憶している対象配列記憶部、問合せ配列の配列情報を記憶する、または、記憶している問合せ配列記憶部、配列情報の入力部、前記各記憶部に情報を更新するための情報更新部等を備えてもよい。【００５７】
＜相同性検索方法＞
本発明の相同性検索方法は、核酸塩基配列からなる問合せ配列の配列情報を用いて、核酸塩基配列からなるゲノムスケールの対象配列の配列情報から、前記問合せ配列と相同する部分配列を検索する相同性検索方法であって、
前記問合せ配列および対象配列の配列情報を取得する取得ステップと；
取得された前記問合せ配列と前記対象配列について、それぞれ、同一塩基が２個以上連続したホモポリマー領域を前記塩基１個に置き換えた圧縮問合せ配列と圧縮対象配列とを準備する圧縮配列準備ステップと；
前記圧縮問合せ配列と前記圧縮対象配列とを対比し、前記圧縮対象配列において前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を候補配列の圧縮配列（圧縮候補配列）として選択する検索ステップと；
前記圧縮問合せ配列と前記検索ステップで選択した前記圧縮候補配列とについて、それぞれの圧縮前の配列における同一塩基の連続数の情報を準備する連続数準備ステップと；
前記同一塩基の連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する類似度演算ステップと；
前記類似度演算ステップにより演算した類似度に基づいて、前記問合せ配列と相対的に相同性が高い任意数の候補配列を順位付けて選択する選択ステップと；
前記選択ステップにより選択した前記任意数の候補配列の情報を出力する出力ステップとを有する。【００５８】
本発明の相同性検索方法は、問合せ配列と対象配列とについて、前述のように、圧縮配列および同一塩基連続数を対比して相同性を検索することが特徴であり、その他の条件や構成は特に制限されない。【００５９】
前記取得ステップにより取得される配列情報は、前述の相同性検索システムの前記取得ステップにより取得される配列情報と同様であり、対象配列および問合せ配列の圧縮前の配列情報があげられる。また、前記配列情報として、前記圧縮前の配列に代えて、または、加えて、例えば、圧縮配列、同一塩基の連続数等の情報が含まれてもよい。前記取得ステップにより、配列情報として圧縮配列を取得する場合、例えば、前記取得ステップと、圧縮配列を準備する前記圧縮配列準備ステップは、同じステップともいえる。また、前記取得ステップにより、配列情報として同一塩基の連続数の情報が取得される場合、例えば、前記取得ステップと、同一塩基の連続数の情報を準備する前記連続数準備ステップは、同じステップともいえる。また、問合せ配列および対象配列のいずれか一方の配列についてのみ、圧縮配列や同一塩基の連続数等の配列情報を取得し、他方の配列については、圧縮前の配列情報を取得してもよい。【００６０】
前記配列情報の取得ステップは、例えば、配列情報を入力する入力ステップがあげられる。また、配列情報が記憶された記憶手段（例えば、データベース）から配列情報を呼び出す、呼び出しステップであってもよい。対象配列および問合せ配列は、両方が入力ステップにより入力されてもよいし、いずれか一方が入力ステップにより入力されてもよい。また、対象配列および問合せ配列の両方が、呼び出しステップにより記憶手段から呼び出されてもよいし、いずれか一方が呼び出しステップにより記憶手段から呼び出され、他方は、入力ステップにより入力されてもよい。本発明においては、前記取得ステップが、例えば、前記問合せ配列および対象配列の両方を入力する入力ステップである形態、前記問合せ配列を入力する入力ステップと、前記対象配列が記憶されている対象配列記憶手段から前記対象配列の配列情報を呼び出す呼び出しステップとを有する形態、前記対象配列を入力する入力ステップと、前記問合せ配列が記憶されている問合せ配列記憶手段から前記問合せ配列の配列情報を呼び出す呼び出しステップとを有する形態、問合せ配列が記憶されている問合せ配列記憶手段および対象配列が記憶されている対象配列記憶手段から、それぞれ問合せ配列および対象配列を呼び出す呼び出しステップである形態等が例示できる。【００６１】
本発明の相同性検索方法においては、さらに、問合せ配列の配列情報を記憶する問合せ配列記憶ステップおよび／または対象配列の配列情報を記憶する対象配列記憶ステップを有することが好ましい。配列情報は、例えば、前述のような問合せ配列記憶手段や対象配列記憶手段に記憶することが好ましい。記憶する配列情報は、例えば、入力ステップにより入力された配列情報や、後述する圧縮変換ステップにより圧縮変換された圧縮配列の配列情報、連続数準備ステップで準備された同一塩基の連続数の情報等があげられる。【００６２】
本発明の相同性検索方法においては、前記問合せ配列および対象配列における同一塩基の連続数は、それぞれ、取得された配列情報に基づいて得てもよいし、予め配列情報として前述のような記憶手段に記憶されている場合には、前述の各記憶手段から呼び出してもよい。すなわち、本発明の相同性検索方法において、前記連続数準備ステップとしては、例えば、取得した問合せ配列および／または対象配列の配列情報に基づいて、問合せ配列および／または対象配列について、それぞれの圧縮前の配列における同一塩基の連続数を計数（演算）する計数ステップ（連続数計数（演算）ステップ）があげられる。また、前記連続数準備ステップは、前述の問合せ配列記憶手段および／または対象配列記憶手段にそれぞれの連続数の情報が記憶されている場合、問合せ配列の情報が記憶されている問合せ配列記憶手段および／または対象配列の情報が記憶されている対象配列記憶手段から呼び出すステップであってもよい。後者の場合、検索対象とする所望の配列を指定することで、各記憶手段からそれぞれの連続数の情報を呼び出すことができる。【００６３】
本発明の相同性検索方法においては、前記圧縮問合せ配列および圧縮対象配列は、それぞれ、取得された配列情報に基づいて得てもよいし、予め配列情報として前述のような記憶手段に記憶されている場合には、前述の各記憶手段から呼び出してもよい。すなわち、本発明の相同性検索方法において、前記圧縮配列準備ステップとしては、例えば、取得した問合せ配列および／または対象配列の配列情報に基づいて、圧縮問合せ配列および／または圧縮対象配列に圧縮変換する圧縮変換ステップがあげられる。また、前記圧縮配列準備ステップは、前述の問合せ配列記憶手段および／または対象配列記憶手段にそれぞれの圧縮配列が記憶されている場合、圧縮問合せ配列が記憶されている問合せ配列記憶手段および／または圧縮対象配列が記憶されている対象配列記憶手段から呼び出すステップであってもよい。後者の場合、検索対象とする所望の配列を指定することで、各記憶手段からそれぞれの圧縮配列を呼び出すことができる。【００６４】
前記検索ステップは、特に制限されず、ハッシュ検索ステップ、二分木検索ステップ、Ｂ木検索ステップ等があげられる。前記ハッシュ検索ステップは、例えば、前記圧縮問合せ配列と前記圧縮対象部分配列群の各圧縮対象部分配列とをキーとし、同じハッシュ関数を用いて、ハッシュ検索を行うことにより、前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索する。【００６５】
本発明の相同性検索方法においてハッシュ検索を行う場合、例えば、さらに、前記圧縮対象部分配列群の各圧縮対象部分配列をキーとし、同じハッシュ関数を用いて、対象配列用ハッシュテーブルを生成する対象配列用ハッシュテーブル生成ステップを有することが好ましい。この場合、前記検索ステップは、ハッシュ検索ステップであり、例えば、前記圧縮問合せ配列をキーとし、前記対象配列用ハッシュテーブル生成ステップと同じハッシュ関数を用いて、前記対象配列用ハッシュテーブル生成ステップで生成した前記対象配列用ハッシュテーブルのハッシュ検索を行うことにより、前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索する。【００６６】
また、ハッシュ検索を行う場合、さらに、２つ以上の前記圧縮問合せ配列をキーとし、同じハッシュ関数を用いて、問合せ配列用ハッシュテーブル生成する問合せ配列用ハッシュテーブル生成ステップを有することが好ましい。この場合、前記検索ステップは、ハッシュ検索ステップであり、例えば、前記圧縮対象部分配列群の各圧縮対象部分配列をキーとし、前記問合せ配列用ハッシュテーブル生成ステップと同じハッシュ関数を用いて、前記問合せ配列用ハッシュテーブル生成ステップで生成した前記問合せ配列用ハッシュテーブルのハッシュ検索を行うことにより、前記各圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索する。【００６７】
前記類似度演算ステップは、前記対応する塩基ごとの連続数の不一致度をペナルティスコアとし、前記対応する塩基ごとのペナルティスコアを加算することによって、類似度を演算することが好ましい。ただし、前記圧縮問合せ配列の上流末端塩基または下流末端塩基における圧縮前の連続数が、前記圧縮候補配列の上流末端塩基または下流末端塩基における圧縮前の連続数よりも短い不一致を除くことが好ましい。【００６８】
本発明の相同性検索方法は、前記選択ステップにおいて、前記類似度演算ステップにより、新たな候補配列の前記問合せ配列に対する類似度が演算された際、前記新たな類似度と、先立っての前記選択ステップで選択された前記任意数の候補配列の前記問合せ配列に対する類似度とに基づいて、前記各候補配列から、再度、任意数の候補配列を選択することが好ましい。このような場合、例えば、さらに、前記問合せ配列と前記選択ステップにより選択した任意数の候補配列との情報を記憶する記憶ステップを有することが好ましい。前記記憶ステップにおいて、例えば、前述のような記憶手段に、選択された任意数の候補配列の問合せ配列に対する類似度を記憶しておくことで、先立っての類似度と新たな類似との間で、再度、候補配列の選択を行うことが容易となる。【００６９】
本発明の相同性検索方法を用いて、問合せ配列が、対象配列のある部分配列にのみ特異的に相同するか否かを検索する場合には、さらに、問合せ配列用ハッシュテーブルのデータを更新するハッシュテーブル更新ステップを有することが好ましい。前記ハッシュテーブル更新ステップは、例えば、前記選択ステップにより、１つの問合せ配列に対して、最も高い相同性を示す同じ類似度の候補配列が２つ以上選択された際、前記問合せ配列用ハッシュテーブルのデータから、前記問合せ配列と、それに対して選択された２つ以上の候補配列を削除する。【００７０】
＜コンピュータプログラム＞
本発明のコンピュータプログラムは、本発明の相同性検索方法をコンピュータ上で実行可能なコンピュータプログラムである。【００７１】
＜電子媒体＞
本発明の電子媒体は、本発明のコンピュータプログラムを格納した電子媒体である。前記電子媒体は、コンピュータ読み取り可能な媒体であり、例えば、記録媒体である。【００７２】
（実施形態１）
ハードウェアの構成
本発明の相同性検索装置について、ハードウェア構成の概略を説明する。なお、以下に示す構成は、一例であり、本発明はこれに制限されない。【００７３】
図１は、本発明の相同性検索装置のハードウェア構成の一例を示すブロック図である。同図において、相同性検索装置１は、ＣＰＵ１０１、ＲＡＭ１０２、記憶手段（記憶装置）１０３、入出力Ｉ／Ｆ（インターフェイス）１０５、表示手段（ディスプレイ）１０６、入力手段（入力装置）１０７、通信デバイス１０８、および、ドライブ１０９を備えている。ＲＡＭ１０２、記憶装置１０３および入出力Ｉ／Ｆ（インターフェイス）１０５は、通信バス１０４によって、ＣＰＵ１０１に接続されている。入出力Ｉ／Ｆ（インターフェイス）１０５には、ディスプレイ１０６、入力装置１０７、通信デバイス１０８およびドライブ１０９が接続されている。【００７４】
ＣＰＵ１０１は、相同性検索装置１の全体の制御を担う。ＲＡＭ１０２は、コンピュータのメインメモリであり、ＣＰＵ１０１のワークメモリである。記憶装置１０３は、例えば、ＲＯＭ、ＨＤＤ、ＨＤ等である。ＲＯＭは、読み込みのみのメモリーであり、動作プログラムを格納している。ＨＤＤは、ＣＰＵ１０１の制御下、ＨＤに対するデータの読み込みと書き込みを制御し、ＨＤは、ＨＤＤの制御下で書き込まれたデータを記憶する。ドライブ１０９は、リムーバブル記録媒体用のドライブであり、ＣＰＵ１０１の制御下、リムーバブル記録媒体に対するデータの読み込み／書き込みを制御する。リムーバブル記録媒体としては、例えば、ＦＤ、ＣＤ−ＲＯＭ（ＣＤ−Ｒ、ＣＤ−ＲＷ）、ＭＯ、ＤＶＤ、メモリーカード等が使用でき、これらの記録媒体は、ドライブ１０９の制御で書き込まれたデータを記憶する。通常、ＲＡＭ１０２は、主記憶装置であり、ＲＯＭ、ＨＤおよびＦＤ等の外部記録媒体が補助記憶装置となる。本発明においては、ＣＰＵ１０１により、例えば、本発明のコンピュータプログラムやその他のプログラムが実行され、また、各種情報の読み込みや書き込みが行われる。図１の相同性検索装置１には、一例として、各種ソフトウェア（配列圧縮ソフトウェア１１１、検索システムソフトウェア１１２）を格納するプログラム格納部１１０と、情報を格納する情報格納部１１３とを備える形態を示す。これらの格納部は、例えば、前述の補助記憶装置に確保された一定の領域に設けられる。図１においては、プログラム格納部１１０および情報格納部１１３を、記憶装置１０３に確保された記憶領域として示す。これらのソフトウェアは、例えば、ＣＰＵ１０１によってＲＡＭ１０２上に呼び出され、ＯＳ（オペレーションシステム）と共同して実行されることで、それらの機能を実現する。前記配列圧縮ソフトウェア１１１は、問合せ配列や対象配列を圧縮変換するためのプログラムであり、前記検索システムソフトウェア１１２は、圧縮変換以外の本発明における処理を実行するプログラムである。また、これらのプログラムは、本発明のプログラムとして単一のソフトウェアであってもよい。【００７５】
ディスプレイ１０６は、文書等の各種情報を表示し、例えば、ＬＥＤディスプレイ、液晶ディスプレイ等がある。Ｉ／Ｆ（インターフェイス）１０５は、通信デバイス１０８を通じて、ＬＡＮやインターネット等の外部ネットワークに接続され、前記外部ネットワークを介して、他のサーバーや情報処理装置に接続される。本発明においては、例えば、ゲノムや遺伝子の核酸塩基配列データを備える外部データベース（ＤＢ）に接続される。Ｉ／Ｆ（インターフェイス）１０５は、前記ネットワークと内部とのインターフェイスを担い、他のサーバー等からのデータの入出力を制御する。通信デバイス１０８は、例えば、モデム等である。入力装置１０７としては、例えば、キーボードやマウス等があり、これによって文字、数字、各種指示、カーソルの移動等を行う。また、これらの構成部の他に、例えば、スキャナやプリンタ等を備えてもよい。前記スキャナは、例えば、文章等の画像情報を光学的に読み取り、画像データとして取り込むことができる。また、プリンタを備えてもよく、これは各種情報を印刷する。【００７６】
（実施形態２）
本発明の第１の相同性検索システムおよび第２のネットワーク型相同性検索システムの構成について、それぞれ一例を示す。【００７７】
第１のシステム構成例
図８に、本発明のシステムの構成の一例であるスタンドアローン型の全体構成図を示す。図８に示すシステムは、本発明の相同性検索システム１から構成され、相同性検索システム１は、データ入出力部１２と相同性検索部１３から構成される。相同性検索部１３は、例えば、配列情報の取得部、圧縮配列を準備する圧縮配列準備部（例えば、圧縮変換部）、圧縮候補配列の検索部、同一塩基の連続数準備部（例えば、連続数計数部）、類似度演算部、候補配列の選択部を有する。図１０に、スタンドアローン型の相同性検索装置のハードウェア構成の一例を示す。図示のように、相同性検索システム１は、データ入出力部１２、相同性検索部１３および記憶装置３７から構成されている。前記データ入出力部１２は、各ステップをコンピュータにより実行可能なプログラムを実行するＣＰＵ３１、入出力Ｉ／Ｆ（インターフェイス）３２、データの入力を行う入力装置３３、データの出力を行う出力装置３４を有するコンピュータ機器で構成される。相同性検索部１３は、プログラムが格納されたプログラム格納部３６およびプログラムを実行するＣＰＵ３５を有するコンピュータ機器で構成される。記憶装置３７は、例えば、問合せ配列および対象配列の圧縮前の配列情報、圧縮後の配列情報、同一塩基の連続数の情報、類似度、候補配列の順位等のデータが記憶される。なお、データ入出力部１２、相同性検索部１３、記憶装置３７は、あくまでも機能上のものであり、例えば、１台のコンピュータ機器で一体に構成してもよいし、複数台のコンピュータ機器で個別に構成してもよい。【００７８】
第２のシステム構成例
図９に、サーバーで処理するネットワーク型のシステムの全体構成図を示す。図９に示すように、本実施形態の相同性検索システム２は、端末２１、および、サーバーシステム２４から構成される。端末２１は、データ入出力部２２から構成される。サーバーシステム２４は、相同性検索部２３と対象配列が蓄積されたデータベース（対象配列ＤＢ）２５とから構成される。相同性検索部２３は、例えば、圧縮配列準備部（例えば、圧縮変換部）、圧縮候補配列の検索部、同一塩基の連続数準備部（例えば、連続数計数部）、類似度演算部、候補配列の選択部を有する。相同性検索部２３とサーバーシステム２４は、例えば、ＴＣＰ（Transmission  Control  Protocol）／ＩＰ（Internet  Protocol）に基づくインターネットとして機能する公衆網や専用線等の通信回線１００を介して接続されている。図１１に、前記ネットワーク型システムの装置の構成の一例を示す。端末２１は、データ入出力部２２および通信インターフェイス４７から構成され、通信インターフェイス４７を介して通信回線に接続されている。データ入出力部２２は、プログラムを実行するＣＰＵ４１、入出力Ｉ／Ｆ４２、データの入力を行う入力装置４３およびデータの出力を行う出力装置４４から構成される。前記データ入出力部２２および通信インターフェイス４７は、あくまでも機能上のものであり、例えば、１台のコンピュータ機器で一体に構成してもよいし、複数台のコンピュータ機器で個別に構成してもよい。サーバーシステム２４は、相同性検索部２３、対象配列が蓄積されたデータベース（対象配列ＤＢ）２５および通信インターフェイス４８から構成され、通信インターフェイス４８を介して通信回線に接続されている。相同性検索部２３は、候補配列を選択するための一連のステップを実行可能なプログラムを実行するＣＰＵ４５および前記プログラムが格納されたプログラム格納部４６で構成される。相同性検索部２３、対象配列ＤＢ２５および通信インターフェイス４８は、あくまでも機能上のものであり、例えば、１台のコンピュータ機器で一体に構成してもよいし、複数台のコンピュータ機器で個別に構成してもよい。【００７９】
（実施形態３）
本発明の相同性検索システムの一例について、以下に説明する。図２は、本実施形態における相同性検索システムの構成の概略を示すブロック図である。なお、本発明は、この実施形態には制限されず、発明の要旨を変更しない範囲で種々変形可能である。【００８０】
図２に示すように、本実施形態の相同性検索システムは、配列情報の取得手段（入力手段）２０１、圧縮配列準備手段２０２、圧縮候補配列の検索手段２０３、同一塩基の連続数準備手段２０４、類似度演算手段２０５、候補配列の選択手段２０６、情報記憶手段２０７および出力手段２０８を備える。この相同性検索システムは、例えば、前述のようなハードウェア構成のコンピュータシステムによって構築された相同性検索装置があげられる。また、各構成手段は、例えば、コンピュータのＣＰＵが所定のプログラムを実行することによって実現される機能的ブロックであればよい。このため、例えば、各構成手段が、ハードウェアとして実装されてなくともよく、前述のようなネットワークシステムであってもよい。【００８１】
配列情報の取得手段２０１は、対象配列の核酸塩基配列および問合せ配列の核酸塩基配列の配列情報を取得する機能を有する。この情報の取得は、例えば、前述のような入力装置による入力によって行うことができる。また、前述のように、インターネット等の外部ネットワークにアクセスして、外部データベース等から入手してもよい。外部ネットワークから前記情報を入手する場合、例えば、データベースの情報を、コンピュータの記憶装置（例えば、図１におけるＲＡＭ１０２や情報格納部１１３等）にダウンロードしてもよいし、通信回線を接続した状態で、前述の情報を利用することもできる。情報元となる外部データベースは、制限されない。また、配列情報が記憶されたリムーバブル記録媒体を利用することもできる。【００８２】
圧縮配列準備手段２０２は、例えば、核酸塩基配列の配列情報を、同一塩基が２個以上反復したホモポリマー領域を前記塩基１個に置き換えた圧縮配列に変換する機能を有する（圧縮変換手段）。すなわち、この圧縮配列準備手段２０２により、配列情報の取得手段２０１によって取得した対象配列および問合せ配列について、同一塩基が２個以上反復したホモポリマー領域を前記塩基１個に置き換えた圧縮配列の配列情報が作成される。【００８３】
ここで、核酸塩基配列の圧縮変換の一例を、図４を用いて説明する。図４は、核酸塩基配列の圧縮変換ならびに後述する塩基の連続数の計数の概略を示す図である。同図において、Ｄ１が核酸塩基配列である。この核酸塩基配列においては、同じ塩基が連続して並んでいる領域が存在する。具体的に、左端（５’側）から、６個のアデニンが連続した領域、８個のチミンが連続した領域、７個のグアニンが連続した領域、１個のチミンをおいて、さらに、９個のシトシンが連続した領域、３個のアデニンが連続した領域を有している。このように同じ塩基が連続している領域が、それぞれ、本発明における「ホモポリマー領域」である。圧縮変換では、このように同じ塩基が複数個（２個以上）連続している（反復している）領域については、塩基を１個と見なして、４種類の塩基について種別の並びのみを示す配列とする。図４において、Ｄ２で示す配列が、Ｄ１で示す核酸塩基配列に対する圧縮配列となる。【００８４】
前述のように、一般的な相同性検索では、ゲノムスケールの対象配列は、通常、部分配列に分解してから検索が行われるため、本発明においても、対象配列は、部分配列に区切って検索にかけることが好ましい。したがって、本発明における対象配列の圧縮配列は、全長の圧縮配列でもよいが、前述のような圧縮対象部分配列群であることが好ましい。前記対象配列からの部分配列の作成は、限定されず、従来公知の手法をとることができる。具体例としては、例えば、圧縮後の対象配列の先頭から、順次、１塩基ずつずらして圧縮対象部分配列群を作成する。すなわち、本実施形態のシステムでは、対象配列の配列情報を取得手段２０１で取得すると、圧縮配列準備手段２０２において、圧縮された対象配列の配列情報を作成でき、さらに、これを固定長に区切った圧縮対象部分配列からなる圧縮対象部分配列群の配列情報を作成できる。また、対象配列の相補鎖についても検索を行う場合には、例えば、前記圧縮対象部分配列群の配列情報と、それらの相補鎖の圧縮対象部分配列群の情報を、交互に取得すればよい。後者の圧縮対象部分配列群の配列情報は、前者の圧縮対象部分配列の塩基の並びから、相補塩基について逆列とすることにより容易に決定できる。また、後述する塩基の連続数の情報については、例えば、前者の各ホモポリマー領域における同一塩基の連続数を順に示す列を、相補塩基について逆列とすることにより取得できる。例えば、前者の連続数の並びが「６−８−７−１−９−３」であれば、後者の連続数の並びは、「３−９−１−７−８−６」となる。【００８５】
圧縮候補配列の検索手段２０３は、以下の機能を有する。すなわち、まず、圧縮配列準備手段２０２において作成した対象配列の圧縮配列（圧縮対象配列）と問合せ配列の圧縮配列（圧縮問合せ配列）とを対比させる。そして、前記圧縮対象配列において、前記圧縮問合せ配列と一致する圧縮対象部分配列を絞り込み検索して、絞り込んだ前記圧縮対象部分配列を、候補配列の圧縮配列（圧縮候補配列）として選択する。【００８６】
同一塩基の連続数準備手段２０４は、例えば、圧縮候補配列の検索手段２０３で選択した前記圧縮候補配列および前記圧縮問合せ配列について、前記ホモポリマー領域における同一塩基の連続数を計数する機能を有する（連続数計数手段）。なお、前述のように、システム外で計数された連続数の情報を入力する形態であってもよい。【００８７】
ここで、同一塩基の連続数の計数の一例を、前述の図４を用いて説明する。前述のように、同図において、Ｄ１が圧縮前の核酸塩基配列であり、Ｄ２が前記核酸塩基配列を圧縮変換した圧縮配列である。この圧縮配列Ｄ２における各塩基の連続回数が、本発明における前記連続数にあたる。なお、本実施形態においては、ホモポリマー領域の塩基数を連続数として計数（１個目の塩基も換算）し、反復していない塩基は１個として計数している。この同一塩基の連続数の情報は、例えば、同図に示すように、同一塩基連続数の列Ｄ３「６８７１９３」として表すことができる。圧縮配列Ｄ２「ＡＴＧＴＣＡ」の要素数と、同一塩基連続数の列Ｄ３「６８７１９３」における要素数は共通し、圧縮前の核酸塩基配列Ｄ１の要素数は、圧縮配列Ｄ２の要素数とを比較すると、ホモポリマー領域が出現する分短くなる。【００８８】
類似度演算手段２０５は、同一塩基の連続数準備手段２０４により計数した前記連続数の情報に基づいて、前記圧縮問合せ配列と前記圧縮候補配列との間で、対応する塩基ごとに、前記塩基の連続数を対比し、前記連続数の一致度または不一致度から、前記候補配列の前記問合せ配列に対する相同性を示す類似度を演算する機能を有する。【００８９】
候補配列の選択手段２０６は、類似度演算手段２０５より演算された前記類似度結果を比較することにより、前記候補配列について、前記問合せ配列に対する相同性の順位付けを行い、相対的に相同性が高い任意数の候補配列を選択する機能を有する。【００９０】
情報記憶手段２０７は、候補配列の選択手段２０６で選択した前記問合せ配列に対して相対的に相同性が高い任意数の候補配列と、問合せ配列との間における前記類似度とを記憶する機能を有する。特に、圧縮候補配列の検索手段２０３において複数の候補配列が検索される場合は、例えば、任意数まで相同性が高い候補配列の類似度を記憶し、さらに、新たな類似度が演算された際に、記憶した複数の類似度と新たな類似度とを比較して、再度順位付けを行い、相同性が高い任意数の候補配列を選択し、これらの情報を記憶することが好ましい。これによって、問合せ配列との相同性がより高い対象配列の部分配列をさらに検索していくことが可能となる。【００９１】
出力手段２０８は、情報記憶手段２０７に記憶された情報を出力する機能を有する。出力する情報は、例えば、相同性検索システムがディスプレイ等の表示手段（表示装置）を備える場合には、その表示画面に表示されてもよいし、また、プリンタによりプリントアウトすることによって外部に表示されてもよい。また、例えば、コンピュータの記憶装置（例えば、情報格納部）や、リムーバブル記録媒体に出力され、格納されてもよい。【００９２】
つぎに、図５を用いて、本実施形態の相同性検索システムにおける処理の流れの一例を説明する。図５は、前記処理の流れを示すフローチャートである。この処理は、本発明の相同性検索方法の一例であり、例えば、本発明の相同性検索システムや本発明のコンピュータプログラムにより実行できる。なお、対象配列の圧縮配列（圧縮対象配列）は、前述した圧縮対象部分配列群として説明する。【００９３】
まず、問合せ配列ごとの結果を格納する結果格納領域の初期化（ステップＭ０）から開始される。ついで、問合せ配列ならびに対象配列の配列情報が取得（入力）される（ステップＭ１）。例えば、直接的にマウス等の入力装置１０７から配列情報を入力したり、あるいは、間接的に対象配列が格納されたファイルやネットワーク上の場所を特定することで、システム（例えば、ＲＡＭ１０２や記憶装置１０３等）に取り込んだ配列情報に対して、後述する処理が開始される。【００９４】
つぎに、取得された問合せ配列の配列情報を、圧縮配列に圧縮変換し（ステップＭ２）、また、取得された対象配列の配列情報を、圧縮配列（圧縮対象部分配列群）に圧縮変換する（ステップＭ３）。問合せ配列および対象配列の圧縮変換（ステップＭ２およびＭ３）は、例えば、順不同で別個に行ってもよいし、並行して行うこともできる。問合せ配列が複数の場合、後述するステップを実行する前に、全ての問合せ配列についての圧縮変換を完了してもよいし、圧縮変換した配列から順次、後述するステップに供することで、このステップＭ２と後述ステップを並行して行ってもよい。また、対象配列についても、後述するステップを実行する前に、対象部分配列群に含まれる全対象部分配列の圧縮変換を完了してもよいし、圧縮変換した配列から順次、後述するステップに供することで、このステップＭ３と後述ステップを並行して行ってもよい。なお、問合せ配列が複数の場合（特に大量である場合）には、ハッシュテーブルを作成することが好ましい。ハッシュテーブルを利用すれば、例えば、約1,000,000〜5,000,000個の問合せ配列であっても、迅速な処理が可能となる。また、対象配列についても、ゲノムスケールであることから、圧縮対象部分配列群についてハッシュテーブルを作成することが好ましい。これらのハッシュテーブルの作成については、後述する。【００９５】
続いて、問合せ配列の圧縮配列（圧縮問合せ配列）と対象配列の圧縮対象部分配列群とを対比し、圧縮問合せ配列と一致する圧縮対象部分配列の検索を行う（ステップＭ４）。そして、圧縮問合せ配列と一致する圧縮対象部分配列を検索できれば、その圧縮対象部分配列を候補配列の圧縮対象部分配列（以下、「圧縮候補配列」ともいう）として選択する。他方、圧縮問合せ配列と一致する圧縮対象部分配列が検索できなかった場合は、ステップＭ１１に進む。【００９６】
本発明においては、このように、まず、問題となっていたホモポリマー領域の同一塩基連続数を考慮しない圧縮配列同士を対比し、一致する候補配列を選択している。このため、従来のように、例えば、塩基の連続数が異なるのみで非類似と判断されたり、反対に、塩基の連続数の問題を考慮するあまり、ホモポリマー領域における同一塩基連続数以外で不一致が生じるものまでも、類似と判断するというような問題が回避できる。少なくとも、塩基の種類の並びに関しては、一致しているため、後は、後述するように、塩基の連続数に関して相同性を判断し、候補配列の相同性の順位（順序）を判断することによって、精度良く相同性検索が行える。【００９７】
そして、ステップＭ４で選択した圧縮候補配列の圧縮問合せ配列に対する相同性を示す類似度を演算する（ステップＭ５）。類似度の演算にあたっては、圧縮候補配列および圧縮問合せ配列のそれぞれについて、各ホモポリマー領域における同一塩基の連続数の情報が必要である。したがって、このステップＭ５においては、類似度の演算のために、まず、圧縮候補配列および圧縮問合せ配列について、前記ホモポリマー領域における同一塩基の連続数を計数する。具体的には、前記圧縮候補配列の圧縮前の核酸塩基配列および圧縮問合せ配列の圧縮前の核酸塩基配列から、前記ホモポリマー領域における同一塩基の連続数を計数する。問合せ配列における連続数の計数は、この時点で行ってもよいし、例えば、圧縮変換の際に逐次または並行して行ってもよい。また、対象配列の各部分配列については、前記問合せ配列と同様に、例えば、圧縮変換の際に逐次または並行して行ってもよいが、候補配列についての結果が必要であることから、対象部分配列全てについて計数を行うのではなく、ステップＭ４で選択された圧縮候補配列についてのみ計数を行ってもよい。【００９８】
また、予め、各ホモポリマー領域における同一塩基の連続数を計数しておき、これらの情報を、必要に応じて、例えば、直接入力したり、記憶装置や外部記録媒体等から読み込んでもよい。類似度の演算方法については、後述する。【００９９】
つぎに、ステップＭ５で得られた類似度の結果を、他の類似度と比較する（ステップＭ６）。相同性検索においては、通常、問合せ配列に対して相同性を示す対象部分配列が複数得られた場合には、相同性についての順序を付けたり、また、最も相同性が高い対象部分配列（すなわち特異性が高い対象部分配列）の選択が行われる。したがって、本発明においても、ステップＭ４において、圧縮問合せ配列と一致する圧縮候補配列が検索された場合には、各候補配列の問合せ配列に対する相同性を比較することによって、例えば、相同性についての順序付けを行い、相同性が高い任意数の候補配列を選択する。前述のように、選択する候補配列の数は、制限されず、任意の数を設定できる。【０１００】
このステップＭ６の次工程は、ステップＭ６の比較結果に応じて以下のように処理できる。
（１）ステップＭ６で得られた結果（現類似度）が、初めての類似度の場合は、ステップＭ８に進み、問合せ配列の結果として、前記現類似度を、初期化された前記問合せ配列用の結果格納領域に記録する（ステップＭ８）。記録する情報は、問合せ配列に対する候補配列の類似度の他に、例えば、対象配列の種類（例えば、ゲノムの種類、染色体の種類等）、対象配列の順鎖および逆鎖の種類、対象配列における候補配列の座標等があげられる（以下、同様）。
（２）ステップＭ６で得られた現類似度結果が、２つ目以降に得られた結果であって、候補配列が任意数に到っていない場合、この結果を、さらに前記問合せ配列用の結果格納領域に記録する（ステップＭ８）。この際、類似度に基づいて、問合せ配列に対する各候補配列の順序付けを行う。
（３）ステップＭ６で得られた結果（現類似度）が、２つ目以降に得られた結果であって、候補配列が任意数に到っている場合、現類似度とすでに記録された各類似度とに基づいて、問合せ配列に対する各候補配列の順序付けを再度行い、上位から任意数の候補配列を選択し、これらの情報を置換記録する（ステップＭ８）。選択されなかった候補配列は、ステップＭ１１に進む。
（４）ステップＭ６で得られた結果（現類似度）が、問合せ配列との相同性を示さない場合、または、極めて相同性が低い結果の場合には、ステップＭ１１に進む。【０１０１】
また、候補配列が、ある問合せ配列にのみ特異的に相同するか否かを検索する場合には、ステップＭ６の次工程は、ステップＭ６の比較結果に応じて以下のように処理できる。
（５）ステップＭ６で得られた現類似度が、２つ目以降に得られた結果であって、記録された類似度よりも高い相同性を示す類似度の場合（特に、問合せ配列と候補配列とが完全一致）、前記現類似度を、最良の類似度として記録する（ステップＭ８）。
（６）ステップＭ６で得られた現類似度が、２つ目以降に得られた結果であって、記録された類似度と同じ類似度の場合、問合せ配列に対して特異性があるか否かの判断（特異性検索）を行う（ステップＭ７）。すなわち、現類似度と記録された類似度とが同じ場合、この類似度が最良の類似度（最良の値）か否かを判断する。最良の値とは、例えば、図６を用いて後述するペナルティスコアによる類似度の算出方法に従えば、「０.０（最小値）」であり、これは問合せ配列と候補配列とが完全一致であることを意味する。このように問合せ配列と完全一致である候補配列が２つ以上存在するということは、結果的に、問合せ配列が対象配列に対して特異性を示さないことを示す。したがって、このような場合には、問合せ配列は対象配列に対して特異性なしとの情報を記録する（ステップＭ１０）。問合せ配列はこれらの候補配列に対する特異性がないことが明らかであり、以降の検索にこれを含めることが不要になる。したがって、複数の問合せ配列を検索する場合には、前記問合せ配列のデータを削除してもよい。また、これらの候補配列についても、前記問合せ配列に対する特異性がないことが明らかであり、以降の検索にこれを含めることが不要となる。したがって、特異性がないことを記録した後、前記候補配列を、検索する対象のデータから削除してもよい。このように検索するデータが減少することで、例えば、システムの性能は逆比例してさらに向上する。他方、現類似度と記録された類似度とが同じであっても、前述のような最良の値（最良のスコア）でない場合には、現スコアを、前記問合せ配列用の結果格納領域に記録する（ステップＭ９）。【０１０２】
そして、ステップＭ１１において、ある問合せ配列について、準備した対象配列の検索を終了したと判断した場合には、問合せ配列について、記録した類似度やその他の情報を出力し（ステップＭ１３）、対象配列との検索が終了したと判断した場合には、検索を終了する。他方、ステップＭ１１において、ある問合せ配列に対して準備した対象配列との検索が残っている場合には、次の対象配列の圧縮変換（ステップＭ３）または圧縮変換された圧縮対象部分配列群との対比（ステップＭ４）に移動する（ステップＭ１２）。【０１０３】
また、ある問合せ配列について、準備した対象配列の検索が終了した場合、さらに他の問合せ配列が準備されている場合には、他の問合せ配列についても同様の処理を行う。なお、問合せ配列が複数の場合は、ある問合せ配列についてステップＭ０〜Ｍ１３の一連の処理が終わってから、他の問合せ配列について処理を行ってもよいし、逐次または並行して処理を行うこともできる。そして、検索が終了した後に、蓄積した情報（類似度や対象配列における座標等）を、問合せ配列ごとに出力すればよい。【０１０４】
（実施形態４）
本発明の相同性検索システムのその他の例について、以下に説明する。図３は、本実施形態における相同性検索システムの構成の概略を示すブロック図である。なお、特に示さない限り、前記実施形態３における図２のシステムと同様である。【０１０５】
この相同性検索システムは、実施形態３のシステムにおける配列情報の取得手段２０１と圧縮変換手段２０２に代えて、圧縮配列の取得手段３０１を備える。このように本実施形態の相同性検索システムでは、予め圧縮変換処理された圧縮問合せ配列や圧縮対象配列の配列情報が取得（入力）されてもよい。【０１０６】
（実施形態５）
本発明における類似度の算出の一例について、図６を用いて説明する。なお、本発明は、以下の内容には制限されず、本発明の要旨を変更しない範囲で種々変形可能である。【０１０７】
図６は、類似度の算出に必要な情報の一例を列挙した図である。同図において、Ｓ１〜Ｓ３は、対象配列に関する情報であり、Ｓ４〜Ｓ６は、問合せ配列に関する情報である。Ｓ１は、圧縮前の対象配列であり、Ｓ２は、圧縮対象配列、Ｓ３は、対象配列の塩基の連続数を示す列である。同様に、Ｓ４は、圧縮前の問合せ配列であり、Ｓ５は、圧縮問合せ配列であり、Ｓ６は、問合せ配列の塩基の連続数を示す列である。【０１０８】
本発明の相同性検索システムにおいては、前述のように、まず、対象配列の圧縮配列（圧縮対象配列）と問合せ配列の圧縮配列（圧縮問合せ配列）との対比により、圧縮問合せ配列（Ｓ５）と一致する対象配列の圧縮対象部分配列（Ｓ２）が検索される。図６に示すように、圧縮問合せ配列（Ｓ５）と圧縮対象配列（圧縮対象部分配列Ｓ２）は、４種類の塩基が同じ連なりを示している。【０１０９】
本実施形態では、類似度の演算方法として、圧縮問合せ配列と圧縮対象部分配列との間で、前記対応する塩基ごとの連続数の不一致度をペナルティスコアとし、前記対応する塩基ごとのペナルティスコアを加算することによって、類似度を演算する例を説明する。なお、後に説明するが、前記圧縮問合せ配列の上流末端塩基または下流末端塩基における圧縮前の連続数が、前記圧縮候補配列の上流末端塩基または下流末端塩基における圧縮前の連続数よりも短い不一致は除く。このように不一致度を相同性の指標とする場合、例えば、相対的に値が大きいほど相対的に非類似であり、相対的に値が小さいほど相対的に類似であると判断できる。【０１１０】
対応する塩基ごとのペナルティスコアを演算するにあたっては、圧縮対象配列（Ｓ２）と圧縮問合せ配列（Ｓ５）とにおいて、上流側末端塩基のペナルティスコア、下流側末端塩基のペナルティスコア、および、前記両末端以外の内部塩基のペナルティスコアを別途計算する。そして、これらの総和（総和ペナルティー）を、相同性を示す類似度とする。以下、各ペナルティスコアの演算について説明する。【０１１１】
図６に示す式Ｓ８〜Ｓ１０は、それぞれ、前記上流側末端のペナルティスコアを演算する式（Ｓ８）、前記内部の各塩基のペナルティスコアを演算する式（Ｓ９）、前記下流側末端のペナルティスコアを演算する式（Ｓ１０）である。そして、式Ｓ７が、ペナルティの総和を演算する式であり、問合せ配列（Ｓ４）と対象配列の部分配列（Ｓ１）との相同性を示す指標（類似度）が得られる。なお、図６の式Ｓ８〜Ｓ１０において、ホモポリマー数とは、一つのホモポリマー領域における同一塩基の連続数を意味する。式Ｓ８において、ホモポリマー数１とは、圧縮対象配列（Ｓ２）と圧縮問合せ配列（Ｓ５）における対応する１番目の塩基種（上流側末端塩基種）の連続数である。式Ｓ９において、ホモポリマー数ｉとは、前記両圧縮配列（Ｓ２、Ｓ５）における対応するｉ番目（ｉは、ｎ−１であり、ｎは、３以上の整数）の塩基種の連続数である。式Ｓ１０において、ホモポリマー数ｎとは、圧縮対象配列（Ｓ２）と圧縮問合せ配列（Ｓ５）における対応する最後（ｎ番目、ｎは、３以上の整数）の塩基種（下流側末端塩基種）の連続数である。【０１１２】
まず、内部の塩基についてのペナルティスコアを求める式Ｓ９について説明する。この式の場合、ある塩基について問合せ配列における連続数と対象配列における連続数とが同じである場合（問合せ配列ホモポリマー数＝対象配列ホモポリマー数）、前者を後者で割った値は１となるため、その自然対数は０である。また、問合せ配列における連続数が、対象配列における連続数よりも多い場合（問合せ配列ホモポリマー数＞対象配列ホモポリマー数）、前者を後者で割った値は１以上となるため、その自然対数は正の値となる。他方、ある塩基について問合せ配列における連続数が、対象配列における連続数よりも少ない場合（問合せ配列ホモポリマー数＜対象配列ホモポリマー数）、前者を後者で割った値は１以下となり、その自然対数は、負の値となる。つまり、問合せ配列における連続数と対象配列における連続数とが近似する程、自然対数は０に近づき、異なる程、自然対数の値は、０から離れる。したがって、式Ｓ９においては、前記自然対数の絶対値をペナルティスコアとしている。【０１１３】
つぎに、式Ｓ８および式Ｓ１０について説明する。末端塩基についても、前記式Ｓ９と同様に、問合せ配列における連続数と対象配列における連続数とが同じである場合（問合せ配列ホモポリマー数＝対象配列ホモポリマー数）、前者を後者で割った値は１となるため、その自然対数は０である。また、問合せ配列における連続数が、対象配列における連続数よりも多い場合（問合せ配列ホモポリマー数＞対象配列ホモポリマー数）、前者を後者で割った値は１以上となり、その自然対数は、正の値となる。しかしながら、問合せ配列における連続数が対象配列における連続数より多い場合、すなわち、対象配列における連続数が少ない場合、末端塩基に関しては、以下のように考える。問合せ配列は、ゲノムや染色体における部分配列であるため、末端のホモポリマー領域については、問合せ配列における連続数が対象配列における連続数よりも少ないことのみをもって、相同性が低いという評価を行うことは妥当ではない。そこで、末端塩基の連続数に関しては、式Ｓ９のように絶対値はとらず、対象配列の連続数よりも問合せ配列の連続数が少ない場合、同じ連続数の場合には、ペナルティスコアを０とし、問合せ配列の連続数が大きい場合、すなわち自然対数が正の値となる場合のみを演算する式（Ｓ８、Ｓ１０）としている。【０１１４】
そして、式Ｓ７において、式Ｓ８で算出した前記上流側末端のペナルティスコア、式Ｓ９で算出した前記内部の各塩基のペナルティスコアの和、および、式Ｓ１０で算出した前記下流側末端のペナルティスコアを加算して、問合せ配列（Ｓ４）と対象配列の部分配列（Ｓ１）との相同性を示す指標（類似度）を得る。なお、本例においては、「０」が、最大の一致度、すなわち完全一致を表し、相対的に数値が大きくなるほど類似度は、相対的に低くなる。通常は、上限の閾値、例えば、２の自然対数を設け、これ以上は相同性なしとみなすことができる。【０１１５】
式Ｓ７〜Ｓ１０は、本発明を実現するための一例であり、これには制限されない。一例として、前述のように対数を用いるのは、誤差のペナルティの累積を加算的に表現するためであって、例えば、各式における分子分母の逆転、正負の逆転、自然対数を取るか指数のまま扱うか、自然対数を使うか対数の底として別の値を使うか、絶対値を取るか自乗を取るかなど、等価な式や応用した式に変形することが可能である。また、本発明の用途に応じて、場所による重み付けを付ける等の変更も可能である。また、このような式の変形や構築は、本明細書の記載に基づけば、当該技術分野における当業者であれば実施可能である。【０１１６】
具体例として、例えば、式Ｓ７において、絶対値を取る前の正負の差によって、重み付けを与えることで、オーバーコール、アンダーコールの評価を組み込むことができる。ホモポリマー領域における同一塩基の塩基数のエラーについては、例えば、塩基配列の決定方法によって、塩基数が多く計数される、または、塩基数が少なく計数される、という傾向があるという可能性を示唆している。したがって、この傾向を考慮することによって、さらに、ペナルティスコアからエラーによる影響を軽減することができる。例えば、問合せ配列側の同一塩基数が多いという傾向が予めわかっている場合には、以下のような処理が可能である。すなわち、例えば、図６に示す式を用いて各塩基についてのペナルティスコアを算出する際、絶対値を取る前の値が正の場合、つまり、問合せ配列側の連続数が対象配列側の連続数よりも多い場合（問合せ配列ホモポリマー数＞対象配列ホモポリマー数）には、例えば、これに１未満の係数をかける。これにより、問合せ配列の同一塩基数が多いという傾向によって大きくなる見かけのペナルティスコアを、軽減することができる。つまり、「オーバーコールの傾向」を反映して、より信頼性の高い類似度を求めることができる。他方、例えば、問合せ配列側の同一塩基数が少ないという傾向が予めわかっている場合には、以下のような処理が可能である。すなわち、例えば、図６に示す式を用いて各塩基についてのペナルティスコアを算出する際、絶対値を取る前の値が負の場合、つまり、問合せ配列側の連続数が対象配列側の連続数よりも少ない場合（問合せ配列ホモポリマー数＞対象配列ホモポリマー数）には、例えば、これに１未満の係数をかける。これにより、問合せ配列の同一塩基数が少ないという傾向によって大きくなる見かけのペナルティスコアを、軽減することができる。つまり、「アンダーコールの傾向」を反映して、より信頼性の高い類似度を求めることができる。なお、式Ｓ８（ｈｅａｄ＿ｐｅｎａｌｔｙ）と式Ｓ１０（ｔａｉｌ＿ｐｅｎａｌｔｙ）は、前述のように、ともに正の数だけ積算されるので、常に、前者のケース（絶対値を取る前の値が正）において、１未満の係数を掛けるだけとなる。【０１１７】
さらに、塩基の種別（Ａ，Ｇ，Ｃ，Ｔ）に関する同一塩基数の傾向も、前述と同様に重み付けを行うことが可能である。つまり、式Ｓ７の部分式である式Ｓ９により各塩基についてのペナルティスコアを算出する際、絶対値を取る前の値の正負に関して、塩基種別毎に重み付け計数を変えれば、例えば、塩基種別毎にオーバーコール、アンダーコールの評価傾向を反映することも可能となる。【０１１８】
（実施形態６）
本発明における対象配列用ハッシュテーブルの一例について、説明する。なお、本発明は、以下の内容には制限されず、本発明の要旨を変更しない範囲で種々変形可能である。【０１１９】
ハッシュテーブルは、データ構造であり、例えば、圧縮対象部分配列群の各圧縮対象部分配列の文字列にハッシュ関数をかけた値によって、テーブル内の要素に直接インデックス付けされている。文字列に対してハッシュ関数をかけた数値を得る方法は、制限されず、従来公知の手法が採用できる。具体例としては、例えば、プログラミング言語のｊａｖａの中にある、標準的パッケージクラスjava.  lang.  Stringのhash  Codeメソッドに定義されているものを使用することで、容易に実現できる。また、整数空間に写像された値をさらにテーブル要素数で除して、正の剰余を算出することで、必要なインデックスを得ることができる。【０１２０】
異なる文字列であっても、値の衝突によって、同一のハッシュテーブルのインデックスに割り振られる場合がある。この場合、例えば、オーバーフロー領域を、対象配列の圧縮後の長さ分確保しておくことが好ましい。そして、例えば、衝突した文字列要素同士を次々に順次指し示すデータ構造をとることによって、例えば、あるハッシュインデックスに対する対象配列内の要素を、直接に、次々にアクセスすることができる。ハッシュテーブルの最後の要素には、通常、終了を示す空データを格納する。これは、通常、主記憶装置であるＲＡＭ中に置くことが望ましいが、容量が物理的制限を超える場合には、例えば、外部記憶装置に置いておき、必要に応じて主記憶装置にキャッシュしてもよい。【０１２１】
このようにオーバーフロー領域を含む対象配列用ハッシュテーブルを予め作成すれば、例えば、圧縮対象配列の取得（図５ステップＭ３）と、圧縮問合せ配列と一致する圧縮対象部分配列の検索（図５ステップＭ４）とを組み合わせることができる。そして、対象配列はゲノムスケールであるために、極めて長い配列であるが、ハッシュテーブルを用いたハッシュ検索によれば、圧縮問合せ配列と不一致な圧縮対象部分配列を飛ばして、次の圧縮対象部分配列を一回の論理アクセスで取得することができる。また、ハッシュテーブルを作成すれば、例えば、図５に示すステップＭ１１で、ある対象配列についての検索が終了した場合、対象配列用ハッシュテーブルの次のハッシュエントリーに進むことにより、より高速に次の対象配列（圧縮対象配列群）を得ることができる。【０１２２】
前記ハッシュテーブルは、例えば、必要に応じて、圧縮前の対象部分配列の配列や、圧縮前の対象配列における座標、対象部分配列の各ホモポリマー領域における同一塩基の連続数等と、ホモポリマー数との対応が取れるような、データ構造とすることが好ましい。また、システムのライフサイクル上、一度しか検索の必要がない対象配列に関しては、例えば、このようなハッシュテーブルは、特に必要なく、例えば、適宜、圧縮処理のみを行い、圧縮問合せ配列との対応を行うことでも足りる。対象配列用ハッシュテーブルを作成しない場合であっても、後述する問合せ配列用ハッシュテーブルによる性能の向上は阻害されない。【０１２３】
ハッシュテーブルについては、何ら制限されず、例えば、Donald  Knuth.  “The  Art  of  Computer  Programming”  Volume3,  Sorting  and  Searching,  second  edition,  1998,  pp.  513-558,  ISBN  0-201-89685-0.を参照できる。また、本発明においては、前述のように、ハッシュ検索以外に、二分木検索、Ｂ木検索があげられ、それぞれ、例えば、Donald  Knuth.  Fundamental  Algorithms,  Third  Edition.  Addison-Wesley,  1997.  pp.318-348.  ISBN  0-201-89683-4.およびR.  Bayer  and  E.  McCreight.  "Organization  and  Maintenance  of  Large  Ordered  Indexes,"  Acta  Informatica,  1,  1972.等が参照できる。なお、ハッシュ検索、二分木検索、Ｂ木検索は、例示であって、本発明は、これらには何ら制限されない。【０１２４】
（実施形態７）
本発明における問合せ配列用ハッシュテーブルの一例について、図７を用いて説明する。なお、本発明は、以下の内容には制限されず、また、特に示さない限り、実施形態６と同様にハッシュテーブルを作成できる。【０１２５】
図７に、問合せ配列用ハッシュテーブルの構造の一例を示す。このハッシュテーブルは、例えば、各問合せ配列の各文字列にハッシュ関数をかけた値によって、テーブル内の要素に直接インデックス付けされている。前述と同様に衝突に関しては、例えば、次の要素とチェイニングすることでオーバーフロー領域を形成することが好ましい。【０１２６】
問合せ配列は、前述のように、検索の進行に併せて、検索結果を記録することが好ましい。したがって、例えば、問合せ配列用ハッシュテーブルとともに、各種検索情報を格納したテーブルを作成することが好ましい。前記検索情報格納テーブルには、例えば、類似度に基づく相同性の順位（Ｕ３）、問合せ配列に相同する対象配列の染色体番号（Ｕ４）、前記対象配列のストランドの種別（Ｕ５）、圧縮前の対象配列（対象部分配列）の染色体上の位置（Ｕ６）、類似度（Ｕ７）等があげられる。【０１２７】
また、前述のステップＭ７（図５）に示すように、特異性検索を行う場合には、適宜、問合せ配列用ハッシュテーブルのデータを削除することが好ましい。前述のように、特異性検索は、例えば、問合せ配列に対して、対象配列の中に最も相同するスコアを示す対象部分配列が一つしか存在しないか否かを調べるものである。このため、対象配列の部分配列群の中で、最も相同性が高いスコア（上位のスコア）が複数検索された時点で、特異性はないことが明確となる。したがって、このように、対象配列において複数の対象部分配列について最も相同性が高いスコアが得られた際には、その要素（問合せ配列）をハッシュテーブルから除外することが好ましい。これによって、例えば、メモリーの逼迫を回避し、オーバーフロー領域の探索時間の短縮を図ることができる。図７のスコアリング体系を例にすると、例えば、類似度（Ｕ７）が０．０となる同率一位の要素が複数出現した場合が該当する。このような結果を示す要素を、検索途中に除外すれば、例えば、問合せ配列の数が膨大な場合、特に性能の向上に有効に寄与できる。
【産業上の利用可能性】
【０１２８】
以上のように、本発明によれば、例えば、ホモポリマー領域における同一塩基連続数が、塩基配列の決定法や配列自身の多型のために、誤差や変位を含む場合であっても、その影響を回避して、より正確な相同性検索が可能となる。さらに、このように精度良く相同性検索が行えることから、例えば、問合せ配列と対象配列における部分配列とが、唯一の相同性（類似性）を示すものであるか否かの判断も精度良く行うことが可能になる。また、第一に、ホモポリマー領域の同一塩基連続数を考慮しない圧縮配列同士を対比し、一致した対象配列の部分配列を選択することため、従来と比較して、データ処理能力が格段に向上し、低コスト化の実現も可能である。したがって、本発明は、相同性検索（類似性検索）の分野において、これまで回避できなかったホモポリマー領域における同一塩基連続数の変動による影響を解決できることから、特に遺伝子解析の分野において極めて有用な技術であるといえる。
【図１】
2008108297.tif 000003
【図２】
2008108297.tif 000004
【図３】
2008108297.tif 000005
【図４】
2008108297.tif 000006
【図５】
2008108297.tif 000007
【図６】
2008108297.tif 000008
【図７】
2008108297.tif 000009
【図８】
2008108297.tif 000010
【図９】
2008108297.tif 000011
【図１０】
2008108297.tif 000012
【図１１】
2008108297.tif 000013
【国際調査報告】
2008108297.tif 000014
2008108297.tif 000015
2008108297.tif 000016
2008108297.tif 000017