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

开发大规模字符串数据分析的算法和数据结构

• 批准号: 14J09151
• 负责人: 小野寺 拓
• 金额: $ 0.9万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2014
• 资助国家: 日本
• 起止时间: 2014-04-25 至 2016-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14J09151/
• 关键词: アルゴリズム; タンパク質立体構造解析; 機械学習; 文字列カーネル; 接尾辞木; タンパク質立体構造; contact map

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

In recent years, the importance of the method of extracting useful information has increased due to the large number of text columns arranged in the list. The purpose of this study is to explore the efficient implementation of large-scale text analysis. In the past year, the existing text analysis method was developed, and the high-speed analysis method of the three-dimensional structure was developed. The specific method was determined. The development of qualitative three-dimensional structure identification method, the acquisition of multiple three-dimensional structure information, the standard similarity of three-dimensional structure, the calculation time of multiple three-dimensional structure identification methods, and the difficulty of large-scale analysis. A new method for calculating the similarity and efficiency of solid structures is developed. The similarity is calculated by using the existing structure of the character string search, the structure of the character string search, and the basic structure of the character string search. A kind of similarity between them is called SVM, which is a kind of combination of three-dimensional structure. This year's survey of the usefulness of the previous year's records shows that the improvement of the theory and the evaluation of the results have been carried out. The former is related to the implementation of the proposal, the design of the seed, the prediction of the SVM, the calculation of the amount of the seed, the development of the seed The latter is similar to the existing method, and the accuracy of the classification is less than 300 times higher than that of the SCOP. The results of this research include the preparation of a draft paper, the preparation of a doctoral paper submitted to future international conferences, and the preparation of a doctoral paper submitted by the author of this research.