パターン照合に基づく情報検索・発見支援システムの開発

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

本研究の目的は,インターネット上に氾濫するWEBファイル,研究者によって蓄積された実験データ等の電子化されたデータから,そこに内在するパターンを効率よく発見するためのアルゴリズムの開発を行い,それを実装して計算機実験を行うことを目的としている.ここで対称とするパターンの表現として,どのようなものを採用するかは,パターンの表現力とそれを探すアルゴリズムの実行時間のトレードオフになる重要な問題である.本年度は,可変長代入を許したワイルドカードを持つパターン(以後VLDCパターンと呼ぶ)に特に着目した.VLDCパターンは,これまでに行ってきた部分文字列パターンや部分列パターンの一般化であり,バイオインフォマティクスの分野でも自然に用いられているモチーフの表現に近い.まず,VLDCパターンの照合を高速化する必要があるので,そのためのデータ構造について,領域計算量と構築アルゴリズムについての考察を行った.その結果,部分文字列パターンや部分列パターンのように領域計算量を線形にすることはできないが,照合に関してはこれまでと同様にパターン長の線形時間で照合が行えることがわかった.また,パターン発見アルゴリズムに関しても,これまでのパターン発見アルゴリズムを拡張することによって,探索時間をそれほど増大させずに最適なパターンを発見できることがわかった.今後,このアルゴリズムを実装してそのパフォーマンスを評価していく予定である.