A Linear Time Algorithm for Computing a Maximal Common Subsequence Among Strings

IPSJ

Bibliographic Information

Other Title
  • 文字列間の極大共通部分系列を求める線形時間アルゴリズム

Search this article

Description

Σを、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の記述長である。

Journal

  • 全国大会講演論文集

    全国大会講演論文集 第47回 (基礎理論及び基礎技術), 93-94, 1993-09-27

    情報処理学会

Details 詳細情報について

Report a problem

Back to top