文字列属性を含む多属性データからのパターン発見アルゴリズムに関する研究

字符串属性等多属性数据的模式发现算法研究

• 批准号: 15700121
• 负责人: 坂内 英夫
• 金额: $ 2.05万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15700121/
• 关键词: パターン発見; 接尾辞木; 接尾辞配列; 索引構造; suffix tree

本年度は前年度に扱った,文字列属性中の出現が実数値属性との相関が高い様なパターンを発見する,相関パターン発見問題を更に発展させた.主な成果は以下の通りである.●2つの部分文字列パターンの論理的組み合わせを探索するアルゴリズムについて:接尾辞木(Suffix Tree)と言うデータ構造を用いる事で,最適なパターンの組をデータ中の文字列の長さの総和をNとした時にO(N^2)時間で求める事ができる新しいアルゴリズムを示した.更にアルゴリズムを一般化し,k個のパターンの最適な組み合わせがO(N^k)時間で求められる事を示した.また,接尾辞配列(Suffix Array)と言うデータ構造を用いた同アルゴリズムの効率の良い実装を示した.●2つの部分文字列パターンの論理的組み合わせに関して,更に出現位置に関する制約を加えた場合にもO(N^2)時間で最適なものを求める事ができるアルゴリズムを示した.●アルゴリズムを酵母及びヒトのマイクロアレイ実験によって得られたmRNAの分解速度(半減期)を測定した数値データと,mRNAの分解に関係すると言われている3'UTR配列を組にしたデータに対して適用した.得られたパターンはmRNAの分解に関係すると言われる蛋白が結合する配列を一部含んでおり,アルゴリズムの有用性を示す事ができた.

This year, compared to the previous year, the number of attributes appearing in the text column is higher than the number of attributes appearing in the text column. The main achievement is to pass through the following.●2. The logical combination of some text strings is explored in the following way: Suffix Tree and the structure of text strings are used, and the optimal combination of text strings in the text strings is found in the O(N^2) time table. In addition, the optimal combination of k different types of objects is O(N^k) time. Suffix Array is used to describe the structure of the system and to demonstrate the effectiveness of the system.●2. Some text columns are composed of logical elements, such as the relevant elements, the relevant elements, the relevant constraints, and the O(N^2)-time optimal elements. The speed of mRNA decomposition (half-time) was measured by yeast and yeast, and the relationship between mRNA decomposition and 3'UTR alignment was determined. The results show that the protein binding sequence is partially composed of the protein binding sequence and the protein binding sequence.

项目成果

Hideo Bannai, et al.: "Inferring strings from graphs and arrays"Lecture Notes in Computer Science (Mathematical Foundations of Computer Science (MFCS 2003)). 2747. 208-217 (2003)

Hideo Bannai 等人：“从图形和数组推断字符串”计算机科学讲义（计算机科学数学基础 (MFCS 2003)）。

An O(N^2) Algorithm for Discovering Optimal Boolean Pattern Pairs

一种用于发现最佳布尔模式对的 O(N^2) 算法

• 发表时间: 2004
• 期刊: IEEE/ACM Trans.Comp.Biol.Bioinfo. 1・4
• 作者: Hideo Bannai et al.

Finding Optimal Pairs of Patterns

寻找最佳模式对

• 发表时间: 2004
• 期刊: Lecture Notes in Bioinformatics (WABI2004) 3240
• 作者: Hideo Bannai et al.;Shunsuke Inenaga et al.;Hideo Bannai et al.
• 通讯作者: Hideo Bannai et al.

Efficiency Finding Regulatory Elements using correlation with Gene Expression

利用与基因表达的相关性高效寻找调控元件

• 发表时间: 2004
• 期刊: Journal of Bioinformatics and Computational Biology 2・2
• 作者: Hideo Bannai et al.;Shunsuke Inenaga et al.;Hideo Bannai et al.;Hideo Bannai et al.
• 通讯作者: Hideo Bannai et al.

Finding Optimal Pairs of Cooperative and Competing Patterns with Bounded Distance

寻找有界距离的最佳合作和竞争模式对

• 发表时间: 2004
• 期刊: Lecture Notes in Computer Science (Discovery Science (DS2004)) 3245
• 作者: Hideo Bannai et al.;Shunsuke Inenaga et al.
• 通讯作者: Shunsuke Inenaga et al.