図面 (/)

技術 RNA配列情報処理装置

出願人 国立研究開発法人産業技術総合研究所みずほ情報総研株式会社国立大学法人東京大学
発明者 津田宏治金大真浜田道昭浅井潔
出願日 2006年2月27日 (14年9ヶ月経過) 出願番号 2006-049694
公開日 2007年9月6日 (13年2ヶ月経過) 公開番号 2007-226700
状態 特許登録済
技術分野 特定用途計算機 突然変異または遺伝子工学
主要キーワード ステムパターン ループ距離 最小許容値 最小性 ラベル集合 パターンα 導出パターン 枝狩り
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2007年9月6日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (19)

課題

RNA配列群から2次構造モチーフを抽出する新規な技術を提供する。

解決手段

複数のRNA配列データの各々から、RNA2次構造の複数のステム候補が抽出される。各RNA配列のステム候補を用いてステムグラフが生成される。ステムグラフは、複数のステム候補を頂点として有し、頂点間を辺で結んだグラフである。複数のRNA配列に対応する複数のステムグラフが分析される。それらステムグラフに頻出する類似した部分グラフが、RNA2次構造モチーフを表す頻出ステムパターンとして抽出される。複数のステムグラフのステム候補群が分類されて、分類データが生成される。分類データを用いて、類似する部分グラフが抽出される。ラベル付き有向グラフが好適に生成される。また、分類データとして階層的なタクソノミデータが生成される。

概要

背景

