文字の分類とパターン探索アルゴリズムの研究

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

本年度はパターン探索の対象となるパターンのクラスを、昨年度まで主に用いていた単純な部分文字列クラスや、代入・削除・挿入を許した近似文字列パターンから拡張を試みた。具体的には任意の文字列とマッチする事が可能な「ワイルドカード文字」を含むVLDC (variable length don't care) パターンと呼ばれるパターンのクラスについて新たに考察し、VLDCパターンの問合せを高速に処理する事が可能なMASDAWGと呼ばれる文字列の索引構造を開発した。更にこの索引構造を用いて効率的にVLDCパターンの探索を行なうアルゴリズムに関して研究・開発を行なった。このようにパターンの記述力を高める事で、パターン探索に際してより有用な知識を得られる事が期待される。これを検証するために、データとして正例と負例の文字列集合が与えられた時に、正例のみ、もしくは負例のみに、最も特異的に現われるVLDCパターンを探索するアルゴリズムを開発し、実データに対して適用した。開発したアルゴリズムを昨年度に解析したN-末端細胞内局在化シグナルを持つアミノ酸配列データに対して適用したところ、分類精度の向上と、発見されたパターンが局在化シグナルに関して既知の特徴を良く捉えている事が確認できた。他には遺伝子のDNA配列における長大なイントロンの配列の解析を行ない、長いイントロンに特徴的なVLDCパターンを発見する事に成功した。プログラムの開発はObjective Camlと呼ばれる関数型言語で行ない、ソースコードは一部GPLで公開している(http://biocaml.org/)。