サンプリングによる近似ストリングマッチングアルゴリズムに関する研究

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

サンプル法による近似ストリングマッチングのアルゴリズムを東京大学医科学研究所ヒトゲノム解析センターのマシンの上にインストールしてパタンマッチングの実験を行なった。テキストとしては、40MB位のものを選び、遺伝子パタンとしては120文字のものを用いて近似マッチの正しい位置をみつけることに成功した。現在のところ、BLASTより速くなってはいないが、これはgenbankのテキストが不等号“>"で区切られた特別のフォーマットのデータの集合となっており、我々はこの情報を有効に利用していないこと、また多分、BLASTが採用しているテキストの前処理情報を用いていないことによる。テキストの前処理を加えて更に我々のアルゴリズムを速くする予定である。我々のアルゴリズムは次頁の発表論文において発表した。また、研究を進める上でいくつかの方向が開けてきた。まず、一つはオンライン法である。これは、パタンを与える入力時間を利用して、それまでに入力されたパタンをすぐに探しに行く方法である。これによりパタン入力が終わった時点でテキスト中の所定の場所に到達している可能性がある。この結果は、やはり我々の学科のマシンの上にインプリメントして実験に成功した。もう一つの方向は、テキストとパタンのデータを文字列ではなく連続値をとる値とすることである。これは一般的時系列のパタンマッチングや2次元の場合の濃淡画像でのパタンマッチングに用いることができ、応用分野が飛躍的に拡大する。例えば1次元の場合,音楽のメロディー、地震波、株価変動等のデータベースでの検索、濃淡画像では、指紋検出、コンピュータヴィジョン、IC基板での位置決め、分子生物学における電気泳動法等への応用が考えられる。この分野でもサブリニア時間の近似パタンマッチングの開発に成功した。この結果は1995年中に発表する予定である。