JP2003108187A - 類似性評価方法及び類似性評価プログラム - Google Patents
類似性評価方法及び類似性評価プログラムInfo
- Publication number
- JP2003108187A JP2003108187A JP2001299218A JP2001299218A JP2003108187A JP 2003108187 A JP2003108187 A JP 2003108187A JP 2001299218 A JP2001299218 A JP 2001299218A JP 2001299218 A JP2001299218 A JP 2001299218A JP 2003108187 A JP2003108187 A JP 2003108187A
- Authority
- JP
- Japan
- Prior art keywords
- probability
- similarity
- information
- types
- evaluation
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/18—Complex mathematical operations for evaluating statistical data, e.g. average values, frequency distributions, probability functions, regression analysis
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Data Mining & Analysis (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Life Sciences & Earth Sciences (AREA)
- Operations Research (AREA)
- Probability & Statistics with Applications (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Algebra (AREA)
- Evolutionary Biology (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- General Engineering & Computer Science (AREA)
- Bioinformatics & Computational Biology (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Complex Calculations (AREA)
Abstract
(57)【要約】
【課題】 確率モデル間の類似性を高速に（少ない計算
量で）判定することが出来る類似性評価プログラムを、
提供する。 【解決手段】 コンピュータを、複数種類の確率データ
からなる確率情報を複数個含む確率モデル情報間の類似
性を評価するための装置であって、類似性を評価すべき
２つの確率モデル情報の中の一方の確率モデル情報に含
まれる確率情報と他方の確率モデル情報に含まれる確率
情報との間の類似性を示す類似値を、経路の選択のため
の指標として用いたダイナミック・プログラミング法に
基づく演算処理を行なうダイナミック・プログラミング
処理部２３を備える類似性評価装置２０として動作させ
ることが出来るように、類似性評価プログラムを作成し
ておく。
量で）判定することが出来る類似性評価プログラムを、
提供する。 【解決手段】 コンピュータを、複数種類の確率データ
からなる確率情報を複数個含む確率モデル情報間の類似
性を評価するための装置であって、類似性を評価すべき
２つの確率モデル情報の中の一方の確率モデル情報に含
まれる確率情報と他方の確率モデル情報に含まれる確率
情報との間の類似性を示す類似値を、経路の選択のため
の指標として用いたダイナミック・プログラミング法に
基づく演算処理を行なうダイナミック・プログラミング
処理部２３を備える類似性評価装置２０として動作させ
ることが出来るように、類似性評価プログラムを作成し
ておく。
Description
【０００１】
【発明の属する技術分野】本発明は、確率モデル間の類
似性を判定するための類似性評価方法及び類似性評価プ
ログラムに、関する。
似性を判定するための類似性評価方法及び類似性評価プ
ログラムに、関する。
【０００２】
【従来の技術】音声認識やバイオインフォマティクスと
いった分野では、発生パターンやホモロジーグループを
数学的に表すために確率モデル（主に、隠れマルコフモ
デル）が使用されている。確率モデルは、主として、或
る発生パターンがどの単語を発生したものであるかや、
或る配列が、どのホモロジーグループに属するものであ
るかを求めるために使用されるものであるが、確率モデ
ル間の類似性を評価したい場合もある。このため、類似
性の評価法の研究も盛んに行なわれており、例えば、以
下に記すｅｑ．１〜ｅｑ．３を用いて、確率モデル間の
類似性の評価が試みられている。
いった分野では、発生パターンやホモロジーグループを
数学的に表すために確率モデル（主に、隠れマルコフモ
デル）が使用されている。確率モデルは、主として、或
る発生パターンがどの単語を発生したものであるかや、
或る配列が、どのホモロジーグループに属するものであ
るかを求めるために使用されるものであるが、確率モデ
ル間の類似性を評価したい場合もある。このため、類似
性の評価法の研究も盛んに行なわれており、例えば、以
下に記すｅｑ．１〜ｅｑ．３を用いて、確率モデル間の
類似性の評価が試みられている。
【０００３】
【数１】
【０００４】なお、ｅｑ．１〜ｅｑ．３にて算出されて
いる値は、それぞれ、相対エントロピー（kulleback-Li
eber Distance）、相互情報量（mutual informatio
n）、同時発生確率（co-emmision propability）と呼ば
れているものである。
いる値は、それぞれ、相対エントロピー（kulleback-Li
eber Distance）、相互情報量（mutual informatio
n）、同時発生確率（co-emmision propability）と呼ば
れているものである。
【０００５】
【発明が解決しようとする課題】上記した各式は、確率
論的に良く定義されたものであるので、いずれかの式を
用いれば、確率モデル間の類似性の評価を正確に行なう
ことが出来ることになる。しかしながら、いずれの式を
用いて確率モデル間の類似性の評価を行なう場合にも、
膨大な量の計算が必要となるため、上記のような式によ
る確率モデル間の類似性の評価を、音声認識用の確率モ
デルに対して実施することは可能であるが、配列長が１
０００程度になることがあるタンパク質に関する確率モ
デルに対して実施することは実際上不可能であった。
論的に良く定義されたものであるので、いずれかの式を
用いれば、確率モデル間の類似性の評価を正確に行なう
ことが出来ることになる。しかしながら、いずれの式を
用いて確率モデル間の類似性の評価を行なう場合にも、
膨大な量の計算が必要となるため、上記のような式によ
る確率モデル間の類似性の評価を、音声認識用の確率モ
デルに対して実施することは可能であるが、配列長が１
０００程度になることがあるタンパク質に関する確率モ
デルに対して実施することは実際上不可能であった。
【０００６】そこで、本発明の課題は、確率モデル間の
類似性を高速に（少ない計算量で）判定することが出来
る類似性評価方法と、そのような類似性評価方法による
確率モデル間の類似性判定をコンピュータに行なわせる
ことが出来る類似性評価プログラムとを、提供すること
にある。
類似性を高速に（少ない計算量で）判定することが出来
る類似性評価方法と、そのような類似性評価方法による
確率モデル間の類似性判定をコンピュータに行なわせる
ことが出来る類似性評価プログラムとを、提供すること
にある。
【０００７】
【課題を解決するための手段】上記課題を解決するため
に、本発明の類似性評価方法では、複数種類の確率デー
タからなる確率情報を複数個含む確率モデル情報間の類
似性を評価するに際して、類似性を評価すべき２つの確
率モデル情報のうちの一方の確率モデル情報に含まれる
確率情報と他方の確率モデル情報に含まれる確率情報と
の間の類似性を示す類似値が、経路の選択のための指標
値として用いられて、ダイナミック・プログラミング法
に基づく演算処理が行なわれるステップ構成が、採用さ
れる。
に、本発明の類似性評価方法では、複数種類の確率デー
タからなる確率情報を複数個含む確率モデル情報間の類
似性を評価するに際して、類似性を評価すべき２つの確
率モデル情報のうちの一方の確率モデル情報に含まれる
確率情報と他方の確率モデル情報に含まれる確率情報と
の間の類似性を示す類似値が、経路の選択のための指標
値として用いられて、ダイナミック・プログラミング法
に基づく演算処理が行なわれるステップ構成が、採用さ
れる。
【０００８】このような構成の本発明の類似性評価方法
によれば、高速に完了するダイナミック・プログラミン
グ法に基づく演算処理にて、確率モデル情報間の類似性
の評価が行なえることになるので、確率モデル情報間の
類似性の評価を短時間で行なえることになる。
によれば、高速に完了するダイナミック・プログラミン
グ法に基づく演算処理にて、確率モデル情報間の類似性
の評価が行なえることになるので、確率モデル情報間の
類似性の評価を短時間で行なえることになる。
【０００９】なお、本発明の類似性評価方法を実現する
に際しては、評価対象とする確率モデル情報を、隠れマ
ルコフモデルに関する確率モデル情報とすることができ
る。そして、その場合には、類似値が、２つの確率情報
のうちの一方の確率情報に含まれる複数種類の出力確率
データと、他方の確率情報に含まれる複数種類の出力確
率データとに基づき、算出されるようにすることが出来
る。
に際しては、評価対象とする確率モデル情報を、隠れマ
ルコフモデルに関する確率モデル情報とすることができ
る。そして、その場合には、類似値が、２つの確率情報
のうちの一方の確率情報に含まれる複数種類の出力確率
データと、他方の確率情報に含まれる複数種類の出力確
率データとに基づき、算出されるようにすることが出来
る。
【００１０】また、類似値が、２つの確率情報のうちの
一方の確率情報に含まれる複数種類の出力確率データ及
び複数種類の遷移確率データと、他方の確率情報に含ま
れる複数種類の出力確率データと複数種類の遷移確率デ
ータとに基づき、算出されるように、例えば、類似値
が、一方の確率情報に含まれる複数種類の出力確率デー
タからなる出力確率ベクトルと他方の確率情報に含まれ
る複数種類の出力確率データからなる出力確率ベクトル
とがなす角度の余弦値の二乗値に、一方の確率情報に含
まれる複数種類の遷移確率データからなる遷移確率ベク
トルと他方の確率情報に含まれる複数種類の遷移確率デ
ータからなる遷移確率ベクトルとがなす角度の余弦値の
二乗値を乗じた結果とされるように、することが出来
る。そして、本発明の類似性評価方法、類似性評価装置
を、遷移確率データが考慮されて類似値が算出されるも
のとしておいた場合には、Ｉノード、Ｄノードの存在を
考慮した形で、隠れマルコフモデルに関する確率モデル
情報間の類似性を評価できる方法を実現できることにな
る。
一方の確率情報に含まれる複数種類の出力確率データ及
び複数種類の遷移確率データと、他方の確率情報に含ま
れる複数種類の出力確率データと複数種類の遷移確率デ
ータとに基づき、算出されるように、例えば、類似値
が、一方の確率情報に含まれる複数種類の出力確率デー
タからなる出力確率ベクトルと他方の確率情報に含まれ
る複数種類の出力確率データからなる出力確率ベクトル
とがなす角度の余弦値の二乗値に、一方の確率情報に含
まれる複数種類の遷移確率データからなる遷移確率ベク
トルと他方の確率情報に含まれる複数種類の遷移確率デ
ータからなる遷移確率ベクトルとがなす角度の余弦値の
二乗値を乗じた結果とされるように、することが出来
る。そして、本発明の類似性評価方法、類似性評価装置
を、遷移確率データが考慮されて類似値が算出されるも
のとしておいた場合には、Ｉノード、Ｄノードの存在を
考慮した形で、隠れマルコフモデルに関する確率モデル
情報間の類似性を評価できる方法を実現できることにな
る。
【００１１】一方、本発明の類似性評価プログラムは、
コンピュータに、本発明の類似性評価方法による類似性
評価を実行させることが出来るように作成される。従っ
て、本発明の類似性評価プログラムを用いれば、コンピ
ュータに、確率モデル情報間の類似性の評価を短時間で
行なわせることが出来ることになる。
コンピュータに、本発明の類似性評価方法による類似性
評価を実行させることが出来るように作成される。従っ
て、本発明の類似性評価プログラムを用いれば、コンピ
ュータに、確率モデル情報間の類似性の評価を短時間で
行なわせることが出来ることになる。
【００１２】
【発明の実施の形態】以下、本発明の実施の形態を、図
面を参照して詳細に説明する。
面を参照して詳細に説明する。
【００１３】図１に、本発明の一実施形態に係る類似性
評価装置１０の機能ブロック図を示す。
評価装置１０の機能ブロック図を示す。
【００１４】図示したように、類似性評価装置１０は、
確率モデル情報取得部２１、確率モデル情報記憶部２
２、ダイナミック・プログラミング処理部２３、評価結
果記憶部２４及び評価結果提示処理部２５を、備える。
確率モデル情報取得部２１、確率モデル情報記憶部２
２、ダイナミック・プログラミング処理部２３、評価結
果記憶部２４及び評価結果提示処理部２５を、備える。
【００１５】確率モデル情報記憶部２２は、類似性が評
価されるべき２つの確率モデル（本実施形態では、プロ
ファイルＨＭＭ〔hidden Markov model；隠れマルコフ
モデル〕）の定義情報（以下、確率モデル情報と表記す
る）を一時記憶するためのユニットである。確率モデル
情報取得部２１は、操作者が指定したファイル内の確率
モデル情報、或いは、操作者が入力した確率モデル情報
を、確率モデル情報記憶部２２に記憶するユニットであ
る。この確率モデル情報取得部２１は、操作者から、確
率モデル間の類似性の評価を第１〜第３評価モード（詳
細は後述）のいずれで行なうかについての指示も取得す
る。
価されるべき２つの確率モデル（本実施形態では、プロ
ファイルＨＭＭ〔hidden Markov model；隠れマルコフ
モデル〕）の定義情報（以下、確率モデル情報と表記す
る）を一時記憶するためのユニットである。確率モデル
情報取得部２１は、操作者が指定したファイル内の確率
モデル情報、或いは、操作者が入力した確率モデル情報
を、確率モデル情報記憶部２２に記憶するユニットであ
る。この確率モデル情報取得部２１は、操作者から、確
率モデル間の類似性の評価を第１〜第３評価モード（詳
細は後述）のいずれで行なうかについての指示も取得す
る。
【００１６】ダイナミック・プログラミング処理部２３
は、確率モデル情報記憶部２２に記憶されている２つの
確率モデル情報に基づき、確率モデルの類似性を評価す
るための演算処理を操作者が指定した評価モードで行な
うユニットである。詳細は後述するが、このダイナミッ
ク・プログラミング処理部２３が実行する演算処理は、
ペアワイズ・アライメントのために従来より行なわれて
いるダイナミック・プログラミング法による演算処理
を、変形したものとなっている。
は、確率モデル情報記憶部２２に記憶されている２つの
確率モデル情報に基づき、確率モデルの類似性を評価す
るための演算処理を操作者が指定した評価モードで行な
うユニットである。詳細は後述するが、このダイナミッ
ク・プログラミング処理部２３が実行する演算処理は、
ペアワイズ・アライメントのために従来より行なわれて
いるダイナミック・プログラミング法による演算処理
を、変形したものとなっている。
【００１７】評価結果記憶部２４は、ダイナミック・プ
ログラミング処理部２３による最終的な演算結果が記憶
されるユニットである。評価結果提示処理部２５は、評
価結果記憶部２４に記憶された情報（演算結果）に基づ
き、操作者に評価結果を提示する処理（評価結果を表示
する処理、評価結果をプリンタに印刷させるためのデー
タを出力する処理）を、行なうユニットである。
ログラミング処理部２３による最終的な演算結果が記憶
されるユニットである。評価結果提示処理部２５は、評
価結果記憶部２４に記憶された情報（演算結果）に基づ
き、操作者に評価結果を提示する処理（評価結果を表示
する処理、評価結果をプリンタに印刷させるためのデー
タを出力する処理）を、行なうユニットである。
【００１８】なお、本実施形態に係る類似性評価装置１
０は、比較的に高機能なコンピュータに、類似性評価プ
ログラムをインストールすることによって実現した装置
となっており、確率モデル情報記憶部２２、評価結果記
憶部２４は、それぞれ、当該コンピュータに備えられた
ＲＡＭ、ハードディスクに相当している。また、確率モ
デル情報取得部２１、ダイナミック・プログラミング処
理部２３及び評価結果提示処理部２５は、それぞれ、類
似性評価プログラムの特定の部分が実行されいる状態に
おける当該コンピュータ（ＣＰＵを中心とした部分）に
相当している。
０は、比較的に高機能なコンピュータに、類似性評価プ
ログラムをインストールすることによって実現した装置
となっており、確率モデル情報記憶部２２、評価結果記
憶部２４は、それぞれ、当該コンピュータに備えられた
ＲＡＭ、ハードディスクに相当している。また、確率モ
デル情報取得部２１、ダイナミック・プログラミング処
理部２３及び評価結果提示処理部２５は、それぞれ、類
似性評価プログラムの特定の部分が実行されいる状態に
おける当該コンピュータ（ＣＰＵを中心とした部分）に
相当している。
【００１９】以上のことを前提に、以下、本類似性評価
装置１０の動作を具体的に説明する。
装置１０の動作を具体的に説明する。
【００２０】まず、本類似性評価装置１０を用いて類似
性の評価が行なえる確率モデルであるプロファイルＨＭ
Ｍの概要を、説明する。
性の評価が行なえる確率モデルであるプロファイルＨＭ
Ｍの概要を、説明する。
【００２１】プロファイルＨＭＭは、塩基配列やアミノ
酸配列などを表すＨＭＭであり、図２に例示したよう
に、遷移確率（図では、矢印）を介して関連づけられた
Ｍノード、Ｉノード、Ｄノード、Ｓノード及びＥノード
からなる。
酸配列などを表すＨＭＭであり、図２に例示したよう
に、遷移確率（図では、矢印）を介して関連づけられた
Ｍノード、Ｉノード、Ｄノード、Ｓノード及びＥノード
からなる。
【００２２】プロファイルＨＭＭを構成するＭノード及
びＩノードは、いずれも、配列（配列アライメント）の
或る要素の状態を表すノードであり、Ｍノードには、記
号の出力確率（塩基配列を表すＨＭＭでは、Ａ、Ｇ、
Ｃ、Ｔといった４種の記号についての４種の出力確率、
アミノ酸配列を表すＨＭＭでは、２０種の出力確率）
と、幾つかの他ノード（Ｍノード、Ｉノード及びＤノー
ド）への遷移確率とが、対応づけられている。また、Ｉ
ノードには、Ｍノードと同様に、複数の記号の出力確率
と幾つかの遷移確率とが対応づけられている。ただし、
Ｉノードには、他Ｉノードへの遷移確率ではなく自Ｉノ
ードへの遷移確率が対応づけられている。
びＩノードは、いずれも、配列（配列アライメント）の
或る要素の状態を表すノードであり、Ｍノードには、記
号の出力確率（塩基配列を表すＨＭＭでは、Ａ、Ｇ、
Ｃ、Ｔといった４種の記号についての４種の出力確率、
アミノ酸配列を表すＨＭＭでは、２０種の出力確率）
と、幾つかの他ノード（Ｍノード、Ｉノード及びＤノー
ド）への遷移確率とが、対応づけられている。また、Ｉ
ノードには、Ｍノードと同様に、複数の記号の出力確率
と幾つかの遷移確率とが対応づけられている。ただし、
Ｉノードには、他Ｉノードへの遷移確率ではなく自Ｉノ
ードへの遷移確率が対応づけられている。
【００２３】一方、Ｄノードは、出力確率が対応づけら
れていいないダミーノードである。Ｄノードには、幾つ
かのノードへの遷移確率のみが対応づけられている。Ｓ
ノードは、このプロファイルＨＭＭの初期状態を表すノ
ードであり、Ｓノードには、幾つかの他ノードへの遷移
確率のみが対応づけられている。また、Ｅノードは、こ
のプロファイルＨＭＭの初期状態を表すノードであり、
Ｅノードには、出力確率のみが対応づけられている。
れていいないダミーノードである。Ｄノードには、幾つ
かのノードへの遷移確率のみが対応づけられている。Ｓ
ノードは、このプロファイルＨＭＭの初期状態を表すノ
ードであり、Ｓノードには、幾つかの他ノードへの遷移
確率のみが対応づけられている。また、Ｅノードは、こ
のプロファイルＨＭＭの初期状態を表すノードであり、
Ｅノードには、出力確率のみが対応づけられている。
【００２４】次に、ペアワイズ・アライメントのために
従来より行なわれているダイナミック・プログラミング
法による演算処理の説明（換言すれば、ダイナミック・
プログラミング処理部２３の動作原理の説明）を、行な
う。
従来より行なわれているダイナミック・プログラミング
法による演算処理の説明（換言すれば、ダイナミック・
プログラミング処理部２３の動作原理の説明）を、行な
う。
【００２５】ペアワイズ・アライメントとは、簡単に言
えば、与えられた２つの配列の適当な場所にギャップを
入れることにより、要素の並び方が最も類似した２つの
配列を得る操作（処理）のことである。
えば、与えられた２つの配列の適当な場所にギャップを
入れることにより、要素の並び方が最も類似した２つの
配列を得る操作（処理）のことである。
【００２６】以下、“ＡＩＭＳ”及び“ＡＭＯＳ”とい
う２つの配列（文字列）に対してペアワイズ・アライメ
ントが行なわれる場合を例に、ダイナミック・プログラ
ミング法によるペアワイズ・アライメントの概要を、説
明する。
う２つの配列（文字列）に対してペアワイズ・アライメ
ントが行なわれる場合を例に、ダイナミック・プログラ
ミング法によるペアワイズ・アライメントの概要を、説
明する。
【００２７】この場合、図３に模式的に示したような、
５×５のノード（白丸）を含み、縦方向に並んだノード
群には、アライメントを求めるべき一方の配列（以下、
第１配列と表記する；図では、“ＡＩＭＳ”）の特定の
要素が対応づけられ、横方向に並んだノードには、アラ
イメントを求めるべき２配列の他方の配列（以下、第２
配列と表記する；図では、“ＡＭＯＳ”）の特定の要素
が対応づけられているマトリックスの存在が、想定され
る。
５×５のノード（白丸）を含み、縦方向に並んだノード
群には、アライメントを求めるべき一方の配列（以下、
第１配列と表記する；図では、“ＡＩＭＳ”）の特定の
要素が対応づけられ、横方向に並んだノードには、アラ
イメントを求めるべき２配列の他方の配列（以下、第２
配列と表記する；図では、“ＡＭＯＳ”）の特定の要素
が対応づけられているマトリックスの存在が、想定され
る。
【００２８】そして、ダイナミック・プログラミング法
によってペアワイズ・アライメントを求める際には、こ
のマトリックスの左上端のノードから右下端のノードま
での、矢印に従った各移動経路が、１つのアライメント
（２配列に関する１つの調整結果）として解釈される。
具体的には、右方向矢印に従った移動は、第１配列に関
しては、移動後のノードに対応づけられている要素（文
字）を調整結果の要素として出力する操作と解釈され、
第２配列に関しては、ギャップを調整結果の要素として
出力する操作と解釈される。また、斜め方向矢印に従っ
た移動は、第１配列、第２配列の双方に関して、移動後
のノードに対応づけられている要素（文字）を調整結果
の要素として出力する操作と解釈される。そして、下方
向矢印に従った移動は、第１配列に関しては、ギャップ
を調整結果の要素として出力する操作と解釈され、第２
配列に関しては、移動後のノードに対応づけられている
要素（文字）を調整結果の要素として出力する操作と解
釈される。
によってペアワイズ・アライメントを求める際には、こ
のマトリックスの左上端のノードから右下端のノードま
での、矢印に従った各移動経路が、１つのアライメント
（２配列に関する１つの調整結果）として解釈される。
具体的には、右方向矢印に従った移動は、第１配列に関
しては、移動後のノードに対応づけられている要素（文
字）を調整結果の要素として出力する操作と解釈され、
第２配列に関しては、ギャップを調整結果の要素として
出力する操作と解釈される。また、斜め方向矢印に従っ
た移動は、第１配列、第２配列の双方に関して、移動後
のノードに対応づけられている要素（文字）を調整結果
の要素として出力する操作と解釈される。そして、下方
向矢印に従った移動は、第１配列に関しては、ギャップ
を調整結果の要素として出力する操作と解釈され、第２
配列に関しては、移動後のノードに対応づけられている
要素（文字）を調整結果の要素として出力する操作と解
釈される。
【００２９】すなわち、図中、点線矢印で示された経路
は、“−ＡＩＭＳ”及び“ＡＭＯＳ−”を示すものとし
て解釈され、太線矢印で示された経路は、“ＡＩＭ−
Ｓ”及び“Ａ−ＭＯＳ”を示すものとして解釈される。
は、“−ＡＩＭＳ”及び“ＡＭＯＳ−”を示すものとし
て解釈され、太線矢印で示された経路は、“ＡＩＭ−
Ｓ”及び“Ａ−ＭＯＳ”を示すものとして解釈される。
【００３０】このマトリックスが表し得る全ての調整結
果の中から最も類似したものを見出せば、最適アライメ
ントが得られる訳であるが、全ての調整結果について、
調整後の２配列がどの程度類似しているかを評価してい
たのでは、目的とするアライメントを得るために時間が
かかることになる。この時間を短縮するために用いられ
ているのがダイナミック・プログラミング法（小さな問
題の最適解を求め,その最適解を拡大しながら次第に大
きな問題の解を求める方法）であり、ダイナミック・プ
ログラミング法によってペアワイズ・アライメントを求
める際には、以下に記す（１）式（ｉ，ｊに関する漸化
式）が用いられている。
果の中から最も類似したものを見出せば、最適アライメ
ントが得られる訳であるが、全ての調整結果について、
調整後の２配列がどの程度類似しているかを評価してい
たのでは、目的とするアライメントを得るために時間が
かかることになる。この時間を短縮するために用いられ
ているのがダイナミック・プログラミング法（小さな問
題の最適解を求め,その最適解を拡大しながら次第に大
きな問題の解を求める方法）であり、ダイナミック・プ
ログラミング法によってペアワイズ・アライメントを求
める際には、以下に記す（１）式（ｉ，ｊに関する漸化
式）が用いられている。
【００３１】
【数２】
【００３２】この（１）式において、Ｖi,jは、第１配
列の要素＃ｉと第２配列の要素＃ｊとに対応づけられた
ノードまでの経路に対する評価点（評価値）であり、ｄ
は、ギャップペナルティ或いはギャップコストと呼ばれ
る対応要素の欠失に対する評価点である。また、ｗi,j
は、第１配列の要素＃ｉと第２配列の要素＃ｊとの類似
性に関する評価点である。なお、このｗi,jとしては、
塩基配列を対象とする場合には、両要素が一致している
か否かに応じた値（予め用意された２値のうちのいずれ
か）が用いられており、アミノ酸配列を対象とする場合
には、２つのアミノ酸の各組み合わせに対するｗ値を保
持したテーブルから読み出した値が、用いられている。
列の要素＃ｉと第２配列の要素＃ｊとに対応づけられた
ノードまでの経路に対する評価点（評価値）であり、ｄ
は、ギャップペナルティ或いはギャップコストと呼ばれ
る対応要素の欠失に対する評価点である。また、ｗi,j
は、第１配列の要素＃ｉと第２配列の要素＃ｊとの類似
性に関する評価点である。なお、このｗi,jとしては、
塩基配列を対象とする場合には、両要素が一致している
か否かに応じた値（予め用意された２値のうちのいずれ
か）が用いられており、アミノ酸配列を対象とする場合
には、２つのアミノ酸の各組み合わせに対するｗ値を保
持したテーブルから読み出した値が、用いられている。
【００３３】そして、ダイナミック・プログラミング法
にてペアワイズ・アライメントを求める際には、この
（１）式による計算が、ｉ，ｊを増加させながら各ノー
ドについて行なわれる。また、その際、どの経路（複数
のこともあり得る）をたどった場合に最適であったかが
記憶され、全ての演算が完了した後、右下端から最適経
路を逆向きにたどる（トレースバックする）ことにより
最適アライメントが求められている。
にてペアワイズ・アライメントを求める際には、この
（１）式による計算が、ｉ，ｊを増加させながら各ノー
ドについて行なわれる。また、その際、どの経路（複数
のこともあり得る）をたどった場合に最適であったかが
記憶され、全ての演算が完了した後、右下端から最適経
路を逆向きにたどる（トレースバックする）ことにより
最適アライメントが求められている。
【００３４】要するに、ダイナミック・プログラミング
法によってペアワイズ・アライメントを求める際には、
１つのノードについてＶ値の計算を行う度に、最終的な
評価点（調整後の２配列の評価点）の算出を行わない経
路が増えていく（max関数により、そのノードに至るこ
とが出来る３種の経路の中の２個の経路が、最終的な評
価点の算出を行わない経路とされてしまう）手順の処理
（換言すれば、少ない計算量で目的とする結果が得られ
る処理）が行なわれるので、ダイナミック・プログラミ
ング法によるペアワイズ・アライメントは、高速に完了
するのである。
法によってペアワイズ・アライメントを求める際には、
１つのノードについてＶ値の計算を行う度に、最終的な
評価点（調整後の２配列の評価点）の算出を行わない経
路が増えていく（max関数により、そのノードに至るこ
とが出来る３種の経路の中の２個の経路が、最終的な評
価点の算出を行わない経路とされてしまう）手順の処理
（換言すれば、少ない計算量で目的とする結果が得られ
る処理）が行なわれるので、ダイナミック・プログラミ
ング法によるペアワイズ・アライメントは、高速に完了
するのである。
【００３５】次に、類似性評価装置１０のダイナミック
・プログラミング処理部２３及び判定結果提示部２５の
動作を、説明する。
・プログラミング処理部２３及び判定結果提示部２５の
動作を、説明する。
【００３６】ダイナミック・プログラミング処理部２３
は、ペアワイズ・アライメントを求めるために行なわれ
ている上記した処理と同一原理の処理を、プロファイル
ＨＭＭに対して行なうものとなっている。また、ダイナ
ミック・プログラミング処理部２３は、上述したよう
に、３つの評価モードを有するものとなっている。
は、ペアワイズ・アライメントを求めるために行なわれ
ている上記した処理と同一原理の処理を、プロファイル
ＨＭＭに対して行なうものとなっている。また、ダイナ
ミック・プログラミング処理部２３は、上述したよう
に、３つの評価モードを有するものとなっている。
【００３７】このため、まず、従来の処理手順と異なる
部分を中心に、第１評価モードでの第１ダイナミック・
プログラミング処理部２３の動作を、説明することにす
る。
部分を中心に、第１評価モードでの第１ダイナミック・
プログラミング処理部２３の動作を、説明することにす
る。
【００３８】第１評価モードは、２つのプロファイルＨ
ＭＭの比較が、各プロファイルＨＭＭのＭノードに付与
されている出力確率のみを用いて行なわれるモードであ
る。この第１評価モードでは、（ｉmax＋１）×（ｊmax
＋１）個のノードからなり、ノード〔ｉ，ｊ〕が、ＨＭ
Ｍ＃０に関するｉ番目のＭノードの出力確率ベクトルと
ＨＭＭ＃１に関するｊ番目のＭノードの出力確率ベクト
ルとに対応づけられたマトリックス（図３参照；以下、
評価値マトリックスと表記する）が、想定される。な
お、ｉmaxは、類似性の評価が行なわれるべき２プロフ
ァイルＨＭＭのうちの一方のプロファイルＨＭＭ（以
下、ＨＭＭ＃０と表記する）のＭノードの数であり、ｊ
maxは、他方のプロファイルＨＭＭ（以下、ＨＭＭ＃１
と表記する）のＭノードの数である。
ＭＭの比較が、各プロファイルＨＭＭのＭノードに付与
されている出力確率のみを用いて行なわれるモードであ
る。この第１評価モードでは、（ｉmax＋１）×（ｊmax
＋１）個のノードからなり、ノード〔ｉ，ｊ〕が、ＨＭ
Ｍ＃０に関するｉ番目のＭノードの出力確率ベクトルと
ＨＭＭ＃１に関するｊ番目のＭノードの出力確率ベクト
ルとに対応づけられたマトリックス（図３参照；以下、
評価値マトリックスと表記する）が、想定される。な
お、ｉmaxは、類似性の評価が行なわれるべき２プロフ
ァイルＨＭＭのうちの一方のプロファイルＨＭＭ（以
下、ＨＭＭ＃０と表記する）のＭノードの数であり、ｊ
maxは、他方のプロファイルＨＭＭ（以下、ＨＭＭ＃１
と表記する）のＭノードの数である。
【００３９】この第１評価モードでの評価を指示された
場合、ダイナミック・プログラミング処理部２３は、評
価値マトリックスのノード〔ｉ，ｊ〕の評価値Ｖi,j
を、以下に記す（２）式を用いて算出する。
場合、ダイナミック・プログラミング処理部２３は、評
価値マトリックスのノード〔ｉ，ｊ〕の評価値Ｖi,j
を、以下に記す（２）式を用いて算出する。
【００４０】
【数３】
【００４１】この（２）式において、ｄは、いわゆるギ
ャップコスト（ギャップペナルティ）であり、Ｌ、
Ｌ′、Ｌ″は、ノード〔ｉ，ｊ〕に至るまでに通過して
きたノードの数である。なお、Ｌ、Ｌ′及びＬ″を導入
しているのは、ギャップが多く挿入された経路の評価値
が、相対的に小さな値となるようにするためである。
ャップコスト（ギャップペナルティ）であり、Ｌ、
Ｌ′、Ｌ″は、ノード〔ｉ，ｊ〕に至るまでに通過して
きたノードの数である。なお、Ｌ、Ｌ′及びＬ″を導入
しているのは、ギャップが多く挿入された経路の評価値
が、相対的に小さな値となるようにするためである。
【００４２】また、Ｍiは、ＨＭＭ＃０のノードＭiに関
する出力確率ベクトルであり、ＭjＨＭＭ＃１のノード
Ｍjに関する出力確率ベクトルである。Ｓ(Ｍi，Ｍj)
は、出力確率ベクトルＭiと出力確率ベクトルＭjとか
ら、それらの類似性を示す数値情報である類似度を求め
る関数である。このＳ(Ｍi，Ｍj)としては、Ｍi，Ｍjが
同一のものであるときに、最大値（例えば、“１”）を
とり、Ｍi，Ｍjが全く異なったものである（Ｍi，Ｍjが
直交している）ときに、最小値（例えば、“０”）をと
る関数であればどのようなものでも用いることもでき
る。すなわち、このＳ(Ｍi，Ｍj)としては、図４に示し
たように、ベクトルＭi，Ｍj間の角度Θの余弦cos(Θ)
や、角度Θの余弦の二乗値cos2(Θ)等を用いることが出
来るのであるが、本実施形態のダイナミック・プログラ
ミング処理部２３は、このＳ(Ｍi，Ｍj)として、角度Θ
の余弦の二乗値cos2(Θ)が用いられたものとなってい
る。
する出力確率ベクトルであり、ＭjＨＭＭ＃１のノード
Ｍjに関する出力確率ベクトルである。Ｓ(Ｍi，Ｍj)
は、出力確率ベクトルＭiと出力確率ベクトルＭjとか
ら、それらの類似性を示す数値情報である類似度を求め
る関数である。このＳ(Ｍi，Ｍj)としては、Ｍi，Ｍjが
同一のものであるときに、最大値（例えば、“１”）を
とり、Ｍi，Ｍjが全く異なったものである（Ｍi，Ｍjが
直交している）ときに、最小値（例えば、“０”）をと
る関数であればどのようなものでも用いることもでき
る。すなわち、このＳ(Ｍi，Ｍj)としては、図４に示し
たように、ベクトルＭi，Ｍj間の角度Θの余弦cos(Θ)
や、角度Θの余弦の二乗値cos2(Θ)等を用いることが出
来るのであるが、本実施形態のダイナミック・プログラ
ミング処理部２３は、このＳ(Ｍi，Ｍj)として、角度Θ
の余弦の二乗値cos2(Θ)が用いられたものとなってい
る。
【００４３】以下、図５及び図６を用いて、この第１評
価モードでの評価を指示された場合のダイナミック・プ
ログラミング処理部２３の動作を、より具体的に説明す
る。
価モードでの評価を指示された場合のダイナミック・プ
ログラミング処理部２３の動作を、より具体的に説明す
る。
【００４４】第１評価モードでの評価を指示された形で
動作を開始したダイナミック・プログラミング処理部２
３は、図５に示したように、まず、モデル情報記憶部２
２に記憶されている２つの確率モデル情報に基づき、ノ
ード毎に、類似度の計算を行なう（ステップＳ１０
１）。
動作を開始したダイナミック・プログラミング処理部２
３は、図５に示したように、まず、モデル情報記憶部２
２に記憶されている２つの確率モデル情報に基づき、ノ
ード毎に、類似度の計算を行なう（ステップＳ１０
１）。
【００４５】例えば、類似性を評価すべき確率モデル
（プロファイルＨＭＭ）として、それぞれ、図６
（ａ）、（ｂ）に示した内容の確率モデルＨ０，Ｈ１が
与えられた場合、ダイナミック・プログラミング処理部
２３は、ステップＳ１０１において、図６（ｃ）に示し
たように、１６個の類似度の計算を行なう。なお、確率
モデルＨ０は、“ＡＡＡＡ”と“ＡＡＡＡ”とからなる
ホモロジーグループに対して作成されたものであり、確
率モデルＨ１は、“ＡＡＧＡ”と“ＡＣＡＡ”とからな
るホモロジーグループに対して作成されたものである。
（プロファイルＨＭＭ）として、それぞれ、図６
（ａ）、（ｂ）に示した内容の確率モデルＨ０，Ｈ１が
与えられた場合、ダイナミック・プログラミング処理部
２３は、ステップＳ１０１において、図６（ｃ）に示し
たように、１６個の類似度の計算を行なう。なお、確率
モデルＨ０は、“ＡＡＡＡ”と“ＡＡＡＡ”とからなる
ホモロジーグループに対して作成されたものであり、確
率モデルＨ１は、“ＡＡＧＡ”と“ＡＣＡＡ”とからな
るホモロジーグループに対して作成されたものである。
【００４６】そして、ダイナミック・プログラミング処
理部２３は、（２）式を用いた逐次演算により各ノード
の評価値を算出して内部に記憶するとともに、各ノード
について、評価値の算出に用いられた経路を示す経路情
報を内部に記憶する処理を行なう（ステップＳ１０
２）。図６に示したケースでは、このステップＳ１０２
にて、図６（ｄ）に示したような評価値群が算出、記憶
されるとともに、図６（ｅ）に示したような状態を表す
経路情報群が、記憶される。なお、図６（ｅ）は、斜
め、右、下の経路で評価値が算出されたノードに、それ
ぞれ、“＼”、“←”、“↑”を対応づけた図となって
いる。
理部２３は、（２）式を用いた逐次演算により各ノード
の評価値を算出して内部に記憶するとともに、各ノード
について、評価値の算出に用いられた経路を示す経路情
報を内部に記憶する処理を行なう（ステップＳ１０
２）。図６に示したケースでは、このステップＳ１０２
にて、図６（ｄ）に示したような評価値群が算出、記憶
されるとともに、図６（ｅ）に示したような状態を表す
経路情報群が、記憶される。なお、図６（ｅ）は、斜
め、右、下の経路で評価値が算出されたノードに、それ
ぞれ、“＼”、“←”、“↑”を対応づけた図となって
いる。
【００４７】ステップＳ１０２の完了後、ダイナミック
・プログラミング処理部２３は、バックトレースを行な
って、その結果を、判定結果提示部２５が必要とする情
報（バックトレースがされなかった部分に関する経路情
報）とともに、判定結果記憶部２４に記憶（図５：ステ
ップＳ１０３）して、図示した処理を終了する。
・プログラミング処理部２３は、バックトレースを行な
って、その結果を、判定結果提示部２５が必要とする情
報（バックトレースがされなかった部分に関する経路情
報）とともに、判定結果記憶部２４に記憶（図５：ステ
ップＳ１０３）して、図示した処理を終了する。
【００４８】この後、評価結果提示処理部２５によっ
て、評価結果記憶部２４に記憶された情報に基づき、操
作者に評価結果を提示する処理（評価結果を表示、印刷
させるための処理）が、行なわれ、例えば、図７に示し
たような内容のグラフ（記号をマトリックス状に並べた
もの）と、バックトレースによって得られた最適アライ
メントのＶ値とが表示する処理が行なわれる。
て、評価結果記憶部２４に記憶された情報に基づき、操
作者に評価結果を提示する処理（評価結果を表示、印刷
させるための処理）が、行なわれ、例えば、図７に示し
たような内容のグラフ（記号をマトリックス状に並べた
もの）と、バックトレースによって得られた最適アライ
メントのＶ値とが表示する処理が行なわれる。
【００４９】なお、この図７は、本件出願時点における
Pfam(http://pfam.wsustl.edu)のエントリーBig1(Bacte
rial Ig-like domein(group1))：length108と、Big2 (B
acterial Ig-like domein(group2))：length88とに対し
て、第１評価モードによる評価を行なった結果を示した
図であり、図中、“＼”、“｜”、“＝”は、各記号が
記された部分が、バックトレースされた部分であって、
それぞれ、斜め上、上、横（左）から接続されている部
分であることを、示している。また、“＋”、“：”、
“−”は、各記号が記された部分が、バックトレースさ
れなかった部分であって、それぞれ、斜め上、上、横
（左）から接続されている部分であることを、示してい
る。また、この図のバックトレースされた部分（すなわ
ち、アライメント）の類似度（評価値）は、0.392255と
計算されている。
Pfam(http://pfam.wsustl.edu)のエントリーBig1(Bacte
rial Ig-like domein(group1))：length108と、Big2 (B
acterial Ig-like domein(group2))：length88とに対し
て、第１評価モードによる評価を行なった結果を示した
図であり、図中、“＼”、“｜”、“＝”は、各記号が
記された部分が、バックトレースされた部分であって、
それぞれ、斜め上、上、横（左）から接続されている部
分であることを、示している。また、“＋”、“：”、
“−”は、各記号が記された部分が、バックトレースさ
れなかった部分であって、それぞれ、斜め上、上、横
（左）から接続されている部分であることを、示してい
る。また、この図のバックトレースされた部分（すなわ
ち、アライメント）の類似度（評価値）は、0.392255と
計算されている。
【００５０】次に、第２評価モードでのダイナミック・
プログラミング処理部２３の動作を、第１評価モードで
のダイナミック・プログラミング処理部２３の動作との
違いを中心に、説明する。
プログラミング処理部２３の動作を、第１評価モードで
のダイナミック・プログラミング処理部２３の動作との
違いを中心に、説明する。
【００５１】第２評価モードでは、２つのプロファイル
ＨＭＭの比較が、各プロファイルＨＭＭのＭノードに付
与されている出力確率及び遷移確率を用いて行なわれ
る。
ＨＭＭの比較が、各プロファイルＨＭＭのＭノードに付
与されている出力確率及び遷移確率を用いて行なわれ
る。
【００５２】この第２評価モードでの評価を指示された
場合、ダイナミック・プログラミング処理部２３は、評
価値マトリックスのノード〔ｉ，ｊ〕の評価値Ｖi,j
を、以下に記す（３）式を用いて算出する。
場合、ダイナミック・プログラミング処理部２３は、評
価値マトリックスのノード〔ｉ，ｊ〕の評価値Ｖi,j
を、以下に記す（３）式を用いて算出する。
【００５３】
【数４】
【００５４】この（３）式において、Ｔiは、ＨＭＭ＃
０のノードＭiに関する遷移確率ベクトルであり、Ｔ
jは、ＨＭＭ＃１のノードＭjに関する遷移確率ベクトル
である。Ｓ(Ｔi，Ｔj)は、それら２つの遷移確率ベクト
ル間の類似度（２ベクトルのなす角の余弦の二乗値）で
ある。
０のノードＭiに関する遷移確率ベクトルであり、Ｔ
jは、ＨＭＭ＃１のノードＭjに関する遷移確率ベクトル
である。Ｓ(Ｔi，Ｔj)は、それら２つの遷移確率ベクト
ル間の類似度（２ベクトルのなす角の余弦の二乗値）で
ある。
【００５５】以下、図８を用いて、この（３）式が有効
である理由を簡単に説明する。
である理由を簡単に説明する。
【００５６】周知のように、ある配列群から作成できる
プロファイルＨＭＭは、１つに限られない。例えば、
“ＡＣＴ”、“ＡＧＴ”、“Ａ−Ｔ”、“Ａ−Ｔ”とい
ったマルチプル・アライメントからは、図８に模式的に
示したような内容の２つのプロファイルＨＭＭ（簡単に
言えば、同じ部分が、それぞれ、Ｍノード、Ｉノードと
して扱われている２つのプロファイルＨＭＭ）を、作成
することが出来る。
プロファイルＨＭＭは、１つに限られない。例えば、
“ＡＣＴ”、“ＡＧＴ”、“Ａ−Ｔ”、“Ａ−Ｔ”とい
ったマルチプル・アライメントからは、図８に模式的に
示したような内容の２つのプロファイルＨＭＭ（簡単に
言えば、同じ部分が、それぞれ、Ｍノード、Ｉノードと
して扱われている２つのプロファイルＨＭＭ）を、作成
することが出来る。
【００５７】そして、この２つのプロファイルＨＭＭの
類似性の判定が行われた場合、「上側に記してあるプロ
ファイルＨＭＭの１番目、２番目のＭノードと、下側に
記してあるプロファイルＨＭＭの１番目、３番目のＭノ
ードとが対応しており、これらのプロファイルＨＭＭ
は、極めて類似している」といった結果が得られるべき
である。しかしながら、上記した第１評価モードでは、
Ｉノードの存在が完全に無視されているので、極めて類
似しているという結果が得られないことや、Ｍノード間
の対応関係が誤って解釈されることが有り得る。
類似性の判定が行われた場合、「上側に記してあるプロ
ファイルＨＭＭの１番目、２番目のＭノードと、下側に
記してあるプロファイルＨＭＭの１番目、３番目のＭノ
ードとが対応しており、これらのプロファイルＨＭＭ
は、極めて類似している」といった結果が得られるべき
である。しかしながら、上記した第１評価モードでは、
Ｉノードの存在が完全に無視されているので、極めて類
似しているという結果が得られないことや、Ｍノード間
の対応関係が誤って解釈されることが有り得る。
【００５８】これに対して、この第２評価モードでは、
斜め方向の移動に対する評価値が、Ｓ(Ｔi，Ｔj)・Ｓ
(Ｍi，Ｍj)とされている。Ｓ(Ｔi，Ｔj)は、Ｉノード、
Ｄノードの存在を直接的に示す値ではないが、図８に示
したような関係が生じている部分に関するＳ(Ｔi，Ｔj)
は、かなり小さな値となる（図８の、左端に示してある
２つのＭノードに関するＳ(Ｔi，Ｔj)は、０．２５）。
従って、この第２評価モードによれば、横方向或いは縦
方向の移動が選択されるべき部分で、斜め方向の移動が
選択されることが少なくなり、その結果として、第１評
価モードよりも正確な類似性の判定が行なえることにな
る。
斜め方向の移動に対する評価値が、Ｓ(Ｔi，Ｔj)・Ｓ
(Ｍi，Ｍj)とされている。Ｓ(Ｔi，Ｔj)は、Ｉノード、
Ｄノードの存在を直接的に示す値ではないが、図８に示
したような関係が生じている部分に関するＳ(Ｔi，Ｔj)
は、かなり小さな値となる（図８の、左端に示してある
２つのＭノードに関するＳ(Ｔi，Ｔj)は、０．２５）。
従って、この第２評価モードによれば、横方向或いは縦
方向の移動が選択されるべき部分で、斜め方向の移動が
選択されることが少なくなり、その結果として、第１評
価モードよりも正確な類似性の判定が行なえることにな
る。
【００５９】次に、第３評価モードにおけるダイナミッ
ク・プログラミング処理部２３の動作を、上記した第２
評価モードにおけるダイナミック・プログラミング処理
部２３の動作との違いを中心に、説明する。
ク・プログラミング処理部２３の動作を、上記した第２
評価モードにおけるダイナミック・プログラミング処理
部２３の動作との違いを中心に、説明する。
【００６０】第３評価モードは、Ｉノード、Ｄノードの
存在がより積極的に考慮された評価モードであり、この
第３評価モードでの評価を指示された場合、ダイナミッ
ク・プログラミング処理部２３は、評価値マトリックス
のノード〔ｉ，ｊ〕の評価値Ｖi,j を、以下に記す
（４）〜（７）式を用いて算出する。
存在がより積極的に考慮された評価モードであり、この
第３評価モードでの評価を指示された場合、ダイナミッ
ク・プログラミング処理部２３は、評価値マトリックス
のノード〔ｉ，ｊ〕の評価値Ｖi,j を、以下に記す
（４）〜（７）式を用いて算出する。
【００６１】
【数５】
【００６２】これらの式において、Ｔｍi、Ｔｉi、Ｔｄ
iは、それぞれ、ＨＭＭ＃０のＭノード＃ｉに関するＭ
ノードへの遷移確率、Ｉノードへの遷移確率、Ｄノード
への遷移確率である。Ｔｍj、Ｔｉj、Ｔｄjは、それぞ
れ、ＨＭＭ＃１のＭノード＃ｊに関するＭノードへの遷
移確率、Ｉノードへの遷移確率、Ｄノードへの遷移確率
ある。また、Ｉiは、ＨＭＭ＃０のノードＩiに関する出
力確率ベクトルであり、Ｉjは、ＨＭＭ＃１のノードＩj
に関する出力確率ベクトルである。
iは、それぞれ、ＨＭＭ＃０のＭノード＃ｉに関するＭ
ノードへの遷移確率、Ｉノードへの遷移確率、Ｄノード
への遷移確率である。Ｔｍj、Ｔｉj、Ｔｄjは、それぞ
れ、ＨＭＭ＃１のＭノード＃ｊに関するＭノードへの遷
移確率、Ｉノードへの遷移確率、Ｄノードへの遷移確率
ある。また、Ｉiは、ＨＭＭ＃０のノードＩiに関する出
力確率ベクトルであり、Ｉjは、ＨＭＭ＃１のノードＩj
に関する出力確率ベクトルである。
【００６３】すなわち、この第３評価モードでは、斜め
方向の移動に対する評価値として、（５）式で示されて
いるように、２つのＭノードの出力確率ベクトルの類似
度（“Ｓ(Ｍi、Ｍj)”）、２つのＩノードの出力確率ベ
クトルの類似度（“Ｓ(Ｉi、Ｉj)”）、及び、２つのＭ
ノードの遷移確率ベクトル（“Ｔｍi、Ｔｉi、Ｔｄi”
と“Ｔｍj、Ｔｉj、Ｔｄj”）の関数が、使用される。
なお、（５）式におけるＳ(Ｍi，Ｍj) 、Ｓ(Ｉi，Ｉj)
を、それぞれ、“１”に置換することによって得られる
式が、遷移確率ベクトルＴi、Ｔjのなす角度Θの余弦co
s（Θ）を示す式であることから明らかなように、
（５）式によって算出されるＳｉｍi、jは、“０”〜
“１”の範囲内の値となる。
方向の移動に対する評価値として、（５）式で示されて
いるように、２つのＭノードの出力確率ベクトルの類似
度（“Ｓ(Ｍi、Ｍj)”）、２つのＩノードの出力確率ベ
クトルの類似度（“Ｓ(Ｉi、Ｉj)”）、及び、２つのＭ
ノードの遷移確率ベクトル（“Ｔｍi、Ｔｉi、Ｔｄi”
と“Ｔｍj、Ｔｉj、Ｔｄj”）の関数が、使用される。
なお、（５）式におけるＳ(Ｍi，Ｍj) 、Ｓ(Ｉi，Ｉj)
を、それぞれ、“１”に置換することによって得られる
式が、遷移確率ベクトルＴi、Ｔjのなす角度Θの余弦co
s（Θ）を示す式であることから明らかなように、
（５）式によって算出されるＳｉｍi、jは、“０”〜
“１”の範囲内の値となる。
【００６４】また、（６）、（７）式で定義されている
Ｄ１i,j、Ｄ２i,jは、Ｉノード或いはＤノードの存在
が、経路選択時により積極的に考慮されるようにするた
めに導入した関数である。
Ｄ１i,j、Ｄ２i,jは、Ｉノード或いはＤノードの存在
が、経路選択時により積極的に考慮されるようにするた
めに導入した関数である。
【００６５】すなわち、図８に用いて行なった説明から
明らかなように、プロファイルＨＭＭ間の比較では、一
方のプロファイルＨＭＭのＩノード或いはＤノードを経
由させた方が良いケースがある。そのような結果が得ら
れるようにするためには、いわゆるギャップコスト
（（３）式のｄ値）が、存在しているＩノード及びＤノ
ードの状態に応じた値となるようにしてやれば良い。
明らかなように、プロファイルＨＭＭ間の比較では、一
方のプロファイルＨＭＭのＩノード或いはＤノードを経
由させた方が良いケースがある。そのような結果が得ら
れるようにするためには、いわゆるギャップコスト
（（３）式のｄ値）が、存在しているＩノード及びＤノ
ードの状態に応じた値となるようにしてやれば良い。
【００６６】そして、ＨＭＭ＃１のＭノードと類似する
ＩノードがＨＭＭ＃０に存在する場合に、大きな値を取
る関数（演算式）としては、Ｔｉi・Ｔｍj・Ｓ（Ｉi、
Ｍj）（逆の場合は、Ｔｉj・Ｔｍi・Ｓ（Ｉj、Ｍi））
が考えられる。また、Ｄノードへの遷移確率が高いＭノ
ードが存在するＨＭＭ＃０に対して、そのＭノードに関
して大きくなる関数（演算式）としては、Ｔｍi・Ｔｄj
（逆の場合は、Ｔｍj・Ｔｄi）が、考えられる。このた
め、横方向の移動に対する評価値として、（６）式で定
義されているＤ１i,j値とｄ値との中の大きな方の値が
用いられ、縦方向の移動に対する評価値として、（７）
式で定義されているＤ１i,j値とｄ値との中の大きな方
の値が、用いられるようにしているのである。
ＩノードがＨＭＭ＃０に存在する場合に、大きな値を取
る関数（演算式）としては、Ｔｉi・Ｔｍj・Ｓ（Ｉi、
Ｍj）（逆の場合は、Ｔｉj・Ｔｍi・Ｓ（Ｉj、Ｍi））
が考えられる。また、Ｄノードへの遷移確率が高いＭノ
ードが存在するＨＭＭ＃０に対して、そのＭノードに関
して大きくなる関数（演算式）としては、Ｔｍi・Ｔｄj
（逆の場合は、Ｔｍj・Ｔｄi）が、考えられる。このた
め、横方向の移動に対する評価値として、（６）式で定
義されているＤ１i,j値とｄ値との中の大きな方の値が
用いられ、縦方向の移動に対する評価値として、（７）
式で定義されているＤ１i,j値とｄ値との中の大きな方
の値が、用いられるようにしているのである。
【００６７】以下、本類似性評価装置１０による実際の
評価結果を幾つか紹介することにする。
評価結果を幾つか紹介することにする。
【００６８】まず、“ＡＡＣＡＡ”、“ＡＡＣＡＡ”、
“ＡＡ−ＡＡ”、“ＡＡ−ＡＡ”というマルチプル・ア
ライメントから作成された図９（Ａ）、（Ｂ）に示した
内容のＨＭＭ＃０、ＨＭＭ＃１に対する第１評価モード
での評価結果と第２評価モードでの評価結果とを説明す
る。
“ＡＡ−ＡＡ”、“ＡＡ−ＡＡ”というマルチプル・ア
ライメントから作成された図９（Ａ）、（Ｂ）に示した
内容のＨＭＭ＃０、ＨＭＭ＃１に対する第１評価モード
での評価結果と第２評価モードでの評価結果とを説明す
る。
【００６９】この場合、第２評価モードでのバックトレ
ース結果は、図１０に示したものとなり、両ＨＭＭの類
似度（評価値）としては、0.962821が算出された。一
方、第１評価モードでのバックトレース結果は、図１０
に示したものと同様のものであるが、類似度としては、
0.85が算出された。
ース結果は、図１０に示したものとなり、両ＨＭＭの類
似度（評価値）としては、0.962821が算出された。一
方、第１評価モードでのバックトレース結果は、図１０
に示したものと同様のものであるが、類似度としては、
0.85が算出された。
【００７０】このことから、第２評価モードの方が、第
１評価モードよりも、信頼できる類似度を算出できる評
価モードとなっていると言うことができる。
１評価モードよりも、信頼できる類似度を算出できる評
価モードとなっていると言うことができる。
【００７１】ただし、大量にデータがあるＨＭＭに関し
ては、第１評価モードでも十分な類似性判定が行なえる
ことも確認されている。
ては、第１評価モードでも十分な類似性判定が行なえる
ことも確認されている。
【００７２】具体的には、４つのホモロジーグループの
アミノ酸配列から、それぞれ、5H1A_M7、5H1B_D7、5HT_BO
6、5HT_HE6と名付けたプロファイルＨＭＭを作成し、そ
れらの全ての組み合わせに対して、第１評価モードで評
価を行なった。その結果、図１１〜図１７に示した判定
結果を得ることが出来た。
アミノ酸配列から、それぞれ、5H1A_M7、5H1B_D7、5HT_BO
6、5HT_HE6と名付けたプロファイルＨＭＭを作成し、そ
れらの全ての組み合わせに対して、第１評価モードで評
価を行なった。その結果、図１１〜図１７に示した判定
結果を得ることが出来た。
【００７３】なお、これらの図のうち、図１１は、各組
み合わせに対して得られた類似度（評価値）を示した図
であり、図１２は、5H1A_M7と5H1B_D7との間のバックト
レース結果を示した図である。図１３は、5H1A_M7と5HT
_BO6との間のバックトレース結果を示した図であり、図
１４は、5H1A_M7と5HT_HE6との間のバックトレース結果
を示した図である。図１５は、5H1B_D7と5HT_BO6との間
のバックトレース結果である。図１６は、5H1B_D7と5HT
_HE6との間のバックトレース結果を示した図である。そ
して、図１７は、5HT_BO6と5HT_HE6との間のバックトレ
ース結果を示した図である。また、図１２〜図１７中、
“＼”、“｜”、“＝”は、各記号が記された部分が、
バックトレースされた部分であって、それぞれ、斜め
上、上、横（左）から接続されている部分であること
を、示しており、“＋”、“：”、“−”は、各記号が
記された部分が、バックトレースされなかった部分であ
って、それぞれ、斜め上、上、横（左）から接続されて
いる部分であることを、示している。
み合わせに対して得られた類似度（評価値）を示した図
であり、図１２は、5H1A_M7と5H1B_D7との間のバックト
レース結果を示した図である。図１３は、5H1A_M7と5HT
_BO6との間のバックトレース結果を示した図であり、図
１４は、5H1A_M7と5HT_HE6との間のバックトレース結果
を示した図である。図１５は、5H1B_D7と5HT_BO6との間
のバックトレース結果である。図１６は、5H1B_D7と5HT
_HE6との間のバックトレース結果を示した図である。そ
して、図１７は、5HT_BO6と5HT_HE6との間のバックトレ
ース結果を示した図である。また、図１２〜図１７中、
“＼”、“｜”、“＝”は、各記号が記された部分が、
バックトレースされた部分であって、それぞれ、斜め
上、上、横（左）から接続されている部分であること
を、示しており、“＋”、“：”、“−”は、各記号が
記された部分が、バックトレースされなかった部分であ
って、それぞれ、斜め上、上、横（左）から接続されて
いる部分であることを、示している。
【００７４】このように、第１評価モードの評価結果か
らも、5H1A_M7と5H1B_D7が極めて似ていること、5HT_BO
6と5HT_HE6が極めて似ていること、5H1B_D7の後半部分
に、5H1A_M7と極めて類似した部分が含まれることなど
を、十分に読取ることが出来る。
らも、5H1A_M7と5H1B_D7が極めて似ていること、5HT_BO
6と5HT_HE6が極めて似ていること、5H1B_D7の後半部分
に、5H1A_M7と極めて類似した部分が含まれることなど
を、十分に読取ることが出来る。
【００７５】以上、詳細に説明したように、本実施形態
に係る類似性評価装置１０は、確率モデル間の類似度
を、ダイナミック・プログラミング法により求めること
が出来るように構成されているので、この類似性評価装
置１０を用いれば、従来よりも高速に確率モデル間の類
似性の判定が行なえることになる。
に係る類似性評価装置１０は、確率モデル間の類似度
を、ダイナミック・プログラミング法により求めること
が出来るように構成されているので、この類似性評価装
置１０を用いれば、従来よりも高速に確率モデル間の類
似性の判定が行なえることになる。
【００７６】＜変形形態＞上記した類似性評価装置１０
は、各種の変形が可能である。例えば、実施形態に係る
ダイナミック・プログラミング処理部２３が、第３評価
モードで動作しているときに処理に使用するＤ１、Ｄ２
値は、ＤノードとＩノードの存在の双方が考慮された値
であったが、Ｄノード経由時の評価値（評価関数）とＩ
ノード経由時の評価値（評価関数）とが算出され、それ
らとｄ値の中の最大値が、横方向或いは縦方向の移動に
対する評価値とようにしておいても良い。
は、各種の変形が可能である。例えば、実施形態に係る
ダイナミック・プログラミング処理部２３が、第３評価
モードで動作しているときに処理に使用するＤ１、Ｄ２
値は、ＤノードとＩノードの存在の双方が考慮された値
であったが、Ｄノード経由時の評価値（評価関数）とＩ
ノード経由時の評価値（評価関数）とが算出され、それ
らとｄ値の中の最大値が、横方向或いは縦方向の移動に
対する評価値とようにしておいても良い。
【００７７】また、類似性評価装置１０は、コンピュー
タに類似性評価プログラムをインストールした装置であ
ったが、ダイナミック・プログラミング処理部２３をＩ
Ｃとしてもよいことや、類似性評価装置１０で用いられ
ている技術を、ＨＭＭ以外の確率モデルに適用しても良
いことは、当然である。
タに類似性評価プログラムをインストールした装置であ
ったが、ダイナミック・プログラミング処理部２３をＩ
Ｃとしてもよいことや、類似性評価装置１０で用いられ
ている技術を、ＨＭＭ以外の確率モデルに適用しても良
いことは、当然である。
【００７８】
【発明の効果】本発明の類似性評価方法によれば、従来
よりも高速に確率モデル間の類似性の判定が行なえるこ
とになる。また、本発明の類似性評価プログラムによれ
ば、コンピュータを、従来よりも高速に確率モデル間の
類似性の判定が行なえる装置として動作させことが可能
となる。
よりも高速に確率モデル間の類似性の判定が行なえるこ
とになる。また、本発明の類似性評価プログラムによれ
ば、コンピュータを、従来よりも高速に確率モデル間の
類似性の判定が行なえる装置として動作させことが可能
となる。
【図１】 本発明の一実施形態に係る類似性評価装置の
機能ブロック図である。
機能ブロック図である。
【図２】 実施形態に係る類似性評価装置が処理対象と
する確率モデルであるプロファイルＨＭＭを説明するた
めの図である。
する確率モデルであるプロファイルＨＭＭを説明するた
めの図である。
【図３】 ダイナミック・プログラミング法によるペア
ワイズ・アライメントを説明するための図である。
ワイズ・アライメントを説明するための図である。
【図４】 ダイナミック・プログラミング処理部によっ
て算出される類似度の説明図である。
て算出される類似度の説明図である。
【図５】 ダイナミック・プログラミング処理部の動作
手順を示したフローチャートである。
手順を示したフローチャートである。
【図６】 ダイナミック・プログラミング処理部の動作
を説明するための図である。
を説明するための図である。
【図７】 ダイナミック・プログラミング処理部の動作
結果を説明するための図である。
結果を説明するための図である。
【図８】 ダイナミック・プログラミング処理部の動作
内容を説明するための図である。
内容を説明するための図である。
【図９】 ダイナミック・プログラミング処理部の動作
を説明するための図である。
を説明するための図である。
【図１０】 ダイナミック・プログラミング処理部の動
作結果を説明するための図である。
作結果を説明するための図である。
【図１１】 ダイナミック・プログラミング処理部の動
作結果を説明するための図である。
作結果を説明するための図である。
【図１２】 ダイナミック・プログラミング処理部の動
作結果を説明するための図である。
作結果を説明するための図である。
【図１３】 ダイナミック・プログラミング処理部の動
作結果を説明するための図である。
作結果を説明するための図である。
【図１４】 ダイナミック・プログラミング処理部の動
作結果を説明するための図である。
作結果を説明するための図である。
【図１５】 ダイナミック・プログラミング処理部の動
作結果を説明するための図である。
作結果を説明するための図である。
【図１６】 ダイナミック・プログラミング処理部の動
作結果を説明するための図である。
作結果を説明するための図である。
【図１７】 ダイナミック・プログラミング処理部の動
作結果を説明するための図である。
作結果を説明するための図である。
１０ 類似性評価装置
２１ 確率モデル情報取得部
２２ 確率モデル情報記憶部
２３ ダイナミック・プログラミング処理部
２４ 評価結果記憶部
２５ 評価結果提示処理部
Claims (10)
- 【請求項１】 複数種類の確率データからなる確率情報
を複数個含む確率モデル情報間の類似性を評価するため
の類似性評価方法であって、 類似性を評価すべき２つの確率モデル情報のうちの一方
の確率モデル情報に含まれる任意の確率情報と、他方の
確率モデル情報に含まれる任意の確率情報とに基づき、
それらの確率情報間の類似性を示す類似値を算出するた
めの類似値算出ステップと、前記２つの確率モデル情報
の類似性を評価するために、前記類似値算出ステッ プにより算出された類似値を経路の選択のための指標値
として用いたダイナミック・プログラミング法に基づく
演算処理を行なう評価ステップとを、含むことを特徴と
する類似性評価方法。 - 【請求項２】 前記確率モデル情報が、隠れマルコフモ
デルに関する確率モデル情報であり、 前記類似値算出ステップは、前記２つの確率情報のうち
の一方の確率情報に含まれる複数種類の出力確率データ
と、他方の確率情報に含まれる複数種類の出力確率デー
タとに基づき、前記類似値を算出することを特徴とする
請求項１記載の類似性評価方法。 - 【請求項３】 前記確率モデル情報が、隠れマルコフモ
デルに関する確率モデル情報であり、 前記類似値算出ステップは、前記２つの確率情報のうち
の一方の確率情報に含まれる複数種類の出力確率データ
及び複数種類の遷移確率データと、他方の確率情報に含
まれる複数種類の出力確率データと複数種類の遷移確率
データとに基づき、前記類似値を算出することを特徴と
する請求項１記載の類似性評価方法。 - 【請求項４】 前記類似値算出ステップは、前記一方の
確率情報に含まれる複数種類の出力確率データからなる
出力確率ベクトルと前記他方の確率情報に含まれる複数
種類の出力確率データからなる出力確率ベクトルとがな
す角度の余弦値の二乗値に、前記一方の確率情報に含ま
れる前記複数種類の遷移確率データからなる遷移確率ベ
クトルと前記他方の確率情報に含まれる前記複数種類の
遷移確率データからなる遷移確率ベクトルとがなす角度
の余弦値の二乗値を乗じた結果を、前記類似値として算
出することを特徴とする請求項３記載の類似性評価方
法。 - 【請求項５】 前記評価ステップが行なった演算処理の
結果に基づき、前記２つの確率モデル情報間の確率情報
単位での類似関係を示す情報を出力する類似関係情報出
力ステップを、さらに含むことを特徴とする請求項１乃
至請求項４のいずれかに記載の類似性評価方法。 - 【請求項６】 複数種類の確率データからなる確率情報
を複数個含む確率モデル情報間の類似性を評価させるこ
とを目的として、 コンピュータに、 類似性を評価すべき２つの確率モデル情報のうちの一方
の確率モデル情報に含まれる任意の確率情報と、他方の
確率モデル情報に含まれる任意の確率情報とに基づき、
それらの確率情報間の類似性を示す類似値を算出するた
めの類似値算出ステップと、 前記２つの確率モデル情報の類似性を評価するために、
前記類似値算出ステップにより算出された類似値を経路
の選択のための指標値として用いたダイナミック・プロ
グラミング法に基づく演算処理を行なう評価ステップと
を、実行させることを特徴とする類似性評価プログラ
ム。 - 【請求項７】 前記確率モデル情報が、隠れマルコフモ
デルに関する確率モデル情報であり、 前記類似値算出ステップは、前記２つの確率情報のうち
の一方の確率情報に含まれる複数種類の出力確率データ
と、他方の確率情報に含まれる複数種類の出力確率デー
タとに基づき、前記類似値を算出することを特徴とする
請求項６記載の類似性評価プログラム。 - 【請求項８】 前記確率モデル情報が、隠れマルコフモ
デルに関する確率モデル情報であり、 前記類似値算出ステップは、前記２つの確率情報のうち
の一方の確率情報に含まれる複数種類の出力確率データ
及び複数種類の遷移確率データと、他方の確率情報に含
まれる複数種類の出力確率データと複数種類の遷移確率
データとに基づき、前記類似値を算出することを特徴と
する請求項６記載の類似性評価プログラム。 - 【請求項９】 前記類似値算出ステップは、前記一方の
確率情報に含まれる複数種類の出力確率データからなる
出力確率ベクトルと前記他方の確率情報に含まれる複数
種類の出力確率データからなる出力確率ベクトルとがな
す角度の余弦値の二乗値に、前記一方の確率情報に含ま
れる前記複数種類の遷移確率データからなる遷移確率ベ
クトルと前記他方の確率情報に含まれる前記複数種類の
遷移確率データからなる遷移確率ベクトルとがなす角度
の余弦値の二乗値を乗じた結果を、前記類似値として算
出することを特徴とする請求項８記載の類似性評価プロ
グラム。 - 【請求項１０】 前記コンピュータに、 前記評価ステップが行なった演算処理の結果に基づき、
前記２つの確率モデル情報間の確率情報単位での類似関
係を示す情報を出力する類似関係情報出力ステップを、
さらに実行させることを特徴とする請求項６乃至請求項
９のいずれかに記載の類似性評価プログラム。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001299218A JP2003108187A (ja) | 2001-09-28 | 2001-09-28 | 類似性評価方法及び類似性評価プログラム |
| AU27731/02A AU765400B2 (en) | 2001-09-28 | 2002-03-27 | Similarity evaluation method, similarity evaluation program and similarity evaluation apparatus |
| US10/107,204 US20030065510A1 (en) | 2001-09-28 | 2002-03-28 | Similarity evaluation method, similarity evaluation program and similarity evaluation apparatus |
| EP02252615A EP1298534A3 (en) | 2001-09-28 | 2002-04-12 | Method and apparatus for Similarity evaluation |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001299218A JP2003108187A (ja) | 2001-09-28 | 2001-09-28 | 類似性評価方法及び類似性評価プログラム |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2003108187A true JP2003108187A (ja) | 2003-04-11 |
Family
ID=19120005
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001299218A Pending JP2003108187A (ja) | 2001-09-28 | 2001-09-28 | 類似性評価方法及び類似性評価プログラム |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US20030065510A1 (ja) |
| EP (1) | EP1298534A3 (ja) |
| JP (1) | JP2003108187A (ja) |
| AU (1) | AU765400B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100612882B1 (ko) | 2004-12-29 | 2006-08-14 | 삼성전자주식회사 | 시계열 신호의 패턴 인식 가능성 판단 방법 및 장치 |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7822614B2 (en) * | 2003-12-05 | 2010-10-26 | Kabushikikaisha Kenwood | Device control, speech recognition device, agent device, control method |
| JP2007047575A (ja) * | 2005-08-11 | 2007-02-22 | Canon Inc | パターンマッチング方法およびその装置、および音声情報検索システム |
| US20080059190A1 (en) * | 2006-08-22 | 2008-03-06 | Microsoft Corporation | Speech unit selection using HMM acoustic models |
| US8234116B2 (en) * | 2006-08-22 | 2012-07-31 | Microsoft Corporation | Calculating cost measures between HMM acoustic models |
| US8244534B2 (en) * | 2007-08-20 | 2012-08-14 | Microsoft Corporation | HMM-based bilingual (Mandarin-English) TTS techniques |
| JP7662953B2 (ja) * | 2021-02-15 | 2025-04-16 | 日本電信電話株式会社 | 情報処理装置、情報処理方法、及び、情報処理プログラム |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| MX9706407A (es) * | 1995-03-07 | 1997-11-29 | British Telecomm | Reconocimiento del lenguaje. |
| CA2180392C (en) * | 1995-07-31 | 2001-02-13 | Paul Wesley Cohrs | User selectable multiple threshold criteria for voice recognition |
| US5842161A (en) * | 1996-06-25 | 1998-11-24 | Lucent Technologies Inc. | Telecommunications instrument employing variable criteria speech recognition |
| US6128587A (en) * | 1997-01-14 | 2000-10-03 | The Regents Of The University Of California | Method and apparatus using Bayesian subfamily identification for sequence analysis |
| US5983180A (en) * | 1997-10-23 | 1999-11-09 | Softsound Limited | Recognition of sequential data using finite state sequence models organized in a tree structure |
-
2001
- 2001-09-28 JP JP2001299218A patent/JP2003108187A/ja active Pending
-
2002
- 2002-03-27 AU AU27731/02A patent/AU765400B2/en not_active Ceased
- 2002-03-28 US US10/107,204 patent/US20030065510A1/en not_active Abandoned
- 2002-04-12 EP EP02252615A patent/EP1298534A3/en not_active Withdrawn
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100612882B1 (ko) | 2004-12-29 | 2006-08-14 | 삼성전자주식회사 | 시계열 신호의 패턴 인식 가능성 판단 방법 및 장치 |
Also Published As
| Publication number | Publication date |
|---|---|
| AU2773102A (en) | 2003-04-03 |
| AU765400B2 (en) | 2003-09-18 |
| EP1298534A3 (en) | 2005-01-19 |
| EP1298534A2 (en) | 2003-04-02 |
| US20030065510A1 (en) | 2003-04-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3585523B2 (ja) | テキスト状画像認識方法 | |
| Sato et al. | RNA secondary structural alignment with conditional random fields | |
| CN110930993B (zh) | 特定领域语言模型生成方法及语音数据标注系统 | |
| JP3447762B2 (ja) | 画像生成器及び画像認識システム | |
| US20110022380A1 (en) | Phrase-based statistical machine translation as a generalized traveling salesman problem | |
| CN109670190B (zh) | 翻译模型构建方法和装置 | |
| JP2008532176A (ja) | 認識グラフ | |
| JP2009528604A (ja) | 第一のコンピュータ援用３ｄモデルを第二のコンピュータ援用３ｄモデルと比較するための方法 | |
| Zhu et al. | A system for automatic animation of piano performances | |
| WO2025241278A1 (zh) | 基于图文模态融合的文档信息抽取方法、装置及存储介质 | |
| CN109977085A (zh) | 一种识别模型构件文件重复的方法和装置 | |
| Bujny et al. | Hybrid evolutionary approach for level set topology optimization | |
| JP2003108187A (ja) | 類似性評価方法及び類似性評価プログラム | |
| KR20230082792A (ko) | 소스코드 보안 취약점의 종류를 구별하는 인공지능 기반의 구별 모델의 생성을 통해 소스코드에 대한 보안 취약점의 종류를 확인할 수 있도록 지원하는 전자 장치 및 그 동작 방법 | |
| US8069026B2 (en) | Clock gating analyzing apparatus, clock gating analyzing method, and computer product | |
| CN116013278B (zh) | 基于拼音对齐算法的语音识别多模型结果合并方法及装置 | |
| JP2003256435A (ja) | 配列データ統合処理方法、配列データ統合処理装置及び配列データ統合処理プログラム | |
| JP2019016163A (ja) | 磁性体シミュレーション装置、磁性体シミュレーションプログラム、及び磁性体シミュレーション方法 | |
| CN110070120B (zh) | 基于判别采样策略的深度度量学习方法及系统 | |
| Zhang et al. | On the robustness of diffusion inversion in image manipulation | |
| JP2022103676A (ja) | 情報処理装置、情報処理方法、プログラム | |
| CN114882515B (zh) | 基于神经网络模型的表格类型判定方法、设备及介质 | |
| WO2015030016A1 (ja) | 非構造化データ処理システム、非構造化データ処理方法および記録媒体 | |
| JPWO2009151002A1 (ja) | パターン識別方法、装置およびプログラム | |
| JP7687527B2 (ja) | 画像処理装置、方法およびプログラム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20051202 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20051227 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20060926 |