大規模文字列データ解析のためのアルゴリズムとデータ構造の開発

近年ウェブページやゲノム配列などの大量の文字列データが安価に得られるようになったことで、これらから有用な情報を抽出するための手法の重要性が増している。本研究の目的は大規模文字列解析を効率的に行うためのアルゴリズムとデータ構造の開発である。前年度までに、既存の文字列解析手法を発展させタンパク質立体構造のための高速解析手法を開発する、という課題を設定し、具体的な方法も大まかに決定していた。タンパク質立体構造同定法の発展により、多くの立体構造情報が得られるようになってきているが、立体構造に対する標準的な類似度である構造アラインメントは多くの計算時間が必要であり、大規模データ解析に応用困難である。そこで我々はタンパク質立体構造に対する新しい類似度とその効率的な計算法を開発した。この類似度は文字列検索のアイディアに基づくため、二次元接尾辞木という既存のデータ構造を応用し、構造アラインメントよりも小さい計算量で求められる。また、この類似度はカーネル関数の一種になっており、サポートベクターマシン（SVM）と組み合わせて立体構造の教師あり分類に応用可能である。本年度は前年度までに得られた上記のアイディアの有用性を調査するため、さらなる理論的改善および、実験による評価を行った。前者に関しては提案手法をより実践的にするための変種の設計と、SVMの予測をデータベースのサイズによらない計算量で行うためのアルゴリズムを開発した。後者については、タンパク質データベースSCOPを用いた実験を行い、提案手法は類似の既存手法と殆ど遜色ない精度の分類を、少なくとも３００倍以上高速に行えることを確認した。また、これらの結果をまとめた論文の草稿を作成し、今後国際会議に投稿予定であるほか、本研究提案者の博士論文にも一部、本研究で得られた成果を含めた。

近年ウェブページやゲノム配列などの大量の文字列データが安価に得られるようになったことで、これらから有用な情報を抽出するための手法の重要性が増している。本研究の目的は大規模文字列解析を効率的に行うためのアルゴリズムとデータ構造の開発である。前年度までに、既存の文字列解析手法を発展させタンパク質立体構造のための高速解析手法を開発する、という課題を設定し、具体的な方法も大まかに決定していた。タンパク質立体構造同定法の発展により、多くの立体構造情報が得られるようになってきているが、立体構造に対する標準的な類似度である構造アラインメントは多くの計算時間が必要であり、大規模データ解析に応用困難である。そこで我々はタンパク質立体構造に対する新しい類似度とその効率的な計算法を開発した。この類似度は文字列検索のアイディアに基づくため、二次元接尾辞木という既存のデータ構造を応用し、構造アラインメントよりも小さい計算量で求められる。また、この類似度はカーネル関数の一種になっており、サポートベクターマシン（SVM）と組み合わせて立体構造の教師あり分類に応用可能である。本年度は前年度までに得られた上記のアイディアの有用性を調査するため、さらなる理論的改善および、実験による評価を行った。前者に関しては提案手法をより実践的にするための変種の設計と、SVMの予測をデータベースのサイズによらない計算量で行うためのアルゴリズムを開発した。後者については、タンパク質データベースSCOPを用いた実験を行い、提案手法は類似の既存手法と殆ど遜色ない精度の分類を、少なくとも３００倍以上高速に行えることを確認した。また、これらの結果をまとめた論文の草稿を作成し、今後国際会議に投稿予定であるほか、本研究提案者の博士論文にも一部、本研究で得られた成果を含めた。