Non-coding RNAs (ncRNAs) show a unique evolutionary process where the substitutions of distant bases are correlated in order to conserve the secondary structure of the ncRNA molecule. Although their functions often depend on their 3D-structures rather than their primary sequence, the existence of conserved secondary structures among phylogenetic relatives highlights their functional importance. Therefore, alignment algorithms for RNA sequences should take into account both the primary sequence and the secondary structures.

The Sankoff algorithm simultaneously provides solutions to the structure prediction and alignment problem. However, the original version of the Sankoff algorithm is impractical, because of its prohibitive computational cost. Therefore, an efficient structural alignment algorithm for RNA sequences is required. In this thesis, we propose fast and accurate comparison methods of RNA sequences by stem candidate representation. Stem candidates are a set of potential stems as continuous base-pairs in a secondary structure of an RNA sequence. The computational biology of RNA secondary structure has a long history. First method to predict the secondary structure of an RNA sequence was developed about 40 yeas ago. The methods for analyzing ncRNAs have extremely advanced, recently. Especially, various algorithm designing techniques, machine learning techniques and data mining techniques have been applied to RNA secondary structure prediction and structural alignment of ncRNAs. Combining these techniques, we also show that representing RNA sequences as stem candidates is an effective strategy for designing comparison methods for ncRNAs.

First, we deal with the pairwise alignment problem of RNA sequences. The functions of ncRNAs are strongly related to their secondary structures, but it is known that a secondary structure prediction of a single sequence is not reliable. Therefore, we have to collect similar RNA sequences with a common secondary structure for the analyses of a new non-coding RNA without knowing the exact secondary structure itself. Because we often want to compare a large number of cDNA sequences or to search similar RNAs in the whole genome sequences, much faster algorithms are required. We propose an efficient pairwise alignment algorithm based on fixed-length stemfragments, implemented in SCARNA (Stem Candidate Aligner for RNAs).

We next deal with the global multiple alignment problem of ncRNAs. Multiple alignments of ncRNAs are useful in order to accurately predict secondary structures of ncRNAs, identify novel ncRNAs from genomic sequences and analyze phylogeny of ncRNAs. We propose a novel global multiple alignment method, implemented in MXSCARNA (Multiplex SCARNA),which is an extension of our pairwise alignment method.

We then deal with the local multiple alignment problem of ncRNAs. Recently, there has been intense focus on multiple alignment investigations for the detection of ncRNAs; however, most of the proposed methods are designed for global multiple alignments. For this reason, these methods are not appropriate to identify locally conserved ncRNAs among genomic sequences. A more efficient local multiple alignment method for the detection of ncRNAs is required. We propose a local multiple alignment method, implemented in SCARNA_LM (SCARNA Local Multiple), as an application of our proposed pairwise alignment algorithm and global multiple alignment method.

Finally, we discuss efficient methods for finding frequent secondary structures from a set of unaligned RNA sequences by means of reverse search techniques. Reverse search is a general scheme for designing efficient algorithms for hard enumeration problems. A state-of-the-art method propose an enumeration method of RNA secondary structures by the gSpan algorithm, which is a graph mining algorithm. However, the computational time of the gSpan algorithm is exponential for the size of graphs. We propose a polynomial time algorithm for this problem.

Through all these topics, we present efficient comparison methods of ncRNAs.

RNAの二次構造を配列から予測する問題は、40年近く研究の歴史がある。近年は 機能を持ったnon-coding RNAの研究が進展する中で、塩基配列としては異なっていても、二次構造的には類似しているRNA配列を、アラインメントにより検出する問題が注目を集めている。

しかしながらRNAの二次構造予測は計算コストが高くつくことが知られている。著名な Sankoff のアルゴリズムも、配列の長さを N としたとき最悪計算量が O(N6) にも達するため、現実的な時間で動作させることが困難である。そのため、精度をできるだけ保持しながら高速にRNAの二次構造を予測することが大切な基準となっている。さらに、異なるRNA配列を比較して、進化的に保存された構造を予測して、アラインメントすることは自明でない。特にマッチ率が低い場合でも感度良く構造的類似性を検出するのは困難である。

田部井は、RNA二次構造の中で、ステム(塩基部分配列が相補的に結合して比較的長い棒状の骨格を構成する部分)に注目した。そして、あらかじめステムの候補を列挙した後に、それをガイドにしてRNA二次構造を予測する効率的な計算アルゴリズムを考案した。最悪計算量が O(N3) に抑えられており、記憶領域もO(N2) 程度消費するだけで済むように実用性を重視している。注目の精度であるが、様々なベンチマークテストを使って検証した結果、マッチ率が低い RNA配列からも高い精度で構造を予測できることを実証した。

田部井は、この二次構造を鑑みて2つのRNA配列のアラインメントを計算するアルゴリズムを、多数のRNA配列をアラインメントする問題へと拡張している。さらに、全体的な類似性を検出する大域的アラインメント、部分的な類似性を検出する局所的アラインメントという2種類の場合にも拡張している。どの場合においても、精度を落とさずに高速化することに成功している。本分野において国際的評価も高くBioinformatics 誌に2つの論文を報告している。

なお、本論文第2章は、津田宏治、木立尚孝、金大真、浅井潔との共同研究であるが、論文提出者が主体となって分析及び検証を行ったもので、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。