(57)【要約】【課題】塩基配列データベースに対するクエリー配列のＨＳＰ数を適切に推定することのできるＨＳＰ数推定プログラム、ＨＳＰ数推定装置、及びＨＳＰ数推定方法の提供を目的とする。【解決手段】コンピュータに、塩基配列データベースに対するクエリー配列からＨＳＰ長の全ての部分文字列を抽出する部分文字列抽出手順と、固定長の配列の全ての種類について前記配列データベースにおける出現回数が記録された出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の推定値を算出するＨＳＰ数推定手順と、前記クエリー配列のＨＳＰ数として全ての前記推定値の総和を算出するＨＳＰ数算出手順とを実行させる。【選択図】図９
2010134694.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
塩基配列データベースに対するクエリー配列からＨＳＰ長の全ての部分文字列を抽出する部分文字列抽出手順と、
固定長の配列の全ての種類について前記配列データベースにおける出現回数が記録された出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の推定値を算出するＨＳＰ数推定手順と、
前記クエリー配列のＨＳＰ数として全ての前記推定値の総和を算出するＨＳＰ数算出手順とを実行させるためのＨＳＰ数推定プログラム。
【請求項２】
前記ＨＳＰ数推定手順は、固定長Ｎの配列に係る前記出現回数管理手段に記録された出現回数を、
【数１】
2010134694.tif 000008
に当てはめることにより、ＨＳＰ長Ｍの前記部分文字列［ｌｉｌｉ＋１・・・ｌＭ−１ｌＭ］のＨＳＰ数の推定値を算出する請求項１記載のＨＳＰ数推定プログラム。
【請求項３】
前記固定長は、前記ＨＳＰ長より短い請求項１又は２記載のＨＳＰ数推定プログラム。
【請求項４】
前記固定長は８である請求項１乃至３いずれか一項記載のＨＳＰ数推定プログラム。
【請求項５】
前記固定長が前記ＨＳＰ長以上のときに、前記出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の実測値を取得するＨＳＰ数取得手順を有し、
前記ＨＳＰ数算出手順は、前記固定長が前記ＨＳＰ長以上のときは、前記クエリー配列のＨＳＰ数として全ての前記実測値の総和を算出する請求項１又は２記載のＨＳＰ数推定プログラム。
【請求項６】
塩基配列データベースに対するクエリー配列からＨＳＰ長の全ての部分文字列を抽出する部分文字列抽出手段と、
固定長の配列の全ての種類について前記配列データベースにおける出現回数が記録された出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の推定値を算出するＨＳＰ数推定手段と、
前記クエリー配列のＨＳＰ数として全ての前記推定値の総和を算出するＨＳＰ数算出手段とを有するＨＳＰ数推定定装置。
【請求項７】
コンピュータが実行するＨＳＰ数推定方法であって、
塩基配列データベースに対するクエリー配列からＨＳＰ長の全ての部分文字列を抽出する部分文字列抽出手順と、
固定長の配列の全ての種類について前記配列データベースにおける出現回数が記録された出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の推定値を算出するＨＳＰ数推定手順と、
前記クエリー配列のＨＳＰ数として全ての前記推定値の総和を算出するＨＳＰ数算出手順とを有するＨＳＰ数推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＨＳＰ数推定プログラム、ＨＳＰ数推定装置、及びＨＳＰ数推定方法に関し、特に塩基配列データベースに対するクエリー配列のＨＳＰ数を推定するＨＳＰ数推定プログラム、ＨＳＰ数推定装置、及びＨＳＰ数推定方法に関する。
【背景技術】
【０００２】
相同性検索とは、例えば未知のＤＮＡの塩基配列（以下、単に「配列」という。）が見つかったときに、既存の配列群の中から生物学的に似ている配列（＝相同性の高い配列）を探し出す処理のことである。一般の検索に対応させると、未知の配列がクエリー（ｑｕｅｒｙ）に、既存の配列群がデータベースに相当する。
【０００３】
相同性検索では、一回の検索時において複数の配列がクエリーとして入力されることが多い。この複数の配列間には相互依存関係が無いため、配列毎に独立して検索を行うことができる。具体的には、検索サーバがＮ台有れば、クエリーを配列単位でＮ分割し、分割された各クエリーをそれぞれ別のサーバに入力することができる。この場合、分割後の各クエリーの配列長がほぼ等しければ原理的にはＮ倍の検索性能を得ることができ、１／Ｎの検索時間によって検索結果が得られることが期待される。したがって、相同性検索はクエリー分割により複数のサーバを用いて高速化されることが多い。
【０００４】
例えば、図１は、クエリーを２分割した場合の分割前後の原理的な検索時間を示す図である。同図において、分割クエリー１及び２は、分割前クエリーを配列単位で２分割したクエリーである。こここで、分割前クエリーによる検索時間がＴである場合、分割クエリー１の配列長と分割クエリー２の配列長とが等しければ、分割クエリー１及び分割クエリー２による検索時間は原理的にはそれぞれＴ／２であり、全体としてＴ／２の時間で検索処理が完了することが期待される。
【０００５】
ところで、相同性検索には、Ｓｍｉｔｈ＆Ｗａｔｅｒｍａｎ、ＦＡＳＴＡ、ＢＬＡＳＴ等、多数のアルゴリズムが存在する。それぞれ長所又は短所が有るが、最も頻繁に使用されているアルゴリズムはＢＬＡＳＴである。ＢＬＡＳＴは他のアルゴリズムに比べて検索精度は若干低いが、検索時間が一桁以上短いという特長があるからである。斯かるＢＬＡＳＴアルゴリズムに基づく相同性検索（以下、単に「ＢＬＡＳＴ」という。）でも、クエリー分割による複数サーバによる高速化は一般的である。
【特許文献１】特表２００５−５００５９４号公報
【特許文献２】特開平９−５０４３８号公報
【特許文献３】特開２００５−８４９７３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、ＢＬＡＳＴの場合、配列長が同じでも配列の内容により大きく検索時間が変わることがあり、事前に検索時間を予測することが難しい。出願人が調べた結果によると、クエリー配列の長さと検索時間との相関値は０．６〜０．７程度に止まった。一般的には、相関値が０．９を越えないと相関が高いとは言えない。こしたがって、配列長に基づいてクエリーを分割した場合に分割後のクエリーに基づくそれぞれの検索処理の間には相当の時間差が生じる可能性がある。
【０００７】
図２は、配列長の等しい二つの配列をクエリーとした場合の検索時間の例を示す図である。同図において、配列Ａと配列Ｂとは内容が異なるが配列長は等しいこととする。
【０００８】
それぞれをクエリーとして配列データベースＸに対して検索を行った場合、同図に示されるように配列ＡとＢとでは検索時間が倍以上違うことも珍しくない（検索時間の配列長非依存性）。また、配列データベースＸに対して検索を行った場合には配列Ａの方が検索時間が短くても、他の配列データベース（配列データベースＹ）に対して検索を行った場合には配列Ｂの方が検索時間が短いということも起こりうる（配列データベースによる検索時間の逆転）。このように、クエリー配列と配列データベースの組み合わせにより検索時間は大きく変動するため、ＢＬＡＳＴでは、クエリー配列の特徴から精度良く検索時間を予測することが難しい。
【０００９】
しかし、実用的な観点において適当な方法が無いため、クエリー分割を行うときには分割後のクエリーの配列長が等しくなるようにクエリーを分割することが多い。その結果として検索サーバを増やしたときに、高い並列化効果を得られないという問題が生じる。
【００１０】
例えば、図３は、配列長に基づいてクエリーを２分割した場合の分割前後のＢＬＡＳＴによる検索時間を示す図である。同図では、分割クエリー２の検索時間ｔ２はＴ／２より短い。しかし、分割クエリー１の検索時間ｔ１はＴ／２より長い。その結果、全体の検索時間として得られるのはｔ１であり、Ｔ／２より長くとなってしまう。
【００１１】
ところで、配列長ではなく、ＨＳＰ（High Scoring Pair）数を用いてクエリー分割する方法もある。ＢＬＡＳＴは、クエリー配列と配列データベース内の各配列との間で指定文字列長（ＨＳＰ長）単位で完全に一致する部分を見つけ、それをベースに検索を行う。この完全一致部分はＨＳＰと呼ばれる。また、配列データベース内におけるＨＳＰの数をＨＳＰ数という。
【００１２】
ＨＳＰ数と検索時間との相関は０．９５程度と非常に高く、ＨＳＰ数に基づいて（ＨＳＰ数が等しくなるように）クエリー分割を行うと、分割後のクエリー間の実行時間ばらつきを小さくすることができる。しかし、ＨＳＰ数を取得するにはクエリー配列から取り出せる指定文字列長単位の各文字列について配列データベース内の各配列に対する照合を行う必要がある。したがって、ＨＳＰ数の取得処理がオーバーヘッド（ときには相同性検索時間の数十％）になるという問題がある。
【００１３】
図４は、ＨＳＰ数に基づいてクエリーを２分割した場合の分割前後のＢＬＡＳＴによる処理時間を示す図である。この場合、分割クエリー１の検索時間と分割クエリー２の検索時間とはそれぞれＴ／２に近くなる。しかし、分割処理に時間がかかってしまうため、全体としての処理時間は、Ｔ／２より大きくなってしまう。
【００１４】
本発明は、上記の点に鑑みてなされたものであって、塩基配列データベースに対するクエリー配列のＨＳＰ数を適切に推定することのできるＨＳＰ数推定プログラム、ＨＳＰ数推定装置、及びＨＳＰ数推定方法の提供を目的とする。
【課題を解決するための手段】
【００１５】
そこで上記課題を解決するため、ＨＳＰ数推定プログラムは、コンピュータに、塩基配列データベースに対するクエリー配列からＨＳＰ長の全ての部分文字列を抽出する部分文字列抽出手順と、固定長の配列の全ての種類について前記配列データベースにおける出現回数が記録された出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の推定値を算出するＨＳＰ数推定手順と、前記クエリー配列のＨＳＰ数として全ての前記推定値の総和を算出するＨＳＰ数算出手順とを実行させる。
【００１６】
このようなＨＳＰ数推定プログラムでは、塩基配列データベースに対するクエリー配列のＨＳＰ数を適切に推定することができる。
【発明の効果】
【００１７】
塩基配列データベースに対するクエリー配列のＨＳＰ数を適切に推定することができる。
【発明を実施するための最良の形態】
【００１８】
以下、図面に基づいて本実施の形態を説明する。図５は、本実施の形態における相同性検索システムの構成例を示す図である。同図において、相同性検索システム１は、検索クライアント装置１０、検索サーバ装置２０ａ及び２０ｂ、並びに配列データベース装置３０等を含む。各装置は、ＬＡＮ（Local Area Network）又はインターネット等のネットワークを介して接続されている。
【００１９】
配列データベース装置３０は、配列データベース３１が記録された記憶装置を有する装置である。配列データベース３１は、既知又は既存のＤＮＡの塩基配列（ａｃｇｔの配列。以下、単に「配列」という。）の集合を含む塩基配列データベースである。
【００２０】
検索サーバ装置２０ａ及び２０ｂ（以下、総称する場合「検索サーバ装置２０」という。）は、検索クライアント装置１０より入力されるクエリー配列に基づいて、配列データベース３１に対して相同性検索を行い、その検索結果を検索クライアント２０に応答するコンピュータである。本実施の形態において、検索サーバ装置２０は、ＢＬＡＳＴ（Basic Local Alignment Search Tool）を用いて相同性検索を行う。
【００２１】
検索クライアント装置１０は、入力されるクエリー配列群（複数のクエリー配列）をクエリー配列単位で適切にＮ分割し、分割されたクエリー配列を各検索サーバ装置２０に入力するコンピュータである。なお、クエリー配列群の分割数は、検索サーバ装置２０の数（プロセッサ数）に依存する。検索サーバ装置２０がＮ台の場合、Ｎ分割される。したがって、本実施の形態では２分割される。
【００２２】
同図において、検索クライアント装置１０は、固定長文字列出現回数調査部１１、クエリー入力部１２、部分文字列抽出部１３、部分文字列ＨＳＰ数取得部１４、クエリー配列ＨＳＰ数算出部１５、クエリー配列群分割部１６、検索要求部１７、検索結果出力部１８、及び固定長文字列出現回数テーブル１９等を有する。これら各部は、検索クライアント装置１０にインストールされたプログラムによって実現される。なお、各部は必ずしも同一のコンピュータ内に配置されなくてもよい。各部による協調がネットワークを介して行われてもよい。
【００２３】
固定長文字列出現回数調査部１１は、予め定められた固定長の配列の全ての種類について、配列データベース３１に含まれている配列における出現回数を調査する。固定長文字列出現回数調査部１１は、調査結果を固定長文字列出現回数テーブル１８として記憶装置に記録する。クエリー入力部１２は、クエリー配列群（例えば、未知の塩基配列群）の入力を受け付ける。当該入力は、ネットワークを介して行われてもよいし、検索クライアント装置１０に接続された入力装置（キーボード、マウス等）を用いて行われてもよい。部分文字列抽出部１３は、各クエリー配列から指定文字列長（ＨＳＰ（High Scoring Pair）長）の全ての部分文字列を抽出する。部分文字列は、クエリー配列において連続した一部分の文字列である。ＨＳＰ長は、検索時のパラメータとして指定される。
【００２４】
部分文字列ＨＳＰ数取得部１４は、固定長文字列出現回数テーブル１８を用いて、各部分文字列のＨＳＰ数（配列データベース３１における出現回数）の実測値又は推定値を取得する。クエリー配列ＨＳＰ数算出部１５は、各部分文字列のＨＳＰ数の実測値又は推定値に基づいて、各クエリー配列のＨＳＰ数の実測値又は推定値を算出する。クエリー配列群分割部１６は、各クエリー配列のＨＳＰ数の実測値又は推定値に基づいて、クエリー配列群をＮ分割（本実施の形態では２分割）する。検索要求部１７は、分割されたクエリー配列を各検索サーバ装置２０に入力することにより、各検索サーバ装置２０に並列的に相同性検索を実行させ、その検索結果を各検索サーバ装置２０より受信する。検索結果出力部１８は、検索結果を出力する。出力先は、ネットワークを介したコンピュータでもよいし、検索クライアント装置１０に接続された表示装置でもよい。
【００２５】
図６は、本実施の形態における検索クライアント装置のハードウェア構成例を示す図である。図６の検索クライアント装置１０は、それぞれバスBで相互に接続されているドライブ装置１００と、補助記憶装置１０２と、メモリ装置１０３と、ＣＰＵ１０４と、インタフェース装置１０５と、表示装置１０６と、入力装置１０７とを有する。
【００２６】
検索クライアント装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記録した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等（例えば、固定長文字列出現回数テーブル１９）を格納する。
【００２７】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従って検索クライアント装置１０に係る機能を実現する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。表示装置１０６はプログラムによるＧＵＩ（Graphical User Interface）等を表示する。入力装置１０７はキーボード及びマウス等で構成され、様々な操作指示を入力させるために用いられる。
【００２８】
以下、検索クライアント装置１０の処理手順について説明する。まず、相同性検索を実行する前に事前に実行される必要がある準備処理について説明する。
【００２９】
図７は、事前準備処理の処理手順を説明するためのフローチャートである。
【００３０】
ステップＳ１０１において、固定長文字列出現回数調査部１１は、固定長の配列（固定長文字列）の全ての種類について、配列データベース３１に含まれている全ての配列と一致する部分を検索することにより、固定長文字列の配列データベース３１における出現回数を取得する。
【００３１】
続いて、固定長文字列出現回数調査部１１は、固定長文字列の種類ごとに出現回数を示す情報を固定長文字列出現回数テーブル１９として補助記憶装置１０２に保存する（Ｓ１０２）。
【００３２】
図８は、固定長文字列出現回数テーブルの一例を示す図である。同図では、固定長文字列の長さを８とした場合の例が示されている。塩基配列の場合、配列の各要素は４つの文字（ａｃｇｔ）のいずれかとなる。したがって、文字列長（配列長）が８の場合、４の８乗＝６５５３６種類の固定長文字列が存在する。固定長文字列出現回数テーブル１９には、その全ての種類の固定長文字列ごとに出現回数が記録される。
【００３３】
なお、図７の処理は、配列データベース３１が複数有る場合は配列データベース３１ごとに実行される。また、配列データベース３１の内容が更新されるたびに実行される。
【００３４】
以上のような固定長文字列出現回数テーブル１９が作成されていることを前提として、以下の処理手順が実行される。
【００３５】
図９は、相同性検索において検索クライアント装置によって実行される処理手順を説明するためのフローチャートである。
【００３６】
ステップＳ２０１において、クエリー入力部１２は、クエリー配列群の入力を受け付ける。各クエリー配列の配列長は同じでなくてもよい。続いて、部分文字列抽出部１３は、ＨＳＰ長の全ての部分文字列を各クエリー配列より抽出する（Ｓ２０２）。ＨＳＰ長は、クエリー配列群の入力に伴って入力されてもよいし、予め補助記憶装置１０２に記録されていてもよい。なお、ＨＳＰ長は検索ごとに可変である。
【００３７】
図１０は、クエリー配列からの部分文字列の抽出を説明するための図である。同図では、ＨＳＰ長が１１に指定された場合に、配列長が１５のクエリー配列より部分文字列を抽出する例が示されている。この場合、部分文字列１〜５の５つの部分文字列が抽出される。一般化すると、クエリー配列長がＮ、ＨＳＰ長がＭの場合、Ｎ−Ｍ＋１個の部分文字列が抽出される。なお、同図では、一つのクエリー配列からの部分文字列の抽出例を示しているが、同様のことが各クエリー配列に対して行われる。
【００３８】
続いて、部分文字列ＨＳＰ数取得部１４は、抽出された各部分文字列のＨＳＰ数の実測値又は推定値を取得する。具体的には、ＨＳＰ長（部分文字列長）が固定長文字列の長さ以下の場合（Ｓ２０３でＹｅｓ）、部分文字列ＨＳＰ数取得部１４は、固定長文字列出現回数テーブル１９を用いて、各部分文字列のＨＳＰ数の実測値（実測ＨＳＰ数）を取得する（Ｓ２０４）。すなわち、ＨＳＰ長が固定長文字列の長さと同じであれば、固定長文字列出現回数テーブル１９において部分文字列と一致する文字列に対して登録されている出現回数を当該部分文字列の実測ＨＳＰ数とする。また、ＨＳＰ長が固定長文字列の長さより小さければ、固定長文字列出現回数テーブル１９において部分文字列と一致する文字列を最初に含む文字列（前方が部分文字列と一致する文字列）に対して登録されている出現回数の総和を当該部分文字列の実測ＨＳＰ数とする。ここで取得されるＨＳＰ数を「実測値」というのは、各部分文字列が配列データベース３１に実際に出現する回数に一致するからである。
【００３９】
一方、ＨＳＰ長が固定長文字列の長さより大きい場合（Ｓ２０３でＮｏ）、固定長文字列出現回数テーブル１９に基づいて正確なＨＳＰ数を取得することはできない。そこで、部分文字列ＨＳＰ数取得部１４は、固定長文字列出現回数テーブル１９と以下のＨＳＰ数推定式（１）とに基づいて部分文字列［ｌｉｌｉ＋１・・・ｌＭ−１ｌＭ］のＨＳＰ数を推定する（すなわち、各部分文字列のＨＳＰ数の推定値（推定ＨＳＰ長）を取得（算出）する。）（Ｓ２０４）。
【００４０】
【数２】
2010134694.tif 000003
式（１）の各パラメータ又は関数の意味は以下の通りである。
Ｍ：ＨＳＰ長
ｌｉ：部分文字列のｉ番目の文字（ｉの起点は０）
Ｎ：固定長文字列の長さ
ｃｎｔＸ［Ｙ］：文字列長Ｘの文字列Ｙの出現回数
なお、分子と分母の先頭の記号は総乗を示す。
【００４１】
式（１）の根拠については後述する。ここでは、式（１）の使い方を理解するため、式（１）に対して具体的な値を当てはめてみる。例えば、図８に示されるように固定長文字列の長さ（Ｎ）が８であり、図１０に示されるようにＨＳＰ長（Ｍ）が１１である場合、式（１）は以下の式（２）となる。
【００４２】
【数３】
2010134694.tif 000004
例えば、図１０の部分文字列１を対象として式（２）を展開すると以下のようになる。
【００４３】
cnt8[cctatggc]×(cnt8[ctatggct]/cnt7[ctatggc])
×(cnt8[tatggctg]/cnt7[tatggct])
×(cnt8[atggctgt]/cnt7[atggctg])  ・・・式（３）
ここで展開された式の各項は、８文字列又は７文字列の出現回数である。したがって、各項の値は、固定長文字列出現回数テーブル１９より取得することができる。すなわち、式（１）によれば、固定長文字列出現回数テーブル１９に基づいて部分文字列の推定ＨＳＰ長を得ることができる。
【００４４】
部分文字列ＨＳＰ数取得部１４は、以上の処理を各部分文字列について実行し、部分文字列ごとに推定ＨＳＰ長を取得する。
【００４５】
続いて、クエリー配列ＨＳＰ数算出部１５は、クエリー配列ごとに部分文字列の実測ＨＳＰ数又は推定ＨＳＰ数の総和を算出することにより、各クエリー配列の実測ＨＳＰ数又は推定ＨＳＰ数（以下、単に「ＨＳＰ数」という。）を取得する（Ｓ２０６）。続いて、クエリー配列群分割部１６は、各クエリー配列のＨＳＰ数に基づいてクエリー配列群を２分割する（Ｓ２０７）。この際、クエリー配列群分割部１６は、分割後の二つのクエリー配列群のそれぞれのＨＳＰ数の総和の差が最小となるように分割する。
【００４６】
続いて、検索要求部１７は、分割後の二つのクエリー配列群の一方を検索サーバ装置２０ａへ、他方を検索サーバ装置２０ｂへ入力することにより、配列データベース３１に対する相同性検索を各検索サーバ装置２０に並列的に実行させる（Ｓ２０８）。各検索サーバ２０より検索結果が返信されると、検索結果出力部１８は、検索結果を例えば表示装置１０６に表示させる（Ｓ２０９）。
【００４７】
上述したように、本実施の形態の検索クライアント装置１０によれば、固定長文字列出現回数テーブル１９に基づいて各クエリー配列のＨＳＰ数の実測値又は推定値を高速に取得することができる。したがって、ＨＳＰ数に基づくクエリー配列群の分割処理に関するオーバーヘッドを著しく減少させることができる。その結果、検索処理全体に関して、高い並列化効果を得ることができる。また、高速、かつ、高精度に検索時間を予測することができる。
【００４８】
但し、上記の効果は、部分文字列ＨＳＰ数取得部１４によって取得されるＨＳＰ数の精度が高いという前提に基づく。当該ＨＳＰ数の精度が低ければ、クエリー配列群を検索性能の観点より効果的に分割することができないからである。
【００４９】
そこで、当該ＨＳＰ数の精度について考察する。本実施の形態では、ＨＳＰ数について実測値又は推定値が得られる。実測値の場合、精度に問題はない。したがって、常に実測値を得られるようにすればよいと考えられる。実測値が得られるのは、ＨＳＰ長が固定長文字列の長さ以下の場合である。そうすると、固定長文字列の長さを、指定されうるＨＳＰ長よりも長く設定しておけばよいということになる。
【００５０】
しかしながら、ＨＳＰ長は検索時にオプションで指定可能であり、指定されうる最長のＨＳＰ長に対して固定長文字列出現回数テーブル１９を用意するのは現実的ではない。
【００５１】
例えば、図１１は、固定長文字列の長さと固定長文字列出現回数テーブルのサイズとの関係を示す図である。同図は、固定長文字列出現回数テーブル１９の１エントリに４Ｂｙｔｅ使用することとしている。本実施の形態のように固定長文字列の長さを８文字とした場合、テーブルサイズは２５６ＫＢｙｔｅとなる。以降、固定長文字列が１文字増加するごとにテーブルサイズは４倍となる。その結果、１４文字の場合は１ＧＢｙｔｅとなり、配列データベース３１より大きな記憶容量が必要となる可能性がある。また、テーブルサイズの肥大化は、固定長文字列出現回数テーブル１９に対する参照時間の増加にもつながる。
【００５２】
そこで、本実施の形態では、固定長文字列の長さを８としているのである。この場合、固定長文字列出現回数テーブル１９のサイズは２５６ＫＢｙｔｅであり、その全てをメモリ装置１０３に展開できる可能性が高い。その結果、固定長文字列出現回数テーブル１９に対する参照時間を減少させることができる。
【００５３】
但し、この場合に得られるＨＳＰ数は推定値となる。そこで、本実施の形態における推定ＨＳＰ数の精度について、すなわち、式（２）の根拠について説明する。
【００５４】
ここでは、図１０に示される部分文字列１（ｃｃｔａｔｇｇｃｔｇｔ）をＨＳＰ数の推定対象とする。本実施の形態における表現規則によれば、部分文字列１のＨＳＰ数は、
cnt11[cctatggctgt]
と表せる。
【００５５】
これを以下のように展開する。
【００５６】
cnt11[cctatggctgt]
=cnt10[cctatggctg]×(cnt11[cctatggctgt]/cnt10[cctatggctg])  ・・・（第一展開式）
これは、単に、cnt11[cctatggctgt]をcnt10[cctatggctg]で除し、その結果にcnt10[cctatggctg]を乗じただけである。
【００５７】
ここで、本願発明者は、第一展開式を以下のように第一近似式に近似できることに想到した。
【００５８】
cnt10[cctatggctg]×(cnt11[cctatggctgt]/cnt10[cctatggctg])
≒cnt10[cctatggctg]×(cnt8[atggctgt]/cnt7[atggctg])  ・・・（第一近似式）
第一展開式から第一近似式への近似について説明する。まず、第一展開式の部分式
cnt11[cctatggctgt]/cnt10[cctatggctg]
に注目する。これは、１１文字列「cctatggctgt」の出現回数を１０文字列「cctatggctg」の出現回数で除すというものである。当該１０文字列は、当該１１文字列の末尾のｔを削除したものである。そうすると、当該部分式は、当該１０文字列の後に「ｔ」が出現する確率に相当する。
【００５９】
次に、第一近似式の部分式
cnt8[atggctgt]/cnt7[atggctg]
に注目する。これは、８文字列「atggctgt」の出現回数を７文字列「atggctg」の出現回数で除すというものである。当該７文字列は、当該８文字列の末尾のｔを削除したものである。そうすると、当該部分式は、当該７文字列の後に「ｔ」が出現する確率に相当する。
【００６０】
すなわち、第一展開式から第一近似式への展開は、上記１０文字列「cctatggctg」の後に「ｔ」が出現する確率と、上記７文字列「atggctg」の後に「ｔ」が出現する確率とは近似するという推定に基づく。ここで、当該７文字列「atggctg」は、当該１０文字列「cctatggctg」の最初の「ｃｃｔ」を削除したものであり、双方の後方の７文字は完全に一致する。そうすると、当該推定の確からしさは、理論上からも非常に高いものと考えられる。
【００６１】
また、本願発明者は、当該推定を裏付けるために実際の配列データベースを用いて上記１１文字列、１０文字列、８文字列、７文字列の出現回数を調査し、上記近似の誤差が実運用上無視できる程度のものであることを確認した。
【００６２】
そうすると、第一近似式におけるcnt10[cctatggctg]は以下のように展開することができる。
【００６３】
cnt10[cctatggctg]
＝cnt9[cctatggct]×(cnt10[cctatggctg]/cnt9[cctatggct])  ・・・（第二展開式）
≒cnt9[cctatggct]×(cnt8[tatggctg]/cnt7[tatggct])      ・・・（第二近似式）
第二展開式への展開は自明である。また、第二展開式から第二近似式への展開の根拠は、第一展開式から第一近似式への近似の根拠と同じである。
【００６４】
更に、第二近似式におけるcnt9[cctatggct]は以下のように展開することができる。
【００６５】
cnt9[cctatggct]
＝cnt8[cctatggc]×(cnt9[cctatggct]/cnt8[cctatggc])  ・・・（第三展開式）
≒cnt8[cctatggc]×(cnt8[ctatggct]/cnt7[ctatggc])    ・・・（第三近似式）
第三展開式への展開は自明である。また、第三展開式から第三近似式への近似の根拠は、第一展開式から第一近似式への展開の根拠と同じである。
【００６６】
ここで、第三近似式を第二近似式のcnt9[cctatggct]に代入し、その結果得られる式を第一近似式のcnt10[cctatggctg]に代入すると、以下の式（４）が得られる。
【００６７】
cnt8[cctatggc]×(cnt8[ctatggct]/cnt7[ctatggc])
×(cnt8[tatggctg]/cnt7[tatggct])
×(cnt8[atggctgt]/cnt7[atggctg])  ・・・（４）
式（４）は、図１０の部分文字列１を対象として式（２）を展開した式（３）と同じである。そうすると、部分文字列１について式（２）の根拠（妥当性）は検証できたことになる。そして、部分文字列１について式（２）が妥当であれば、確率的に他の部分文字列２〜５についても式（２）は妥当であると考えられる。したがって、式（２）による推定は妥当であるといえる。
【００６８】
更に、ＨＳＰ長が１１以外であり、固定長文字列の長さが８以外である場合も同様の推定が可能であると考えられる。例えば、ＨＳＰ長が１２であり、固定長文字列の長さが９であっても推定の精度は近いと考えられる。そうすると、式（２）をＨＳＰ長と固定長文字列の長さに関して一般化することにより得られる式（１）に基づく推定も妥当であるといえる。なお、推定の精度の観点からは、ＨＳＰ長と固定長文字列との差が小さければ小さいほど好ましい。
【００６９】
上述したように、本実施の形態における検索クライアント装置１０によれば、固定長文字列出現回数テーブル１９に予め登録された出現回数を式（１）に当てはめることによりＨＳＰ長を高速かつ精度良く推定することができる。したがって、固定長文字列出現回数テーブル１９において、最長のＨＳＰ長による固定長文字列の出現回数を管理する必要性を著しく低減させることができる。その結果、固定長文字列出現回数テーブル１９のサイズを小さくすることができ、当該テーブルに対する参照時間を短縮させることができる。よって、ＨＳＰ数に基づくクエリー配列群の分割の実装を現実的なものとすることができる。
【００７０】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【００７１】
以上の説明に関し、更に以下の項を開示する。
（付記１）
コンピュータに、
塩基配列データベースに対するクエリー配列からＨＳＰ長の全ての部分文字列を抽出する部分文字列抽出手順と、
固定長の配列の全ての種類について前記配列データベースにおける出現回数が記録された出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の推定値を算出するＨＳＰ数推定手順と、
前記クエリー配列のＨＳＰ数として全ての前記推定値の総和を算出するＨＳＰ数算出手順とを実行させるためのＨＳＰ数推定プログラム。
（付記２）
前記ＨＳＰ数推定手順は、固定長Ｎの配列に係る前記出現回数管理手段に記録された出現回数を、
【数４】
2010134694.tif 000005
に当てはめることにより、ＨＳＰ長Ｍの前記部分文字列［ｌｉｌｉ＋１・・・ｌＭ−１ｌＭ］のＨＳＰ数の推定値を算出する付記１記載のＨＳＰ数推定プログラム。
（付記３）
前記固定長は、前記ＨＳＰ長より短い付記１又は２記載のＨＳＰ数推定プログラム。
（付記４）
前記固定長は８である付記１乃至３いずれか一項記載のＨＳＰ数推定プログラム。
（付記５）
前記固定長が前記ＨＳＰ長以上のときに、前記出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の実測値を取得するＨＳＰ数取得手順を有し、
前記ＨＳＰ数算出手順は、前記固定長が前記ＨＳＰ長以上のときは、前記クエリー配列のＨＳＰ数として全ての前記実測値の総和を算出する付記１又は２記載のＨＳＰ数推定プログラム。
（付記６）
塩基配列データベースに対するクエリー配列からＨＳＰ長の全ての部分文字列を抽出する部分文字列抽出手段と、
固定長の配列の全ての種類について前記配列データベースにおける出現回数が記録された出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の推定値を算出するＨＳＰ数推定手段と、
前記クエリー配列のＨＳＰ数として全ての前記推定値の総和を算出するＨＳＰ数算出手段とを有するＨＳＰ数推定定装置。
（付記７）
前記ＨＳＰ数推定手段は、固定長Ｎの配列に係る前記出現回数管理手段に記録された出現回数を、
【数５】
2010134694.tif 000006
に当てはめることにより、ＨＳＰ長Ｍの前記部分文字列［ｌｉｌｉ＋１・・・ｌＭ−１ｌＭ］のＨＳＰ数の推定値を算出する付記６記載のＨＳＰ数推定定装置。
（付記８）
前記固定長は、前記ＨＳＰ長より短い付記６又は７記載のＨＳＰ数推定定装置。
（付記９）
前記固定長は８である付記６乃至８いずれか一項記載のＨＳＰ数推定定装置。
（付記１０）
前記固定長が前記ＨＳＰ長以上のときに、前記出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の実測値を取得するＨＳＰ数取得手段を有し、
前記ＨＳＰ数算出手段は、前記固定長が前記ＨＳＰ長以上のときは、前記クエリー配列のＨＳＰ数として全ての前記実測値の総和を算出する付記６又は７記載のＨＳＰ数推定定装置。
（付記１１）
コンピュータが実行するＨＳＰ数推定方法であって、
塩基配列データベースに対するクエリー配列からＨＳＰ長の全ての部分文字列を抽出する部分文字列抽出手順と、
固定長の配列の全ての種類について前記配列データベースにおける出現回数が記録された出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の推定値を算出するＨＳＰ数推定手順と、
前記クエリー配列のＨＳＰ数として全ての前記推定値の総和を算出するＨＳＰ数算出手順とを有するＨＳＰ数推定方法。
（付記１２）
前記ＨＳＰ数推定手順は、固定長Ｎの配列に係る前記出現回数管理手段に記録された出現回数を、
【数６】
2010134694.tif 000007
に当てはめることにより、ＨＳＰ長Ｍの前記部分文字列［ｌｉｌｉ＋１・・・ｌＭ−１ｌＭ］のＨＳＰ数の推定値を算出する付記１１記載のＨＳＰ数推定方法。
（付記１３）
前記固定長は、前記ＨＳＰ長より短い付記１１又は１２記載のＨＳＰ数推定方法。
（付記１４）
前記固定長は８である付記１乃至３いずれか一項記載のＨＳＰ数推定方法。
（付記１５）
前記固定長が前記ＨＳＰ長以上のときに、前記出現回数管理手段を用いて、全ての前記部分文字列のＨＳＰ数の実測値を取得するＨＳＰ数取得手順を有し、
前記ＨＳＰ数算出手順は、前記固定長が前記ＨＳＰ長以上のときは、前記クエリー配列のＨＳＰ数として全ての前記実測値の総和を算出する付記１１又は１２記載のＨＳＰ数推定方法。
【図面の簡単な説明】
【００７２】
【図１】クエリーを２分割した場合の分割前後の原理的な検索時間を示す図である。
【図２】配列長の等しい二つの配列をクエリーとした場合のＢＬＡＳＴによる検索時間の例を示す図である。
【図３】配列長に基づいてクエリーを２分割した場合の分割前後のＢＬＡＳＴによる検索時間を示す図である。
【図４】ＨＳＰ数に基づいてクエリーを２分割した場合の分割前後のＢＬＡＳＴによる処理時間を示す図である。
【図５】本実施の形態における相同性検索システムの構成例を示す図である。
【図６】本実施の形態における検索クライアント装置のハードウェア構成例を示す図である。
【図７】事前準備処理の処理手順を説明するためのフローチャートである。
【図８】固定長文字列出現回数テーブルの一例を示す図である。
【図９】相同性検索において検索クライアント装置によって実行される処理手順を説明するためのフローチャートである。
【図１０】クエリー配列からの部分文字列の抽出を説明するための図である。
【図１１】固定長文字列の長さと固定長文字列出現回数テーブルのサイズとの関係を示す図である。
【符号の説明】
【００７３】
１            相同性検索システム
１０          検索クライアント装置
１１          固定長文字列出現回数調査部
１２          クエリー入力部
１３          部分文字列抽出部
１４          部分文字列ＨＳＰ数取得部
１５          クエリー配列ＨＳＰ数算出部
１６          クエリー配列群分割部
１７          検索要求部
１８          検索結果出力部
１９          固定長文字列出現回数テーブル
２０ａ、２０ｂ    検索サーバ装置
３０          配列データベース装置
３１          配列データベース
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
１０６        表示装置
１０７        入力装置
Ｂ            バス
【図１】
2010134694.tif 000009
【図２】
2010134694.tif 000010
【図３】
2010134694.tif 000011
【図４】
2010134694.tif 000012
【図５】
2010134694.tif 000013
【図６】
2010134694.tif 000014
【図７】
2010134694.tif 000015
【図８】
2010134694.tif 000016
【図９】
2010134694.tif 000017
【図１０】
2010134694.tif 000018
【図１１】
2010134694.tif 000019