近年、多くのRNAがタンパク質翻訳されることなく、それ自身が機能性分子として生理学的に重要な役割を果たすことが明らかになってきた。これらのRNAは総称して機能性RNA(functional RNA)または非コードRNA(non-coding RNA, ncRNA)と呼ばれ非常に注目を集めている。たんぱく質と同様に、機能性RNAは、1次配列よりも立体構造がその機能に重要であると考えられている。また、Tinoco らは、RNAの立体構造は2次構造により大部分が決定されるとの報告をしている(非特許文献1)。それらを裏付けるように、多くの機能性RNAが、進化的に高度に保存された大域的あるいは局所的な2次構造モチーフを有する機能ファミリーを形成している(例えばtRNA,RNaseP-bact-a, tmRNAなど(http://www.sanger.ac.uk/software/rfam/))。従って、機能性RNAファミリーを特定すること及び機能性RNAファミリーを特徴付ける2次構造モチーフを抽出することは、機能性RNAを解析する際に非常に有用な情報をもたらす。

現在のところ、RNAの2次構造予測の手法は大きく分けて2種類存在する。そのひとつが、mfold(非特許文献2)やRNAfold(非特許文献3)に代表される、最小自由エネルギー(Minimum Free energy,MFE)に基づいた単一のRNA配列からの2次構造予測である。これらの手法は比較的古くから研究がなされているが、一般的にはそれほど高精度ではない。その理由は、エネルギーパラメタの精度や、また、実際のRNA分子は他の分子との相互作用の中で立体構造を形成しているため単一の配列の最適な構造とは異なることなど、にあると考えられる。そのため、最適な構造だけでなく、準最適な2次構造まで導出する手法(非特許文献4、5、6)や統計的にRNAの2次構造をサンプリングする手法(非特許文献7、8)の研究もなされている。

もうひとつが、共通の二次構造を有すると考えられる複数のRNAを用いた(共通)2次構造予測手法である。この手法には、入力配列アラインメントを必要とするもの(RNAalifold(非特許文献9)、ILM(非特許文献10)、Pfold(非特許文献11)など) とアラインメントを必要としないもの(ScaRNA(非特許文献12)、Cofolga(非特許文献13)、PMcomp/PMmulti(非特許文献14)、RNAcast(非特許文献15)、comRNA(非特許文献16)、CaRNAc(非特許文献17)など)が存在する。これらの手法は、似たような構造を有する入力配列群が適切に与えられれば、MFEだけに基づいた2次構造予測よりも多くの情報を用いるので一般的には精度が良いとされている。ただし、アラインメントを仮定せずに、複数配列からその共通2次構造を導出する数理的に厳密なアルゴリズムは、Sankoff アルゴリズム(非特許文献18)と呼ばれるものと等価となり、時間計算量と記憶計算量が膨大である。

このような一般的な2次構造の予測手法だけでなく、RNAのモチーフに焦点を当てたRNA情報解析技術も多数存在する(非特許文献19)。ERPIN(非特許文献20、21)、Infernal(非特許文献22)、RNAMotif(非特許文献23)は、RNAのマルチプルアラインメントから、それらの2次構造モチーフのモデル化を行い、構築されたモデルを用いてゲノム上からそのモデルに適合する2次構造モチーフの探索を行う。すなわちこれらの手法は、既知のモチーフを有する配列を発見する際に利用可能である。一方で、ファミリーを形成すると考えられる機能性RNA配列群から、そのファミリーを特徴付けるモチーフを抽出するための手法も存在する。GPRM(非特許文献24)は、遺伝的アルゴリズムを用いて入力配列群とランダム配列群とを区別する2次構造モチーフの発見を行う。RNAprofile(非特許文献25)は、Greedy かつヒューリスティックな方法により探索空間を減少させ、整列していないRNA配列群から局所的に保存された2次構造モチーフを発見する手法を提案している。さらについ最近では、CMfinder(非特許文献26)と呼ばれるCovariance Model とヒューリスティック手法を組み合わせた、ノイズに対してロバストな、非整列RNA配列群からのモチーフ発見手法も提案されている。これらの機能性RNAファミリーからのモチーフ抽出手法は、ある程度のノイズに対しては影響を受けないような工夫がされているが、基本的には単一のRNAのファミリーである配列群に適用する手法である。しかしながら、解析対象となるRNA配列集合に複数のファミリーや未知のファミリーが含まれるという現実的な状況においては、機能性RNAファミリーの特定と2次構造モチーフの抽出は表裏一体となり、同時に行われることが望ましい。なぜなら、ファミリーの決定にはファミリーを特徴付ける2次構造モチーフが必要であり、かつ、2次構造モチーフの決定にはファミリーが必要となるからである。これは、ある意味、特徴抽出クラスタリングを同時に行う問題に近いといえる。

その他の関連する背景技術を説明すると、RNA配列のグラフによるモデル化の既存手法としては、RAG(非特許文献27)が有名であるが、これはRNAの2次構造のモデル化を行う方法である。また、非特許文献28は、RNAファミリーの2次構造のプロファイルが与えられた際に、そのプロファイルをグラフで表現すると同時に、プロファイルを用いてゲノム配列(の断片)をグラフによりモデル化する方法を提案している。
I Jr Tinoco and C Bustamante. How RNA folds. J Mol Biol, Vol. 293, No. 2, pp. 271-281, Oct 1999.
Michael Zuker. Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res, Vol. 31, No. 13, pp. 3406-3415, Jul 2003.
Ivo L Hofacker. Vienna RNA secondary structure server. Nucleic Acids Res, Vol. 31, No. 13, pp. 3429-3431, Jul 2003.
Robert Giegerich, Bjorn Voss, and Marc Rehmsmeier. Abstract shapes of RNA. Nucleic Acids Res, Vol. 32, No. 16, pp. 4843-4851, 2004. Evaluation Studies.
Steffen P, Voss B, Rehmsmeier M, Reeder J, and Giegerich R. RNAshapes: an integrated RNA analysis package based on abstract shapes. Bioinformatics, Dec 2005. JOURNALARTICLE.
S Wuchty, W Fontana, I L Hofacker, and P Schuster. Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers, Vol. 49, No. 2, pp. 145-165, Feb 1999.
Chi Yu Chan, Charles E Lawrence, and Ye Ding. Structure clustering features on the Sfold Web server. Bioinformatics, Vol. 21, No. 20, pp. 3926-3928, Oct 2005.
Ye Ding, Chi Yu Chan, and Charles E Lawrence. Sfold web server for statistical folding and rational design of nucleic acids. Nucleic Acids Res, Vol. 32, No. Web Server issue, pp. 135-141, Jul 2004.
Stefan Washietl and Ivo L Hofacker. Consensus folding of aligned sequences as a new measure for the detection of functional RNAs by comparative genomics. J Mol Biol, Vol. 342, No. 1, pp. 19-30, Sep 2004.
Jianhua Ruan, Gary D Stormo, and Weixiong Zhang.ILM: a web server for predicting RNA secondary structures with pseudoknots. Nucleic Acids Res, Vol. 32, No. Web Server issue, pp. 146-149, Jul 2004.
Bjarne Knudsen and Jotun Hein. Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Res, Vol. 31, No. 13, pp. 3423-3428, Jul 2003. Evaluation Studies.
Y Tabei, K Tsuda, T Kin, and K Asai.SCARNA:Fast and Accurate Structural Alignment of RNA Sequences by Matching Fixed-length Stem Fragments. submitted to Bioinformatics.
Akito Taneda. Cofolga: a genetic algorithm for finding the common folding of two RNAs. Comput Biol Chem, Vol. 29, No. 2, pp. 111-119, Apr 2005.
Ivo L Hofacker, Stephan H F Bernhart, and Peter F Stadler. Alignment of RNA base pairing probability matrices. Bioinformatics, Vol. 20, No. 14, pp. 2222-2227, Sep 2004. Evaluation Studies.
Jens Reeder and Robert Giegerich. Consensus shapes: an alternative to the Sankoff algorithm for RNAc onsensus structure prediction. Bioinformatics, Vol. 21, No. 17, pp. 3516-3523, Sep 2005.
Yongmei Ji, Xing Xu, and Gary D Stormo. A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics, Vol. 20, No. 10, pp. 1591-1602, Jul 2004. Evaluation Studies.
Helene Touzet and Olivier Perriquet. CARNAC: folding families of related RNAs. Nucleic Acids Res, Vol. 32, No. Web Server issue, pp. 142-145, Jul 2004. Evaluation Studies.
D Sankoff. Simultaneous solution of the RNA folding alignment and pro25 tosequence problems. SIAM J. Appl. Math, pp. 810-825, 1985.
Athanasius F. Bompf¨unewerer, Christoph Flamm, Claudia Fried, Guido Fritzsch, Ivo L. Hofacker, J¨org Lehmann, Kristin Missal, Axel Mosig, Bettina M¨uller, Sonja J. Prohaska, B¨arbel M. R. Stadler, Peter F. Stadler, Andrea Tanzer, Stefan Washietl, and Christina Witwer. Evolutionary patterns of non-coding rnas. Th. Biosci., Vol. 123, pp. 301-369, 2005.
Andre Lambert, Jean-Fred Fontaine, Matthieu Legendre,Fabrice Leclerc, Emmanuelle Permal, Francois Major, Harald Putzer, Olivier Delfour, Bernard Michot, and Daniel Gautheret. TheERPIN server: an interface to profile-based RNA motif identification. Nucleic Acids Res, Vol. 32, No. Web Server issue, pp. 160-165, Jul 2004. Evaluation Studies.
D Gautheret and A Lambert. Direct RNA motif definition and identification from multiple sequence alignments using secondary structure profiles. J Mol Biol, Vol. 313, No. 5, pp. 1003-1011, Nov 2001.
S R Eddy and R Durbin. RNA sequence analysis using covariance models. Nucleic Acids Res, Vol. 22, No. 11, pp. 2079-2088, Jun 1994.
T J Macke, D J Ecker, R R Gutell, D Gautheret, D A Case, and R Sampath. RNAMotif, an RNA secondary structure definition and search algorithm. Nucleic Acids Res, Vol. 29, No. 22, pp. 4724-4735, Nov 2001.
Yuh-Jyh Hu. Prediction of consensus structural motifs in a family of coregulated RNA sequences. Nucleic Acids Res, Vol. 30, No. 17, pp. 3886-3893, Sep 2002.
Giulio Pavesi, Giancarlo Mauri, Marco Stefani, and Graziano Pesole. RNAProfile: an algorithm for finding conserved secondary structure motifs in unaligned RNA sequences. Nucleic Acids Res, Vol. 32, No. 10, pp. 3258-3269, 2004.
Yao Z, Weinberg Z, and Ruzzo WL. CMfinder-a covariance model based RNA motif finding algorithm. Bioinformatics, Dec 2005. JOURNAL ARTICLE.
Daniela Fera, Namhee Kim, Nahum Shiffeldrim, Julie Zorn, Uri Laserson, Hin Hark Gan, and Tamar Schlick. RAG: RNA-As-Graphs web resource.BMCBioinformatics, Vol. 5, p. 88, Jul 2004.
Yinglei Song, Chunmei Liu, Russell L. Malmberg, Fangfang Pan, and Liming Cai. Tree decomposition based fast search of rna structures including pseudoknots in genomes. In CSB, pp. 223.234.IEEE Computer Society, 2005.

概要

RNA配列群から2次構造モチーフを抽出する新規な技術を提供する。 複数のRNA配列データの各々から、RNA2次構造の複数のステム候補が抽出される。各RNA配列のステム候補を用いてステムグラフが生成される。ステムグラフは、複数のステム候補を頂点として有し、頂点間を辺で結んだグラフである。複数のRNA配列に対応する複数のステムグラフが分析される。それらステムグラフに頻出する類似した部分グラフが、RNA2次構造モチーフを表す頻出ステムパターンとして抽出される。複数のステムグラフのステム候補群が分類されて、分類データが生成される。分類データを用いて、類似する部分グラフが抽出される。ラベル付き有向グラフが好適に生成される。また、分類データとして階層的なタクソノミデータが生成される。

目的

本発明は上記背景の下でなされたものであり、その目的は、コンピュータを用いたバイオインフォマテクス情報処理によってRNA配列群から2次構造モチーフを抽出することができる好適な配列データ処理技術を提供することにある。本発明の一つの目的は、機能性RNAのファミリーの特定とモチーフ抽出を同時に行うことが可能な技術を提供することにある。

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

複数のRNA配列データの各々から、RNA2次構造の複数のステム候補を抽出するステム候補抽出部と、各RNA配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成するグラフ生成部と、前記複数のRNA配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、RNA2次構造モチーフを表す頻出ステムパターンとして抽出するグラフ解析部と、を備えたことを特徴とするRNA配列情報処理装置

請求項2

前記グラフ生成部は、前記RNA配列上での各ステム候補対の位置関係に応じた向きを、前記各ステム候補対を結ぶ辺のラベルに付与し、前記グラフ解析部は、前記複数のステムグラフから、対応する辺の向きが同じ前記部分グラフを抽出することを特徴とする請求項1に記載のRNA配列情報処理装置。

請求項3

前記グラフ生成部は、各ステム候補対の接続関係並列、埋込み、重複のいずれかに属するかの情報を、前記各ステム候補対を結ぶ辺のラベルに付与し、前記グラフ解析部は、前記複数のステムグラフから、対応する辺の前記接続関係が同じ前記部分グラフを抽出することを特徴とする請求項1または2に記載のRNA配列情報処理装置。

請求項4

前記グラフ生成部は、前記並列、埋込みおよび重複のいずれにも該当しないステム候補対を辺での接続対象から除外することを特徴とする請求項3に記載のRNA配列情報処理装置。

請求項5

前記グラフ生成部は、各頂点が部分グラフ内のすべての他の頂点と辺で結ばれる完全部分グラフを抽出することを特徴とする請求項1〜4のいずれかに記載のRNA配列情報処理装置。

請求項6

前記複数のステムグラフに含まれる前記複数のステム候補を類似性に基づいて分類する分類データを生成する分類データ生成部を含み、前記グラフ解析部は、前記複数のステムグラフから、対応する頂点のステム候補が同じ分類に属する前記部分グラフを抽出することを特徴とする請求項1〜5のいずれかに記載のRNA配列情報処理装置。

請求項7

前記分類データ生成部は、前記分類データとして、前記複数のステム候補を、類似範囲の広さが下位層から上位層へ向かって増大するように階層的にクラスタリングを行ったタクソノミデータを生成し、前記グラフ解析部は、前記タクソノミデータに基づき、対応する頂点のステム候補が下位層では異なる分類に属しても上位層では同一分類に属する前記部分グラフを抽出することを特徴とする請求項6に記載のRNA配列情報処理装置。

請求項8

前記タクソノミデータにて階層に応じて増大する一般化コスト最大許容値である最大一般化コストを入力する最大一般化コスト入力部を含み、前記グラフ解析部は、前記最大一般化コスト以下の一般化コストを有する前記部分グラフを抽出することを特徴とする請求項7に記載のRNA配列情報処理装置。

請求項9

前記分類データ生成部は、ステム候補対の類似性を表す類似性パラメータを、ステム候補対の配列相同性、ステム候補により形成されるループの距離の類似性、および、RNA配列内でのステム候補の位置の類似性の少なくとも一つに応じて求めることを特徴とする請求項6〜8のいずれかに記載のRNA配列情報処理装置。

請求項10

前記複数のステムグラフにおける前記部分グラフの支持度最小許容値である最小支持度を入力する最小支持度入力部を含み、前記グラフ解析部は、前記最小支持度以上の支持度を有する前記部分グラフを抽出することを特徴とする請求項1〜9のいずれかに記載のRNA配列情報処理装置。

請求項11

前記ステム候補抽出部は、分子構造エネルギに基づいて前記RNA配列上の任意の2つの塩基塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域を前記ステム候補として抽出することを特徴とする請求項1〜10のいずれかに記載のRNA配列情報処理装置。

請求項12

複数のRNA配列からコンピュータ処理によって2次構造モチーフを抽出するRNA配列情報処理方法であって、複数のRNA配列データの各々から、RNA2次構造の複数のステム候補を抽出し、各RNA配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、前記複数のRNA配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、RNA2次構造モチーフを表す頻出ステムパターンとして抽出する、ことを特徴とするRNA配列情報処理方法。

請求項13

複数のRNA配列から2次構造モチーフを抽出する配列情報処理をコンピュータに実行させるRNA配列情報処理プログラムであって、複数のRNA配列データの各々から、RNA2次構造の複数のステム候補を抽出し、各RNA配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、前記複数のRNA配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、RNA2次構造モチーフを表す頻出ステムパターンとして抽出する、処理を前記コンピュータに実行させることを特徴とするRNA配列情報処理プログラム。

技術分野

0001

本発明は、複数のRNA配列データをバイオインフォマテクス技術によって処理して、それら複数のRNA配列データに共通に含まれる2次構造モチーフを抽出する技術に関する。

背景技術

0002

近年、多くのRNAがタンパク質翻訳されることなく、それ自身が機能性分子として生理学的に重要な役割を果たすことが明らかになってきた。これらのRNAは総称して機能性RNA(functional RNA)または非コードRNA(non-coding RNA, ncRNA)と呼ばれ非常に注目を集めている。たんぱく質と同様に、機能性RNAは、1次配列よりも立体構造がその機能に重要であると考えられている。また、Tinoco らは、RNAの立体構造は2次構造により大部分が決定されるとの報告をしている(非特許文献1)。それらを裏付けるように、多くの機能性RNAが、進化的に高度に保存された大域的あるいは局所的な2次構造モチーフを有する機能ファミリーを形成している(例えばtRNA,RNaseP-bact-a, tmRNAなど(http://www.sanger.ac.uk/software/rfam/))。従って、機能性RNAファミリーを特定すること及び機能性RNAファミリーを特徴付ける2次構造モチーフを抽出することは、機能性RNAを解析する際に非常に有用な情報をもたらす。

0003

現在のところ、RNAの2次構造予測の手法は大きく分けて2種類存在する。そのひとつが、mfold(非特許文献2)やRNAfold(非特許文献3)に代表される、最小自由エネルギー(Minimum Free energy,MFE)に基づいた単一のRNA配列からの2次構造予測である。これらの手法は比較的古くから研究がなされているが、一般的にはそれほど高精度ではない。その理由は、エネルギーパラメタの精度や、また、実際のRNA分子は他の分子との相互作用の中で立体構造を形成しているため単一の配列の最適な構造とは異なることなど、にあると考えられる。そのため、最適な構造だけでなく、準最適な2次構造まで導出する手法(非特許文献4、5、6)や統計的にRNAの2次構造をサンプリングする手法(非特許文献7、8)の研究もなされている。

0004

もうひとつが、共通の二次構造を有すると考えられる複数のRNAを用いた(共通)2次構造予測手法である。この手法には、入力配列アラインメントを必要とするもの(RNAalifold(非特許文献9)、ILM(非特許文献10)、Pfold(非特許文献11)など) とアラインメントを必要としないもの(ScaRNA(非特許文献12)、Cofolga(非特許文献13)、PMcomp/PMmulti(非特許文献14)、RNAcast(非特許文献15)、comRNA(非特許文献16)、CaRNAc(非特許文献17)など)が存在する。これらの手法は、似たような構造を有する入力配列群が適切に与えられれば、MFEだけに基づいた2次構造予測よりも多くの情報を用いるので一般的には精度が良いとされている。ただし、アラインメントを仮定せずに、複数配列からその共通2次構造を導出する数理的に厳密なアルゴリズムは、Sankoff アルゴリズム(非特許文献18)と呼ばれるものと等価となり、時間計算量と記憶計算量が膨大である。

0005

このような一般的な2次構造の予測手法だけでなく、RNAのモチーフに焦点を当てたRNA情報解析技術も多数存在する(非特許文献19)。ERPIN(非特許文献20、21)、Infernal(非特許文献22)、RNAMotif(非特許文献23)は、RNAのマルチプルアラインメントから、それらの2次構造モチーフのモデル化を行い、構築されたモデルを用いてゲノム上からそのモデルに適合する2次構造モチーフの探索を行う。すなわちこれらの手法は、既知のモチーフを有する配列を発見する際に利用可能である。一方で、ファミリーを形成すると考えられる機能性RNA配列群から、そのファミリーを特徴付けるモチーフを抽出するための手法も存在する。GPRM(非特許文献24)は、遺伝的アルゴリズムを用いて入力配列群とランダム配列群とを区別する2次構造モチーフの発見を行う。RNAprofile(非特許文献25)は、Greedy かつヒューリスティックな方法により探索空間を減少させ、整列していないRNA配列群から局所的に保存された2次構造モチーフを発見する手法を提案している。さらについ最近では、CMfinder(非特許文献26)と呼ばれるCovariance Model とヒューリスティック手法を組み合わせた、ノイズに対してロバストな、非整列RNA配列群からのモチーフ発見手法も提案されている。これらの機能性RNAファミリーからのモチーフ抽出手法は、ある程度のノイズに対しては影響を受けないような工夫がされているが、基本的には単一のRNAのファミリーである配列群に適用する手法である。しかしながら、解析対象となるRNA配列集合に複数のファミリーや未知のファミリーが含まれるという現実的な状況においては、機能性RNAファミリーの特定と2次構造モチーフの抽出は表裏一体となり、同時に行われることが望ましい。なぜなら、ファミリーの決定にはファミリーを特徴付ける2次構造モチーフが必要であり、かつ、2次構造モチーフの決定にはファミリーが必要となるからである。これは、ある意味、特徴抽出クラスタリングを同時に行う問題に近いといえる。

0006

その他の関連する背景技術を説明すると、RNA配列のグラフによるモデル化の既存手法としては、RAG(非特許文献27)が有名であるが、これはRNAの2次構造のモデル化を行う方法である。また、非特許文献28は、RNAファミリーの2次構造のプロファイルが与えられた際に、そのプロファイルをグラフで表現すると同時に、プロファイルを用いてゲノム配列(の断片)をグラフによりモデル化する方法を提案している。
I Jr Tinoco and C Bustamante. How RNA folds. J Mol Biol, Vol. 293, No. 2, pp. 271-281, Oct 1999.
Michael Zuker. Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res, Vol. 31, No. 13, pp. 3406-3415, Jul 2003.
Ivo L Hofacker. Vienna RNA secondary structure server. Nucleic Acids Res, Vol. 31, No. 13, pp. 3429-3431, Jul 2003.
Robert Giegerich, Bjorn Voss, and Marc Rehmsmeier. Abstract shapes of RNA. Nucleic Acids Res, Vol. 32, No. 16, pp. 4843-4851, 2004. Evaluation Studies.
Steffen P, Voss B, Rehmsmeier M, Reeder J, and Giegerich R. RNAshapes: an integrated RNA analysis package based on abstract shapes. Bioinformatics, Dec 2005. JOURNALARTICLE.
S Wuchty, W Fontana, I L Hofacker, and P Schuster. Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers, Vol. 49, No. 2, pp. 145-165, Feb 1999.
Chi Yu Chan, Charles E Lawrence, and Ye Ding. Structure clustering features on the Sfold Web server. Bioinformatics, Vol. 21, No. 20, pp. 3926-3928, Oct 2005.
Ye Ding, Chi Yu Chan, and Charles E Lawrence. Sfold web server for statistical folding and rational design of nucleic acids. Nucleic Acids Res, Vol. 32, No. Web Server issue, pp. 135-141, Jul 2004.
Stefan Washietl and Ivo L Hofacker. Consensus folding of aligned sequences as a new measure for the detection of functional RNAs by comparative genomics. J Mol Biol, Vol. 342, No. 1, pp. 19-30, Sep 2004.
Jianhua Ruan, Gary D Stormo, and Weixiong Zhang.ILM: a web server for predicting RNA secondary structures with pseudoknots. Nucleic Acids Res, Vol. 32, No. Web Server issue, pp. 146-149, Jul 2004.
Bjarne Knudsen and Jotun Hein. Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Res, Vol. 31, No. 13, pp. 3423-3428, Jul 2003. Evaluation Studies.
Y Tabei, K Tsuda, T Kin, and K Asai.SCARNA:Fast and Accurate Structural Alignment of RNA Sequences by Matching Fixed-length Stem Fragments. submitted to Bioinformatics.
Akito Taneda. Cofolga: a genetic algorithm for finding the common folding of two RNAs. Comput Biol Chem, Vol. 29, No. 2, pp. 111-119, Apr 2005.
Ivo L Hofacker, Stephan H F Bernhart, and Peter F Stadler. Alignment of RNA base pairing probability matrices. Bioinformatics, Vol. 20, No. 14, pp. 2222-2227, Sep 2004. Evaluation Studies.
Jens Reeder and Robert Giegerich. Consensus shapes: an alternative to the Sankoff algorithm for RNAc onsensus structure prediction. Bioinformatics, Vol. 21, No. 17, pp. 3516-3523, Sep 2005.
Yongmei Ji, Xing Xu, and Gary D Stormo. A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics, Vol. 20, No. 10, pp. 1591-1602, Jul 2004. Evaluation Studies.
Helene Touzet and Olivier Perriquet. CARNAC: folding families of related RNAs. Nucleic Acids Res, Vol. 32, No. Web Server issue, pp. 142-145, Jul 2004. Evaluation Studies.
D Sankoff. Simultaneous solution of the RNA folding alignment and pro25 tosequence problems. SIAM J. Appl. Math, pp. 810-825, 1985.
Athanasius F. Bompf¨unewerer, Christoph Flamm, Claudia Fried, Guido Fritzsch, Ivo L. Hofacker, J¨org Lehmann, Kristin Missal, Axel Mosig, Bettina M¨uller, Sonja J. Prohaska, B¨arbel M. R. Stadler, Peter F. Stadler, Andrea Tanzer, Stefan Washietl, and Christina Witwer. Evolutionary patterns of non-coding rnas. Th. Biosci., Vol. 123, pp. 301-369, 2005.
Andre Lambert, Jean-Fred Fontaine, Matthieu Legendre,Fabrice Leclerc, Emmanuelle Permal, Francois Major, Harald Putzer, Olivier Delfour, Bernard Michot, and Daniel Gautheret. TheERPIN server: an interface to profile-based RNA motif identification. Nucleic Acids Res, Vol. 32, No. Web Server issue, pp. 160-165, Jul 2004. Evaluation Studies.
D Gautheret and A Lambert. Direct RNA motif definition and identification from multiple sequence alignments using secondary structure profiles. J Mol Biol, Vol. 313, No. 5, pp. 1003-1011, Nov 2001.
S R Eddy and R Durbin. RNA sequence analysis using covariance models. Nucleic Acids Res, Vol. 22, No. 11, pp. 2079-2088, Jun 1994.
T J Macke, D J Ecker, R R Gutell, D Gautheret, D A Case, and R Sampath. RNAMotif, an RNA secondary structure definition and search algorithm. Nucleic Acids Res, Vol. 29, No. 22, pp. 4724-4735, Nov 2001.
Yuh-Jyh Hu. Prediction of consensus structural motifs in a family of coregulated RNA sequences. Nucleic Acids Res, Vol. 30, No. 17, pp. 3886-3893, Sep 2002.
Giulio Pavesi, Giancarlo Mauri, Marco Stefani, and Graziano Pesole. RNAProfile: an algorithm for finding conserved secondary structure motifs in unaligned RNA sequences. Nucleic Acids Res, Vol. 32, No. 10, pp. 3258-3269, 2004.
Yao Z, Weinberg Z, and Ruzzo WL. CMfinder-a covariance model based RNA motif finding algorithm. Bioinformatics, Dec 2005. JOURNAL ARTICLE.
Daniela Fera, Namhee Kim, Nahum Shiffeldrim, Julie Zorn, Uri Laserson, Hin Hark Gan, and Tamar Schlick. RAG: RNA-As-Graphs web resource.BMCBioinformatics, Vol. 5, p. 88, Jul 2004.
Yinglei Song, Chunmei Liu, Russell L. Malmberg, Fangfang Pan, and Liming Cai. Tree decomposition based fast search of rna structures including pseudoknots in genomes. In CSB, pp. 223.234.IEEE Computer Society, 2005.

発明が解決しようとする課題

0007

上述してきたように、機能性RNAの機能ファミリーを同定すること及びファミリーを特徴付ける2次構造モチーフを抽出することは共に機能性RNAの解析において非常に重要である。解析対象となるRNA配列集合に複数のファミリーや未知のファミリーが含まれているという現実的な問題設定の下では、機能性RNAファミリーの特定と2次構造モチーフの抽出は互いに密接に関連した問題となり、同時に解くべき必要が生じる。なぜなら、ファミリーの決定にはファミリーを特徴付ける2次構造モチーフが必要であり、かつ、2次構造モチーフの決定にはファミリーが必要となるからである。しかしながら、既存のRNA解析手法では、これらの問題を同時に解く手法は存在しない。

0008

本発明は上記背景の下でなされたものであり、その目的は、コンピュータを用いたバイオインフォマティクスの情報処理によってRNA配列群から2次構造モチーフを抽出することができる好適な配列データ処理技術を提供することにある。本発明の一つの目的は、機能性RNAのファミリーの特定とモチーフ抽出を同時に行うことが可能な技術を提供することにある。

課題を解決するための手段

0009

本発明は、RNA配列データを対象とした配列情報処理技術を提供する。本発明は、概略的には、RNA配列群をタクソノミ(Taxonomy)を用いたラベル付き有向グラフでモデル化し、近年データマイニングの分野で活発に研究されているグラフ解析グラフマイニング)手法を応用して、配列群に頻出するステムパターン(2次構造モチーフ)の抽出およびそのステムパターンを有するRNA配列集合(機能性RNAファミリー)の特定を行う。ここで言うグラフマイニング手法とは、与えられたグラフセットから多頻度出現する部分グラフグラフパターン)を効率的かつ完全に抽出する手法であり、後に例示されるように近年様々なアルゴリズムが提案されている。本発明は、これらのグラフマイニング手法を応用すると同時に、抽出するグラフパターンがClique(完全グラフ)であるという性質を利用して探索空間を効率良く削減させる。さらに、本発明は、グラフの一般化コストと呼ばれる新しい概念を導入することにより、更なる効率化を行っている。また、本発明は、ランク付けされたステムパターンの候補を複数導出すると同時に、ステムのパターンに対して各RNAの2次構造を複数導出することが可能である。本発明で提案している、頂点間類似度からクラスタリングにより頂点ラベルのTaxonomy を構築し頻出グラフマイニングを行う手法は、対象をグラフによりモデル化した際に、頂点間の類似度や非類似度が自然に定義できる場合に好適に適用可能な手法となっている。

0010

本発明の一態様は、RNA配列情報処理装置であり、この装置は、複数のRNA配列データの各々から、RNA2次構造の複数のステム候補を抽出するステム候補抽出部と、各RNA配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成するグラフ生成部と、前記複数のRNA配列からそれぞれ生成された複数の前記ステムグラフを解析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、RNA2次構造モチーフを表す頻出ステムパターンとして抽出するグラフ解析部と、を備えている。

0011

上記のように、本発明は、複数のRNA配列データから複数のステムグラフをそれぞれ生成する。ステムグラフは、RNA配列中の潜在的なステムの候補が頂点であり、頂点間を辺で結んだグラフである。このようなグラフにおいては、部分グラフがステムパターンであり、ステムパターンはRNA配列の部分的な2次構造を表す。したがって、同様の部分グラフが複数のステムグラフに頻出すれば、その類似部分グラフは、複数のRNA配列に共通の2次構造モチーフである。本発明は、この点に着目して、複数のステムグラフに頻出する類似部分グラフを、RNA2次構造モチーフを表す頻出ステムパターンとして抽出している。このようにして、本発明によれば、RNA配列群から2次構造モチーフを抽出することができる。

0012

本発明の情報処理が、機能性RNAのファミリーが特定されていないRNA配列群に適用されたとする。この場合、頻出ステムパターンが抽出されると同時に、頻出ステムパターンを含むRNA配列(ステムグラフ)も分かる。すなわち、2次構造モチーフが抽出されると同時に、2次構造モチーフを含むファミリーを同定することができる。また、本発明は、既に同定されている機能ファミリーの配列群に適用されてもよく、この場合にも2次構造モチーフが好適に抽出される。

0013

前記グラフ生成部は、前記RNA配列上での各ステム候補対の位置関係に応じた向きを、前記各ステム候補対を結ぶ辺のラベルに付与してよい。前記グラフ解析部は、前記複数のステムグラフから、対応する辺の向きが同じ前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0014

前記グラフ生成部は、各ステム候補対の接続関係並列、埋込み、重複のいずれかに属するかの情報を、前記各ステム候補対を結ぶ辺のラベルに付与してよい。前記グラフ解析部は、前記複数のステムグラフから、対応する辺の前記接続関係が同じ前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0015

前記グラフ生成部は、前記並列、埋込みおよび重複のいずれにも該当しないステム候補対を辺での接続対象から除外してよい。これにより、不適当な部分グラフの抽出を回避して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0016

前記グラフ生成部は、各頂点が部分グラフ内のすべての他の頂点と辺で結ばれる完全部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0017

本発明のRNA配列情報処理装置は、前記複数のステムグラフに含まれる前記複数のステム候補を類似性に基づいて分類する分類データを生成する分類データ生成部を含んでよい。前記グラフ解析部は、前記複数のステムグラフから、対応する頂点のステム候補が同じ分類に属する前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0018

前記分類データ生成部は、前記分類データとして、前記複数のステム候補を、類似範囲の広さが下位層から上位層へ向かって増大するように階層的にクラスタリングを行ったタクソノミデータを生成してよい。前記グラフ解析部は、前記タクソノミデータに基づき、対応する頂点のステム候補が下位層では異なる分類に属しても上位層では同一分類に属する前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0019

本発明のRNA配列情報処理装置は、前記タクソノミデータにて階層に応じて増大する一般化コストの最大許容値である最大一般化コストを入力する最大一般化コスト入力部を含んでよい。前記グラフ解析部は、前記最大一般化コスト以下の一般化コストを有する前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0020

前記分類データ生成部は、ステム候補対の類似性を表す類似性パラメータを、ステム候補対の配列相同性、ステム候補により形成されるループの距離の類似性、および、RNA配列内でのステム候補の位置の類似性の少なくとも一つに応じて求めてよい。また、分類データ生成部は、ステム候補対の類似性を類似性パラメータを、ステム候補の塩基対形成確率に応じて求めてよく、このとき、2つのステム候補の塩基対形成確率の和が評価されてよく、そして、和の値が大きいほど類似度が高いと判断されてよい。これにより、ステム候補である頂点間の類似性を適切に判断して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0021

本発明のRNA配列情報処理装置は、前記複数のステムグラフにおける前記部分グラフの支持度最小許容値である最小支持度を入力する最小支持度入力部を含んでよい。前記グラフ解析部は、前記最小支持度以上の支持度を有する前記部分グラフを抽出してよい。支持度はグラフ解析で使われる用語で、頻度(頻出の程度)を表す。最小支持度以上の支持度を有する部分グラフを抽出することにより、RNA配列群に頻出するステムパターンを適切に抽出できる。

0022

前記ステム候補抽出部は、分子構造エネルギに基づいて前記RNA配列上の任意の2つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域を前記ステム候補として抽出してよい。これにより、ステム候補を適切に抽出することができる。

0023

本発明のRNA配列情報処理装置は、単独のコンピュータで実現されてもよく、複数のコンピュータからなるシステムによって実現されてもよい。RNA配列情報処理装置は、インターネット等のネットワークを介して、データの受付(入力)と提供(出力)を行ってもよい。

0024

また、本発明は上記のRNA配列情報処理装置の態様に限定されない。本発明の別の態様は、例えば、コンピュータによる情報処理方法であり、また、そのような方法を実現するプログラムである。このような別の態様にも、上述のRNA配列情報処理装置に関する各種の発明を適用可能なことはもちろんである。

0025

本発明の別の態様は、複数のRNA配列からコンピュータ処理によって2次構造モチーフを抽出するRNA配列情報処理方法である。この方法は、複数のRNA配列データの各々から、RNA2次構造の複数のステム候補を抽出し、各RNA配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、前記複数のRNA配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、RNA2次構造モチーフを表す頻出ステムパターンとして抽出する。この態様でも上述の本発明の利点が得られる。

0026

また、本発明の別の態様は、複数のRNA配列から2次構造モチーフを抽出する配列情報処理をコンピュータに実行させるRNA配列情報処理プログラムである。このプログラムは、複数のRNA配列データの各々から、RNA2次構造の複数のステム候補を抽出し、各RNA配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、前記複数のRNA配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、RNA2次構造モチーフを表す頻出ステムパターンとして抽出する、処理を前記コンピュータに実行させる。この態様でも上述の本発明の利点が得られる。

発明の効果

0027

上記のように、本発明は、コンピュータを用いた情報処理によって複数のRNA配列から2次構造モチーフを抽出することができる配列データ処理技術を提供できる。本発明は、機能性RNAのファミリーの特定とモチーフ抽出を同時に行うことが可能な技術を提供できる。

発明を実施するための最良の形態

0028

以下、本発明の実施の形態を図面を参照して説明する。以下に説明されるように、本実施の形態のバイオインフォマティクス技術は、全体としては、RNA配列を処理の対象とし、RNAの2次構造を有向グラフで表現し、階層的分類に基づいたグラフ探索処理を有向グラフに組み合わせて2次構造パターンの抽出を行う新規な手法を提供する。

0029

まず、本発明のバイオインフォマティクス技術を説明する前に、RNA配列の2次構造を説明する。

0030

図1を参照すると、周知のように、DNAおよびRNAを構成する塩基は、a、u(t)、c、gで表される。そして、aとuが相補塩基対を作り、cとgが相補塩基対を作る。DNAでは、逆相補配列が2重らせんを形成している。これに対して、構造RNAでは、1本鎖が折り畳まれる。そして、相補塩基対により2次構造が作られる。

0031

図2は、局所的な2次構造の例を示している。図示のように、1本鎖RNA上には、互いに相補的な2つの領域が存在している。2箇所の相補的な領域が結合し、これにより2次構造が作られる。2次構造を作る相補的な領域は、ステムと呼ばれている。以下の説明では、ステムを形成する2つの部分配列を必要に応じてパーツまたはステムパーツと呼ぶ。2つのパーツが結合されてステムが形成される。

0032

図3は、より大きな範囲の2次構造の例を示している。図示のように、1つのRNA配列に複数のステムが存在している。

0033

図4は、本実施の形態のRNA配列情報処理装置を実現するコンピュータを示している。図4のコンピュータ1において、プログラム実行部3は、CPU等のプロセッサで構成され、プログラム記憶部5および処理データ記憶部7は、メモリで構成される。また、コンピュータ1は、ハードディスク等の外部記憶装置11を備え、さらに、入力装置13、出力装置15、記録媒体装着部17および通信部19などを備えている。

0034

プログラム記憶部5は、本実施の形態の装置および方法を実現するためのプログラムを記憶し、特に、ステム候補抽出プログラム、グラフ生成プログラム、分類データ生成プログラムおよびグラフ解析プログラムを記憶する。これらプログラムは、外部記憶装置11から読み出され、そいて、プログラム実行部3により実行される。これらプログラムの機能の詳細は後述する。

0035

処理データ記憶部7は、処理されるべきデータや、処理後のデータを記憶する。処理データ記憶部7は、例えば、処理対象のRNA配列データ、ステム候補データ、ステムグラフデータ、分類データおよびグラフ解析データを記憶する。その他にも、メモリは、プログラム実行部3による処理の作業エリアとして機能し、各種の処理データを記憶する。

0036

コンピュータ1へのデータの入出力は、典型的には、入力装置13および出力装置15を介して行われる。その他、データの入出力は、記録媒体装着部17を介して、記録媒体との間で行われてよい。また、データの入出力は、通信部19を介して行われてよい。コンピュータ1がWEBサーバに接続され、ネットワークを介してデータが入出力されてよい。あるいは、コンピュータ1がWEBサーバの機能を有していてもよい。

0037

RNA配列情報処理装置は、概略的には、RNA配列群から、個々の配列に潜在するステム候補を抽出し、RNA配列群に頻出するステムパターンを抽出する。ステムパターンは、複数のステムにより形成されるパターン(部分的配列)である。このステムパターンは、RNAのモチーフ抽出に応用され、また、RNAのファミリー抽出に応用され、さらには、複数配列からの2次構造予測に応用される。

0038

本実施の形態において、入力データと出力データは以下の通りである。入力データは、RNA配列群のデータである。RNA配列群に整列(アライメント)が施されていなくてよい。また、RNA配列群が同一のRNAファミリーに属している必要はない。コンピュータ1はRNA配列情報処理装置として機能し、図4の各種プログラムに従ってRNA配列群のデータを処理して、RNA配列群に頻出する頻出ステムパターンを求め、さらに、頻出ステムパターンに対応する二次構造を求める。これら頻出ステムパターンおよび二次構造が出力データとして出力される。その他、本実施の形態では、パラメータとして最小支持度および最大一般化コストが入力される。これらパラメータは、頻出ステムパターンの抽出処理において、抽出条件として処理される。

0039

図5は、RNA配列情報処理の全体像を示している。図示のように、RNA配列群が入力される(S1)。上述したように、RNA配列群は整列されていなくてよい。各RNA配列がステム候補抽出プログラムの処理を受け(S2)、各RNA配列のステム候補が抽出される(S3)。本実施の形態では、ステム候補抽出プログラムは、塩基対確率行列を生成するプログラムによって実現される。

0040

次に、ステム候補の情報から、ステムグラフと分類データが、グラフ生成プログラムおよび分類データ生成プログラムにより生成される(S4)。各RNA配列に対して一つのステムグラフが生成される。ステムグラフは、RNA配列から抽出された複数のステム候補を頂点とし、頂点間を辺で結んだグラフである。本実施の形態では、後述するようなラベル付き有向グラフが生成される。また、分類データは、複数のRNA配列群から抽出された全部のステム候補(グラフの頂点)をそれらの類似性に基づき分類したデータであり、本実施の形態では図示のように、階層構造を持つツリー型タクソノミデータ(taxonomy)である。

0041

次に、ステムグラフ群がグラフ解析プログラムによって解析されて(S5)、ステムグラフ群に頻出する部分グラフが抽出され、さらに部分グラフに対応する2次構造が求められる(S6)。部分グラフは、ステムグラフの一部の頂点と辺で構成されるパターンであり、ステムパターンに相当する。本実施の形態は、グラフ形状が類似し、かつ、対応する頂点のステム候補が類似し、ステムグラフ群に頻出する部分グラフを抽出する。頂点の類似は分類データから求められる。このような頻出部分グラフが、RNA2次構造モチーフを表す頻出ステムパターンとして抽出される。そして、頻出部分グラフに対応する2次構造が求められる。

0042

図6は、上述した処理を実現するためのRNA配列情報処理装置を機能ブロック図のかたちで示している。図6のRNA配列情報処理装置21において、配列データ入力部23は、RNA配列群のデータを入力する。入力されたRNA配列データは、配列データ記憶部25に記憶される。ステム候補抽出部27は、入力された各々のRNA配列から、RNA2次構造のステム候補を抽出し、ステム候補記憶部29に格納する。

0043

グラフ生成部31は、各RNA配列のステムグラフを生成し、グラフ記憶部33に記憶する。また、分類データ生成部35は、ステムグラフの頂点(ステム候補)に関する分類データを生成して、分類データ記憶部37に格納する。本実施の形態では、ラベル付き有向グラフと階層的なツリー型タクソノミデータが生成される。

0044

グラフ解析部39は、分類データを参照しながらステムグラフ群を解析して、それらステムグラフに頻出する部分グラフを抽出する。グラフ解析部39は、グラフ形状が類似し、かつ、対応する頂点のステム候補が類似する部分グラフを抽出する。このような部分グラフが、RNA2次構造モチーフを表す頻出ステムパターンとして抽出される。

0045

最小支持度入力部41および最大一般化コスト入力部43は、頻出ステムパターン抽出処理における抽出条件を決定するパラメータである最小支持度および最大一般化コストを入力する。これらパラメータは、グラフ解析部39の処理に用いられる。

0046

出力部45は、グラフ解析部39によって抽出された頻出ステムパターンの情報を出力する。また、出力部45は、頻出ステムパターンに対応する2次構造データを出力する。2次構造データは、2次構造データ生成部47により生成される。

0047

図6の構成において、配列データ入力部23、最小支持度入力部41および最大一般化コスト入力部43は、図4の入力装置13、記録媒体装着部17または通信部19によって実現される。また、出力部45は、図4の出力装置15、記録媒体装着部17または通信部19によって実現される。また、ステム候補抽出部27、グラフ生成部31、分類データ生成部35およびグラフ解析部39は、図4のプログラム記憶部5に記憶されたステム候補抽出プログラム、グラフ生成プログラム、分類データ生成プログラムおよびグラフ解析プログラムをプログラム実行部3が実行することによって実現される。2次構造データ生成部47も、プログラム記憶部5のプログラムをプログラム実行部3が実行することにより実現される。また、配列データ記憶部25、ステム候補記憶部29、グラフ記憶部33および分類データ記憶部37は、図4の処理データ記憶部7および外部記憶装置11によって実現される。

0048

以下、RNA配列情報処理装置の各部機能についてより詳細に説明する。

0049

「ステム候補の抽出」
図6のステム候補抽出部27は、各々のRNA配列データから、RNA2次構造の複数のステム候補を抽出する処理を行う。本実施の形態では、以下に説明するように、ステム候補抽出部27が、分子構造のエネルギに基づいてRNA配列上の任意の2つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域をステム候補として抽出する。

0050

図7は、RNA配列データから生成された塩基対確率行列を、RNA配列の2次構造の例と共に示している。塩基対確率行列においては、同一のRNA配列が横方向と縦方向に配置される。行列の要素(i,j)は、i番目の塩基とj番目の塩基が塩基対を形成する確率を表す。この確率は、エネルギが最小になる構造を求める計算によって得られる。図7では、確率の大きさが、点の大きさで表されている。一つのRNA配列が両方向に配置されているので、図示のような半分の領域(三角形領域)にて、全塩基対の確率が表される。

0051

図7の塩基対確率行列において、ステムは、確率が大きい複数の要素が、図示のように右上がりの45度方向に並んだ領域である。

0052

ステム候補抽出部27は、各々のRNA配列データから、図7に示されるような塩基対確率行列を生成する。本実施の形態では、McCaskillのアルゴリズムが好適に用いられる。そして、ステム候補抽出部27は、塩基対確率行列から、所定値p以上の確率を持つ要素が所定個数n以上連続する領域を抽出する。この領域が、ステム候補として特定され、ステム候補記憶部29に記憶される。

0053

さらに、ステム候補抽出部27は、ステム候補における全要素の確率の平均を求める。平均値は0から1の間の値になる。この平均値は、ステム候補のスコアとしてステム候補記憶部29に記憶される。このスコアは、後述のステム候補間の類似性の判断に用いられる。

0054

以上にステム候補抽出処理の好適な例を説明した。ステム候補抽出処理は上記に限定されない。より簡単な例としては、既知のステム配列が、RNA配列から探索され、ステム候補として特定されてよい。ステムを構成する2つの部分配列が探索される。既知のステムの配列は、過去の研究で得られた既知の2次構造から求められてよい。

0055

「ステムグラフの生成」
図6のグラフ生成部31は、上述したように、各RNA配列データから抽出されたステム候補の情報を基に、各RNA配列に対応するステムグラフを生成する処理を行う。

0056

図8および図9は、ステムグラフの例を示している。図8ではステムグラフが確率塩基対行列の上に描かれており、図9ではステムグラフが単独で描かれている。図示のように、ステムグラフでは、各ステム候補が頂点である。図の例では、9個のステム候補が頂点になっている。そして、ステム候補間が辺で結ばれる。

0057

本実施の形態では、ステムグラフがラベル付き有向グラフであり、グラフの頂点および辺にはラベルが付与される。各頂点および各辺には、それらを識別するためのユニークなラベルが付与される。さらに、各辺には、下記の2つの情報が付与される。

0058

(1)向き:ステム候補間の位置関係を表す向きである。図8では、辺の向きが矢印で示されている。辺の向きは、配列上で5’側(一般の直線配置で左側)のステム候補から3’側(一般の直線配置で右側)のステム候補へ向くように設定される。ここで、ステム候補位置は、各ステム候補の5’側のステムパーツの位置で特定される。

0059

図8(および図7)では、横方向の配置にて、5’側が左であり、3’側が右である。そして、縦方向の配置では、5’側が上であり、3’側が下である。この場合、辺の向きは、縦の配置の5’側のステム候補から3’側のステム候補へ向くように付けられている。要するに、辺の矢印は、図8の上側のステム候補から下側のステム候補を向いている。

0060

(2)接続関係:これは、ステム候補間の接続関係が3つのタイプのいずれに属するかの情報である。図10に示されるように、3つのタイプとは、並列(Juxtaposed)、埋込み(Embedded)、重複(Overlapped)である。これらは、矛盾のない関係(consistent relation)である。図9のグラフは、並列(“J”)と埋込み(“E”)の辺を含んでいる。

0061

なお、グラフ生成部31は、上記3つのタイプいずれにも該当しないステム候補対を辺での接続対象から除外する。これにより、矛盾のある関係(inconsistent relation)が除外される。例えば、ステム候補#2、#8は、上記の接続タイプに該当せず、したがって、辺で結ばれていない。

0062

上記の例において、#2、#8のステム候補では、ステムの片側パーツが共通している。したがって、これらのステム候補の両方共が本当のステムである可能性は無い。このようなステム候補対が辺で結ばれないので、妥当なグラフが形成される。

0063

以上、グラフ生成部31により生成されるステムグラフ(ラベル付き有向グラフ)について説明した。グラフ生成部31は、ステム候補抽出部27により抽出されたステム候補を頂点に設定し、頂点間の辺を設定し、頂点および辺にラベルを付与する処理を行い、これにより上記のグラフが生成される。

0064

グラフ生成部31は、各々のRNA配列に対して上記のようなステムグラフを生成する。したがって、グラフ生成部31は、入力されたRNA配列の数と同じ枚数のグラフを生成する。これらグラフがグラフ記憶部33に記憶される。

0065

「分類データの生成」
図6の分類データ生成部35は、上述したように、ステム候補群を分類する分類データを生成する処理を行う。本実施の形態では、図11に示されるように、分類データが、階層型でツリー型のタクソノミデータである。以下、分類データの生成処理について、より詳細に説明する。

0066

上述のステムグラフ生成処理は、一本のRNA配列から一つのステムグラフを生成する。一方、この分類処理は、複数のRNA配列から抽出された全部のステム候補を分類して一つの分類データを生成する。

0067

ステム候補の分類は、ステム候補間の類似性に基づいて行われる。ステム候補の全組合わせの類似性が求められ、類似性を使って分類が行われる。類似性のパラメータは、典型的には、ステム候補同士の配列の相同性である。本実施の形態では、ステム候補対の類似性が、上記の配列相同性を含む4つの類似性によって定義される。(1)ステム候補同士の配列相同性、(2)各ステム候補のスコア、(3)ループの距離の類似性、(4)配列内での位置の類似性。

0068

上記において、(2)のスコアは、ステム候補抽出時に算出された確率である。より詳細には、スコアは、ステム候補の塩基対形成確率の平均である。本実施の形態は、2つのステム候補のスコアの和を利用している。本実施の形態は、スコアの和が大きいほど2つのステム候補の類似度を大きいと考え、スコアの和が小さいほど2つのステム候補の類似度が小さい(非類似度が大きい)と考える。ここで、本発明は、スコアの和が大きいほど、2つのステム候補の両方共が実際のステムである可能性が高いことに着目している。このことを考慮し、本発明は、両方のステム候補が実際のステムである可能性が高いほど類似性が高いと決めている。(3)のループの距離は、ステムを構成する2つのパーツ間の距離(塩基数)である。(4)の位置は、各ステム候補が属するRNA配列内での位置である。位置は、配列端からの距離(塩基数)で表されてよい。

0069

4つの要素的な類似性パラメータを計算するために、RNA配列のデータから、各ステム候補が有する配列、スコア、ループ距離、配列内位置の4つのデータが求められる(スコアは既に説明したように塩基対確率から算出されている)。各データから一組のステム候補の類似性が計算され、したがって、4つのデータから4つの類似性パラメータが計算され、それらが合成されて、一組のステム候補の総合的な類似性パラメータが計算される。このような類似性パラメータが、任意の組のステム候補に対して計算される。類似性パラメータの算出処理は、後述にてさらに詳しく説明されるが、本実施の形態の実現例では、2つのステム候補の違いが大きくなるほど値が大きくなるような類似性パラメータが使われてよい。つまり、類似性パラメータが、非類似度で実現される。

0070

図11は、上記のような類似性に基づいて生成された分類データを示している。分類データ生成部35は、頂点間の類似性に基づいたクラスタリングを行い、これにより、図示のようなツリー型のタクソノミデータを生成する。図11において、左の図は、ステム候補の階層的クラスタリングによって生成される系統樹(dendrogram)である。クラスタリングのためのステム候補間の類似性(similarity)は、既述の通り、(1)配列相同性(sequence similarity)、(2)候補のスコア(score of candidate)、(3)ループ距離(loop distance)、(4)配列内位置(position in sequence)のミックス(mixture)によって定義される。右側の図は、系統樹(dendrogram)から構築されたステム候補のラベルのタクソノミである。

0071

図11のタクソノミデータでは、最下層の頂点1〜7は、個々のステム候補と対応する。上位層の頂点(分類、ラベル)は、下位層で類似する複数の頂点を代表する。例えば、最下層の3つの頂点1、2、3が類似するので、第2層では一つの頂点8に分類される。分類データ生成部35は、このような分類データを生成して、分類データ記憶部37に記憶する。

0072

上記より明らかなように、分類データでは、下位層よりも上位層にて類似範囲が広い。すなわち、下位層よりも上位層にて、一般化の程度が大きい。そこで、本実施の形態では、一般化の程度を表現するために、図11に示されるように、上位層へ行くほど値が大きくなるように一般化コストが定義される。i層の一般化コストは、1−n(i)/Nで表される。ここで、Nは、最下層の頂点数(ステム候補の総数)である。n(i)は、階層iに属する頂点数である。一般化コストは下記のグラフ解析処理にて用いられることになる。

0073

「グラフ解析処理」
図6のグラフ解析部39は、上述したように、グラフ生成部31によって生成された複数のステムグラフに頻出する部分グラフを抽出する処理を行う。ここでは、類似する部分グラフが抽出される。類似する部分グラフとは、グラフ形状が類似し、かつ、対応する頂点のステム候補が類似するグラフである。部分グラフはステム候補のパターンに相当するので、以下、必要に応じて、部分グラフをステムパターンと呼び、抽出される頻出部分グラフを頻出ステムパターンという。

0074

より詳細には、グラフ解析部39は、ステムグラフでの出現の頻度が所定しきい以上のステムパターン(部分グラフ)を抽出する処理を行う。この頻度は、典型的には、後述するように、「ステムグラフの総数」に対する、「特定の類似するステムパターンを含むステムグラフの数」の比、で表される。

0075

頻出ステムパターンの抽出では、上記のように類似性が考慮される。したがって、抽出される一つ頻出ステムパターンは、実際には、複数のステムパターンの集合になってよい。

0076

図12は、グラフ解析の原理を示している。図12は、2つのステムグラフを示している。互いに類似するステムパターンが2つのステムグラフから抽出されている。図12の例では、ステムパターンは、3つの頂点とそれらを結ぶ3つの辺で構成されている。

0077

ステムパターン(部分グラフ)の類似は、グラフ形状の類似性と、グラフ内の頂点の類似性によって決まる。本実施の形態では、以下の3条件が満たされるとき、2つの部分グラフのグラフ形状が類似する。
(1)頂点の数が同じである。
(2)対応する辺の向きが同じである。
(3)対応する辺の接続関係が同じである。

0078

なお、本実施の形態では、後述するように完全(Clique)グラフが抽出される。したがって、類似する部分グラフにおいては、頂点の数が同じであり、それらの任意の2つの頂点間が辺で結ばれ、かつ、各辺のラベルが(2)(3)の条件を満たす。

0079

次に、図13を参照して、頂点間の類似について説明する。頂点間の類似は、分類データを用いて判断することができる。分類データにおいて同じグループに属する頂点を類似と判断する。

0080

図13は、2つのステムパターンの例を示している。図において、対応する2組の頂点は同じであるが、対応する1組の頂点が異なっている。しかし、これら頂点が、図11のタクソノミにおいて、1つ上の階層では同一分類に属するとする。この場合、対応頂点が類似し、そして、2つのステムパターンが類似する。

0081

このようにして、下位層での比較では対応頂点が異なる分類に属しても、上位層の比較で対応頂点が同じ分類に属していれば、対応頂点が類似する。グラフ解析処理では、順次階層を上に変更して、頂点間の類似が判断される。

0082

しかし、階層を高くしすぎると、類似範囲が広くなり過ぎる。例えば、最上層では、すべての頂点が類似し、妥当な比較が困難になる。そこで、本実施の形態では、類似判断における階層の高さが制限される。この制限のために、前述の一般化コストが用いられる。

0083

一般化コストは、図11に示したように、上位層へ行くほど大きくなる。前述の説明を繰り返すと、i層の一般化コストは、1−n(i)/Nで表され、Nは、最下層の頂点数(ステム候補の総数)であり、n(i)は、階層iに属する頂点数である。

0084

図14は、ステムパターンの一般化コストを示している。ステムパターンの一般化コストは、各頂点の一般化コストの平均である。グラフ解析処理では、ステムパターンの最大一般化コストが指定され、一般化コストが最大一般化コスト以下になるように頻出ステムパターンが抽出される。例えば、図13の一般化を行うと、一般化コストが最大値オーバーしたとする。この場合、図13の2つのステムパターンは類似しない。

0085

上述の原理に基づきグラフ解析の問題を定式化すると、以下のようになる。
(1)ラベル付き有向グラフの集合、(2)ラベルの一般化コスト付きタクソノミ、(3)最小支持度(minsup)、(4)最大一般化コスト(maxcost)が与えられた際に、以下を満たすステムパターンをすべて抽出する。
A)支持度が最小支持度以上
B)完全グラフ(Cique)
C)一般化コストが最大一般化コスト以下
D)クローズドパターン(Closed Pattern)

