文字列間の極大共通部分系列を求める線形時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
Σを、2つ以上の文字からなる有限アルファベットとする。Σ上の文字からなる有限長系列を文字列という。文字列s=a_1a_2・・・a_nに対して、文字列t=a_<i1>a_<i2>・・・a_<ij>(1≤i_1<i_2<・・・<i_j≤n)をsの部分系列という。例えば、文字列abcbaに対してabb、bba、abcba等は部分系列である。Sを文字列の有限集合とする。もし、文字列tがSに属するすべての文字列に対して部分系列となっている時、tをSの共通部分系列という。Sの共通部分系列のうち、長さが最大のものをSの最長共通部分系列という。また、文字列tがSの極大共通部分系列であるとは、tがSの共通部分系列であり、かつ、Sのどの共通部分系列もtを真の部分系列として含まないことをいう。例えば、文字列集合S={abac,aabc,abca}に対してa,b,c,aa,ab,ac,bc,abcは共通部分系列であり、aa,abcは極大共通部分系列、abcは最長共通部分系列である。マルチプルアライメントとは、与えられた複数の有限長文字列を類似した文字パタンがなるべく揃うように配置する操作をいう。このマルチプルアライメントは、(1)生物の進化の推定(2)蛋白質や遺伝子における構造と機能との関連調査などの生物学の研究において利用される重要な技術である。マルチプルアライメントを行なう際に、共通部分系列を求めることで類似した文字パタンを揃えやすくなる。しかし、任意の文字列集合Sの最長共通部分系列を求めることはNP困難である。本稿では、先に示したSの極大共通部分系列を1つ求める。Ο(l∥S∥)時間の手続きをΟ(k∥S∥)に改良した手法を示す。ここで、lはSに属する最短の系列の長さで、kはΣに属する文字の数、∥S∥はSの記述長である。
- 一般社団法人情報処理学会の論文
- 1993-09-27
著者
関連論文
- マルチエージェントによる異種の分子生物学データベースの統合と検索の実現
- 通信量を考慮したデータウェアハウスの更新反映処理
- 検索処理を高速化するためのデータベーススキーマの設計手法
- 文字列集合における識別文字列を求めるための多項式時間手続き
- タンパク質データベースの試作検索機能について
- オブジェクト指向データベースにおけるビュー機能の試作
- 文字列間の極大共通部分系列を求める線形時間アルゴリズム
- 遺伝的アルゴリズムによるマルチプルストリングアライメント
- 遺伝的アルゴリズムにおけるマルチプル・ストリング・アライメント
- 遺伝的アルゴリズムによる分子系統樹の作成