(57)【要約】   【課題】  配列の類似部分を探索するときの時間計算量および空間計算量を改善する。  【解決手段】  配列探索システムは、配列を構成する部分列中、第１の配列中の各要素から延びる部分列の出現位置を格納する第１のテーブルと、第２の配列中の各要素から延びる部分列に対応する、第１のテーブル中の、第１の配列の部分列に関する出現位置を取得する出現位置取得手段と、第２の配列の部分列および第１の配列の部分列に関する出現位置に基づく構造体を、それぞれの出現位置の間の差異にしたがってヒープに投入し、形成されたヒープの根に、差異が同一の構造体が所定回数表れるときに、構造体を取り出して、その情報を記憶装置に記憶するヒープ形成手段と、取り出された、差異が同一の構造体の第１の配列の部分列および第２の配列の部分列に関する出現位置から、所定の長さ以上、第１の配列および第２の配列とが一致する位置を特定する類似位置特定手段とを備える。【選択図】  図１
2005190248.tif 000002
【特許請求の範囲】
【請求項１】
第１の配列から、第２の配列と類似する位置を探索する配列探索システムであって、
配列を構成する所定の長さの部分列中、第１の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第１のテーブルと、
第２の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第１のテーブル中の、前記第１の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第２の配列の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく構造体を、前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異にしたがってヒープに投入することにより、ヒープを形成するヒープ形成手段であって、前記形成されたヒープの根に、前記差異が同一の構造体が所定回数表れるときに、当該構造体を取り出して、その情報を記憶装置に記憶するヒープ形成手段と、
前記取り出された、差異が同一の構造体の第１の配列の部分列に関する出現位置と、前記第２の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第１の配列および第２の配列とが一致する位置を特定する類似位置特定手段とを備えたことを特徴とする配列探索システム。
【請求項２】
前記第２の配列の部分列qkの第２の配列中の出現位置をquery(qk)、第１の配列中の部分列qkの出現位置をdb(qk)とするときに、
前記ヒープ形成手段が、構造体として、(query(qk),db(qk))を生成することを特徴とする請求項１に記載の配列探索システム。
【請求項３】
前記第２の配列の部分列qkの第２の配列中の出現位置をquery(qk)、第１の配列中の部分列qkの出現位置をdb(qk)とするときに、ヒープ形成手段が、構造体として、(query(qk)-db(qk))または(db(qk)-query(qk)と、前記部分列qkの第２の配列における出現位置を表わすIDとの組を生成することを特徴とする請求項１に記載の配列探索システム。
【請求項４】
前記ヒープ形成手段が、第２の配列の部分列と、第２の配列の他の部分列との間の距離が所定の値を超えた場合には、前記他の部分列を、前記ヒープ形成処理の処理対象から除外することを特徴とする請求項１ないし３の何れか一項に記載の配列探索システム。
【請求項５】
第１の配列から、第２の配列と類似する位置を探索する配列探索システムであって、
配列を構成する所定の長さの部分列中、第１の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第１のテーブルと、
第２の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第１のテーブル中の、前記第１の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第２の配列の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく第１の構造体を形成するとともに、前記第２の配列の他の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく第２の構造体を形成し、前記第１の構造体における、前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異と、前記第２の構造体における前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異とが一致するときに、前記第１の構造体および第２の構造体を取り出して、それらの情報を記憶する比較手段と、
前記取り出された、差異が同一の構造体の第１の配列の部分列に関する出現位置と、前記第２の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第１の配列および第２の配列とが一致する位置を特定する類似位置特定手段とを備えたことを特徴とする配列探索システム。
【請求項６】
前記第２の配列の部分列をqi、他の部分列をqjとしたときに、前記比較手段が、qi=(q1,q2,…,qQ-1)およびqj=(q2,…,qQ)として、qiに関する第１の構造体と、qjに関する第２の構造体との間で比較を実行することを特徴とする請求項５に記載の配列探索システム。
【請求項７】
前記第２の配列の部分列をqi、他の部分列をqjとしたときに、前記比較手段が、qi=(q1,q2,…,qQ-1)およびq2=(qi+1,…max(qi+k,qQ)として、qiに関する第１の構造体と、q2に関する第２の構造体との間で比較を実行することを特徴とする請求項５に記載の配列探索システム。
【請求項８】
第１の配列から、第２の配列と類似する位置を探索するために、配列を構成する所定の長さの部分列中、第１の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第１のテーブルを備えたコンピュータを、
前記第１のテーブルに基づいて、第２の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第１のテーブル中の、前記第１の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第２の配列の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく構造体を、前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異にしたがってヒープに投入することにより、ヒープを形成するヒープ形成手段であって、前記形成されたヒープの根に、前記差異が同一の構造体が所定回数表れるときに、当該構造体を取り出して、その情報を記憶装置に記憶するヒープ形成手段と、
前記取り出された、差異が同一の構造体の第１の配列の部分列に関する出現位置と、前記第２の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第１の配列および第２の配列とが一致する位置を特定する類似位置特定手段として機能させることを特徴とするコンピュータにより読み取り可能な配列探索プログラム。
【請求項９】
第１の配列から、第２の配列と類似する位置を探索するために、配列を構成する所定の長さの部分列中、第１の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第１のテーブルを備えたコンピュータを、
第２の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第１のテーブル中の、前記第１の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第２の配列の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく第１の構造体を形成するとともに、前記第２の配列の他の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく第２の構造体を形成し、前記第１の構造体における、前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異と、前記第２の構造体における前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異とが一致するときに、前記第１の構造体および第２の構造体を取り出して、それらの情報を記憶する比較手段と、
前記取り出された、差異が同一の構造体の第１の配列の部分列に関する出現位置と、前記第２の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第１の配列および第２の配列とが一致する位置を特定する類似位置特定手段として機能させることを特徴とするコンピュータにより読み取り可能な配列探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の配列中、類似する配列の位置を探索する方法およびプログラムに関する。
【背景技術】
【０００２】
配列の探索方法においては、長い文字列からなるデータベース中から、クエリー配列に類似の文字列がある領域（類似領域）を探すこと、特にゲノム配列のような少ない種類の文字で構成される大きなデータベースに対して、クエリー配列と一致もしくは類似の文字列が存在する領域を探索する。このような手法は、クエリー配列の類似領域を高速に推定する方法は近年爆発的に増加している生物学的情報の処理方法として重要である。
【０００３】
たとえば、ゲノム配列中から遺伝子の領域を推定する方法において、もしくは大規模な文章中から文字の置換、挿入、損を許して検索する必要のあるような検索方法において重要である。
【特許文献１】ＷＯ０３／０５６４５８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
たとえば、配列からクエリー配列に類似する領域を探索するアルゴリズム（以下、「配列写像アルゴリズム」とも称する。）として、動的プログラミング手法と比較して高速であるため、FastaやBlastのようなheuristicアルゴリズムが用いられている。また、２５０万個のヒトＥＳＴ（長さ数百から１万程度）を約３０億個の塩基からなるゲノム配列に写像する場合に、ヒトＥＳＴをエクソンに分割しながらゲノム配列に写像する際に、長いギャップを少数だけ挿入するようなアルゴリズムにより、高速にＥＳＴ配列をアラインメントできる手法が特許文献１に開示されている。
【０００５】
しかしながら、これらアルゴリズムは、多くの処理時間を必要とする。また、二つの配列感の類似性を解くことのみのために設計されているため、ＥＳＴを、既知のコード化すべきゲノムに射影することができない。以下、二つの配列中の類似する部分を探索するための技術の例について説明する。
【０００６】
［ハッシュテーブルを利用した類似位置推定方法］
クエリー配列をデータベース配列上に高速にアライメントするために、データベース配列に対して、ゲノム配列中に現れる短い配列（以降索引単語とする）をキーとするハッシュテーブルを構成して、それを用いてその所在を高速に探し出す方法がある。ここで索引単語とは、例えばデータベース配列上の全ての12merの配列でもよいし、不連続な配列であってもよい。また、例えば空白文字で囲まれた単語であってもかまわない。
【０００７】
「シングルヒット法による類似位置推定方法」
索引単語をキーとする索引が作成された上記ハッシュテーブルもしくはルックアップテーブルを用いて、クエリー配列中にある単語がハッシュテーブル中の索引単語にあるかどうか、そしてその索引単語はデータベース中どの位置にあったのかを調べることによって、クエリー配列の類似位置を推定する方法が提案されている。ここでいうシングルヒット法とは、ハッシュテーブルもしくはルックアップテーブルに対してひとつの単語について調べ、そのデータベース中での該当位置を取得し、その該当位置周辺を類似領域の候補とする手法をいう。
【０００８】
また、Ｎ−ｈｉｔ法は、シングルヒット法と同様に、索引単語を用いて索引が作成された上記ハッシュテーブルもしくはルックアップテーブルを用いて、クエリー配列中の各々の単語がデータベース中のどの位置にあるのか調べることによって、クエリー配列の類似位置を推定する方法である。Ｎ−ｈｉｔ法においては、クエリー配列のＮ箇所の単語がその位置関係を保存したまま、データベース配列中に現れることを条件にして、その該当位置周辺を類似領域の候補とする。ここで、Ｎ＝１の時に、Ｎ−ｈｉｔ法はシングルヒット法と同じになる。
【０００９】
従来のＮ−ｈｉｔ法は、以下の手法で類似領域の候補を見出している。まず、データベース配列に対して作成されたルックアップテーブルの表を、クエリー配列の各単語に対して索引する。次いで、ルックアップテーブルから取り出されたデータベース配列中の位置から該当する単語が、クエリー配列上にあった位置を引いた値（対角位置とする）を全ての該当箇所に対して求める。それらの値全体を例えばマージソートすることによって、対角位置を昇順に並べ、同じ対角位置を与える単語を探すことによって、Ｎ−ｈｉｔを見つけることができる。この手法を用いると、クエリー配列の単語に対するデータベース上の位置の候補数の合計をＮとすると、時間計算量でＯ(ＮｌｏｇＮ)、空間計算量でＯ(Ｎ)必要である。
【００１０】
本発明は、時間計算量および空間計算量が改善された、高速な配列の探索システムおよびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の目的は、第１の配列から、第２の配列と類似する位置を探索する配列探索システムであって、
配列を構成する所定の長さの部分列中、第１の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第１のテーブルと、
第２の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第１のテーブル中の、前記第１の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第２の配列の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく構造体を、前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異にしたがってヒープに投入することにより、ヒープを形成するヒープ形成手段であって、前記形成されたヒープの根に、前記差異が同一の構造体が所定回数表れるときに、当該構造体を取り出して、その情報を記憶装置に記憶するヒープ形成手段と、
前記取り出された、差異が同一の構造体の第１の配列の部分列に関する出現位置と、前記第２の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第１の配列および第２の配列とが一致する位置を特定する類似位置特定手段とを備えたことを特徴とする配列探索システムにより達成される。
【００１２】
本発明において、出現位置取得手段は、第１のテーブル中の要素に対して配置されたポインタが指し示す値を取得し、その後、ポインタを移動させるように構成しても良い。或いは、出現位置を示す第２のテーブルを生成し、当該第２のテーブルを参照しても良い。
【００１３】
たとえば、前記第２の部分列qkの第２の配列中の出現位置をquery(qk)、第１の配列中の部分列qkの出現位置をdb(qk)とするときに、前記ヒープ形成手段が、構造体として、(query(qk),db(qk))を生成するのが望ましい。
【００１４】
或いは、第２の配列の部分列qkの第２の配列中の出現位置をquery(qk)、第１の配列中の部分列qkの出現位置をdb(qk)とするときに、ヒープ形成手段が、構造体として、(query(qk)-db(qk))または(db(qk)-query(qk)と、前記部分列qkの第２の配列における出現位置を表わすIDとの組を生成しても良い。
【００１５】
好ましい実施態様においては、前記ヒープ形成手段が、第２の配列の部分列と、第２の配列の他の部分列との間の距離が所定の値を超えた場合には、前記他の部分列を、前記ヒープ形成処理の処理対象から除外する。これにより、処理時間をより短縮することが可能となる。
【００１６】
また、本発明の別の実施態様において、第１の配列から、第２の配列と類似する位置を探索する配列探索システムであって、
配列を構成する所定の長さの部分列中、第１の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第１のテーブルと、
第２の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第１のテーブル中の、前記第１の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第２の配列の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく第１の構造体を形成するとともに、前記第２の配列の他の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく第２の構造体を形成し、前記第１の構造体における、前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異と、前記第２の構造体における前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異とが一致するときに、前記第１の構造体および第２の構造体を取り出して、それらの情報を記憶する比較手段と、
前記取り出された、差異が同一の構造体の第１の配列の部分列に関する出現位置と、前記第２の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第１の配列および第２の配列とが一致する位置を特定する類似位置特定手段とを備えている。
【００１７】
たとえば、前記第２の配列の部分列をqi、他の部分列をqjとしたときに、前記比較手段が、qi=(q1,q2,…,qQ-1)およびqj=(q2,…,qQ)として、qiに関する第１の構造体と、qjに関する第２の構造体との間で比較を実行する。
【００１８】
別の好ましい実施態様においては、前記第２の配列の部分列をqi、他の部分列をqjとしたときに、前記比較手段が、qi=(q1,q2,…,qQ-1)およびq2=(qi+1,…max(qi+k,qQ)として、qiに関する第１の構造体と、q2に関する第２の構造体との間で比較を実行する。
【００１９】
また、本発明の目的は第１の配列から、第２の配列と類似する位置を探索するために、配列を構成する所定の長さの部分列中、第１の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第１のテーブルを備えたコンピュータを、
前記第１のテーブルに基づいて、第２の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第１のテーブル中の、前記第１の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第２の配列の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく構造体を、前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異にしたがってヒープに投入することにより、ヒープを形成するヒープ形成手段であって、前記形成されたヒープの根に、前記差異が同一の構造体が所定回数表れるときに、当該構造体を取り出して、その情報を記憶装置に記憶するヒープ形成手段と、
前記取り出された、差異が同一の構造体の第１の配列の部分列に関する出現位置と、前記第２の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第１の配列および第２の配列とが一致する位置を特定する類似位置特定手段として機能させることを特徴とするコンピュータにより読み取り可能な配列探索プログラムによっても達成される。
【００２０】
さらに、本発明の目的は、第１の配列から、第２の配列と類似する位置を探索するために、配列を構成する所定の長さの部分列中、第１の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第１のテーブルを備えたコンピュータを、
第２の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第１のテーブル中の、前記第１の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第２の配列の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく第１の構造体を形成するとともに、前記第２の配列の他の部分列に関する出現位置および第１の配列の部分列に関する出現位置に基づく第２の構造体を形成し、前記第１の構造体における、前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異と、前記第２の構造体における前記第２の配列の部分列に関する出現位置と、第１の配列の部分列に関する出現位置との間の差異とが一致するときに、前記第１の構造体および第２の構造体を取り出して、それらの情報を記憶する比較手段と、
前記取り出された、差異が同一の構造体の第１の配列の部分列に関する出現位置と、前記第２の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第１の配列および第２の配列とが一致する位置を特定する類似位置特定手段として機能させることを特徴とするコンピュータにより読み取り可能な配列探索プログラムによっても達成される。
【発明を実施するための最良の形態】
【００２１】
以下、添付図面を参照して、本発明の実施の形態について説明する。図１は、本発明の実施の形態にかかる配列探索システムの概略を示すブロックダイヤグラムである。本実施の形態において、配列探索システムは、ゲノム配列中、ＥＳＴ配列に類似する位置を推定する。図１に示すように、配列探索システム１０は、ゲノム配列に基づく第１のルックアップテーブル（ＬＵＴ）を生成するゲノム配列ＬＵＴ生成部１２と、ＥＳＴ配列に関する第２のＬＵＴを生成するＥＳＴ配列ＬＵＴ生成部１４と、ヒープを構築するヒープ形成処理部１６と、後述する値の対（位置の対）に基づいて類似する配列の位置を抽出するＮｈｉｔ抽出部１８と、ＬＵＴや処理結果を記憶する記憶装置２０とを有している。記憶装置２０は、ＲＡＭなどのメモリやハードディスク装置などの外部記憶装置を含む。配列探索システムは、コンピュータにより実現でき、配列探索プログラムをコンピュータにインストールし、これを起動することにより、コンピュータが、ゲノム配列ＬＵＴ生成部、ＥＳＴ配列生成部、ヒープ形成処理部およびＮｈｉｔ抽出部として機能する。
【００２２】
なお、本実施の形態においては説明を容易にするために、ＥＳＴ配列ＬＵＴ生成部１４を設け、ＥＳＴ配列ＬＵＴ生成部１４が第２のＬＵＴを生成しているが、これは必須のものではなく、後述するように、第１のＬＵＴのみを生成し、第１のＬＵＴの要素に対するポインタを配置することで、第２のＬＵＴの要素に相当する値を適切に取得することはできる。
【００２３】
本発明の第１の実施の形態においては、クエリー配列（本実施の形態ではＥＳＴ配列）の長さをＱとすると、時間計算量Ｏ(ＮｌｏｇＱ)、空間計算量Ｏ(Ｑ)となる。また、後述する第２の実施の形態においては、時間計算量Ｏ(Ｎ^２)、空間計算量Ｏ(１)となる。第１の実施の形態および第２の実施の形態とも、Ｎ−ｈｉｔの条件（クエリー配列のＮ個の単語とデータベース配列のＮ個の単語が位置関係を保存して発見される条件）を満たす対角位置を抽出することを目的としている。
【００２４】
以下、第１の実施の形態にかかる配列探索システム１０にて実行される処理について説明する。ゲノム配列ＬＵＴ生成部１２は、記憶装置に記憶されたゲノム配列のデータを読み出し、第１のＬＵＴを生成する。第１のＬＵＴは、所定の長さのＮ−ｍｅｒ配列のそれぞれが、ゲノム配列中のどの位置に出現するかを示す。つまり、各Ｎ−ｍｅｒ配列の出現位置が格納される。図２（ａ）はゲノム配列の例を示す図、図３は、図２（ａ）に示すゲノム配列に基づいて、２−ｍｅｒ配列の出現位置が格納された第１のＬＵＴの例を示す。
【００２５】
次いで、ＥＳＴ配列ＬＵＴ生成部１４は、第１のＬＵＴを参照して、ＥＳＴ配列を構成するＮ−ｍｅｒ配列のそれぞれに、当該Ｎ−ｍｅｒ配列が出現するゲノム配列中の位置を格納したような第２のＬＵＴを生成する。ここで、ＥＳＴ配列を構成するＮ−ｍｅｒ配列は、ＥＳＴの各要素を先頭としてＮ個の要素からなる。したがって、第２のＬＵＴにおいては、（Ｎ−Ｑ＋１）個の配列のそれぞれについて、当該配列について格納されていた第１のＬＵＴの値が収容される。図４は、図２（ｂ）に示すＥＳＴ配列を構成する２−ｍｅｒ配列のそれぞれが、図２（ａ）のゲノム配列中に出現する位置を示したＬＵＴの例を示す。図４において、先頭の行（符号４０１参照）には、ＥＳＴ配列中の先頭の２−ｍｅｒ配列「ＧＣ」が、ゲノム配列において出現する位置「８、２３、２５，２９」が示される。次の行（符号４０２参照）には、ＥＳＴ配列中の次の２−ｍｅｒ配列「ＣＡ」が、ゲノム配列において出現する位置「２６」が示される。なお、処理の便宜のため、それぞれの値の組の末尾には、別の値「φ」が格納される。
【００２６】
ルックアップテーブル（ＬＵＴ）には、キーとなる配列が出現する位置を保存している。第１の実施の形態にかかる手法では、ＬＵＴ中の配列の出現位置が位置によってソートされていることが望ましい。これは、第１の実施の形態においては、各配列について出現位置順にＬＵＴから取り出すためである。このようなＬＵＴは、ゲノム配列ＬＵＴ生成部１２やＥＳＴ配列ＬＵＴ生成部１４が、記憶装置に記憶されたデータに基づいてＬＵＴを生成する際に、出現位置の小さなものから順に作成してゆくことで実現できる。
【００２７】
以下の説明において、ＬＵＴのキーとなる２−ｍｅｒの配列を、複数の文字からなる単語と考えることもできるため、「単語」とも称する。ＥＳＴ配列（以下、機能面から「クエリー配列」とも称する。）において、類似位置推定に使用する単語をq1,q2,q3,....,qQとする。また、単語qkが出現するデータベース上の位置は、長さn1のリストdb(qk)で与えられるものとする。また、単語qkが出現するクエリー配列上の位置はquery(qk)で与えられるものとする。リストdb(qk)の各要素db(qk)1,db(qk)2,...,db(qk)n1は出現位置順にソートされている。
【００２８】
次に、ヒープ形成処理部１６における処理について、図５のフローチャートを参照して説明する。ヒープには、q1,..,qQの各単語の最初の出現位置とクエリー配列での出現位置との対角位置〔db(qk)1
- query(qk)〕、および、単語qkのクエリー配列上の位置を特定するためのID〔k、qk、或いは、query(qk)〕が対となった構造体が格納される（ステップ５０１）。或いは、ヒープには、単語qkのデータベース上の出現位置db(qk)およびクエリー配列上の出現位置query(qk)が対となった構造体が格納されてもよい（ステップ５０１）。後述する具体例では、後者にしたがって形成された構造体が利用される。
【００２９】
ここで、これらの構造体は、対角位置とクエリー単語の出現位置の大小関係によって構築され（つまり、対角位置の大小関係を優先し、対角位置が等しい場合は、クエリー単語の出現位置の大小関係を用いる。）、現在ヒープ中にある最小の対角位置を与える構造体から順に取り出すことができる。
【００３０】
次いで、ヒープ形成処理部１６は、ヒープ中の最小の対角位置を与える構造体を取得し
ステップ５０２）、その構造体からクエリー配列上の位置を特定するためのID(k)を取り出し（ステップ５０３）、そのIDが示すリストdb(qk)から次の要素を新しく取得して、構造体を作成し、ヒープに入れる（ステップ５０４）。リストdb(qk)から取得する要素がなくなったら、ヒープ形成処理部１６は、ヒープには何もいれない。ヒープ形成処理部１６は、取得した構造体を、直前までに取得した構造体と比較して（ステップ５０５）、連続してN回以上の等しい、若しくは、幅ｋ以下の距離にある対角位置を与える場合、対角位置とクエリー配列上の位置関係を出力する（ステップ５０６）。
【００３１】
ヒープ形成処理部１６は、ヒープに構造体がなくなるまで、ステップ５０２〜５０７を繰り返す（ステップ５０７参照）。このようにすると、N-hitの条件を満たす対角位置を抽出することができる。
【００３２】
このように、第１の実施の形態では、ヒープを利用して、ヒープのルートに（ｙ−ｘ）が最小となるような値の組が位置するようにしておく。そして、このルートの構造体を順に取り出すことで、（ｙ−ｘ）の値が昇順となるような構造体群を取得することができる。ヒープから、（ｙ−ｘ）の値が等しいような構造体がN回取り出すことができれば、それがN-hitとなる。
【００３３】
図２〜図４に示したゲノム配列およびＥＳＴ配列に関して、ヒープ形成処理部１６の処理をより具体的に説明する。図６に示すように、まず、先頭の単語「q1＝ＧＣ」のクエリー配列（つまりＥＳＴ配列）上の出現位置「query(q1)＝１」と、当該単語のデータベース上（つまりゲノム配列上）の出現位置「db(q1)＝８」との対（１、８）がヒープに入れられる。なお、この対の構造体（ｘ，ｙ）に関して、ヒープは「ｙ−ｘ」の大小関係で構成される。
【００３４】
次いで、図７に示すように、次の単語「q2＝ＡＧ」のクエリー配列上の出現位置「query(q2)＝２」と、当該単語のデータベース上の出現位置「db(q2)＝２６」との対の構造体（２，２６）がヒープに入れられる。ここでは上記「ｙ−ｘ」の大小関係が考慮される。このように、図８〜図１０に示すように、クエリー配列の出現位置（を示す値）が進むように、それぞれの単語q3〜q5の、クエリー配列上の出現位置（「３」〜「５」）およびデータベース上の出現位置（それぞれ、「７」、「６」、「２」）の対の構造体がヒープに入れられる。
【００３５】
全ての単語qk（その出現位置「query(qk)」）について、対の構造体をヒープに入れた状態を図１１に示す。この状態において、ヒープ中の最小の構造体（つまりヒープにおいてルートに位置する構造体（１１，２）が取り出され、記憶装置２０中に記憶される。図１２は、ヒープにおいて構造体（１１，２）が取り出された状態を示す。
【００３６】
構造体が取り出されると、当該取り出された構造体に対応する単語の、次のデータベース上の出現位置「db(qk)＝１４」が取得されて、対の構造体（１１，１４）がヒープに入れられる（図１３参照）。
【００３７】
これにより、「ｙ−ｘ」が最小となる対の構造体（８，４）がヒープから取り出され、記憶装置２０中に記憶される。図１４は、ヒープにおいて構造体（８，４）が取り出された状態を示す図である。次いで、当該取り出された構造体に対応する単語の、次のデータベース上の出現位置「db(qk)＝２４」が取得されて、対の構造体（８，２４）がヒープに入れられる（図１５参照）。
【００３８】
ここでも、「ｙ−ｘ」が最小となる対の構造体（９，５）がヒープから取り出され、記憶装置２０中に記憶される。図１６は、ヒープにおいて構造体（９，５）が取り出された状態を示す図である。なお、取り出された構造体に対応する単語の次のデータベース上の出現位置は「φ」であるため、「query(qk)＝９」に関する処理は終了する。そこで、次の単語（つまり、「query(qk)＝１０」）について、構造体（１０，６）が取り出されて記憶装置に記憶され（図１７参照）、さらに、次の構造体（１０，１７）を形成してヒープに入れられる（図１８参照）。
【００３９】
このような構造体のヒープへの投入、所定の条件の下でのヒープの取り出し／記憶を繰り返すことにより、取り出された順で、図１９（ａ）に示すような構造体の列を作ることができる。これら構造体の「ｙ−ｘ」は、図１９（ｂ）に示すように、ソートされている。したがって、Ｎ−ｈｉｔ算出部１８は、連続で同じ値が並んでいるものとＮ−ｈｉｔとして取り出す。取り出された構造体の情報（位置情報など）は、記憶装置２０に記憶される。図２０（ａ）は、取り出された構造体の値「ｙ−ｘ」を示し、図２０（ｂ）は、図２０（ａ）の値に対応する構造体を示す。
【００４０】
図２１は、Ｎ−ｈｉｔ算出部１８により取り出された構造体に基づいて、ゲノム配列において、ＥＳＴ配列と類似する部分が見出された状態を示す図である。たとえば、図２０（ｂ）に示す「ｙ−ｘ＝−４」の構造体の組（８，４）、（９，５）および（１０，６）から、クエリー配列（つまりＥＳＴ配列）の「８」の位置から「１０」の位置までの要素（この例では２−ｍｅｒ配列）と、データベース上の配列（つまりゲノム配列）の「４」の位置から６の位置までの要素とが一致することが理解できる（符号２１０１、２１０２参照）。なお、図２等で示した例において、ゲノム配列の位置は先頭で「０」をとり、ＥＳＴ配列の位置は先頭で「１」をとっている。
【００４１】
また、図２０（ｂ）に示す「ｙ−ｘ＝７」の構造体の組（１，８）、（６，１３）、（１０，１７）および（１１，１８）から、クエリー配列の「１」の位置、「６」の位置、「１０」の位置および「１１」の位置の要素と、データベース上の配列の「８」の位置、「１３」の位置、「１７」の位置および「１８」の位置の要素とが一致することが理解できる（符号２１０３、２１０４参照）。他の部分についても同様に、それぞれの配列において類似する要素をもつ位置を特定することが可能である。
【００４２】
次に、本発明の第２の実施の形態について説明する。図１ではヒープを形成しているが、第２の実施の形態ではヒープを形成せず、対角位置を逐一比較している。第２の実施の形態にかかる配列探索システムでは、図１のヒープ形成処理部の代わりに、比較処理部が配置される。
【００４３】
比較処理部では、以下の処理が実行される。図２２は本実施の形態にかかる比較処理部で実行される処理を示すフローチャートである。
【００４４】
比較処理部は、単語qi = (q1,...,qQ-1)の各々、および、単語qj = (q2,...,qQ)の各々について、qiとqjの与える対角位置を比較して、等しい対角位置を与える組を得る（ステップ２２０１）。
db(qi)1 - query(qi),db(qi)2 - query(qi), ... , db(qi)x - query(qi)
db(qj)1 - query(qj),db(qj)2 - query(qj), ... , db(qj)y - query(qj)
つまり、上記のようなリストを、db(q1)1-query(q1)およびdb(q2)1-query(q2)の組から順に比較し、小さいほうを大きいほうより大きくなるまで進めることを繰り返し、その過程で等しい対角位置を与える組を得る。
【００４５】
等しい対角位置を与える組を発見した場合、比較処理部は、その組を記憶装置に記憶するとともに、単語qi側で、その対角位置を与えるデータベース上の位置を重複して発見しないために、リストから除外する（ステップ２２０２）。或いは、ステップ２２０１を繰り返す際に、等しい対角位置を与える組を無視する。
【００４６】
リストから除外されたものを除く全ての組について処理が終了すると（ステップ２２０３でイエス(Yes)）、比較処理部は、記憶装置に記憶された等しい対角位置を与える組を取得した後、対角位置とクエリー配列での出現位置の大小関係でソートし（ステップ２２０４）、連続してN回以上の、若しくは幅ｋ以下の距離にある対角位置を与える場合、対角位置とクエリー配列上の位置関係を出力する（ステップ２２０５）。このような処理によっても、N-hitの条件を満たす対角位置を抽出することができる。
【００４７】
図２〜図４に示したゲノム配列およびＥＳＴ配列に関して、比較処理部の処理をより具体的に説明する。まず、図２３に示すように、db(q1)1-query(q1)と、db(q2)1-query(q2)とを比較する。上記例では、先頭の単語の「８−１」と次の単語の「２６−２」とが比較される。ここでは、「２６−２＞８−１」のため、単語q1のデータベース上の出現位置が進められ、db(q1)2-query(q1)と、db(q2)1-query(q2)とが比較される（図２４参照）。ここでも、「２６−２＞２３−１」であるため、さらに単語q1のデータベース上の出現位置が進められ、db(q1)3-query(q1)と、db(q2)1-query(q2)とが比較される（図２５参照）。ここで、「２６−２＝２５−１」となるため、(query(qk),db(qk)の組（２，２６）および（１，２５）が、それぞれ記憶装置２０に記憶される。引き続く比較において、（query(q2),db(q2)2）＝（２，φ）であるため、この組の処理は終了する。
【００４８】
単語q2に関する処理は終了したため、次に、単語q1および単語q3に関して処理が進められる。ここでは、db(q1)1-query(q1)と、db(q3)1-query(q3)とが比較される（図２６参照）。「７−３＜８−１」であるため、db(q3)が進められて、db(q1)1-query(q1)と、db(q3)2-query(q3)とが比較される（図２７参照）。ここでは、「１６−３＞８−１」であるため、db(q1)が進められる。このような処理を必要な(qi,qj)の組について繰り返し、db(qi)-query(qi)とdb(qj)-query(qj)との差が同一となるような、（query(qi),db(qi)）よび（query(qj),db(qj)）の組を記憶装置に記憶しておく。
【００４９】
その後、比較処理部は、抽出した値の組を、db(qk)-query(qk)の値でソートする（ステップ２２０６）。この値が同じ場合には、query(qk)の値に従う。つまり、昇順のソートであれば、query(qk)の値が小さいほうが、先頭に近い位置に配置される。これにより、図１９（ａ）と同様の結果を得ることができる。
【００５０】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【００５１】
たとえば、前記実施の形態においては、ゲノム配列生成部１２が、第１のＬＵＴを生成し、ＥＳＴ配列ＬＵＴ生成部１４が、第２のＬＵＴを生成しているが、このような構成をとらずとも本発明を実現することができる。他の例においては、ゲノム配列生成部１２は、第１のＬＵＴを生成する。その一方、第２のＬＵＴは生成されず、したがって、ＥＳＴ配列ＬＵＴ生成部１４は存在しない。その代わりに、第１のＬＵＴへのポインタを生成してポインタを制御し、db(qk)の値を第１のＬＵＴから取り出すことができるようにするポインタ制御部が設けられれば良い。この構成では、ポインタは、第１のＬＵＴにおいて、クエリー配列の部分列qkと同じ値の部分列に設けられていれば良い。たとえば、上述した例では、第１のＬＵＴにおいて、「ＧＣ」、「ＣＡ」、「ＡＧ」、「ＧＡ」、「ＡＴ」、「ＴＡ」、「ＡＣ」、「ＣＧ」および「ＧＧ」についてポインタを配置しておけばよい。初期的には、ポインタは、第１のＬＵＴにおける先頭の値に位置する。
【００５２】
たとえば、第１の実施の形態にかかる処理において、ヒープ形成部１６が、ＤＢ２０中に記憶されたクエリー配列の所定の部分列qkを参照し、第１のＬＵＴ中、部分列qkに一致する値に関するポインタを参照して、db(qk)を特定することができる。これにより、（query(qk),db(qk)）を得ることができる。値を得た後、ポインタ制御部が、参照されたポインタを一つ進めればよい。
【００５３】
また、第１の実施の形態のステップのステップ５０２以降において、抽出して連続してN回近い対角位置を与える場合を調べる際に、クエリー配列上での単語の距離が指定の距離よりも遠い場合を除外することで、おこる確率が極めて低い2hitを検出しないことが可能である。
【００５４】
また、第２の実施の形態において、qi=(q1,...,qQ-1),qj=(q2,...,qQ)としてqiおよびqjに関する逐一比較を実行したが、おこる確率が極めて低い2hitを検出しないために、qi=(q1,...,qQ-1),q2=(qi+1,...,max(qi+k,qQ))として、qiおよびq2に関する逐一比較を実行しても良い。
【００５５】
さらに、上記実施の形態によれば、N-hitによってアライメント候補地点を推定することができるが、クエリー配列とデータベース配列のすべてのN-hitを出力すると、N-hitが存在しない領域がクエリー配列中に存在することがわかる。これらは、クエリー配列とデータベース配列には、相同領域がないことを示している。クエリー配列中にそのようなN-hitが存在しない領域が一定以上存在する場合に、相同領域がないものとして詳細なアライメントをする必要はなく、アライメントプログラムにおいて、このような条件分岐によって、アライメントの枝かりを行うことで効率化を図ることが可能である。
【００５６】
また、前記実施の形態において、理解を容易にするために、部分列として２−ｍｅｒ配列を利用したが、これに限定されず、Ｎ−ｍｅｒ（たとえば８−ｍｅｒ）配列を利用しても良いことは言うまでもない。
【００５７】
また、本発明によれば、時間計算量の改善（処理の高速化）、空間計算量の改善（必要なメモリ量の削減）に加え、以下のような利点がある。
【００５８】
文字（遺伝子）の置換、挿入、損を許して検索することにより、文字の読み取りミス（ゲノムの読み取りミス）が生じた場合でも適用することができる。また、異種の動物のゲノム間でも高速かつ正確な候補を挙げることが可能となる。さらに、たんぱく質から推定される核酸配列をゲノムにアライメントすることに適用可能である。
【００５９】
さらには、一般の文書、たとえば、特許明細書などで、検索したい言葉が等距離で出てくるものを一緒にして抽出することなどに適用することも可能である。
【図面の簡単な説明】
【００６０】
【図１】図１は、本発明の実施の形態にかかる配列探索システムの概略を示すブロックダイヤグラムである。
【図２】図２（ａ）は、本実施の形態において、ゲノム配列の例を示す図、図２（ｂ）はＥＳＴ配列の例を示す図である。
【図３】、図３は、図２（ａ）に示すゲノム配列に基づいて、２−ｍｅｒ配列の出現位置が格納された第１のＬＵＴの例を示す図である。
【図４】図４は、図２（ｂ）に示すＥＳＴ配列を構成する２−ｍｅｒ配列のそれぞれが、図２（ａ）のゲノム配列中に出現する位置を示したＬＵＴの例を示す図である。
【図５】図５は、本実施の形態にかかるヒープ形成処理部にて実行される処理を示すフローチャートである。
【図６】図６は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図７】図７は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図８】図８は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図９】図９は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１０】図１０は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１１】図１１は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１２】図１２は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１３】図１３は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１４】図１４は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１５】図１５は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１６】図１６は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１７】図１７は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１８】図１８は、ヒープ形成処理部の実行により形成されるヒープを具体的に示す図である。
【図１９】図１９（ａ）は、ヒープから取り出された構造体群を示す図、図１９（ｂ）は、各構造体に基づく値「ｙ−ｘ」を示す図である。
【図２０】図２０（ａ）は、取り出された各構造体の値「ｙ−ｘ」を示す図、図２０（ｂ）は対応する構造体群を示す図である。
【図２１】図２１は、Ｎ−ｈｉｔ算出部により取り出された構造体に基づいて、ゲノム配列において、ＥＳＴ配列と類似する部分が見出された状態を示す図である。
【図２２】図２２は、本実施の形態にかかる比較処理部で実行される処理を示すフローチャートである。
【図２３】図２３は、第２の実施の形態にかかる構造体の比較を具体的に示す図である。
【図２４】図２４は、第２の実施の形態にかかる構造体の比較を具体的に示す図である。
【図２５】図２５は、第２の実施の形態にかかる構造体の比較を具体的に示す図である。
【図２６】図２６は、第２の実施の形態にかかる構造体の比較を具体的に示す図である。
【図２７】図２７は、第２の実施の形態にかかる構造体の比較を具体的に示す図である。
【符号の説明】
【００６１】
１０    配列探索システム
１２    ゲノム配列ＬＵＴ生成部
１４    ＥＳＴ配列ＬＵＴ生成部
１６    ヒープ形成処理部
１８    Ｎ−ｈｉｔ抽出部
２０    記憶装置
【図１】
2005190248.tif 000003
【図２】
2005190248.tif 000004
【図３】
2005190248.tif 000005
【図４】
2005190248.tif 000006
【図５】
2005190248.tif 000007
【図６】
2005190248.tif 000008
【図７】
2005190248.tif 000009
【図８】
2005190248.tif 000010
【図９】
2005190248.tif 000011
【図１０】
2005190248.tif 000012
【図１１】
2005190248.tif 000013
【図１２】
2005190248.tif 000014
【図１３】
2005190248.tif 000015
【図１４】
2005190248.tif 000016
【図１５】
2005190248.tif 000017
【図１６】
2005190248.tif 000018
【図１７】
2005190248.tif 000019
【図１８】
2005190248.tif 000020
【図１９】
2005190248.tif 000021
【図２０】
2005190248.tif 000022
【図２１】
2005190248.tif 000023
【図２２】
2005190248.tif 000024
【図２３】
2005190248.tif 000025
【図２４】
2005190248.tif 000026
【図２５】
2005190248.tif 000027
【図２６】
2005190248.tif 000028
【図２７】
2005190248.tif 000029