0086

支持度は、図15に示される通り、頻出の程度を表す。図において、一つのステムパターンが、3つのステムグラフのうちの2つに存在する。この場合、該当パターンの支持度は、2/3である。完全グラフとは、各頂点がすべての頂点と辺で結ばれたグラフである。ステムパターンがRNA配列の一部分であれば、必ずステムパターンが完全グラフになる。一般化コストは、既に説明した通りである。クローズドパターンは、「自分を真に含むパターンであって、自分と同じ支持度を持つようなパターンが存在しない」パターンである。

0087

次に、図16を参照すると、上述してきたグラフ解析処理は、パターン探索アルゴリズムにより好適に実現される。より詳細には、グラフ解析機能は、図16DFS code treeの探索アルゴリズムにより実現される。この探索アルゴリズムは、少しずつパターンを変えながら、ツリーを深さ方向に探索し、各種の候補パターン数え上げる。

0088

本実施の形態では、パターン探索アルゴリズムが、上述のグラフ解析処理を実行する。すなわち、パターンの形状が変更される。また、タクソノミに基づいて一般化の程度が変更される。そして、各種のパターンが複数のステムグラフから数えられる。そして、上述の条件を満たす頻出ステムパターンが求められる。

0089

パターン探索のアルゴリズムは、効率よく完全に多様なパターンが数えられるように構成されている。さらに、本実施の形態は、上述のパターン抽出の条件も考慮して下記の制限された処理を行い、さらなる効率的を実現する。(1)支持度の逆単調性による枝狩り、(2)Clique制約によりDFS code treeの子要素を限定、(3)最大一般化コストの制約を用いた枝狩り、(4)過度に一般化されたパターンを除くための枝狩り。枝狩り(pruning)とは、ツリー上の部分木探索対象から除外することをいう。これらの処理については、後にさらに詳細に説明する。

