(57)【特許請求の範囲】
【請求項１】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、
を備え、
上記制御装置は、
利用者が上記入力装置を介して入力した二次構造を特定したいＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して、上記生成文法毎に構文解析木を導出する構文解析手段と、
上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、
上記適合度計算手段により計算された各々の上記構文解析木に対する上記適合度が高い順に上記構文解析木をソートするソート手段と、
上記ソート手段によりソートされた上記構文解析木と上記適合度を上記出力装置に出力する出力手段と、
を備えたことを特徴とするＲＮＡ配列解析装置。
【請求項２】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、
複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、
を備え、
上記制御装置は、
上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析手段と、
上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、
上記適合度計算手段により計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出手段と、
上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出手段にて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分をマークすることにより、上記ＲＮＡ配列間で共通に有する構造トポロジーを可視化する共通構造マトリックス作成手段と、
上記共通構造マトリックス作成手段により作成された上記二次元マトリックスを上記出力装置に出力する出力手段と、
を備えたことを特徴とするＲＮＡ配列解析装置。
【請求項３】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、
を備え、
上記制御装置は、
利用者が上記入力装置を介して入力したＤＮＡ配列から転写されるＲＮＡ配列を作成するＲＮＡ配列作成手段と、
上記ＲＮＡ配列作成手段により作成された上記ＲＮＡ配列に対して、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析手段と、
上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、
上記適合度計算手段により計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列に対応する上記ＤＮＡ配列を遺伝子の候補として予測する遺伝子予測手段と、
上記遺伝子予測手段にて予測された上記ＤＮＡ配列と上記構造解析木を上記出力装置に出力する出力手段と、
を備えたことを特徴とするＲＮＡ配列解析装置。
【請求項４】
制御装置と記憶装置と入力装置とを少なくとも備えたＲＮＡ配列解析装置において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、
複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、
を備え、
上記制御装置は、
上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析手段と、
上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、
上記適合度計算手段により計算された上記適合度に基づいて上記複数のＲＮＡ配列の間の類似度を計算する類似度計算手段と、
を備えたことを特徴とするＲＮＡ配列解析装置。
【請求項５】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、
複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、
を備え、
上記制御装置は、
上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析手段と、
上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、
上記適合度計算手段により計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出手段と、
上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出手段にて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分に上記適合度を表示する適合度マトリックスを作成する適合度マトリックス作成手段と、
上記適合度マトリックス作成手段にて作成された上記適合度マトリックスについて、上記構造トポロジー毎に対応する全ての上記適合度の総和を計算し、当該総和に基づいて上記構造トポロジーをソートする共通構造抽出手段と、
上記共通構造抽出手段によりソートされた上記適合度マトリックスを上記出力装置に出力する出力手段と、
を備えたことを特徴とするＲＮＡ配列解析装置。
【請求項６】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、
を備え、
上記制御装置において実行される、
利用者が上記入力装置を介して入力した二次構造を特定したいＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して、上記生成文法毎に構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された各々の上記構文解析木に対する上記適合度が高い順に上記構文解析木をソートするソートステップと、
上記ソートステップによりソートされた上記構文解析木と上記適合度を上記出力装置に出力する出力ステップと、
を備えたことを特徴とするＲＮＡ配列解析方法。
【請求項７】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、
複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、
を備え、
上記制御装置において実行される、
上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出ステップと、
上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出ステップにて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分をマークすることにより、上記ＲＮＡ配列間で共通に有する構造トポロジーを可視化する共通構造マトリックス作成ステップと、
上記共通構造マトリックス作成ステップにより作成された上記二次元マトリックスを上記出力装置に出力する出力ステップと、
を備えたことを特徴とするＲＮＡ配列解析方法。
【請求項８】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、
を備え、
上記制御装置において実行される、
利用者が上記入力装置を介して入力したＤＮＡ配列から転写されるＲＮＡ配列を作成するＲＮＡ配列作成ステップと、
上記ＲＮＡ配列作成ステップにより作成された上記ＲＮＡ配列に対して、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列に対応する上記ＤＮＡ配列を遺伝子の候補として予測する遺伝子予測ステップと、
上記遺伝子予測ステップにて予測された上記ＤＮＡ配列と上記構造解析木を上記出力装置に出力する出力ステップと、
を備えたことを特徴とするＲＮＡ配列解析方法。
【請求項９】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、
複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、
を備え、
上記制御装置において実行される、
上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された上記適合度に基づいて上記複数のＲＮＡ配列の間の類似度を計算する類似度計算ステップと、
を備えたことを特徴とするＲＮＡ配列解析方法。
【請求項１０】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、
複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、
を備え、
上記制御装置において実行される、
上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出ステップと、
上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出ステップにて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分に上記適合度を表示する適合度マトリックスを作成する適合度マトリックス作成ステップと、
上記適合度マトリックス作成ステップにて作成された上記適合度マトリックスについて、上記構造トポロジー毎に対応する全ての上記適合度の総和を計算し、当該総和に基づいて上記構造トポロジーをソートする共通構造抽出ステップと、
上記共通構造抽出ステップによりソートされた上記適合度マトリックスを上記出力装置に出力する出力ステップと、
を備えたことを特徴とするＲＮＡ配列解析方法。
【請求項１１】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、
を備え、
上記制御装置において実行される、
利用者が上記入力装置を介して入力した二次構造を特定したいＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して、上記生成文法毎に構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された各々の上記構文解析木に対する上記適合度が高い順に上記構文解析木をソートするソートステップと、
上記ソートステップによりソートされた上記構文解析木と上記適合度を上記出力装置に出力する出力ステップと、
を備えたことを特徴とするプログラム。
【請求項１２】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、
複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、
を備え、
上記制御装置において実行される、
上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出ステップと、
上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出ステップにて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分をマークすることにより、上記ＲＮＡ配列間で共通に有する構造トポロジーを可視化する共通構造マトリックス作成ステップと、
上記共通構造マトリックス作成ステップにより作成された上記二次元マトリックスを上記出力装置に出力する出力ステップと、
を備えたことを特徴とするプログラム。
【請求項１３】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、
を備え、
上記制御装置において実行される、
利用者が上記入力装置を介して入力したＤＮＡ配列から転写されるＲＮＡ配列を作成するＲＮＡ配列作成ステップと、
上記ＲＮＡ配列作成ステップにより作成された上記ＲＮＡ配列に対して、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列に対応する上記ＤＮＡ配列を遺伝子の候補として予測する遺伝子予測ステップと、
上記遺伝子予測ステップにて予測された上記ＤＮＡ配列と上記構造解析木を上記出力装置に出力する出力ステップと、
を備えたことを特徴とするプログラム。
【請求項１４】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、
複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、
を備え、
上記制御装置において実行される、
上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された上記適合度に基づいて上記複数のＲＮＡ配列の間の類似度を計算する類似度計算ステップと、
を備えたことを特徴とするプログラム。
【請求項１５】
制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、
上記記憶装置は、
ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、
複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、
を備え、
上記制御装置において実行される、
上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、
上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、
上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出ステップと、
上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出ステップにて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分に上記適合度を表示する適合度マトリックスを作成する適合度マトリックス作成ステップと、
上記適合度マトリックス作成ステップにて作成された上記適合度マトリックスについて、上記構造トポロジー毎に対応する全ての上記適合度の総和を計算し、当該総和に基づいて上記構造トポロジーをソートする共通構造抽出ステップと、
上記共通構造抽出ステップによりソートされた上記適合度マトリックスを上記出力装置に出力する出力ステップと、
を備えたことを特徴とするプログラム。
【請求項１６】
上記請求項１１〜１５のいずれか一つに記載されたプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体に関し、特に、ＲＮＡの二次構造を予測し、また、ＤＮＡ配列から遺伝子部分を予測するＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体に関する。
【０００２】
【従来の技術】
ＲＮＡ配列は、Ａ（アデニン）、Ｃ（シトシン）、Ｇ（グアニン）、Ｕ（ウラシル）の４種の塩基により構成されるが、その一部は回文言語のような入れ子の状態となり、相補的な塩基同士（ＡとＵ、ＧとＣ、稀にＧとＵ）が結合して二次構造を構成している。ＲＮＡ配列の二次構造は、図１に示すように、多種の構造トポロジーを有している。ここで、積み重ねられた塩基対の連続領域をステム（ｓｔｅｍ）と呼び、また、塩基対で挟まれた一本鎖の部分配列をループ（ｌｏｏｐ）と呼ぶ。ステムの端のループをヘアピンループという（図１のａ）。ステムの中にある一本鎖の塩基は、それがステムの片側だけにあるときバルジループ（ｂｕｌｇｅ  ｌｏｏｐ）と呼び（図１のｂ）、ステムの両側にあるときは内側ループ（ｉｎｔｅｒｎａｌ  ｌｏｏｐ）と呼ぶ（図１のｃ）。放射状に３個以上のステムが出ているものをマルチループ（ｍｕｌｔｉ−ｂｒａｎｃｈｅｄ  ｌｏｏｐ）と呼ぶ。また、入れ子ではない塩基対があるとき、シュードノット（ｐｓｅｕｄｏｋｎｏｔｓ）と呼ぶ（図１のｄ）。
【０００３】
ここで、ＲＮＡ配列を形式文法（生成文法）により構文解析することによりその二次構造を予測する手法が存在するが、正規文法では回文言語を記述することができないため、一般に、ＲＮＡ二次構造解析においては、木文法（ｔｒｅｅ  ａｄｊｏｉｎｉｎｇ  ｇｒａｍｍａｒｓ）や、文脈自由文法（ＣＦＧ）などを用いて構文解析を行い構造モデリング（構造トポロジー表現）を求める手法が考案されている。
【０００４】
例えば、Ｙａｓｕｏ  Ｕｅｍｕｒａ等著「Ｔｒｅｅ  ａｄｊｏｉｎｉｎｇ  ｇｒａｍｍａｒｓ  ｆｏｒ  ＲＮＡ  ｓｔｒｕｃｔｕｒｅ  ｐｒｅｄｉｃｔｉｏｎ（Ｔｈｅｏｒｅｔｉｃａｌ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２１０  １９９９  ２７７ｐ−３０３ｐ）」（以下「文献１」という）には、木文法による構造モデリングと、パーザ（ｐａｓｅｒ）を利用したエネルギー極小化によるＲＮＡ二次構造予測方法が開示されている。
【０００５】
また、Ｅｌｅｎａ  Ｒｉｖａｓ  ａｎｄ  Ｓｅａｎ  Ｒ．Ｒｄｄｙ著「Ｔｈｅｌａｎｇｕａｇｅ  ｏｆ  ＲＮＡ：  ａ  ｆｏｒｍａｌ  ｇｒａｍｍａｒ  ｔｈａｔ  ｉｎｃｌｕｄｅｓ  ｐｓｅｕｄｏｋｎｏｔｓ  （ＢＩＯＩＮＦＯＲＭＡＴＩＣＳ  ｖｏｌ．１６  ｎｏ．４  ２０００  ３３４ｐ−３４０ｐ）」（以下「文献２」という）には、Ｃｒｏｓｓｅｄ−ｉｎｔｅｒａｃｔｉｏｎ  Ｇｒａｍｍａｒｓなどの独自の拡張を施した文脈自由文法（ＣＦＧ）による構造モデリングと、パーザを利用したエネルギー極小化によるＲＮＡ二次構造予測方法が開示されている。
【０００６】
また、Ｍｉｃｈａｅｌ  Ｚｕｋｅｒ著「Ｐｒｅｄｉｃｔｉｏｎ  ｏｆ  ＲＮＡＳｅｃｏｎｄａｒｙ  Ｓｔｒｕｃｔｕｒｅ  ｂｙ  Ｅｎｅｒｇｙ  ｍｉｎｉｍｉｚａｔｉｏｎ（Ｊｕｌｙ  ８，１９９６）」（以下「文献３」という）には、形式文法やパーザを用いず動的計画法（Ｄｙｎａｍｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ）によってＲＮＡ二次構造を予測する方法を用いたＲＮＡ配列解析システムであるＭｆｏｌｄ（製品名）が開示されている。これらの文献では、形式文法や動的計画法などの手法と、エネルギー極小化手法とを組み合わせることによってＲＮＡ二次構造予測精度を高めている。
【０００７】
図２は、従来技術によるＲＮＡの二次構造がステムループをとる場合の構文解析木の一例を示す図である。図２のａに示すＲＮＡ配列の二次構造を図２のｂに、また、構文解析木を図２のｃに示している。ここで、部分木（ｓｕｂｔｒｅｅ）は、内部の節を根とする構文解析木の断片である。ＲＮＡ二次構造の構造トポロジーについて構文解析木を作成して構文解析を行うことにより二次構造解析を行う技術が研究されており、主要な構造トポロジーに対する文法が既知となっている。
【０００８】
図３は、従来技術によるＲＮＡ二次構造の構造トポロジーについて、文法が固定されるとそれに対応した構造トポロジーが規定される（逆もまた可）ことを示す概念図である。ここで、生成文法（以下単に「文法」という）は、有限個の記号と、有限個の生成規則Ｐ（ｐｒｏｄｕｃｔｉｏｎ  ｒｕｌｅ）から成る。記号には、抽象的な非終端記号Ｎ（ｎｏｎｔｅｒｍｉｎａｌ  ｓｙｍｂｏｌ）と、観測文字列に実際に現れる終端記号Ｔ（ｔｅｒｍｉｎａｌ  ｓｙｍｂｏｌ）の２種類がある。終端記号Ｔは、ＲＮＡ配列の場合にはＡ、Ｔ、Ｇ、Ｃの４文字である。図３に示すように、各構造トポロジーについてそれぞれ対応する文法を定義することができる。
【０００９】
また、図４は、従来技術である木文法パーザを用いて、既知の文法からＲＮＡ配列の構文解析木を導出する場合の一例を示す図である。まず、構造未知のＲＮＡ配列を木文法パーザに入力する。ここで、木文法パーザは、入力された既知の木文法に従ってＲＮＡ配列の構文解析を行い構文解析木を導出する機能、および、導出された構文解析木について、ループや、塩基対とその他の二次構造要素のそれぞれの自由エネルギーの合計などを計算することにより平衡自由エネルギー（ΔＧ）などの値を求める機能などを有する（文献１から３参照）。
【００１０】
ここで、木文法パーザは必ずしも構文解析木を導出するわけではなく、入力したＲＮＡ配列が当該文法に適合しない場合（パーズが成功しない場合）には構文解析木を導出しない（すなわち、構文解析木は０個になる）。また、複数個の構文解析木が導出された場合には、エネルギー計算の結果、極小の自由エネルギーとなる１つの構文解析木を選択する。このとき、木文法パーザは導出過程の各段階において自由エネルギー極小な部分構造を見つけていくことができる。また、木文法パーザはエネルギー準最適な構文も出力することができる。このように、木文法パーザは、構文解析（パーズ）の途中でエネルギー計算を行うことにより、高速化と精度向上を実現している。
【００１１】
【発明が解決しようとする課題】
しかしながら、従来の木文法パーザなどにより構文解析とエネルギー計算を行う手法を用いたＲＮＡ二次構造予測システムにおいては、ＲＮＡ配列や抽出した文法を統合的に管理し、集積した文法やＲＮＡ配列を用いて二次構造予測などをより効率的に行うものは存在しなかったという問題点がある。
【００１２】
また、与えられた特定の二次構造を取り得るようなＲＮＡ配列を検索するような方法は存在しなかったという問題点がある。
【００１３】
また、複数のＲＮＡ配列に共通な二次構造を簡易に抽出する方法は存在しなかったという問題点がある。
【００１４】
また、ＲＮＡ配列からＲＮＡ二次構造に基づく類似度を簡易に求める方法は存在しなかったという問題点がある。
【００１５】
さらに、ＤＮＡ配列から遺伝子部分を発見するための手法としては、ホモロジー検索やモチーフ検索などを利用する手法が一般的であるが、未知の遺伝子部分の発見には利用できないという問題点がある。ここで、従来技術で説明したように、ＲＮＡ配列の構造トポロジーを予測可能な生成文法が求められているが、既知の生成文法により導出された構文解析木を用いた遺伝子発見方法は存在しなかったという問題点がある。
【００１６】
このように、従来のシステム等は数々の問題点を有しており、その結果、システムの利用者および管理者のいずれにとっても、利便性が悪く、また、利用効率が悪いものであった。
本発明は上記問題点に鑑みてなされたもので、ＲＮＡ配列や抽出した文法を統合的に管理し、集積した文法やＲＮＡ配列を用いて二次構造予測や新たな解析手法などをより効率的に行うことのできる、ＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体を提供することを目的としている。
【００１７】
【課題を解決するための手段】
このような目的を達成するため、請求項１に記載のＲＮＡ配列解析装置は、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、を備え、上記制御装置は、利用者が上記入力装置を介して入力した二次構造を特定したいＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して、上記生成文法毎に構文解析木を導出する構文解析手段と、上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、上記適合度計算手段により計算された各々の上記構文解析木に対する上記適合度が高い順に上記構文解析木をソートするソート手段と、上記ソート手段によりソートされた上記構文解析木と上記適合度を上記出力装置に出力する出力手段と、を備えたことを特徴とする。
【００１８】
この装置によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する。制御装置は、利用者が入力装置を介して入力した二次構造を特定したいＲＮＡ配列を、記憶された複数の生成文法に適用して、生成文法毎に構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された各々の構文解析木に対する適合度が高い順に構文解析木をソートし、ソートされた構文解析木と適合度を出力装置に出力するので、一配列に対して多文法で構文解析を行うことができるようになる。すなわち、各生成文法に対してそれぞれ構文解析し適合度計算を行い適合度を得る。その結果、生成文法ごとに適合度が得られることになり、それらの適合度をソートすることによって生成文法に順位を付ける。これにより、生成文法に対する構造トポロジーにも順位が付けられることになるので、最終的にＲＮＡ配列が取り得る可能性の高い順に構造トポロジーを確認することができるようになる。
【００２１】
また、請求項２に記載のＲＮＡ配列解析装置は、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、を備え、上記制御装置は、上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析手段と、上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、上記適合度計算手段により計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出手段と、上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出手段にて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分をマークすることにより、上記ＲＮＡ配列間で共通に有する構造トポロジーを可視化する共通構造マトリックス作成手段と、上記共通構造マトリックス作成手段により作成された上記二次元マトリックスを上記出力装置に出力する出力手段と、を備えたことを特徴とする。
【００２２】
この装置によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶し、複数のＲＮＡ配列を記憶する。制御装置は、記憶されたＲＮＡ配列から利用者が入力装置を介して選択した複数のＲＮＡ配列を、記憶された複数の生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出し、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と、当該ＲＮＡ配列の構文解析木を導出した生成文法の構造トポロジーに対応する格子部分をマークすることにより、ＲＮＡ配列間で共通に有する構造トポロジーを可視化し、作成された二次元マトリックスを出力装置に出力するので、ＲＮＡ配列間の共通構造を容易に発見することができるようになる。
【００２３】
また、請求項３に記載のＲＮＡ配列解析装置は、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、を備え、上記制御装置は、利用者が上記入力装置を介して入力したＤＮＡ配列から転写されるＲＮＡ配列を作成するＲＮＡ配列作成手段と、上記ＲＮＡ配列作成手段により作成された上記ＲＮＡ配列に対して、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析手段と、上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、上記適合度計算手段により計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列に対応する上記ＤＮＡ配列を遺伝子の候補として予測する遺伝子予測手段と、上記遺伝子予測手段にて予測された上記ＤＮＡ配列と上記構造解析木を上記出力装置に出力する出力手段と、を備えたことを特徴とする。
【００２４】
この装置によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する。制御装置は、利用者が入力装置を介して入力したＤＮＡ配列から転写されるＲＮＡ配列を作成し、作成されたＲＮＡ配列に対して、記憶された複数の生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列に対応するＤＮＡ配列を遺伝子の候補として予測し、予測されたＤＮＡ配列と構造解析木を出力装置に出力するので、ＤＮＡ配列のうち既知のトポロジーを有する可能性のあるＲＮＡ配列に対応する部分について、遺伝子部分である可能性があることを予測することができるようになる。
【００２５】
また、請求項４に記載のＲＮＡ配列解析装置は、制御装置と記憶装置と入力装置とを少なくとも備えたＲＮＡ配列解析装置において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、を備え、上記制御装置は、上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析手段と、上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、上記適合度計算手段により計算された上記適合度に基づいて上記複数のＲＮＡ配列の間の類似度を計算する類似度計算手段と、を備えたことを特徴とする。
【００２６】
この装置によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶し、複数のＲＮＡ配列を記憶する。制御装置は、記憶されたＲＮＡ配列から利用者が入力装置を介して選択した複数のＲＮＡ配列を、記憶された複数の生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度に基づいて複数のＲＮＡ配列の間の類似度を計算するので、ＲＮＡ構造の類似度を容易に求めることができるようになる。
【００２７】
また、請求項５に記載のＲＮＡ配列解析装置は、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、を備え、上記制御装置は、上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析手段と、上記構文解析手段にて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算手段と、上記適合度計算手段により計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出手段と、上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出手段にて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分に上記適合度を表示する適合度マトリックスを作成する適合度マトリックス作成手段と、上記適合度マトリックス作成手段にて作成された上記適合度マトリックスについて、上記構造トポロジー毎に対応する全ての上記適合度の総和を計算し、当該総和に基づいて上記構造トポロジーをソートする共通構造抽出手段と、上記共通構造抽出手段によりソートされた上記適合度マトリックスを上記出力装置に出力する出力手段と、を備えたことを特徴とする。
【００２８】
この装置によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶し、複数のＲＮＡ配列を記憶する。制御装置は、記憶されたＲＮＡ配列から利用者が入力装置を介して選択した複数のＲＮＡ配列を、記憶された複数の上記生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出し、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と、当該ＲＮＡ配列の構文解析木を導出した生成文法の構造トポロジーに対応する格子部分に適合度を表示する適合度マトリックスを作成し、作成された適合度マトリックスについて、構造トポロジー毎に対応する全ての適合度の総和を計算し、当該総和に基づいて構造トポロジーをソートし、ソートされた適合度マトリックスを出力装置に出力するので、共通の構造を持つＲＮＡ配列を容易に発見することができるようになる。
【００２９】
また、本発明はＲＮＡ配列解析方法に関するものであり、請求項６に記載のＲＮＡ配列解析方法は、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、を備え、上記制御装置は、利用者が上記入力装置を介して入力した二次構造を特定したいＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して、上記生成文法毎に構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された各々の上記構文解析木に対する上記適合度が高い順に上記構文解析木をソートするソートステップと、上記ソートステップによりソートされた上記構文解析木と上記適合度を上記出力装置に出力する出力ステップと、を備えたことを特徴とする。
【００３０】
この方法によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する。制御装置は、利用者が入力装置を介して入力した二次構造を特定したいＲＮＡ配列を、記憶された複数の生成文法に適用して、生成文法毎に構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された各々の構文解析木に対する適合度が高い順に構文解析木をソートし、ソートされた構文解析木と適合度を出力装置に出力するので、一配列に対して多文法で構文解析を行うことができるようになる。すなわち、各生成文法に対してそれぞれ構文解析し適合度計算を行い適合度を得る。その結果、生成文法ごとに適合度が得られることになり、それらの適合度をソートすることによって生成文法に順位を付ける。これにより、生成文法に対する構造トポロジーにも順位が付けられることになるので、最終的にＲＮＡ配列が取り得る可能性の高い順に構造トポロジーを確認することができるようになる。
【００３３】
また、請求項７に記載のＲＮＡ配列解析方法は、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、を備え、上記制御装置は、上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出ステップと、上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出ステップにて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分をマークすることにより、上記ＲＮＡ配列間で共通に有する構造トポロジーを可視化する共通構造マトリックス作成ステップと、上記共通構造マトリックス作成ステップにより作成された上記二次元マトリックスを上記出力装置に出力する出力ステップと、を備えたことを特徴とする。
【００３４】
この方法によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶し、複数のＲＮＡ配列を記憶する。制御装置は、記憶されたＲＮＡ配列から利用者が入力装置を介して選択した複数のＲＮＡ配列を、記憶された複数の生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出し、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と、当該ＲＮＡ配列の構文解析木を導出した生成文法の構造トポロジーに対応する格子部分をマークすることにより、ＲＮＡ配列間で共通に有する構造トポロジーを可視化し、作成された二次元マトリックスを出力装置に出力するので、ＲＮＡ配列間の共通構造を容易に発見することができるようになる。
【００３５】
また、請求項８に記載のＲＮＡ配列解析方法は、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、を備え、上記制御装置は、利用者が上記入力装置を介して入力したＤＮＡ配列から転写されるＲＮＡ配列を作成するＲＮＡ配列作成ステップと、上記ＲＮＡ配列作成ステップにより作成された上記ＲＮＡ配列に対して、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列に対応する上記ＤＮＡ配列を遺伝子の候補として予測する遺伝子予測ステップと、上記遺伝子予測ステップにて予測された上記ＤＮＡ配列と上記構造解析木を上記出力装置に出力する出力ステップと、を備えたことを特徴とする。
【００３６】
この方法によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する。制御装置は、利用者が入力装置を介して入力したＤＮＡ配列から転写されるＲＮＡ配列を作成し、作成されたＲＮＡ配列に対して、記憶された複数の生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列に対応するＤＮＡ配列を遺伝子の候補として予測し、予測されたＤＮＡ配列と構造解析木を出力装置に出力するので、ＤＮＡ配列のうち既知のトポロジーを有する可能性のあるＲＮＡ配列に対応する部分について、遺伝子部分である可能性があることを予測することができるようになる。
【００３７】
また、請求項９に記載のＲＮＡ配列解析方法は、制御装置と記憶装置と入力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、を備え、上記制御装置は、上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された上記適合度に基づいて上記複数のＲＮＡ配列の間の類似度を計算する類似度計算ステップと、を備えたことを特徴とする。
【００３８】
この方法によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶し、複数のＲＮＡ配列を記憶する。制御装置は、記憶されたＲＮＡ配列から利用者が入力装置を介して選択した複数のＲＮＡ配列を、記憶された複数の生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度に基づいて複数のＲＮＡ配列の間の類似度を計算するので、ＲＮＡ構造の類似度を容易に求めることができるようになる。
【００３９】
また、請求項１０に記載のＲＮＡ配列解析方法は、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるＲＮＡ配列解析方法において、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、を備え、上記制御装置は、上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出ステップと、上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出ステップにて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分に上記適合度を表示する適合度マトリックスを作成する適合度マトリックス作成ステップと、上記適合度マトリックス作成ステップにて作成された上記適合度マトリックスについて、上記構造トポロジー毎に対応する全ての上記適合度の総和を計算し、当該総和に基づいて上記構造トポロジーをソートする共通構造抽出ステップと、上記共通構造抽出ステップによりソートされた上記適合度マトリックスを上記出力装置に出力する出力ステップと、を備えたことを特徴とする。
【００４０】
この方法によれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶し、複数のＲＮＡ配列を記憶する。制御装置は、記憶されたＲＮＡ配列から利用者が入力装置を介して選択した複数のＲＮＡ配列を、記憶された複数の上記生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出し、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と、当該ＲＮＡ配列の構文解析木を導出した生成文法の構造トポロジーに対応する格子部分に適合度を表示する適合度マトリックスを作成し、作成された適合度マトリックスについて、構造トポロジー毎に対応する全ての適合度の総和を計算し、当該総和に基づいて構造トポロジーをソートし、ソートされた適合度マトリックスを出力装置に出力するので、共通の構造を持つＲＮＡ配列を容易に発見することができるようになる。
【００４１】
また、本発明はＲＮＡ配列解析方法をコンピュータに実行させるプログラムに関するものであり、請求項１１に記載のプログラムは、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、を備え、上記制御装置は、利用者が上記入力装置を介して入力した二次構造を特定したいＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して、上記生成文法毎に構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された各々の上記構文解析木に対する上記適合度が高い順に上記構文解析木をソートするソートステップと、上記ソートステップによりソートされた上記構文解析木と上記適合度を上記出力装置に出力する出力ステップと、を備えたことを特徴とする。
【００４２】
このプログラムによれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する。制御装置は、利用者が入力装置を介して入力した二次構造を特定したいＲＮＡ配列を、記憶された複数の生成文法に適用して、生成文法毎に構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された各々の構文解析木に対する適合度が高い順に構文解析木をソートし、ソートされた構文解析木と適合度を出力装置に出力するので、一配列に対して多文法で構文解析を行うことができるようになる。すなわち、各生成文法に対してそれぞれ構文解析し適合度計算を行い適合度を得る。その結果、生成文法ごとに適合度が得られることになり、それらの適合度をソートすることによって生成文法に順位を付ける。これにより、生成文法に対する構造トポロジーにも順位が付けられることになるので、最終的にＲＮＡ配列が取り得る可能性の高い順に構造トポロジーを確認することができるようになる。
【００４５】
また、請求項１２に記載のプログラムは、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、を備え、上記制御装置は、上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出ステップと、上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出ステップにて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分をマークすることにより、上記ＲＮＡ配列間で共通に有する構造トポロジーを可視化する共通構造マトリックス作成ステップと、上記共通構造マトリックス作成ステップにより作成された上記二次元マトリックスを上記出力装置に出力する出力ステップと、を備えたことを特徴とする。
【００４６】
このプログラムによれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶し、複数のＲＮＡ配列を記憶する。制御装置は、記憶されたＲＮＡ配列から利用者が入力装置を介して選択した複数のＲＮＡ配列を、記憶された複数の生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出し、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と、当該ＲＮＡ配列の構文解析木を導出した生成文法の構造トポロジーに対応する格子部分をマークすることにより、ＲＮＡ配列間で共通に有する構造トポロジーを可視化し、作成された二次元マトリックスを出力装置に出力するので、ＲＮＡ配列間の共通構造を容易に発見することができるようになる。
【００４７】
また、請求項１３に記載のプログラムは、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段、を備え、上記制御装置は、利用者が上記入力装置を介して入力したＤＮＡ配列から転写されるＲＮＡ配列を作成するＲＮＡ配列作成ステップと、上記ＲＮＡ配列作成ステップにより作成された上記ＲＮＡ配列に対して、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列に対応する上記ＤＮＡ配列を遺伝子の候補として予測する遺伝子予測ステップと、上記遺伝子予測ステップにて予測された上記ＤＮＡ配列と上記構造解析木を上記出力装置に出力する出力ステップと、を備えたことを特徴とする。
【００４８】
このプログラムによれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する。制御装置は、利用者が入力装置を介して入力したＤＮＡ配列から転写されるＲＮＡ配列を作成し、作成されたＲＮＡ配列に対して、記憶された複数の生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列に対応するＤＮＡ配列を遺伝子の候補として予測し、予測されたＤＮＡ配列と構造解析木を出力装置に出力するので、ＤＮＡ配列のうち既知のトポロジーを有する可能性のあるＲＮＡ配列に対応する部分について、遺伝子部分である可能性があることを予測することができるようになる。
【００４９】
また、請求項１４に記載のプログラムは、制御装置と記憶装置と入力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、を備え、上記制御装置は、上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された上記適合度に基づいて上記複数のＲＮＡ配列の間の類似度を計算する類似度計算ステップと、を備えたことを特徴とする。
【００５０】
このプログラムによれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶し、複数のＲＮＡ配列を記憶する。制御装置は、記憶されたＲＮＡ配列から利用者が入力装置を介して選択した複数のＲＮＡ配列を、記憶された複数の生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度に基づいて複数のＲＮＡ配列の間の類似度を計算するので、ＲＮＡ構造の類似度を容易に求めることができるようになる。
【００５１】
また、請求項１５に記載のプログラムは、制御装置と記憶装置と入力装置と出力装置とを少なくとも備えたＲＮＡ配列解析装置において実行されるプログラムにおいて、上記記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶する文法格納手段と、複数のＲＮＡ配列を記憶したＲＮＡ配列格納手段と、を備え、上記制御装置は、上記ＲＮＡ配列格納手段にて記憶された上記ＲＮＡ配列から利用者が上記入力装置を介して選択した複数の上記ＲＮＡ配列を、上記文法格納手段にて記憶された上記複数の上記生成文法に適用して構文解析木を導出する構文解析ステップと、上記構文解析ステップにて導出された各々の上記構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行う適合度計算ステップと、上記適合度計算ステップにより計算された上記適合度のうち予め定めた条件を満たす適合度である上記構文解析木を導出した上記ＲＮＡ配列を抽出する抽出ステップと、上記構造トポロジーと上記ＲＮＡ配列とを二次元マトリックスで表示し、上記二次元マトリックスにおいて上記抽出ステップにて抽出された上記ＲＮＡ配列と、当該ＲＮＡ配列の上記構文解析木を導出した上記生成文法の上記構造トポロジーに対応する格子部分に上記適合度を表示する適合度マトリックスを作成する適合度マトリックス作成ステップと、上記適合度マトリックス作成ステップにて作成された上記適合度マトリックスについて、上記構造トポロジー毎に対応する全ての上記適合度の総和を計算し、当該総和に基づいて上記構造トポロジーをソートする共通構造抽出ステップと、上記共通構造抽出ステップによりソートされた上記適合度マトリックスを上記出力装置に出力する出力ステップと、を備えたことを特徴とする。
【００５２】
このプログラムによれば、記憶装置は、ＲＮＡ二次構造の構造トポロジーに適合する複数の生成文法を記憶し、複数のＲＮＡ配列を記憶する。制御装置は、記憶されたＲＮＡ配列から利用者が入力装置を介して選択した複数のＲＮＡ配列を、記憶された複数の上記生成文法に適用して構文解析木を導出し、導出された各々の構文解析木に対して、塩基対数、平衡自由エネルギー、導出確率のうち少なくとも一つに基づいて適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出し、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と、当該ＲＮＡ配列の構文解析木を導出した生成文法の構造トポロジーに対応する格子部分に適合度を表示する適合度マトリックスを作成し、作成された適合度マトリックスについて、構造トポロジー毎に対応する全ての適合度の総和を計算し、当該総和に基づいて構造トポロジーをソートし、ソートされた適合度マトリックスを出力装置に出力するので、共通の構造を持つＲＮＡ配列を容易に発見することができるようになる。
【００５３】
また、本発明は記録媒体に関するものであり、請求項１６に記載の記録媒体は、上記請求項１１から１５のいずれか一つに記載されたプログラムを記録したことを特徴とする。
【００５４】
この記録媒体によれば、当該記録媒体に記録されたプログラムをコンピュータに読み取らせて実行することによって、請求項１１から１５のいずれか一つに記載されたプログラムをコンピュータを利用して実現することができ、これら各プログラムと同様の効果を得ることができる。
【００５５】
【発明の実施の形態】
以下に、本発明にかかるＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
特に、以下の実施の形態においては、本発明を、木文法に適用した例について説明するが、この場合に限られず、全ての生成文法において、同様に適用することができる。
【００５６】
［本システムの概要］
以下、本システムの概要について説明し、その後、本システムの構成および処理等について詳細に説明する。
このシステムは、概略的に、以下の基本的特徴を有する。すなわち、本システムのＲＮＡ配列解析装置は、ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納し、ＲＮＡ配列を生成文法に適用して構文解析木を導出し、導出された構文解析木に対して適合度を計算し、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を適合度が高い順にソートし、ソートされた構文解析木をＲＮＡ配列の二次構造の候補として出力する。ここで、生成文法は、木文法、文脈自由文法などを含むが、シュードノットを表現するためには木文法が最も適しているため、木文法を用いることが好ましい。
【００５７】
また、本装置は、導出された構文解析木に対して適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を上記構造トポロジーの二次構造を持つＲＮＡ配列の候補として出力する。
【００５８】
また、本装置は、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出し、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と構造トポロジーに対応する格子部分をマークすることにより、ＲＮＡ配列間で共通に有する構造トポロジーを可視化する。
【００５９】
また、本装置は、利用者が入力したＤＮＡ配列から転写されるＲＮＡ配列を作成し、作成されたＲＮＡ配列に対して生成文法を適用して構文解析木を導出し、導出された構文解析木に対して適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列に対応するＤＮＡ配列部分を遺伝子の候補として予測する。
【００６０】
さらに、本装置は、ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納し、ＲＮＡ配列を生成文法に適用して構文解析木を導出し、導出された構文解析木に対して適合度の計算を行い、計算された適合度に基づいてＲＮＡ配列間の類似度を計算する。
【００６１】
［システム構成］
まず、本システムの構成について説明する。図５は、本発明が適用される本システムの構成の一例を示すブロック図であり、該構成のうち本発明に関係する部分のみを概念的に示している。本システムは、概略的に、配列情報を解析するＲＮＡ配列解析装置であるＲＮＡ配列解析装置１００と、配列情報等に関する外部データベースやホモロジー検索用の外部分析プログラム等を提供する外部システム２００とを、ネットワーク３００を介して通信可能に接続して構成されている。
【００６２】
図５においてネットワーク３００は、ＲＮＡ配列解析装置１００と外部システム２００とを相互に接続する機能を有し、例えば、インターネット等である。
【００６３】
図５において外部システム２００は、ネットワーク３００を介して、ＲＮＡ配列解析装置１００と相互に接続され、利用者に対して配列情報等に関する外部データベースやホモロジー検索やモチーフ検索等の外部分析プログラムを実行するウェブサイトを提供する機能を有する。
【００６４】
ここで、外部システム２００は、ＷＥＢサーバやＡＳＰサーバ等として構成してもよく、そのハードウェア構成は、一般に市販されるワークステーション、パーソナルコンピュータ等の情報処理装置およびその付属装置により構成してもよい。また、外部システム２００の各機能は、外部システム２００のハードウェア構成中のＣＰＵ、ディスク装置、メモリ装置、入力装置、出力装置、通信制御装置等およびそれらを制御するプログラム等により実現される。
【００６５】
図５においてＲＮＡ配列解析装置１００は、概略的に、ＲＮＡ配列解析装置１００の全体を統括的に制御するＣＰＵ等の制御部１０２、通信回線等に接続されるルータ等の通信装置（図示せず）に接続される通信制御インターフェース部１０４、入力装置１１２および出力装置１１４に接続される入出力制御インターフェース部１０８、および、各種のデータベースやテーブル（ＲＮＡ配列データベース１０６ａ〜共通構造マトリックス１０６ｃ）を格納する記憶部１０６を備えて構成されており、これら各部は任意の通信路を介して通信可能に接続されている。さらに、このＲＮＡ配列解析装置１００は、ルータ等の通信装置および専用線等の有線または無線の通信回線を介して、ネットワーク３００に通信可能に接続されている。
【００６６】
記憶部１０６に格納される各種のデータベース（ＲＮＡ配列データベース１０６ａ〜共通構造マトリックス１０６ｃ）は、固定ディスク装置等のストレージ手段であり、各種処理に用いる各種のプログラムやテーブルやファイルやデータベースやウェブページ用ファイル等を格納する。
【００６７】
これら記憶部１０６の各構成要素のうち、ＲＮＡ配列データベース１０６ａは、ＲＮＡ配列を格納したデータベースである。ＲＮＡ配列データベース１０６ａは、インターネットを経由してアクセスする外部のＲＮＡ配列データベースであってもよく、また、これらのデータベースをコピーしたり、オリジナルの配列情報を格納したり、さらに独自のアノテーション情報等を付加したりして作成したインハウスデータベースであってもよい。また、ＲＮＡ配列データベース１０６ａは、ｃＤＮＡ等のＤＮＡ配列データベースに基づいて予め生成された、あるいは必要時に動的に生成されたＲＮＡ配列を格納したものでもよい。
【００６８】
また、文法データベース１０６ｂは、ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納する文法格納手段である。ここで、図６は、文法データベース１０６ｂに格納される情報の一例を示す図である。図６に示すように、文法データベース１０６ｂは、構造トポロジーと、その構造トポロジーに対応する文法とを対応付けて格納する。ここで、文法データベース１０６ｂには、図６に示したように、構造トポロジーと文法とが１対１で対応するようにしてもよく、また、複数のトポロジーが結合した文法（例えば、シュードノットとヘアピンループとを両方持つトポロジーなど）や、特徴的な構造を有するＲＮＡ用の文法（例えば、ｒＲＮＡに特有の構造トポロジーなど）や、所定のカテゴリーのＲＮＡが共通で備えるトポロジー用の文法や、全てのＲＮＡに適合する文法などを規定してもよい。
【００６９】
また、共通構造マトリックス１０６ｃは、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示するためのテーブル（記憶領域）である。
【００７０】
また、図５において、通信制御インターフェース部１０４は、ＲＮＡ配列解析装置１００とネットワーク３００（またはルータ等の通信装置）との間における通信制御を行う。すなわち、通信制御インターフェース部１０４は、他の端末と通信回線を介してデータを通信する機能を有する。
【００７１】
また、図５において、入出力制御インターフェース部１０８は、入力装置１１２や出力装置１１４の制御を行う。ここで、出力装置１１４としては、モニタ（家庭用テレビを含む）の他、スピーカを用いることができる（なお、以下においては出力装置をモニタとして記載する）。また、入力装置１１２としては、キーボード、マウス、および、マイク等を用いることができる。また、モニタも、マウスと協働してポインティングデバイス機能を実現する。
【００７２】
また、図５において、制御部１０２は、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）等の制御プログラム、各種の処理手順等を規定したプログラム、および所要データを格納するための内部メモリを有し、これらのプログラム等により、種々の処理を実行するための情報処理を行う。制御部１０２は、機能概念的に、構造予測部１０２ａ、類似度計算部１０２ｄ、共通構造マトリックス作成部１０２ｆ、および、遺伝子予測部１０２ｇを備えて構成されている。
【００７３】
このうち、構造予測部１０２ａは、入力された既知の文法に従ってＲＮＡ配列の構文解析を行い構文解析木を導出する機能（構文解析部１０２ｂ）、および、導出された構文解析木に対して適合度の計算を行う機能（適合度計算部１０２ｃ）などを有する。
【００７４】
また、類似度計算部１０２ｄは、複数のＲＮＡ配列間の類似度を計算する類似度計算手段である。
【００７５】
また、共通構造マトリックス作成部１０２ｆは、適合度計算手段により計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出する抽出手段、および、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出手段にて抽出されたＲＮＡ配列と構造トポロジーに対応する格子部分をマークすることにより、ＲＮＡ配列間で共通に有する構造トポロジーを可視化する共通構造マトリックス作成手段、二次元マトリックスにおいて抽出手段にて抽出されたＲＮＡ配列と構造トポロジーに対応する格子部分に適合度を表示する適合度マトリックスを作成する適合度マトリックス作成手段、および、適合度マトリックス作成手段にて作成された適合度マトリックスについて、適合度により構造トポロジーをソートし、他のＲＮＡ配列について当該ソートされた構造トポロジーの順番に対応する生成文法により構文解析を行い適合度が最大となる構文解析木を求め、予め定めた条件を満たす適合度を持つ構文解析木に対応する他のＲＮＡ配列を抽出する共通構造抽出手段である。
【００７６】
また、遺伝子予測部１０２ｇは、利用者が入力したＤＮＡ配列から転写されるＲＮＡ配列を作成するＲＮＡ配列作成手段、および、適合度計算手段により計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列に対応するＤＮＡ配列部分を遺伝子の候補として予測する遺伝子予測手段である。なお、これら各部によって行なわれる処理の詳細については、後述する。
【００７７】
［システムの処理］
次に、このように構成された本実施の形態における本システムの処理の一例について、以下に図７〜図１１を参照して詳細に説明する。
【００７８】
［ＲＮＡ二次構造予測処理］
まず、ＲＮＡ二次構造予測処理の詳細について図７を参照して説明する。図７は、本実施の形態における本システムのＲＮＡ二次構造予測処理の一例を示す処理概念図である。
【００７９】
まず、文法データベース１０６ｂに既知のＲＮＡの構造トポロジーを表す文法を集積する。そして、利用者が構造未知のＲＮＡ配列であってその二次構造を特定したいものを入力装置１１２を介してＲＮＡ配列解析装置１００に入力すると（ステップＳＡ−１）、構造予測部１０２ａは、構文解析部１０２ｂの処理により、文法データベース１０６ｂから文法を取り出し（ステップＳＡ−２）、ＲＮＡ配列に対して各文法を適合して構文解析（パーズ）を行う（ステップＳＡ−３）。ここで、利用者のＲＮＡ配列の入力は、ＲＮＡ配列データベース１０６ａから所望の配列を選択することにより入力してもよく、外部システム２００の外部データベースから所望の配列を選択することにより入力してもよく、さらに、所望の配列を直接入力してもよい。
【００８０】
そして、構造予測部１０２ａは、適合度計算部１０２ｃの処理により、パーズが成功し導出された構文解析木について、例えば、ループや、塩基対とその他の二次構造要素のそれぞれの自由エネルギーの合計などを計算することにより求める平衡自由エネルギー（ΔＧ）などに基づいて適合度を求める。ここで、適合度計算方法は、例えば上述した文献１から３に示した方法のほか、従来のいずれの方法を用いてもよい。
【００８１】
そして、構造予測部１０２ａは、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を適合度が高い順にソートする（ステップＳＡ−４）。
【００８２】
そして、構造予測部１０２ａは、入出力制御インターフェース部１０８を介して出力装置１１４にソートされた構文解析木とその適合度を出力することにより、利用者が入力した一配列に対して多文法で構文解析を行うことができるようになる。すなわち、各生成文法に対してそれぞれ構文解析し適合度計算を行い適合度を得る。その結果、生成文法ごとに適合度が得られることになり、それらの適合度をソートすることによって生成文法に順位を付ける。これにより、生成文法に対する構造トポロジーにも順位が付けられることになるので、最終的にＲＮＡ配列が取り得る可能性の高い順に構造トポロジーを確認することができるようになる。これにて、ＲＮＡ二次構造予測処理が終了する。
【００８３】
［同一構造ＲＮＡ配列抽出処理］
次に、同一構造ＲＮＡ配列抽出処理の詳細について図８を参照して説明する。図８は、本実施の形態における本システムの同一構造ＲＮＡ配列抽出処理の一例を示す処理概念図である。
【００８４】
まず、利用者は、特定の構造トポロジーに対応する文法を文法データベース１０６ｂから選択する。そして、構造予測部１０２ａは、構文解析部１０２ｂの処理により、ＲＮＡ配列データベース１０６ａからＲＮＡ配列を取り出し（ステップＳＢ−１）、各ＲＮＡ配列に対して文法を適合して（ステップＳＢ−２）、構文解析を行う（ステップＳＢ−３）。
【００８５】
そして、適合度計算部１０２ｃは、導出された構文解析木に対して適合度計算を行う。そして、構造予測部１０２ａは、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を、指定した文法が表す構造トポロジーの二次構造を持つＲＮＡ配列の候補として抽出する（ステップＳＢ−４）。
【００８６】
そして、構造予測部１０２ａは、抽出されたＲＮＡ配列を当該文法が表す構造トポロジーの二次構造をもつ可能性のあるものとして、入出力制御インターフェース部１０８を介して出力装置１１４に出力する（ステップＳＢ−５）。これにて、同一構造ＲＮＡ配列抽出処理が終了する。
【００８７】
［共通構造抽出処理］
次に、共通構造抽出処理の詳細について図９を参照して説明する。図９は、本実施の形態における本システムの共通構造抽出処理の一例を示す処理概念図である。
【００８８】
まず、構造予測部１０２ａは、ＲＮＡ配列データベース１０６ａから１つまたは２つ以上のＲＮＡ配列を取り出し（ステップＳＣ−１およびステップＳＣ−２）、構文解析部１０２ｂの処理により、各ＲＮＡ配列に対して、文法データベース１０６ｂから取り出した（ステップＳＣ−３）、１つまたは２つ以上の文法を適合する（ステップＳＣ−４）。ＲＮＡ配列解析装置１００は、これらの取り出しや、パーズ処理について並列処理を行ってもよく、また、順次処理を行ってもよい。
【００８９】
そして、適合度計算部１０２ｃは、導出された構文解析木に対して適合度計算を行い、共通構造マトリックス作成部１０２ｆの処理により、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出する（ステップＳＣ−５）。
【００９０】
そして、共通構造マトリックス作成部１０２ｆは、適合した文法が表す構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と構造トポロジーに対応する格子部分をマークすることにより、ＲＮＡ配列間で共通に有する構造トポロジーを可視化する（ステップＳＣ−６）。
【００９１】
ここで、マークは、図９に示すように対象の格子部分に特定の色をつけてもよく、また、特定の記号（○など）や文字（「Ｙ」など）を記載してもよい。これにより、例えば、縦方向にマークが連続した場合（図９に示す例においては、２番目の構造トポロジーの列）には、この構造トポロジーが各ＲＮＡ配列に共通に持っている配列であることが可視的に把握することができるようになる。これにて、共通構造抽出処理が終了する。
【００９２】
［構造類似度計算処理］
次に、構造類似度計算処理の詳細について図１０を参照して説明する。図１０は、本実施の形態における本システムの構造類似度計算処理の一例を示す処理概念図である。
【００９３】
まず、利用者が、入力装置１１２により類似度を計算したい複数（図１０の例では２個）のＲＮＡ配列をＲＮＡ配列解析装置１００に入力する（ステップＳＥ−１）。
【００９４】
そして、類似度計算部１０２ｄは、文法データベース１０６ｂから１つまたは２つ以上の文法を取り出し（ステップＳＥ−２）、構文解析部１０２ｂの処理により、入力したＲＮＡ配列について文法を適合して構文解析を行う（ステップＳＥ−３）。また、適合度計算部１０２ｃは、導出された構文解析木に対して適合度計算を行う（ステップＳＥ−４）。
【００９５】
そして、類似度計算部１０２ｄは、文法を適合することにより導出された構文解析木と適合度（導出されなかった場合には、それを表現する特別な値を設定する）を各ＲＮＡ配列ごとに対応付けてベクトル演算や内積の計算などをすることにより（ステップＳＥ−５）、ＲＮＡ配列間の類似度を計算する（ステップＳＥ−６）。
【００９６】
例えば、入力であるｉ個のＲＮＡ配列をＲＮＡ1，ＲＮＡ2，．．．，ＲＮＡiとし、文法データベース１０６ｂに格納されているＮ個の文法をＧ1，Ｇ2，．．．，ＧNとし、また、ＲＮＡ配列ｘと文法ｇに対するパーザが成功したときの適合度をｒ（ｘ，ｇ）とする。ここで、適合度は実数値とし、適合度が大きいほどその構造を取り易いことを示すものとする。
また、入力ＲＮＡjに関する適合度のベクトルＲjにおいて、Ｒjのｋ番目の要素Ｒj［ｋ］は、ＲＮＡjとＧkに対するパーザが成功したときはｒ（ＲＮＡj，Ｇk）とし、ＲＮＡjとＧkに対するパーザが失敗したときは仮に「×」とする。
【００９７】
このとき、類似度計算部１０２ｄによる類似度計算は、以下の手法により行われる。まず、２つのＲＮＡ配列の適合度のベクトルＲ1とＲ2を入力する。
【００９８】
ついで、類似度計算部１０２ｄは、類似度ベクトルＳ1、Ｓ2とペナルティＰを求める。ここで、「ペナルティＰ」は、Ｒ1［ｋ］とＲ2［ｋ］の片方だけが「パーザ失敗（×）」であるｋの個数であり、「類似度ベクトルＳ1、Ｓ2」は、Ｒ1［ｋ］もＲ2［ｋ］も「パーザ失敗（×）」ではない箇所だけを抜き出したベクトルである。図１２は、ペナルティＰと類似度ベクトルＳ1、Ｓ2の概念を説明する図である。
【００９９】
ついで、類似度計算部１０２ｄは、類似度ベクトルＳ1、Ｓ2間の距離Ｄを以下の方法により求める。まず、類似度ベクトルＳ1、Ｓ2の要素数（ベクトルの次元）をＭとする。そして、類似度計算で一般的に用いられるユークリッド距離を用いて以下の数式により距離を計算する。
Ｄ＝ｓｑｒｔ（Σ｛（Ｓ1［ｋ］  −Ｓ2［ｋ］）2｝）
（ｓｑｒｔは平方根であり、Σはｋ＝１〜Ｍに関する総和である。）
【０１００】
ここで、距離Ｄが大きい場合には類似度が低いことになり、また、ペナルティＰが大きいと類似度が低いことになるので、ペナルティＰと距離Ｄを用いて以下の数式により類似度Ｓｉｍを求める。
Ｓｉｍ＝ａP／Ｄ
（ａは定数（０＜ａ＜１）である。）
【０１０１】
そして、Ｓｉｍを類似度として出力する。ここで、定数ａを小さくすると、距離ＤよりもペナルティＰが重視されることになる。これにて、構造類似度計算処理が終了する。
【０１０２】
［遺伝子予測処理］
次に、遺伝子予測処理の詳細について図１１を参照して説明する。図１１は、本実施の形態における本システムの遺伝子予測処理の一例を示す処理概念図である。
【０１０３】
まず、利用者が遺伝子部分が未知のＤＮＡ配列を入力装置１１２を介してＲＮＡ配列解析装置１００に入力すると、ＲＮＡ配列解析装置１００は、遺伝子予測部１０２ｇの処理により、入力されたＤＮＡ配列に基づいて、当該ＤＮＡ配列から転写されるＲＮＡ配列（以下、「予測ＲＮＡ配列」という）を自動的に変換して作成する（ステップＳＦ−１）。ここで、利用者のＤＮＡ配列の入力は、外部システム２００の外部データベースやインハウスデータベースから所望のＤＮＡ配列を選択することにより入力してもよく、さらに、所望の配列を直接入力してもよい。
【０１０４】
ついで、構造予測部１０２ａがこの予測ＲＮＡ配列を構文解析部１０２ｂに入力すると（ステップＳＦ−２）、構文解析部１０２ｂの処理により、文法データベース１０６ｂから１つまたは２つ以上の文法が取り出され（ステップＳＦ−３）、各文法を予測ＲＮＡ配列に適合する（ステップＳＦ−４）。
【０１０５】
そして、適合度計算部１０２ｃは、構文解析部１０２ｂが導出した構文解析木について適合度計算を行い（ステップＳＦ−５）、遺伝子予測部１０２ｇは、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出した予測ＲＮＡ配列に対応するＤＮＡ配列部分を遺伝子の候補として予測する（ステップＳＦ−６）。すなわち、ＤＮＡ配列のうち、当該予測ＲＮＡ配列の部分が遺伝子部分である可能性が高い領域として出力される。
【０１０６】
これにより、ＤＮＡ配列のうち既知のトポロジーを有する可能性のある予測ＲＮＡ配列に対応する部分について、遺伝子部分である可能性があることを予測することができるようになる。これにて、遺伝子予測処理が終了する。
【０１０７】
［実施例］
本発明の実施例について、以下に図１３〜図２３を参照して説明する。
１  準備
本節では実施例の準備として、いくつかの具体的なＲＮＡ二次構造トポロジーを定義し、それらをモデリングする生成文法を規定する。本実施例では説明の便宜上、生成文法として文脈自由文法を用いるが、よりモデリング能力の高いＲＮＡ木文法（文献１）を用いた場合でも同様のことが説明できる。
【０１０８】
１．１    二次構造トポロジー
図１３に示される２つのＲＮＡ二次構造トポロジーを考える。
ステムループは、ステム（Ｈ（ａ））とヘアピンループ（Ｌ（ａ））から構成される。２並列ステムループは、並列に並んだ２つのステムループから構成される。それぞれのステム部分（Ｈ1（ｂ）、Ｈ2（ｂ））とヘアピンループ部分、（Ｌ1（ｂ）、Ｌ2（ｂ））の他にステムとステムをつなぐループ部分（Ｉ（ｂ））がある。
【０１０９】
上記構造トポロジーについて、さらに具体的な特徴を考えることができる。例えばステムやループ部分のサイズの制約、ステムを構成する塩基対にミスマッチ（内部ループやバルジループ）を許すかどうか、あるいは特定の場所に特定の塩基配列を含むかどうか、などといったより詳細な特徴を持ったトポロジーを考えることが可能である。そこで、本実施例では次のような特徴を持ったＲＮＡ二次構造トポロジーＴ1、Ｔ2を扱う。
【０１１０】
トポロジーＴ1
−      以下の特徴を持ったステムループ構造（図１３（ａ）参照）である。
−      ステム（Ｈ（ａ））を構成する塩基対はミスマッチを含まない。
−      ステム（Ｈ（ａ））サイズは１塩基対以上とする。
−      ヘアピンループ（Ｌ（ａ））のサイズは１塩基以上とする。
【０１１１】
トポロジーＴ2
−      以下の特徴を持った２並列ステムループ構造（図１３（ｂ）参照）である。
−      トポロジーＴ1を２つ並列に並べたもの。
−      ステム（Ｈ1（ｂ））とステム（Ｈ2（ｂ））の間のループ（Ｉ（ｂ））の長さは１塩基以上とする。
【０１１２】
１．２    文脈自由文法による二次構造トポロジーのモデリング
以上のように定義された２つのトポロジーＴ1、Ｔ2を文脈自由文法を用いてモデリングする。文脈自由文法は一般に以下の４項組によって規定される。
Ｇ＝（Ｎ，Σ，Ｐ，Ｓ）
Ｎは非終端記号の有限集合、Σは終端記号の有限集合、Ｐは生成規則の有限集合、Ｓは開始記号を表す。
【０１１３】
しかしながら、本実施例では常にΣ＝｛ａ，ｕ，ｇ，ｃ｝、開始記号はＳ、さらにＮは生成規則Ｐに出現する非終端記号のみからなるものとすることから、Ｐのみを指定することにより文脈自由文法Ｇを規定することができる。よって便宜上、本稿では文脈自由文法Ｇを規定する際には、生成規則の有限集合Ｐのみを指定することにする。
【０１１４】
（１）トポロジーＴ1は以下の生成規則からなる文脈自由文法Ｇ1によってモデリングされる。
【数１】
0003881238.tif 000002
【０１１５】
すなわち、ワトソン−クリック塩基対のみを考える場合は、一番最初の生成規則は以下と同値である。
Ｓ→ａＨｕ｜ｕＨａ｜ｇＨｃ｜ｃＨｇ
非ワトソン−クリック塩基対を許す場合はさらに、Ｓ→ｇＨｕなどを追加してもよい。
【０１１６】
Ｇ1において、
【数２】
0003881238.tif 000003
によって塩基対（ステムを構成）が生成され、Ｌ→ｘＬとＬ→ｘによって塩基対を形成しない塩基（ループを構成）が生成されるとみなす。すると、Ｇ1はＲＮＡの二次構造を生成することができることになる。このように、任意の文脈自由文法Ｇに対して、Ｇが生成することができるすべてのＲＮＡ二次構造からなる集合ＳＳ（Ｇ）が規定されることになる。
【０１１７】
Ｇ1がトポロジーＴ1をモデリングする、とは以下が成り立つことを言う。“Ｇ1はトポロジーＴ1の性質を満たすすべてのＲＮＡ二次構造を生成することができ、なおかつ、Ｇ1で生成することができるすべてのＲＮＡ二次構造はトポロジーＴ1の性質を満たす。”
【０１１８】
これは、Ｇ1による導出をみれば自明である。Ｇ1による導出はすべて以下のようになる。
【数３】
0003881238.tif 000004
【０１１９】
よって、Ｇ1はＴ1をモデリングすることがわかる。
【０１２０】
（２）トポロジーＴ2は以下の生成規則からなる文脈自由文法Ｇ2によってモデリングされる。
【数４】
0003881238.tif 000005
【０１２１】
以下の生成規則からなる文脈自由文法Ｇ0は、文脈自由文法によって生成することが可能なすべてのＲＮＡ二次構造を生成することができる万能な文脈自由文法である。
【数５】
0003881238.tif 000006
ただし、λは空文字を表す。例えば、Ｇ1によるいかなる導出もＧ0によってシミュレートできる。すなわち、以下のような導出をＧ0によって行なうことが可能である。
【数６】
0003881238.tif 000007
【０１２２】
上記の導出は非終端記号以外、すなわち生成されるＲＮＡ二次構造は、Ｇ1によって生成されるものとまったく同じである。よってＧ1が生成可能なすべての二次構造をＧ0によって生成可能なことがわかる。すなわち、
ＳＳ（Ｇ0）⊇ＳＳ（Ｇ1）
である。
【０１２３】
このように、どんな文脈自由文法Ｇに対しても
ＳＳ（Ｇ0）⊇ＳＳ（Ｇ）
が成り立つことが知られている。以降では、このような万能文法によって生成される二次構造全体を“すべての二次構造”と考える。
【０１２４】
１．３  構文解析木と適合度
ある与えられたＲＮＡ配列がある与えられたＲＮＡ二次構造トポロジーの性質を満たす二次構造を形成できるかどうかという問題は、対象トポロジーをモデリングした文法によって対象配列が導出できるかという問題に対応する。これは生成文法の構文解析アルゴリズムによって解くことができる。
【０１２５】
構文解析アルゴリズムは、与えられた文法によって、与えられた配列が導出できるかどうかを判定し、導出可能な場合はその導出過程、すなわち構文解析木を出力する。二次構造トポロジーをモデリングした文法において、構文解析木は二次構造を表現しているので、構文解析アルゴリズムは、対象トポロジーに適合する具体的な二次構造を出力すると解釈してよいことになるからである。
【０１２６】
ＲＮＡ配列ｓ1＝ｇｇｇｇａａａｃｃｃｃ（配列番号１）がトポロジーＴ1、Ｔ2に適合する二次構造を形成できるかどうかについて考える。
配列ｓ1はＧ1によって以下のように導出できる。これにより配列ｓ1はＴ1に適合する二次構造をとりうることがわかる。
Ｓ→ｇＨｃ→ｇｇＨｃｃ→ｇｇｇＨｃｃｃ→ｇｇｇｇＨｃｃｃｃ
→ｇｇｇｇＬｃｃｃｃ→ｇｇｇｇａＬｃｃｃｃ→ｇｇｇｇａａＬｃｃｃｃ
→ｇｇｇｇａａａｃｃｃｃ                                （１）
【０１２７】
また、ｓ1はＧ1によって以下のようにも導出できる。
Ｓ→ｇＨｃ→ｇｇＨｃｃ→ｇｇｇＨｃｃｃ
→ｇｇｇＬｃｃｃ→ｇｇｇｇＬｃｃｃ→ｇｇｇｇａＬｃｃｃ
→ｇｇｇｇａａＬｃｃｃ→ｇｇｇｇａａａＬｃｃｃ
→ｇｇｇｇａａａｃｃｃｃ                                （２）
【０１２８】
しかし、ｓ1はＧ2によって導出することはできない。これによりｓ1はトポロジーＴ2に適合する二次構造をとりえないことがわかる。
【０１２９】
ｓ1をＧ1によって上記の２通りの方法で導出するとき、それぞれの導出に対応する構文解析木とそれが表現する二次構造を図１４に示す。すなわち、（１）のように導出した場合は、図１４の（１）に示される構文解析木と二次構造が生成され、（２）のように導出した場合は、図１４の（２）に示される構文解析木と二次構造が生成される。
【０１３０】
この例のように複数の構文解析木が得られたときに、どの構文解析木、すなわち、どの二次構造を結果として出力するかを決定する必要が生じる。そのために、何らかの評価関数によって構文解析木（あるいは二次構造）にスコアを与え、構文解析木（あるいは二次構造）に順位を付ける必要が生じる。このようなスコアは文法によって異なる評価関数を用いても良いし、文法に依存しない絶対的な評価関数であってもよい。以降では、このスコアを適合度と呼ぶ。
【０１３１】
以下に、これまでに利用されている適合度の評価法の例を示すが、本発明によって利用される適合度は以下のものに限定されない。
【０１３２】
（１）  塩基対数による適合度の評価
一般に、塩基対を形成する際の水素結合によってＲＮＡ分子はエネルギー的に安定なものになる。そこでこの評価法では、単純に塩基対の数が多い二次構造ほど優先させる。つまり、構文解析木の適合度として、対応する二次構造の塩基対数を用いる。この評価法において、上記の例の適合度を評価すると、図１４の（１）に示される構文解析木は適合度３となり、（２）に示される構文解析木は適合度２となり、適合度の大きい（１）の構造が採用されることになる。
【０１３３】
本評価法に基づいた代表的な手法として、Ｎｕｓｓｉｎｏｖの折り畳みアルゴリズム［Ｎｕｓｓｉｎｏｖ，Ｒ．，Ｐｉｅｃｘｅｎｋ，Ｇ．，ｇｅｉｇｇｓ，ｊ．Ｒ．，ａｎｄ  Ｋｌｅｉｔｍａｎ，Ｄ．Ｊ．，  “  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｌｏｏｐ  ｍａｔｃｈｉｎｇｓ，”  ＳＩＡＭ  ｊｏｕｒｎａｌ  ｏｆＡｐｐｌｉｅｄ  Ｍａｔｈｅｍａｔｉｃｓ，  ３５，  ６８−８２，１９７８］がある。
【０１３４】
（２）  平衡自由エネルギー（ΔＧ）による適合度の評価
ＲＮＡ二次構造の物理化学的な安定度を計算するために、小さなモデルＲＮＡ分子の熱力学的な実験によって決定された平衡自由エネルギー（ΔＧ）パラメータを利用する方法がある。ある二次構造の（ΔＧ）は、それを構成する塩基対やループなどの二次構造要素に対する自由エネルギーの合計で近似される。この自由エネルギーパラメータでは、塩基対により構造が安定化し、ループにより構造が不安定化する。各二次構造要素の詳細なパラメータは［Ｔｕｒｎｅｒ，  Ｄ．Ｈ．，Ｓｕｇｉｍｏｔｏ，Ｎ．，Ｊａｅｇｅｒ，Ｊ．Ａ．，Ｌｏｎｇｆｅｌｌｏｗ，Ｃ．Ｅ．，Ｆｒｅｉｅｒ，Ｓ．Ｍ．，ａｎｄ  Ｋｉｅｒｚｅｋ，Ｒ．，“Ｉｍｐｒｏｖｅｄ  ｐａｒａｍｅｔｅｒｓ  ｆｏｒ  ｐｒｅｄｉｃｔｉｏｎ  ｏｆＲＮＡ  ｓｔｒｕｃｔｕｒｅ，”  Ｃｏｌｄ  Ｓｐｒｉｎｇ  Ｈａｒｂｏｒ  Ｓｙｍｐｏｓｉａ  Ｑｕａｎｔｉｔａｔｉｖｅ  Ｂｉｏｌｏｇｙ，  ５２，１２３−１３３，１９８７］に示されている。ここでは塩基対の自由エネルギーを図１５に、ループの自由エネルギーを図１６に示す。
【０１３５】
上記の自由エネルギーパラメータを用いて図１４の構造（１）と（２）の（ΔＧ）を求めると、それぞれ以下のようになる。
ΔＧ（構造（１））＝ΔＧ（ｇｃ，ｇｃ）＋ΔＧ（ｇｃ，ｇｃ）
＋ΔＧ（ｇｃ，ｇｃ）
＋（ΔＧ）（サイズ３のヘアピンループ）
＝（−２．９）＋（−２．９）＋（−２．９）
＋７．４＝−１．３
ΔＧ（構造（２））＝ΔＧ（ｇｃ，ｇｃ）＋ΔＧ（ｇｃ，ｇｃ）
＋ΔＧ（サイズ５のヘアピンループ）
＝（−２．９）＋（−２．９）＋４．４＝−１．４
【０１３６】
ここで注意すべきことは、塩基対の自由エネルギーの計算方法である。連続して積み重なった２組の塩基対に対してひとつのエネルギー値が与えられる。すなわち、構造（１）では５’側から数えて１番目のｇｃ塩基対と２番目のｇｃ塩基対に対して、ΔＧ（ｇｃ，ｇｃ）が計算され、２番目のｇｃ塩基対と３番目のｇｃ塩基対に対して、ΔＧ（ｇｃ，ｇｃ）が計算され、３番目のｇｃ塩基対と４番目のｇｃ塩基対に対して、ΔＧ（ｇｃ，ｇｃ）が計算される。これに対し構造（２）では５’側から数えて１番目のｇｃ塩基対と２番目のｇｃ塩基対に対して、ΔＧ（ｇｃ，ｇｃ）が計算され、２番目のｇｃ塩基対と３番目のｇｃ塩基対に対して、ΔＧ（ｇｃ，ｇｃ）が計算される。
【０１３７】
構文解析木の適合度を−ΔＧと定めると、（１）の適合度は１．３となり、（２）の適合度は１．４となり、結果として適合度の大きい（２）の構造が採用されることになる。
【０１３８】
ΔＧに基づいた代表的なＲＮＡ二次構造予測システムとして、ＺｕｋｅｒのＭｆｏｌｄ（文献３）がある。
【０１３９】
（３）  導出確率による適合度の評価
確率文法とは個々の生成規則にその適用確率が付加された生成文法である。例えばＧ1の各生成規則に以下のような確率ｐが付加されている確率文脈自由文法Ｇ1を考える。
ｐ（Ｓ→ａＨｕ）＝０．２
ｐ（Ｓ→ｕＨａ）＝０．２
ｐ（Ｓ→ｇＨｃ）＝０．３
ｐ（Ｓ→ｃＨｇ）＝０．３
ｐ（Ｈ→ａＨｕ）＝０．２
ｐ（Ｈ→ｕＨａ）＝０．２
ｐ（Ｈ→ｇＨｃ）＝０．３
ｐ（Ｈ→ｃＨｇ）＝０．２
ｐ（Ｈ→Ｌ）＝０．１
ｐ（Ｌ→ａＬ）＝０．２
ｐ（Ｌ→ｕＬ）＝０．２
ｐ（Ｌ→ｇＬ）＝０．１５
ｐ（Ｌ→ｃＬ）＝０．１５
ｐ（Ｌ→ａ）＝０．１
ｐ（Ｌ→ｕ）＝０．１
ｐ（Ｌ→ｇ）＝０．０５
ｐ（Ｌ→ｃ）＝０．０５
【０１４０】
このときＧ1によるｓ1の導出確率は次のようにして計算される。すなわち、（１）の導出確率は、
ｐ（Ｓ→ｇＨｃ）×ｐ（Ｈ→ｇＨｃ）×ｐ（Ｈ→ｇＨｃ）×ｐ（Ｈ→ｇＨｃ）×ｐ（Ｈ→Ｌ）×ｐ（Ｌ→ａＬ）×ｐ（Ｌ→ａＬ）×ｐ（Ｌ→ａ）
＝０．３×０．３×０．３×０．３×０．１×０．２×０．２×０．１
＝０．０００００３２４
と計算される。また、（２）の導出確率は、
ｐ（Ｓ→ｇＨｃ）×ｐ（Ｈ→ｇＨｃ）×ｐ（Ｈ→ｇＨｃ）×ｐ（Ｈ→Ｌ）×ｐ（Ｌ→ｇＬ）×ｐ（Ｌ→ａＬ）×ｐ（Ｌ→ａＬ）×ｐ（Ｌ→ａＬ）×ｐ（Ｌ→ｃ）
＝０．３×０．３×０．３×０．１×０．１５×０．２×０．２×０．２×０．０５
＝０．００００００１６２
となる。
【０１４１】
そこで構文解析木の適合度として導出確率の自然対数をとると、（１）の適合度は１ｎ０．０００００３２４＝−１２．６、（２）の適合度は１ｎ０．００００００１６２＝−１５．６となり、結果として適合度の大きい（１）の構造が採用されることになる。
【０１４２】
本評価法の根本である、各生成規則に付加されるべき確率パラメータは、最尤推定法と内側・外側アルゴリズム（ｉｎｓｉｄｅ−ｏｕｔｓｉｄｅ  ａｌｇｏｒｉｔｈｍ）などにより学習してもよいし、ヒューリスティクス（ｈｅｕｒｉｓｔｉｃｓ）などによって主観的に推定してもよい。例えば、文献［Ｓａｋａｋｉｂａｒａら“Ｓｔｏｃｈａｓｔｉｃ  Ｃｏｎｔｅｘｔ−ｆｅｅ  Ｇｒａｍｍａｒｓｆｏｒ  ｔＲＮＡ  ｍｏｄｅｌｉｎｇ，”  Ｎｕｃｌｅｉｃ  Ａｃｉｄｓ  Ｒｅｓｅａｒｃｈ，  ２２，５１１２−５１２０，１９９４．］では複数のｔＲＮＡ配列からｔＲＮＡの構造をモデリングする確率文脈自由文法を学習する手法について述べられている。
【０１４３】
以上いくつかの適合度評価法について説明したが、以降の説明では適合度として−ΔＧを用いる。
【０１４４】
次にＲＮＡ配列ｓ2＝ｇｃｃｃａｕａｇｇｃａａａｇｃｃｕａｕｇｇｇｃ（配列番号２）がトポロジーＴ1、Ｔ2に適合する二次構造を形成できるかどうかを考える。この場合も同様にｓ2がＧ1、Ｇ2によって導出できるかどうかを調べればよい。結論からいうと、ｓ2はＧ1、Ｇ2のいずれからも導出することができる。さらにどちらの文法でも複数の導出のしかたが存在する。それぞれの文法について−ΔＧの適合度指標において最適な構文解析木とそれに対応する二次構造を図１７に示す。
【０１４５】
それぞれの構造のΔＧを求めると、以下のようになる。
ΔＧ（構造（１））＝ΔＧ（ｇｃ，ｃｇ）×２＋ΔＧ（ｃｇ，ｃｇ）
×２＋ΔＧ（ｃｇ，ａｕ）＋ΔＧ（ａｕ，ｕａ）
＋ΔＧ（ｕａ，ａｕ）＋ΔＧ（ａｕ，ｇｃ）
＋ΔＧ（ｇｃ，ｇｃ）
＋ΔＧ（サイズ３のヘアピンループ）
＝（−３．４）×２＋（−２．９）×２＋（−１．８）
＋（−０．９）＋（−１．１）＋（−１．７）
＋（−２．９）＋７．４＝−１３．６
ΔＧ（構造（２））＝ΔＧ（ｇｃ，ｃｇ）×２＋ΔＧ（ｃｇ，ｃｇ）×２
＋ΔＧ（サイズ４のヘアピンループ）×２
＝（−３．４）×２＋（−２．９）×２＋５．９×２
＝−６．７
よってトポロジーＴ1に適合するＲＮＡ二次構造においてｓ2がとりうる最適な構造の適合度は１３．６であることがわかる。また、トポロジーＴ2に適合するＲＮＡ二次構造においてｓ2がとりうる最適な構造の適合度は６．７であることがわかる。また、ｓ2を万能な文法Ｇ0によって構文解析すると、最適構造として構造（１）が見つかる。これにより、構造（１）が“すべての二次構造”の中で最適な構造であることがわかる。このように万能文法によって構文解析を行なうことにより、すべての構造の中から最適な構造を見つけ出すことができる。
【０１４６】
本発明の基本となる“ＲＮＡ配列を生成文法に適用して構文解析木を導出する構文解析手段と、上記構文解析手段にて導出された構文解析木に対して適合度の計算を行う適合度計算手段と、適合度最大の構文解析木に対応する二次構造を出力する最適二次構造出力手段”は、適合度計算を組み込んだ構文解析アルゴリズムにより実現されることになる。このような構文解析アルゴリズムを構造予測アルゴリズムと呼ぶ。ΔＧの適合度を指標にしたＲＮＡ木文法に基づく構造予測アルゴリズムは文献１に示されている。
【０１４７】
２．  発明実施例
本節では、前節までに定義したＲＮＡ配列ｓ1、ｓ2、トポロジーＴ1、Ｔ2およびそれらをモデリングする文脈自由文法Ｇ0、Ｇ1、Ｇ2、さらに適合度として−ΔＧを用いた場合の実施例について示す。
【０１４８】
はじめに、“ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納する文法格納手段”においては、例えば（Ｌｅｕ−ｔＲＮＡ，Ｇ’）や（１６Ｓ  ｒＲＮＡ，Ｇ”）などのようにある構造トポロジーに付けられた名称とその構造トポロジーをモデリングした文法が対応づけられて格納されている。本実施例では（ステムループＴ1，Ｇ1）と（２並列ステムループＴ2，Ｇ2）を含むような文法ＤＢを仮定する。また、ＲＮＡ配列ｓ1とｓ2を含むＲＮＡ配列ＤＢを仮定する。
【０１４９】
（１）生成文法と適合度計算で構造候補を出力
あるＲＮＡ配列に対して、これがとりうる構造トポロジーを適合度が大きい順に知りたいとき、本発明によれば、以下の手順でこれを調べることができる。例として、入力配列をｓ2、検査対象トポロジー集合をＴ1、Ｔ2とした場合について示す。
【０１５０】
手順１）  ＲＮＡ配列を配列ＤＢから指定する。あるいは直接入力する。ここではｓ2を指定する。
手順２）  検査対象とするトポロジーの集合（生成文法の集合）を文法ＤＢから選択する。ここではＴ1とＴ2（Ｇ1とＧ2）を選択する。
手順３）  適合度の閾値を設定する。閾値は手順２で得られた各トポロジー（生成文法）に対してそれぞれ設定してもよいし、共通にひとつ設定してもよい。ここではＴ1（Ｇ1）に対して１０をＴ2（Ｇ2）に対して５を設定する。
手順４）  手順１で得られた配列を手順２で得られた各生成文法によってそれぞれ構文解析を行ない、適合度最大の構文解析木を求める。ここではｓ2をＧ1によって構文解析し、最大の適合度１３．６を持つ構文解析木を得る（図１７（１）参照）。
さらにｓ2をＧ2によって構文解析し、最大の適合度６．７を持つ構文解析木を得る（図１７（２）参照）。
手順５）  手順４で得られた構文解析木のうち手順３で得られた閾値以上の適合度をもつ構文解析木を適合度の大きい順にソートする。手順４で得られたＧ1に対する適合度１３．６の構文解析木１は手順３でＧ1に対して設定された閾値１０よりも大きいのでこれをソート対象とする。手順４で得られたＧ2に対する適合度６．７の構文解析木２は手順３でＧ2に対して設定された閾値５よりも大きいのでこれをソート対象とする。上でソート対象となった構文解析木を適合度の大きい順にソートすることによって、構文解析木１、構文解析木２の順に順序づけされる。
手順６）  手順５でソートされた構文解析木の順に、対応するトポロジー名、適合度、構文解析木（二次構造）などを出力する。構文解析木１に対応して、ステムループＴ1、適合度１３．６、図１７（１）に示された二次構造を出力する。構文解析木２に対応して、２並列ステムループＴ2、適合度６．７、図１７（２）に示された二次構造を出力する。
以上の結果から、選択されたトポロジー集合のなかでｓ2が適合する構造候補が図１８のように出力される。
【０１５１】
従来の二次構造予測プログラムでは、与えられた配列がとりうる構造のなかで最適あるいは準最適な二次構造を順に出力するだけで、出力された構造がどのようなトポロジーであるかはユーザが判断しなければならなかった。本発明によれば、構造とトポロジーとを対応付けて出力することができるので、予測結果の確認にかかる労力が大きく軽減されることが期待される。
【０１５２】
また、本発明の実施について厳密に上記の手順と同じである必要はない。例えば、手順１と２は順序をいれかえてもよいし、手順５の閾値により構文解析木を取捨選択する部分は手順４の構文解析部分に含めてしまってもよい。
【０１５３】
（２）同じ構造を持つ配列の候補を出力
ある構造トポロジーに対して、これに適合する二次構造をとりうるＲＮＡ配列を探したいとき、本発明によれば、以下の手順でこれを調べることができる。例として、入力構造トポロジーをＴ2、検査対象配列集合をｓ1、ｓ2とした場合について示す。
手順１）  トポロジー（生成文法）を文法ＤＢから選択する。ここではＴ2（Ｇ2）を選択する。
手順２）  適合度の閾値を設定する。ここでは５を選択する。
手順３）  検査対象とするＲＮＡ配列集合を配列ＤＢから選択する。あるいは直接入力する。ここではｓ1、ｓ2選択する。
手順４）  手順３で得られた各配列を、手順１で得られた生成文法によってそれぞれ構文解析を行ない、適合度最大の構文解析木をそれぞれ求める。ここではｓ1をＧ2によって構文解析し、導出不能であることを得る。さらにｓ2をＧ2によって構文解析し、最大の適合度６．７を持つ構文解析木を得る。（図１７（２）参照）
手順５）  手順４で得られた構文解析木のうち手順２で得られた閾値以上の適合度をもつ構文解析木に対応する配列を出力する。手順４で得られたｓ2のＧ2に対する適合度６．７の構文解析木は手順２で設定された閾値５よりも大きいのでｓ2を出力する。以上の結果から、選択されたトポロジーをとりうる配列の候補が図１９のように出力される。
【０１５４】
本発明の実施について厳密に上記の手順と同じである必要はない。例えば、手順１と２と３は任意の順にいれかえてもよいし、手順５は手順４の構文解析部分に含めてしまってもよい。
【０１５５】
（３）共通構造抽出
あるＲＮＡ配列の集合に対して、これらの配列が共通してとりうる構造トポロジーを調べたいとき、本発明によれば、以下の手順でこれを調べることができる。例として、入力配列集合をｓ1、ｓ2とし、検査対象構造トポロジーの集合をＴ1、Ｔ2とした場合について示す。
【０１５６】
手順１）  ＲＮＡ配列の集合を配列ＤＢから指定する。あるいは直接入力する。ここではｓ1とｓ2を指定する。
手順２）  検査対象とするトポロジーの集合（生成文法の集合）を文法ＤＢから選択する。ここではＴ1（Ｇ1）とＴ2（Ｇ2）を選択する。
手順３）  適合度の閾値を設定する。閾値は手順２で得られた各トポロジー（生成文法）に対してそれぞれ設定してもよいし、共通にひとつ設定してもよい。ここでは共通に０を設定する。
手順４）  手順１で得られた各配列を、手順２で得られた各生成文法によってそれぞれ構文解析を行ない、適合度最大の構文解析木を求める。
ｓ1をＧ1によって構文解析し、最大の適合度１．４を持つ構文解析木を得る（図１４（２）参照）。
ｓ1をＧ2によって構文解析し、導出不能であることを得る。
ｓ2をＧ1によって構文解析し、最大の適合度１３．６を持つ構文解析木を得る。（図１７（１）参照）
ｓ2をＧ2によって構文解析し、最大の適合度６．７を持つ構文解析木を得る。（図１７（２）参照）
手順５）  手順４で得られた構文解析木のうち閾値以上の適合度を持つ構文解析木を抽出する。手順４で得られたすべての構文解析木は手順３で得られた閾値０よりも大きい適合度を持つので手順４で得られたすべての構文解析木を抽出する。
手順６）  手順１で得られた配列集合を行に、手順２で得られたトポロジー集合を列に、手順５で得られた構文解析木の適合度を要素に持つマトリックスを作成する。図２０に示すマトリックスを得る。
以上の結果得られたマトリックスを出力すれば、対象配列集合が共通してとりうる構造トポロジーを容易に確認することが可能になる。あるいは、以下の追加手順を実行すれば、共通構造の候補を順位づけて出力することができる。
手順７）  手順６で得られたマトリックスの各列、すなわちトポロジー、に対してスコアを計算する。例えば、有効な行要素の数を各列ごとに計算しスコアとすると、Ｔ1のスコアは２、Ｔ2のスコアは１となる。例えば、各行の適合度の総和を各列ごとに計算しスコアとすると、Ｔ1のスコアは１５．０、Ｔ2のスコアは６．７となる。
手順８）  手順７で得られたスコアの高い順にトポロジーをソートし、出力する。上記のいずれのスコアを用いてもＴ1、Ｔ2の順に出力される。
【０１５７】
また、本発明の実施について厳密に上記の手順と同じである必要はない。例えば、手順１と２は順序をいれかえてもよいし、手順５を手順４の構文解析部分に含めてしまってもよい。
【０１５８】
（４）  ジーン・ファインダ
ＲＮＡ遺伝子部分に対応する配列は、非常に安定な構造をとりやすいので、適合度が高くなる。そこで本発明では、万能文法を用いて構文解析を行ない、適合度の高い配列を配列ＤＢから選び出して遺伝子候補として出力する。例として、配列集合をｓ1、ｓ2とした場合について示す。
【０１５９】
手順１）  検査対象とするＲＮＡ配列の集合を配列ＤＢから指定する。あるいは直接入力する。ここではｓ1とｓ2を指定する。
手順２）  適合度の閾値を設定する。ここでは１０を設定する。
手順３）  手順１で得られた各配列を万能文法Ｇ0によってそれぞれ構文解析を行ない、適合度最大の構文解析木を求める。
ｓ1をＧ0によって構文解析し、最大の適合度１．４を持つ構文解析木を得る。ｓ2をＧ0によって構文解析し、最大の適合度１３．６を持つ構文解析木を得る。
手順４）  手順３で得られた構文解析木のうち閾値以上の適合度をもつ構文解析木に対応する配列を遺伝子候補として出力する。手順３で得られたｓ1の構文解析木は閾値１０に満たないのでｓ1は出力しない。手順３で得られたｓ2の構文解析木は閾値１０よりも大きいのでｓ2を遺伝子候補として出力する。
本発明の実施について厳密に上記の手順と同じである必要はない。例えば、手順１と２は順序をいれかえてもよいし、手順４は手順３の構文解析部分に含めてしまってもよい。
【０１６０】
（５）  ＲＮＡ配列から同じ構造を持つＲＮＡ配列を出力
あるＲＮＡ配列集合に対して、これらと同じトポロジーをとりうるＲＮＡ配列を調べたいとき、（３）の発明と（２）の発明とを組み合わせた本発明によれば、以下の手順でこれを調べることができる。例として、入力配列をｓ＝ｇｃｃｃａａａａｇｇｇｃａｇｃｃｃａａａｇｇｇｃ（配列番号３）、検査対象トポロジー集合をＴ1、Ｔ2、検査対象配列集合をｓ1、ｓ2とした場合について示す。
【０１６１】
手順１）  ＲＮＡ配列集合を入力する。ここではｓのみからなる配列集合を入力する。
手順２）  検査対象とするＲＮＡ配列の集合を配列ＤＢから指定する。ここではｓ1とｓ2を指定する。
手順３）  検査対象とするトポロジーの集合（生成文法の集合）を文法ＤＢから選択する。ここではＴ1（Ｇ1）とＴ2（Ｇ2）を選択する。
手順４）  適合度の閾値を設定する。閾値は手順３で得られた各トポロジー（生成文法）に対してそれぞれ設定してもよいし、共通にひとつ設定してもよい。ここでは共通に５を設定する。
手順５）  手順１で得られた各ＲＮＡ配列を、手順２で得られた各生成文法によってそれぞれ構文解析を行ない、適合度最大の構文解析木をそれぞれ求める。ここではｓをＧ1によって構文解析し、最大の適合度３．１を持つ構文解析木を得る。図２１（１）にこの構文解析木が表現する二次構造を示す。さらにｓをＧ2によって構文解析し、最大の適合度５．１を持つ構文解析木を得る。図２１（２）にこの構文解析木が表現する二次構造を示す。
手順６）  手順５で得られた構文解析木のうち、手順４で得られた閾値以上の適合度をもつ構文解析木に対応する構文解析木を抽出する。手順５で得られた構文解析木のうち、Ｇ2で構文解析することによって得られた適合度５．１の構文解析木が手順４で得られた閾値５よりも大きいのでこれを抽出する。
手順７）  手順１で得られた配列集合を行に、手順３で得られたトポロジー集合を列に、手順６で得られた構文解析木の適合度を要素に持つマトリックスを作成する。図２２に示すマトリックスを得る。
手順８）  手順６で得られたマトリックスの各列、すなわちトポロジー、に対してスコアを計算し、スコアの順にトポロジーをソートする。ここでは行の総和を各列ごとに計算しスコアとするが、１行しかないので結果として、Ｔ1のスコアが未定義、Ｔ2のスコアが５．１になる。スコアを持つものだけでソートすると、Ｔ2のみが得られる。
手順９）  手順２で得られた各配列を、手順８で得られたトポロジーの順にそれぞれ対応する文法で構文解析を行ない、適合度最大の構文解析木をそれぞれ求める。ここではｓ1をＧ2によって構文解析し、導出不能であることを得る。
さらにｓ2をＧ2によって構文解析し、最大の適合度６．７を持つ構文解析木を得る。（図１７（２）参照）
手順１０）  手順９で得られた構文解析木のうち手順４で得られた閾値以上の適合度をもつ構文解析木に対応する配列を出力する。このとき、あわせてトポロジーとそのトポロジーに対する手順８で得られたスコアを出力する。手順９で得られたｓ2のＧ2に対する構文解析木の適合度６．７は手順４で得られた閾値５よりも大きいのでｓ2を出力する。あわせて、Ｔ2とそのスコア５．１を出力する。
以上の結果から図２３に示すような出力が得られる。
この結果、ｓ2がトポロジーＴ2において、ｓと共通な構造をとりうることがわかるようになる。
【０１６２】
本発明の実施について厳密に上記の手順と同じである必要はない。例えば、手順１と２と３は任意の順に入れ換えてもよいし、手順６は手順５の構文解析部分に含めてしまってもよいし、手順１０の閾値により構文解析木を取捨選択する部分は手順９の構文解析部分に含めてしまってもよい。
【０１６３】
［他の実施の形態］
さて、これまで本発明の実施の形態について説明したが、本発明は、上述した実施の形態以外にも、上記特許請求の範囲に記載した技術的思想の範囲内において種々の異なる実施の形態にて実施されてよいものである。
【０１６４】
例えば、ＲＮＡ配列解析装置１００がスタンドアローンの形態でＲＮＡ配列解析方法を行う場合を一例に説明したが、ＲＮＡ配列解析装置１００とは別筐体で構成されるクライアント端末からの要求に応じてＲＮＡ配列解析方法を行い、その処理結果を当該クライアント端末に返却するように構成してもよい。
【０１６５】
また、構造予測部１０２ａは、適合度計算部１０２ｃによる適合度計算を行いながら構文解析部１０２ｂにより構文解析木を導出してもよい。すなわち、構文解析木を導出する構文解析部１０２ｂと、導出された構文解析木に対して適合度の計算を行う適合度計算部１０２ｃをひとつのアルゴリズムにて実現してもよい。このように構成することにより、ＲＮＡ配列と木文法に対して可能な構文解析木は無数（配列長に対して指数のオーダー）に存在するため、構文解析木を導出してから適合度計算を行いソートすると指数オーダーの計算時間と記憶容量が必要となるという問題点を解決することができる。
【０１６６】
また、実施の形態において説明した各処理のうち、自動的に行なわれるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行なわれるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。
特に、構造予測部１０２ａは複数のタスクとして実現してもよく、それぞれのタスクで並列処理を行うように実現してもよい。
この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種の登録データや検索条件等のパラメータを含む情報、画面例、データベース構成については、特記する場合を除いて任意に変更することができる。
【０１６７】
また、ＲＮＡ配列解析装置１００に関して、図示の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。
例えば、ＲＮＡ配列解析装置１００の各サーバが備える処理機能、特に制御部にて行なわれる各処理機能については、その全部または任意の一部を、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）および当該ＣＰＵにて解釈実行されるプログラムにて実現することができ、あるいは、ワイヤードロジックによるハードウェアとして実現することも可能である。なお、プログラムは、後述する記録媒体に記録されており、必要に応じてＲＮＡ配列解析装置１００に機械的に読み取られる。
【０１６８】
記憶部１０６に格納される各種のデータベース等（ＲＮＡ配列データベース１０６ａ〜共通構造マトリックス１０６ｃ）は、ＲＡＭ、ＲＯＭ等のメモリ装置、ハードディスク等の固定ディスク装置、フレキシブルディスク、光ディスク等のストレージ手段であり、各種処理やウェブサイト提供に用いる各種のプログラムやテーブルやファイルやデータベースやウェブページ用ファイル等を格納する。
【０１６９】
また、ＲＮＡ配列解析装置１００は、既知のパーソナルコンピュータ、ワークステーション等の情報処理端末等の情報処理装置にプリンタやモニタやイメージスキャナ等の周辺装置を接続し、該情報処理装置に本発明の方法を実現させるソフトウェア（プログラム、データ等を含む）を実装することにより実現してもよい。
【０１７０】
さらに、ＲＮＡ配列解析装置１００の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷等に応じた任意の単位で、機能的または物理的に分散・統合して構成することができる。例えば、各データベースを独立したデータベース装置として独立に構成してもよく、また、処理の一部をＣＧＩ（Ｃｏｍｍｏｎ  Ｇａｔｅｗａｙ  Ｉｎｔｅｒｆａｃｅ）を用いて実現してもよい。
【０１７１】
また、本発明にかかるプログラムを、コンピュータ読み取り可能な記録媒体に格納することもできる。ここで、この「記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等の任意の「可搬用の物理媒体」や、各種コンピュータシステムに内蔵されるＲＯＭ、ＲＡＭ、ＨＤ等の任意の「固定用の物理媒体」、を含むものとする。
【０１７２】
また、「プログラム」とは、任意の言語や記述方法にて記述されたデータ処理方法であり、ソースコードやバイナリコード等の形式を問わない。なお、「プログラム」は必ずしも単一的に構成されるものに限られず、複数のモジュールやライブラリとして分散構成されるものや、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）に代表される別個のプログラムと協働してその機能を達成するものをも含む。なお、実施の形態に示した各装置において記録媒体を読み取るための具体的な構成、読み取り手順、あるいは、読み取り後のインストール手順等については、周知の構成や手順を用いることができる。
【０１７３】
また、ネットワーク３００は、ＲＮＡ配列解析装置１００と外部システム２００とを相互に接続する機能を有し、例えば、インターネットや、イントラネットや、ＬＡＮ（有線／無線の双方を含む）や、ＶＡＮや、パソコン通信網や、公衆電話網（アナログ／デジタルの双方を含む）や、専用回線網（アナログ／デジタルの双方を含む）や、ＣＡＴＶ網や、ＩＭＴ２０００方式、ＧＳＭ方式またはＰＤＣ／ＰＤＣ―Ｐ方式等の携帯回線交換網／携帯パケット交換網や、無線呼出網や、Ｂｌｕｅｔｏｏｔｈ等の局所無線網や、ＰＨＳ網や、ＣＳ、ＢＳまたはＩＳＤＢ等の衛星通信網等のうちいずれかを含んでもよい。すなわち、本システムは、有線・無線を問わず任意のネットワークを介して、各種データを送受信することができる。
【０１７４】
【発明の効果】
以上詳細に説明したように、本発明によれば、ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納し、ＲＮＡ配列を生成文法に適用して構文解析木を導出し、導出された構文解析木に対して適合度を計算し、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を適合度が高い順にソートし、ソートされた構文解析木をＲＮＡ配列の二次構造の候補として出力するので、一配列に対して多文法で構文解析を行うことができるようになる。すなわち、各生成文法に対してそれぞれ構文解析し適合度計算を行い適合度を得る。その結果、生成文法ごとに適合度が得られることになり、それらの適合度をソートすることによって生成文法に順位を付ける。これにより、生成文法に対する構造トポロジーにも順位が付けられることになるので、最終的にＲＮＡ配列が取り得る可能性の高い順に構造トポロジーを確認することができるＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体を提供することができる。
【０１７５】
また、本発明によれば、ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納し、ＲＮＡ配列を生成文法に適用して構文解析木を導出し、導出された構文解析木に対して適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を上記構造トポロジーの二次構造を持つＲＮＡ配列の候補として出力するので、多配列に対して一文法で構文解析を行うことができるようになる。すなわち、与えられた特定の構造トポロジーに対し、対応する生成文法を取得し、これを用いてＲＮＡ配列データベースに格納されているすべてまたは一部のＲＮＡ配列をそれぞれ構文解析し、ある閾値以下の適合度で構文解析に成功したＲＮＡ配列群を結果として出力する。これにより、与えられた特定の二次構造を取り得るようなＲＮＡ配列を検索することができるＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体を提供することができる。
【０１７６】
また、本発明によれば、ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納し、ＲＮＡ配列を生成文法に適用して構文解析木を導出し、導出された構文解析木に対して適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出し、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と構造トポロジーに対応する格子部分をマークすることにより、ＲＮＡ配列間で共通に有する構造トポロジーを可視化するので、ＲＮＡ配列間の共通構造を容易に発見することができるＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体を提供することができる。
【０１７７】
また、本発明によれば、ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納し、利用者が入力したＤＮＡ配列から転写されるＲＮＡ配列を作成し、作成されたＲＮＡ配列に対して生成文法を適用して構文解析木を導出し、導出された構文解析木に対して適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列に対応するＤＮＡ配列部分を遺伝子の候補として予測するので、ＤＮＡ配列のうち既知のトポロジーを有する可能性のあるＲＮＡ配列に対応する部分について、遺伝子部分である可能性があることを予測することができるＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体を提供することができる。
【０１７８】
また、本発明によれば、ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納し、ＲＮＡ配列を生成文法に適用して構文解析木を導出し、導出された構文解析木に対して適合度の計算を行い、計算された適合度に基づいてＲＮＡ配列間の類似度を計算するので、ＲＮＡ構造の類似度を容易に求めることができるＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体を提供することができる。
【０１７９】
さらに、本発明によれば、ＲＮＡ二次構造の構造トポロジーと、当該構造トポロジーに適合する生成文法とを対応付けて格納し、ＲＮＡ配列を生成文法に適用して構文解析木を導出し、導出された構文解析木に対して適合度の計算を行い、計算された適合度のうち予め定めた条件を満たす適合度である構文解析木を導出したＲＮＡ配列を抽出し、構造トポロジーとＲＮＡ配列とを二次元マトリックスで表示し、二次元マトリックスにおいて抽出されたＲＮＡ配列と構造トポロジーに対応する格子部分に適合度を表示する適合度マトリックスを作成し、適合度マトリックスについて、適合度により構造トポロジーをソートし、他のＲＮＡ配列について当該ソートされた構造トポロジーの順番に対応する生成文法により構文解析を行い適合度が最大となる構文解析木を求め、予め定めた条件を満たす適合度を持つ構文解析木に対応する他のＲＮＡ配列を抽出するので、共通の構造を持つＲＮＡ配列を容易に発見することができるＲＮＡ配列解析装置、ＲＮＡ配列解析方法、プログラム、および、記録媒体を提供することができる。
【配列表】
0003881238.tif 000008
0003881238.tif 000009
0003881238.tif 000010
【図面の簡単な説明】
【図１】ＲＮＡの構造トポロジーの一例を説明する図である。
【図２】従来技術によるＲＮＡの二次構造がステムループをとる場合の構文解析木の一例を示す図である。
【図３】従来技術によるＲＮＡ二次構造の構造トポロジーについて、文法が固定されるとそれに対応した構造トポロジーが規定されることを示す概念図である。
【図４】従来技術である木文法パーザを用いて、既知の文法からＲＮＡ配列の構文解析木を導出する場合の一例を示す図である。
【図５】本発明が適用される本システムの構成の一例を示すブロック図である。
【図６】文法データベース１０６ｂに格納される情報の一例を示す図である。
【図７】本実施の形態における本システムのＲＮＡ二次構造予測処理の一例を示す処理概念図である。
【図８】本実施の形態における本システムの同一構造ＲＮＡ配列抽出処理の一例を示す処理概念図である。
【図９】本実施の形態における本システムの共通構造抽出処理の一例を示す処理概念図である。
【図１０】本実施の形態における本システムの構造類似度計算処理の一例を示す処理概念図である。
【図１１】本実施の形態における本システムの遺伝子予測処理の一例を示す処理概念図である。
【図１２】ペナルティＰと類似度ベクトルｓ1、ｓ2の概念を説明する図である。
【図１３】ＲＮＡ二次構造トポロジーの例を示す図である。
【図１４】ｓ1の構文解析木と二次構造を示す図である。
【図１５】塩基対の自由エネルギーを示す図である。
【図１６】ループの自由エネルギーを示す図である。
【図１７】それぞれの文法について−ΔＧの適合度指標において最適な構文解析木とそれに対応する二次構造を示す図である。
【図１８】選択されたトポロジー集合のなかでｓ2が適合する構造候補を示す図である。
【図１９】選択されたトポロジーをとりうる配列の候補を示す図である。
【図２０】構文解析木の適合度を要素に持つマトリックスを示す図である。
【図２１】ｓの最適な二次構造を示す図である。
【図２２】構文解析木の適合度を要素に持つマトリックスを示す図である。
【図２３】出力結果の一例を示す図である。
【符号の説明】
１００  ＲＮＡ配列解析装置
１０２  制御部
１０２ａ  構造予測部
１０２ｂ  構文解析部
１０２ｃ  適合度計算部
１０２ｄ  類似度計算部
１０２ｆ  共通構造マトリックス作成部
１０２ｇ  遺伝子予測部
１０４  通信制御インターフェース部
１０６  記憶部
１０６ａ  ＲＮＡ配列データベース
１０６ｂ  文法データベース
１０６ｃ  共通構造マトリックス
１０８  入出力制御インターフェース部
１１２  入力装置
１１４  出力装置
２００  外部システム
３００  ネットワーク
【図１】
0003881238.tif 000011
【図２】
0003881238.tif 000012
【図３】
0003881238.tif 000013
【図４】
0003881238.tif 000014
【図５】
0003881238.tif 000015
【図６】
0003881238.tif 000016
【図７】
0003881238.tif 000017
【図８】
0003881238.tif 000018
【図９】
0003881238.tif 000019
【図１０】
0003881238.tif 000020
【図１１】
0003881238.tif 000021
【図１２】
0003881238.tif 000022
【図１３】
0003881238.tif 000023
【図１４】
0003881238.tif 000024
【図１５】
0003881238.tif 000025
【図１６】
0003881238.tif 000026
【図１７】
0003881238.tif 000027
【図１８】
0003881238.tif 000028
【図１９】
0003881238.tif 000029
【図２０】
0003881238.tif 000030
【図２１】
0003881238.tif 000031
【図２２】
0003881238.tif 000032
【図２３】
0003881238.tif 000033