ＲＮＡ配列情報処理装置
【課題】ＲＮＡ配列群から２次構造モチーフを抽出する新規な技術を提供する。
【解決手段】複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補が抽出される。各RNA配列のステム候補を用いてステムグラフが生成される。ステムグラフは、複数のステム候補を頂点として有し、頂点間を辺で結んだグラフである。複数のＲＮＡ配列に対応する複数のステムグラフが分析される。それらステムグラフに頻出する類似した部分グラフが、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出される。複数のステムグラフのステム候補群が分類されて、分類データが生成される。分類データを用いて、類似する部分グラフが抽出される。ラベル付き有向グラフが好適に生成される。また、分類データとして階層的なタクソノミデータが生成される。
【解決手段】複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補が抽出される。各RNA配列のステム候補を用いてステムグラフが生成される。ステムグラフは、複数のステム候補を頂点として有し、頂点間を辺で結んだグラフである。複数のＲＮＡ配列に対応する複数のステムグラフが分析される。それらステムグラフに頻出する類似した部分グラフが、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出される。複数のステムグラフのステム候補群が分類されて、分類データが生成される。分類データを用いて、類似する部分グラフが抽出される。ラベル付き有向グラフが好適に生成される。また、分類データとして階層的なタクソノミデータが生成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のＲＮＡ配列データをバイオインフォマティクス技術によって処理して、それら複数のＲＮＡ配列データに共通に含まれる２次構造モチーフを抽出する技術に関する。
【背景技術】
【０００２】
近年、多くのＲＮＡがタンパク質に翻訳されることなく、それ自身が機能性分子として生理学的に重要な役割を果たすことが明らかになってきた。これらのＲＮＡは総称して機能性ＲＮＡ（functional RNA）または非コードＲＮＡ（non-coding RNA, ncRNA）と呼ばれ非常に注目を集めている。たんぱく質と同様に、機能性ＲＮＡは、１次配列よりも立体構造がその機能に重要であると考えられている。また、Tinoco らは、ＲＮＡの立体構造は２次構造により大部分が決定されるとの報告をしている（非特許文献１）。それらを裏付けるように、多くの機能性ＲＮＡが、進化的に高度に保存された大域的あるいは局所的な２次構造モチーフを有する機能ファミリーを形成している（例えばtRNA, RNaseP-bact-a, tmRNAなど（http://www.sanger.ac.uk/software/rfam/））。従って、機能性ＲＮＡファミリーを特定すること及び機能性ＲＮＡファミリーを特徴付ける２次構造モチーフを抽出することは、機能性ＲＮＡを解析する際に非常に有用な情報をもたらす。
【０００３】
現在のところ、ＲＮＡの２次構造予測の手法は大きく分けて２種類存在する。そのひとつが、mfold（非特許文献２）やRNAfold（非特許文献３）に代表される、最小自由エネルギー（Minimum Free energy, MFE）に基づいた単一のＲＮＡ配列からの２次構造予測である。これらの手法は比較的古くから研究がなされているが、一般的にはそれほど高精度ではない。その理由は、エネルギーパラメタの精度や、また、実際のＲＮＡ分子は他の分子との相互作用の中で立体構造を形成しているため単一の配列の最適な構造とは異なることなど、にあると考えられる。そのため、最適な構造だけでなく、準最適な２次構造まで導出する手法（非特許文献４、５、６）や統計的にＲＮＡの２次構造をサンプリングする手法（非特許文献７、８）の研究もなされている。
【０００４】
もうひとつが、共通の二次構造を有すると考えられる複数のＲＮＡを用いた（共通）２次構造予測手法である。この手法には、入力配列のアラインメントを必要とするもの(RNAalifold（非特許文献９）、ILM（非特許文献１０）、Pfold（非特許文献１１）など) とアラインメントを必要としないもの（ScaRNA（非特許文献１２）、Cofolga（非特許文献１３）、PMcomp/PMmulti（非特許文献１４）、RNAcast（非特許文献１５）、comRNA（非特許文献１６）、CaＲＮＡc（非特許文献１７）など）が存在する。これらの手法は、似たような構造を有する入力配列群が適切に与えられれば、ＭＦＥだけに基づいた２次構造予測よりも多くの情報を用いるので一般的には精度が良いとされている。ただし、アラインメントを仮定せずに、複数配列からその共通２次構造を導出する数理的に厳密なアルゴリズムは、Sankoff アルゴリズム（非特許文献１８）と呼ばれるものと等価となり、時間計算量と記憶計算量が膨大である。
【０００５】
このような一般的な２次構造の予測手法だけでなく、ＲＮＡのモチーフに焦点を当てたＲＮＡ情報解析技術も多数存在する（非特許文献１９）。ERPIN（非特許文献２０、２１）、Infernal（非特許文献２２）、RNAMotif（非特許文献２３）は、ＲＮＡのマルチプルアラインメントから、それらの２次構造モチーフのモデル化を行い、構築されたモデルを用いてゲノム上からそのモデルに適合する２次構造モチーフの探索を行う。すなわちこれらの手法は、既知のモチーフを有する配列を発見する際に利用可能である。一方で、ファミリーを形成すると考えられる機能性ＲＮＡ配列群から、そのファミリーを特徴付けるモチーフを抽出するための手法も存在する。GPRM（非特許文献２４）は、遺伝的アルゴリズムを用いて入力配列群とランダム配列群とを区別する２次構造モチーフの発見を行う。RNAprofile（非特許文献２５）は、Greedy かつヒューリスティックな方法により探索空間を減少させ、整列していないＲＮＡ配列群から局所的に保存された２次構造モチーフを発見する手法を提案している。さらについ最近では、CMfinder（非特許文献２６）と呼ばれるCovariance Model とヒューリスティック手法を組み合わせた、ノイズに対してロバストな、非整列ＲＮＡ配列群からのモチーフ発見手法も提案されている。これらの機能性ＲＮＡファミリーからのモチーフ抽出手法は、ある程度のノイズに対しては影響を受けないような工夫がされているが、基本的には単一のＲＮＡのファミリーである配列群に適用する手法である。しかしながら、解析対象となるＲＮＡ配列集合に複数のファミリーや未知のファミリーが含まれるという現実的な状況においては、機能性ＲＮＡファミリーの特定と２次構造モチーフの抽出は表裏一体となり、同時に行われることが望ましい。なぜなら、ファミリーの決定にはファミリーを特徴付ける２次構造モチーフが必要であり、かつ、２次構造モチーフの決定にはファミリーが必要となるからである。これは、ある意味、特徴抽出とクラスタリングを同時に行う問題に近いといえる。
【０００６】
その他の関連する背景技術を説明すると、ＲＮＡ配列のグラフによるモデル化の既存手法としては、RAG（非特許文献２７）が有名であるが、これはＲＮＡの２次構造のモデル化を行う方法である。また、非特許文献２８は、ＲＮＡファミリーの２次構造のプロファイルが与えられた際に、そのプロファイルをグラフで表現すると同時に、プロファイルを用いてゲノム配列（の断片）をグラフによりモデル化する方法を提案している。
【非特許文献１】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. JOURNAL ARTICLE.
【非特許文献６】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. The ERPIN 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. BMC Bioinformatics, 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.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述してきたように、機能性ＲＮＡの機能ファミリーを同定すること及びファミリーを特徴付ける２次構造モチーフを抽出することは共に機能性ＲＮＡの解析において非常に重要である。解析対象となるＲＮＡ配列集合に複数のファミリーや未知のファミリーが含まれているという現実的な問題設定の下では、機能性ＲＮＡファミリーの特定と２次構造モチーフの抽出は互いに密接に関連した問題となり、同時に解くべき必要が生じる。なぜなら、ファミリーの決定にはファミリーを特徴付ける２次構造モチーフが必要であり、かつ、２次構造モチーフの決定にはファミリーが必要となるからである。しかしながら、既存のＲＮＡ解析手法では、これらの問題を同時に解く手法は存在しない。
【０００８】
本発明は上記背景の下でなされたものであり、その目的は、コンピュータを用いたバイオインフォマティクスの情報処理によってＲＮＡ配列群から２次構造モチーフを抽出することができる好適な配列データ処理技術を提供することにある。本発明の一つの目的は、機能性ＲＮＡのファミリーの特定とモチーフ抽出を同時に行うことが可能な技術を提供することにある。
【課題を解決するための手段】
【０００９】
本発明は、ＲＮＡ配列データを対象とした配列情報処理技術を提供する。本発明は、概略的には、ＲＮＡ配列群をタクソノミ（Taxonomy）を用いたラベル付き有向グラフでモデル化し、近年データマイニングの分野で活発に研究されているグラフ解析（グラフマイニング）手法を応用して、配列群に頻出するステムパターン（２次構造モチーフ）の抽出およびそのステムパターンを有するＲＮＡ配列集合（機能性ＲＮＡファミリー）の特定を行う。ここで言うグラフマイニング手法とは、与えられたグラフセットから多頻度で出現する部分グラフ（グラフパターン）を効率的かつ完全に抽出する手法であり、後に例示されるように近年様々なアルゴリズムが提案されている。本発明は、これらのグラフマイニング手法を応用すると同時に、抽出するグラフパターンがClique（完全グラフ）であるという性質を利用して探索空間を効率良く削減させる。さらに、本発明は、グラフの一般化コストと呼ばれる新しい概念を導入することにより、更なる効率化を行っている。また、本発明は、ランク付けされたステムのパターンの候補を複数導出すると同時に、ステムのパターンに対して各ＲＮＡの２次構造を複数導出することが可能である。本発明で提案している、頂点間の類似度からクラスタリングにより頂点ラベルのTaxonomy を構築し頻出グラフマイニングを行う手法は、対象をグラフによりモデル化した際に、頂点間の類似度や非類似度が自然に定義できる場合に好適に適用可能な手法となっている。
【００１０】
本発明の一態様は、ＲＮＡ配列情報処理装置であり、この装置は、複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出するステム候補抽出部と、各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成するグラフ生成部と、前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを解析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出するグラフ解析部と、を備えている。
【００１１】
上記のように、本発明は、複数のＲＮＡ配列データから複数のステムグラフをそれぞれ生成する。ステムグラフは、ＲＮＡ配列中の潜在的なステムの候補が頂点であり、頂点間を辺で結んだグラフである。このようなグラフにおいては、部分グラフがステムパターンであり、ステムパターンはＲＮＡ配列の部分的な２次構造を表す。したがって、同様の部分グラフが複数のステムグラフに頻出すれば、その類似部分グラフは、複数のＲＮＡ配列に共通の２次構造モチーフである。本発明は、この点に着目して、複数のステムグラフに頻出する類似部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出している。このようにして、本発明によれば、ＲＮＡ配列群から２次構造モチーフを抽出することができる。
【００１２】
本発明の情報処理が、機能性ＲＮＡのファミリーが特定されていないＲＮＡ配列群に適用されたとする。この場合、頻出ステムパターンが抽出されると同時に、頻出ステムパターンを含むＲＮＡ配列（ステムグラフ）も分かる。すなわち、２次構造モチーフが抽出されると同時に、２次構造モチーフを含むファミリーを同定することができる。また、本発明は、既に同定されている機能ファミリーの配列群に適用されてもよく、この場合にも２次構造モチーフが好適に抽出される。
【００１３】
前記グラフ生成部は、前記ＲＮＡ配列上での各ステム候補対の位置関係に応じた向きを、前記各ステム候補対を結ぶ辺のラベルに付与してよい。前記グラフ解析部は、前記複数のステムグラフから、対応する辺の向きが同じ前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１４】
前記グラフ生成部は、各ステム候補対の接続関係が並列、埋込み、重複のいずれかに属するかの情報を、前記各ステム候補対を結ぶ辺のラベルに付与してよい。前記グラフ解析部は、前記複数のステムグラフから、対応する辺の前記接続関係が同じ前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１５】
前記グラフ生成部は、前記並列、埋込みおよび重複のいずれにも該当しないステム候補対を辺での接続対象から除外してよい。これにより、不適当な部分グラフの抽出を回避して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１６】
前記グラフ生成部は、各頂点が部分グラフ内のすべての他の頂点と辺で結ばれる完全部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１７】
本発明のＲＮＡ配列情報処理装置は、前記複数のステムグラフに含まれる前記複数のステム候補を類似性に基づいて分類する分類データを生成する分類データ生成部を含んでよい。前記グラフ解析部は、前記複数のステムグラフから、対応する頂点のステム候補が同じ分類に属する前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１８】
前記分類データ生成部は、前記分類データとして、前記複数のステム候補を、類似範囲の広さが下位層から上位層へ向かって増大するように階層的にクラスタリングを行ったタクソノミデータを生成してよい。前記グラフ解析部は、前記タクソノミデータに基づき、対応する頂点のステム候補が下位層では異なる分類に属しても上位層では同一分類に属する前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１９】
本発明のＲＮＡ配列情報処理装置は、前記タクソノミデータにて階層に応じて増大する一般化コストの最大許容値である最大一般化コストを入力する最大一般化コスト入力部を含んでよい。前記グラフ解析部は、前記最大一般化コスト以下の一般化コストを有する前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００２０】
前記分類データ生成部は、ステム候補対の類似性を表す類似性パラメータを、ステム候補対の配列相同性、ステム候補により形成されるループの距離の類似性、および、ＲＮＡ配列内でのステム候補の位置の類似性の少なくとも一つに応じて求めてよい。また、分類データ生成部は、ステム候補対の類似性を類似性パラメータを、ステム候補の塩基対形成確率に応じて求めてよく、このとき、２つのステム候補の塩基対形成確率の和が評価されてよく、そして、和の値が大きいほど類似度が高いと判断されてよい。これにより、ステム候補である頂点間の類似性を適切に判断して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００２１】
本発明のＲＮＡ配列情報処理装置は、前記複数のステムグラフにおける前記部分グラフの支持度の最小許容値である最小支持度を入力する最小支持度入力部を含んでよい。前記グラフ解析部は、前記最小支持度以上の支持度を有する前記部分グラフを抽出してよい。支持度はグラフ解析で使われる用語で、頻度（頻出の程度）を表す。最小支持度以上の支持度を有する部分グラフを抽出することにより、ＲＮＡ配列群に頻出するステムパターンを適切に抽出できる。
【００２２】
前記ステム候補抽出部は、分子構造のエネルギに基づいて前記ＲＮＡ配列上の任意の２つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域を前記ステム候補として抽出してよい。これにより、ステム候補を適切に抽出することができる。
【００２３】
本発明のＲＮＡ配列情報処理装置は、単独のコンピュータで実現されてもよく、複数のコンピュータからなるシステムによって実現されてもよい。ＲＮＡ配列情報処理装置は、インターネット等のネットワークを介して、データの受付（入力）と提供（出力）を行ってもよい。
【００２４】
また、本発明は上記のＲＮＡ配列情報処理装置の態様に限定されない。本発明の別の態様は、例えば、コンピュータによる情報処理方法であり、また、そのような方法を実現するプログラムである。このような別の態様にも、上述のＲＮＡ配列情報処理装置に関する各種の発明を適用可能なことはもちろんである。
【００２５】
本発明の別の態様は、複数のＲＮＡ配列からコンピュータ処理によって２次構造モチーフを抽出するＲＮＡ配列情報処理方法である。この方法は、複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出し、各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出する。この態様でも上述の本発明の利点が得られる。
【００２６】
また、本発明の別の態様は、複数のＲＮＡ配列から２次構造モチーフを抽出する配列情報処理をコンピュータに実行させるＲＮＡ配列情報処理プログラムである。このプログラムは、複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出し、各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出する、処理を前記コンピュータに実行させる。この態様でも上述の本発明の利点が得られる。
【発明の効果】
【００２７】
上記のように、本発明は、コンピュータを用いた情報処理によって複数のＲＮＡ配列から２次構造モチーフを抽出することができる配列データ処理技術を提供できる。本発明は、機能性ＲＮＡのファミリーの特定とモチーフ抽出を同時に行うことが可能な技術を提供できる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の実施の形態を図面を参照して説明する。以下に説明されるように、本実施の形態のバイオインフォマティクス技術は、全体としては、RNA配列を処理の対象とし、RNAの２次構造を有向グラフで表現し、階層的分類に基づいたグラフ探索処理を有向グラフに組み合わせて２次構造パターンの抽出を行う新規な手法を提供する。
【００２９】
まず、本発明のバイオインフォマティクス技術を説明する前に、ＲＮＡ配列の２次構造を説明する。
【００３０】
図１を参照すると、周知のように、ＤＮＡおよびＲＮＡを構成する塩基は、ａ、ｕ（ｔ）、ｃ、ｇで表される。そして、ａとｕが相補塩基対を作り、ｃとｇが相補塩基対を作る。ＤＮＡでは、逆相補配列が２重らせんを形成している。これに対して、構造ＲＮＡでは、１本鎖が折り畳まれる。そして、相補塩基対により２次構造が作られる。
【００３１】
図２は、局所的な２次構造の例を示している。図示のように、１本鎖ＲＮＡ上には、互いに相補的な２つの領域が存在している。２箇所の相補的な領域が結合し、これにより２次構造が作られる。２次構造を作る相補的な領域は、ステムと呼ばれている。以下の説明では、ステムを形成する２つの部分配列を必要に応じてパーツまたはステムパーツと呼ぶ。２つのパーツが結合されてステムが形成される。
【００３２】
図３は、より大きな範囲の２次構造の例を示している。図示のように、１つのＲＮＡ配列に複数のステムが存在している。
【００３３】
図４は、本実施の形態のＲＮＡ配列情報処理装置を実現するコンピュータを示している。図４のコンピュータ１において、プログラム実行部３は、ＣＰＵ等のプロセッサで構成され、プログラム記憶部５および処理データ記憶部７は、メモリで構成される。また、コンピュータ１は、ハードディスク等の外部記憶装置１１を備え、さらに、入力装置１３、出力装置１５、記録媒体装着部１７および通信部１９などを備えている。
【００３４】
プログラム記憶部５は、本実施の形態の装置および方法を実現するためのプログラムを記憶し、特に、ステム候補抽出プログラム、グラフ生成プログラム、分類データ生成プログラムおよびグラフ解析プログラムを記憶する。これらプログラムは、外部記憶装置１１から読み出され、そいて、プログラム実行部３により実行される。これらプログラムの機能の詳細は後述する。
【００３５】
処理データ記憶部７は、処理されるべきデータや、処理後のデータを記憶する。処理データ記憶部７は、例えば、処理対象のＲＮＡ配列データ、ステム候補データ、ステムグラフデータ、分類データおよびグラフ解析データを記憶する。その他にも、メモリは、プログラム実行部３による処理の作業エリアとして機能し、各種の処理データを記憶する。
【００３６】
コンピュータ１へのデータの入出力は、典型的には、入力装置１３および出力装置１５を介して行われる。その他、データの入出力は、記録媒体装着部１７を介して、記録媒体との間で行われてよい。また、データの入出力は、通信部１９を介して行われてよい。コンピュータ１がＷＥＢサーバに接続され、ネットワークを介してデータが入出力されてよい。あるいは、コンピュータ１がＷＥＢサーバの機能を有していてもよい。
【００３７】
ＲＮＡ配列情報処理装置は、概略的には、ＲＮＡ配列群から、個々の配列に潜在するステム候補を抽出し、ＲＮＡ配列群に頻出するステムパターンを抽出する。ステムパターンは、複数のステムにより形成されるパターン（部分的配列）である。このステムパターンは、ＲＮＡのモチーフ抽出に応用され、また、ＲＮＡのファミリー抽出に応用され、さらには、複数配列からの２次構造予測に応用される。
【００３８】
本実施の形態において、入力データと出力データは以下の通りである。入力データは、ＲＮＡ配列群のデータである。ＲＮＡ配列群に整列（アライメント）が施されていなくてよい。また、ＲＮＡ配列群が同一のＲＮＡファミリーに属している必要はない。コンピュータ１はＲＮＡ配列情報処理装置として機能し、図４の各種プログラムに従ってＲＮＡ配列群のデータを処理して、ＲＮＡ配列群に頻出する頻出ステムパターンを求め、さらに、頻出ステムパターンに対応する二次構造を求める。これら頻出ステムパターンおよび二次構造が出力データとして出力される。その他、本実施の形態では、パラメータとして最小支持度および最大一般化コストが入力される。これらパラメータは、頻出ステムパターンの抽出処理において、抽出条件として処理される。
【００３９】
図５は、ＲＮＡ配列情報処理の全体像を示している。図示のように、ＲＮＡ配列群が入力される（Ｓ１）。上述したように、ＲＮＡ配列群は整列されていなくてよい。各ＲＮＡ配列がステム候補抽出プログラムの処理を受け（Ｓ２）、各ＲＮＡ配列のステム候補が抽出される（Ｓ３）。本実施の形態では、ステム候補抽出プログラムは、塩基対確率行列を生成するプログラムによって実現される。
【００４０】
次に、ステム候補の情報から、ステムグラフと分類データが、グラフ生成プログラムおよび分類データ生成プログラムにより生成される（Ｓ４）。各ＲＮＡ配列に対して一つのステムグラフが生成される。ステムグラフは、ＲＮＡ配列から抽出された複数のステム候補を頂点とし、頂点間を辺で結んだグラフである。本実施の形態では、後述するようなラベル付き有向グラフが生成される。また、分類データは、複数のＲＮＡ配列群から抽出された全部のステム候補（グラフの頂点）をそれらの類似性に基づき分類したデータであり、本実施の形態では図示のように、階層構造を持つツリー型タクソノミデータ（taxonomy）である。
【００４１】
次に、ステムグラフ群がグラフ解析プログラムによって解析されて（Ｓ５）、ステムグラフ群に頻出する部分グラフが抽出され、さらに部分グラフに対応する２次構造が求められる（Ｓ６）。部分グラフは、ステムグラフの一部の頂点と辺で構成されるパターンであり、ステムパターンに相当する。本実施の形態は、グラフ形状が類似し、かつ、対応する頂点のステム候補が類似し、ステムグラフ群に頻出する部分グラフを抽出する。頂点の類似は分類データから求められる。このような頻出部分グラフが、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出される。そして、頻出部分グラフに対応する２次構造が求められる。
【００４２】
図６は、上述した処理を実現するためのＲＮＡ配列情報処理装置を機能ブロック図のかたちで示している。図６のＲＮＡ配列情報処理装置２１において、配列データ入力部２３は、ＲＮＡ配列群のデータを入力する。入力されたＲＮＡ配列データは、配列データ記憶部２５に記憶される。ステム候補抽出部２７は、入力された各々のＲＮＡ配列から、ＲＮＡ２次構造のステム候補を抽出し、ステム候補記憶部２９に格納する。
【００４３】
グラフ生成部３１は、各ＲＮＡ配列のステムグラフを生成し、グラフ記憶部３３に記憶する。また、分類データ生成部３５は、ステムグラフの頂点（ステム候補）に関する分類データを生成して、分類データ記憶部３７に格納する。本実施の形態では、ラベル付き有向グラフと階層的なツリー型タクソノミデータが生成される。
【００４４】
グラフ解析部３９は、分類データを参照しながらステムグラフ群を解析して、それらステムグラフに頻出する部分グラフを抽出する。グラフ解析部３９は、グラフ形状が類似し、かつ、対応する頂点のステム候補が類似する部分グラフを抽出する。このような部分グラフが、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出される。
【００４５】
最小支持度入力部４１および最大一般化コスト入力部４３は、頻出ステムパターン抽出処理における抽出条件を決定するパラメータである最小支持度および最大一般化コストを入力する。これらパラメータは、グラフ解析部３９の処理に用いられる。
【００４６】
出力部４５は、グラフ解析部３９によって抽出された頻出ステムパターンの情報を出力する。また、出力部４５は、頻出ステムパターンに対応する２次構造データを出力する。２次構造データは、２次構造データ生成部４７により生成される。
【００４７】
図６の構成において、配列データ入力部２３、最小支持度入力部４１および最大一般化コスト入力部４３は、図４の入力装置１３、記録媒体装着部１７または通信部１９によって実現される。また、出力部４５は、図４の出力装置１５、記録媒体装着部１７または通信部１９によって実現される。また、ステム候補抽出部２７、グラフ生成部３１、分類データ生成部３５およびグラフ解析部３９は、図４のプログラム記憶部５に記憶されたステム候補抽出プログラム、グラフ生成プログラム、分類データ生成プログラムおよびグラフ解析プログラムをプログラム実行部３が実行することによって実現される。２次構造データ生成部４７も、プログラム記憶部５のプログラムをプログラム実行部３が実行することにより実現される。また、配列データ記憶部２５、ステム候補記憶部２９、グラフ記憶部３３および分類データ記憶部３７は、図４の処理データ記憶部７および外部記憶装置１１によって実現される。
【００４８】
以下、ＲＮＡ配列情報処理装置の各部機能についてより詳細に説明する。
【００４９】
「ステム候補の抽出」
図６のステム候補抽出部２７は、各々のＲＮＡ配列データから、ＲＮＡ２次構造の複数のステム候補を抽出する処理を行う。本実施の形態では、以下に説明するように、ステム候補抽出部２７が、分子構造のエネルギに基づいてＲＮＡ配列上の任意の２つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域をステム候補として抽出する。
【００５０】
図７は、ＲＮＡ配列データから生成された塩基対確率行列を、ＲＮＡ配列の２次構造の例と共に示している。塩基対確率行列においては、同一のＲＮＡ配列が横方向と縦方向に配置される。行列の要素（ｉ，ｊ）は、ｉ番目の塩基とｊ番目の塩基が塩基対を形成する確率を表す。この確率は、エネルギが最小になる構造を求める計算によって得られる。図７では、確率の大きさが、点の大きさで表されている。一つのＲＮＡ配列が両方向に配置されているので、図示のような半分の領域（三角形領域）にて、全塩基対の確率が表される。
【００５１】
図７の塩基対確率行列において、ステムは、確率が大きい複数の要素が、図示のように右上がりの４５度方向に並んだ領域である。
【００５２】
ステム候補抽出部２７は、各々のＲＮＡ配列データから、図７に示されるような塩基対確率行列を生成する。本実施の形態では、ＭｃＣａｓｋｉｌｌのアルゴリズムが好適に用いられる。そして、ステム候補抽出部２７は、塩基対確率行列から、所定値ｐ以上の確率を持つ要素が所定個数ｎ以上連続する領域を抽出する。この領域が、ステム候補として特定され、ステム候補記憶部２９に記憶される。
【００５３】
さらに、ステム候補抽出部２７は、ステム候補における全要素の確率の平均を求める。平均値は０から１の間の値になる。この平均値は、ステム候補のスコアとしてステム候補記憶部２９に記憶される。このスコアは、後述のステム候補間の類似性の判断に用いられる。
【００５４】
以上にステム候補抽出処理の好適な例を説明した。ステム候補抽出処理は上記に限定されない。より簡単な例としては、既知のステム配列が、ＲＮＡ配列から探索され、ステム候補として特定されてよい。ステムを構成する２つの部分配列が探索される。既知のステムの配列は、過去の研究で得られた既知の２次構造から求められてよい。
【００５５】
「ステムグラフの生成」
図６のグラフ生成部３１は、上述したように、各ＲＮＡ配列データから抽出されたステム候補の情報を基に、各ＲＮＡ配列に対応するステムグラフを生成する処理を行う。
【００５６】
図８および図９は、ステムグラフの例を示している。図８ではステムグラフが確率塩基対行列の上に描かれており、図９ではステムグラフが単独で描かれている。図示のように、ステムグラフでは、各ステム候補が頂点である。図の例では、９個のステム候補が頂点になっている。そして、ステム候補間が辺で結ばれる。
【００５７】
本実施の形態では、ステムグラフがラベル付き有向グラフであり、グラフの頂点および辺にはラベルが付与される。各頂点および各辺には、それらを識別するためのユニークなラベルが付与される。さらに、各辺には、下記の２つの情報が付与される。
【００５８】
（１）向き：ステム候補間の位置関係を表す向きである。図８では、辺の向きが矢印で示されている。辺の向きは、配列上で５’側（一般の直線配置で左側）のステム候補から３’側（一般の直線配置で右側）のステム候補へ向くように設定される。ここで、ステム候補位置は、各ステム候補の５’側のステムパーツの位置で特定される。
【００５９】
図８（および図７）では、横方向の配置にて、５’側が左であり、３’側が右である。そして、縦方向の配置では、５’側が上であり、３’側が下である。この場合、辺の向きは、縦の配置の５’側のステム候補から３’側のステム候補へ向くように付けられている。要するに、辺の矢印は、図８の上側のステム候補から下側のステム候補を向いている。
【００６０】
（２）接続関係：これは、ステム候補間の接続関係が３つのタイプのいずれに属するかの情報である。図１０に示されるように、３つのタイプとは、並列（Juxtaposed）、埋込み（Embedded）、重複（Overlapped）である。これらは、矛盾のない関係（consistent relation）である。図９のグラフは、並列（“Ｊ”）と埋込み（“Ｅ”）の辺を含んでいる。
【００６１】
なお、グラフ生成部３１は、上記３つのタイプいずれにも該当しないステム候補対を辺での接続対象から除外する。これにより、矛盾のある関係（inconsistent relation）が除外される。例えば、ステム候補＃２、＃８は、上記の接続タイプに該当せず、したがって、辺で結ばれていない。
【００６２】
上記の例において、＃２、＃８のステム候補では、ステムの片側パーツが共通している。したがって、これらのステム候補の両方共が本当のステムである可能性は無い。このようなステム候補対が辺で結ばれないので、妥当なグラフが形成される。
【００６３】
以上、グラフ生成部３１により生成されるステムグラフ（ラベル付き有向グラフ）について説明した。グラフ生成部３１は、ステム候補抽出部２７により抽出されたステム候補を頂点に設定し、頂点間の辺を設定し、頂点および辺にラベルを付与する処理を行い、これにより上記のグラフが生成される。
【００６４】
グラフ生成部３１は、各々のＲＮＡ配列に対して上記のようなステムグラフを生成する。したがって、グラフ生成部３１は、入力されたＲＮＡ配列の数と同じ枚数のグラフを生成する。これらグラフがグラフ記憶部３３に記憶される。
【００６５】
「分類データの生成」
図６の分類データ生成部３５は、上述したように、ステム候補群を分類する分類データを生成する処理を行う。本実施の形態では、図１１に示されるように、分類データが、階層型でツリー型のタクソノミデータである。以下、分類データの生成処理について、より詳細に説明する。
【００６６】
上述のステムグラフ生成処理は、一本のＲＮＡ配列から一つのステムグラフを生成する。一方、この分類処理は、複数のＲＮＡ配列から抽出された全部のステム候補を分類して一つの分類データを生成する。
【００６７】
ステム候補の分類は、ステム候補間の類似性に基づいて行われる。ステム候補の全組合わせの類似性が求められ、類似性を使って分類が行われる。類似性のパラメータは、典型的には、ステム候補同士の配列の相同性である。本実施の形態では、ステム候補対の類似性が、上記の配列相同性を含む４つの類似性によって定義される。（１）ステム候補同士の配列相同性、（２）各ステム候補のスコア、（３）ループの距離の類似性、（４）配列内での位置の類似性。
【００６８】
上記において、（２）のスコアは、ステム候補抽出時に算出された確率である。より詳細には、スコアは、ステム候補の塩基対形成確率の平均である。本実施の形態は、２つのステム候補のスコアの和を利用している。本実施の形態は、スコアの和が大きいほど２つのステム候補の類似度を大きいと考え、スコアの和が小さいほど２つのステム候補の類似度が小さい（非類似度が大きい）と考える。ここで、本発明は、スコアの和が大きいほど、２つのステム候補の両方共が実際のステムである可能性が高いことに着目している。このことを考慮し、本発明は、両方のステム候補が実際のステムである可能性が高いほど類似性が高いと決めている。（３）のループの距離は、ステムを構成する２つのパーツ間の距離（塩基数）である。（４）の位置は、各ステム候補が属するＲＮＡ配列内での位置である。位置は、配列端からの距離（塩基数）で表されてよい。
【００６９】
４つの要素的な類似性パラメータを計算するために、ＲＮＡ配列のデータから、各ステム候補が有する配列、スコア、ループ距離、配列内位置の４つのデータが求められる（スコアは既に説明したように塩基対確率から算出されている）。各データから一組のステム候補の類似性が計算され、したがって、４つのデータから４つの類似性パラメータが計算され、それらが合成されて、一組のステム候補の総合的な類似性パラメータが計算される。このような類似性パラメータが、任意の組のステム候補に対して計算される。類似性パラメータの算出処理は、後述にてさらに詳しく説明されるが、本実施の形態の実現例では、２つのステム候補の違いが大きくなるほど値が大きくなるような類似性パラメータが使われてよい。つまり、類似性パラメータが、非類似度で実現される。
【００７０】
図１１は、上記のような類似性に基づいて生成された分類データを示している。分類データ生成部３５は、頂点間の類似性に基づいたクラスタリングを行い、これにより、図示のようなツリー型のタクソノミデータを生成する。図１１において、左の図は、ステム候補の階層的クラスタリングによって生成される系統樹（dendrogram）である。クラスタリングのためのステム候補間の類似性（similarity）は、既述の通り、（１）配列相同性（sequence similarity）、（２）候補のスコア（score of candidate）、（３）ループ距離（loop distance）、（４）配列内位置（position in sequence）のミックス（mixture）によって定義される。右側の図は、系統樹（dendrogram）から構築されたステム候補のラベルのタクソノミである。
【００７１】
図１１のタクソノミデータでは、最下層の頂点１〜７は、個々のステム候補と対応する。上位層の頂点（分類、ラベル）は、下位層で類似する複数の頂点を代表する。例えば、最下層の３つの頂点１、２、３が類似するので、第２層では一つの頂点８に分類される。分類データ生成部３５は、このような分類データを生成して、分類データ記憶部３７に記憶する。
【００７２】
上記より明らかなように、分類データでは、下位層よりも上位層にて類似範囲が広い。すなわち、下位層よりも上位層にて、一般化の程度が大きい。そこで、本実施の形態では、一般化の程度を表現するために、図１１に示されるように、上位層へ行くほど値が大きくなるように一般化コストが定義される。ｉ層の一般化コストは、１−ｎ（ｉ）／Ｎで表される。ここで、Ｎは、最下層の頂点数（ステム候補の総数）である。ｎ（ｉ）は、階層ｉに属する頂点数である。一般化コストは下記のグラフ解析処理にて用いられることになる。
【００７３】
「グラフ解析処理」
図６のグラフ解析部３９は、上述したように、グラフ生成部３１によって生成された複数のステムグラフに頻出する部分グラフを抽出する処理を行う。ここでは、類似する部分グラフが抽出される。類似する部分グラフとは、グラフ形状が類似し、かつ、対応する頂点のステム候補が類似するグラフである。部分グラフはステム候補のパターンに相当するので、以下、必要に応じて、部分グラフをステムパターンと呼び、抽出される頻出部分グラフを頻出ステムパターンという。
【００７４】
より詳細には、グラフ解析部３９は、ステムグラフでの出現の頻度が所定しきい以上のステムパターン（部分グラフ）を抽出する処理を行う。この頻度は、典型的には、後述するように、「ステムグラフの総数」に対する、「特定の類似するステムパターンを含むステムグラフの数」の比、で表される。
【００７５】
頻出ステムパターンの抽出では、上記のように類似性が考慮される。したがって、抽出される一つ頻出ステムパターンは、実際には、複数のステムパターンの集合になってよい。
【００７６】
図１２は、グラフ解析の原理を示している。図１２は、２つのステムグラフを示している。互いに類似するステムパターンが２つのステムグラフから抽出されている。図１２の例では、ステムパターンは、３つの頂点とそれらを結ぶ３つの辺で構成されている。
【００７７】
ステムパターン（部分グラフ）の類似は、グラフ形状の類似性と、グラフ内の頂点の類似性によって決まる。本実施の形態では、以下の３条件が満たされるとき、２つの部分グラフのグラフ形状が類似する。
（１）頂点の数が同じである。
（２）対応する辺の向きが同じである。
（３）対応する辺の接続関係が同じである。
【００７８】
なお、本実施の形態では、後述するように完全（Ｃｌｉｑｕｅ）グラフが抽出される。したがって、類似する部分グラフにおいては、頂点の数が同じであり、それらの任意の２つの頂点間が辺で結ばれ、かつ、各辺のラベルが（２）（３）の条件を満たす。
【００７９】
次に、図１３を参照して、頂点間の類似について説明する。頂点間の類似は、分類データを用いて判断することができる。分類データにおいて同じグループに属する頂点を類似と判断する。
【００８０】
図１３は、２つのステムパターンの例を示している。図において、対応する２組の頂点は同じであるが、対応する１組の頂点が異なっている。しかし、これら頂点が、図１１のタクソノミにおいて、１つ上の階層では同一分類に属するとする。この場合、対応頂点が類似し、そして、２つのステムパターンが類似する。
【００８１】
このようにして、下位層での比較では対応頂点が異なる分類に属しても、上位層の比較で対応頂点が同じ分類に属していれば、対応頂点が類似する。グラフ解析処理では、順次階層を上に変更して、頂点間の類似が判断される。
【００８２】
しかし、階層を高くしすぎると、類似範囲が広くなり過ぎる。例えば、最上層では、すべての頂点が類似し、妥当な比較が困難になる。そこで、本実施の形態では、類似判断における階層の高さが制限される。この制限のために、前述の一般化コストが用いられる。
【００８３】
一般化コストは、図１１に示したように、上位層へ行くほど大きくなる。前述の説明を繰り返すと、ｉ層の一般化コストは、１−ｎ（ｉ）／Ｎで表され、Ｎは、最下層の頂点数（ステム候補の総数）であり、ｎ（ｉ）は、階層ｉに属する頂点数である。
【００８４】
図１４は、ステムパターンの一般化コストを示している。ステムパターンの一般化コストは、各頂点の一般化コストの平均である。グラフ解析処理では、ステムパターンの最大一般化コストが指定され、一般化コストが最大一般化コスト以下になるように頻出ステムパターンが抽出される。例えば、図１３の一般化を行うと、一般化コストが最大値をオーバーしたとする。この場合、図１３の２つのステムパターンは類似しない。
【００８５】
上述の原理に基づきグラフ解析の問題を定式化すると、以下のようになる。
（１）ラベル付き有向グラフの集合、（２）ラベルの一般化コスト付きタクソノミ、（３）最小支持度（ｍｉｎｓｕｐ）、（４）最大一般化コスト（ｍａｘｃｏｓｔ）が与えられた際に、以下を満たすステムパターンをすべて抽出する。
Ａ）支持度が最小支持度以上
Ｂ）完全グラフ（Ｃｉｑｕｅ）
Ｃ）一般化コストが最大一般化コスト以下
Ｄ）クローズドパターン（Ｃｌｏｓｅｄ Ｐａｔｔｅｒｎ）
【００８６】
支持度は、図１５に示される通り、頻出の程度を表す。図において、一つのステムパターンが、３つのステムグラフのうちの２つに存在する。この場合、該当パターンの支持度は、２／３である。完全グラフとは、各頂点がすべての頂点と辺で結ばれたグラフである。ステムパターンがＲＮＡ配列の一部分であれば、必ずステムパターンが完全グラフになる。一般化コストは、既に説明した通りである。クローズドパターンは、「自分を真に含むパターンであって、自分と同じ支持度を持つようなパターンが存在しない」パターンである。
【００８７】
次に、図１６を参照すると、上述してきたグラフ解析処理は、パターン探索アルゴリズムにより好適に実現される。より詳細には、グラフ解析機能は、図１６のＤＦＳ ｃｏｄｅ ｔｒｅｅの探索アルゴリズムにより実現される。この探索アルゴリズムは、少しずつパターンを変えながら、ツリーを深さ方向に探索し、各種の候補パターンを数え上げる。
【００８８】
本実施の形態では、パターン探索アルゴリズムが、上述のグラフ解析処理を実行する。すなわち、パターンの形状が変更される。また、タクソノミに基づいて一般化の程度が変更される。そして、各種のパターンが複数のステムグラフから数えられる。そして、上述の条件を満たす頻出ステムパターンが求められる。
【００８９】
パターン探索のアルゴリズムは、効率よく完全に多様なパターンが数えられるように構成されている。さらに、本実施の形態は、上述のパターン抽出の条件も考慮して下記の制限された処理を行い、さらなる効率的を実現する。（１）支持度の逆単調性による枝狩り、（２）Ｃｌｉｑｕｅ制約によりＤＦＳ ｃｏｄｅ ｔｒｅｅの子要素を限定、（３）最大一般化コストの制約を用いた枝狩り、（４）過度に一般化されたパターンを除くための枝狩り。枝狩り（pruning）とは、ツリー上の部分木を探索対象から除外することをいう。これらの処理については、後にさらに詳細に説明する。
【００９０】
以上に頻出ステムパターンを抽出するグラフ解析処理を説明した。グラフ解析部３９は、上述の処理を行うことによって頻出ステムパターンを抽出する。さらに、２次構造生データ成部４７は、抽出された頻出ステムパターンに対応する２次構造データを生成する。これら頻出ステムパターンと対応する２次構造データが出力部４５から出力される。
【００９１】
ここで、グラフ解析部３９は、上述の条件に該当する全部の頻出ステムパターンを抽出する。したがって、グラフ解析部３９は、通常は複数の頻出ステムパターンを抽出する。さらに、類似性が考慮されているので、一つの頻出ステムパターンは、複数のステムパターンに対応することもある。２次構造データは、各々のステムパターン（部分グラフ）から作られてよい。これらデータが、出力されてよい。
【００９２】
以上に、本実施の形態のＲＮＡ配列情報処理装置、方法およびプログラムについて詳細に説明した。以下、本発明の各種態様の利点をまとめて述べる。本発明は、複数のＲＮＡ配列データから複数のステムグラフをそれぞれ生成し、それら複数のステムグラフから頻出ステムパターンを抽出する。頻出ステムパターンは、ＲＮＡ２次構造モチーフを表している。したがって、本発明は、ＲＮＡ配列群から２次構造モチーフを抽出することができる。
【００９３】
本発明の情報処理が、機能性ＲＮＡのファミリーが特定されていないＲＮＡ配列群に適用されたとする。この場合、頻出ステムパターンが抽出されると同時に、頻出ステムパターンを含むＲＮＡ配列（ステムグラフ）も分かる。すなわち、２次構造モチーフが抽出されると同時に、２次構造モチーフを含むファミリーを同定することができる。また、本発明は、既に同定されている機能ファミリーの配列群に適用されてもよく、この場合にも２次構造モチーフが好適に抽出される。
【００９４】
また、上述にて説明したように、グラフ生成部は、ＲＮＡ配列上での各ステム候補対の位置関係に応じた向きを、各ステム候補対を結ぶ辺のラベルに付与してよい。そして、グラフ解析部は、複数のステムグラフから、対応する辺の向きが同じ部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００９５】
また、グラフ生成部は、各ステム候補対の接続関係が並列、埋込み、重複のいずれかに属するかの情報を、各ステム候補対を結ぶ辺のラベルに付与してよい。グラフ解析部は、複数のステムグラフから、対応する辺の接続関係が同じ部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００９６】
また、グラフ生成部は、並列、埋込みおよび重複のいずれにも該当しないステム候補対を辺での接続対象から除外してよい。これにより、不適当な部分グラフの抽出を回避して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００９７】
また、グラフ生成部は、各頂点が部分グラフ内のすべての他の頂点と辺で結ばれる完全部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００９８】
また、分類データ生成部は、複数のステムグラフに含まれる複数のステム候補を類似性に基づいて分類する分類データを生成してよい。グラフ解析部は、複数のステムグラフから、対応する頂点のステム候補が同じ分類に属する部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出できる。
【００９９】
また、分類データ生成部は、分類データとして、複数のステム候補を、類似範囲の広さが下位層から上位層へ向かって増大するように階層的にクラスタリングを行ったタクソノミデータを生成してよい。グラフ解析部は、タクソノミデータに基づき、対応する頂点のステム候補が下位層では異なる分類に属しても上位層では同一分類に属する部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【０１００】
また、最大一般化コスト入力部が、タクソノミデータにて階層に応じて増大する一般化コストの最大許容値である最大一般化コストを入力してよい。グラフ解析部は、最大一般化コスト以下の一般化コストを有する部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【０１０１】
また、分類データ生成部は、ステム候補対の類似性を表す類似性パラメータを、ステム候補対の配列相同性、ステム候補により形成されるループの距離の類似性、および、ＲＮＡ配列内でのステム候補の位置の類似性の少なくとも一つに応じて求めてよい。また、分類データ生成部は、二次構造エネルギに基づいたステム候補の塩基対形成確率に応じて類似性パラメータを求めてよく、このとき、２つのステム候補の塩基対形成確率の和が評価されてよく、そして、和の値が大きいほど類似度が高いと判断されてよい。上記の例では、これら全部が加味されている。これにより、ステム候補である頂点間の類似性を適切に判断して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。類似性判断の基礎になるパラメータは、ステムグラフの頂点のラベルに付与されてよい。
【０１０２】
また、最小支持度入力部が、複数のステムグラフにおける部分グラフの支持度の最小許容値である最小支持度を入力してよい。グラフ解析部は、最小支持度以上の支持度を有する部分グラフを抽出してよい。支持度は頻度（頻出の程度）を表す。最小支持度以上の支持度を有する部分グラフを抽出することにより、ＲＮＡ配列群に頻出するステムパターンを適切に抽出できる。
【０１０３】
また、ステム候補抽出部は、分子構造のエネルギに基づいてＲＮＡ配列上の任意の２つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域をステム候補として抽出してよい。これにより、ステム候補を適切に抽出することができる。
【０１０４】
また、上述の実施の形態では、頂点間のタクソノミが考慮されて、類似部分グラフ（頻出ステムパターン）が抽出された。本発明のさらなる応用例では、辺のタクソノミが考慮されて、類似部分グラフ（頻出ステムパターン）が抽出されてよい。この場合、辺を特徴づけるパラメータを用いて、辺の類似性を基に、辺のタクソノミが生成される。辺のタクソノミが、頂点のタクソノミと同様に処理されて、辺が類似する部分グラフが抽出される。
【０１０５】
以下、上述の発明に関する研究について詳細に説明する。以下では、上述したラベル付き有向グラフ、タクソノミ、グラフ解析なども詳細に説明される。なお、参考文献は、（文献＋番号）と表記し、文献のリストを最後に記載する。
【０１０６】
「１．はじめに」
この記述の構成は、以下の通りである。セクション２は、グラフ理論の基本的な用語を定義した後に、ＲＮＡのグラフ表現の方法および今回解決すべき問題のグラフマイニングによる定式化、さらにはそれを効率よく解く為の理論およびアルゴリズムについて詳細に説明する。セクション３は、実装方法について述べる。
【０１０７】
「２．手法」
「２．１ グラフ理論・グラフマイニングからの準備」
本文章では、特に断らない限り、グラフとは多重辺や自己ループ辺を許さないラベル付き有向グラフ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 ) で定義されるラベルを含まないグラフである。
【０１０８】
「定義２．１（部分グラフ）」
グラフGが与えられているものとする。グラフGsがGの部分グラフ（subgraph）である（Gs⊆G と書く）とは、写像φ：V ( Gs )→V ( G ) が存在して
（１）任意のv∈V ( Gs ) に対してlb ( v ) = lb (φ( v ) )
（２）任意の( vi, vj )∈E ( Gs ) に対してlb ( vi, vj ) = lb (φ( vi ),φ( vj ) )
を満たすことである。
Srikantら（文献１）は、アイテムセットにおける個々のアイテムの関係をTxonomyとして表現した。さらに、Inokuchi（文献２）は、グラフのラベルにTaxonomyを考えることを提案している。ここではこららを発展させ、ラベル間の関係と各ラベルの一般化コストを考慮した「一般化コスト付きTaxonomy」を定義する。
【０１０９】
「定義２．２（一般化コスト付きTaxonomy）」
ラベルの集合LSが与えられているものとする。このとき、一般化コスト付きTaxonomy（Taxonomy with generalization cost） Tとは、頂点がLSのDAG（directed acyclic graph）で、その各頂点v∈LS に対して一般化コストc ( v )∈R+ が定義されているものである。
（注意２．１) 関係A→Bは、B is a A（ラベルAの方がラベルBよりも一般化されている、逆に言うとラベルBの方がラベルAよりも特殊化されている）を意味する。TaxonomyをforestではなくDAGでモデル化したのは、multiple taxonomiesを表現することを可能にするためである（文献１）。また、c ( A )、c ( B )は、それぞれ、ラベルA、Bの一般化に対するコストを表すが、通常の場合、上位概念ほど一般化のコストが大きいと考えられるので、c ( B )＜c ( A ) である。
今後は簡単のため、一般化コスト付きTaxonomyを単にTaxonomyと呼ぶことにする。Taxonomyの頂点xに対して、xまたはxの祖先の集合（xから有向辺を逆にたどっていって到達できる全ての頂点の集合）をτT ( x ) と表すことにする。グラフとTaxonomyが与えられた際の部分グラフを以下のように定義する。
【０１１０】
「定義２．３（Taxonomyが与えられた下での部分グラフ（文献２））」
Taxonomy TとグラフG、Gsが与えられているものとする。Gsが、GのTaxonomy Tが与えられた下での部分グラフ（subgraph under Taxonomy T）であるとき、
【数１】
とかく。これは、写像φ：V ( Gs )→V ( G ) が存在して、
（１）任意のv∈V ( Gs ) に対してlb ( v )∈τT ( lb (φ( v ) ) )
（２）任意の( vi, vj )∈E ( Gs )に対してlb ( vi, vj )∈τT ( lb (φ( vi ),φ( vj ) ) )
を満たすことである。今後は、簡単のため、Taxonomy Tが明らかな場合には、添え字Tは省略する。
（注意２．２） 定義より明らかに
【数２】
である（逆は成立しない）。つまり、Taxonomyが与えられた下での部分グラフの定義は、通常の部分グラフの定義を弱めたものとなっている。
【０１１１】
「定義２．４（Clique）」
グラフがクリーク（Clique）であるとは、任意の頂点間に辺が存在することである。
【０１１２】
「２．２ グラフとTaxonomyを用いたＲＮＡ配列集合のモデル化」
本節では、ＲＮＡ配列の集合全体をラベル付有向グラフとTaxonomyを用いてモデル化を行う方法について記述する。
近年、ステムやループなどのＲＮＡ２次構造の構成要素を一つの単位として積極的に利用したＲＮＡ解析手法が一定の成功を納めている。例えば、Scarna（文献３）は固定長のステムのアラインメントを良く考えられたダイナミックプログラミングにより定式化し、２本のＲＮＡ配列のアラインメントおよびその共通２次構造の予測を高速で行う。RNAscf（文献４）は、複数配列からステム候補のアラインメントを繰り返し行うことにより、共通の２次構造の予測を行う。また、Carnac（文献５）は、２本あるいは３本以上のＲＮＡ配列群から、可能性のあるステム候補を抽出し、cofoldingと呼ばれる手法を用いて、各ＲＮＡ配列の２次構造を予測する。comRNA（文献６）は、グラフ理論におけるClique探索手法を利用して、整列していないＲＮＡ配列群からその共通のモチーフを発見する手法を提案している。これらのステムベースの手法は、ヒューリスティックな部分を多く含んでいるが、精度と計算量のバランスが取れた実用的な手法が多い。本手法でも、これらの手法と同様にステムの候補を積極的に利用したモデル化を行う。
また、単一のＲＮＡ配列は、２次構造を一つに決めれば木構造やRAG（文献７）を用いて表現することが可能であるが、ここでは各ＲＮＡ配列の２次構造自体をモデル化するのではなく、ＲＮＡ配列から得られる可能性のあるステムの候補をすべて用いてＲＮＡのモデル化を行う。その手順は以下の通りである。
（１）各ＲＮＡ配列の塩基対確率行列からステム候補を抽出しグラフの頂点とする。
（２）ステム候補の類似度に基づいた階層型クラスタリングの樹形図から頂点ラベルに対するTaxonomyを構築する。
（３）consistentなステム候補間を有向辺で結びその関係（Juxtaposed, Embedded, Overlapped）に応じて辺にラベルを付与する。
以下に各ステップについてもう少し詳細に説明を行う。
【０１１３】
「２．２．１ グラフの頂点」
McCaskillのアルゴリズム（文献８）を用いてＲＮＡ配列から塩基対確率行列（base pairing probability matrix）を計算する。ここで、McCaskillのアルゴリズムにより計算される塩基対確率行列の( i, j ) 要素は、ｉ番目の塩基とｊ番目の塩基が塩基対を形成する確率を表す。計算された塩基対確率行列から、塩基対を形成する確率がｐ以上で、ｎ個以上の連続する塩基対集合の極大集合をステム候補（Stem candidate）として抽出する（文献３）。なお、現在の実装では、塩基対単位でＭ個のギャップは許容している。ただし、バルジが入るようなステム候補は考えることが出来ない（ステム候補の数が増えるため許容していない）。
さらにステム候補には、そのステム候補を形成する塩基対の確率の平均をスコアとして付与する（このスコアは０以上１以下の実数である）。本手法では、このステム候補をグラフの頂点とする。
【０１１４】
「２．２．２ 頂点ラベルのTaxonomyの構築」
頂点ラベルのTaxonomyを構築するために、セクション2.2.1の２つの頂点（ステム候補）間の非類似度を以下のように定める。ステム候補Sに対して、p ( S ) で５’側ステムの開始位置、d ( S ) でループの距離、r ( S ) で３’側ステムの開始位置、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置換行列（文献９）を用いたステムS1とステムS2のSmith Watermanアラインメント（文献１０）のスコアである。また、wi はΣ i = 1, 2, 3, 4 wi = 1, wi≧0 を満たす重みパラメタである。
セクション２．２．１の方法で抽出されたステム候補全てに対して上述の非類似度に基づき階層型クラスタリングを行う。この際得られる樹形図を用いてTaxonomyを構築する。すなわち、クラス間の距離の列をd = [ dk ]Nk=1 ( d1＜d2＜・・・＜dN ) とする際に、距離がdk 以下のクラスタに対して同一のラベルを付与することによりTaxonomyを構築する。従って、今の場合Taxonomyは階層構造になっている。ここで、Taxonomyの第ｎ階層に属するラベルの一般化コストを、「１−（第ｎ階層のラベル数）／（頂点数）」で与える。
【０１１５】
「２．２．３ グラフの辺」
２つのステム候補間の関係は次のように分類できる。
「性質２．１（文献１１、文献３）」
セクション２．２．１で抽出した２つのステム候補S1、S2の位置関係は、ステム候補の配列上での位置をS1 = ( [ ls1, le1 ] , [ rs1, re1 ] ) 、S2 = ( [ ls2, le2 ] , [ rs2, re2 ] ) (lsk は５’側のステムの開始位置、lek は５’側のステムの終了位置、rsk は３’側のステムの開始位置、rek は３’側のステムの終了位置)とするときに、以下のいずれかが成立する。
【数４】
（１）、（２）、（３）のいずれかの関係である場合に、２つのステム候補S1、S2の関係はconsistentであると言う。
本研究では、２つのステム候補S1 = ( [ ls1, le1 ] , [ rs1, re1 ] ) , S2 = ( [ ls2, le2 ] , [ rs2, re2 ] ) がls1＜ls2 かつ（１）、（２）、（３）のいずれかの関係であるならば、S1からS2の向きに有向辺を付与し、辺にはその関係に応じて異なるラベルを付与することとする。
【０１１６】
「２．２．４ モデル化の特徴」
このようにモデル化を行った場合、明らかに次の著しい性質が成立する。この性質は、後にアルゴリズムを構築する際に非常に役に立つ。
「性質２．２」
２次構造として成立可能なステム候補の集合は、上述の方法でＲＮＡをグラフ化した際に、Cliqueな部分グラフでなければならない。
例１：図７は、ｔＲＮＡのステムグラフである。図７では、例えば、頂点の組み合わせ（1, 2, 8, 9）、（1, 2, 4, 5, 9）などがＲＮＡの２次構造として正当なステム候補のセットである。これに対して、ステム候補の集合（1, 3, 5）に対応する２次構造は存在しない。
我々のモデル化の手法では、ＲＮＡ配列集合の個々の配列に対してその可能性のあるステム候補を全て考慮したラベル付有向グラフを構築する点および頂点のラベルにはTaxonomyを考慮する点の２点を新しく提案している。本セクションの最初にも述べたとおり、ＲＮＡの２次構造を木構造やグラフでモデル化する方法はすでに提案されているが、本手法のようなモデル化の方法は今までには考えられてこなかった。従って、上記のモデル化手法は本論文の貢献のひとつであるといえる。
【０１１７】
「２．３ グラフマイニングとしての定式化」
我々が現在解決しようとしていＲＮＡの問題は以下のように述べられる。
「問題１」 ＲＮＡ配列集合に頻出するステムのパターンを全て抽出する。同時に各ステムパターンに対応するＲＮＡ配列のステムの集合（ＲＮＡ配列の２次構造）を特定する。
本セクションでは、上記の問題をグラフマイニングとして定式化を行う。まず、次の定義はグラフマイニング分野では非常に基本的なものである。
【０１１８】
「定義２．５（支持度（文献２））」
グラフの集合GS = [ G1,・・・, GN ] とTaxonomy TとグラフPに対して、
【数５】
をグラフPの支持度（support）と呼ぶ。支持度が０より大きいグラフをパターン（pattern）と呼ぶ。また、支持度が与えられたminsupより大きいパターンを頻出パターン（Frequent pattern）と呼ぶ。
前セクションの結果およびこの定義を用いて問題１を言い換えると次のようになる。
【０１１９】
「問題２」 グラフ集合GSとTaxonomy Tおよび支持度minsupが与えられている際に、Cliqueなパターンで支持度がminsup以上のものをすべて導出する。同時に、導出されたパターンに対応する各グラフの部分グラフを特定する。
一般に、与えられたグラフ集合から頻出パターン（Cliqueなパターンとは限らない）を完全に抽出する問題はグラフマイニングの問題として近年盛んに研究がなされている（FSSM（文献１２）、FSG（文献１３）、AGM（文献１４、１５）、AcGM（文献１６）、gSpan（文献１７））。ラベルにTaxonomyを用いた場合の一般的なグラフマイニングは（文献２）で提案された。今回は、ベースとなる一般のグラフマイニングアルゴリズムにはgSpanアルゴリズムを用いて、頂点ラベルにTaxonomyを考慮できるように変更を行った。また、後で述べる通り、抽出するパターンがCliqueなパターンであること（性質）を利用して探索の効率化を行っている。また、問題１を完全に解くことも可能であるが、本研究ではさらになる探索の効率化を行うために抽出されるパターンにいくつかの制約を課すことにする。
次に定義される過度に一般化されたパターンは、ラベルにTaxonomyを考慮した場合に出現するパターンであるがパターンとしての有用性は低い。
【０１２０】
「定義２．６（一般化パターン、過度に一般化されたパターン（文献２））」
パターンP1とP2のトポロジーが同型であるとする。
【数６】
であるとき、P1はP2の一般化パターン（generalized pattern）と呼ぶ。また、P2が存在して、
【数７】
を満たす場合、P1は過度に一般化されたパターン（over-generalized pattern）と呼ぶ。
以下は、Yanら（文献１８）により提案されたclosed patternの定義をTaxonomyを考慮した場合に拡張したものである。closed patternでないパターンもパターンとしての有用性は低い。
【０１２１】
「定義２．７（closed pattern（文献１８））」
グラフの集合GS = [ G1, G2,・・・, Gn ] とTxonomy Tが与えられているものとする。このとき、パターンPがclosed patternであるとは、
【数８】
を満たすパターンP' が存在しないことを言う。
（注意２．３） Yanら（文献１８）は、通常の部分グラフ（定義２．１）の意味でclosed patternを定義したが、ここではTaxonomyを用いた部分グラフ（定義２．３）の意味でclosed patternを定義している。定義より、この意味でClosedなパターンは、定義２．６で定義される過度に一般化された（over-generalized）パターンではない。
Taxonomyを考えることにより、柔軟なパターンの抽出が可能になる一方で、抽出されるパターンが増加することが懸念される。しかしながら、Taxonomyの上位のラベルばかりで構成されるパターンは、たとえ頻出していたとしてもあまり重要でない可能性が高い。このようなパターンがTaxonomyの上位のラベルばかりで構成されているかどうかを判定するために、パターンの一般化コストと呼ばれる概念を新たに定義する。
【０１２２】
「定義２．８（パターンの一般化コスト）」
グラフGとTaxonomy Tが与えられているものとする。このときパターンPの一般化コスト（generalization cost）：cost ( P ) を、
【数９】
と定義する。言い換えれば、パターンの一般化コストは、パターンを構成するラベルのコストの平均である。
以上の定義をもとに、最終的に我々が解くべきグラフマイニングの問題は以下となる。
【０１２３】
「問題３」 グラフの集合GS = [ G1, G2,・・・, Gn ] 、Taxonomy T、最小支持度minsup、最大一般化コストmaxcostが与えられた際に、以下の条件を満たすパターンを完全に抽出する。
（１）支持度がminsup以上（定義２．５を参照）
（２）Clique（定義２．４を参照）
（３）Closed patterns（定義２．７を参照）
（４）一般化コストがmaxcost以下（定義２．８を参照）
さらに、抽出されたパターンに対応する各グラフの部分グラフを全て特定する。
【０１２４】
「２．４ 理論」
本セクションでは、問題３を解くためのグラフマイニングアルゴリズムの理論的な部分について、出来る限りself-containedな形で記述を行う。以下の定義はグラフアルゴリズムの分野では基本的なものである。
【０１２５】
「定義２．９（DFS木、DFS添え字付け、前向きの辺、後ろ向きの辺（文献１９））」
本定義においてグラフは連結グラフであるとする。
（１）深さ優先木（DFS木、DFS Tree）：グラフを深さ優先探索した際に得られる木構造。
（２）DFS添え字付け（DFS Subscripting）：グラフの頂点にDFS木で探索される順番に従って番号付けをしたもの。またグラフGとDFS木Tに対してDFS subscriptingをGTと書く。ｉ番目の頂点をvi と表すとGT = [ vi ] と書ける。
（３）前向きの辺（Forward Edge）と後ろ向きの辺（Backward Edge）：グラフGと深さ優先木Tが与えられた際に、Gの辺の中でTに含まれるものを前向きの辺（Forward Edge）、含まれないものを後ろ向きの辺（Backward edge）と呼ぶ。前向きの辺を( vi, vj ) ( i＜j )、後ろ向きの辺を( vi, vj ) ( i＞j ) と表す。
（注意２．４） 開始頂点の選び方などにより、同一のグラフに対して複数の深さ優先木が存在する（すなわち複数のDFS Subscriptingが存在する）。
【０１２６】
「定義２．１０（文献２０）」
連結グラフ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 ] に対して順序関係を以下の通り定義する（これらはすべて半順序関係であることは容易に示せる）。
【数１０】
（注意２．５） DFS木Tを固定する限り、（１）の（ii）の条件は必要ない。ただし、（１）の（ii）の条件を入れることにより、グラフやそのDFS木が異なっている場合でも辺の比較が可能になる。
（注意２．６） 今後は特に誤解が無い限り辺( vi, vj ) を省略して ( i, j ) と書く。
この順序関係について以下の結果が成立する。
【０１２７】
「定理２．１（文献２０）」
グラフGとDFS木Tを固定したときに、定義２．１０の順序を合わせて定義されるEf, T∪Eb, T上の順序関係は、線形順序である。なお、集合( A,＜) が線形順序集合であるとは、（ｉ）∀a, b∈Aに対して、a＜bかつb＜cならばa＜c、かつ、（ｉｉ）∀a, b∈Aに対して、a＜bまたはb＜aが成り立つことである（一般的には「a＜a」と「a＜bかつb＜aならば、a = b」を条件に入れる場合も多いが、ここでは入れない）。
この定理により、グラフと深さ優先木を固定したときに、グラフに含まれる辺（前向きの辺または後ろ向きの辺のいずれか）には線形順序を与えることが出来る。さらに、頂点や辺のラベルを考慮して次のようにDFSコードと呼ばれる表現方法を定義する。
【０１２８】
「定義２．１１（DFSコード（文献２０））」
グラフGとDFS subscripting GTに対して辺を ( i, j, li, lj, l( i, j ) , d( i, j ) ) と表す。ここでli, lj はそれぞれｉ番目、ｊ番目の頂点のラベルを表す。l( i, j ) は辺( i, j )のラベルを表す。d( i, j ) は辺( i, j )の向き（ｉからｊの向きであれば＋１、ｊからｉの向きを−１とする）を表す。このとき、Gの辺を定理２．１の順序に従って並べた順列 [ ( i, j, li, lj, l( i, j ) , d( i, j ) ) ] をグラフGのDFSコード（DFS code）と呼び、code ( G, T )と書く。
（注意２．７） 上記のDFSコードの定義は原論文（文献２０）とは以下の点で異なる。
（１）グラフが有向グラフのため辺の方向に関する項d( i, j ) が存在する。
（２）ラベルの順序は、（fromlabel, tolabel, edgelabel, direction）の順番である（原論文では（fromlabel, edgelabel, tolabel）の順番）。これは、後に一般化コストによる枝狩りを行う際に重要になってくる。
DFSコードから辺をひとつ拡張して新しいDFSコードを作成する場合、定義２．１０の順序関係により任意に拡張を行うことは出来ず、以下の制限がある。
【０１２９】
「命題２．１（DFSコードの拡張の制限（文献２０））」
グラフGとDFS木Tが与えられているものとする。α = code ( G, T ) = ( a0, a1,・・・am ), ak = ( ik, jk ), ak+1 = ( ik+1, jk+1 ) とするとき以下が成立する。
（１）ak が前向きの辺かつak+1 が前向きの辺であるならば、
ik+1≦jk かつjk+1 = jk + 1
（２）ak が前向きの辺かつak+1 が後ろ向きの枝であるならば、
ik+1 = jk かつjk+1＜ik
（３）ak が後ろ向きの辺かつak+1 が前向きの辺であるならば、
ik+1≦ik かつjk+1 = ik + 1
（４）ak が後ろ向きの辺かつak+1 が後ろ向きの枝であるならば、
ik+1 = ik かつjk＜jk+1
（証明）DFS木の定義およびDFSコードの定義より明らかである。
【０１３０】
「定義２．１２（最右拡張（文献２０））」
パターンPとそのDFSコードに対して以下の拡張を最右拡張（Right-most extension）と呼ぶ。
（１）最右頂点から他の最右パスに含まれる頂点への辺の拡張（後ろ向きの拡張、backward extension）
（２）最右パスに含まれる頂点から、Pに含まれない新しい頂点への拡張（前向きの拡張、forward extension）
（注意２．８） 定義２．１２を使って性質２．１を言い換えれば、パターン（DFSコード）の拡張は最右拡張に限るということである。
任意の２つのDFS code（異なるグラフでもよい）の間に以下のようにして順序を与えることが可能である。
【０１３１】
「定義２．１３（DFS Lexicographic Order（文献２０））」
連結グラフGに対してZ ( G ) = [ code ( G, T )｜∀T：GのDFS木 ] と表す。さらにＺ = ∪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 に対して、α≦βとは、次の（１）または（２）が成立することである。
【数１３】
（注意２．９）
【数１４】
【０１３２】
「定義２．１４（最小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と呼ぶこともある。
【０１３３】
「定理２．２（文献２０）」
グラフGとG' が同型である必要十分条件はmin ( G ) = min ( G' ) となることである。
【０１３４】
「定義２．１５（DFSコードの親および子（文献２０））」
DFSコードα= ( a0, a1,・・・, am ) が与えられているとする。このとき妥当なDFSコードβ= ( a0, a1,・・・, am, b ) をDFS code αの子（child）、αはDFSコードβの親（parents）と呼ぶ（「性質２．１」を満たさなければならない）。αの子の集合をchildren ( α )と書く。
【０１３５】
「定義２．１６（DFS Code Tree（文献２））」
「親要素と子要素の関係が定義２．１５で与えられ、さらに同じ親の子要素の関係はDFS lexcographic orderで与えて得られるような、DFS codeを頂点とする木構造」を、「DFS code tree」と呼ぶ。
上で定義されているDFS code treeはDFSコードをノードとする順序木である。問題３はこの順序木の順序で探索を行っていくが、DFS code treeが全ての部分グラフを数え上げることが可能であることを保障するのが次の定理である。
【０１３６】
「定理２．３（DFS Code Tree Covering（文献２０））」
DFS Code Treeは全てのグラフの最小DFSコードを含む。
DFS Code Tree TとDFS code αが与えられたときに、Tにおけるαの祖先の集合をans ( α )、子孫の集合をdes ( α )と表す。
次の定理は、最小でないDFSコードを根とする部分木を枝狩りしても、全ての部分グラフを数え上げることが可能であることを保障している。
【０１３７】
「定理２．４（DFS Code Pruning（文献２０））」
グラフ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を含む。
（注意２．１０） 定理２．４により、DFS code treeの最小DFSコードでないDFS codeを根とする部分木は全て枝狩りを行っても全ての部分グラフを網羅可能である（完全性）。
定義より支持度に関して以下の単調性が成立することがわかる。これにより、支持度が与えられた最小支持度を下回ったパターンはそれ以上拡張する必要がないことが保障される。
【０１３８】
「命題２．２（支持度の逆単調性）」
【数１５】
ここまでの理論はYanらの貢献による。本研究ではYanらの理論をベースにラベルにTaxonomy情報およびその枝狩り手法（文献２）の統合を行う。つまり、定義２．１６で定義されるDFS code tree上を今回の制約を用いてさらに効率的に探索していく。さらに、cliqueなパターンのみを抽出することを利用した探索の効率化及びパターンの一般化コストによる枝狩り手法の提案を新たに行う。
導出パターンをCliqueなパターンに制限する場合には、DFS codeの子に対して「性質２．１」よりさらに強い制約を与えることが可能である。
【０１３９】
「命題２．３（抽出パターンの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コードを含む。
（１）ak が前向きの枝かつak+1 が前向きの枝であるならば、
k = 0 かつj0 = i1 = 1 かつj1 = 2
（２）ak が前向きの枝かつak+1 が後ろ向きの枝であるならば、
ik+1 = jk かつjk+1 = i0 ( = 0 )
（３）ak が後ろ向きの枝かつak+1 が前向きの枝であるならば、
ik = ik+1 かつjk+1 = ik +1かつik−2 = jk
（４）ak が後ろ向きの枝かつak+1 が後ろ向きの枝であるならば、
ik+1 = ik かつik+1 = ik
【０１４０】
（証明） （１）から（４）のいずれの条件も満たさない拡張によって得られられるDFSコードを根とする部分木にはCliqueなパターンを含まないことを示す。
（１）ak およびak+1 が前向きの枝であるとする。jk≠ik+1 とすると深さ優先木の定義から今後の拡張により後ろ向きの辺 ( jk+1, jk ) が拡張されることはない。よって jk = ik+1 としてよい。このとき、もしk≠0とするとik＞1 となり、定義２．１０を繰り返し使うと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 が前向きの枝であるならば、拡張を（１）に制限することにより探索されないパターンはすべてCliqueでないパターンとなる。
（２）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 ) は今後の辺の拡張によって得られることはない。よって、拡張を（２）に制限することにより探索されないパターンは全てCliqueなパターンではない。
（３）明らかに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 ) は存在しない。よって拡張を（３）に制限することにより探索されないパターンは全てCliqueなパターンではない。
（４）上と同様に（４）の制限を加えることにより探索されないパターンは全てCliqueなパターンではないことが示せる。
以上と定理２．３より題意が証明できた。
（注意２．１１） 以下ではDFS code treeとは子要素に上記の制限を加えたDFS code treeを意味するものとする。
一般にDFSコードαの最小性の判定は、αの最小DFSコードとαが等しいかどうかを比較することにより行われる。これは、グラフの同型性を判定することと実質的に等価であり多大な計算量を要する。しかしながら、抽出するパターンをCliqueなパターンに限る場合には、 以下の命題を用いることによりこのDFSコードの最小性の判定を回避することができる。
【０１４１】
「命題２．４（導出パターンの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コードは最小でない。
次の命題を用いると、一般化コストによる枝狩りを効率よく行うことが可能となる。
【０１４２】
「命題２．５（Cliqueと最大一般化コストの制限を用いた枝狩り）」
グラフの集合GSとTaxonomy Tが固定されているものとする。さらに、以下の仮定を置く。
（１）ラベルのTaxonomyは頂点にのみ存在し、辺ラベルの一般化コストは全て０である。
（２）GSの任意のラベルx∈V ( T ) とTaxonomy Tにおけるその任意の祖先yに対してx＜y を満たすラベル付けがなされている。
（３）ラベルx, yがx＜yを満たすならば、c ( x ) ≦ c ( y )
このとき、DFS code tree上で一般化コストがmaxcostより大きいDFS codeを根とする部分木を枝狩りした結果残るDFS code treeは、すべての一般化コストがmaxcost以下かつcliqueなパターンの最小DFSコードを含む。
（証明） 命題２．４により、パターンに新しい頂点ラベルが追加される（DFSコードを前向きの辺により拡張する）場合、追加される頂点のラベルはパターンのどの頂点ラベルとも等しいか、より大きい。このことと仮定を用いると容易に証明できる。
（注意２．１２） 前出の「分類データの生成」のセクションで説明された方法により構築されるタクソノミデータが上記の命題の条件を満たすことは容易にわかる。
（注意２．１３） このPropositionは導出パターンをCliqueなパターンに制限しない場合には成立しない。また、DFSコードの順序付けを定義２．１１のようにしなければ成立しない（辺のラベルより２つの頂点ラベルの方が順序付けに対する優先度が高い）。さらに、辺のラベルにもTaxonomyを考慮した場合にも成立しない。
最後に、導出パターンをover-generalizedでないパターンに制限する場合に対する枝狩りの基本となる理論について述べる。
【０１４３】
「定義２．１７（重みつき支持度（文献２））」
グラフGとTaxonomy Tが与えられた際に、パターンPのグラフGにおける出現回数を
【数１６】
と表す。このとき、グラフセットGS = [ Gi ] を固定したとき、パターンPに対して
【数１７】
をパターンPの重みつき支持度（weighted support）と呼ぶ。ここで、
【数１８】
【０１４４】
「命題２．６」 グラフの集合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をそれぞれα，βとするとき、α＜βとなることを示せばよい。一般化パターンの定義と、ラベル付けの仮定により容易に示せる。
【０１４５】
「命題２．７（文献２）」 DFS code tree上のDFS code Pに対して、Pより以前に出てきたDFSコードP' で、P（の表現するグラフ）がP'（の表現するグラフ）の一般化されたパターンでありかつsupw ( P ) = supw ( P' ) を満たすものが存在するとき、DFSコードPを根にもつ部分木を枝狩りした結果残る部分木は全てのover-genralizedでない部分グラフの最小DFSコードを含む。
（注意２．１４） この命題を用いて過度に一般化されたパターンの枝狩りを効率良く行うためには、あるパターンの特殊化パターンはそのパターンより以前に探索されていなければならない。命題２．６により、任意のパターンはその特殊化パターンよりDFS Lexicographic orderで後に出現するため、DFS lexicographic orderでDFS code treeを探索すれば、上記の枝狩りは効率よく行えることがわかる。
（注意２．１５） この条件による枝狩りだけでは、全てのover-generalizedでないパターンをDFS code treeの探索の段階で枝狩りをすることはできない。枝狩りにもれたパターンは後処理で削除する。
【０１４６】
「２．５ アルゴリズム」
本セクションでは、セクション２．４で述べた理論に基づいて構築されるアルゴリズムについて述べる。その骨格部分は、図１７のアルゴリズム１（Algorithm 1）である。アルゴリズムの入力はＲＮＡ配列の集合（複数のファミリーや未知のファミリーが含まれていても構わない）と最小支持度（minimum support）、最大一般化コスト（maximum generalization cost）である。まず、セクション２．２に述べる方法によりＲＮＡ配列集合からグラフ集合GSおよび頂点ラベルのTaxonomy Tを構築する（line 2）。次にGSから辺のサイズが１の頻出でありかつ一般化コストがmaxcost以下のパターンを抽出する。ここで頻出パターンと一般化コストがmaxcost以下のパターンだけを考えれば十分なのは、命題２．２と命題２．５により保障されている。その後、Cinitial をDFS lexicographi order（定義２．１３）でソートし、その順番でCinitialのパターンに対して、アルゴリズムGraphMining （アルゴリズム２（Algorithm 2）（図１８））を呼び出す。最後に、PSからnon-closed patternおよびnon-cliqueパターンを除く（line 8）。
【０１４７】
アルゴリズム２（Algorithm 2）は提案手法におけるグラフマイニングの骨格部分である。まず、現在考えているパターンsの最小性を判定し、最小でないものに関しては探索を打ち切る（line 3）。この操作によりアルゴリズムの完全性が保たれることは定理２．４による。この際、DFS codeの最小性判定にはコストがかかるため命題２．４を用いて最小性の判定をやらなくていいものに関しては行わない。次に一般化コストの判定を行い、一般化コストがmaxcostより大きいものに関しては探索を打ち切る。これを保障するのが命題２．５である。最後にover-generalizedなパターンであるかどうかの判定を行い、over-generalizedなパターンであれば探索を打ち切る（line 4）。この判定は、命題２．７により行うが注意２．１４にも述べたとおりこの段階ですべてのover-generalizedなパターンを除くことはできない。以上で枝狩りをされなかったパターンはPSに保存する。ここで注意するのは、PSにはcliqueでないパターンも格納する（line 5）。これはover-generalizedなパターンの判定に使用するためである。
line 6では辺を１つ拡張することにより、現在のパターンsの拡張を行う。ここでは命題２．３の条件を満たすようにパターンを拡張し、頻出である（支持度がminsupより大きい）パターンをCに格納する（line 6）。その後、Cのパターンに対してDFS lexicographic orderの順番で再帰的にアルゴリズムGraphMiningを呼び出す。
【０１４８】
「３ 実装」
本アルゴリズムを実装したソフトウェアRNAminer（RNA stem pattern miner）を開発した。実装はC++言語およびSTL / Boostライブラリを用いて行った。さらに現在の実装においては、グラフの同型性判定ライブラリとしてVFlib 2.0（文献２１）をクラスタリングのライブラリとしてCluster 3.0（文献２２）を用いている。また、塩基対確率行列の計算にはVienna RNA package（文献２３）のライブラリを用いている。
なお、ステム候補の抽出の部分で塩基対単位でギャップが許されてよい。また、ステム候補は塩基対の極大集合として抽出するので、ステム候補間が若干オーバラップしていても辺を与えてよい。
【０１４９】
「参考文献」
以下の参考文献のうち、（文献３）は（非特許文献１２）と同じであり、（文献５）は（非特許文献１７）と同じであり、（文献６）は（非特許文献１６）と同じである。
（文献１）
Ramakrishnan Srikant and Rakesh Agrawal. Mining generalized association rules. Future Gener. Comput. Syst., Vol. 13, No. 2-3, pp. 161-180, 1997.
（文献２）
Akihiro Inokuchi. Mining generalized substructures from a set of labeled graphs. In ICDM, pp. 415-418. IEEE Computer Society, 2004.
（文献３）
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.
（文献４）
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.
（文献５）
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.
（文献６）
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.
（文献７）
Daniela Fera, Namhee Kim, Nahum Shiffeldrim, Julie Zorn, Uri Laserson, Hin Hark Gan, and Tamar Schlick. RAG: RNA-As-Graphs web resource. BMC Bioinformatics, Vol. 5, p. 88, Jul 2004.
（文献８）
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.
（文献９）
Robert J Klein and Sean R Eddy. RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics, Vol. 4, p. 44, Sep 2003.
（文献１０）
T F Smith and M S Waterman. Identification of common molecular subsequences. J Mol Biol, Vol. 147, No. 1, pp. 195-197, Mar 1981.
（文献１１）
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.
（文献１２）
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.
（文献１３）
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.
（文献１４）
Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda. An apriori-based algorithm for mining frequent substructures from graph data. In PKDD '00: Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, pp. 13-23, London, UK, 2000. Springer-Verlag.
（文献１５）
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.
（文献１６）
Akihiro Inokuchi, Takashi Washio, Kunio Nishimura, and Hiroshi Motoda. A Fast Algorithm for Mining Frequent Connected Subgraphs. IBM Research. In IBM Research Report, 2002.
（文献１７）
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.
（文献１８）
Xifeng Yan and Jiawei Han. Closegraph: mining closed frequent graph patterns. In KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 286-295, New York, NY, USA, 2003. ACM Press.
（文献１９）
T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms (2nd edition). MIT Press, 2001.
（文献２０）
Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. 2002.
（文献２１）
C. Goggia and S. Tortorella. Graph matching: A fast algorithm and its evaluation. 1999.
（文献２２）
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.
（文献２３）
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.
（文献２４）
Bernhart SH, Hofacker IL, and Stadler PF. Local RNA base pairing probabilities in large sequences. Bioinformatics, Dec 2005. JOURNAL ARTICLE.
【０１５０】
以上に本発明の好適な実施の形態を説明した。しかし、本発明は上述の実施の形態に限定されず、当業者が本発明の範囲内で上述の実施の形態を変形可能なことはもちろんである。
【産業上の利用可能性】
【０１５１】
以上のように、本発明は、複数のＲＮＡ配列データからコンピュータ処理によって２次構造モチーフを抽出することができ、バイオインフォマティクス技術として有用である。
【図面の簡単な説明】
【０１５２】
【図１】ＤＮＡおよびＲＮＡの配列を示す図である。
【図２】ＲＮＡの局所的な２次構造の例を示す図である。
【図３】ＲＮＡの２次構造の例を示す図である。
【図４】本実施の形態のＲＮＡ配列情報処理を実現するコンピュータを示す図である。
【図５】本実施の形態のＲＮＡ配列情報処理の全体像を示す図である。
【図６】本実施の形態のＲＮＡ配列情報処理装置の機能ブロック図である。
【図７】塩基対確率行列を示す図である。
【図８】ステムグラフを示す図である。
【図９】ステムグラフを示す図である。
【図１０】ステム候補間の３タイプの接続関係を示す図である。
【図１１】分類データとしてのタクソノミを示す図である。
【図１２】本実施の形態におけるグラフ解析の原理を示す図である。
【図１３】分類データを用いたステムパターンの比較処理を示す図である。
【図１４】ステムパターンの一般化コストを示す図である。
【図１５】支持度の定義を示す図である。
【図１６】パターン探索アルゴリズムのＤＦＳツリーを示す図である。
【図１７】本実施の形態のRNA配列情報処理を実現するアルゴリズムを示す図である。
【図１８】本実施の形態のRNA配列情報処理を実現するアルゴリズムを示す図である。
【符号の説明】
【０１５３】
２１ ＲＮＡ配列情報処理装置
２３ 配列データ入力部
２５ 配列データ記憶部
２７ ステム候補抽出部
２９ ステム候補記憶部
３１ グラフ生成部
３３ グラフ記憶部
３５ 分類データ生成部
３７ 分類データ記憶部
３９ グラフ解析部
４１ 最小支持度入力部
４３ 最大一般化コスト入力部
４５ 出力部
４７ ２次構造データ生成部
【技術分野】
【０００１】
本発明は、複数のＲＮＡ配列データをバイオインフォマティクス技術によって処理して、それら複数のＲＮＡ配列データに共通に含まれる２次構造モチーフを抽出する技術に関する。
【背景技術】
【０００２】
近年、多くのＲＮＡがタンパク質に翻訳されることなく、それ自身が機能性分子として生理学的に重要な役割を果たすことが明らかになってきた。これらのＲＮＡは総称して機能性ＲＮＡ（functional RNA）または非コードＲＮＡ（non-coding RNA, ncRNA）と呼ばれ非常に注目を集めている。たんぱく質と同様に、機能性ＲＮＡは、１次配列よりも立体構造がその機能に重要であると考えられている。また、Tinoco らは、ＲＮＡの立体構造は２次構造により大部分が決定されるとの報告をしている（非特許文献１）。それらを裏付けるように、多くの機能性ＲＮＡが、進化的に高度に保存された大域的あるいは局所的な２次構造モチーフを有する機能ファミリーを形成している（例えばtRNA, RNaseP-bact-a, tmRNAなど（http://www.sanger.ac.uk/software/rfam/））。従って、機能性ＲＮＡファミリーを特定すること及び機能性ＲＮＡファミリーを特徴付ける２次構造モチーフを抽出することは、機能性ＲＮＡを解析する際に非常に有用な情報をもたらす。
【０００３】
現在のところ、ＲＮＡの２次構造予測の手法は大きく分けて２種類存在する。そのひとつが、mfold（非特許文献２）やRNAfold（非特許文献３）に代表される、最小自由エネルギー（Minimum Free energy, MFE）に基づいた単一のＲＮＡ配列からの２次構造予測である。これらの手法は比較的古くから研究がなされているが、一般的にはそれほど高精度ではない。その理由は、エネルギーパラメタの精度や、また、実際のＲＮＡ分子は他の分子との相互作用の中で立体構造を形成しているため単一の配列の最適な構造とは異なることなど、にあると考えられる。そのため、最適な構造だけでなく、準最適な２次構造まで導出する手法（非特許文献４、５、６）や統計的にＲＮＡの２次構造をサンプリングする手法（非特許文献７、８）の研究もなされている。
【０００４】
もうひとつが、共通の二次構造を有すると考えられる複数のＲＮＡを用いた（共通）２次構造予測手法である。この手法には、入力配列のアラインメントを必要とするもの(RNAalifold（非特許文献９）、ILM（非特許文献１０）、Pfold（非特許文献１１）など) とアラインメントを必要としないもの（ScaRNA（非特許文献１２）、Cofolga（非特許文献１３）、PMcomp/PMmulti（非特許文献１４）、RNAcast（非特許文献１５）、comRNA（非特許文献１６）、CaＲＮＡc（非特許文献１７）など）が存在する。これらの手法は、似たような構造を有する入力配列群が適切に与えられれば、ＭＦＥだけに基づいた２次構造予測よりも多くの情報を用いるので一般的には精度が良いとされている。ただし、アラインメントを仮定せずに、複数配列からその共通２次構造を導出する数理的に厳密なアルゴリズムは、Sankoff アルゴリズム（非特許文献１８）と呼ばれるものと等価となり、時間計算量と記憶計算量が膨大である。
【０００５】
このような一般的な２次構造の予測手法だけでなく、ＲＮＡのモチーフに焦点を当てたＲＮＡ情報解析技術も多数存在する（非特許文献１９）。ERPIN（非特許文献２０、２１）、Infernal（非特許文献２２）、RNAMotif（非特許文献２３）は、ＲＮＡのマルチプルアラインメントから、それらの２次構造モチーフのモデル化を行い、構築されたモデルを用いてゲノム上からそのモデルに適合する２次構造モチーフの探索を行う。すなわちこれらの手法は、既知のモチーフを有する配列を発見する際に利用可能である。一方で、ファミリーを形成すると考えられる機能性ＲＮＡ配列群から、そのファミリーを特徴付けるモチーフを抽出するための手法も存在する。GPRM（非特許文献２４）は、遺伝的アルゴリズムを用いて入力配列群とランダム配列群とを区別する２次構造モチーフの発見を行う。RNAprofile（非特許文献２５）は、Greedy かつヒューリスティックな方法により探索空間を減少させ、整列していないＲＮＡ配列群から局所的に保存された２次構造モチーフを発見する手法を提案している。さらについ最近では、CMfinder（非特許文献２６）と呼ばれるCovariance Model とヒューリスティック手法を組み合わせた、ノイズに対してロバストな、非整列ＲＮＡ配列群からのモチーフ発見手法も提案されている。これらの機能性ＲＮＡファミリーからのモチーフ抽出手法は、ある程度のノイズに対しては影響を受けないような工夫がされているが、基本的には単一のＲＮＡのファミリーである配列群に適用する手法である。しかしながら、解析対象となるＲＮＡ配列集合に複数のファミリーや未知のファミリーが含まれるという現実的な状況においては、機能性ＲＮＡファミリーの特定と２次構造モチーフの抽出は表裏一体となり、同時に行われることが望ましい。なぜなら、ファミリーの決定にはファミリーを特徴付ける２次構造モチーフが必要であり、かつ、２次構造モチーフの決定にはファミリーが必要となるからである。これは、ある意味、特徴抽出とクラスタリングを同時に行う問題に近いといえる。
【０００６】
その他の関連する背景技術を説明すると、ＲＮＡ配列のグラフによるモデル化の既存手法としては、RAG（非特許文献２７）が有名であるが、これはＲＮＡの２次構造のモデル化を行う方法である。また、非特許文献２８は、ＲＮＡファミリーの２次構造のプロファイルが与えられた際に、そのプロファイルをグラフで表現すると同時に、プロファイルを用いてゲノム配列（の断片）をグラフによりモデル化する方法を提案している。
【非特許文献１】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. JOURNAL ARTICLE.
【非特許文献６】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. The ERPIN 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. BMC Bioinformatics, 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.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述してきたように、機能性ＲＮＡの機能ファミリーを同定すること及びファミリーを特徴付ける２次構造モチーフを抽出することは共に機能性ＲＮＡの解析において非常に重要である。解析対象となるＲＮＡ配列集合に複数のファミリーや未知のファミリーが含まれているという現実的な問題設定の下では、機能性ＲＮＡファミリーの特定と２次構造モチーフの抽出は互いに密接に関連した問題となり、同時に解くべき必要が生じる。なぜなら、ファミリーの決定にはファミリーを特徴付ける２次構造モチーフが必要であり、かつ、２次構造モチーフの決定にはファミリーが必要となるからである。しかしながら、既存のＲＮＡ解析手法では、これらの問題を同時に解く手法は存在しない。
【０００８】
本発明は上記背景の下でなされたものであり、その目的は、コンピュータを用いたバイオインフォマティクスの情報処理によってＲＮＡ配列群から２次構造モチーフを抽出することができる好適な配列データ処理技術を提供することにある。本発明の一つの目的は、機能性ＲＮＡのファミリーの特定とモチーフ抽出を同時に行うことが可能な技術を提供することにある。
【課題を解決するための手段】
【０００９】
本発明は、ＲＮＡ配列データを対象とした配列情報処理技術を提供する。本発明は、概略的には、ＲＮＡ配列群をタクソノミ（Taxonomy）を用いたラベル付き有向グラフでモデル化し、近年データマイニングの分野で活発に研究されているグラフ解析（グラフマイニング）手法を応用して、配列群に頻出するステムパターン（２次構造モチーフ）の抽出およびそのステムパターンを有するＲＮＡ配列集合（機能性ＲＮＡファミリー）の特定を行う。ここで言うグラフマイニング手法とは、与えられたグラフセットから多頻度で出現する部分グラフ（グラフパターン）を効率的かつ完全に抽出する手法であり、後に例示されるように近年様々なアルゴリズムが提案されている。本発明は、これらのグラフマイニング手法を応用すると同時に、抽出するグラフパターンがClique（完全グラフ）であるという性質を利用して探索空間を効率良く削減させる。さらに、本発明は、グラフの一般化コストと呼ばれる新しい概念を導入することにより、更なる効率化を行っている。また、本発明は、ランク付けされたステムのパターンの候補を複数導出すると同時に、ステムのパターンに対して各ＲＮＡの２次構造を複数導出することが可能である。本発明で提案している、頂点間の類似度からクラスタリングにより頂点ラベルのTaxonomy を構築し頻出グラフマイニングを行う手法は、対象をグラフによりモデル化した際に、頂点間の類似度や非類似度が自然に定義できる場合に好適に適用可能な手法となっている。
【００１０】
本発明の一態様は、ＲＮＡ配列情報処理装置であり、この装置は、複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出するステム候補抽出部と、各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成するグラフ生成部と、前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを解析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出するグラフ解析部と、を備えている。
【００１１】
上記のように、本発明は、複数のＲＮＡ配列データから複数のステムグラフをそれぞれ生成する。ステムグラフは、ＲＮＡ配列中の潜在的なステムの候補が頂点であり、頂点間を辺で結んだグラフである。このようなグラフにおいては、部分グラフがステムパターンであり、ステムパターンはＲＮＡ配列の部分的な２次構造を表す。したがって、同様の部分グラフが複数のステムグラフに頻出すれば、その類似部分グラフは、複数のＲＮＡ配列に共通の２次構造モチーフである。本発明は、この点に着目して、複数のステムグラフに頻出する類似部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出している。このようにして、本発明によれば、ＲＮＡ配列群から２次構造モチーフを抽出することができる。
【００１２】
本発明の情報処理が、機能性ＲＮＡのファミリーが特定されていないＲＮＡ配列群に適用されたとする。この場合、頻出ステムパターンが抽出されると同時に、頻出ステムパターンを含むＲＮＡ配列（ステムグラフ）も分かる。すなわち、２次構造モチーフが抽出されると同時に、２次構造モチーフを含むファミリーを同定することができる。また、本発明は、既に同定されている機能ファミリーの配列群に適用されてもよく、この場合にも２次構造モチーフが好適に抽出される。
【００１３】
前記グラフ生成部は、前記ＲＮＡ配列上での各ステム候補対の位置関係に応じた向きを、前記各ステム候補対を結ぶ辺のラベルに付与してよい。前記グラフ解析部は、前記複数のステムグラフから、対応する辺の向きが同じ前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１４】
前記グラフ生成部は、各ステム候補対の接続関係が並列、埋込み、重複のいずれかに属するかの情報を、前記各ステム候補対を結ぶ辺のラベルに付与してよい。前記グラフ解析部は、前記複数のステムグラフから、対応する辺の前記接続関係が同じ前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１５】
前記グラフ生成部は、前記並列、埋込みおよび重複のいずれにも該当しないステム候補対を辺での接続対象から除外してよい。これにより、不適当な部分グラフの抽出を回避して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１６】
前記グラフ生成部は、各頂点が部分グラフ内のすべての他の頂点と辺で結ばれる完全部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１７】
本発明のＲＮＡ配列情報処理装置は、前記複数のステムグラフに含まれる前記複数のステム候補を類似性に基づいて分類する分類データを生成する分類データ生成部を含んでよい。前記グラフ解析部は、前記複数のステムグラフから、対応する頂点のステム候補が同じ分類に属する前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１８】
前記分類データ生成部は、前記分類データとして、前記複数のステム候補を、類似範囲の広さが下位層から上位層へ向かって増大するように階層的にクラスタリングを行ったタクソノミデータを生成してよい。前記グラフ解析部は、前記タクソノミデータに基づき、対応する頂点のステム候補が下位層では異なる分類に属しても上位層では同一分類に属する前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００１９】
本発明のＲＮＡ配列情報処理装置は、前記タクソノミデータにて階層に応じて増大する一般化コストの最大許容値である最大一般化コストを入力する最大一般化コスト入力部を含んでよい。前記グラフ解析部は、前記最大一般化コスト以下の一般化コストを有する前記部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００２０】
前記分類データ生成部は、ステム候補対の類似性を表す類似性パラメータを、ステム候補対の配列相同性、ステム候補により形成されるループの距離の類似性、および、ＲＮＡ配列内でのステム候補の位置の類似性の少なくとも一つに応じて求めてよい。また、分類データ生成部は、ステム候補対の類似性を類似性パラメータを、ステム候補の塩基対形成確率に応じて求めてよく、このとき、２つのステム候補の塩基対形成確率の和が評価されてよく、そして、和の値が大きいほど類似度が高いと判断されてよい。これにより、ステム候補である頂点間の類似性を適切に判断して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００２１】
本発明のＲＮＡ配列情報処理装置は、前記複数のステムグラフにおける前記部分グラフの支持度の最小許容値である最小支持度を入力する最小支持度入力部を含んでよい。前記グラフ解析部は、前記最小支持度以上の支持度を有する前記部分グラフを抽出してよい。支持度はグラフ解析で使われる用語で、頻度（頻出の程度）を表す。最小支持度以上の支持度を有する部分グラフを抽出することにより、ＲＮＡ配列群に頻出するステムパターンを適切に抽出できる。
【００２２】
前記ステム候補抽出部は、分子構造のエネルギに基づいて前記ＲＮＡ配列上の任意の２つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域を前記ステム候補として抽出してよい。これにより、ステム候補を適切に抽出することができる。
【００２３】
本発明のＲＮＡ配列情報処理装置は、単独のコンピュータで実現されてもよく、複数のコンピュータからなるシステムによって実現されてもよい。ＲＮＡ配列情報処理装置は、インターネット等のネットワークを介して、データの受付（入力）と提供（出力）を行ってもよい。
【００２４】
また、本発明は上記のＲＮＡ配列情報処理装置の態様に限定されない。本発明の別の態様は、例えば、コンピュータによる情報処理方法であり、また、そのような方法を実現するプログラムである。このような別の態様にも、上述のＲＮＡ配列情報処理装置に関する各種の発明を適用可能なことはもちろんである。
【００２５】
本発明の別の態様は、複数のＲＮＡ配列からコンピュータ処理によって２次構造モチーフを抽出するＲＮＡ配列情報処理方法である。この方法は、複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出し、各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出する。この態様でも上述の本発明の利点が得られる。
【００２６】
また、本発明の別の態様は、複数のＲＮＡ配列から２次構造モチーフを抽出する配列情報処理をコンピュータに実行させるＲＮＡ配列情報処理プログラムである。このプログラムは、複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出し、各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出する、処理を前記コンピュータに実行させる。この態様でも上述の本発明の利点が得られる。
【発明の効果】
【００２７】
上記のように、本発明は、コンピュータを用いた情報処理によって複数のＲＮＡ配列から２次構造モチーフを抽出することができる配列データ処理技術を提供できる。本発明は、機能性ＲＮＡのファミリーの特定とモチーフ抽出を同時に行うことが可能な技術を提供できる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の実施の形態を図面を参照して説明する。以下に説明されるように、本実施の形態のバイオインフォマティクス技術は、全体としては、RNA配列を処理の対象とし、RNAの２次構造を有向グラフで表現し、階層的分類に基づいたグラフ探索処理を有向グラフに組み合わせて２次構造パターンの抽出を行う新規な手法を提供する。
【００２９】
まず、本発明のバイオインフォマティクス技術を説明する前に、ＲＮＡ配列の２次構造を説明する。
【００３０】
図１を参照すると、周知のように、ＤＮＡおよびＲＮＡを構成する塩基は、ａ、ｕ（ｔ）、ｃ、ｇで表される。そして、ａとｕが相補塩基対を作り、ｃとｇが相補塩基対を作る。ＤＮＡでは、逆相補配列が２重らせんを形成している。これに対して、構造ＲＮＡでは、１本鎖が折り畳まれる。そして、相補塩基対により２次構造が作られる。
【００３１】
図２は、局所的な２次構造の例を示している。図示のように、１本鎖ＲＮＡ上には、互いに相補的な２つの領域が存在している。２箇所の相補的な領域が結合し、これにより２次構造が作られる。２次構造を作る相補的な領域は、ステムと呼ばれている。以下の説明では、ステムを形成する２つの部分配列を必要に応じてパーツまたはステムパーツと呼ぶ。２つのパーツが結合されてステムが形成される。
【００３２】
図３は、より大きな範囲の２次構造の例を示している。図示のように、１つのＲＮＡ配列に複数のステムが存在している。
【００３３】
図４は、本実施の形態のＲＮＡ配列情報処理装置を実現するコンピュータを示している。図４のコンピュータ１において、プログラム実行部３は、ＣＰＵ等のプロセッサで構成され、プログラム記憶部５および処理データ記憶部７は、メモリで構成される。また、コンピュータ１は、ハードディスク等の外部記憶装置１１を備え、さらに、入力装置１３、出力装置１５、記録媒体装着部１７および通信部１９などを備えている。
【００３４】
プログラム記憶部５は、本実施の形態の装置および方法を実現するためのプログラムを記憶し、特に、ステム候補抽出プログラム、グラフ生成プログラム、分類データ生成プログラムおよびグラフ解析プログラムを記憶する。これらプログラムは、外部記憶装置１１から読み出され、そいて、プログラム実行部３により実行される。これらプログラムの機能の詳細は後述する。
【００３５】
処理データ記憶部７は、処理されるべきデータや、処理後のデータを記憶する。処理データ記憶部７は、例えば、処理対象のＲＮＡ配列データ、ステム候補データ、ステムグラフデータ、分類データおよびグラフ解析データを記憶する。その他にも、メモリは、プログラム実行部３による処理の作業エリアとして機能し、各種の処理データを記憶する。
【００３６】
コンピュータ１へのデータの入出力は、典型的には、入力装置１３および出力装置１５を介して行われる。その他、データの入出力は、記録媒体装着部１７を介して、記録媒体との間で行われてよい。また、データの入出力は、通信部１９を介して行われてよい。コンピュータ１がＷＥＢサーバに接続され、ネットワークを介してデータが入出力されてよい。あるいは、コンピュータ１がＷＥＢサーバの機能を有していてもよい。
【００３７】
ＲＮＡ配列情報処理装置は、概略的には、ＲＮＡ配列群から、個々の配列に潜在するステム候補を抽出し、ＲＮＡ配列群に頻出するステムパターンを抽出する。ステムパターンは、複数のステムにより形成されるパターン（部分的配列）である。このステムパターンは、ＲＮＡのモチーフ抽出に応用され、また、ＲＮＡのファミリー抽出に応用され、さらには、複数配列からの２次構造予測に応用される。
【００３８】
本実施の形態において、入力データと出力データは以下の通りである。入力データは、ＲＮＡ配列群のデータである。ＲＮＡ配列群に整列（アライメント）が施されていなくてよい。また、ＲＮＡ配列群が同一のＲＮＡファミリーに属している必要はない。コンピュータ１はＲＮＡ配列情報処理装置として機能し、図４の各種プログラムに従ってＲＮＡ配列群のデータを処理して、ＲＮＡ配列群に頻出する頻出ステムパターンを求め、さらに、頻出ステムパターンに対応する二次構造を求める。これら頻出ステムパターンおよび二次構造が出力データとして出力される。その他、本実施の形態では、パラメータとして最小支持度および最大一般化コストが入力される。これらパラメータは、頻出ステムパターンの抽出処理において、抽出条件として処理される。
【００３９】
図５は、ＲＮＡ配列情報処理の全体像を示している。図示のように、ＲＮＡ配列群が入力される（Ｓ１）。上述したように、ＲＮＡ配列群は整列されていなくてよい。各ＲＮＡ配列がステム候補抽出プログラムの処理を受け（Ｓ２）、各ＲＮＡ配列のステム候補が抽出される（Ｓ３）。本実施の形態では、ステム候補抽出プログラムは、塩基対確率行列を生成するプログラムによって実現される。
【００４０】
次に、ステム候補の情報から、ステムグラフと分類データが、グラフ生成プログラムおよび分類データ生成プログラムにより生成される（Ｓ４）。各ＲＮＡ配列に対して一つのステムグラフが生成される。ステムグラフは、ＲＮＡ配列から抽出された複数のステム候補を頂点とし、頂点間を辺で結んだグラフである。本実施の形態では、後述するようなラベル付き有向グラフが生成される。また、分類データは、複数のＲＮＡ配列群から抽出された全部のステム候補（グラフの頂点）をそれらの類似性に基づき分類したデータであり、本実施の形態では図示のように、階層構造を持つツリー型タクソノミデータ（taxonomy）である。
【００４１】
次に、ステムグラフ群がグラフ解析プログラムによって解析されて（Ｓ５）、ステムグラフ群に頻出する部分グラフが抽出され、さらに部分グラフに対応する２次構造が求められる（Ｓ６）。部分グラフは、ステムグラフの一部の頂点と辺で構成されるパターンであり、ステムパターンに相当する。本実施の形態は、グラフ形状が類似し、かつ、対応する頂点のステム候補が類似し、ステムグラフ群に頻出する部分グラフを抽出する。頂点の類似は分類データから求められる。このような頻出部分グラフが、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出される。そして、頻出部分グラフに対応する２次構造が求められる。
【００４２】
図６は、上述した処理を実現するためのＲＮＡ配列情報処理装置を機能ブロック図のかたちで示している。図６のＲＮＡ配列情報処理装置２１において、配列データ入力部２３は、ＲＮＡ配列群のデータを入力する。入力されたＲＮＡ配列データは、配列データ記憶部２５に記憶される。ステム候補抽出部２７は、入力された各々のＲＮＡ配列から、ＲＮＡ２次構造のステム候補を抽出し、ステム候補記憶部２９に格納する。
【００４３】
グラフ生成部３１は、各ＲＮＡ配列のステムグラフを生成し、グラフ記憶部３３に記憶する。また、分類データ生成部３５は、ステムグラフの頂点（ステム候補）に関する分類データを生成して、分類データ記憶部３７に格納する。本実施の形態では、ラベル付き有向グラフと階層的なツリー型タクソノミデータが生成される。
【００４４】
グラフ解析部３９は、分類データを参照しながらステムグラフ群を解析して、それらステムグラフに頻出する部分グラフを抽出する。グラフ解析部３９は、グラフ形状が類似し、かつ、対応する頂点のステム候補が類似する部分グラフを抽出する。このような部分グラフが、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出される。
【００４５】
最小支持度入力部４１および最大一般化コスト入力部４３は、頻出ステムパターン抽出処理における抽出条件を決定するパラメータである最小支持度および最大一般化コストを入力する。これらパラメータは、グラフ解析部３９の処理に用いられる。
【００４６】
出力部４５は、グラフ解析部３９によって抽出された頻出ステムパターンの情報を出力する。また、出力部４５は、頻出ステムパターンに対応する２次構造データを出力する。２次構造データは、２次構造データ生成部４７により生成される。
【００４７】
図６の構成において、配列データ入力部２３、最小支持度入力部４１および最大一般化コスト入力部４３は、図４の入力装置１３、記録媒体装着部１７または通信部１９によって実現される。また、出力部４５は、図４の出力装置１５、記録媒体装着部１７または通信部１９によって実現される。また、ステム候補抽出部２７、グラフ生成部３１、分類データ生成部３５およびグラフ解析部３９は、図４のプログラム記憶部５に記憶されたステム候補抽出プログラム、グラフ生成プログラム、分類データ生成プログラムおよびグラフ解析プログラムをプログラム実行部３が実行することによって実現される。２次構造データ生成部４７も、プログラム記憶部５のプログラムをプログラム実行部３が実行することにより実現される。また、配列データ記憶部２５、ステム候補記憶部２９、グラフ記憶部３３および分類データ記憶部３７は、図４の処理データ記憶部７および外部記憶装置１１によって実現される。
【００４８】
以下、ＲＮＡ配列情報処理装置の各部機能についてより詳細に説明する。
【００４９】
「ステム候補の抽出」
図６のステム候補抽出部２７は、各々のＲＮＡ配列データから、ＲＮＡ２次構造の複数のステム候補を抽出する処理を行う。本実施の形態では、以下に説明するように、ステム候補抽出部２７が、分子構造のエネルギに基づいてＲＮＡ配列上の任意の２つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域をステム候補として抽出する。
【００５０】
図７は、ＲＮＡ配列データから生成された塩基対確率行列を、ＲＮＡ配列の２次構造の例と共に示している。塩基対確率行列においては、同一のＲＮＡ配列が横方向と縦方向に配置される。行列の要素（ｉ，ｊ）は、ｉ番目の塩基とｊ番目の塩基が塩基対を形成する確率を表す。この確率は、エネルギが最小になる構造を求める計算によって得られる。図７では、確率の大きさが、点の大きさで表されている。一つのＲＮＡ配列が両方向に配置されているので、図示のような半分の領域（三角形領域）にて、全塩基対の確率が表される。
【００５１】
図７の塩基対確率行列において、ステムは、確率が大きい複数の要素が、図示のように右上がりの４５度方向に並んだ領域である。
【００５２】
ステム候補抽出部２７は、各々のＲＮＡ配列データから、図７に示されるような塩基対確率行列を生成する。本実施の形態では、ＭｃＣａｓｋｉｌｌのアルゴリズムが好適に用いられる。そして、ステム候補抽出部２７は、塩基対確率行列から、所定値ｐ以上の確率を持つ要素が所定個数ｎ以上連続する領域を抽出する。この領域が、ステム候補として特定され、ステム候補記憶部２９に記憶される。
【００５３】
さらに、ステム候補抽出部２７は、ステム候補における全要素の確率の平均を求める。平均値は０から１の間の値になる。この平均値は、ステム候補のスコアとしてステム候補記憶部２９に記憶される。このスコアは、後述のステム候補間の類似性の判断に用いられる。
【００５４】
以上にステム候補抽出処理の好適な例を説明した。ステム候補抽出処理は上記に限定されない。より簡単な例としては、既知のステム配列が、ＲＮＡ配列から探索され、ステム候補として特定されてよい。ステムを構成する２つの部分配列が探索される。既知のステムの配列は、過去の研究で得られた既知の２次構造から求められてよい。
【００５５】
「ステムグラフの生成」
図６のグラフ生成部３１は、上述したように、各ＲＮＡ配列データから抽出されたステム候補の情報を基に、各ＲＮＡ配列に対応するステムグラフを生成する処理を行う。
【００５６】
図８および図９は、ステムグラフの例を示している。図８ではステムグラフが確率塩基対行列の上に描かれており、図９ではステムグラフが単独で描かれている。図示のように、ステムグラフでは、各ステム候補が頂点である。図の例では、９個のステム候補が頂点になっている。そして、ステム候補間が辺で結ばれる。
【００５７】
本実施の形態では、ステムグラフがラベル付き有向グラフであり、グラフの頂点および辺にはラベルが付与される。各頂点および各辺には、それらを識別するためのユニークなラベルが付与される。さらに、各辺には、下記の２つの情報が付与される。
【００５８】
（１）向き：ステム候補間の位置関係を表す向きである。図８では、辺の向きが矢印で示されている。辺の向きは、配列上で５’側（一般の直線配置で左側）のステム候補から３’側（一般の直線配置で右側）のステム候補へ向くように設定される。ここで、ステム候補位置は、各ステム候補の５’側のステムパーツの位置で特定される。
【００５９】
図８（および図７）では、横方向の配置にて、５’側が左であり、３’側が右である。そして、縦方向の配置では、５’側が上であり、３’側が下である。この場合、辺の向きは、縦の配置の５’側のステム候補から３’側のステム候補へ向くように付けられている。要するに、辺の矢印は、図８の上側のステム候補から下側のステム候補を向いている。
【００６０】
（２）接続関係：これは、ステム候補間の接続関係が３つのタイプのいずれに属するかの情報である。図１０に示されるように、３つのタイプとは、並列（Juxtaposed）、埋込み（Embedded）、重複（Overlapped）である。これらは、矛盾のない関係（consistent relation）である。図９のグラフは、並列（“Ｊ”）と埋込み（“Ｅ”）の辺を含んでいる。
【００６１】
なお、グラフ生成部３１は、上記３つのタイプいずれにも該当しないステム候補対を辺での接続対象から除外する。これにより、矛盾のある関係（inconsistent relation）が除外される。例えば、ステム候補＃２、＃８は、上記の接続タイプに該当せず、したがって、辺で結ばれていない。
【００６２】
上記の例において、＃２、＃８のステム候補では、ステムの片側パーツが共通している。したがって、これらのステム候補の両方共が本当のステムである可能性は無い。このようなステム候補対が辺で結ばれないので、妥当なグラフが形成される。
【００６３】
以上、グラフ生成部３１により生成されるステムグラフ（ラベル付き有向グラフ）について説明した。グラフ生成部３１は、ステム候補抽出部２７により抽出されたステム候補を頂点に設定し、頂点間の辺を設定し、頂点および辺にラベルを付与する処理を行い、これにより上記のグラフが生成される。
【００６４】
グラフ生成部３１は、各々のＲＮＡ配列に対して上記のようなステムグラフを生成する。したがって、グラフ生成部３１は、入力されたＲＮＡ配列の数と同じ枚数のグラフを生成する。これらグラフがグラフ記憶部３３に記憶される。
【００６５】
「分類データの生成」
図６の分類データ生成部３５は、上述したように、ステム候補群を分類する分類データを生成する処理を行う。本実施の形態では、図１１に示されるように、分類データが、階層型でツリー型のタクソノミデータである。以下、分類データの生成処理について、より詳細に説明する。
【００６６】
上述のステムグラフ生成処理は、一本のＲＮＡ配列から一つのステムグラフを生成する。一方、この分類処理は、複数のＲＮＡ配列から抽出された全部のステム候補を分類して一つの分類データを生成する。
【００６７】
ステム候補の分類は、ステム候補間の類似性に基づいて行われる。ステム候補の全組合わせの類似性が求められ、類似性を使って分類が行われる。類似性のパラメータは、典型的には、ステム候補同士の配列の相同性である。本実施の形態では、ステム候補対の類似性が、上記の配列相同性を含む４つの類似性によって定義される。（１）ステム候補同士の配列相同性、（２）各ステム候補のスコア、（３）ループの距離の類似性、（４）配列内での位置の類似性。
【００６８】
上記において、（２）のスコアは、ステム候補抽出時に算出された確率である。より詳細には、スコアは、ステム候補の塩基対形成確率の平均である。本実施の形態は、２つのステム候補のスコアの和を利用している。本実施の形態は、スコアの和が大きいほど２つのステム候補の類似度を大きいと考え、スコアの和が小さいほど２つのステム候補の類似度が小さい（非類似度が大きい）と考える。ここで、本発明は、スコアの和が大きいほど、２つのステム候補の両方共が実際のステムである可能性が高いことに着目している。このことを考慮し、本発明は、両方のステム候補が実際のステムである可能性が高いほど類似性が高いと決めている。（３）のループの距離は、ステムを構成する２つのパーツ間の距離（塩基数）である。（４）の位置は、各ステム候補が属するＲＮＡ配列内での位置である。位置は、配列端からの距離（塩基数）で表されてよい。
【００６９】
４つの要素的な類似性パラメータを計算するために、ＲＮＡ配列のデータから、各ステム候補が有する配列、スコア、ループ距離、配列内位置の４つのデータが求められる（スコアは既に説明したように塩基対確率から算出されている）。各データから一組のステム候補の類似性が計算され、したがって、４つのデータから４つの類似性パラメータが計算され、それらが合成されて、一組のステム候補の総合的な類似性パラメータが計算される。このような類似性パラメータが、任意の組のステム候補に対して計算される。類似性パラメータの算出処理は、後述にてさらに詳しく説明されるが、本実施の形態の実現例では、２つのステム候補の違いが大きくなるほど値が大きくなるような類似性パラメータが使われてよい。つまり、類似性パラメータが、非類似度で実現される。
【００７０】
図１１は、上記のような類似性に基づいて生成された分類データを示している。分類データ生成部３５は、頂点間の類似性に基づいたクラスタリングを行い、これにより、図示のようなツリー型のタクソノミデータを生成する。図１１において、左の図は、ステム候補の階層的クラスタリングによって生成される系統樹（dendrogram）である。クラスタリングのためのステム候補間の類似性（similarity）は、既述の通り、（１）配列相同性（sequence similarity）、（２）候補のスコア（score of candidate）、（３）ループ距離（loop distance）、（４）配列内位置（position in sequence）のミックス（mixture）によって定義される。右側の図は、系統樹（dendrogram）から構築されたステム候補のラベルのタクソノミである。
【００７１】
図１１のタクソノミデータでは、最下層の頂点１〜７は、個々のステム候補と対応する。上位層の頂点（分類、ラベル）は、下位層で類似する複数の頂点を代表する。例えば、最下層の３つの頂点１、２、３が類似するので、第２層では一つの頂点８に分類される。分類データ生成部３５は、このような分類データを生成して、分類データ記憶部３７に記憶する。
【００７２】
上記より明らかなように、分類データでは、下位層よりも上位層にて類似範囲が広い。すなわち、下位層よりも上位層にて、一般化の程度が大きい。そこで、本実施の形態では、一般化の程度を表現するために、図１１に示されるように、上位層へ行くほど値が大きくなるように一般化コストが定義される。ｉ層の一般化コストは、１−ｎ（ｉ）／Ｎで表される。ここで、Ｎは、最下層の頂点数（ステム候補の総数）である。ｎ（ｉ）は、階層ｉに属する頂点数である。一般化コストは下記のグラフ解析処理にて用いられることになる。
【００７３】
「グラフ解析処理」
図６のグラフ解析部３９は、上述したように、グラフ生成部３１によって生成された複数のステムグラフに頻出する部分グラフを抽出する処理を行う。ここでは、類似する部分グラフが抽出される。類似する部分グラフとは、グラフ形状が類似し、かつ、対応する頂点のステム候補が類似するグラフである。部分グラフはステム候補のパターンに相当するので、以下、必要に応じて、部分グラフをステムパターンと呼び、抽出される頻出部分グラフを頻出ステムパターンという。
【００７４】
より詳細には、グラフ解析部３９は、ステムグラフでの出現の頻度が所定しきい以上のステムパターン（部分グラフ）を抽出する処理を行う。この頻度は、典型的には、後述するように、「ステムグラフの総数」に対する、「特定の類似するステムパターンを含むステムグラフの数」の比、で表される。
【００７５】
頻出ステムパターンの抽出では、上記のように類似性が考慮される。したがって、抽出される一つ頻出ステムパターンは、実際には、複数のステムパターンの集合になってよい。
【００７６】
図１２は、グラフ解析の原理を示している。図１２は、２つのステムグラフを示している。互いに類似するステムパターンが２つのステムグラフから抽出されている。図１２の例では、ステムパターンは、３つの頂点とそれらを結ぶ３つの辺で構成されている。
【００７７】
ステムパターン（部分グラフ）の類似は、グラフ形状の類似性と、グラフ内の頂点の類似性によって決まる。本実施の形態では、以下の３条件が満たされるとき、２つの部分グラフのグラフ形状が類似する。
（１）頂点の数が同じである。
（２）対応する辺の向きが同じである。
（３）対応する辺の接続関係が同じである。
【００７８】
なお、本実施の形態では、後述するように完全（Ｃｌｉｑｕｅ）グラフが抽出される。したがって、類似する部分グラフにおいては、頂点の数が同じであり、それらの任意の２つの頂点間が辺で結ばれ、かつ、各辺のラベルが（２）（３）の条件を満たす。
【００７９】
次に、図１３を参照して、頂点間の類似について説明する。頂点間の類似は、分類データを用いて判断することができる。分類データにおいて同じグループに属する頂点を類似と判断する。
【００８０】
図１３は、２つのステムパターンの例を示している。図において、対応する２組の頂点は同じであるが、対応する１組の頂点が異なっている。しかし、これら頂点が、図１１のタクソノミにおいて、１つ上の階層では同一分類に属するとする。この場合、対応頂点が類似し、そして、２つのステムパターンが類似する。
【００８１】
このようにして、下位層での比較では対応頂点が異なる分類に属しても、上位層の比較で対応頂点が同じ分類に属していれば、対応頂点が類似する。グラフ解析処理では、順次階層を上に変更して、頂点間の類似が判断される。
【００８２】
しかし、階層を高くしすぎると、類似範囲が広くなり過ぎる。例えば、最上層では、すべての頂点が類似し、妥当な比較が困難になる。そこで、本実施の形態では、類似判断における階層の高さが制限される。この制限のために、前述の一般化コストが用いられる。
【００８３】
一般化コストは、図１１に示したように、上位層へ行くほど大きくなる。前述の説明を繰り返すと、ｉ層の一般化コストは、１−ｎ（ｉ）／Ｎで表され、Ｎは、最下層の頂点数（ステム候補の総数）であり、ｎ（ｉ）は、階層ｉに属する頂点数である。
【００８４】
図１４は、ステムパターンの一般化コストを示している。ステムパターンの一般化コストは、各頂点の一般化コストの平均である。グラフ解析処理では、ステムパターンの最大一般化コストが指定され、一般化コストが最大一般化コスト以下になるように頻出ステムパターンが抽出される。例えば、図１３の一般化を行うと、一般化コストが最大値をオーバーしたとする。この場合、図１３の２つのステムパターンは類似しない。
【００８５】
上述の原理に基づきグラフ解析の問題を定式化すると、以下のようになる。
（１）ラベル付き有向グラフの集合、（２）ラベルの一般化コスト付きタクソノミ、（３）最小支持度（ｍｉｎｓｕｐ）、（４）最大一般化コスト（ｍａｘｃｏｓｔ）が与えられた際に、以下を満たすステムパターンをすべて抽出する。
Ａ）支持度が最小支持度以上
Ｂ）完全グラフ（Ｃｉｑｕｅ）
Ｃ）一般化コストが最大一般化コスト以下
Ｄ）クローズドパターン（Ｃｌｏｓｅｄ Ｐａｔｔｅｒｎ）
【００８６】
支持度は、図１５に示される通り、頻出の程度を表す。図において、一つのステムパターンが、３つのステムグラフのうちの２つに存在する。この場合、該当パターンの支持度は、２／３である。完全グラフとは、各頂点がすべての頂点と辺で結ばれたグラフである。ステムパターンがＲＮＡ配列の一部分であれば、必ずステムパターンが完全グラフになる。一般化コストは、既に説明した通りである。クローズドパターンは、「自分を真に含むパターンであって、自分と同じ支持度を持つようなパターンが存在しない」パターンである。
【００８７】
次に、図１６を参照すると、上述してきたグラフ解析処理は、パターン探索アルゴリズムにより好適に実現される。より詳細には、グラフ解析機能は、図１６のＤＦＳ ｃｏｄｅ ｔｒｅｅの探索アルゴリズムにより実現される。この探索アルゴリズムは、少しずつパターンを変えながら、ツリーを深さ方向に探索し、各種の候補パターンを数え上げる。
【００８８】
本実施の形態では、パターン探索アルゴリズムが、上述のグラフ解析処理を実行する。すなわち、パターンの形状が変更される。また、タクソノミに基づいて一般化の程度が変更される。そして、各種のパターンが複数のステムグラフから数えられる。そして、上述の条件を満たす頻出ステムパターンが求められる。
【００８９】
パターン探索のアルゴリズムは、効率よく完全に多様なパターンが数えられるように構成されている。さらに、本実施の形態は、上述のパターン抽出の条件も考慮して下記の制限された処理を行い、さらなる効率的を実現する。（１）支持度の逆単調性による枝狩り、（２）Ｃｌｉｑｕｅ制約によりＤＦＳ ｃｏｄｅ ｔｒｅｅの子要素を限定、（３）最大一般化コストの制約を用いた枝狩り、（４）過度に一般化されたパターンを除くための枝狩り。枝狩り（pruning）とは、ツリー上の部分木を探索対象から除外することをいう。これらの処理については、後にさらに詳細に説明する。
【００９０】
以上に頻出ステムパターンを抽出するグラフ解析処理を説明した。グラフ解析部３９は、上述の処理を行うことによって頻出ステムパターンを抽出する。さらに、２次構造生データ成部４７は、抽出された頻出ステムパターンに対応する２次構造データを生成する。これら頻出ステムパターンと対応する２次構造データが出力部４５から出力される。
【００９１】
ここで、グラフ解析部３９は、上述の条件に該当する全部の頻出ステムパターンを抽出する。したがって、グラフ解析部３９は、通常は複数の頻出ステムパターンを抽出する。さらに、類似性が考慮されているので、一つの頻出ステムパターンは、複数のステムパターンに対応することもある。２次構造データは、各々のステムパターン（部分グラフ）から作られてよい。これらデータが、出力されてよい。
【００９２】
以上に、本実施の形態のＲＮＡ配列情報処理装置、方法およびプログラムについて詳細に説明した。以下、本発明の各種態様の利点をまとめて述べる。本発明は、複数のＲＮＡ配列データから複数のステムグラフをそれぞれ生成し、それら複数のステムグラフから頻出ステムパターンを抽出する。頻出ステムパターンは、ＲＮＡ２次構造モチーフを表している。したがって、本発明は、ＲＮＡ配列群から２次構造モチーフを抽出することができる。
【００９３】
本発明の情報処理が、機能性ＲＮＡのファミリーが特定されていないＲＮＡ配列群に適用されたとする。この場合、頻出ステムパターンが抽出されると同時に、頻出ステムパターンを含むＲＮＡ配列（ステムグラフ）も分かる。すなわち、２次構造モチーフが抽出されると同時に、２次構造モチーフを含むファミリーを同定することができる。また、本発明は、既に同定されている機能ファミリーの配列群に適用されてもよく、この場合にも２次構造モチーフが好適に抽出される。
【００９４】
また、上述にて説明したように、グラフ生成部は、ＲＮＡ配列上での各ステム候補対の位置関係に応じた向きを、各ステム候補対を結ぶ辺のラベルに付与してよい。そして、グラフ解析部は、複数のステムグラフから、対応する辺の向きが同じ部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００９５】
また、グラフ生成部は、各ステム候補対の接続関係が並列、埋込み、重複のいずれかに属するかの情報を、各ステム候補対を結ぶ辺のラベルに付与してよい。グラフ解析部は、複数のステムグラフから、対応する辺の接続関係が同じ部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００９６】
また、グラフ生成部は、並列、埋込みおよび重複のいずれにも該当しないステム候補対を辺での接続対象から除外してよい。これにより、不適当な部分グラフの抽出を回避して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００９７】
また、グラフ生成部は、各頂点が部分グラフ内のすべての他の頂点と辺で結ばれる完全部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【００９８】
また、分類データ生成部は、複数のステムグラフに含まれる複数のステム候補を類似性に基づいて分類する分類データを生成してよい。グラフ解析部は、複数のステムグラフから、対応する頂点のステム候補が同じ分類に属する部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出できる。
【００９９】
また、分類データ生成部は、分類データとして、複数のステム候補を、類似範囲の広さが下位層から上位層へ向かって増大するように階層的にクラスタリングを行ったタクソノミデータを生成してよい。グラフ解析部は、タクソノミデータに基づき、対応する頂点のステム候補が下位層では異なる分類に属しても上位層では同一分類に属する部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【０１００】
また、最大一般化コスト入力部が、タクソノミデータにて階層に応じて増大する一般化コストの最大許容値である最大一般化コストを入力してよい。グラフ解析部は、最大一般化コスト以下の一般化コストを有する部分グラフを抽出してよい。これにより、複数のステムグラフから類似する部分グラフを適切に抽出することができる。
【０１０１】
また、分類データ生成部は、ステム候補対の類似性を表す類似性パラメータを、ステム候補対の配列相同性、ステム候補により形成されるループの距離の類似性、および、ＲＮＡ配列内でのステム候補の位置の類似性の少なくとも一つに応じて求めてよい。また、分類データ生成部は、二次構造エネルギに基づいたステム候補の塩基対形成確率に応じて類似性パラメータを求めてよく、このとき、２つのステム候補の塩基対形成確率の和が評価されてよく、そして、和の値が大きいほど類似度が高いと判断されてよい。上記の例では、これら全部が加味されている。これにより、ステム候補である頂点間の類似性を適切に判断して、複数のステムグラフから類似する部分グラフを適切に抽出することができる。類似性判断の基礎になるパラメータは、ステムグラフの頂点のラベルに付与されてよい。
【０１０２】
また、最小支持度入力部が、複数のステムグラフにおける部分グラフの支持度の最小許容値である最小支持度を入力してよい。グラフ解析部は、最小支持度以上の支持度を有する部分グラフを抽出してよい。支持度は頻度（頻出の程度）を表す。最小支持度以上の支持度を有する部分グラフを抽出することにより、ＲＮＡ配列群に頻出するステムパターンを適切に抽出できる。
【０１０３】
また、ステム候補抽出部は、分子構造のエネルギに基づいてＲＮＡ配列上の任意の２つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域をステム候補として抽出してよい。これにより、ステム候補を適切に抽出することができる。
【０１０４】
また、上述の実施の形態では、頂点間のタクソノミが考慮されて、類似部分グラフ（頻出ステムパターン）が抽出された。本発明のさらなる応用例では、辺のタクソノミが考慮されて、類似部分グラフ（頻出ステムパターン）が抽出されてよい。この場合、辺を特徴づけるパラメータを用いて、辺の類似性を基に、辺のタクソノミが生成される。辺のタクソノミが、頂点のタクソノミと同様に処理されて、辺が類似する部分グラフが抽出される。
【０１０５】
以下、上述の発明に関する研究について詳細に説明する。以下では、上述したラベル付き有向グラフ、タクソノミ、グラフ解析なども詳細に説明される。なお、参考文献は、（文献＋番号）と表記し、文献のリストを最後に記載する。
【０１０６】
「１．はじめに」
この記述の構成は、以下の通りである。セクション２は、グラフ理論の基本的な用語を定義した後に、ＲＮＡのグラフ表現の方法および今回解決すべき問題のグラフマイニングによる定式化、さらにはそれを効率よく解く為の理論およびアルゴリズムについて詳細に説明する。セクション３は、実装方法について述べる。
【０１０７】
「２．手法」
「２．１ グラフ理論・グラフマイニングからの準備」
本文章では、特に断らない限り、グラフとは多重辺や自己ループ辺を許さないラベル付き有向グラフ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 ) で定義されるラベルを含まないグラフである。
【０１０８】
「定義２．１（部分グラフ）」
グラフGが与えられているものとする。グラフGsがGの部分グラフ（subgraph）である（Gs⊆G と書く）とは、写像φ：V ( Gs )→V ( G ) が存在して
（１）任意のv∈V ( Gs ) に対してlb ( v ) = lb (φ( v ) )
（２）任意の( vi, vj )∈E ( Gs ) に対してlb ( vi, vj ) = lb (φ( vi ),φ( vj ) )
を満たすことである。
Srikantら（文献１）は、アイテムセットにおける個々のアイテムの関係をTxonomyとして表現した。さらに、Inokuchi（文献２）は、グラフのラベルにTaxonomyを考えることを提案している。ここではこららを発展させ、ラベル間の関係と各ラベルの一般化コストを考慮した「一般化コスト付きTaxonomy」を定義する。
【０１０９】
「定義２．２（一般化コスト付きTaxonomy）」
ラベルの集合LSが与えられているものとする。このとき、一般化コスト付きTaxonomy（Taxonomy with generalization cost） Tとは、頂点がLSのDAG（directed acyclic graph）で、その各頂点v∈LS に対して一般化コストc ( v )∈R+ が定義されているものである。
（注意２．１) 関係A→Bは、B is a A（ラベルAの方がラベルBよりも一般化されている、逆に言うとラベルBの方がラベルAよりも特殊化されている）を意味する。TaxonomyをforestではなくDAGでモデル化したのは、multiple taxonomiesを表現することを可能にするためである（文献１）。また、c ( A )、c ( B )は、それぞれ、ラベルA、Bの一般化に対するコストを表すが、通常の場合、上位概念ほど一般化のコストが大きいと考えられるので、c ( B )＜c ( A ) である。
今後は簡単のため、一般化コスト付きTaxonomyを単にTaxonomyと呼ぶことにする。Taxonomyの頂点xに対して、xまたはxの祖先の集合（xから有向辺を逆にたどっていって到達できる全ての頂点の集合）をτT ( x ) と表すことにする。グラフとTaxonomyが与えられた際の部分グラフを以下のように定義する。
【０１１０】
「定義２．３（Taxonomyが与えられた下での部分グラフ（文献２））」
Taxonomy TとグラフG、Gsが与えられているものとする。Gsが、GのTaxonomy Tが与えられた下での部分グラフ（subgraph under Taxonomy T）であるとき、
【数１】
とかく。これは、写像φ：V ( Gs )→V ( G ) が存在して、
（１）任意のv∈V ( Gs ) に対してlb ( v )∈τT ( lb (φ( v ) ) )
（２）任意の( vi, vj )∈E ( Gs )に対してlb ( vi, vj )∈τT ( lb (φ( vi ),φ( vj ) ) )
を満たすことである。今後は、簡単のため、Taxonomy Tが明らかな場合には、添え字Tは省略する。
（注意２．２） 定義より明らかに
【数２】
である（逆は成立しない）。つまり、Taxonomyが与えられた下での部分グラフの定義は、通常の部分グラフの定義を弱めたものとなっている。
【０１１１】
「定義２．４（Clique）」
グラフがクリーク（Clique）であるとは、任意の頂点間に辺が存在することである。
【０１１２】
「２．２ グラフとTaxonomyを用いたＲＮＡ配列集合のモデル化」
本節では、ＲＮＡ配列の集合全体をラベル付有向グラフとTaxonomyを用いてモデル化を行う方法について記述する。
近年、ステムやループなどのＲＮＡ２次構造の構成要素を一つの単位として積極的に利用したＲＮＡ解析手法が一定の成功を納めている。例えば、Scarna（文献３）は固定長のステムのアラインメントを良く考えられたダイナミックプログラミングにより定式化し、２本のＲＮＡ配列のアラインメントおよびその共通２次構造の予測を高速で行う。RNAscf（文献４）は、複数配列からステム候補のアラインメントを繰り返し行うことにより、共通の２次構造の予測を行う。また、Carnac（文献５）は、２本あるいは３本以上のＲＮＡ配列群から、可能性のあるステム候補を抽出し、cofoldingと呼ばれる手法を用いて、各ＲＮＡ配列の２次構造を予測する。comRNA（文献６）は、グラフ理論におけるClique探索手法を利用して、整列していないＲＮＡ配列群からその共通のモチーフを発見する手法を提案している。これらのステムベースの手法は、ヒューリスティックな部分を多く含んでいるが、精度と計算量のバランスが取れた実用的な手法が多い。本手法でも、これらの手法と同様にステムの候補を積極的に利用したモデル化を行う。
また、単一のＲＮＡ配列は、２次構造を一つに決めれば木構造やRAG（文献７）を用いて表現することが可能であるが、ここでは各ＲＮＡ配列の２次構造自体をモデル化するのではなく、ＲＮＡ配列から得られる可能性のあるステムの候補をすべて用いてＲＮＡのモデル化を行う。その手順は以下の通りである。
（１）各ＲＮＡ配列の塩基対確率行列からステム候補を抽出しグラフの頂点とする。
（２）ステム候補の類似度に基づいた階層型クラスタリングの樹形図から頂点ラベルに対するTaxonomyを構築する。
（３）consistentなステム候補間を有向辺で結びその関係（Juxtaposed, Embedded, Overlapped）に応じて辺にラベルを付与する。
以下に各ステップについてもう少し詳細に説明を行う。
【０１１３】
「２．２．１ グラフの頂点」
McCaskillのアルゴリズム（文献８）を用いてＲＮＡ配列から塩基対確率行列（base pairing probability matrix）を計算する。ここで、McCaskillのアルゴリズムにより計算される塩基対確率行列の( i, j ) 要素は、ｉ番目の塩基とｊ番目の塩基が塩基対を形成する確率を表す。計算された塩基対確率行列から、塩基対を形成する確率がｐ以上で、ｎ個以上の連続する塩基対集合の極大集合をステム候補（Stem candidate）として抽出する（文献３）。なお、現在の実装では、塩基対単位でＭ個のギャップは許容している。ただし、バルジが入るようなステム候補は考えることが出来ない（ステム候補の数が増えるため許容していない）。
さらにステム候補には、そのステム候補を形成する塩基対の確率の平均をスコアとして付与する（このスコアは０以上１以下の実数である）。本手法では、このステム候補をグラフの頂点とする。
【０１１４】
「２．２．２ 頂点ラベルのTaxonomyの構築」
頂点ラベルのTaxonomyを構築するために、セクション2.2.1の２つの頂点（ステム候補）間の非類似度を以下のように定める。ステム候補Sに対して、p ( S ) で５’側ステムの開始位置、d ( S ) でループの距離、r ( S ) で３’側ステムの開始位置、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置換行列（文献９）を用いたステムS1とステムS2のSmith Watermanアラインメント（文献１０）のスコアである。また、wi はΣ i = 1, 2, 3, 4 wi = 1, wi≧0 を満たす重みパラメタである。
セクション２．２．１の方法で抽出されたステム候補全てに対して上述の非類似度に基づき階層型クラスタリングを行う。この際得られる樹形図を用いてTaxonomyを構築する。すなわち、クラス間の距離の列をd = [ dk ]Nk=1 ( d1＜d2＜・・・＜dN ) とする際に、距離がdk 以下のクラスタに対して同一のラベルを付与することによりTaxonomyを構築する。従って、今の場合Taxonomyは階層構造になっている。ここで、Taxonomyの第ｎ階層に属するラベルの一般化コストを、「１−（第ｎ階層のラベル数）／（頂点数）」で与える。
【０１１５】
「２．２．３ グラフの辺」
２つのステム候補間の関係は次のように分類できる。
「性質２．１（文献１１、文献３）」
セクション２．２．１で抽出した２つのステム候補S1、S2の位置関係は、ステム候補の配列上での位置をS1 = ( [ ls1, le1 ] , [ rs1, re1 ] ) 、S2 = ( [ ls2, le2 ] , [ rs2, re2 ] ) (lsk は５’側のステムの開始位置、lek は５’側のステムの終了位置、rsk は３’側のステムの開始位置、rek は３’側のステムの終了位置)とするときに、以下のいずれかが成立する。
【数４】
（１）、（２）、（３）のいずれかの関係である場合に、２つのステム候補S1、S2の関係はconsistentであると言う。
本研究では、２つのステム候補S1 = ( [ ls1, le1 ] , [ rs1, re1 ] ) , S2 = ( [ ls2, le2 ] , [ rs2, re2 ] ) がls1＜ls2 かつ（１）、（２）、（３）のいずれかの関係であるならば、S1からS2の向きに有向辺を付与し、辺にはその関係に応じて異なるラベルを付与することとする。
【０１１６】
「２．２．４ モデル化の特徴」
このようにモデル化を行った場合、明らかに次の著しい性質が成立する。この性質は、後にアルゴリズムを構築する際に非常に役に立つ。
「性質２．２」
２次構造として成立可能なステム候補の集合は、上述の方法でＲＮＡをグラフ化した際に、Cliqueな部分グラフでなければならない。
例１：図７は、ｔＲＮＡのステムグラフである。図７では、例えば、頂点の組み合わせ（1, 2, 8, 9）、（1, 2, 4, 5, 9）などがＲＮＡの２次構造として正当なステム候補のセットである。これに対して、ステム候補の集合（1, 3, 5）に対応する２次構造は存在しない。
我々のモデル化の手法では、ＲＮＡ配列集合の個々の配列に対してその可能性のあるステム候補を全て考慮したラベル付有向グラフを構築する点および頂点のラベルにはTaxonomyを考慮する点の２点を新しく提案している。本セクションの最初にも述べたとおり、ＲＮＡの２次構造を木構造やグラフでモデル化する方法はすでに提案されているが、本手法のようなモデル化の方法は今までには考えられてこなかった。従って、上記のモデル化手法は本論文の貢献のひとつであるといえる。
【０１１７】
「２．３ グラフマイニングとしての定式化」
我々が現在解決しようとしていＲＮＡの問題は以下のように述べられる。
「問題１」 ＲＮＡ配列集合に頻出するステムのパターンを全て抽出する。同時に各ステムパターンに対応するＲＮＡ配列のステムの集合（ＲＮＡ配列の２次構造）を特定する。
本セクションでは、上記の問題をグラフマイニングとして定式化を行う。まず、次の定義はグラフマイニング分野では非常に基本的なものである。
【０１１８】
「定義２．５（支持度（文献２））」
グラフの集合GS = [ G1,・・・, GN ] とTaxonomy TとグラフPに対して、
【数５】
をグラフPの支持度（support）と呼ぶ。支持度が０より大きいグラフをパターン（pattern）と呼ぶ。また、支持度が与えられたminsupより大きいパターンを頻出パターン（Frequent pattern）と呼ぶ。
前セクションの結果およびこの定義を用いて問題１を言い換えると次のようになる。
【０１１９】
「問題２」 グラフ集合GSとTaxonomy Tおよび支持度minsupが与えられている際に、Cliqueなパターンで支持度がminsup以上のものをすべて導出する。同時に、導出されたパターンに対応する各グラフの部分グラフを特定する。
一般に、与えられたグラフ集合から頻出パターン（Cliqueなパターンとは限らない）を完全に抽出する問題はグラフマイニングの問題として近年盛んに研究がなされている（FSSM（文献１２）、FSG（文献１３）、AGM（文献１４、１５）、AcGM（文献１６）、gSpan（文献１７））。ラベルにTaxonomyを用いた場合の一般的なグラフマイニングは（文献２）で提案された。今回は、ベースとなる一般のグラフマイニングアルゴリズムにはgSpanアルゴリズムを用いて、頂点ラベルにTaxonomyを考慮できるように変更を行った。また、後で述べる通り、抽出するパターンがCliqueなパターンであること（性質）を利用して探索の効率化を行っている。また、問題１を完全に解くことも可能であるが、本研究ではさらになる探索の効率化を行うために抽出されるパターンにいくつかの制約を課すことにする。
次に定義される過度に一般化されたパターンは、ラベルにTaxonomyを考慮した場合に出現するパターンであるがパターンとしての有用性は低い。
【０１２０】
「定義２．６（一般化パターン、過度に一般化されたパターン（文献２））」
パターンP1とP2のトポロジーが同型であるとする。
【数６】
であるとき、P1はP2の一般化パターン（generalized pattern）と呼ぶ。また、P2が存在して、
【数７】
を満たす場合、P1は過度に一般化されたパターン（over-generalized pattern）と呼ぶ。
以下は、Yanら（文献１８）により提案されたclosed patternの定義をTaxonomyを考慮した場合に拡張したものである。closed patternでないパターンもパターンとしての有用性は低い。
【０１２１】
「定義２．７（closed pattern（文献１８））」
グラフの集合GS = [ G1, G2,・・・, Gn ] とTxonomy Tが与えられているものとする。このとき、パターンPがclosed patternであるとは、
【数８】
を満たすパターンP' が存在しないことを言う。
（注意２．３） Yanら（文献１８）は、通常の部分グラフ（定義２．１）の意味でclosed patternを定義したが、ここではTaxonomyを用いた部分グラフ（定義２．３）の意味でclosed patternを定義している。定義より、この意味でClosedなパターンは、定義２．６で定義される過度に一般化された（over-generalized）パターンではない。
Taxonomyを考えることにより、柔軟なパターンの抽出が可能になる一方で、抽出されるパターンが増加することが懸念される。しかしながら、Taxonomyの上位のラベルばかりで構成されるパターンは、たとえ頻出していたとしてもあまり重要でない可能性が高い。このようなパターンがTaxonomyの上位のラベルばかりで構成されているかどうかを判定するために、パターンの一般化コストと呼ばれる概念を新たに定義する。
【０１２２】
「定義２．８（パターンの一般化コスト）」
グラフGとTaxonomy Tが与えられているものとする。このときパターンPの一般化コスト（generalization cost）：cost ( P ) を、
【数９】
と定義する。言い換えれば、パターンの一般化コストは、パターンを構成するラベルのコストの平均である。
以上の定義をもとに、最終的に我々が解くべきグラフマイニングの問題は以下となる。
【０１２３】
「問題３」 グラフの集合GS = [ G1, G2,・・・, Gn ] 、Taxonomy T、最小支持度minsup、最大一般化コストmaxcostが与えられた際に、以下の条件を満たすパターンを完全に抽出する。
（１）支持度がminsup以上（定義２．５を参照）
（２）Clique（定義２．４を参照）
（３）Closed patterns（定義２．７を参照）
（４）一般化コストがmaxcost以下（定義２．８を参照）
さらに、抽出されたパターンに対応する各グラフの部分グラフを全て特定する。
【０１２４】
「２．４ 理論」
本セクションでは、問題３を解くためのグラフマイニングアルゴリズムの理論的な部分について、出来る限りself-containedな形で記述を行う。以下の定義はグラフアルゴリズムの分野では基本的なものである。
【０１２５】
「定義２．９（DFS木、DFS添え字付け、前向きの辺、後ろ向きの辺（文献１９））」
本定義においてグラフは連結グラフであるとする。
（１）深さ優先木（DFS木、DFS Tree）：グラフを深さ優先探索した際に得られる木構造。
（２）DFS添え字付け（DFS Subscripting）：グラフの頂点にDFS木で探索される順番に従って番号付けをしたもの。またグラフGとDFS木Tに対してDFS subscriptingをGTと書く。ｉ番目の頂点をvi と表すとGT = [ vi ] と書ける。
（３）前向きの辺（Forward Edge）と後ろ向きの辺（Backward Edge）：グラフGと深さ優先木Tが与えられた際に、Gの辺の中でTに含まれるものを前向きの辺（Forward Edge）、含まれないものを後ろ向きの辺（Backward edge）と呼ぶ。前向きの辺を( vi, vj ) ( i＜j )、後ろ向きの辺を( vi, vj ) ( i＞j ) と表す。
（注意２．４） 開始頂点の選び方などにより、同一のグラフに対して複数の深さ優先木が存在する（すなわち複数のDFS Subscriptingが存在する）。
【０１２６】
「定義２．１０（文献２０）」
連結グラフ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 ] に対して順序関係を以下の通り定義する（これらはすべて半順序関係であることは容易に示せる）。
【数１０】
（注意２．５） DFS木Tを固定する限り、（１）の（ii）の条件は必要ない。ただし、（１）の（ii）の条件を入れることにより、グラフやそのDFS木が異なっている場合でも辺の比較が可能になる。
（注意２．６） 今後は特に誤解が無い限り辺( vi, vj ) を省略して ( i, j ) と書く。
この順序関係について以下の結果が成立する。
【０１２７】
「定理２．１（文献２０）」
グラフGとDFS木Tを固定したときに、定義２．１０の順序を合わせて定義されるEf, T∪Eb, T上の順序関係は、線形順序である。なお、集合( A,＜) が線形順序集合であるとは、（ｉ）∀a, b∈Aに対して、a＜bかつb＜cならばa＜c、かつ、（ｉｉ）∀a, b∈Aに対して、a＜bまたはb＜aが成り立つことである（一般的には「a＜a」と「a＜bかつb＜aならば、a = b」を条件に入れる場合も多いが、ここでは入れない）。
この定理により、グラフと深さ優先木を固定したときに、グラフに含まれる辺（前向きの辺または後ろ向きの辺のいずれか）には線形順序を与えることが出来る。さらに、頂点や辺のラベルを考慮して次のようにDFSコードと呼ばれる表現方法を定義する。
【０１２８】
「定義２．１１（DFSコード（文献２０））」
グラフGとDFS subscripting GTに対して辺を ( i, j, li, lj, l( i, j ) , d( i, j ) ) と表す。ここでli, lj はそれぞれｉ番目、ｊ番目の頂点のラベルを表す。l( i, j ) は辺( i, j )のラベルを表す。d( i, j ) は辺( i, j )の向き（ｉからｊの向きであれば＋１、ｊからｉの向きを−１とする）を表す。このとき、Gの辺を定理２．１の順序に従って並べた順列 [ ( i, j, li, lj, l( i, j ) , d( i, j ) ) ] をグラフGのDFSコード（DFS code）と呼び、code ( G, T )と書く。
（注意２．７） 上記のDFSコードの定義は原論文（文献２０）とは以下の点で異なる。
（１）グラフが有向グラフのため辺の方向に関する項d( i, j ) が存在する。
（２）ラベルの順序は、（fromlabel, tolabel, edgelabel, direction）の順番である（原論文では（fromlabel, edgelabel, tolabel）の順番）。これは、後に一般化コストによる枝狩りを行う際に重要になってくる。
DFSコードから辺をひとつ拡張して新しいDFSコードを作成する場合、定義２．１０の順序関係により任意に拡張を行うことは出来ず、以下の制限がある。
【０１２９】
「命題２．１（DFSコードの拡張の制限（文献２０））」
グラフGとDFS木Tが与えられているものとする。α = code ( G, T ) = ( a0, a1,・・・am ), ak = ( ik, jk ), ak+1 = ( ik+1, jk+1 ) とするとき以下が成立する。
（１）ak が前向きの辺かつak+1 が前向きの辺であるならば、
ik+1≦jk かつjk+1 = jk + 1
（２）ak が前向きの辺かつak+1 が後ろ向きの枝であるならば、
ik+1 = jk かつjk+1＜ik
（３）ak が後ろ向きの辺かつak+1 が前向きの辺であるならば、
ik+1≦ik かつjk+1 = ik + 1
（４）ak が後ろ向きの辺かつak+1 が後ろ向きの枝であるならば、
ik+1 = ik かつjk＜jk+1
（証明）DFS木の定義およびDFSコードの定義より明らかである。
【０１３０】
「定義２．１２（最右拡張（文献２０））」
パターンPとそのDFSコードに対して以下の拡張を最右拡張（Right-most extension）と呼ぶ。
（１）最右頂点から他の最右パスに含まれる頂点への辺の拡張（後ろ向きの拡張、backward extension）
（２）最右パスに含まれる頂点から、Pに含まれない新しい頂点への拡張（前向きの拡張、forward extension）
（注意２．８） 定義２．１２を使って性質２．１を言い換えれば、パターン（DFSコード）の拡張は最右拡張に限るということである。
任意の２つのDFS code（異なるグラフでもよい）の間に以下のようにして順序を与えることが可能である。
【０１３１】
「定義２．１３（DFS Lexicographic Order（文献２０））」
連結グラフGに対してZ ( G ) = [ code ( G, T )｜∀T：GのDFS木 ] と表す。さらにＺ = ∪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 に対して、α≦βとは、次の（１）または（２）が成立することである。
【数１３】
（注意２．９）
【数１４】
【０１３２】
「定義２．１４（最小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と呼ぶこともある。
【０１３３】
「定理２．２（文献２０）」
グラフGとG' が同型である必要十分条件はmin ( G ) = min ( G' ) となることである。
【０１３４】
「定義２．１５（DFSコードの親および子（文献２０））」
DFSコードα= ( a0, a1,・・・, am ) が与えられているとする。このとき妥当なDFSコードβ= ( a0, a1,・・・, am, b ) をDFS code αの子（child）、αはDFSコードβの親（parents）と呼ぶ（「性質２．１」を満たさなければならない）。αの子の集合をchildren ( α )と書く。
【０１３５】
「定義２．１６（DFS Code Tree（文献２））」
「親要素と子要素の関係が定義２．１５で与えられ、さらに同じ親の子要素の関係はDFS lexcographic orderで与えて得られるような、DFS codeを頂点とする木構造」を、「DFS code tree」と呼ぶ。
上で定義されているDFS code treeはDFSコードをノードとする順序木である。問題３はこの順序木の順序で探索を行っていくが、DFS code treeが全ての部分グラフを数え上げることが可能であることを保障するのが次の定理である。
【０１３６】
「定理２．３（DFS Code Tree Covering（文献２０））」
DFS Code Treeは全てのグラフの最小DFSコードを含む。
DFS Code Tree TとDFS code αが与えられたときに、Tにおけるαの祖先の集合をans ( α )、子孫の集合をdes ( α )と表す。
次の定理は、最小でないDFSコードを根とする部分木を枝狩りしても、全ての部分グラフを数え上げることが可能であることを保障している。
【０１３７】
「定理２．４（DFS Code Pruning（文献２０））」
グラフ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を含む。
（注意２．１０） 定理２．４により、DFS code treeの最小DFSコードでないDFS codeを根とする部分木は全て枝狩りを行っても全ての部分グラフを網羅可能である（完全性）。
定義より支持度に関して以下の単調性が成立することがわかる。これにより、支持度が与えられた最小支持度を下回ったパターンはそれ以上拡張する必要がないことが保障される。
【０１３８】
「命題２．２（支持度の逆単調性）」
【数１５】
ここまでの理論はYanらの貢献による。本研究ではYanらの理論をベースにラベルにTaxonomy情報およびその枝狩り手法（文献２）の統合を行う。つまり、定義２．１６で定義されるDFS code tree上を今回の制約を用いてさらに効率的に探索していく。さらに、cliqueなパターンのみを抽出することを利用した探索の効率化及びパターンの一般化コストによる枝狩り手法の提案を新たに行う。
導出パターンをCliqueなパターンに制限する場合には、DFS codeの子に対して「性質２．１」よりさらに強い制約を与えることが可能である。
【０１３９】
「命題２．３（抽出パターンの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コードを含む。
（１）ak が前向きの枝かつak+1 が前向きの枝であるならば、
k = 0 かつj0 = i1 = 1 かつj1 = 2
（２）ak が前向きの枝かつak+1 が後ろ向きの枝であるならば、
ik+1 = jk かつjk+1 = i0 ( = 0 )
（３）ak が後ろ向きの枝かつak+1 が前向きの枝であるならば、
ik = ik+1 かつjk+1 = ik +1かつik−2 = jk
（４）ak が後ろ向きの枝かつak+1 が後ろ向きの枝であるならば、
ik+1 = ik かつik+1 = ik
【０１４０】
（証明） （１）から（４）のいずれの条件も満たさない拡張によって得られられるDFSコードを根とする部分木にはCliqueなパターンを含まないことを示す。
（１）ak およびak+1 が前向きの枝であるとする。jk≠ik+1 とすると深さ優先木の定義から今後の拡張により後ろ向きの辺 ( jk+1, jk ) が拡張されることはない。よって jk = ik+1 としてよい。このとき、もしk≠0とするとik＞1 となり、定義２．１０を繰り返し使うと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 が前向きの枝であるならば、拡張を（１）に制限することにより探索されないパターンはすべてCliqueでないパターンとなる。
（２）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 ) は今後の辺の拡張によって得られることはない。よって、拡張を（２）に制限することにより探索されないパターンは全てCliqueなパターンではない。
（３）明らかに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 ) は存在しない。よって拡張を（３）に制限することにより探索されないパターンは全てCliqueなパターンではない。
（４）上と同様に（４）の制限を加えることにより探索されないパターンは全てCliqueなパターンではないことが示せる。
以上と定理２．３より題意が証明できた。
（注意２．１１） 以下ではDFS code treeとは子要素に上記の制限を加えたDFS code treeを意味するものとする。
一般にDFSコードαの最小性の判定は、αの最小DFSコードとαが等しいかどうかを比較することにより行われる。これは、グラフの同型性を判定することと実質的に等価であり多大な計算量を要する。しかしながら、抽出するパターンをCliqueなパターンに限る場合には、 以下の命題を用いることによりこのDFSコードの最小性の判定を回避することができる。
【０１４１】
「命題２．４（導出パターンの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コードは最小でない。
次の命題を用いると、一般化コストによる枝狩りを効率よく行うことが可能となる。
【０１４２】
「命題２．５（Cliqueと最大一般化コストの制限を用いた枝狩り）」
グラフの集合GSとTaxonomy Tが固定されているものとする。さらに、以下の仮定を置く。
（１）ラベルのTaxonomyは頂点にのみ存在し、辺ラベルの一般化コストは全て０である。
（２）GSの任意のラベルx∈V ( T ) とTaxonomy Tにおけるその任意の祖先yに対してx＜y を満たすラベル付けがなされている。
（３）ラベルx, yがx＜yを満たすならば、c ( x ) ≦ c ( y )
このとき、DFS code tree上で一般化コストがmaxcostより大きいDFS codeを根とする部分木を枝狩りした結果残るDFS code treeは、すべての一般化コストがmaxcost以下かつcliqueなパターンの最小DFSコードを含む。
（証明） 命題２．４により、パターンに新しい頂点ラベルが追加される（DFSコードを前向きの辺により拡張する）場合、追加される頂点のラベルはパターンのどの頂点ラベルとも等しいか、より大きい。このことと仮定を用いると容易に証明できる。
（注意２．１２） 前出の「分類データの生成」のセクションで説明された方法により構築されるタクソノミデータが上記の命題の条件を満たすことは容易にわかる。
（注意２．１３） このPropositionは導出パターンをCliqueなパターンに制限しない場合には成立しない。また、DFSコードの順序付けを定義２．１１のようにしなければ成立しない（辺のラベルより２つの頂点ラベルの方が順序付けに対する優先度が高い）。さらに、辺のラベルにもTaxonomyを考慮した場合にも成立しない。
最後に、導出パターンをover-generalizedでないパターンに制限する場合に対する枝狩りの基本となる理論について述べる。
【０１４３】
「定義２．１７（重みつき支持度（文献２））」
グラフGとTaxonomy Tが与えられた際に、パターンPのグラフGにおける出現回数を
【数１６】
と表す。このとき、グラフセットGS = [ Gi ] を固定したとき、パターンPに対して
【数１７】
をパターンPの重みつき支持度（weighted support）と呼ぶ。ここで、
【数１８】
【０１４４】
「命題２．６」 グラフの集合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をそれぞれα，βとするとき、α＜βとなることを示せばよい。一般化パターンの定義と、ラベル付けの仮定により容易に示せる。
【０１４５】
「命題２．７（文献２）」 DFS code tree上のDFS code Pに対して、Pより以前に出てきたDFSコードP' で、P（の表現するグラフ）がP'（の表現するグラフ）の一般化されたパターンでありかつsupw ( P ) = supw ( P' ) を満たすものが存在するとき、DFSコードPを根にもつ部分木を枝狩りした結果残る部分木は全てのover-genralizedでない部分グラフの最小DFSコードを含む。
（注意２．１４） この命題を用いて過度に一般化されたパターンの枝狩りを効率良く行うためには、あるパターンの特殊化パターンはそのパターンより以前に探索されていなければならない。命題２．６により、任意のパターンはその特殊化パターンよりDFS Lexicographic orderで後に出現するため、DFS lexicographic orderでDFS code treeを探索すれば、上記の枝狩りは効率よく行えることがわかる。
（注意２．１５） この条件による枝狩りだけでは、全てのover-generalizedでないパターンをDFS code treeの探索の段階で枝狩りをすることはできない。枝狩りにもれたパターンは後処理で削除する。
【０１４６】
「２．５ アルゴリズム」
本セクションでは、セクション２．４で述べた理論に基づいて構築されるアルゴリズムについて述べる。その骨格部分は、図１７のアルゴリズム１（Algorithm 1）である。アルゴリズムの入力はＲＮＡ配列の集合（複数のファミリーや未知のファミリーが含まれていても構わない）と最小支持度（minimum support）、最大一般化コスト（maximum generalization cost）である。まず、セクション２．２に述べる方法によりＲＮＡ配列集合からグラフ集合GSおよび頂点ラベルのTaxonomy Tを構築する（line 2）。次にGSから辺のサイズが１の頻出でありかつ一般化コストがmaxcost以下のパターンを抽出する。ここで頻出パターンと一般化コストがmaxcost以下のパターンだけを考えれば十分なのは、命題２．２と命題２．５により保障されている。その後、Cinitial をDFS lexicographi order（定義２．１３）でソートし、その順番でCinitialのパターンに対して、アルゴリズムGraphMining （アルゴリズム２（Algorithm 2）（図１８））を呼び出す。最後に、PSからnon-closed patternおよびnon-cliqueパターンを除く（line 8）。
【０１４７】
アルゴリズム２（Algorithm 2）は提案手法におけるグラフマイニングの骨格部分である。まず、現在考えているパターンsの最小性を判定し、最小でないものに関しては探索を打ち切る（line 3）。この操作によりアルゴリズムの完全性が保たれることは定理２．４による。この際、DFS codeの最小性判定にはコストがかかるため命題２．４を用いて最小性の判定をやらなくていいものに関しては行わない。次に一般化コストの判定を行い、一般化コストがmaxcostより大きいものに関しては探索を打ち切る。これを保障するのが命題２．５である。最後にover-generalizedなパターンであるかどうかの判定を行い、over-generalizedなパターンであれば探索を打ち切る（line 4）。この判定は、命題２．７により行うが注意２．１４にも述べたとおりこの段階ですべてのover-generalizedなパターンを除くことはできない。以上で枝狩りをされなかったパターンはPSに保存する。ここで注意するのは、PSにはcliqueでないパターンも格納する（line 5）。これはover-generalizedなパターンの判定に使用するためである。
line 6では辺を１つ拡張することにより、現在のパターンsの拡張を行う。ここでは命題２．３の条件を満たすようにパターンを拡張し、頻出である（支持度がminsupより大きい）パターンをCに格納する（line 6）。その後、Cのパターンに対してDFS lexicographic orderの順番で再帰的にアルゴリズムGraphMiningを呼び出す。
【０１４８】
「３ 実装」
本アルゴリズムを実装したソフトウェアRNAminer（RNA stem pattern miner）を開発した。実装はC++言語およびSTL / Boostライブラリを用いて行った。さらに現在の実装においては、グラフの同型性判定ライブラリとしてVFlib 2.0（文献２１）をクラスタリングのライブラリとしてCluster 3.0（文献２２）を用いている。また、塩基対確率行列の計算にはVienna RNA package（文献２３）のライブラリを用いている。
なお、ステム候補の抽出の部分で塩基対単位でギャップが許されてよい。また、ステム候補は塩基対の極大集合として抽出するので、ステム候補間が若干オーバラップしていても辺を与えてよい。
【０１４９】
「参考文献」
以下の参考文献のうち、（文献３）は（非特許文献１２）と同じであり、（文献５）は（非特許文献１７）と同じであり、（文献６）は（非特許文献１６）と同じである。
（文献１）
Ramakrishnan Srikant and Rakesh Agrawal. Mining generalized association rules. Future Gener. Comput. Syst., Vol. 13, No. 2-3, pp. 161-180, 1997.
（文献２）
Akihiro Inokuchi. Mining generalized substructures from a set of labeled graphs. In ICDM, pp. 415-418. IEEE Computer Society, 2004.
（文献３）
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.
（文献４）
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.
（文献５）
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.
（文献６）
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.
（文献７）
Daniela Fera, Namhee Kim, Nahum Shiffeldrim, Julie Zorn, Uri Laserson, Hin Hark Gan, and Tamar Schlick. RAG: RNA-As-Graphs web resource. BMC Bioinformatics, Vol. 5, p. 88, Jul 2004.
（文献８）
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.
（文献９）
Robert J Klein and Sean R Eddy. RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics, Vol. 4, p. 44, Sep 2003.
（文献１０）
T F Smith and M S Waterman. Identification of common molecular subsequences. J Mol Biol, Vol. 147, No. 1, pp. 195-197, Mar 1981.
（文献１１）
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.
（文献１２）
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.
（文献１３）
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.
（文献１４）
Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda. An apriori-based algorithm for mining frequent substructures from graph data. In PKDD '00: Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, pp. 13-23, London, UK, 2000. Springer-Verlag.
（文献１５）
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.
（文献１６）
Akihiro Inokuchi, Takashi Washio, Kunio Nishimura, and Hiroshi Motoda. A Fast Algorithm for Mining Frequent Connected Subgraphs. IBM Research. In IBM Research Report, 2002.
（文献１７）
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.
（文献１８）
Xifeng Yan and Jiawei Han. Closegraph: mining closed frequent graph patterns. In KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 286-295, New York, NY, USA, 2003. ACM Press.
（文献１９）
T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms (2nd edition). MIT Press, 2001.
（文献２０）
Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. 2002.
（文献２１）
C. Goggia and S. Tortorella. Graph matching: A fast algorithm and its evaluation. 1999.
（文献２２）
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.
（文献２３）
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.
（文献２４）
Bernhart SH, Hofacker IL, and Stadler PF. Local RNA base pairing probabilities in large sequences. Bioinformatics, Dec 2005. JOURNAL ARTICLE.
【０１５０】
以上に本発明の好適な実施の形態を説明した。しかし、本発明は上述の実施の形態に限定されず、当業者が本発明の範囲内で上述の実施の形態を変形可能なことはもちろんである。
【産業上の利用可能性】
【０１５１】
以上のように、本発明は、複数のＲＮＡ配列データからコンピュータ処理によって２次構造モチーフを抽出することができ、バイオインフォマティクス技術として有用である。
【図面の簡単な説明】
【０１５２】
【図１】ＤＮＡおよびＲＮＡの配列を示す図である。
【図２】ＲＮＡの局所的な２次構造の例を示す図である。
【図３】ＲＮＡの２次構造の例を示す図である。
【図４】本実施の形態のＲＮＡ配列情報処理を実現するコンピュータを示す図である。
【図５】本実施の形態のＲＮＡ配列情報処理の全体像を示す図である。
【図６】本実施の形態のＲＮＡ配列情報処理装置の機能ブロック図である。
【図７】塩基対確率行列を示す図である。
【図８】ステムグラフを示す図である。
【図９】ステムグラフを示す図である。
【図１０】ステム候補間の３タイプの接続関係を示す図である。
【図１１】分類データとしてのタクソノミを示す図である。
【図１２】本実施の形態におけるグラフ解析の原理を示す図である。
【図１３】分類データを用いたステムパターンの比較処理を示す図である。
【図１４】ステムパターンの一般化コストを示す図である。
【図１５】支持度の定義を示す図である。
【図１６】パターン探索アルゴリズムのＤＦＳツリーを示す図である。
【図１７】本実施の形態のRNA配列情報処理を実現するアルゴリズムを示す図である。
【図１８】本実施の形態のRNA配列情報処理を実現するアルゴリズムを示す図である。
【符号の説明】
【０１５３】
２１ ＲＮＡ配列情報処理装置
２３ 配列データ入力部
２５ 配列データ記憶部
２７ ステム候補抽出部
２９ ステム候補記憶部
３１ グラフ生成部
３３ グラフ記憶部
３５ 分類データ生成部
３７ 分類データ記憶部
３９ グラフ解析部
４１ 最小支持度入力部
４３ 最大一般化コスト入力部
４５ 出力部
４７ ２次構造データ生成部
【特許請求の範囲】
【請求項１】
複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出するステム候補抽出部と、
各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成するグラフ生成部と、
前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出するグラフ解析部と、
を備えたことを特徴とするＲＮＡ配列情報処理装置。
【請求項２】
前記グラフ生成部は、前記ＲＮＡ配列上での各ステム候補対の位置関係に応じた向きを、前記各ステム候補対を結ぶ辺のラベルに付与し、
前記グラフ解析部は、前記複数のステムグラフから、対応する辺の向きが同じ前記部分グラフを抽出することを特徴とする請求項１に記載のＲＮＡ配列情報処理装置。
【請求項３】
前記グラフ生成部は、各ステム候補対の接続関係が並列、埋込み、重複のいずれかに属するかの情報を、前記各ステム候補対を結ぶ辺のラベルに付与し、
前記グラフ解析部は、前記複数のステムグラフから、対応する辺の前記接続関係が同じ前記部分グラフを抽出することを特徴とする請求項１または２に記載のＲＮＡ配列情報処理装置。
【請求項４】
前記グラフ生成部は、前記並列、埋込みおよび重複のいずれにも該当しないステム候補対を辺での接続対象から除外することを特徴とする請求項３に記載のＲＮＡ配列情報処理装置。
【請求項５】
前記グラフ生成部は、各頂点が部分グラフ内のすべての他の頂点と辺で結ばれる完全部分グラフを抽出することを特徴とする請求項１〜４のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項６】
前記複数のステムグラフに含まれる前記複数のステム候補を類似性に基づいて分類する分類データを生成する分類データ生成部を含み、
前記グラフ解析部は、前記複数のステムグラフから、対応する頂点のステム候補が同じ分類に属する前記部分グラフを抽出することを特徴とする請求項１〜５のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項７】
前記分類データ生成部は、前記分類データとして、前記複数のステム候補を、類似範囲の広さが下位層から上位層へ向かって増大するように階層的にクラスタリングを行ったタクソノミデータを生成し、
前記グラフ解析部は、前記タクソノミデータに基づき、対応する頂点のステム候補が下位層では異なる分類に属しても上位層では同一分類に属する前記部分グラフを抽出することを特徴とする請求項６に記載のＲＮＡ配列情報処理装置。
【請求項８】
前記タクソノミデータにて階層に応じて増大する一般化コストの最大許容値である最大一般化コストを入力する最大一般化コスト入力部を含み、
前記グラフ解析部は、前記最大一般化コスト以下の一般化コストを有する前記部分グラフを抽出することを特徴とする請求項７に記載のＲＮＡ配列情報処理装置。
【請求項９】
前記分類データ生成部は、ステム候補対の類似性を表す類似性パラメータを、ステム候補対の配列相同性、ステム候補により形成されるループの距離の類似性、および、ＲＮＡ配列内でのステム候補の位置の類似性の少なくとも一つに応じて求めることを特徴とする請求項６〜８のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項１０】
前記複数のステムグラフにおける前記部分グラフの支持度の最小許容値である最小支持度を入力する最小支持度入力部を含み、
前記グラフ解析部は、前記最小支持度以上の支持度を有する前記部分グラフを抽出することを特徴とする請求項１〜９のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項１１】
前記ステム候補抽出部は、分子構造のエネルギに基づいて前記ＲＮＡ配列上の任意の２つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域を前記ステム候補として抽出することを特徴とする請求項１〜１０のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項１２】
複数のＲＮＡ配列からコンピュータ処理によって２次構造モチーフを抽出するＲＮＡ配列情報処理方法であって、
複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出し、
各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、
前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出する、
ことを特徴とするＲＮＡ配列情報処理方法。
【請求項１３】
複数のＲＮＡ配列から２次構造モチーフを抽出する配列情報処理をコンピュータに実行させるＲＮＡ配列情報処理プログラムであって、
複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出し、
各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、
前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出する、
処理を前記コンピュータに実行させることを特徴とするＲＮＡ配列情報処理プログラム。
【請求項１】
複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出するステム候補抽出部と、
各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成するグラフ生成部と、
前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出するグラフ解析部と、
を備えたことを特徴とするＲＮＡ配列情報処理装置。
【請求項２】
前記グラフ生成部は、前記ＲＮＡ配列上での各ステム候補対の位置関係に応じた向きを、前記各ステム候補対を結ぶ辺のラベルに付与し、
前記グラフ解析部は、前記複数のステムグラフから、対応する辺の向きが同じ前記部分グラフを抽出することを特徴とする請求項１に記載のＲＮＡ配列情報処理装置。
【請求項３】
前記グラフ生成部は、各ステム候補対の接続関係が並列、埋込み、重複のいずれかに属するかの情報を、前記各ステム候補対を結ぶ辺のラベルに付与し、
前記グラフ解析部は、前記複数のステムグラフから、対応する辺の前記接続関係が同じ前記部分グラフを抽出することを特徴とする請求項１または２に記載のＲＮＡ配列情報処理装置。
【請求項４】
前記グラフ生成部は、前記並列、埋込みおよび重複のいずれにも該当しないステム候補対を辺での接続対象から除外することを特徴とする請求項３に記載のＲＮＡ配列情報処理装置。
【請求項５】
前記グラフ生成部は、各頂点が部分グラフ内のすべての他の頂点と辺で結ばれる完全部分グラフを抽出することを特徴とする請求項１〜４のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項６】
前記複数のステムグラフに含まれる前記複数のステム候補を類似性に基づいて分類する分類データを生成する分類データ生成部を含み、
前記グラフ解析部は、前記複数のステムグラフから、対応する頂点のステム候補が同じ分類に属する前記部分グラフを抽出することを特徴とする請求項１〜５のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項７】
前記分類データ生成部は、前記分類データとして、前記複数のステム候補を、類似範囲の広さが下位層から上位層へ向かって増大するように階層的にクラスタリングを行ったタクソノミデータを生成し、
前記グラフ解析部は、前記タクソノミデータに基づき、対応する頂点のステム候補が下位層では異なる分類に属しても上位層では同一分類に属する前記部分グラフを抽出することを特徴とする請求項６に記載のＲＮＡ配列情報処理装置。
【請求項８】
前記タクソノミデータにて階層に応じて増大する一般化コストの最大許容値である最大一般化コストを入力する最大一般化コスト入力部を含み、
前記グラフ解析部は、前記最大一般化コスト以下の一般化コストを有する前記部分グラフを抽出することを特徴とする請求項７に記載のＲＮＡ配列情報処理装置。
【請求項９】
前記分類データ生成部は、ステム候補対の類似性を表す類似性パラメータを、ステム候補対の配列相同性、ステム候補により形成されるループの距離の類似性、および、ＲＮＡ配列内でのステム候補の位置の類似性の少なくとも一つに応じて求めることを特徴とする請求項６〜８のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項１０】
前記複数のステムグラフにおける前記部分グラフの支持度の最小許容値である最小支持度を入力する最小支持度入力部を含み、
前記グラフ解析部は、前記最小支持度以上の支持度を有する前記部分グラフを抽出することを特徴とする請求項１〜９のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項１１】
前記ステム候補抽出部は、分子構造のエネルギに基づいて前記ＲＮＡ配列上の任意の２つの塩基の塩基対形成確率を求めた塩基対確率行列から、連続する塩基対領域を前記ステム候補として抽出することを特徴とする請求項１〜１０のいずれかに記載のＲＮＡ配列情報処理装置。
【請求項１２】
複数のＲＮＡ配列からコンピュータ処理によって２次構造モチーフを抽出するＲＮＡ配列情報処理方法であって、
複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出し、
各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、
前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出する、
ことを特徴とするＲＮＡ配列情報処理方法。
【請求項１３】
複数のＲＮＡ配列から２次構造モチーフを抽出する配列情報処理をコンピュータに実行させるＲＮＡ配列情報処理プログラムであって、
複数のＲＮＡ配列データの各々から、ＲＮＡ２次構造の複数のステム候補を抽出し、
各ＲＮＡ配列データから抽出された前記複数のステム候補の各々を頂点として有し、頂点間を辺で結んだステムグラフを生成し、
前記複数のＲＮＡ配列からそれぞれ生成された複数の前記ステムグラフを分析して、グラフ形状が類似し、対応する頂点のステム候補が類似し、前記複数のステムグラフに頻出する部分グラフを、ＲＮＡ２次構造モチーフを表す頻出ステムパターンとして抽出する、
処理を前記コンピュータに実行させることを特徴とするＲＮＡ配列情報処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２００７−２２６７００（Ｐ２００７−２２６７００Ａ）
【公開日】平成１９年９月６日（２００７．９．６）
【国際特許分類】
【出願番号】特願２００６−４９６９４（Ｐ２００６−４９６９４）
【出願日】平成１８年２月２７日（２００６．２．２７）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成１７年度経済産業省委託研究「戦略的技術開発委託（機能性ＲＮＡプロジェトに係るもの）」産業活力再生特別措置法第３０条の適用を受ける特許出願
【出願人】（３０１０２１５３３）独立行政法人産業技術総合研究所 (6,529)
【出願人】（５９２１３１９０６）みずほ情報総研株式会社 (187)
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
【公開日】平成１９年９月６日（２００７．９．６）
【国際特許分類】
【出願日】平成１８年２月２７日（２００６．２．２７）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成１７年度経済産業省委託研究「戦略的技術開発委託（機能性ＲＮＡプロジェトに係るもの）」産業活力再生特別措置法第３０条の適用を受ける特許出願
【出願人】（３０１０２１５３３）独立行政法人産業技術総合研究所 (6,529)
【出願人】（５９２１３１９０６）みずほ情報総研株式会社 (187)
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
[ Back to top ]