0090

以上に頻出ステムパターンを抽出するグラフ解析処理を説明した。グラフ解析部39は、上述の処理を行うことによって頻出ステムパターンを抽出する。さらに、2次構造生データ成部47は、抽出された頻出ステムパターンに対応する2次構造データを生成する。これら頻出ステムパターンと対応する2次構造データが出力部45から出力される。

0091

ここで、グラフ解析部39は、上述の条件に該当する全部の頻出ステムパターンを抽出する。したがって、グラフ解析部39は、通常は複数の頻出ステムパターンを抽出する。さらに、類似性が考慮されているので、一つの頻出ステムパターンは、複数のステムパターンに対応することもある。2次構造データは、各々のステムパターン(部分グラフ)から作られてよい。これらデータが、出力されてよい。

0092

以上に、本実施の形態のRNA配列情報処理装置、方法およびプログラムについて詳細に説明した。以下、本発明の各種態様の利点をまとめて述べる。本発明は、複数のRNA配列データから複数のステムグラフをそれぞれ生成し、それら複数のステムグラフから頻出ステムパターンを抽出する。頻出ステムパターンは、RNA2次構造モチーフを表している。したがって、本発明は、RNA配列群から2次構造モチーフを抽出することができる。

0093

本発明の情報処理が、機能性RNAのファミリーが特定されていないRNA配列群に適用されたとする。この場合、頻出ステムパターンが抽出されると同時に、頻出ステムパターンを含むRNA配列(ステムグラフ)も分かる。すなわち、2次構造モチーフが抽出されると同時に、2次構造モチーフを含むファミリーを同定することができる。また、本発明は、既に同定されている機能ファミリーの配列群に適用されてもよく、この場合にも2次構造モチーフが好適に抽出される。

