Abstract今年度の、主な研究成果は、自らが設計したRNAのペアワイズアライメントアルゴリズムをローカルマルチプルアライメントへと拡張し、論文として出版したことである。これは、複数本の近縁種の配列が与えられたら、効率よく局所的に保存されたRNA部位を発見することを行う。これまでに、このタスクを行う手法は存在したが、精度が悪いか実行速度が遅いという点で問題があった。この問題に対して、田部井さんは精度と実行時間において実用性のある手法を開発した。これにより、ゲノム配列中から効率よくRNAを発見することが可能となった。実装したソフトウェアーをウェブにて公開し、世界中の研究者からアクセス可能とした。その他、線形グラフからの効率的なマイニングアルゴリズムの設計及び実装を行った。線形グラフとは、ノードに全順序けられたグラフである。タンパク質のコンタクトマップや、自然言語の文章の係り受け関係などを表現したグラフが線形グラフのインスタンスとなる。ノードの順序を利用することにより、エッジも全順序を与えることができる。このグラフ上で、逆探索法を用いることにより、部分グラフの列挙アルゴリズムを設計を行った。逆探索法とは、列挙アルゴリズムの設計技法の1つであり、同型計画法などと同様に重要なアルゴリズム設計技法のひとつである。設計したアルゴリズムを実装し、コンタクトマップやセンテンスデーターで計算機実験を行うことにより、提案手法が、従来の部分グラフ列挙アルゴリズムよりも高速であることを示した。