最長共通部分列の長さを求めるアルゴリズム

列X＝{x₁, x₂, …, xₙ}に対して，順序を保持して要素を抽出した列を部分列という。また，列の長さはその列の要素の個数で定義される。ここでは，各要素が文字である列を考える。例えば，X＝{“A”, “B”, “C”, “B”, “D”, “A”, “B”}のとき，図1に示すように{“B”, “C”, “D”, “B”}はXの部分列の例であり，その長さは4である。

クリックで拡大

図1　部分列の例

ある列Zが二つの列X，Y両方の部分列であるとき，ZをXとYとの共通部分列といい，共通部分列のうち長さが最大となるものを最長共通部分列という。最長共通部分列は複数通り存在する場合もあるが，その長さは一意に決まる。X＝{“A”, “B”, “C”, “B”, “D”, “A”, “B”}，Y＝{“B”, “D”, “C”, “A”, “B”, “A”}の場合の共通部分列及び最長共通部分列の例を図2に示す。

クリックで拡大

図2　共通部分列及び最長共通部分列の例

なお，共通部分列が存在しない場合，最長共通部分列は空の列となり，その長さは0である。

最長共通部分列の長さは，2本のDNAの塩基配列間の類似度を測る目的などに用いられる。

〔最長共通部分列の長さを求めるアルゴリズム〕

二つの列X，Yの最長共通部分列の長さを求めるアルゴリズムを考える。列X，Yそれぞれについて，先頭からn個，k個の要素を抽出した列をXₙ，Yₖと表記し，列Xₙ，Yₖそれぞれの末尾の要素をxₙ，yₖと表記する。例えば，X＝{“A”, “B”, “C”, “B”}とすると，X₃＝{“A”, “B”, “C”}，x₃＝“C”である。このとき，列Xₙと列Yₖとの最長共通部分列の中の一つをLCS(n, k)，最長共通部分列の長さをLCSL(n, k)と表記する。なお，X₀とY₀は空の列であり，x₀とy₀は存在しない。

ここで，xₙとyₖとが一致しているか否かに着目して次の(1)〜(3)に場合分けし，再帰的な関係を用いてLCSL(n, k)を求めることを考える。

〔動的計画法を用いて最長共通部分列の長さを求めるアルゴリズム〕

(1)〜(3)の再帰的な関係に従い，LCSL(n, k)を再帰的に計算することによって，列X，Yの最長共通部分列の長さを求めることができる。しかし，再帰的に計算するアルゴリズムでは，重複して同じ計算をすることによって時間計算量が大きくなり，非効率になる場合がある。そこで，重複して同じ計算をすることを避けるために，LCSL(n, k)の値を動的計画法によって求めることを考える。

二つの列がX＝{“A”, “B”, “C”, “B”, “D”, “A”, “B”}，Y＝{“B”, “D”, “C”, “A”, “B”, “A”}の場合，0≦n≦7かつ0≦k≦6に対するLCSL(n, k)の値を図3に示す。図3の左端2列はn（0〜7）とそれに対応するxₙを，上端2行はk（0〜6）とそれに対応するyₖを表す。n＝0のときのxₙ，k＝0のときのyₖは存在しないので，“－”と表す。各要素は列Xₙと列Yₖとの最長共通部分列の長さLCSL(n, k)の値を示している。

注記1　（）内の①〜③については，図3に続く本文で値の求め方を説明している。

注記2　LCSL(n, k)の値の一部は，設問のため表示していない。

図3の各要素の値は，〔最長共通部分列の長さを求めるアルゴリズム〕の(1)〜(3)の再帰的な関係に従って求められる。

まず，n＝0又はk＝0のときは(3)に対応するので，LCSL(n, k)＝0である。

それ以外の値について，例えば，図3の①〜③は次のように値が決まる。

①について，x₂＝y₁なので(1)に対応し，LCSL(2, 1)＝LCSL(1, 0)＋1である。LCSL(1, 0)＝0なので，LCSL(2, 1)＝1となる。

②について，x₂≠y₂なので(2)に対応し，LCSL(2, 1)＝1，LCSL(1, 2)＝0なので，LCSL(2, 2)＝1となる。

③について，x₆≠y₂なので(2)に対応し，LCSL(6, 1)＝1，LCSL(5, 2)＝2なので，LCSL(6, 2)＝2となる。

図3の要素の値を全て計算することによって列X，Yの最長共通部分列の長さが4であると分かる。

〔動的計画法を用いて最長共通部分列の長さを求めるプログラム〕

〔動的計画法を用いて最長共通部分列の長さを求めるアルゴリズム〕に基づいて，二つの列の最長共通部分列の長さを求めるプログラムを考える。任意の二つの列をそれぞれ配列S，Tとして受け取り，動的計画法を用いて最長共通部分列の長さを求めるプログラムを図4に示す。ここで，配列の要素番号は0から始まり，整数型の二次元配列lcslは，行番号が0から配列Sの要素数sまでの(s ＋ 1)行，列番号が0から配列Tの要素数tまでの(t ＋ 1)列の大きさをもつ。

図4のプログラムの時間計算量を，配列Sの要素数s，配列Tの要素数tを用いて表すとO(キ)である。