0094

また、上述にて説明したように、グラフ生成部は、RNA配列上での各ステム候補対の位置関係に応じた向きを、各ステム候補対を結ぶ辺のラベルに付与してよい。そして、グラフ解析部は、複数のステムグラフから、対応する辺の向きが同じ部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0095

また、グラフ生成部は、各ステム候補対の接続関係が並列、埋込み、重複のいずれかに属するかの情報を、各ステム候補対を結ぶ辺のラベルに付与してよい。グラフ解析部は、複数のステムグラフから、対応する辺の接続関係が同じ部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0096

また、グラフ生成部は、並列、埋込みおよび重複のいずれにも該当しないステム候補対を辺での接続対象から除外してよい。これにより、不適当な部分グラフの抽出を回避して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0097

また、グラフ生成部は、各頂点が部分グラフ内のすべての他の頂点と辺で結ばれる完全部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0098

また、分類データ生成部は、複数のステムグラフに含まれる複数のステム候補を類似性に基づいて分類する分類データを生成してよい。グラフ解析部は、複数のステムグラフから、対応する頂点のステム候補が同じ分類に属する部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出できる。

0099

また、分類データ生成部は、分類データとして、複数のステム候補を、類似範囲の広さが下位層から上位層へ向かって増大するように階層的にクラスタリングを行ったタクソノミデータを生成してよい。グラフ解析部は、タクソノミデータに基づき、対応する頂点のステム候補が下位層では異なる分類に属しても上位層では同一分類に属する部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0100

また、最大一般化コスト入力部が、タクソノミデータにて階層に応じて増大する一般化コストの最大許容値である最大一般化コストを入力してよい。グラフ解析部は、最大一般化コスト以下の一般化コストを有する部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。

0101

また、分類データ生成部は、ステム候補対の類似性を表す類似性パラメータを、ステム候補対の配列相同性、ステム候補により形成されるループの距離の類似性、および、RNA配列内でのステム候補の位置の類似性の少なくとも一つに応じて求めてよい。また、分類データ生成部は、二次構造エネルギに基づいたステム候補の塩基対形成確率に応じて類似性パラメータを求めてよく、このとき、2つのステム候補の塩基対形成確率の和が評価されてよく、そして、和の値が大きいほど類似度が高いと判断されてよい。上記の例では、これら全部が加味されている。これにより、ステム候補である頂点間の類似性を適切に判断して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。類似性判断の基礎になるパラメータは、ステムグラフの頂点のラベルに付与されてよい。

0102

また、最小支持度入力部が、複数のステムグラフにおける部分グラフの支持度の最小許容値である最小支持度を入力してよい。グラフ解析部は、最小支持度以上の支持度を有する部分グラフを抽出してよい。支持度は頻度(頻出の程度)を表す。最小支持度以上の支持度を有する部分グラフを抽出することにより、RNA配列群に頻出するステムパターンを適切に抽出できる。

0103

また、ステム候補抽出部は、分子構造のエネルギに基づいてRNA配列上の任意の2つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域をステム候補として抽出してよい。これにより、ステム候補を適切に抽出することができる。

0104

また、上述の実施の形態では、頂点間のタクソノミが考慮されて、類似部分グラフ(頻出ステムパターン)が抽出された。本発明のさらなる応用例では、辺のタクソノミが考慮されて、類似部分グラフ(頻出ステムパターン)が抽出されてよい。この場合、辺を特徴づけるパラメータを用いて、辺の類似性を基に、辺のタクソノミが生成される。辺のタクソノミが、頂点のタクソノミと同様に処理されて、辺が類似する部分グラフが抽出される。

0105

以下、上述の発明に関する研究について詳細に説明する。以下では、上述したラベル付き有向グラフ、タクソノミ、グラフ解析なども詳細に説明される。なお、参考文献は、(文献+番号)と表記し、文献のリストを最後に記載する。

0106

「1.はじめに」
この記述の構成は、以下の通りである。セクション2は、グラフ理論の基本的な用語を定義した後に、RNAのグラフ表現の方法および今回解決すべき問題のグラフマイニングによる定式化、さらにはそれを効率よく解く為の理論およびアルゴリズムについて詳細に説明する。セクション3は、実装方法について述べる。

0107

「2.手法」
「2.1グラフ理論・グラフマイニングからの準備」
文章では、特に断らない限り、グラフとは多重辺や自己ループ辺を許さないラベル付き有向グラフG = ( V, E, Lv,LE, lb ) を意味することとする。ここで、V = V ( G ) = [ v1,・・・,vk ] は頂点の集合を表す。E = E ( G ) = [ ( vi, vj )|vi, vj∈V ] は辺の集合を表す。( vi, vj ) は、頂点vi から頂点vj への辺を表す。LVは頂点のラベルの集合を表す。LEは辺のラベルの集合を表す。lb:V∪E→LV∪LE は頂点または辺からそのラベルへの写像を表す。さらに、グラフGのトポロジー(topology)GTとは、GT = ( V, E ) で定義されるラベルを含まないグラフである。

0108

「定義2.1(部分グラフ)」
グラフGが与えられているものとする。グラフGsがGの部分グラフ(subgraph)である(Gs⊆G と書く)とは、写像φ:V ( Gs )→V ( G ) が存在して
(1)任意のv∈V ( Gs ) に対してlb ( v ) = lb (φ( v ) )
(2)任意の( vi, vj )∈E ( Gs ) に対してlb ( vi, vj ) = lb (φ( vi ),φ( vj ) )
を満たすことである。
Srikantら(文献1)は、アイテムセットにおける個々のアイテムの関係をTxonomyとして表現した。さらに、Inokuchi(文献2)は、グラフのラベルにTaxonomyを考えることを提案している。ここではこららを発展させ、ラベル間の関係と各ラベルの一般化コストを考慮した「一般化コスト付きTaxonomy」を定義する。

0109

「定義2.2(一般化コスト付きTaxonomy)」
ラベルの集合LSが与えられているものとする。このとき、一般化コスト付きTaxonomy(Taxonomy with generalization cost) Tとは、頂点がLSのDAG(directed acyclic graph)で、その各頂点v∈LS に対して一般化コストc ( v )∈R+ が定義されているものである。
注意2.1) 関係A→Bは、B is a A(ラベルAの方がラベルBよりも一般化されている、逆に言うとラベルBの方がラベルAよりも特殊化されている)を意味する。TaxonomyをforestではなくDAGでモデル化したのは、multiple taxonomiesを表現することを可能にするためである(文献1)。また、c ( A )、c ( B )は、それぞれ、ラベルA、Bの一般化に対するコストを表すが、通常の場合、上位概念ほど一般化のコストが大きいと考えられるので、c ( B )<c ( A ) である。
今後は簡単のため、一般化コスト付きTaxonomyを単にTaxonomyと呼ぶことにする。Taxonomyの頂点xに対して、xまたはxの祖先の集合(xから有向辺を逆にたどっていって到達できる全ての頂点の集合)をτT ( x ) と表すことにする。グラフとTaxonomyが与えられた際の部分グラフを以下のように定義する。

