(57)【要約】【課題】動的計画法に基づき２つの自己類似度行列を照合し、長さの異なる２つの系列データの各要素の対応付けられた照合スコアを出力する系列データ照合方法、系列データ照合装置、プログラムおよび記憶媒体を提供することにある。【解決手段】自己類似度行列計算部２が、入力された系列データに基づき自己類似度行列を計算し、自己類似度行列整列部３が、自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と他方の系列データの要素とを対応付け自己類似度行列に基づき動的計画法行列を計算し、適合位置・照合スコア決定部４が、動的計画法行列に基づき系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する系列データ照合方法、系列データ照合装置、プログラムおよび記憶媒体を提供することにある。【選択図】図１
2010039927.tif 000002
【特許請求の範囲】
【請求項１】
異なる系列データに基づき、動的計画法により前記自己類似度行列を照合する系列データ照合装置における系列データ照合方法であって、
前記系列データ照合装置の自己類似度行列計算部が、
入力された前記系列データに基づき前記自己類似度行列を計算し、
前記系列データ照合装置の自己類似度行列整列部が、
前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算し、
前記系列データ照合装置の適合位置・照合スコア決定部が、
前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する
ことを特徴とする系列データ照合方法。
【請求項２】
長さが異なる２つの系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合する系列データ照合装置における系列データ照合方法であって、
前記系列データ照合装置の自己類似度行列計算部が、
入力された前記系列データに基づき自己類似度行列を計算するとともに、
前記系列データのうち、長さが長い方の系列データを、自己類似度行列に変換したと仮定した場合の仮定行列サイズに比べて小さいサイズであって、分割されたそれぞれの行列が対角線方向に重なり合うサブ行列に分割し、
前記系列データ照合装置の自己類似度行列整列部が、
前記自己類似度行列および前記サブ行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算し、
前記系列データ照合装置の適合位置・照合スコア決定部が、
前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する
ことを特徴とする系列データ照合方法。
【請求項３】
異なる系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合する系列データ照合装置における系列データ照合方法であって、
前記系列データ照合装置の特徴ベクトル列計算部が、
入力データを、この入力データの特徴を表わす系列データに変換し、
前記系列データ照合装置の自己類似度行列計算部が、
前記特徴ベクトル列計算部により変換された前記系列データに基づき自己類似度行列を計算し、
前記系列データ照合装置の自己類似度行列整列部が、
前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算し、
前記系列データ照合装置の適合位置・照合スコア決定部が、
前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する
ことを特徴とする系列データ照合方法。
【請求項４】
前記入力データが、タンパク質などの物質を構成する三次元座標であり、前記自己類似度行列として前記タンパク質の構成要素間の距離行列を用いることを特徴とする請求項３に記載の系列データ照合方法。
【請求項５】
前記自己類似度行列整列部は、
予めこの自己類似度行列計算部からの前記自己類似度行列との照合のための蓄積自己類似度行列を記憶しているデータベースから、前記蓄積自己類似度行列を読み出し、
前記自己類似度行列および前記蓄積自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算し、
適合位置・照合スコア決定部が、
前記動的計画法行列に基づき、前記自己類似度行列および前記蓄積自己類似度行列の対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する
ことを特徴とする請求項３に記載の系列データ照合方法。
【請求項６】
異なる系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合する系列データ照合装置において、
入力された前記系列データに基づき自己類似度行列を計算する自己類似度行列計算部と、
前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算する自己類似度行列整列部と、
前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する適合位置・照合スコア決定部とを
有することを特徴とする系列データ照合装置。
【請求項７】
入力データを、この入力データの特徴を表す前記系列データに変換し、前記自己類似度行列計算部に出力する特徴ベクトル列計算部をさらに有することを特徴とする請求項６に記載の系列データ照合装置。
【請求項８】
異なる系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合するコンピュータに、
入力された前記系列データに基づき自己類似度行列を計算する自己類似度行列計算手段と、
前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算する自己類似度行列整列手段と、
前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する適合位置・照合スコア決定手段とを
実行させるためのプログラム。
【請求項９】
異なる系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合するコンピュータに、
入力された前記系列データに基づき自己類似度行列を計算する自己類似度行列計算手段と、
前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算する自己類似度行列整列手段と、
前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する適合位置・照合スコア決定手段とを
実行させるためのプログラムを記憶した記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、主に、２つの異なる系列データを照合し、類似する系列データを検索する系列データ照合方法、系列データ照合装置、プログラムおよび記憶媒体に関する。
【背景技術】
【０００２】
類似する音楽やタンパク質のアミノ酸配列などのデータから所定のデータを検索する場合、長さの異なる２つの系列データを照合し、照合スコアを計算する必要があり、以下のような方法が知られている。
例えば、類似音楽を照合する方法として、１２音階に対応する周波数のパワー値で短時間フレームの音響特徴を表現して系列データを作成し、動的計画法を用いて２つの系列データの要素の対応付けと照合スコアの計算を行う手法が知られている（特許文献１参照）。
また、文字列として表現されるタンパク質のアミノ酸配列を照合する方法として、確率モデルに基づくアミノ酸残基の置換スコアと動的計画法により、２つの配列の照合を行う手法が広く使われている（非特許文献１参照）。
【０００３】
動的計画法（ＤＰ）に基づくベクトル列の照合としては、図１６，１７に示すような方法が知られている。例えば、図１６に示すような、ｍ個の要素からなる長さｍのベクトル列Ａ´と、ｎ個の要素からなる長さｎのベクトル列Ｂ´を照合する場合、ベクトル列Ａ´の要素ベクトルａ（ｉ）とベクトル列Ｂ´の要素ベクトルｂ（ｉ）との対応付け（整列と呼ぶ）がなされ、この整列により得られるベクトル同士の距離や類似度に基づき、ベクトル列Ａ´とベクトル列Ｂ´との照合スコアが算出される。
ベクトル要素の対応付け、および照合スコアは、図１７に示すような、（ｍ＋１）×（ｎ＋１）のサイズを持つ動的計画法行列（ＤＰ行列）Ｆ´が利用される。すなわち、ＤＰ行列Ｆ´は、要素番号ｉおよびｊがそれぞれ０〜ｍ，０〜ｎの整数値をとる要素Ｆ´（ｉ，ｊ）を含む。要素Ｆ´（ｉ，ｊ）は、ベクトル列Ａ´の紙面左端のベクトルａ（１）からベクトルａ（ｉ）まで、ベクトル列Ｂ´の紙面左端のベクトルｂ（１）からベクトルｂ（ｊ）まで、紙面において右方向に順番に対応付け（整列）がなされ、ベクトルａ（ｉ）とベクトルｂ（ｊ）まで対応付けがなされた場合における最大照合スコアを表わしている。なお、図１７には、図１６の例において、上述したベクトルａ（ｉ）からベクトルｂ（ｊ）まで、ベクトル列Ａ´，Ｂ´のすべての要素の対応付けを行った場合の最大照合スコアを示す。
【０００４】
ＤＰ行列の要素Ｆ´（ｉ，ｊ）は、次式に示すような、隣接する３つのＦ´（ｉ−１，ｊ），Ｆ´（ｉ，ｊ−１），Ｆ´（ｉ−１，ｊ−１）を用い、式１に示す計算式に従って再帰的に計算（繰り返し計算）することにより算出できる。
【数１】
2010039927.tif 000003
ここで、式１（Ａ）に示される
【数２】
2010039927.tif 000004
は、「要素照合スコア」であって、ベクトルａ（ｉ）と、ベクトルｂ（ｊ）の類似度を表わす関数である。
【０００５】
なお、式１に示す定数ｇは、ギャップ要素（どのベクトルにも対応付けがされない要素）に対して与えられるペナルティである。また、ＤＰ行列Ｆ´の０行目および０列目の値は、式１の繰り返し計算の初期値として与えられる。ベクトル列Ａ´の全長とベクトル列Ｂ´の全長を整列に用いる場合、すなわち、ベクトル列Ａ´およびベクトル列Ｂ´それぞれのすべての要素ベクトルを用いて整列を行う場合には、初期条件を、ＤＰ行列の要素Ｆ´（ｉ，０）＝―ｉ×ｇ，Ｆ´（０，ｊ）＝―ｊ×ｇとする。本明細書において、このように系列データのすべての要素を用いて整列を行うことを、大域整列と呼称する。
また、ベクトル列Ａ´の全長と最も合致するベクトル列Ｂ´の一部分を整列に用いる場合には、ベクトル列Ｂ´の冒頭のギャップ要素を無視するため、初期条件を、ベクトルＦ´（ｉ，０）＝―ｉ×ｇ，Ｆ´（０，ｊ）＝０とする。本明細書において、このように一方の系列データのすべての要素と、これに最も合致する他の系列データを部分的に用いて整列を行うことを、半大域整列と呼称する。
さらに、ベクトル列Ａ´，Ｂ´のそれぞれにおいて、最も合致する一部分のデータを整列に用いる場合には、両方の系列データ（ベクトル列Ａ´，ベクトル列Ｂ´）の冒頭のギャップを無視するため、初期条件を、ベクトルＦ´（ｉ，０）＝０，Ｆ´（０，ｊ）＝０とする。本明細書において、このように互いに最も合致する系列データの一部分を局所的に用いて整列を行うことを、局所整列と呼称する。
【０００６】
局所整列の場合、式１に代えて、下に示す式２の計算式を用いて繰り返し計算を実行し、Ｆ´（ｉ，ｊ）を算出する。
【数３】
2010039927.tif 000005
なお、式１の要素照合スコアＭは、ベクトル列Ａ´の要素ｉとベクトル列Ｂ´の要素ｊが類似する場合に大きな値を与える関数であり、ユークリッド距離の逆数、あるいは定数からユークリッド距離を引いたものなど、ベクトル同士の類似度を表す関数を用いることができる。局所整列の場合には、ベクトルａ（ｉ）とベクトルｂ（ｊ）の類似度が低い場合には、要素照合スコアＭが負の値をとるようにする。
【０００７】
式１あるいは式２に従って、すべての要素ｉ，ｊにおけるＤＰ行列Ｆ´の計算が終了したら、整列のタイプに応じて、以下に説明する照合スコアの算出と整列を行う。
大域整列の場合、Ｆ´（ｍ，ｎ）の値を照合スコアとして、式１において選択された（Ａ）〜（Ｃ）の計算式に基づき、Ｆ´（ｍ，ｎ）からＦ´（０，０）に向かって遡っていくこと（バックトラッキング）により、ベクトル列Ａ´とベクトル列Ｂ´との対応関係を特定する。つまり、Ｆ´（ｉ，ｊ）の計算において、（Ａ）が選択された場合には、（ｉ−１，ｊ−１）に、（Ｂ）が選択された場合は（ｉ−１，ｊ）に、（Ｃ）が選択された場合は（ｉ，ｊ−１）に移動し、これを繰り返すことで最終的に（０，０）に到達する。この（ｍ，ｎ）から（０，０）に向かう経路において、（Ａ）が選択された場合の（ｉ，ｊ）それぞれについて、ベクトルａ（ｉ）とベクトルｂ（ｊ）を対応させることで、ベクトル列Ａ´，Ｂ´の整列を行う。
半大域整列の場合、ＤＰ行列Ｆ´のｍ行目の中で局所的に最大となるＦ´（ｍ，ｎ）を照合スコアとして、このＦ´（ｍ，ｎ）を個々の出発点としてＦ´（０，０）に向かって、大域整列の場合と同様のバックトラッキングにより整列を行う。
局所整列の場合、局所的に最大となるＦ´（ｉ，ｊ）を照合スコアとして、このＦ´（ｍ，ｎ）を個々の出発点としてＦ´（０，０）に向かって、大域整列、半大域整列の場合と同様のバックトラッキングにより整列を行う。Ｆ´（ｉ，ｊ）の値が０となったところでバックトラッキングを終了する。
【特許文献１】特開２００３−４４０８２号公報
【非特許文献１】Ｓ．Ｄｕｒｂｉｎなど、“Ｂｉｏｌｏｇｉｃａｌ  ｓｅｑｕｅｎｃｅ  ａｎａｌｙｓｉｓ”，Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，１９９８．より，第２章．
【発明の開示】
【発明が解決しようとする課題】
【０００８】
これらの手法は、音響信号やアミノ酸配列という表層的な構造の類似度を計算するのに適しているが、移調や編曲された音楽や、３次元立体構造のタンパク質等の照合においては、深層的な構造の類似度を計算することが困難であった。
また、音楽の照合の場合、１２音階に基づく音響特徴を半音ずつずらして１２回動的計画法による照合を行うことで移調された音楽の照合が可能であるが、計算量が増加してしまうという問題があった。
さらに、アミノ酸配列の照合の場合、３次元立体構造のタンパク質の類似する系列データのペアに対して高い照合スコアを与えることができず、検索精度が低下するという問題があった。
また、系列データの照合において、従来の短時間スペクトルの形状を特徴ベクトルとして利用すると、同一の楽曲が異なる調で演奏された場合などには高い類似度が得られず、正しい検索結果を得ることができないという問題があった。
【０００９】
本発明は、このような事情を考慮し、上記の問題を解決すべくなされたものであって、その目的は、動的計画法に基づき２つの自己類似度行列を照合し、長さの異なる２つの系列データの各要素の対応付けられた照合スコアを出力する系列データ照合方法、系列データ照合装置、プログラムおよび記憶媒体を提供することにある。
【課題を解決するための手段】
【００１０】
上記問題を解決するために、本発明は、異なる系列データに基づき、動的計画法により前記自己類似度行列を照合する系列データ照合装置における系列データ照合方法であって、前記系列データ照合装置の自己類似度行列計算部が、入力された前記系列データに基づき前記自己類似度行列を計算し、前記系列データ照合装置の自己類似度行列整列部が、前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算し、前記系列データ照合装置の適合位置・照合スコア決定部が、前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力することを特徴とする系列データ照合方法である。
【００１１】
また、本発明は、長さが異なる２つの系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合する系列データ照合装置における系列データ照合方法であって、前記系列データ照合装置の自己類似度行列計算部が、入力された前記系列データに基づき自己類似度行列を計算するとともに、前記系列データのうち、長さが長い方の系列データを、自己類似度行列に変換したと仮定した場合の仮定行列サイズに比べて小さいサイズであって、分割されたそれぞれの行列が対角線方向に重なり合うサブ行列に分割し、前記系列データ照合装置の自己類似度行列整列部が、前記自己類似度行列および前記サブ行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算し、前記系列データ照合装置の適合位置・照合スコア決定部が、前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力することを特徴とする系列データ照合方法である。
【００１２】
また、本発明は、異なる系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合する系列データ照合装置における系列データ照合方法であって、前記系列データ照合装置の特徴ベクトル列計算部が、入力データを、この入力データの特徴を表わす系列データに変換し、前記系列データ照合装置の自己類似度行列計算部が、前記特徴ベクトル列計算部により変換された前記系列データに基づき自己類似度行列を計算し、前記系列データ照合装置の自己類似度行列整列部が、前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算し、前記系列データ照合装置の適合位置・照合スコア決定部が、前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力することを特徴とする系列データ照合方法である。
【００１３】
また、本発明は、前記入力データが、タンパク質などの物質を構成する三次元座標であり、前記自己類似度行列として前記タンパク質の構成要素間の距離行列を用いることを特徴とする系列データ照合方法である。
【００１４】
また、本発明は、前記自己類似度行列整列部は、予めこの自己類似度行列計算部からの前記自己類似度行列との照合のための蓄積自己類似度行列を記憶しているデータベースから、前記蓄積自己類似度行列を読み出し、前記自己類似度行列および前記蓄積自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算し、適合位置・照合スコア決定部が、前記動的計画法行列に基づき、前記自己類似度行列および前記蓄積自己類似度行列の対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する
ことを特徴とする請求項３に記載の系列データ照合方法である。
【００１５】
また、本発明は、異なる系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合する系列データ照合装置において、入力された前記系列データに基づき自己類似度行列を計算する自己類似度行列計算部と、前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算する自己類似度行列整列部と、前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する適合位置・照合スコア決定部とを有することを特徴とする系列データ照合装置である。
【００１６】
また、本発明は、入力データを、この入力データの特徴を表す前記系列データに変換し、前記自己類似度行列計算部に出力する特徴ベクトル列計算部をさらに有することを特徴とする系列データ照合装置である。
【００１７】
また、本発明は、異なる系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合するコンピュータに、入力された前記系列データに基づき自己類似度行列を計算する自己類似度行列計算手段と、前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算する自己類似度行列整列手段と、前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する適合位置・照合スコア決定手段とを実行させるためのプログラムである。
【００１８】
また、本発明は、異なる系列データに基づき、自己類似度行列を算出し、動的計画法により前記自己類似度行列を照合するコンピュータに、入力された前記系列データに基づき自己類似度行列を計算する自己類似度行列計算手段と、前記自己類似度行列のうち互いに対応している適合要素の位置を表わす適合要素インデクスを用いて、一方の系列データの要素と、他方の系列データの要素とを対応付け、前記自己類似度行列に基づき動的計画法行列を計算する自己類似度行列整列手段と、前記動的計画法行列に基づき、前記系列データの対応関係において適合する部分を特定し、この適合する部分の位置を表わす照合スコアおよび適合位置を出力する適合位置・照合スコア決定手段とを実行させるためのプログラムを記憶した記憶媒体である。
【発明の効果】
【００１９】
本発明によれば、例えば同一の楽曲が異なる速度で演奏されている場合や、異なる調で演奏されている場合であっても、系列データの要素同士の類似度を表す行列（自己類似度行列）を用いて系列データの構造を表現し、動的計算法に基づき自己類似度行列を照合することにより、高い精度で類似する音楽を検索することができる。
【発明を実施するための最良の形態】
【００２０】
［第１の実施形態］
以下、図面を参照して、本発明の一実施形態について説明する。図１は、本発明の実施の形態の構成を示すブロック図である。なお、本実施の形態において、以下、系列データとして２本の楽曲の音響信号が入力される系列データ照合装置の構成と動作の一例について説明する。
図１に示すとおり、本実施の形態の系列データ照合装置は、特徴ベクトル列計算部１、自己類似度行列計算部２、自己類似度行列整列部３、適合位置・照合スコア決定部４を有する。この系列データ照合装置は、入力データＡ１，Ｂ１が入力され、この入力データＡ１，Ｂ１に基づく系列データＡ２，Ｂ２、自己類似度行列Ａ３，Ｂ３、ＤＰ行列Ｆを生成し、これらに基づき、２つの系列データ内の適合する位置（適合位置）と、照合スコアを生成する。自己類似度行列整列部３および適合位置・照合スコア決定部４は、動的計画法に基づく照合による整列を行う。
【００２１】
特徴ベクトル列計算部１は、入力された異なる２つの入力データＡ１，Ｂ１を、入力データＡ１，Ｂ１の特徴を表わす系列データ（ベクトル列）Ａ２，Ｂ２に変換する。ここで、系列データとは、例えば、図２に示すようなベクトル列や、図３に示すような文字列・記号列等を含むデータである。以下では、系列データが図２に示すようなベクトル列である場合を例に説明する。なお、図２に示すベクトルａ（ｉ）は、第ｉ番目のベクトルを表わし、そのｊ番目の要素はａｊ（ｉ）で表わす。
本実施の形態において、特徴ベクトル列計算部１は、図４に示すような特徴ベクトル列計算処理、すなわち、入力データＡ１，Ｂ１を、図２に示すようなベクトル列である系列データＡ２，Ｂ２に変換する処理を実行する。
図４に示すとおり、特徴ベクトル列計算部１は、入力データである音響信号が入力されると（Ｓ１）、この音響信号を短時間のフレームに分割する（Ｓ２）。特徴ベクトル列計算部１は、各フレーム内の音響信号サンプルの値からある定数の次元数を持つベクトルを作成する。すなわち、特徴ベクトル列計算部１は、各フレームにおけるベクトルの要素として、例えば、短時間フーリエ変換、帯域フィルタバンクの出力から計算されるスペクトルパワー値、ケプストラム解析、メル周波数ケプストラム分析、あるいはその他の解析方法等を用いて、系列データである特徴ベクトル列を算出し（Ｓ３）、出力する（Ｓ４）。特徴ベクトル列計算部１は、この特徴ベクトル列の算出を各フレーム対して行い、入力データＡ１，Ｂ１を系列データＡ２，Ｂ２に変換する。
【００２２】
自己類似度行列計算部２は、入力された異なる２つの系列データＡ２，Ｂ２に基づき、自己類似度行列Ａ３，Ｂ３を計算する。
上述のとおり、本実施の形態において、特徴ベクトル列計算部１に入力される入力データＡ１，Ｂ１は、図５に示すような音響信号であって、この音響信号は、特徴ベクトル列計算部１により図５に示す短時間のフレームごとの特徴ベクトル列（系列データ）ａ（ｉ）に変換される。
自己類似度行列計算部２は、この（ｉ，ｊ）のすべての組合せについてベクトルａ（ｉ）とベクトルａ（ｊ）の類似度の計算を行い、自己類似度行列Ａ３の（ｉ，ｊ）要素である自己類似度Ｒｉ，ｊを算出する。自己類似度行列計算部２は、例えば、下に示す式３の動径基底関数などを用いて、自己類似度Ｒｉ，ｊを計算することができる。なお、式３において、Ｃは定数である。
【数４】
2010039927.tif 000006
自己類似度行列計算部２は、同様にして、ベクトルｂ（ｉ）とベクトルｂ（ｊ）の類似度の計算を行い、自己類似度行列Ｂの（ｉ，ｊ）要素である自己類似度Ｓｉ，ｊを算出する。
なお、自己類似度行列計算部２は、上述の方法に限られず、例えば、ユークリッド距離など、ベクトル同士の類似度または距離を表す関数一般を用いて、自己類似度Ｒｉ，ｊ，Ｓｉ，ｊを計算するものであってもよい。
自己類似度行列計算部２は、このようにして計算された自己類似度Ｒｉ，ｊ，Ｓｉ，ｊに基づく自己類似度行列Ａ３，Ｂ３を出力する。なお、自己類似度行列Ａ３，Ｂ３は、対角線に対して対称となる対称行列である。
【００２３】
自己類似度行列整列部３は、入力された異なる２つの自己類似度行列Ａ３，Ｂ３に対して、整列のタイプに応じて設定されている初期値、更新式および適合要素インデックスを利用し、ＤＰ行列（動的計画法行列）Ｆを出力する。
詳細については後述するが、自己類似度行列整列部３は、対称行列である自己類似度行列Ａ３，Ｂ３に応じた更新式を用いてＤＰ行列Ｆを計算する。なお、この更新式および初期値は、整列のタイプに応じて予め選択され、自己類似度行列整列部３に設定されている。
また、自己類似度行列整列部３は、互いに対応付けられた適合要素の位置を示す適合要素インデクスを利用し、対応関係にないギャップ要素が排除された自己類似度Ｒｉ，ｊ，Ｓｉ，ｊに基づく要素照合スコアＭを用いる。
ここで、図１６，１７を用いた従来技術の説明においては、ＤＰ行列Ｆ´として（ｍ＋１）×（ｎ＋１）のサイズの行列を利用しているが、本発明では照合をａ（２）およびｂ（２）から行うため、ｍ×ｎのサイズを持つＤＰ行列Ｆを導入する。
つまり、自己類似度行列整列部３は、ｍ×ｎのサイズのＤＰ行列Ｆを導入し、上述の更新式に示されるＦの要素番号ｋおよびｌは、それぞれ１〜ｍ、１〜ｎの整数値を取るものとする。自己類似度行列整列部３は、このＤＰ行列Ｆの（ｋ，ｌ）要素であるＦ（ｋ，ｌ）を（ｍ，ｎ）まで、適合要素インデクスに基づく要素照合スコアＭを用いて対応付けを行い、Ｆ（ｍ，ｎ）まで対応付けさせた場合の最大照合スコアを算出する。
本実施の形態において、バックトラッキングは、大域整列、半大域整列の場合は（式６）を、局所整列の場合は（式７）を、逆算に用いて（Ａ）（Ｂ）（Ｃ）を再選択することで行われる。しかし、本発明はこれに限られず、自己類似度行列整列部３は、（式６）あるいは（式７）を用いた更新式による計算時の（Ａ）（Ｂ）（Ｃ）の選択の履歴を記憶しておくことで、バックトラッキングにおける再選択を省略する構成であってもよい。
【００２４】
適合位置・照合スコア決定部４は、入力されたＤＰ行列Ｆに基づき、２つの系列データＡ２，Ｂ２が適合する適合位置、および照合スコアを出力する。
つまり、適合位置・照合スコア決定部４は、整列のタイプに応じて、ＤＰ行列Ｆに基づき照合スコアを決定する。
大域整列の場合、Ｆ（ｍ，ｎ）の値を照合スコアとし、この照合スコアＦ（ｍ，ｎ）から後で説明する式６において選択された（Ａ）〜（Ｃ）の計算式に基づいて、Ｆ（１，１）に向かって遡っていくこと（バックトラッキング）により、自己類似度行列Ａ３と自己類似度行列Ｂ３との対応関係を特定する。例えば、Ｆ（ｋ、ｌ）の計算において、（Ａ）の計算式が選択された場合には、（ｋ−１，ｌ−１）に、（Ｂ）の計算式が選択された場合は（ｋ−１，ｌ）に、（Ｃ）の計算式が選択された場合は（ｋ，ｌ−１）に移動し、これを繰り返すことで最終的に（１，１）に到達する。この（ｍ，ｎ）から（１，１）に向かう経路において、（Ａ）の計算式が選択された場合の（ｉ，ｊ）それぞれについて、ベクトルａ（ｉ）とベクトルｂ（ｊ）を対応させることで、ベクトル列Ａ´，Ｂ´の整列を行う。
半大域整列の場合、ＤＰ行列Ｆのｍ行目の中で局所的に最大となるＦ（ｍ，ｊ）を照合スコアとし、この照合スコアＦ（ｍ，ｊ）を個々の出発点としてＦ（１，１）に向かって、大域整列の場合と同様のバックトラッキングによる整列を行う。
局所整列の場合、局所的に最大となるＦ（ｋ，ｌ）を照合スコアとし、この照合スコアＦ（ｋ，ｌ）を個々の出発点としてＦ（１，１）に向かって、大域整列、半大域整列の場合と同様のバックトラッキングによる整列を行う。Ｆ（ｋ，ｌ）の値が０となったところでバックトラッキングを終了する。
適合位置・照合スコア決定部４は、上述のようにバックトラッキングによる整列により、自己類似度行列Ａ３と自己類似度行列Ｂ３との対応関係を特定し、対応付けられた照合スコアと、自己類似度行列Ａ３，Ｂ３が適合する位置（ｋ，ｌ）とを、適合要素インデクスの示す位置に基づき決定し、適合位置として出力する。
【００２５】
次に、自己類似度行列整列部３について詳細に説明する。
図６，７を用いて、自己類似度行列整列部３の更新式を利用した整列について詳細に説明する。自己類似度行列整列部３は、図６に示すように、それぞれの自己類似度行列Ａ３，Ｂ３の対角線方向に連なる逆Ｌ字領域同士を対応付けて整列を行う。自己類似度行列Ａ３（Ｒ＝（ｒｉｊ））および自己類似度行列Ｂ３（Ｓ＝（ｓｉｊ））が、図７に示すように、要素照合スコアＭ（Ｑｋ，Ｄｌ）として下に示す式６，７の更新式に従って計算されることにより、ＤＰ行列Ｆが算出される。
より詳細に説明すると、図７に示す自己類似度行列Ａ３の斜線で表された逆Ｌ字領域は、自己類似度行列Ａ３の中で、系列データＡ２の第ｋ番目のフレームに関連する部分であり、自己類似度行列Ｂ３の斜線で表された逆Ｌ字領域は、自己類似度行列Ｂ３の中で、系列データＢ２の第ｌ番目のフレームに関連する部分である。
自己類似度行列Ａ３，Ｂ３は対称行列であるため、紙面において左下方または右上方の三角部分の値のみを考慮すればよく、上述の逆Ｌ字領域は、折り返し部分を境にして、一方の行あるいは列を利用する。以下（行列の左下三角部分）を用いる例について説明する。
また、対角要素は、同じフレーム同士の自己類似度であり、式３に示すような類似度尺度を用いた場合には、常に定数値となるため、本実施の形態において、対角要素について考慮する必要はない。
したがって、ＤＰ行列Ｆ（ｋ，ｌ）の第ｋフレームの対応付けには、自己類似度行列Ａ３の太枠で囲まれた斜線領域で示す自己類似度Ｑｋを用いる。この自己類似度Ｑｋに含まれる各要素は、下に示す式４で表される。
【数５】
2010039927.tif 000007
また、自己類似度行列Ｂ３についても同様、ＤＰ行列Ｆ（ｋ，ｌ）の第ｌフレームの対応付けには、自己類似度行列Ｂ３の太枠で囲まれた斜線領域で示す自己類似度Ｄｌを用いる。この自己類似度Ｄｌに含まれる各要素は、下に示す式５で表される。
【数６】
2010039927.tif 000008
自己類似度行列整列部３は、整列のタイプ（大域整列、半大域整列、局所整列）に応じた更新式（式６あるいは式７）に従い、上述の自己類似度Ｑｋ，Ｄｌに基づく要素照合スコアＭを用いて、隣接する３つの要素Ｆ（ｉ−１，ｊ），Ｆ（ｉ，ｊ−１），Ｆ（ｉ−１，ｊ−１）を繰り返し計算することにより、ＤＰ行列Ｆを算出する。
【数７】
2010039927.tif 000009
【数８】
2010039927.tif 000010
自己類似度行列整列部３は、大域整列、半大域整列の場合には、式６に従ってＤＰ行列Ｆを計算し、局所整列の場合には、式７に従ってＤＰ行列Ｆを計算する。なお、大域整列とは、照合させる２つの系列データのすべての要素を用いて整列を行うことをいい、半大域整列とは、一方の系列データのすべての要素と、他の系列データのうち一方の系列データに最も合致する要素を部分的に用いて整列を行うことをいい、局所整列とは、照合させる２つの系列データが、互いに最も合致する一部分を局所的に用いて整列を行うことをいう。
上述のＤＰ行列Ｆの計算において、自己類似度行列整列部３は、下に示す式８，式９，式１０から、整列のタイプに応じて設定されている初期条件を選択する。式８は、大域整列の場合の初期条件を、式９は半大域整列の場合の初期条件を、式１０は局所整列の場合の初期条件である。
【数９】
2010039927.tif 000011
【数１０】
2010039927.tif 000012
【数１１】
2010039927.tif 000013
このように、初期条件は、整列のタイプに応じてそれぞれ設けられている。これは、系列データが一部的に整合に用いられる場合、冒頭のギャップが無視されるためである。
【００２６】
また、図８を用いて、自己類似度行列整列部３の適合要素インデクスを利用した整列について詳細に説明する。自己類似度行列整列部３は、適合要素インデクスを用いて、ギャップ要素が排除された要素照合スコアに基づき、上述の更新式（式６あるいは式７）に従って照合を行う。
自己類似度Ｑｋ，Ｄｌは、概ね、図８に示すように適合要素（○記号で示す要素）と、ギャップ要素（−記号で示す要素）とを含む。ここで、ギャップ要素とは、動的計画法に基づく照合において除去される要素であって、図示するように、自己類似度Ｑｋ，Ｄｌの間において対応付けされない要素のことであり、適合要素とは、自己類似度Ｑｋ，Ｄｌの間において互いに対応付けされる要素のことである。
【００２７】
図８に示す例においては、自己類似度Ｄｌは、適合要素としてＳｌ３，Ｓｌ６，Ｓｌ７を、自己類似度Ｑｋは、適合要素としてｒｋ１，ｒｋ２，ｒｋ４を含み、これら適合要素は互いに対応している。なお、この適合要素は、図７に示すＤＰ行列ＦのＦ（１，１）からＦ（ｋ，ｌ）に向かう経路（太い折れ線で示す）においては、右下の要素に向かう線分の始端の要素、すなわちＦ（１，３）、Ｆ（２，６）、（Ｆ４，７）に対応している（図７に示すＤＰ行列Ｆの斜線部分）。
適合要素インデクスは、これら対応関係にある適合要素の位置を示し、自己類似度行列Ａ３に対応する自己類似度Ｑｋの適合要素インデクスはＩｑ（ｋ，ｌ）であり、自己類似度行列Ｂ３に対応する自己類似度Ｄｌの適合要素インデクスはＩｄ（ｋ，ｌ）である。図８に示す例において、自己類似度Ｑｋの適合要素インデクスはＩｑ（ｋ，ｌ）＝｛１，２，４｝、自己類似度Ｄｌの適合要素インデクスはＩｄ（ｋ，ｌ）＝｛３，６，７｝である。これにより、適合要素は、ＤＰ行列Ｆの各位置（ｋ，ｌ）によって異なるが、適合要素インデクスを利用することにより、ＤＰ行列Ｆの各位置（ｋ，ｌ）に対応した適合要素の位置を設定することができる。
【００２８】
自己類似度行列整列部３は、この適合要素インデクスを利用して、適合要素のみを含む自己類似度Ｑｋ，Ｄｌに基づく要素照合スコアＭ（Ｑｋ，Ｄｌ）を用いて、更新式に従い照合スコアを計算する。
なお、ＤＰ行列Ｆ内の位置（ｋ，ｌ）における（Ｑｋ，Ｄｌ）の適合要素で構成されるベクトルをそれぞれベクトルｑｋ（ｌ），ｄｌ（ｋ）とすると、次式が成立つ。
【数１２】
2010039927.tif 000014
適合要素インデクスは、自己類似度行列整列部３により、上述の更新式（式６あるいは式７）におけるＤＰ行列Ｆの計算を行う際に順次算出される。従って、適合要素インデクスとして、Ｉｑ（ｋ−１，ｌ−１），Ｉｑ（ｋ−１，ｌ），Ｉｑ（ｋ，ｌ−１），Ｉｄ（ｋ−１，ｌ−１），Ｉｄ（ｋ−１，ｌ），Ｉｄ（ｋ，ｌ−１）が与えられたときの適合要素インデクスＩｑ（ｋ，ｌ）およびＩｄ（ｋ，ｌ）は以下のような手順にて計算される。
まず、仮の適合要素インデクスＩｑ（ｋ，ｌ）およびＩｄ（ｋ，ｌ）を次式に従って計算する。
【数１３】
2010039927.tif 000015
次に、この式１２で求められるＩ´ｑ（ｋ，ｌ）およびＩ´ｄ（ｋ，ｌ）を、更新式に応じて置き換える。つまり、上述の更新式（式６または式７）において、それぞれ（Ａ）の更新式が選択された場合は、下に示す式１３に従って置き換えられた適合要素インデクスＩｑ（ｋ，ｌ）およびＩｄ（ｋ，ｌ）を用いる。
【数１４】
2010039927.tif 000016
また、上述の更新式（式６または式７）において、それぞれ（Ｂ）の更新式が選択された場合は、下に示す式１４に従って置き換えられた適合要素インデクスＩｑ（ｋ，ｌ）およびＩｄ（ｋ，ｌ）を用いる。
【数１５】
2010039927.tif 000017
同様にして、上述の更新式（式６または式７）において、それぞれ（Ｃ）の更新式が選択された場合は、下に示す式１５に従って置き換えられた適合要素インデクスＩｑ（ｋ，ｌ）およびＩｄ（ｋ，ｌ）を用いる。
【数１６】
2010039927.tif 000018
上述の更新式（式７）において、（Ｄ）の更新式が選ばれた場合は、下に示す式１６に従って置き換えられた適合要素インデクスＩｑ（ｋ，ｌ）およびＩｄ（ｋ，ｌ）を用いる。
【数１７】
2010039927.tif 000019
なお、初期条件としては、以下に示す空集合を用いる。
【数１８】
2010039927.tif 000020
ここで、上述方法により計算されるＤＰ行列Ｆ（ｋ，ｌ）は、（１，１）から（ｋ，ｌ）に至る動的計画法の経路に対応した最大の要素照合スコアを必ずしも示すとは限らないが、実用上の大きな問題はない。
また、上述のベクトルｑｋ（ｌ），ｄｌ（ｋ）は、互いに同じ次元数であって、図８における自己類似度Ｑｋ，Ｄｌの要素同士の対応関係に示されるように、各次元がそれぞれ対応している。このため、要素照合スコアＭ（Ｑｋ，Ｄｌ）としては、類似度尺度として一般に用いられるユークリッド距離、動径基底関数、内積、コサインなどに基づく尺度を用いることができる。例えば、自己類似度行列Ａ３，Ｂ３を計算する際に、式３を用いた場合、次式に示すような、要素ごとの差の絶対値の和に基づく尺度が有効である。
【数１９】
2010039927.tif 000021
なお、式１８において、ベクトルｑ，ｄは、ベクトルｑｋ（ｌ），ｄｌ（ｋ）を意味し、ベクトルｑｉ，ｄｉは、それぞれベクトルｑ，ｄの第ｉ要素を意味し、定数ａは、ベクトルｑ，ｄの次元数を意味している。
【００２９】
次に、図９におフローチャートを用いて、本実施の形態における系列データ照合装置ｊの系列データ照合方法の一例について説明する。
入力データＡ１，Ｂ１が系列データ照合装置に入力されると（Ｓ１１）、特徴ベクトル列計算部１は、入力データＡ１，Ｂ１の特徴を表わす系列データＡ２，Ｂ２に変換し、自己類似度行列計算部２に出力する。自己類似度行列計算部２は、入力された系列データＡ２，Ｂ２のそれぞれに基づき、例えば式３に従って自己類似度行列Ａ３，Ｂ３を算出し、自己類似度行列整列部３に出力する（Ｓ１２）。
自己類似度行列整列部３は、自己類似度行列Ａ３，Ｂ３が入力されると、整列のタイプに応じた初期値を、式８〜１０に示す初期値から選択するとともに、式１７に示す適合要素インデクスの初期値を初期条件として設定する（Ｓ１３）。
自己類似度行列整列部３は、所定のフレーム番号における自己類似度ごとに、整列のタイプに応じて予め選択されている式６あるいは式７に基づく更新式Ｆ（ｋ，ｌ）の計算を行うとともに（Ｓ１４）、式１２〜式１７を用いて適合要素インデクスの設定を行う（Ｓ１５）。
自己類似度行列整列部３は、このステップＳ１４，Ｓ１５の過程を、ｋ＝２，３，・・・，ｍ、ｌ＝２，３，・・・，ｎにおいて繰り返し計算することにより、ＤＰ行列Ｆを計算する。自己類似度行列整列部３は、計算したＤＰ行列Ｆを適合位置・照合スコア決定部４に出力する。
適合位置・照合スコア決定部４は、入力したＤＰ行列Ｆに基づき、最大照合スコアを決定し、整列タイプに応じたバックトラッキングによる整列を行う（Ｓ１６）。
適合位置・照合スコア決定部４は、ステップＳ１６の整列により対応付けられた、照合スコアと自己類似度行列Ａ３，Ｂ３とが適合する位置（ｋ，ｌ）を、適合要素インデクスの示す位置に基づき決定し、適合位置として出力するとともに、決定した照合スコアを出力する（Ｓ１７）。
【００３０】
なお、本実施の形態において、系列データ照合装置は、入力データＡ１，Ｂ１として入力される音響信号を特徴を表わす系列データに変換する必要があったため、図１に示す構成のものを例に説明したが、本発明はこれに限られず、図１０に示すように、系列データＡ２，Ｂ２を直接入力する構成であってもよい。この場合、上述した系列データ照合装置と、特徴ベクトル列計算部１を備えていない点が異なる。
【００３１】
［第２の実施形態］
本実施の形態は、前述の第１の実施形態と同様の構成を有し同様の動作をする系列データ照合装置に、入力データとして音響信号にかえてタンパク質などの線状に繋がった高分子化合物を入力された場合の一例について説明する。よって、構成の詳細な説明は、同じ符号を付すことで省略する。なお、本実施の形態における系列データ照合装置としては、図１０に示した系列データが直接入力される構成を想定して以下説明する。
【００３２】
図１１は、本実施の形態における自己類似度行列計算の概要を示した図である。
図１１に示すとおり、タンパク質は複数のアミノ酸がペプチド結合で繋がった高分子化合物であり、タンパク質内の各アミノ酸は残基と呼ばれ、ここではタンパク質内に７つの残基が存在する例を示す。
タンパク質の立体構造は、概ね、Ｘ線結晶解析などにより決定され、タンパク質内の各原子の３次元座標が求められる。なお、各残基の位置は、各残基内のＣαと呼ばれる炭素原子の座標で代表される場合もある。
これらすべての残基のペアについて、Ｃα間の距離を計算して得られる行列を距離マップといい、本実施の形態では、この距離マップを自己類似度行列として利用することで、２つのタンパク質の立体構造による整列を行い、照合スコアを算出することができる。
本実施の形態において、自己類似度行列計算部２は、タンパク質の残基を表わす系列データを、自己類似度行列として、各残基の距離のすべての組合せであるｄｉｊの行列に変換する。よって、図１１に示す７つの残基が存在するタンパク質の例において、図示のとおり、距離マップは７×７の行列で表わされる。
【００３３】
すなわち、本実施の形態における系列データ照合装置は、タンパク質の残基を表わす異なる２つの系列データが、系列データＡ２，Ｂ２として自己類似度行列計算部２に入力されると、自己類似度行列計算部２が、入力された系列データＡ２，Ｂ２のそれぞれを、距離マップを表す自己類似度行列Ａ３，Ｂ３に変換し、自己類似度行列整列部３に出力する。
以下、自己類似度行列Ａ３，Ｂ３に基づく整合、適合位置・照合スコアの決定・出力は、上述と同様であるため、詳細な説明は省略する。
【００３４】
［第３の実施形態］
次に、上述の第１，２の実施形態の応用例として、系列データＡ２の長さと系列データＢ２の長さとの差が大きい場合における系列データ照合方法について説明する。
図１２は、本実施の形態における自己類似度行列整列部３による自己類似度行列整列過程での自己類似度行列の分割の概略を示す。
系列データＢ２は、系列データＡ２に比べてＭ倍の長さを持ち、したがって、自己類似度行列Ｂ３は、自己類似度行列Ａ３に比べてＭの二乗倍の大きさを持つ。
自己類似度行列整列部３は、系列データＡ２，Ｂ２の差が所定の差分よりも大きい場合、長い方の系列データにおける自己類似度行列を分割する。図１２に示す例では、自己類似度行列Ｂ３は、一辺の長さがＮであり、自己類似度行列Ａ３に比べて十分長く、両者の差は所定の差分よりも大きい。自己類似度行列整列部３は、大きい方の自己類似度行列Ｂ３を、対角線方向に、一辺の長さがｎＳをもつ複数の行列（サブ行列）に分割する。このとき、自己類似度行列整列部３は、整列による適合位置がサブ行列の境界付近に存在する場合の検出精度を下げないように、隣り合うサブ行列は長さｎＯだけ重なり合うように分割する。
自己類似度行列整列部３は、自己類似度行列整列過程において、自己類似度行列Ａ３に対して、自己類似度行列Ｂ３が複数に分割された複数のサブ行列のそれぞれと対応付け、図７〜９を用いて上述したのと同様に、更新式の繰り返し計算により計算されたＤＰ行列Ｆを適合位置・照合スコア決定部４に出力する。
適合位置・照合スコア決定部４は、複数のサブ行列のそれぞれに対応付けられたＤＰ行列Ｆに基づき照合スコアを決定し、すべてのサブ行列を通じてもっとも照合スコアの高い位置からバックトラッキングを行う。適合位置・照合スコア決定部４は、この適合位置・照合スコア決定過程において得られた位置を、分割される前の元の自己類似度行列Ｂ３における位置に変換した適合位置として出力する。
【００３５】
本実施の形態のように、系列データの一方の長さが他方の系列データの長さに比べて長い場合、この長さの差により、自己類似度行列における領域の差も大きくなる。また、本発明は、図６に示すように逆Ｌ字領域同士を対応付けて整列を行うものであり、自己類似度行列整列部３による整列は、図６に示す行列の対角線方向に進む。このため、系列データの長さが長い方の自己類似度行列Ｂ３は、系列データの長さの短い方の自己類似度行列Ａ３に比べてサイズ（記憶領域）が大きく、対角線から外れた領域（図６に示す自己類似度行列Ｂ３の左下部分および右上部分）は整列にほとんど使われることがなく、非効率となっていた。
本実施の形態にかかる自己類似度行列整列部３は、自己類似度行列を分割されたサブ行列として用いることにより、系列データの長さの差が大きい場合であっても、自己類似度行列に利用するための記憶領域を効率よく利用することができる。
【００３６】
［第４の実施形態］
次に、図１３，１４を用いて、第１，３の実施形態で説明した系列データ照合装置および系列データ照合方法の応用例について説明する。
図１３に示すとおり、本実施の形態にかかる系列データ照合装置は、データベース作成処理部５と、データベース６と、探索処理部７とを有する。
データベース作成処理部５は、蓄積音楽信号および楽曲付随情報が入力され、蓄積音楽音響信号入力部５１と、蓄積自己類似度行列計算部５２と、楽曲付随情報入力部５３とを含み、入力される蓄積音楽信号と楽曲付随情報とを関連付ける固有のＩＤ番号を蓄積音楽信号および楽曲付随情報に付与する。
データベース６は、蓄積信号データベース６１と、蓄積自己類似度行列データベース６２と、楽曲付随情報データベース６３とを含み、データベース作成処理部５に入力された蓄積音楽信号および楽曲付随情報に関する情報を記憶し、探索処理部７から読み出し可能に接続されている。
探索処理部７は、参照音楽音響信号入力部７１と、参照自己類似度行列計算部７２と、自己類似度行列整列部７３と、適合位置・照合スコア決定部７４と、探索結果出力部７５とを含み、参照音楽信号が入力され、本発明にかかる系列データ照合方法を用いて参照音楽信号と蓄積音楽信号との照合を行う。
【００３７】
蓄積音楽音響信号入力部５１は、入力された蓄積音楽信号を、この蓄積音楽信号の特徴を表わす系列データに変換し、蓄積信号データベース６１に記憶するとともに、蓄積自己類似度行列計算部５２に出力する。なお、構成や動作は特徴ベクトル列計算部１と概ね同様であるため、詳細な説明は省略する。
蓄積自己類似度行列計算部５２は、蓄積音楽音響信号入力部５１から入力された系列データに基づき、自己類似度行列を計算し、蓄積自己類似度行列データベース６２に記憶する。また、蓄積自己類似度行列計算部５２は、照合対象である系列データが以前に蓄積音楽音響信号入力部により蓄積自己類似度行列データベースに記憶されている場合、蓄積信号データベース６１に記憶されている蓄積音楽信号に基づく系列データを読み出し、自己類似度行列に変換する。なお、構成や動作は自己類似度行列計算部２と概ね同様であるため、詳細な説明は省略する。
楽曲付随情報入力部５３は、入力された楽曲付随情報を種類ごとに区別して、楽曲付随情報データベース６３に記憶する。ここで、楽曲付随情報は、例えば、タイトル名、アーティスト名などのテキストデータや、レコードジャケット写真等の画像データ、プロモーションビデオなどの音響・映像データなどが利用可能である。
【００３８】
蓄積信号データベース６１は、蓄積音楽音響信号入力部５１から出力された蓄積音楽信号からなる系列データを記憶する。
蓄積自己類似度行列データベース６２は、蓄積自己類似度行列計算部５２により計算された自己類似度行列を記憶する。
楽曲付随情報データベース６３は、楽曲付随情報入力部５３から入力された楽曲付随情報を記憶する。
【００３９】
参照音楽音響信号入力部７１は、入力された参照音楽信号を、この参照音楽信号の特徴を表わす系列データに変換し、参照自己類似度行列計算部７２に出力する。なお、構成や動作は特徴ベクトル列計算部１と概ね同様であるため、詳細な説明は省略する。
参照自己類似度行列計算部７２は、参照音楽音響信号入力部７１から入力された系列データに基づき自己類似度行列を計算し、自己類似度行列整列部７３に出力する。なお、構成や動作は自己類似度行列計算部２と概ね同様であるため、詳細な説明は省略する。
自己類似度行列整列部７３は、参照自己類似度行列計算部７２から出力された自己類似度行列と、蓄積自己類似度行列データベース６２から読み出した自己類似度行列に対して、整列のタイプに応じて設定されている初期値、更新式および適合要素インデックスを利用し、動的計画法に基づく照合による整列を行い、ＤＰ（動的計画法）行列Ｆを出力する。なお、構成や動作は自己類似度行列整列部３と概ね同様であるため、詳細な説明は省略する。
適合位置・照合スコア決定部７４は、参照自己類似度行列整列部７３から入力されたＤＰ行列Ｆに基づき、参照音楽信号の系列データと、蓄積音楽信号の系列データが適合する適合位置、および照合スコアを出力する。なお、構成や動作は適合位置・照合スコア決定部４と概ね同様であるため、詳細な説明は省略する。
【００４０】
次に、図１４，１５を用いて、本実施の形態における系列データ照合方法について説明する。図１４は、データベース作成処理部５によるデータベース作成処理フローを示す概略図であり、図１５は、探索処理部７による探索処理フローを示す概略図である。
図１４に示すとおり、データベース作成処理部５に、楽曲単位に蓄積音楽信号が入力されると（Ｓ２１）、この蓄積音楽信号に楽曲付随情報があるか否かを検出する。楽曲付随情報がない場合、蓄積音楽音響信号入力部５１は、入力された蓄積音楽信号を系列データに変換し、蓄積信号データベース６１に登録するとともに、蓄積自己類似度行列計算部５２に出力する。蓄積自己類似度行列計算部５２は、入力された蓄積音楽信号の系列データに基づき自己類似度行列を計算し（Ｓ２２）、蓄積自己類似度行列データベース６２に登録する（Ｓ２３）
一方、蓄積音楽信号に楽曲付随情報がある場合、データベース作成処理部５は、蓄積音楽信号と楽曲付随情報とを関連付けるＩＤ番号をそれぞれに付与する。蓄積音楽音響信号入力部５１は、ＩＤ番号が付与された蓄積音楽信号を蓄積信号データベース６１に登録し、楽曲付随情報入力部５３は、ＩＤ番号が付与された楽曲付随情報を楽曲付随情報データベース６３に登録する（Ｓ２４）。
これにより、蓄積音楽信号の自己類似度行列と、この蓄積音楽信号と関連付けられた楽曲付随情報がデータベース６に記憶される。
【００４１】
図１５に示すとおり、探索処理部７に、参照音楽信号が入力されると（Ｓ３１）、参照音楽音響信号入力部７１によりこの参照音楽信号が系列データに変換され、参照自己類似度行列計算部７２に出力される。参照自己類似度行列計算部７２は、入力された系列データにもとづき自己類似度行列を計算し（Ｓ３２）、自己類似度行列整列部７３に出力する。
自己類似度行列整列部７３は、参照音楽信号の自己類似度行列と、蓄積自己類似度行列データベース６２内の各楽曲の自己類似度行列に対して、整列のタイプに応じて設定されている初期値、更新式および適合要素インデックスを利用し、動的計画法に基づく照合による整列を行い、ＤＰ（動的計画法）行列Ｆを出力する（Ｓ３３）。
適合位置・照合スコア決定部７４は、参照自己類似度行列整列部７３から入力されたＤＰ行列Ｆに基づき、参照音楽信号の系列データと、蓄積音楽信号の系列データが適合する適合位置、および照合スコアを決定し、照合スコアの高い自己類似度行列と、この自己類似度行列の行列内の位置を示す適合位置（蓄積音楽信号のＩＤ番号とフレーム番号を含む）を、探索結果出力部７５に出力する（Ｓ３４）。
探索結果出力部７５は、適合位置・照合スコア決定部７４から照合スコア（照合スコアの高い自己類似度行列）と適合位置（この自己類似度行列の行列内の位置を示す）を受け取り、自己類似度行列整列部７３により読み出し整列がなされた自己類似度行列に基づく蓄積音楽信号と関連付けられた楽曲付随情報が、楽曲付随情報データベース６３に記憶されているか否かを探索する。
探索結果出力部７５は、関連付けられた楽曲付随情報があった場合、適合位置および照合スコアとともに、楽曲付随情報を探索結果として出力する。一方、関連付けられた楽曲付随情報がなかった場合、探索結果出力部７５は、適合位置および照合スコアのみを探索結果として出力する（Ｓ３５）。
すなわち、自己類似度行列整列部７３，適合位置・照合スコア決定部７４および探索結果出力部７５は、図９を用いて説明したステップＳ１３での初期条件設定からステップＳ１７での照合スコア・適合位置の出力までの処理（Ａで示す部分）を上述の説明と同様に実施することができる。
なお、探索結果出力部７５は、関連付けられた楽曲付随情報を楽曲付随情報データベース６３から読み出し、探索された蓄積音楽信号の自己類似度行列の適合位置を、この適合位置を示すフレーム番号に該当する時刻とともに出力する構成であってもよい。
【００４２】
なお、上述の特徴ベクトル列計算部１、自己類似度行列計算部２、自己類似度行列整列部３、適合位置・照合スコア決定部４における、図９等を用いて説明したそれぞれの動作の過程は、コンピュータに実行させるためのプログラムや、このプログラムとしてコンピュータ読み取り可能な記録媒体として利用可能であり、コンピュータシステムが読み出して実行することによって、上記処理が行われる。なお、ここでいう「コンピュータシステム」とは、ＣＰＵ及び各種メモリやＯＳ、周辺機器等のハードウェアを含むものである。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００４３】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に記憶したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムに既に記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００４４】
【図１】本実施の形態の構成の一例を示すブロック図である。
【図２】本実施の形態にかかる系列データを説明するベクトル列の一例である。
【図３】本実施の形態にかかる系列データを説明する文字列の一例である。
【図４】本実施の形態にかかる特徴ベクトル列計算部のフローの一例を示す図である。
【図５】本実施の形態にかかる自己類似度行列計算部のフローの一例を示す図である。
【図６】本実施の形態にかかる自己類似度行列の整列による照合の概略図である。
【図７】本実施に形態にかかる自己類似度行列の整列を説明するための模式図である。
【図８】本実施の形態にかかる適合要素インデクスを説明するための図である。
【図９】本実施の形態にかかる自己類似度行列を用いた系列データの整列フローを説明する図である。
【図１０】本実施の形態にかかる他の構成の例を示すブロック図である。
【図１１】本実施の形態にかかるタンパク質の自己類似度行列の計算を説明するための図である。
【図１２】本実施の形態にかかる自己類似度行列の分割を説明するための図である。
【図１３】本発明にかかる他の実施形態を説明するための概略図である。
【図１４】本実施の形態にかかるデータベース作成処理のフローの一例を示す図である。
【図１５】本実施の形態にかかる探索処理のフローの一例を示す図である。
【図１６】従来例を説明する図である。
【図１７】従来例を説明する図である。
【符号の説明】
【００４５】
１  特徴ベクトル列計算部
２  自己類似度行列計算部
３  自己類似度行列整列部
４  適合要素インデクス
５  データベース作成処理部
６  データベース
７  探索処理部
５１  蓄積音楽音響信号入力部
５２  蓄積自己類似度行列計算部
５３  楽曲付随情報入力部
６１  蓄積信号データベース
６２  蓄積自己類似度行列データベース      
６３  楽曲付随情報データベース
７１  参照音楽音響信号入力部
７２  参照自己類似度行列計算部
７３  自己類似度行列整列部
７４  適合位置・照合スコア決定部
７５  探索結果出力部
【図１】
2010039927.tif 000022
【図２】
2010039927.tif 000023
【図３】
2010039927.tif 000024
【図４】
2010039927.tif 000025
【図５】
2010039927.tif 000026
【図６】
2010039927.tif 000027
【図７】
2010039927.tif 000028
【図８】
2010039927.tif 000029
【図９】
2010039927.tif 000030
【図１０】
2010039927.tif 000031
【図１１】
2010039927.tif 000032
【図１２】
2010039927.tif 000033
【図１３】
2010039927.tif 000034
【図１４】
2010039927.tif 000035
【図１５】
2010039927.tif 000036
【図１６】
2010039927.tif 000037
【図１７】
2010039927.tif 000038