可変長圧縮基準による頻出文字列検出

摘要

様々な生物種のゲノムDNA配列やタンパク質のアミノ酸配列等から，頻出する部分を抽出し，遺伝暗号を解く手掛かりとすることは有用であると思われる．本研究では，長い一次元のシンボル列データから，頻出する部分シンボル列を抽出するという一般的なアルゴリズムを考案した．Huffman符号や算術符号は，シンボルの出現頻度のみを手掛かりとして情報源符号化を行う．シンボルをk個毎に纏めたk次拡大情報源は，シンボルの並びが独立でなければ，拡大すればする程平均符号長は短くなることが期待される．一方，頻度テーブルの記述サイズは指数的に増大する．この拡大情報源は，独立な並びの部分でも一纏めにしてしまうという欠点や，先頭からたシンボル毎に纏められるため，フレームシフトに対応できないという欠点がある．提案手法ではこれらを解決し，隣り合う二つのシンボルを纏めて新しい一つのシンボルと見倣すか否かを圧縮基準に基づき，逐次的，貪欲的に行うとした．この際に纏められたシンボル列を，有意に頻出する部分シンボル列と解釈することができる．本手法を，DNA配列データ等に対して適用し，比較検証した．