0110

「定義2.3(Taxonomyが与えられた下での部分グラフ(文献2))」
Taxonomy TとグラフG、Gsが与えられているものとする。Gsが、GのTaxonomy Tが与えられた下での部分グラフ(subgraph under Taxonomy T)であるとき、



とかく。これは、写像φ:V ( Gs )→V ( G ) が存在して、
(1)任意のv∈V ( Gs ) に対してlb ( v )∈τT ( lb (φ( v ) ) )
(2)任意の( vi, vj )∈E ( Gs )に対してlb ( vi, vj )∈τT ( lb (φ( vi ),φ( vj ) ) )
を満たすことである。今後は、簡単のため、Taxonomy Tが明らかな場合には、添え字Tは省略する。
(注意2.2) 定義より明らかに



である(逆は成立しない)。つまり、Taxonomyが与えられた下での部分グラフの定義は、通常の部分グラフの定義を弱めたものとなっている。

0111

「定義2.4(Clique)」
グラフがクリーク(Clique)であるとは、任意の頂点間に辺が存在することである。

0112

「2.2グラフとTaxonomyを用いたRNA配列集合のモデル化」
本節では、RNA配列の集合全体をラベル付有向グラフとTaxonomyを用いてモデル化を行う方法について記述する。
近年、ステムやループなどのRNA2次構造の構成要素を一つの単位として積極的に利用したRNA解析手法が一定の成功を納めている。例えば、Scarna(文献3)は固定長のステムのアラインメントを良く考えられたダイナミックプログラミングにより定式化し、2本のRNA配列のアラインメントおよびその共通2次構造の予測を高速で行う。RNAscf(文献4)は、複数配列からステム候補のアラインメントを繰り返し行うことにより、共通の2次構造の予測を行う。また、Carnac(文献5)は、2本あるいは3本以上のRNA配列群から、可能性のあるステム候補を抽出し、cofoldingと呼ばれる手法を用いて、各RNA配列の2次構造を予測する。comRNA(文献6)は、グラフ理論におけるClique探索手法を利用して、整列していないRNA配列群からその共通のモチーフを発見する手法を提案している。これらのステムベースの手法は、ヒューリスティックな部分を多く含んでいるが、精度と計算量のバランスが取れた実用的な手法が多い。本手法でも、これらの手法と同様にステムの候補を積極的に利用したモデル化を行う。
また、単一のRNA配列は、2次構造を一つに決めれば木構造やRAG(文献7)を用いて表現することが可能であるが、ここでは各RNA配列の2次構造自体をモデル化するのではなく、RNA配列から得られる可能性のあるステムの候補をすべて用いてRNAのモデル化を行う。その手順は以下の通りである。
(1)各RNA配列の塩基対確率行列からステム候補を抽出しグラフの頂点とする。
(2)ステム候補の類似度に基づいた階層型クラスタリングの樹形図から頂点ラベルに対するTaxonomyを構築する。
(3)consistentなステム候補間を有向辺で結びその関係(Juxtaposed, Embedded, Overlapped)に応じて辺にラベルを付与する。
以下に各ステップについてもう少し詳細に説明を行う。

0113

「2.2.1グラフの頂点」
McCaskillのアルゴリズム(文献8)を用いてRNA配列から塩基対確率行列(base pairing probability matrix)を計算する。ここで、McCaskillのアルゴリズムにより計算される塩基対確率行列の( i, j ) 要素は、i番目の塩基とj番目の塩基が塩基対を形成する確率を表す。計算された塩基対確率行列から、塩基対を形成する確率がp以上で、n個以上の連続する塩基対集合の極大集合をステム候補(Stem candidate)として抽出する(文献3)。なお、現在の実装では、塩基対単位でM個のギャップ許容している。ただし、バルジが入るようなステム候補は考えることが出来ない(ステム候補の数が増えるため許容していない)。
さらにステム候補には、そのステム候補を形成する塩基対の確率の平均をスコアとして付与する(このスコアは0以上1以下の実数である)。本手法では、このステム候補をグラフの頂点とする。

0114

「2.2.2頂点ラベルのTaxonomyの構築」
頂点ラベルのTaxonomyを構築するために、セクション2.2.1の2つの頂点(ステム候補)間の非類似度を以下のように定める。ステム候補Sに対して、p ( S ) で5’側ステムの開始位置、d ( S ) でループの距離、r ( S ) で3’側ステムの開始位置、s ( S ) で塩基対確率行列から計算されるステムのスコアと置く。このときステム候補S1、S2に対して、ステム候補の相同性に関する非類似度d1 ( S1, S2 )、ステム候補のスコアから計算される非類似度d2 ( S1, S2 )、ステム候補のループの距離に関する非類似度d3 ( S1, S2 )、ステム候補の配列内での位置に関連する非類似度d4 ( S1, S2 )を、



とするときに、ステムS1とS2の非類似度はこれらを全て合わせたd ( S1, S2 ) =Σi=1,2,3,4 wi di ( S1, S2 ) で定義する。ここで、SW ( S1, S2 ) は、RIBOSUM置換行列(文献9)を用いたステムS1とステムS2のSmith Watermanアラインメント(文献10)のスコアである。また、wi はΣ i = 1, 2, 3, 4 wi = 1, wi≧0 を満たす重みパラメタである。
セクション2.2.1の方法で抽出されたステム候補全てに対して上述の非類似度に基づき階層型クラスタリングを行う。この際得られる樹形図を用いてTaxonomyを構築する。すなわち、クラス間の距離の列をd = [ dk ]Nk=1 ( d1<d2<・・・<dN ) とする際に、距離がdk 以下のクラスタに対して同一のラベルを付与することによりTaxonomyを構築する。従って、今の場合Taxonomyは階層構造になっている。ここで、Taxonomyの第n階層に属するラベルの一般化コストを、「1−(第n階層のラベル数)/(頂点数)」で与える。

0115

「2.2.3グラフの辺」
2つのステム候補間の関係は次のように分類できる。
「性質2.1(文献11、文献3)」
セクション2.2.1で抽出した2つのステム候補S1、S2の位置関係は、ステム候補の配列上での位置をS1 = ( [ ls1, le1 ] , [ rs1, re1 ] ) 、S2 = ( [ ls2, le2 ] , [ rs2, re2 ] ) (lsk は5’側のステムの開始位置、lek は5’側のステムの終了位置、rsk は3’側のステムの開始位置、rek は3’側のステムの終了位置)とするときに、以下のいずれかが成立する。



(1)、(2)、(3)のいずれかの関係である場合に、2つのステム候補S1、S2の関係はconsistentであると言う。
本研究では、2つのステム候補S1 = ( [ ls1, le1 ] , [ rs1, re1 ] ) , S2 = ( [ ls2, le2 ] , [ rs2, re2 ] ) がls1<ls2 かつ(1)、(2)、(3)のいずれかの関係であるならば、S1からS2の向きに有向辺を付与し、辺にはその関係に応じて異なるラベルを付与することとする。

0116

「2.2.4モデル化の特徴」
このようにモデル化を行った場合、明らかに次の著しい性質が成立する。この性質は、後にアルゴリズムを構築する際に非常に役に立つ。
「性質2.2」
2次構造として成立可能なステム候補の集合は、上述の方法でRNAをグラフ化した際に、Cliqueな部分グラフでなければならない。
例1:図7は、tRNAのステムグラフである。図7では、例えば、頂点の組み合わせ(1, 2, 8, 9)、(1, 2, 4, 5, 9)などがRNAの2次構造として正当なステム候補のセットである。これに対して、ステム候補の集合(1, 3, 5)に対応する2次構造は存在しない。
我々のモデル化の手法では、RNA配列集合の個々の配列に対してその可能性のあるステム候補を全て考慮したラベル付有向グラフを構築する点および頂点のラベルにはTaxonomyを考慮する点の2点を新しく提案している。本セクションの最初にも述べたとおり、RNAの2次構造を木構造やグラフでモデル化する方法はすでに提案されているが、本手法のようなモデル化の方法は今までには考えられてこなかった。従って、上記のモデル化手法は本論文の貢献のひとつであるといえる。

0117

「2.3グラフマイニングとしての定式化」
我々が現在解決しようとしていRNAの問題は以下のように述べられる。
「問題1」RNA配列集合に頻出するステムのパターンを全て抽出する。同時に各ステムパターンに対応するRNA配列のステムの集合(RNA配列の2次構造)を特定する。
本セクションでは、上記の問題をグラフマイニングとして定式化を行う。まず、次の定義はグラフマイニング分野では非常に基本的なものである。

0118

「定義2.5(支持度(文献2))」
グラフの集合GS = [ G1,・・・, GN ] とTaxonomy TとグラフPに対して、



をグラフPの支持度(support)と呼ぶ。支持度が0より大きいグラフをパターン(pattern)と呼ぶ。また、支持度が与えられたminsupより大きいパターンを頻出パターン(Frequent pattern)と呼ぶ。
前セクションの結果およびこの定義を用いて問題1を言い換えると次のようになる。

0119

「問題2」グラフ集合GSとTaxonomy Tおよび支持度minsupが与えられている際に、Cliqueなパターンで支持度がminsup以上のものをすべて導出する。同時に、導出されたパターンに対応する各グラフの部分グラフを特定する。
一般に、与えられたグラフ集合から頻出パターン(Cliqueなパターンとは限らない)を完全に抽出する問題はグラフマイニングの問題として近年盛んに研究がなされている(FSSM(文献12)、FSG(文献13)、AGM(文献14、15)、AcGM(文献16)、gSpan(文献17))。ラベルにTaxonomyを用いた場合の一般的なグラフマイニングは(文献2)で提案された。今回は、ベースとなる一般のグラフマイニングアルゴリズムにはgSpanアルゴリズムを用いて、頂点ラベルにTaxonomyを考慮できるように変更を行った。また、後で述べる通り、抽出するパターンがCliqueなパターンであること(性質)を利用して探索の効率化を行っている。また、問題1を完全に解くことも可能であるが、本研究ではさらになる探索の効率化を行うために抽出されるパターンにいくつかの制約を課すことにする。
次に定義される過度に一般化されたパターンは、ラベルにTaxonomyを考慮した場合に出現するパターンであるがパターンとしての有用性は低い。

0120

「定義2.6(一般化パターン、過度に一般化されたパターン(文献2))」
パターンP1とP2のトポロジーが同型であるとする。



であるとき、P1はP2の一般化パターン(generalized pattern)と呼ぶ。また、P2が存在して、



を満たす場合、P1は過度に一般化されたパターン(over-generalized pattern)と呼ぶ。
以下は、Yanら(文献18)により提案されたclosed patternの定義をTaxonomyを考慮した場合に拡張したものである。closed patternでないパターンもパターンとしての有用性は低い。

0121

「定義2.7(closed pattern(文献18))」
グラフの集合GS = [ G1, G2,・・・, Gn ] とTxonomy Tが与えられているものとする。このとき、パターンPがclosed patternであるとは、



を満たすパターンP' が存在しないことを言う。
(注意2.3) Yanら(文献18)は、通常の部分グラフ(定義2.1)の意味でclosed patternを定義したが、ここではTaxonomyを用いた部分グラフ(定義2.3)の意味でclosed patternを定義している。定義より、この意味でClosedなパターンは、定義2.6で定義される過度に一般化された(over-generalized)パターンではない。
Taxonomyを考えることにより、柔軟なパターンの抽出が可能になる一方で、抽出されるパターンが増加することが懸念される。しかしながら、Taxonomyの上位のラベルばかりで構成されるパターンは、たとえ頻出していたとしてもあまり重要でない可能性が高い。このようなパターンがTaxonomyの上位のラベルばかりで構成されているかどうかを判定するために、パターンの一般化コストと呼ばれる概念を新たに定義する。

0122

「定義2.8(パターンの一般化コスト)」
グラフGとTaxonomy Tが与えられているものとする。このときパターンPの一般化コスト(generalization cost):cost ( P ) を、



と定義する。言い換えれば、パターンの一般化コストは、パターンを構成するラベルのコストの平均である。
以上の定義をもとに、最終的に我々が解くべきグラフマイニングの問題は以下となる。

0123

「問題3」グラフの集合GS = [ G1, G2,・・・, Gn ] 、Taxonomy T、最小支持度minsup、最大一般化コストmaxcostが与えられた際に、以下の条件を満たすパターンを完全に抽出する。
(1)支持度がminsup以上(定義2.5を参照)
(2)Clique(定義2.4を参照)
(3)Closed patterns(定義2.7を参照)
(4)一般化コストがmaxcost以下(定義2.8を参照)
さらに、抽出されたパターンに対応する各グラフの部分グラフを全て特定する。

0124

「2.4 理論」
本セクションでは、問題3を解くためのグラフマイニングアルゴリズムの理論的な部分について、出来る限りself-containedな形で記述を行う。以下の定義はグラフアルゴリズムの分野では基本的なものである。

0125

「定義2.9(DFS木、DFS添え字付け、前向きの辺、後ろ向きの辺(文献19))」
本定義においてグラフは連結グラフであるとする。
(1)深さ優先木(DFS木、DFS Tree):グラフを深さ優先探索した際に得られる木構造。
(2)DFS添え字付け(DFS Subscripting):グラフの頂点にDFS木で探索される順番に従って番号付けをしたもの。またグラフGとDFS木Tに対してDFS subscriptingをGTと書く。i番目の頂点をvi と表すとGT = [ vi ] と書ける。
(3)前向きの辺(Forward Edge)と後ろ向きの辺(Backward Edge):グラフGと深さ優先木Tが与えられた際に、Gの辺の中でTに含まれるものを前向きの辺(Forward Edge)、含まれないものを後ろ向きの辺(Backward edge)と呼ぶ。前向きの辺を( vi, vj ) ( i<j )、後ろ向きの辺を( vi, vj ) ( i>j ) と表す。
(注意2.4) 開始頂点の選び方などにより、同一のグラフに対して複数の深さ優先木が存在する(すなわち複数のDFS Subscriptingが存在する)。

