(57)【要約】      （修正有）【課題】配列計算を行なう計算機において、メモリの使用量を増やさずにパイプラインの数を増加させる。【解決手段】メモリリード機能４２ａを有するパイプラインＲ（第１計算手段、ＰＲ）４２によりメモリ（ＲＡＭ）４０４からデータを読み込み、そのデータを用いて計算を行なった出力を、次にあるパイプラインＮ（第２計算手段）の第１段（ＰＮ1、４４）に渡す。ＰＮ1は、そのデータに基づいて計算を行い、順次ＰＮ2（４６）、ＰＮ3へと計算結果を次段のパイプラインに渡してゆく。そして、パイプラインＮの最終段ＰＮK-2（４８）は、メモリライト機能を持つパイプラインＷ（第３計算手段、ＰＷ、４０２）に出力を渡す。ＰＷはメモリライト機能４０２ａを備え、メモリライト機能４０２ａにより最終的な出力をＲＡＭ４０４に書き込む。並列数ｋのパイプライン（ＰＲ、ＰＮ1〜ＰＮK-2、ＰＷ）は、並列して計算を実行する。【選択図】図４
2005071013.tif 000002
【特許請求の範囲】
【請求項１】
対比される２つの配列についての配列データと該２つの配列間の類似度の初期値データとを格納する機能と、該類似度の計算結果データを格納する機能とを有するメモリと、
該配列データと該類似度の初期値データとを前記メモリから読み込むメモリリード機能と、該メモリリード機能によって読み込まれた該配列データと該類似度の初期値データに基づいて内部レジスタを用いた演算を行って、該２つの配列についての類似度を算出する計算機能とを有する第１計算手段と、
１または互いに直列に接続された２以上の第２計算手段であって、配列データと類似度とに基づいて内部レジスタを用いた演算を行って、該２つの配列についての類似度を算出する計算機能をそれぞれが有し、前記第１計算手段が出力する配列データと類似度とを直列に接続された最初の第２計算手段が直接受け取ってそれに基づいて演算を行なうものである、第２計算手段と、
最終段に接続された該第２計算手段が出力する該配列データと類似度とを直接受け取ってそれに基づいて内部レジスタを用いた演算を行って、該２つの配列についての類似度を算出する計算機能を有し、演算後の類似度のデータを前記メモリに書き込むメモリライト機能を有している第３計算手段と
を備え、類似度を算出する各計算手段の計算機能がパイプライン処理を行なう、ペアワイズアライメントにおける類似度の計算装置。
【請求項２】
第２計算手段を複数有し、
互いに直列に接続された第２計算手段のうち、最初の第２計算手段以外の第２計算手段は、それぞれの前段に接続された第２計算手段が出力する配列データと類似度とを直接受け取ってそれに基づいて演算を行なうものである、請求項１に記載の計算装置。
【請求項３】
前記第１計算手段の前記メモリリード機能は、前記二つの配列について最後に読み込んだ文字の位置に基づいて、今次読み込む配列データの文字の位置を定め、前記２つの配列の一方の配列については順方向に、他の配列については逆方向にそれぞれ１文字移動させた位置の文字を読み込むものであり、
前記第１計算手段と前記第２計算手段は、前記計算機能の計算の進行に同期して類似度のデータをバイパスして進行させる類似度バイパス機能をさらに有しており、
前記各計算手段の少なくともいずれかは、２段前の計算手段による類似度の計算結果を、直前の計算手段の前記バイパス機能によってバイパスさせて受け取って計算に用いるものである、請求項１に記載の計算装置。
【請求項４】
前記第１計算手段および前記第２計算手段に含まれる計算機能は、前記二つの配列における一方の配列の文字と他方の配列の文字位置の対応を１文字だけシフトするものである、請求項１に記載の計算装置。
【請求項５】
前記第１計算手段と前記第２計算手段と前記第３計算手段とに含まれる計算機能は、直列につながれる複数の配列の間に付加される制御文字を認識して、個々の配列に隣接する配列との境界において配列ごとの計算を区分するためのエミュレータ機能を含むものである、請求項１に記載の計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、バイオインフォマティクスの分野において、相同性検索を高速に行なう専用計算機に関する。
【背景技術】
【０００２】
ＤＮＡの塩基配列やタンパク質のアミノ酸配列において２つの配列の間の相同性を効率よく検索する手法等として、ＤＰ法（Dynamic Programming法、あるいは、スミス＝ウォーターマン法、非特許文献１）、ＦＡＳＴＡ法（非特許文献２、３）、ＢＬＡＳＴ法（Basic Local Alignment Search Tool法、非特許文献４）といったアルゴリズムが知られている。
【０００３】
これらの手法の基本となるＤＰ法について、図１および図２を用いて計算法の概念を示す。図１ａ，ｂは、ＤＰ法において用いられるペアワイズアライメントと呼ばれる手法の概念を示す説明図である。ペアワイズアライメントは、対比させたい２つの配列間において一致する部分を対応させた配列（アライメント）と、その２つの配列間の相同性の指標となる数値（類似度）とを求める手法である。
【０００４】
図１ａにおいて、マトリックス状に示されたネットワークの最左列には、ＧＦＳＤという文字列が記載され、ネットワークの最上部には、ＧＫＦＤという文字列が記載されている。これらの文字列は、各文字が２０種のアミノ酸のいずれかを表わし、これらの文字列の示す配列がアミノ酸の実際の配列を表わしている。つまり、図１ａは、ＧＦＳＤというアミノ酸配列（以下、第１の配列という）を有する他のタンパク質と、ＧＫＦＤというアミノ酸配列（以下、第２の配列という）を有するタンパク質との間でペアワイズアライメントを行なうことを示している。
【０００５】
ネットワーク１０は、各文字列に含まれる文字数（ここでは、４）に１を加えた数だけの縦横の線によって構成されている。その各交点は、類似度を求めてアライメントを定める計算の段階を示すノードとなる。また、ネットワーク１０の各ノードを左上から右下に繋ぐ対角線も示されている。ノードは行と列の整数のインデックスｉとｊによって指定される。図１ａでは、文字数が４であるため、ｉ、ｊともに０から４までのインデックスによってノードが指定される。
【０００６】
図１ａには、アライメントを行なった結果を示す太線１２が示されている。この太線は、計算の始点となるノード（ｉ，ｊ）＝（０、０）と、終点となるノード（４、４）とを結ぶ経路のうち、後述する計算を実行して類似度を求めた結果、その類似度が最も高くなった経路を示している。この経路は、第１の配列（ＧＦＳＤ）と第２の配列（ＧＫＦＤ）を対応させるアライメントを示している。このアライメントを、図２に示す。例えば、ノード（０，０）とノード（１，１）の間に引かれた対角の太線１４は、第１と第２の配列のそれぞれの第１文字目がともにＧで一致しており、アライメントにおいてこれらを対応させるべきことを示している。同様に、ノード（１，２）とノード（２，３）を結ぶ対角の太線１６は、第１の配列の第２文字目と第２の配列の第３文字目がともにＦで、これらを対応させるべきことを表わしている。ノード（１，１）とノード（１，２）を結ぶ水平の太線１８は、第２の配列における対比させる文字を一文字進めて、第１の配列では進めないことを意味しており、このずれを合わせるために図２において第１の配列２０中にハイフン２４を挿入して配列にギャップを与えて、第２の配列２２と配列をそろえることに対応する。同様に、図１ａの縦線１８２は図２のハイフン２６で示されるギャップに対応する。
【０００７】
ここで、２つのタンパク質の配列の相同性を検討する際には、対応させる部分が同じアミノ酸同士が類似性を高めるものであるが、対応させる部分が異なるアミノ酸であっても、類似の配列と判断してよいアミノ酸の組み合わせがある。ここでは、タンパク質の生体における突然変異において、あるアミノ酸が他の種類のアミノ酸に遷移する確率が高ければ、その突然変異前のアミノ酸と突然変異後のアミノ酸が生物学的に類似といえることを利用する。このため、この突然変異におけるアミノ酸同士の遷移確率を類似度の計算に反映させる。このような遷移確率は、非特許文献５に複数の種類のものが与えられている。
【０００８】
なお、図１ａおよび２では、配列の長さが等しいタンパク質の配列を対比させているが、異なる長さの配列を対比させてもよい。この場合にも、計算の終点となるノードは、各対比させる配列の長さ（文字列数）のインデックスによって指定されるノードとなる。
【０００９】
次に、類似度を具体的に算出するための数式について説明する。式１〜３は、ペアワイズアライメントを行なう際に用いられる式である。式１〜３において、ＳV、ＳD、ＳHは、それぞれ、垂直方向スコア、対角方向スコア、水平方向スコアと呼ばれる量である。添え字ｉ，ｊは、ネットワーク１０（図１ａ）のノードを表わす添え字であり、図１ｂに示したように、各ノードに対して式１〜３の三種類の量が計算される。
【数１】
2005071013.tif 000003
【数２】
2005071013.tif 000004
【数３】
2005071013.tif 000005
【００１０】
式１〜３は、添え字ｉとｊが小さい値によって定まる漸化式の形態の式であり、図１ｂの様に注目するノード（ｉ，ｊ）に向う上、左、左上の方向からの垂直方向スコア、対角方向スコア、水平方向スコアを含んでいる。式１におけるｒはExtendingギャップコストと呼ばれ、ギャップの長さを１つ伸ばすことに課すコストである。通常、ｒは負の値にする（例えば、−１）。また、式１におけるｇはOpeningギャップコストと呼ばれ、ギャップを設けること自体に課すコストである。ｇも通常は負の値にする（例えば、−７）。式２のＷi、jは、ノードｉ，ｊの示す文字（アミノ酸）がＡiおよびＡjであるとき、ＡiおよびＡjによって定まる確率遷移行列を表わすが、本明細書では簡略のため、ｉ，ｊのみで定まるものであるように記載している。このＷi、jは、例えば、非特許文献５に示されるＰＡＭ２５０である。この値は、同じアミノ酸に対しては高い値（例えば、８）を示すが、異種のアミノ酸に対しては一般にこれより低い値を示す（例えば０）。しかし、異種のアミノ酸であっても、生体内での遷移が多い組み合わせでは高い値を示す。Ｍａｘ（）は、括弧内の要素の最大値を与える演算子（関数）を表わす。なお、各スコアにおいて、添え字は０以上の整数値をとるものであり、値の具体的な算出に必要な添え字に０を含むスコアは、式４〜６のように定める。また、式１〜６によって定義されないスコアは、計算に影響しない十分に小さいスコア（計算機がアンダーフローを起こさない十分小さい数）を代入しておく。
【数４】
2005071013.tif 000006
【数５】
2005071013.tif 000007
【数６】
2005071013.tif 000008
【００１１】
以上の式にしたがって、各ノードに関して計算を行なう。そして、ノードについて３つ値が求まるが、そのうち最大の値をそのノードについての類似度とする。このようにして、始点から終点に至るノードについて、類似度を計算してゆく。対比している第１の配列と第２の配列の類似度は、終点となるノードにおける類似度によって示される。
【００１２】
図１ａにおいては、太線１２の横に記載された数字は、そのノード間のスコアの差分を表わしている。この差分は、図１ｂに示したように、水平方向または垂直方向については、ｇ＋ｒまたはｒの値となり、対角方向については、Ｗi、jの値となる。式１〜３から、太線の経路についてこの数値の和を取ることにより、そのノードまでの類似度となる。図で示された類似度２は、この第１の配列と第２の配列同士の類似度を表わしている。
【００１３】
ＤＰ法は、図１ａでは記載されていないが、全てのノードについて類似度の計算を実行し、最終的な結果として、終点となるノードにおける類似度を二つの配列の全体としての類似度として算出する。なお、アライメントが必要であれば、終点から、その終点の類似度を与えるために選択された経路をさかのぼる（トレースバックする）ことで得られる。
【００１４】
ＤＰ法は、全てのノードについての計算を実行することから、配列長ｎ同士の計算量は、ｎ2に比例するオーダーで増加する。これに対し、ＦＡＳＴＡ法およびＢＬＡＳＴ法は、共に、ＤＰ法の計算が全てのノードについて行なっている点に着目して計算量を低減することにより、それぞれ、ＤＰ法の３倍及び１０倍の計算効率の高速化を実現する（配列長が１０００同士の配列を比較した場合）。具体的には、ＦＡＳＴＡ法では、図１ａのネットワークの対角領域の一定の部分の計算に限定して計算量を削減する。また、ＢＬＡＳＴ法では、図１ａの対角の太線で表わされた部分（同じアミノ酸同士や遷移確率が高いアミノ酸同士となる部分）のみを先に算出し、その後に、水平あるいは垂直の太線で経路を繋ぐことに相当する処理をする。
【００１５】
現在の数値計算を行なう汎用のプロセッサが装備されたコンピュータ（パーソナルコンピュータ、ワークステーション等）には、ＤＰ法による計算量を処理できるだけの十分な能力はない。したがって、汎用のコンピュータによって計算処理する場合には、ＦＡＳＴＡ法やＢＬＡＳＴ法を採用することが多い。しかしながら、これらの手法は、ＤＰ法のように全てのノードについて計算をするものではなく、ＤＰ法のようにペアワイズアライメントについての完全な計算が出来るわけではなく、得られた類似度が完全なものではない。
【００１６】
上記課題に鑑み、本願発明者らは、ＤＰ法において類似度を効率よく計算するための専用計算機を構築している。この計算機は、並列計算（パイプライン処理）を行なうが、その際、図３に示すように、パイプライン処理に適した斜め方向に計算の順序を選ぶ。なお、このような順序にすることで計算の効率が良くなるのは、仮に計算順序を横方向にすると、ノード（ｉ，ｊ＋１）の計算は、ノード（ｉ，ｊ）の計算が完全に終了するまで始めることは出来ないが、図３のように計算順序を斜め方向にすれば、あるパイプライン（例えば、符号１で示されるパイプライン１）は、連続計算するノード（ノード（０，１）とノード（１，０）の計算に依存関係が無いためにすぐに実行でき、このようなパイプラインディレイを回避することが出来るためである。
【００１７】
なお、特許文献１には、核酸やアミノ酸等の生体高分子配列データベースを、ホモロジが高い配列同士が均等に分布するように分割する手法によって、スミス−ウォーターマン法（ＤＰ法）を高速化する手法が開示されている。
【特許文献１】特開平９−５０４３８号公報
【非特許文献１】T. F. Smith and M. F. Waterman, "Identification of common molecular subsequences", Journal of Molecular Biology, vol. 147, pp195-197, 1981
【非特許文献２】W. J. Wilbur and  D. j. Lipman, "Rapid similarity searches of nucleic acid and protein data banks", Proceedings of the National Academy of Sciences of the U.S.A, vol.80(3), pp726-730, 1983
【非特許文献３】D. j. Lipman and W. R. Pearson, "Rapid and sensitive protein similarity search", Science, vol.227, pp.1435-1441, 1985
【非特許文献４】S. F. Altschul, W. Gish, W. Miller, E.W.Myers and D.J.Lipman, "A basic local alignment search tool", Journal of Molecular Biology, vol.215, pp.403-410, 1990
【非特許文献５】M. Dayhoff, R. M. Schwartz and B. C. Orcutt, "A model of evolutionary change in proteins", Atlas of Protein Sequence and Structure, vol. 5(3), pp.345-352, 1978.
【発明の開示】
【発明が解決しようとする課題】
【００１８】
しかしながら、上記の並列計算を用いる手法では、類似度のダイナミックレンジをｍビット、配列長をｎ、パイプラインの並列数をｋとすると、（定数）×ｍ×ｎ×ｋビットだけのメモリを要する。つまり、処理速度を増大させるためにパイプラインの数を増加させようとすると、それに比例してメモリを使用する必要が生じ、並列化が困難となる。
本発明は、上記問題点に鑑み、計算に必要なメモリを増やさずにパイプラインの並列化を行なうことができる専用計算機を提供する。
【課題を解決するための手段】
【００１９】
本発明は複数の計算手段によってパイプラインの並列化を行なう計算機において、メモリアクセス（メモリリード、メモリライト）機能を必要最小限にして、メモリ容量が並列化の妨げにならないような構成の計算機を提供する。
【００２０】
具体的には、本発明では、対比される２つの配列についての配列データと該２つの配列間の類似度の初期値データとを格納する機能と、該類似度の計算結果データを格納する機能とを有するメモリと、該配列データと該類似度の初期値データとを前記メモリから読み込むメモリリード機能と、該メモリリード機能によって読み込まれた該配列データと該類似度の初期値データに基づいて内部レジスタを用いた演算を行って、該２つの配列についての類似度を算出する計算機能とを有する第１計算手段と、１または互いに直列に接続された２以上の第２計算手段であって、配列データと類似度とに基づいて内部レジスタを用いた演算を行って、該２つの配列についての類似度を算出する計算機能をそれぞれが有し、前記第１計算手段が出力する配列データと類似度とを直列に接続された最初の第２計算手段が直接受け取ってそれに基づいて演算を行なうものである、第２計算手段と、最終段に接続された該第２計算手段が出力する該配列データと類似度とを直接受け取ってそれに基づいて内部レジスタを用いた演算を行って、該２つの配列についての類似度を算出する計算機能を有し、演算後の類似度のデータを前記メモリに書き込むメモリライト機能を有している第３計算手段とを備え、類似度を算出する各計算手段の計算機能がパイプライン処理を行なう、ペアワイズアライメントにおける類似度の計算装置が提供される。
【００２１】
本発明の計算装置は、ペアワイズアライメントのネットワーク上を図８に記載したように斜めに辿って計算をおこなう。この際、各ノードで類似度が計算される。この各ノードでの類似度は、各ノードに定まる垂直方向スコアＳV、対角方向スコアＳD、水平方向スコアＳHのうち最大のものである。ここでは、類似度がスコアから直接計算されること、あるノードのスコアの計算は、ネットワーク上で左側上方にあるノードのスコアを用いる必要があることから、スコアを計算することと類似度を計算することを同じ意味で記載している。本発明では、このような計算を行なうための計算装置であって、第１計算手段、１つまたは複数の第２計算手段、第３計算手段が接続された多段の計算手段によって構成される計算装置が提供される。第２計算手段の数を調整することで、全体の計算手段の数を調整することができる。各計算手段は、計算を並列して実行するいわゆるパイプライン処理を行なう。
【００２２】
内部レジスタは、パイプライン実行する各計算手段の計算機能においてデータを一時的に記憶することによって、同期処理を実行するために用いられる。また、前段の計算手段から直接配列データや類似度を受け取る場合にも、内部レジスタが用いられる。このため、メモリは、各計算手段のうち、第２計算手段からアクセスされることは無い。メモリ上には、対比される２つの配列についての配列データとその２つの配列間の類似度の初期値データとが格納される。また、該類似度の計算結果データも格納される。配列についての類似度とは、二つの配列について、ギャップコストを考慮して定められる類似度であり、式１〜式６にしたがって算出される。第１、第２、第３計算手段により計算される類似度は、これらの式に従うものであり、例えば、集積回路にハードワイアード実装された計算機能によって算出される。
【００２３】
本発明においては、第２計算手段を複数有し、互いに直列に接続された第２計算手段のうち、最初の第２計算手段以外の第２計算手段は、それぞれの前段に接続された第２計算手段が出力する配列データと類似度とを直接受け取ってそれに基づいて演算を行なうものとすることも好適である。第２計算手段が複数用いられる場合に、これら同士を直列に接続すると、メモリへのアクセスを伴わずに計算を行なうことができる。
【００２４】
本発明の計算装置において、前記第１計算手段の前記メモリリード機能は、前記二つの配列について最後に読み込んだ文字の位置に基づいて、今次読み込む配列データの文字の位置を定め、前記２つの配列の一方の配列については順方向に、他の配列については逆方向にそれぞれ１文字移動させた位置の文字を読み込むものであり、前記第１計算手段と前記第２計算手段は、前記計算機能の計算の進行に同期して類似度のデータをバイパスして進行させる類似度バイパス機能をさらに有しており、前記各計算手段の少なくともいずれかは、２段前の計算手段による類似度の計算結果を、直前の計算手段の前記バイパス機能によってバイパスさせて受け取って計算に用いるものとすることが好適である。
【００２５】
読み込む配列データの文字の位置を、最後に読み込んだ文字の位置に基づいて２つの配列のある配列については順方向に、他の配列については逆方向に移動すると、図３等における斜め方向に計算が進行する。この際、類似度のデータをバイパスして進行させる類似度をバイパスさせる機能を備えておき、計算手段のうち、第３段以降のものが、２段前からのデータを、直前の計算手段のバイパス機能によってバイパスさせて受け取ることとすると、各ネットワークの対角線がパイプラインを一つ飛び越していることに対応する計算が可能となる。
【００２６】
本発明の計算装置において、前記第１計算手段および前記第２計算手段に含まれる計算機能は、前記二つの配列における一方の配列の文字と他方の配列の文字位置の対応を１文字だけシフトするものとすることが好適である。文字の位置の対応を一文字だけシフトすると、図３における符号３２および３４で示されるパイプライン１およびパイプライン２のように、斜めに計算が進行する際に、連続する二つの計算手段の計算を、隣り合った並びの計算となるようにすることができる。
【００２７】
本発明の計算装置において、前記第１計算手段と前記第２計算手段と前記第３計算手段とに含まれる計算機能は、直列につながれる複数の配列の間に付加される制御文字を認識して、個々の配列に隣接する配列との境界において配列ごとの計算を区分するためのエミュレータ機能を含むものとすることが好適である。
【００２８】
制御文字を配列に付加することにより、本発明の計算装置において計算動作を切り替えることができる。この計算動作の切り替えは、例えば、対比される配列の少なくとも一方が複数の配列を制御文字によって結合した配列である場合に、結合を表わす制御文字によって配列に境界があることを計算機能に認識させることができる。この計算機能がエミュレータ機能を含むことでこの境界を認識することができれば、結合された個々の配列を区分することができる。これにより、それぞれの配列によって計算をおこなうために配列の境界で計算の内容自体を分離しつつ、計算機の演算は連続した大きな配列の計算であるように行なうことができ、計算効率が向上する。
【発明の効果】
【００２９】
本発明の計算装置により、メモリ使用量を削減して効率よく計算可能なペアワイズアライメントにおける類似度を計算する計算装置が実現する。メモリ使用量が削減できるため、同じ計算規模に対してメモリ使用量を削減することができるのみならず、同じメモリ使用量に対しては、計算可能な配列の規模を拡大することが可能になる。
【００３０】
本発明の計算装置では、連続した配列を有する配列同士の比較が効率がよい。これに、制御文字を利用して、比較的短い配列を結合して一度に計算を実行することができる本発明の計算装置の特徴を用いれば、複数の配列の計算を効率よく実行することができる。
【発明を実施するための最良の形態】
【００３１】
以下図面を参照して、本発明の実施の形態について説明する。本実施の形態は、タンパク質におけるアミノ酸の配列同士を比較する場合を例示する。
【００３２】
図４ａは、本発明におけるパイプライン計算を行なう実施の形態に係る計算機４０において、計算データの流れの概念を示すブロック図である。メモリリード機能４２ａを有するパイプラインＲ（第１計算手段、ＰＲ）４２によりメモリ（ＲＡＭ）４０４からデータを読み込み、そのデータを用いて計算を行なった出力を、次にあるパイプラインＮ（第２計算手段）の第１段（ＰＮ1、符号４４）に渡す。ＰＮ1は、そのデータに基づいて計算を行い、順次ＰＮ2（符号４６）、ＰＮ3（図示しない）へと計算結果を次段のパイプラインに渡してゆく。そして、パイプラインＮの最終段ＰＮk-2（符号４８）は、メモリライト機能を持つパイプラインＷ（第３計算手段、ＰＷ、符号４０２）に出力を渡す。ＰＷはメモリライト機能４０２ａを備え、メモリライト機能４０２ａにより最終的な出力をＲＡＭ４０４に書き込む。並列数ｋのパイプライン（ＰＲ、ＰＮ1〜ＰＮk-2、ＰＷ）は、並列して計算を実行する。各パイプライン内では、プロセッサを動作させるクロック（図示しない）に従って計算が実行される。メモリ４０４には、類似度の初期値データを格納する領域４０４ａと類似度の計算結果データを格納する領域４０４ｂが備えられている。
【００３３】
図４ｂに多数の同種パイプラインＰ（Ｐ１〜Ｐｋ、符号４５２）を用いる従来の計算機４５０の構成について示す。ここでは、全てのパイプラインＰが同種のものとされ、それぞれがメモリリード機能４５２ａとメモリライト機能４５２ｂとを備えてメモリ（ＲＡＭ）４５４にアクセスする。そのため、パイプラインの並列数ｋに比例した容量のＲＡＭ４５４が必要になり、パイプライン数を増すためにはＲＡＭ４５４の容量を増大させる必要がある。例えば、メモリ４５４には、類似度の初期値データを格納する領域４５４ａと類似度の計算結果データを格納する領域４５４ｚのほかに、Ｐ１〜Ｐｋ−１が演算途中のデータの受け渡しを行なう領域４５４ｂ〜４５４ｙが備えられている。このように、ＲＡＭの容量を全てのパイプラインで共有するため、計算可能な配列の規模が制限されて、連続して高速に計算可能なパイプラインの特徴を生かすことができない。
【００３４】
図５は、メモリリード機能によりメモリ読み出しを伴って計算を行なうパイプラインＲ（符号５００）を示している。図６は、メモリ（ＲＡＭ）読み出しを行なうことなく、レジスタのみのデータに基づいて計算を行ない、計算結果もレジスタに格納するパイプラインＮ（符号６００）を示している。さらに、図７は、レジスタからのからのデータに基づいて計算を行い、計算結果をメモリに書き出すパイプラインＷ（符号７００）を示している。図４ａのデータの流れを示す矢印４０６は、図５〜７では、レジスタ５１４、６０２、６１０、７０２を介してパイプライン間のデータ入出力を行なう。図５〜７は、ある時刻のスナップショットを表示していて、図５のステージＳ１でＲＡＭからノード（ｉ，ｊ）のアミノ酸を読み込む時刻には、計算が１クロック分進行しているステージＳ２では、計算が進行してきた右斜め上のノード（ｉ−１，ｊ＋１）のデータが格納されていることを示している。
【００３５】
それぞれのパイプラインの計算は、図８に示されたように、ネットワーク８５０の各ノードを斜めに辿りながら、式１〜６の計算を実行する。
【００３６】
［パイプラインＲ］
図５のパイプラインＲ（符号５００）の動作を説明する。ＲＡＭ５０２は、適当なビット数（図では１６ビット）に構成された類似度のスコアデータ、対比させる各配列におけるアミノ酸の配列記号文字列データ（アミノ酸２０種のいずれか）、Ｏｐｅｎｉｎｇギャップコストｇのデータ、Ｅｘｔｅｎｄｉｎｇギャップコストｒのデータを格納している。このＲＡＭ５０２は、図４ａのＲＡＭ４０４の一部の領域を指している。図４ｂの従来の場合と異なり、ＲＡＭ５０２には、全てのノードの類似度のスコアデータの全てを格納する領域は必要ない。
【００３７】
パイプラインＲ（符号５００）は、全体が左からＳ１〜Ｓ６の６つのステージに分かれており、各ステージで計算を実行する。各ステージでは、原則として１クロックの時間内にそのステージ内の処理を終了し、次のステージにデータを出力する。
【００３８】
パイプラインＲ（符号５００）では、ステージＳ１において、垂直方向スコアＳV、対角方向スコアＳD、水平方向スコアＳHをＲＡＭから読み込む。この際、第１の配列のアミノ酸シンボルＡiと第２の配列のアミノ酸シンボルＡjも読み込む（ＲＡＭ５１６）。今次読み込む際には、最後に読み込んだ文字の位置について第１の配列について一文字順方向に文字の位置を移動させ、第２の配列について一文字逆方向に文字の位置を移動させる。つまり、ｉを１だけ増し、ｊを１だけ減じる。この結果として、計算がより進んだステージであるＳ２、Ｓ３等においてこのアミノ酸のシンボルを保持するレジスタ５１８ａ〜ｃにおいては、ステージが進むと共にｉが１ずつ減り、ｊが１ずつ増すように表現される。例えば、第１の配列のアミノ酸シンボルＡi-1と第２の配列のアミノ酸シンボルＡj+1がレジスタ５１８ｂ内に格納されている。
【００３９】
ステージＳ２〜Ｓ４では、コンパレータ（比較器）５０４、アダー（加算器）５０６を用いて、式１〜３の計算を進める。式１、３には加算が３つずつある。ここで、実装回路規模の縮小を図るため、ギャップｇを加算するという共通の加算が2つずつあって加算演算をまとめればアダーの数を削減できること、および、Ｍａｘ（）の演算において共通する比較演算を増やしてコンパレータの数を削減できることを用いる。具体的には、式１、３の右辺において、Ｍａｘ（）の中の各変数からｇを減算し、Ｍａｘ（）の外にｇを加算する式変形を行い、式１、３の加算を、負の値「−ｇ」の加算と、正の値「ｇ＋ｒ」の加算の２つにまとめるとともに、３変数のＭａｘ（）の演算を２変数の比較を２段階用いる際の共通する比較演算を増やしている。つまり、アダー５０６ａは、式１の右辺においてＭａｘ（）内に「−ｇ」を一度加算した場合の内部の第３番目の変数がＳV−ｇ（ノードの添え字は省略）となる演算を行い、コンパレータ５０４ｃは、コンパレータ５０４ｂによって選択されたＳD、ＳHの大きいものと、アダー５０６ａの出力であるＳV−ｇとの比較を行なう。アダー５０６ｃはコンパレータ５０４ｃの出力とｇ＋ｒとを加算する。
【００４０】
ステージＳ４では、ＲＯＭ５１２に格納された確率遷移行列Ｗi、j（ＰＴＭ）が、コンパレータ５０４ｄの出力に加算され、式２の計算が完了する。
【００４１】
ステージＳ５では、エミュレータ５０８が用いられているが、その詳細は後述する。通常の計算の場合には、エミュレータ５０８は、アダー５０６ｃ〜ｅの出力をそのまま出力する。
【００４２】
ステージＳ６ではレジスタ５１４によりタイミングを調整する。ステージＳ５およびＳ６では、アミノ酸のシンボルを保持するレジスタ５１８ｄ、ｅにおいて、第１の配列の位置（インデックスｉ）は同じものとされる。これに対し、第２の配列のシンボルは配列の位置（インデックスｊ）は一つ増している。これによって、次段のパイプラインにデータを引き継ぐ際に、次段のパイプラインの計算するノードが図８において隣り合った並びのノードとなるようにする事ができる。なお、ステージＳ６の右には、ステージＳ６におけるレジスタや信号線に格納されるデータの種類がラベルとして記載されている。
【００４３】
［パイプラインＮ］
図６に示すパイプラインＮ（符号６００）は、パイプラインＲのステージＳ１において、ＲＡＭへのアクセスを行なわずに、レジスタ６０２を用いたものである。これ以外の図５と同じ配置で記載された対応する要素は、パイプラインＲと同様の動作を行なう。パイプラインＮはメモリアクセスを行なうことなく計算を続行することができる。ここで、パイプラインＮのステージＳ１は、パイプラインＲのステージＳ６に該当する。
【００４４】
［パイプラインＷ］
図７に示すパイプラインＷ（符号７００）は、パイプラインＷのステージＳ６の後にＲＡＭ７１０へ直接アクセスする。これ以外の図６と同じ配置で記載された対応する要素は、パイプラインＲと同様の動作を行なう。ここで、パイプラインＷはその後段にパイプラインが接続されることが無いために、図５のレジスタ５１８ｄ、ｅに相当するレジスタは必要ない。
【００４５】
［パイプライン間の結合］
各パイプライン間の結合は、前段のステージＳ６が後段のステージＳ１に対応するように結合される。ここで、それぞれのパイプラインは、アミノ酸配列のＲＡＭ５１６（図５）やレジスタ６０６、７０８（図６、７）における第１の配列および第２の配列のインデックスがｉ，ｊとなるように計算ノードを表現している。これは、各パイプラインの表記を統一するためである。実際にはこれらが相互に結合される。
【００４６】
パイプラインＲのステージＳ６の配列のレジスタ５１８eは、ノード（ｉ−４，ｊ＋５）を参照している。これが、パイプラインＲのステージＳ１のレジスタ６０６に対応している。したがって、パイプラインＲのステージＳ６の各レジスタがパイプラインＮのステージＳ１の各レジスタとどの様に対応するかを見るためには、パイプラインＲのステージＳ６のインデックスにおいて、ｉに４を加えてｊから５を除く換算を行なって対応を見る必要がある。これを行なえば明らかなように、パイプラインＲのレジスタ５１４のうちラベル５１０ａで示されるものがパイプラインＮのレジスタ６０４を指しており、パイプラインＲのレジスタ５２２ｅは、パイプラインＮのレジスタ６０２ａを指している。このように、各パイプラインにおいて単にレジスタを連結するのみで他の計算に寄与していないライン５２４（図５）、６０４（図６）は、それぞれのパイプラインにおいてＳDのデータをバイパスさせ、さらにその次のパイプラインにＳDのデータを渡すように働いている。この働きは、図８において、パイプラインを飛び越すように対角にノードが結合されて計算に用いる必要があることに対応している。なお、ライン７１２（図７）は、ＲＡＭ７０６に計算データを格納するために用いられる。
【００４７】
［計算処理手順］
次に、このようにして構成された並列計算機における計算の処理を、図８を用いて説明する。図８は、第１の配列として、制御文字＆と＃によって修飾され、結合された配列「＆ＧＦＳＤ＆ＷＮＩ＃」を用い、第２の配列として、制御文字＆と＃によって修飾された配列「＆ＧＫＦＤＫＹ＃」を用いる計算について、本実施の形態の専用計算機の動作を説明する説明図である。この説明では、パイプラインＲ（ＰＲ）と、３段のパイプラインＮ（ＰＮ1、ＰＮ2、ＰＮ3）と、パイプラインＷ（ＰＷ）とによる５段のパイプラインで計算が行なわれる例を示す。矢印８０２〜８１０は、それぞれ、ＰＲ、ＰＮ1、ＰＮ2、ＰＮ3、ＰＷが計算を行なうノードとその計算の順序を表わす。また、矢印８１２〜８２０も、それぞれ、ＰＲ、ＰＮ1、ＰＮ2、ＰＮ3、ＰＷが計算を行なうノードとその計算の順序を表わす。
【００４８】
各パイプラインは、各時刻において、複数のノードを斜め方向に一定の範囲にわたって選択して、演算処理を行なう。クロックの進行と共に、矢印方向にその範囲を移動させて計算を進めてゆく。各パイプラインは、その矢印上のノードの計算を終えても、まだ計算すべきノードがある場合（例えば、矢印８０２の計算後に矢印８１２のノードがある場合）には、再び計算を開始する。クロックが進むにつれて、各パイプラインの処理範囲は矢印に沿って左下方向に移動しながら、各ノードの計算がステージＳ１〜ステージＳ６へと進行する。
【００４９】
［エミュレータＥの動作と、配列の結合］
エミュレータＥは、制御文字＆と＃によって、データの出力を制御する。具体的には、第１の配列について開始記号＆が出現すると、エミュレータＥは横方向への計算結果は次のパイプラインに伝えるが、斜め及び縦方向への計算結果は次のパイプラインへは渡さず境界における得点を与える。境界における得点とは、計算に影響を与えない十分に小さな得点である。これにより、上部からの情報が遮断されるため、全てのステージで正しく計算を行なうことが可能である。図示してはいないが、エミュレータは、第２の配列（図１のＧＫＦＤ）に＆が出現すると、左側からの情報を遮断する機能を有する。第１の配列に＆が入る場合は、初期ノードを特定することができる。これにより、複数の配列を結合しても、単一の配列であるかのように計算を行なうことができ、多くの時間において殆どのパイプラインが有効な計算を処理するようにでき、計算機のピーク性能に近い計算を連続的に実行することができる。
【００５０】
図８においては、ノード（５，７）が配列ＧＦＳＤという第１の配列の１番目の配列と配列ＧＫＦＤＫＹという配列の類似度を与える終点のノードとなる。また、ノード（９，７）が配列ＷＮＩという第１の配列の２番目の配列と配列ＧＫＦＤＫＹという配列の類似度を与える終点のノードとなる。（Ａi、Ａj）が（＆、＃）または（＃、＃）のときには、エミュレータＥは類似度取得ノードであると判定する。また、第１の配列に含まれる配列ＧＦＳＤと配列ＷＮＩが制御文字＆によって結合されて、二つの配列を一体として配列ＧＫＦＤＫＹとの間で類似度の計算がなされている。この際、長い配列のように連続した計算がなされるために、計算を開始する際のオーバーヘッドは殆どなく、ただ、制御文字を用いることによる僅かな処理遅延が発生するのみである。
【実施例１】
【００５１】
本発明の専用計算機の実施例を説明する。本実施例では、２個の６００万ゲート相当のＦＰＧＡ（Field Programmable Gate Array、Ｘｉｌｉｎｘ社製、ｘｃ２ｖ６０００）を用いることにより、専用プロセッサを実現し、これをＰＣＩボードに実装した。開発ツールにＸｉｌｉｎｘ社製ＩＳＥ５．２ｓｐ３を用いた場合、１チップあたり６５パイプラインを実装することができ、１ボードとして１３０パイプラインを実装した。この専用プロセッサは１００ＭＨｚで動作可能である。この専用プロセッサを有するボードが、本発明の実施例となる専用計算機である。なお、本ボード上には、通信用のためにＸｉｌｉｎｘ社製ｘｃｖ３００（３０万ゲート相当）も実装している。
【００５２】
このボードを、ホストコンピュータ（Ｉｎｔｅｌ社製ｉ８５０チップが搭載された、Ｐｅｎｔｉｕｍ（登録商標）４、１．８ＧＨｚをＣＰＵとして有するパーソナルコンピュータ）から、ＰＣＩバス（３２ｂｉｔ、３３ＭＨｚ）を経由して、ＯＳをＬｉｎｕｘ−２．４．２０、コンパイラをｇｃｃ−３．２．３とする環境により制御した。この専用計算機は、最大で１００００配列長のアミノ酸配列を処理することが可能である。また、現実のタンパク質は、アミノ酸の配列数が５００前後のものが多いため、平均して２０種のタンパク質を結合した１００００配列長のアミノ酸配列について、計算機の性能を十分に生かした計算を行なうことができる。
【００５３】
本実施例の専用計算機は、１００００配列同士の相同性検索を９ｍｓで完了した。一方、同じ計算を１．８ＧＨｚのＰｅｎｔｉｕｍ（登録商標）４をＣＰＵとして有するパーソナルコンピュータで実行するには、１１秒を要する。したがって、このパーソナルコンピュータによる計算に比較して、本実施例の専用計算機は、相同性計算を１２００倍高速化されたこととなる。
【００５４】
なお、上記実施の形態及び実施例は、タンパク質におけるアミノ酸配列を例として記載しているが、当業者には明らかであるように、同様に文字列により指定される任意の配列（例えば、ＤＮＡにおける核酸の配列）においても、本発明が適用可能である。
【図面の簡単な説明】
【００５５】
【図１】ペアワイズアライメントの計算の概念を示す説明図である。
【図２】ペアワイズアライメントのアライメントの概念を示す説明図である。
【図３】ＤＰ法において類似度を効率よく計算する従来のパイプライン処理の計算順序を説明する説明図である。
【図４】図４ａは、本発明における実施の形態に係るパイプライン処理を行なう計算機の構成を示す構成図である。図４ｂは、従来のパイプライン処理を行なう計算機の構成図である。
【図５】本発明の実施の形態におけるパイプラインＲ（第１計算手段）の構成を示すブロック図である。
【図６】本発明の実施の形態におけるパイプラインＮ（第２計算手段）の構成を示すブロック図である。
【図７】本発明の実施の形態におけるパイプラインＷ（第３計算手段）の構成を示すブロック図である。
【図８】ＤＰ法において類似度を効率よく計算する本発明の実施の形態におけるパイプライン処理の計算順序を説明する説明図である。
【符号の説明】
【００５６】
１０、８５０  ネットワーク
２４、２６  ギャップ
２０  第１の配列
２２  第２の配列
４０  計算機
５００  パイプラインＲ（第１計算手段）
６００  パイプラインＮ（第２計算手段）
７００  パイプラインＷ（第３計算手段）
【図１】
2005071013.tif 000009
【図２】
2005071013.tif 000010
【図３】
2005071013.tif 000011
【図４】
2005071013.tif 000012
【図５】
2005071013.tif 000013
【図６】
2005071013.tif 000014
【図７】
2005071013.tif 000015
【図８】
2005071013.tif 000016