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

点击翻译按钮获取中文摘要

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