0126

「定義2.10(文献20)」
連結グラフGとDFS木Tが与えられているものとする。前向きの辺の集合Ef,T = [ e|∀i, j, i<j, e = ( vi, vj )∈E ] と後ろ向きの辺の集合Eb, T = [ e|∀i, j, i>j, e = ( vi, vj )∈E ] に対して順序関係を以下の通り定義する(これらはすべて半順序関係であることは容易に示せる)。



(注意2.5) DFS木Tを固定する限り、(1)の(ii)の条件は必要ない。ただし、(1)の(ii)の条件を入れることにより、グラフやそのDFS木が異なっている場合でも辺の比較が可能になる。
(注意2.6) 今後は特に誤解が無い限り辺( vi, vj ) を省略して ( i, j ) と書く。
この順序関係について以下の結果が成立する。

0127

定理2.1(文献20)」
グラフGとDFS木Tを固定したときに、定義2.10の順序を合わせて定義されるEf, T∪Eb, T上の順序関係は、線形順序である。なお、集合( A,<) が線形順序集合であるとは、(i)∀a, b∈Aに対して、a<bかつb<cならばa<c、かつ、(ii)∀a, b∈Aに対して、a<bまたはb<aが成り立つことである(一般的には「a<a」と「a<bかつb<aならば、a = b」を条件に入れる場合も多いが、ここでは入れない)。
この定理により、グラフと深さ優先木を固定したときに、グラフに含まれる辺(前向きの辺または後ろ向きの辺のいずれか)には線形順序を与えることが出来る。さらに、頂点や辺のラベルを考慮して次のようにDFSコードと呼ばれる表現方法を定義する。

0128

「定義2.11(DFSコード(文献20))」
グラフGとDFS subscriptingGTに対して辺を ( i, j, li, lj, l( i, j ) , d( i, j ) ) と表す。ここでli, lj はそれぞれi番目、j番目の頂点のラベルを表す。l( i, j ) は辺( i, j )のラベルを表す。d( i, j ) は辺( i, j )の向き(iからjの向きであれば+1、jからiの向きを−1とする)を表す。このとき、Gの辺を定理2.1の順序に従って並べた順列[ ( i, j, li, lj, l( i, j ) , d( i, j ) ) ] をグラフGのDFSコード(DFS code)と呼び、code ( G, T )と書く。
(注意2.7) 上記のDFSコードの定義は原論文(文献20)とは以下の点で異なる。
(1)グラフが有向グラフのため辺の方向に関する項d( i, j ) が存在する。
(2)ラベルの順序は、(fromlabel, tolabel, edgelabel, direction)の順番である(原論文では(fromlabel, edgelabel, tolabel)の順番)。これは、後に一般化コストによる枝狩りを行う際に重要になってくる。
DFSコードから辺をひとつ拡張して新しいDFSコードを作成する場合、定義2.10の順序関係により任意に拡張を行うことは出来ず、以下の制限がある。

0129

命題2.1(DFSコードの拡張の制限(文献20))」
グラフGとDFS木Tが与えられているものとする。α = code ( G, T ) = ( a0, a1,・・・am ), ak = ( ik, jk ), ak+1 = ( ik+1, jk+1 ) とするとき以下が成立する。
(1)ak が前向きの辺かつak+1 が前向きの辺であるならば、
ik+1≦jk かつjk+1 = jk + 1
(2)ak が前向きの辺かつak+1 が後ろ向きの枝であるならば、
ik+1 = jk かつjk+1<ik
(3)ak が後ろ向きの辺かつak+1 が前向きの辺であるならば、
ik+1≦ik かつjk+1 = ik + 1
(4)ak が後ろ向きの辺かつak+1 が後ろ向きの枝であるならば、
ik+1 = ik かつjk<jk+1
(証明)DFS木の定義およびDFSコードの定義より明らかである。

0130

「定義2.12(最右拡張(文献20))」
パターンPとそのDFSコードに対して以下の拡張を最右拡張(Right-most extension)と呼ぶ。
(1)最右頂点から他の最右パスに含まれる頂点への辺の拡張(後ろ向きの拡張、backward extension)
(2)最右パスに含まれる頂点から、Pに含まれない新しい頂点への拡張(前向きの拡張、forward extension)
(注意2.8) 定義2.12を使って性質2.1を言い換えれば、パターン(DFSコード)の拡張は最右拡張に限るということである。
任意の2つのDFS code(異なるグラフでもよい)の間に以下のようにして順序を与えることが可能である。

0131

「定義2.13(DFS Lexicographic Order(文献20))」
連結グラフGに対してZ ( G ) = [ code ( G, T )|∀T:GのDFS木 ] と表す。さらにZ = ∪G:connected graph Z ( G ) と置く(すなわちZはすべての連結ラベル付きグラフのDFSコードの集合である)。グラフの頂点のラベル集合LVと辺のラベル集合LEには、それぞれ、



が定義されていると仮定すると、E×LV×LE×LV上には辞書順で



を入れることが可能である。このとき、DFS Lexicographic orderとは以下で定義されるZ上の線形順序である。α= code ( Gα, Tα ) = ( a0, a1,・・・,am )∈Z, β = code ( Gβ, Tβ ) = ( b0, b1,・・・,bn )∈Z に対して、α≦βとは、次の(1)または(2)が成立することである。



(注意2.9)

0132

「定義2.14(最小DFSコード)」
グラフGが与えられた際に、そのDFSコードの中で(上記順序に対して)最小のDFSコードを最小DFSコード(minimum DFS code)と呼びmin ( G )と書く(すなわちmin ( G ) = min [ code ( G, T )|TはGのDFS木 ] である)。
以下の定理により、min ( G ) はグラフGに対するcanonicalな表現となっている。従って、min ( G ) をcanonical DFS codeと呼ぶこともある。

0133

「定理2.2(文献20)」
グラフGとG' が同型である必要十分条件はmin ( G ) = min ( G' ) となることである。

0134

「定義2.15(DFSコードの親および子(文献20))」
DFSコードα= ( a0, a1,・・・, am ) が与えられているとする。このとき妥当なDFSコードβ= ( a0, a1,・・・, am, b ) をDFS code αの子(child)、αはDFSコードβの親(parents)と呼ぶ(「性質2.1」を満たさなければならない)。αの子の集合をchildren ( α )と書く。

0135

「定義2.16(DFS Code Tree(文献2))」
親要素と子要素の関係が定義2.15で与えられ、さらに同じ親の子要素の関係はDFS lexcographic orderで与えて得られるような、DFS codeを頂点とする木構造」を、「DFS code tree」と呼ぶ。
上で定義されているDFS code treeはDFSコードをノードとする順序木である。問題3はこの順序木の順序で探索を行っていくが、DFS code treeが全ての部分グラフを数え上げることが可能であることを保障するのが次の定理である。

0136

「定理2.3(DFS Code Tree Covering(文献20))」
DFS Code Treeは全てのグラフの最小DFSコードを含む。
DFS Code Tree TとDFS code αが与えられたときに、Tにおけるαの祖先の集合をans ( α )、子孫の集合をdes ( α )と表す。
次の定理は、最小でないDFSコードを根とする部分木を枝狩りしても、全ての部分グラフを数え上げることが可能であることを保障している。

0137

「定理2.4(DFS Code Pruning(文献20))」
グラフGとDFS code tree T内のグラフGのDFS codesをα0,α1,・・・,αn (∀i, j≦nに対しαi≦αj, α0 がminimum DFS code)とする。αi ( 1 ≦ i ≦ n )とその子孫の全て(すなわちDFS code tree内のαiを根とする部分木)を枝狩りして残ったDFS Code Treeは全ての最小DFS codeを含む。
(注意2.10) 定理2.4により、DFS code treeの最小DFSコードでないDFS codeを根とする部分木は全て枝狩りを行っても全ての部分グラフを網羅可能である(完全性)。
定義より支持度に関して以下の単調性が成立することがわかる。これにより、支持度が与えられた最小支持度を下回ったパターンはそれ以上拡張する必要がないことが保障される。

0138

「命題2.2(支持度の逆単調性)」



ここまでの理論はYanらの貢献による。本研究ではYanらの理論をベースにラベルにTaxonomy情報およびその枝狩り手法(文献2)の統合を行う。つまり、定義2.16で定義されるDFS code tree上を今回の制約を用いてさらに効率的に探索していく。さらに、cliqueなパターンのみを抽出することを利用した探索の効率化及びパターンの一般化コストによる枝狩り手法の提案を新たに行う。
導出パターンをCliqueなパターンに制限する場合には、DFS codeの子に対して「性質2.1」よりさらに強い制約を与えることが可能である。

0139

「命題2.3(抽出パターンのClique性を利用したDFSコードの拡張の制限)」
グラフGとDFS木Tが与えられているものとする。α= code ( G, T ) = ( a0, a1,・・・am ), ak = ( ik, jk, lik, ljk, l ( ik, jk ), d ( ik, jk ) ) とするとき、DFSコードの子要素に以下の制限を与えて得られるDFS code treeは、全てのCliqueな部分グラフの最小DFSコードを含む。
(1)ak が前向きの枝かつak+1 が前向きの枝であるならば、
k = 0 かつj0 = i1 = 1 かつj1 = 2
(2)ak が前向きの枝かつak+1 が後ろ向きの枝であるならば、
ik+1 = jk かつjk+1 = i0 ( = 0 )
(3)ak が後ろ向きの枝かつak+1 が前向きの枝であるならば、
ik = ik+1 かつjk+1 = ik +1かつik−2 = jk
(4)ak が後ろ向きの枝かつak+1 が後ろ向きの枝であるならば、
ik+1 = ik かつik+1 = ik

0140

(証明) (1)から(4)のいずれの条件も満たさない拡張によって得られられるDFSコードを根とする部分木にはCliqueなパターンを含まないことを示す。
(1)ak およびak+1 が前向きの枝であるとする。jk≠ik+1 とすると深さ優先木の定義から今後の拡張により後ろ向きの辺 ( jk+1, jk ) が拡張されることはない。よって jk = ik+1 としてよい。このとき、もしk≠0とするとik>1 となり、定義2.10を繰り返し使うとak = ( ik, jk )<( jk, ik−1 ) = ( ik+1, ik−1 )<( ik+1, jk+1 ) = ak+1 となるから今後の拡張により得られるパターンには後ろ向きの辺 ( ik+1, ik−1 ) が存在しない(従ってCliqueなパターンではない)。k = 0 とする。すなわち、ak かつak+1 が前向きの枝であるならば、拡張を(1)に制限することにより探索されないパターンはすべてCliqueでないパターンとなる。
(2)ak が前向きかつak+1 が後ろ向きの枝であるとする。ik+1 = jk はPropositionである。もし、jk+1>0 とすると、ak = ( ik, jk )<( ik+1, 0 )<( ik+1, jk+1 ) = ak+1 であるから、後ろ向きの辺 ( ik+1, 0 ) は今後の辺の拡張によって得られることはない。よって、拡張を(2)に制限することにより探索されないパターンは全てCliqueなパターンではない。
(3)明らかにik≧0 と仮定してよい。jk+1 = ik + 1 はProposition より成立するのは明らかである。もしik≠ik+1 であるとすると後ろ向きの辺 ( ik+1, ik ) は今後拡張されることはないから、ik = ik+1 。もしik−2≠jk ならば、ak = ( ik, jk )<( ik+1, ik−2 )<( ik+1, jk+1 ) = ak+1 となり、今後の拡張により得られるパターンには後ろ向きの辺 ( ik+1, ik−2 ) は存在しない。よって拡張を(3)に制限することにより探索されないパターンは全てCliqueなパターンではない。
(4)上と同様に(4)の制限を加えることにより探索されないパターンは全てCliqueなパターンではないことが示せる。
以上と定理2.3より題意が証明できた。
(注意2.11) 以下ではDFS code treeとは子要素に上記の制限を加えたDFS code treeを意味するものとする。
一般にDFSコードαの最小性の判定は、αの最小DFSコードとαが等しいかどうかを比較することにより行われる。これは、グラフの同型性を判定することと実質的に等価であり多大な計算量を要する。しかしながら、抽出するパターンをCliqueなパターンに限る場合には、 以下の命題を用いることによりこのDFSコードの最小性の判定を回避することができる。

0141

「命題2.4(導出パターンのclique制限を用いた自明な最小でないDFSコード)」
DFSコードα= ( a0, a1,・・・am ), ak = ( ik, jk, lik, ljk, l ( ik, jk ), d ( ik, jk )) ) が、あるk0 に対してak0 が前向きの枝かつljk0<min [ lp|p<k0 ] であるならば、DFS code tree内でαを根とする部分木を枝狩りして残った部分木はすべてのcliqueなパターンの最小DFSコードを含む。
(証明)パターンαを拡張して生成される最初のCliqueなパターンのDFSコードは最小でないことを示せば十分である。DFSコードαに対するグラフのDFS木をT = [ vi ]Ni=1 とすると、仮定からあるn (<N ) が存在してl ( vN )<l ( vn ) となる。αを拡張して得られる最初のCliqueなパターンPは、頂点[ vi ]Ni=1 からなる完全グラフとなり、そのDFSコードα’のDFS木は ( v1,・・・, vn-1, vn,・・・, vN ) である。しかしながら、DFS添え字付け ( v1,・・・, vn-1, vN,・・・)から得られるDFSコードをβとすると、β<αである。よって、パターンαを拡張して生成される最初のCliqueなパターンのDFSコードは最小でない。
次の命題を用いると、一般化コストによる枝狩りを効率よく行うことが可能となる。

0142

