(57)【要約】【課題】多重配列アラインメントにおいて、多数の問い合わせ配列でも高速および高精度にアラインメントできる技術を提供する。【解決手段】配列データ記憶部１１に記憶されたＮ組の配列データを読み出して、Ｎ次元超立方体データを生成するアラインメント用入力データ変換部１３と、Ｎ次元超立方体データのすべての点でスコアを計算する問合せ配列データスコア計算部１５と、Ｎ次元超立方体データにおいて、Ｎ次元超立方体の内部の全点を通るヒルベルト曲線に沿って走査を行い、一次元配列を生成するヒルベルト曲線走査部１７と、一次元配列の始まりから、Ｎ次元超立方体内の同じ対角線上にある点を探索し、最大スコアを有する対角線を最適アラインメントとして選出する対角線探索部１８とを備えた。【選択図】図２
2009217783.tif 000002
【特許請求の範囲】
【請求項１】
複数の配列データのアラインメントを行う多重配列アラインメント装置であって、
文字列から構成されるＮ組（Ｎ≧２）の配列データを記憶する配列データ記憶部と、
超立方体データ記憶部と、
スコア記憶部と、
前記配列データ記憶部に記憶されたＮ組の前記配列データを読み出して、Ｎ次元超立方体に写像し、Ｎ次元超立方体データを生成し、前記超立方体データ記憶部に保存するアラインメント用入力データ変換部と、
前記超立方体データ記憶部に保存された前記Ｎ次元超立方体データのすべての点でスコアを計算し、前記スコア記憶部に保存する問合せ配列データスコア計算部と、
前記Ｎ次元超立方体データにおいて、前記Ｎ次元超立方体の内部の全点を通るヒルベルト曲線に沿って走査を行い、一次元配列Ｈ（Ｋ）を生成するヒルベルト曲線走査部と、
前記一次元配列Ｈ（Ｋ）の始まりから、前記Ｎ次元超立方体内の同じ対角線上にある点を探索し、最大スコアを有する対角線を最適アラインメントとして選出する対角線探索部と、
を備えたことを特徴とする多重配列アラインメント装置。
【請求項２】
前記対角線探索部は、
前記ヒルベルト曲線上で近傍のスコア値が高い複数点からＮ次元対角線を生成し、各対角線上でスコア値が高い点集合である１又は複数の部分対角線を抽出する部分対角線探索部と、
抽出された前記部分対角線の中の、すべての隣接する２つの部分対角線の組について、
一方の前記部分対角線の前記ヒルベルト曲線上の始点の位置をｉｓ，終点の位置をｉｅとし、他方の前記部分対角線の前記ヒルベルト曲線上の始点の位置をｊｓ，終点の位置をｊｅとした場合に、終点ieと始点jsを元の前記Ｎ次元超立方体内部に戻し、そこでの位置座標値をそれぞれ
【数１】
2009217783.tif 000010
（ｌ∈｛１，２，…，Ｎ｝）とし、若しある自然数ｌについて
【数２】
2009217783.tif 000011
が成り立つならば、番目の配列のjs番目の要素とie番目の要素の間にギャップを挿入して、これらの２つの前記部分対角線を結合する
という結合処理を実行することで合成対角線を生成し、
前記一次元配列Ｈ（Ｋ）の始まりから、前記Ｎ次元超立方体内の同じ合成対角線上にある点を探索し、最大スコアを有する合成対角線を最適アラインメントとして選出する部分対角線結合部と、
を備えたことを特徴とする請求項１記載の多重配列アラインメント装置。
【請求項３】
複数の配列データのアラインメントを行う多重配列アラインメント方法であって、
文字列から構成されるＮ組（Ｎ≧２）の配列データを記憶する配列データ記憶部から、Ｎ組の前記配列データを読み出して、Ｎ次元超立方体に写像し、Ｎ次元超立方体データを生成し、超立方体データ記憶部に保存するアラインメント用入力データ変換ステップと、
前記超立方体データ記憶部に保存された前記Ｎ次元超立方体データのすべての点でスコアを計算し、前記スコア記憶部に保存する問合せ配列データスコア計算ステップと、
前記Ｎ次元超立方体データにおいて、前記Ｎ次元超立方体の内部の全点を通るヒルベルト曲線に沿って走査を行い、一次元配列Ｈ（Ｋ）を生成するヒルベルト曲線走査ステップと、
前記一次元配列Ｈ（Ｋ）の始まりから、前記Ｎ次元超立方体内の同じ対角線上にある点を探索し、最大スコアを有する対角線を最適アラインメントとして選出する対角線探索ステップと、
を有することを特徴とする多重配列アラインメント方法。
【請求項４】
前記対角線探索ステップにおいては、
前記ヒルベルト曲線上で近傍のスコア値が高い複数点からＮ次元対角線を生成し、各対角線上でスコア値が高い点集合である一又は複数の部分対角線を抽出する部分対角線探索ステップと、
抽出された前記部分対角線の中の、すべての隣接する２つの部分対角線の組について、
一方の前記部分対角線の前記ヒルベルト曲線上の始点の位置をｉｓ，終点の位置をｉｅとし、他方の前記部分対角線の前記ヒルベルト曲線上の始点の位置をｊｓ，終点の位置をｊｅとした場合に、終点ieと始点jsを元の前記Ｎ次元超立方体内部に戻し、そこでの位置座標値をそれぞれ
2009217783.tif 000012
（ｌ∈｛１，２，…，Ｎ｝）とし、若しある自然数ｌについて
【数４】
2009217783.tif 000013
が成り立つならば、番目の配列のjs番目の要素とie番目の要素の間にギャップを挿入して、これらの２つの前記部分対角線を結合する
という結合処理を実行することで合成対角線を生成し、
前記一次元配列Ｈ（Ｋ）の始まりから、前記Ｎ次元超立方体内の同じ合成対角線上にある点を探索し、最大スコアを有する合成対角線を最適アラインメントとして選出する部分対角線結合ステップと、
を備えたことを特徴とする請求項３記載の多重配列アラインメント方法。
【請求項５】
コンピュータに読み込ませて実行させることにより、当該コンピュータを請求項１又は２に記載の多重配列アラインメント装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多重配列アラインメントにおいて、多数の問い合わせ配列でも高速および高精度にアラインメントする技術に関する。
【背景技術】
【０００２】
複数のアミノ酸配列や塩基配列の比較解析を行う際に、アミノ酸や塩基の挿入／欠失の起きた配列上の位置を推定し、各配列を要素ごとに対応づけて並べる操作を「アラインメント」という。「多重配列アラインメント」とは、２以上のアミノ酸配列や塩基配列を相互に比較可能なものにするため、対応する配列部分が並ぶよう、適宜空白（「ギャップ（gap）」と呼ぶ。）をいれる操作をいう。特に、一対一の場合は「ペアワイズアラインメント」という。
【０００３】
従来の多重配列アラインメント法として、ダイナミックプログラミング（DP）法を利用したMSA（Multiple Sequence Alignment）プログラムが知られている。一般に、N（＞３）個の問い合わせ配列の場合、N次元超立方体の内部を探索することになるが、例えば、300個のアミン酸から成るN個の問い合わせ配列のアラインメントに要求される計算ステップ数とメモリ量は300Nのオーダーである。従って、現実的には、サーバクラスの計算機上では、MSA2.1を使って、せいぜい、500残基から成る8個の塩基ないしアミノ酸配列の近似的なアラインメントが得られるし、スーパーコンピュータ上では、MSA2.1を使って、1000残基の配列10個のアラインメントが得られる程度である。
【０００４】
その後、“sum of the pairs”（SP）法の発見により、改良版MSAプログラムでは、必要なメモリや計算量を大幅に減らすことができた（非特許文献１）。しかしながら、SP法は多重配列アラインメントをペアワイズアラインメントの組み合わせで近似する方法であり、実際、MSAでは、真に最適であることが証明されているアラインメントは滅多に得られない（非特許文献１参照）。
【非特許文献１】グプタ・S・K、ケセシオグル・J・D、シェファー・A・A、「インプルービング・ザ・プラクティカル・スペース・アンド・タイム・エフィシエンシー・オブ・ザ・ショーテスト・パスス・アプローチ・トー・サム・オブ・ペアーズ・マルチプル・シィークエンス・アラインメント（Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment）」、ジャーナル・オブ・コンピュテーショナル・バイオロジー、1995年、Vol.2, p.459-472
【非特許文献２】鎌田清一郎、新見道治、河口英二、「ヒルベルト曲線を利用した多次元画像の対話型解析法」、電子情報通信学会論文誌 D-II Vol.J77-D-II No.7 pp.1255-1264、1994年7月
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は上述した従来技術の欠点を除くためになされたものであって、その目的とするところは、多重配列アラインメントにおいて、多数の問い合わせ配列でも高速および高精度にアラインメントできる技術を提供することである。
【課題を解決するための手段】
【０００６】
本発明では、N個の問い合わせ配列のアラインメントにおいて、Hilbert曲線（非特許文献２参照。）により、N次元超立方体の内部を高速に探索し、Hilbert曲線が辿った軌跡上でN次元スコア値を算出し、Hilbert曲線上のスコア値の分布に基づいて、理想的な最適アラインメントに対応する対角線あるいは部分対角線を探索し、対角線あるいは部分対角線を結合した軌跡をアラインメントとする。
【０００７】
本発明に係る多重配列アラインメント装置は、複数の配列データのアラインメントを行う多重配列アラインメント装置であって、
文字列から構成されるＮ組（Ｎ≧２）の配列データを記憶する配列データ記憶部と、
超立方体データ記憶部と、
スコア記憶部と、
前記配列データ記憶部に記憶されたＮ組の前記配列データを読み出して、Ｎ次元超立方体に写像し、Ｎ次元超立方体データを生成し、前記超立方体データ記憶部に保存するアラインメント用入力データ変換部と、
前記超立方体データ記憶部に保存された前記Ｎ次元超立方体データのすべての点でスコアを計算し、前記スコア記憶部に保存する問合せ配列データスコア計算部と、
前記Ｎ次元超立方体データにおいて、前記Ｎ次元超立方体の内部の全点を通るヒルベルト曲線に沿って走査を行い、一次元配列Ｈ（Ｋ）を生成するヒルベルト曲線走査部と、
前記一次元配列Ｈ（Ｋ）の始まりから、前記Ｎ次元超立方体内の同じ対角線上にある点を探索し、最大スコアを有する対角線を最適アラインメントとして選出する対角線探索部と、を備えたことを特徴とする。
【０００８】
ここで、「スコア」とは、Ｎ次元空間の各座標値のうち２つの座標値の組み合わせ（座標値対）について、各座標値対の一致度を加えた値をいう。「一致度」とは、２つの座標値が一致する度合いをいい、具体的には、２つの座標値が一致する場合に最大値をとり、一致しない場合には最小値をとる関数により表される。例えば、Ｎ次元空間の点（Ｘ１，Ｘ２，…，ＸＮ）の値を（Ａ１，Ａ２，…，ＡＮ）とすると、当該点（Ｘ１，Ｘ２，…，ＸＮ）におけるスコアＳは、次式により表される。
【０００９】
【数１】
2009217783.tif 000003
ここで、Ａｋは座標値（アミノ酸又は塩基等を表すリテラル）である。また、ｓｍａｘ，ｓｍｉｎは任意に設定することができ、例えば、（ｓｍａｘ，ｓｍｉｎ）＝（１，０）、（ｓｍａｘ，ｓｍｉｎ）＝（０．９，０．１）のようにすることができる。
「対角線」とは、Ｎ次元空間における傾きが１の直線をいう。例えば、Ｎ＝２の場合、対角線はｘ−ａ＝ｙ−ｂ（ａ，ｂは定数）と表され、Ｎ＝３の場合、対角線はｘ−ａ＝ｙ−ｂ＝ｚ−ｃ（ａ，ｂ，ｃは定数）と表される。一般にＮ次元空間の対角線は、Ｎ次元空間の位置座標を（Ｘ１，Ｘ２，…，ＸＮ）とすると、
【００１０】
【数２】
2009217783.tif 000004
と表すことができる。
【００１１】
また、本発明の多重配列アラインメント装置において、前記対角線探索部は、
前記ヒルベルト曲線上の位置で１つ置きに配置され、そのスコアが高い又は正である点の集合である１又は複数の部分対角線を抽出する部分対角線探索部と、
抽出された前記部分対角線の中の、すべての隣接する２つの部分対角線の組について、
一方の前記部分対角線の前記ヒルベルト曲線上の始点の位置をｉｓ，終点の位置をｉｅとし、他方の前記部分対角線の前記ヒルベルト曲線上の始点の位置をｊｓ，終点の位置をｊｅとした場合に、終点ieと始点jsを元の前記Ｎ次元超立方体内部に戻し、そこでの位置座標値をそれぞれ
【００１２】
【数３】
2009217783.tif 000005
（ｌ∈｛１，２，…，Ｎ｝）とし、若しあるｌについて
【００１３】
【数４】
2009217783.tif 000006
が成り立つならば、ｌ番目の配列のjs番目の要素とie番目の要素の間にギャップを挿入して、これらの２つの前記部分対角線を結合する
という結合処理を実行することで合成対角線を生成し、
前記一次元配列Ｈ（Ｋ）の始まりから、前記Ｎ次元超立方体内の同じ合成対角線上にある点を探索し、最大スコアを有する合成対角線を最適アラインメントとして選出する部分対角線結合部と、
を備えたものとしてもよい。
【００１４】
ここで、「部分対角線」とは、対角線上の部分線分をいう。
また、２つの部分対角線が「隣接する」とは、一方の部分対角線の終点の位置座標と他方の部分対角線の始点の位置座標が、いずれかの座標値において一致していることをいう。
【００１５】
例えば、２次元空間の場合、部分対角線１の終点の位置座標を（ｘ（１），ｙ（１）），部分対角線２の終点の位置座標を（ｘ（２），ｙ（２））とすると、ｘ（１）＝ｘ（２）又はｙ（１）＝ｙ（２）の場合に部分対角線１，２は隣接し、それ以外の場合には部分対角線１，２は隣接しない。３次元空間の場合、部分対角線１の終点の位置座標を（ｘ（１），ｙ（１），ｚ（１）），部分対角線２の終点の位置座標を（ｘ（２），ｙ（２），ｚ（２））とすると、ｘ（１）＝ｘ（２）又はｙ（１）＝ｙ（２）又はｚ（１）＝ｚ（２）の場合に部分対角線１，２は隣接し、それ以外の場合には部分対角線１，２は隣接しない。一般に、Ｎ次元空間において、部分対角線１の終点の位置座標を（Ｘ１（１），Ｘ２（１），…，ＸＮ（１）），部分対角線２の終点の位置座標を（Ｘ１（２），Ｘ２（２），…，ＸＮ（２））とすると、ｉ＝１，２，…，ＮのうちいずれかのｉにおいてＸｉ（１）＝Ｘｉ（２）の場合に部分対角線１，２は隣接し、それ以外の場合には部分対角線１，２は隣接しない。
【００１６】
本発明に係る多重配列アラインメント方法は、複数の配列データのアラインメントを行う多重配列アラインメント方法であって、
文字列から構成されるＮ組（Ｎ≧２）の配列データを記憶する配列データ記憶部から、Ｎ組の前記配列データを読み出して、Ｎ次元超立方体に写像し、Ｎ次元超立方体データを生成し、超立方体データ記憶部に保存するアラインメント用入力データ変換ステップと、
前記超立方体データ記憶部に保存された前記Ｎ次元超立方体データのすべての点でスコアを計算し、前記スコア記憶部に保存する問合せ配列データスコア計算ステップと、
前記Ｎ次元超立方体データにおいて、前記Ｎ次元超立方体の内部の全点を通るヒルベルト曲線に沿って走査を行い、一次元配列Ｈ（Ｋ）を生成するヒルベルト曲線走査ステップと、
前記一次元配列Ｈ（Ｋ）の始まりから、前記Ｎ次元超立方体内の同じ対角線上にある点を探索し、最大スコアを有する対角線を最適アラインメントとして選出する対角線探索ステップと、
を有することを特徴とする。
【００１７】
また、本発明に係るプログラムは、コンピュータに読み込ませて実行させることにより、当該コンピュータを上記本発明の多重配列アラインメント装置として機能させることを特徴とする。
【発明の効果】
【００１８】
本発明により、複数の配列でも、近似することなく、しかも高速かつ高精度に最適アラインメントを得ることができる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００２０】
図１は、実施例１に係る多重配列アラインメント装置１のハードウェア構成を表す図である。多重配列アラインメント装置１は、入力装置２、ＣＰＵ３、ＲＡＭ４、ＲＯＭ５、外部記憶装置６、ディスプレイ装置７、及びバス８を備えている。これらは通常のコンピュータを用いて構成し、当該コンピュータにおいて本実施例の多重配列アラインメント方法を実行することによって多重配列アラインメント装置１として機能させることができる。この場合、多重配列アラインメントプログラムは外部記憶装置６に記憶され、プログラムの実行時にはＲＡＭ４にロードされて実行される。尚、入力装置２は、キーボードやマウス等のポインティングデバイスなどにより構成される。また、外部記憶装置６は、ＣＤ−ＲＯＭドライブ、ＤＶＤ−ＲＯＭドライブ、磁気ディスク等により構成される。
【００２１】
図２は、実施例１に係る多重配列アラインメント装置１を表す機能ブロック図である。多重配列アラインメント装置１は、機能的には、入力部１０、配列データ記憶部１１、アラインメント用入力データ変換部１３、超立方体データ記憶部１４、問合せ配列データスコア計算部１５、スコア記憶部１６、ヒルベルト曲線走査部１７、対角線探索部１８、及び出力部１９を備える。
【００２２】
入力部１０は、図１の入力装置２により実現されている。配列データ記憶部１１、超立方体データ記憶部１４、及びスコア記憶部１６は、図１の外部記憶装置６又はＲＡＭ４によって実現されている。アラインメント用入力データ変換部１３、問合せ配列データスコア計算部１５、ヒルベルト曲線走査部１７、及び対角線探索部１８は、図１のＣＰＵ３、ＲＡＭ４、ＲＯＭ５、及び外部記憶装置６が協働することによって実現されている。また、出力部１９は、図１のディスプレイ装置７又は外部記憶装置６によって実現されている。
【００２３】
以上のように構成された本実施例に係る多重配列アラインメント装置１について、以下その動作を説明する。。
【００２４】
まず、前提として、アラインメントを行うN個の配列データをs(1)，…，s(N)とする。これらの配列データは、入力部１０から入力されて、配列データ記憶部１１に保存されているものとする。また、ここでは、特殊な場合として、N=2、即ち、ペアワイズアラインメント（２本の配列のアラインメント）の場合も含むものとする。また、各s(i)(i=1，…，N)は塩基あるいはアミノ酸を表すアルファベットの文字列から構成され、各配列を構成する文字数を#s(i)で表すものとする。
【００２５】
図３は、実施例１に係る多重配列アラインメント装置１のデータ処理動作を表すフローチャートである。
【００２６】
まず、アラインメント用入力データ変換部１３は、配列データ記憶部１１から、Ｎ組の配列データs(1)，…，s(N)を読み出す（ステップＳ１）。
【００２７】
そして、アラインメント用入力データ変換部１３は、これらの
配列データs(1)，…，s(N)によってN次元超立方体データを形成し、超立方体データ記憶部１４に保存する（ステップＳ２）。ここで、N次元超立方体とは、例えば、N=2ならば二次元平面であり、N=3であれば三次元立方体である。N次元超立方体データは、各軸に、各配列を構成する文字列が付与されており、例えば、３つの配列、AGTC、AGTC、AGTCの場合、（1，1，1）＝（A,A,A）、（2，2，2）＝（G,G,G）となる。
【００２８】
図４は、Ｎ＝２（２つの配列）の場合の超立方体の例である。配列数が２なので、超立方体は二次元平面となる。
【００２９】
次に、問合せ配列データスコア計算部１５は、超立方体データ記憶部１４に保存されたN次元超立方体データの超立方体内部のすべての点でスコアを計算し、これらの値をスコア記憶部１６に格納する（ステップＳ３）。スコアには、二次元の場合、塩基配列ならば、例えば、PAMの進化距離に基づいた核酸置換行列の値を、アミノ酸配列の場合は、例えば、対数odds形式のPAM250スコア行列やBLOSUM62アミノ酸置換行列の値をそのまま利用することができる。
【００３０】
例えば、N次元超立方体内の各点において、N個の記号中2個以上に同じ記号がある場合に1に近い値をスコアとし、それ以外が0に近い値をスコアとする。
【００３１】
また、Nが3以上の場合は、N=3の時は、例えば、（A, G, T）に対するスコアはS(A, G)+S(G, T)+S(T, A)を指定すればよいし、N=4の時は、例えば、（A, G, T, C）に対するスコアはS(A, G)+S(G, T)+S(T, C) +S(G, C)+S(T, A)+S(C, A)とすればよい。但し、S(A, G)はペアワイズアラインメントの場合のAとGの間のスコアとする。
【００３２】
図５に、図４のデータにおいてBLOSUM62に基づいて計算された超立方体（二次元平面）内部の各点（配列要素間）のスコアを示す。図５において、各マス目の中に記載された数値が、当該マス目に対応する点におけるスコアである。
【００３３】
次に、ヒルベルト曲線走査部１７は、Ｎ組の配列データs(1)，…，s(N)によって形成されるN次元超立方体の内部をヒルベルト（Hilbert）曲線に沿って走査する（ステップＳ４）。その結果、一次元配列H(K)が得られる。但し、Kは各点の総数であり、
【００３４】
【数５】
2009217783.tif 000007
によって定義される。ここで、#s(i)は配列s(i)を構成する塩基あるいはアミノ酸の数である。
【００３５】
図６に、図５の超立方体（二次元平面）をHilbert曲線で走査した結果を示す。各正方形の左上の番号は、Hilbert曲線が辿った順番を表す。
【００３６】
次に、ヒルベルト曲線走査部１７は、一次元配列H(K)上の各点において、その局所的なスコアaとその局所座標c(N)を格納する（ステップＳ５）。
【００３７】
次に、対角線探索部１８は、一次元配列H(K)の始まりから、N次元超立方体内の同じ“対角線”上にある点を探索する（ステップＳ６）。但し、“対角線”とは、例えば、３つの配列、AGTC、AGTC、AGTCの多重配列アラインメントの結果、最適アラインメントとしてHilbert曲線が辿った軌跡を表す。こうして、考え得るアラインメントはすべて戻り無しの、その対角線と平行な線となる。
【００３８】
対角線とは、例えば、3次元上である点の座標（2,3,1）の対角線は、｛(1,2,0)，(3,4,2)，(4,5,3)，(5,6,4),…｝を通る直線である。部分対角線とは、その対角線上の部分線分である。
【００３９】
また、１つのアラインメントにおいて１点は一度しか現れない。
【００４０】
次に、対角線探索部１８は、最大スコアを有する対角線を最適アラインメントとして選出する（ステップＳ７）。
【００４１】
最後に、出力部１９は、選出された最適アラインメントのデータを出力して終了する（ステップＳ８）。
【００４２】
以上の通り、本実施例に係る多重配列アラインメント方法においては、Hilbert曲線を使うので、一次元配列H(K)内の点はアラインメントの順番近くに格納される。また、1点は1つのアラインメントのみに現れるので、一度、1点が１つのアラインメントに対して決まれば、その点が他の探索に現れることはない。従って、探索空間はステップ毎に縮減されることになる。
【実施例２】
【００４３】
図７は、実施例２に係る多重配列アラインメント装置１’を表す機能ブロック図である。尚、本実施例において、多重配列アラインメント装置１’のハードウェア構成は図１と同様である。
【００４４】
本実施例の多重配列アラインメント装置１’は、図２に示した実施例１の多重配列アラインメント装置１と比較すると、図２の対角線探索部１８の部分が、部分対角線探索部２１及び部分対角線結合部２２に置き換わっていることを特徴とする。その他の構成は、実施例１と同様である。
【００４５】
以上のように構成された本実施例に係る多重配列アラインメント装置１’について、以下その動作を説明する。
【００４６】
図８は、実施例２に係る多重配列アラインメント装置１’のデータ処理動作を表すフローチャートである。尚、本実施例においても、実施例１の場合と同様、アラインメントを行うN個の配列データをs(1)，…，s(N)とし、特殊な場合として、N=2、即ち、ペアワイズアラインメントの場合も含むものとする。また、各s(i)(i=1，…，N)は塩基あるいはアミノ酸を表すアルファベットの文字列から構成され、各配列を構成する文字数を#s(i)で表すものとする。
【００４７】
図８において、ステップＳ１〜ステップＳ５までの動作に関しては、実施例１と同様であり、説明は省略する。
【００４８】
ここで、実施例１で定義された“対角線”の概念を拡張して、以下のように“部分対角線”を定義する：
【００４９】
〔定義〕（部分対角線）
Hilbert曲線上の位置で1つ置きに配置され、そのスコア値が高い（あるいは正）である点の集合を“部分対角線”という。
（定義終わり）
【００５０】
即ち、部分対角線とは、アラインメント全体の中の一部分をなす構成要素である。また、1つ置きとは、上下左右の方向ではなく、“対角線”に平行な斜め方向を意味する。
【００５１】
図８のステップＳ１０において、部分対角線探索部２１は、部分対角線を抽出する。
【００５２】
次に、ステップＳ１１において、部分対角線結合部２２は、ステップＳ１０で得られた部分対角線の集合の中から、隣接する2つの部分対角線について、以下の処理を行う：
１．両部分対角線の始点と終点のHilbert曲線上の位置を、それぞれ、is、js、ie、jeとする（図１１参照）。
２．終点ieと始点jsを元のN次元超立方体内部に戻し、そこでの位置座標値をそれぞれ
【００５３】
【数６】
2009217783.tif 000008
３．もし、あるｌについて
【００５４】
【数７】
2009217783.tif 000009
が成り立つならば、ｌ番目の配列のjs番目の要素とie番目の要素の間にギャップ（gap）（空白若しくは「−」記号）を挿入して、これらの２つの部分対角線を結合する。
４．手順３．をすべての部分対角線の組み合わせについて実行することにより合成対角線を生成する。
【００５５】
図９は、図６のHilbert曲線上におけるスコア値の分布と部分対角線の例である。図９において、横軸にHilbert曲線上の位置をとり、縦軸に図６のスコア値を棒グラフで表示したものである。この図から、２つの“部分対角線”の存在が見てとれる。この場合、is＝1、js＝10、ie＝3、je＝14となる。これらHilbert曲線上での位置を、元の二次元超立方体の内部に戻すと、ie⇒（2，2）、je⇒（3，2）となる。従って、2番目の配列にgapを挿入して、これら部分対角線を結合させることができる。また、この例では、２つの部分対角線しか存在しないので、これで（６）部分対角線結合部は完了する。よって、最終的なアラインメント結果は、図１０に示す通りである。
【００５６】
次に、部分対角線結合部２２は、一次元配列H(K)の始まりから、N次元超立方体内の同じ“合成対角線”上にある点を探索する（ステップＳ１２）。
【００５７】
次に、部分対角線結合部２２は、最大スコアを有する合成対角線を最適アラインメントとして選出する（ステップＳ１３）。
【００５８】
最後に、出力部１９は、選出された最適アラインメントのデータを出力して終了する（ステップＳ１４）。
【図面の簡単な説明】
【００５９】
【図１】実施例１に係る多重配列アラインメント装置１のハードウェア構成を表す図である。
【図２】実施例１に係る多重配列アラインメント装置１を表す機能ブロック図である。
【図３】実施例１に係る多重配列アラインメント装置１のデータ処理動作を表すフローチャートである。
【図４】Ｎ＝２（２つの配列）の場合の超立方体の例である。
【図５】図４のデータにおいてBLOSUM62に基づいて計算された超立方体内部の各点のスコアを示す図である。
【図６】図５の超立方体（二次元平面）をHilbert曲線で走査した結果を示す図である。
【図７】実施例２に係る多重配列アラインメント装置１’を表す機能ブロック図である。
【図８】実施例２に係る多重配列アラインメント装置１’のデータ処理動作を表すフローチャートである。
【図９】図６のHilbert曲線上におけるスコア値の分布と部分対角線の例である。
【図１０】最終的なアラインメントの結果を示す図である。
【図１１】部分対角線結合部の説明図である。
【符号の説明】
【００６０】
１，１’  多重配列アラインメント装置
２  入力装置
３  ＣＰＵ
４  ＲＡＭ
５  ＲＯＭ
６  外部記憶装置
７  ディスプレイ装置
８  バス
１０  入力部
１１  配列データ記憶部
１３  アラインメント用入力データ変換部
１４  超立方体データ記憶部
１５  問合せ配列データスコア計算部
１６  スコア記憶部
１７  ヒルベルト曲線走査部
１８  対角線探索部
１９  出力部
２１  部分対角線探索部
２２  部分対角線結合部
【図１】
2009217783.tif 000014
【図２】
2009217783.tif 000015
【図３】
2009217783.tif 000016
【図４】
2009217783.tif 000017
【図５】
2009217783.tif 000018
【図６】
2009217783.tif 000019
【図７】
2009217783.tif 000020
【図８】
2009217783.tif 000021
【図９】
2009217783.tif 000022
【図１０】
2009217783.tif 000023
【図１１】
2009217783.tif 000024