「命題2.5(Cliqueと最大一般化コストの制限を用いた枝狩り)」
グラフの集合GSとTaxonomy Tが固定されているものとする。さらに、以下の仮定を置く。
(1)ラベルのTaxonomyは頂点にのみ存在し、辺ラベルの一般化コストは全て0である。
(2)GSの任意のラベルx∈V ( T ) とTaxonomy Tにおけるその任意の祖先yに対してx<y を満たすラベル付けがなされている。
(3)ラベルx, yがx<yを満たすならば、c ( x ) ≦ c ( y )
このとき、DFS code tree上で一般化コストがmaxcostより大きいDFS codeを根とする部分木を枝狩りした結果残るDFS code treeは、すべての一般化コストがmaxcost以下かつcliqueなパターンの最小DFSコードを含む。
(証明) 命題2.4により、パターンに新しい頂点ラベルが追加される(DFSコードを前向きの辺により拡張する)場合、追加される頂点のラベルはパターンのどの頂点ラベルとも等しいか、より大きい。このことと仮定を用いると容易に証明できる。
(注意2.12) 前出の「分類データの生成」のセクションで説明された方法により構築されるタクソノミデータが上記の命題の条件を満たすことは容易にわかる。
(注意2.13) このPropositionは導出パターンをCliqueなパターンに制限しない場合には成立しない。また、DFSコードの順序付けを定義2.11のようにしなければ成立しない(辺のラベルより2つの頂点ラベルの方が順序付けに対する優先度が高い)。さらに、辺のラベルにもTaxonomyを考慮した場合にも成立しない。
最後に、導出パターンをover-generalizedでないパターンに制限する場合に対する枝狩りの基本となる理論について述べる。

0143

「定義2.17(重みつき支持度(文献2))」
グラフGとTaxonomy Tが与えられた際に、パターンPのグラフGにおける出現回数



と表す。このとき、グラフセットGS = [ Gi ] を固定したとき、パターンPに対して



をパターンPの重みつき支持度(weighted support)と呼ぶ。ここで、

0144

「命題2.6」グラフの集合GSとTaxonomy Tを固定する。GSの任意のラベルx∈V ( T ) と、Taxonomy Tにおけるその任意の祖先y∈ans ( x ) に対してx<yを満たすラベル付けがなされているものとする。このときパターンPの一般化パターンをP' とするとP<P' である。すなわち任意のパターンPに対してその一般化パターンP' はDFS code tree上ででPより後に出現する。
(証明) PとP' の最小DFS codeをそれぞれα,βとするとき、α<βとなることを示せばよい。一般化パターンの定義と、ラベル付けの仮定により容易に示せる。

0145

「命題2.7(文献2)」DFS code tree上のDFS code Pに対して、Pより以前に出てきたDFSコードP' で、P(の表現するグラフ)がP'(の表現するグラフ)の一般化されたパターンでありかつsupw ( P ) = supw ( P' ) を満たすものが存在するとき、DFSコードPを根にもつ部分木を枝狩りした結果残る部分木は全てのover-genralizedでない部分グラフの最小DFSコードを含む。
(注意2.14) この命題を用いて過度に一般化されたパターンの枝狩りを効率良く行うためには、あるパターンの特殊化パターンはそのパターンより以前に探索されていなければならない。命題2.6により、任意のパターンはその特殊化パターンよりDFS Lexicographic orderで後に出現するため、DFS lexicographic orderでDFS code treeを探索すれば、上記の枝狩りは効率よく行えることがわかる。
(注意2.15) この条件による枝狩りだけでは、全てのover-generalizedでないパターンをDFS code treeの探索の段階で枝狩りをすることはできない。枝狩りにもれたパターンは後処理で削除する。

0146

「2.5アルゴリズム」
本セクションでは、セクション2.4で述べた理論に基づいて構築されるアルゴリズムについて述べる。その骨格部分は、図17のアルゴリズム1(Algorithm 1)である。アルゴリズムの入力はRNA配列の集合(複数のファミリーや未知のファミリーが含まれていても構わない)と最小支持度(minimum support)、最大一般化コスト(maximum generalization cost)である。まず、セクション2.2に述べる方法によりRNA配列集合からグラフ集合GSおよび頂点ラベルのTaxonomy Tを構築する(line 2)。次にGSから辺のサイズが1の頻出でありかつ一般化コストがmaxcost以下のパターンを抽出する。ここで頻出パターンと一般化コストがmaxcost以下のパターンだけを考えれば十分なのは、命題2.2と命題2.5により保障されている。その後、Cinitial をDFS lexicographi order(定義2.13)でソートし、その順番でCinitialのパターンに対して、アルゴリズムGraphMining (アルゴリズム2(Algorithm 2)(図18))を呼び出す。最後に、PSからnon-closed patternおよびnon-cliqueパターンを除く(line 8)。

0147

アルゴリズム2(Algorithm 2)は提案手法におけるグラフマイニングの骨格部分である。まず、現在考えているパターンsの最小性を判定し、最小でないものに関しては探索を打ち切る(line 3)。この操作によりアルゴリズムの完全性が保たれることは定理2.4による。この際、DFS codeの最小性判定にはコストがかかるため命題2.4を用いて最小性の判定をやらなくていいものに関しては行わない。次に一般化コストの判定を行い、一般化コストがmaxcostより大きいものに関しては探索を打ち切る。これを保障するのが命題2.5である。最後にover-generalizedなパターンであるかどうかの判定を行い、over-generalizedなパターンであれば探索を打ち切る(line 4)。この判定は、命題2.7により行うが注意2.14にも述べたとおりこの段階ですべてのover-generalizedなパターンを除くことはできない。以上で枝狩りをされなかったパターンはPSに保存する。ここで注意するのは、PSにはcliqueでないパターンも格納する(line 5)。これはover-generalizedなパターンの判定に使用するためである。
line 6では辺を1つ拡張することにより、現在のパターンsの拡張を行う。ここでは命題2.3の条件を満たすようにパターンを拡張し、頻出である(支持度がminsupより大きい)パターンをCに格納する(line 6)。その後、Cのパターンに対してDFS lexicographic orderの順番で再帰的にアルゴリズムGraphMiningを呼び出す。

0148

「3実装」
本アルゴリズムを実装したソフトウェアRNAminer(RNA stem pattern miner)を開発した。実装はC++言語およびSTL/ Boostライブラリを用いて行った。さらに現在の実装においては、グラフの同型性判定ライブラリとしてVFlib 2.0(文献21)をクラスタリングのライブラリとしてCluster 3.0(文献22)を用いている。また、塩基対確率行列の計算にはVienna RNA package(文献23)のライブラリを用いている。
なお、ステム候補の抽出の部分で塩基対単位でギャップが許されてよい。また、ステム候補は塩基対の極大集合として抽出するので、ステム候補間が若干オーバラップしていても辺を与えてよい。

0149

「参考文献」
以下の参考文献のうち、(文献3)は(非特許文献12)と同じであり、(文献5)は(非特許文献17)と同じであり、(文献6)は(非特許文献16)と同じである。
(文献1)
Ramakrishnan Srikant and Rakesh Agrawal. Mining generalized association rules. Future Gener. Comput. Syst., Vol. 13, No. 2-3, pp. 161-180, 1997.
(文献2)
Akihiro Inokuchi. Mining generalized substructures from a set of labeled graphs. InICDM, pp. 415-418.IEEE Computer Society, 2004.
(文献3)
Y Tabei, K Tsuda, T Kin, and K Asai.SCARNA:Fast and Accurate Structural Alignment of RNA Sequences by Matching Fixed-length Stem Fragments. submitted to Bioinformatics.
(文献4)
Vineet Bafna, Haixu Tang, and Shaojie Zhang. Consensus folding of unaligned rna sequences revisited. In Satoru Miyano, Jill P. Mesirov, Simon Kasif, Sorin Istrail, Pavel A. Pevzner, and Michael S. Waterman, editors, RECOMB, Vol. 3500 of Lecture Notes in Computer Science, pp. 172-187. Springer, 2005.
(文献5)
Helene Touzet and Olivier Perriquet. CARNAC: folding families of related RNAs. Nucleic AcidsRes, Vol. 32, No. Web Server issue, pp. 142-145, Jul 2004. Evaluation Studies.
(文献6)
Yongmei Ji, Xing Xu, and Gary D Stormo. A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics, Vol. 20, No. 10, pp. 1591-1602, Jul 2004. Evaluation Studies.
(文献7)
Daniela Fera, Namhee Kim, Nahum Shiffeldrim, Julie Zorn, Uri Laserson, Hin Hark Gan, and Tamar Schlick. RAG: RNA-As-Graphs web resource.BMCBioinformatics, Vol. 5, p. 88, Jul 2004.
(文献8)
J S McCaskill. The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers, Vol. 29, No. 6-7, pp. 1105-1119, May 1990.
(文献9)
Robert J Klein and Sean R Eddy. RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics, Vol. 4, p. 44, Sep 2003.
(文献10)
T F Smith and M S Waterman. Identification of common molecular subsequences. J Mol Biol, Vol. 147, No. 1, pp. 195-197, Mar 1981.
(文献11)
D Bouthinon and H Soldano. A new method to predict the consensus secondary structure of a set of unaligned RNA sequences. Bioinformatics, Vol. 15, No. 10, pp. 785-798, Oct 1999.
(文献12)
Jun Huan, Wei Wang, and Jan Prins. Efficient mining of frequent subgraphs in the presence of isomorphism. In ICDM '03: Proceedings of the Third IEEE International Conference on Data Mining, p. 549, Washington, DC, USA, 2003. IEEE Computer Society.
(文献13)
Michihiro Kuramochi and George Karypis. Frequent subgraph discovery. In ICDM '01: Proceedings of the 2001 IEEE International Conference on Data Mining, pp. 313-320, Washington, DC, USA, 2001. IEEE Computer Society.
(文献14)
Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda. An apriori-based algorithm for mining frequent substructures from graph data. InPKDD'00: Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, pp. 13-23, London, UK, 2000. Springer-Verlag.
(文献15)
Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda. Complete mining of frequent patterns from graphs: Mining graph data. Mach. Learn., Vol. 50, No. 3, pp. 321-354, 2003.
(文献16)
Akihiro Inokuchi, Takashi Washio, Kunio Nishimura, and Hiroshi Motoda. A Fast Algorithm for Mining Frequent Connected Subgraphs. IBM Research. In IBM Research Report, 2002.
(文献17)
Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. In ICDM '02: Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p. 721, Washington, DC, USA, 2002. IEEE Computer Society.
(文献18)
Xifeng Yan and Jiawei Han. Closegraph: mining closed frequent graph patterns. In KDD '03: Proceedings of the ninthACMSIGKDD international conference on Knowledge discovery and data mining, pp. 286-295, New York, NY, USA, 2003. ACM Press.
(文献19)
T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms (2nd edition).MIT Press, 2001.
(文献20)
Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. 2002.
(文献21)
C. Goggia and S. Tortorella. Graph matching: A fast algorithm and its evaluation. 1999.
(文献22)
M J L de Hoon, S Imoto, J Nolan, and S Miyano. Open source clustering software. Bioinformatics, Vol. 20, No. 9, pp. 1453-1454, Jun 2004. Evaluation Studies.
(文献23)
I.L. Hofacker, W. Fontana, P.F. Stadler, S. Bonhoeffer, M. Tacker, and P. Schuster. Fast folding and comparison of RNA secondary structures. Monatsh. Chem., Vol. 125, pp. 167-188, 1994.
(文献24)
Bernhart SH, HofackerIL, and Stadler PF. Local RNA base pairing probabilities in large sequences. Bioinformatics, Dec 2005. JOURNALARTICLE.

0150

以上に本発明の好適な実施の形態を説明した。しかし、本発明は上述の実施の形態に限定されず、当業者が本発明の範囲内で上述の実施の形態を変形可能なことはもちろんである。

0151

以上のように、本発明は、複数のRNA配列データからコンピュータ処理によって2次構造モチーフを抽出することができ、バイオインフォマティクス技術として有用である。

図面の簡単な説明

0152

DNAおよびRNAの配列を示す図である。
RNAの局所的な2次構造の例を示す図である。
RNAの2次構造の例を示す図である。
本実施の形態のRNA配列情報処理を実現するコンピュータを示す図である。
本実施の形態のRNA配列情報処理の全体像を示す図である。
本実施の形態のRNA配列情報処理装置の機能ブロック図である。
塩基対確率行列を示す図である。
ステムグラフを示す図である。
ステムグラフを示す図である。
ステム候補間の3タイプの接続関係を示す図である。
分類データとしてのタクソノミを示す図である。
本実施の形態におけるグラフ解析の原理を示す図である。
分類データを用いたステムパターンの比較処理を示す図である。
ステムパターンの一般化コストを示す図である。
支持度の定義を示す図である。
パターン探索アルゴリズムのDFSツリーを示す図である。
本実施の形態のRNA配列情報処理を実現するアルゴリズムを示す図である。
本実施の形態のRNA配列情報処理を実現するアルゴリズムを示す図である。

符号の説明

0153

21RNA配列情報処理装置
23 配列データ入力部
25 配列データ記憶部
27ステム候補抽出部
29 ステム候補記憶部
31グラフ生成部
33 グラフ記憶部
35分類データ生成部
37 分類データ記憶部
39グラフ解析部
41最小支持度入力部
43 最大一般化コスト入力部
45 出力部
472次構造データ生成部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 日清食品ホールディングス株式会社の「 プライマー及びマンゴーの検出方法」が 公開されました。( 2020/09/24)

    【課題】アレルギーを引き起こす恐れのあるマンゴーが食品原料や製品等に含まれていた場合に、その量が微量であっても高感度で検出することが可能なPCRプライマーを提供する。【解決手段】検出対象とするマンゴー... 詳細

  • ナガセケムテックス株式会社の「 核酸吸着材」が 公開されました。( 2020/09/24)

    【課題】タンパク質、核酸などを含む溶液中の核酸を選択的に吸着することができる核酸吸着材を提供する。【解決手段】窒素原子を含むカチオン性基を有するセルロースナノファイバーを備える、核酸吸着材。窒素原子を... 詳細

  • 国立大学法人名古屋大学の「 生体分子を分離するための流体デバイス及び方法」が 公開されました。( 2020/09/24)

    【課題】生体分子(タンパク質、核酸、細胞、小胞体など)を体液又は生体由来の溶液から短時間、高収率で分離できるデバイス及び方法の提供。【解決手段】平坦面を有する基板102と、平坦面の少なくとも一部に配置... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