最長共通部分列問題

「最長共通部分文字列問題」とは異なります。

最長共通部分列問題（さいちょうきょうつうぶぶんれつもんだい、英: Longest-common subsequence problem, LCS）とは、与えられた列の集合（しばしば、2つの列からなる集合）の最長共通部分列を見つけ出す問題である。（ここで部分列(subsequence)は、部分文字列(substring)とは異なることに注意する。前者は元の列の連続した項からなる必要はない。）例えば、「ABCX」と「AYBZC」との最長共通部分列は「ABC」である。この問題は計算機科学における古典的問題であり、diff などのファイル比較プログラムの基礎をなし、バイオインフォマティクスにも応用されている。

入力列の個数が任意である一般の場合については、この問題はNP困難である。入力列の個数が一定のときには、この問題は動的計画法によって多項式時間で解く事ができる（後の項参照）。${\displaystyle N}$ 個の列があり、長さが ${\displaystyle n_{1},...,n_{N}}$ であるとする。単純な探索では、最初の列の ${\displaystyle 2^{n_{1}}}$ 個の部分列が残りの列の部分列であるかを確かめる。それぞれの配列は、残りの配列長の線形時間で評価される。それゆえ、このアルゴリズムの計算時間は、下記の通りである。

${\displaystyle O\left(2^{n_{1}}\sum _{i>1}n_{i}\right).}$

2つの配列で列の長さが n と m の場合、動的計画法の解法による時間計算量は、O(n × m)である。入力配列の個数が任意の場合、動的計画法の解法は下記の計算量で解を与える。

${\displaystyle O\left(N\prod _{i=1}^{N}n_{i}\right).}$

より計算量の小さい方法が存在^[1]するが、それはしばしば、最長共通部分列の配列長か、アルファベット(=対象とする列に現れる要素)のサイズ、もしくはその両方に依存する。

注意：最長共通部分列は、必ずしも一意ではない。例として ”ABC” と ”ACB” の最長共通部分列は ”AB” と ”AC” の両方である。実際、最長共通部分列の定義が「長さ最大の共通部分列をすべて見つけること」であることも多い。このように問題を変更すると、計算量は増大してしまう。なぜならば、長さ最大の部分列の数は最悪の場合^[2]、指数関数的に増大する。入力配列が2つの場合でさえ同様である。

最長共通部分列問題は、部分構造最適性を持つ。すなわち、この問題は、簡単な部分問題に分解することができ、それらはさらに簡単な部分問題に分解でき、そして最後には自明な問題に帰着される。またこの問題は、部分構造重複性を持つ。上位の部分問題を解く際には、しばしば下位の部分問題の解を再利用することになる。これら二つの特質を伴うこの問題は、動的計画法と呼ばれる手法で解決できる。動的計画法では、部分問題の解をその都度計算するのではなく、メモ化しておく。メモ化、すなわち、ひとつのレベルの部分問題の解をテーブルに格納して、次のレベルの部分問題が利用できるようにし、計算量を節約することが、この手続きには必要不可欠である(メモを取ることによく似ている所が、名前の由来である）。この解法を次に示す。

列が短くなるほど、部分問題も単純になる。短い配列は、「接頭辞(prefix)」という用語を使用して上手く説明できる。 配列の接頭辞は、配列の後ろを削除したものである。S を列(AGCA)とした時、列(AG)は、S の接頭辞の一つである。接頭辞は「もとの配列の名前」の後に、「接頭辞がいくつの文字を含んでいるか」の示す添え字を置くことで表わす。^[3]

接頭辞(AG)は、 S の最初の2要素を含んでいるので、S₂ と表記される。可能な S の接頭辞は、

S₁ = (A)

S₂ = (AG)

S₃ = (AGC)

S₄ = (AGCA)

である。 任意の二つの列 X と Y の最長共通部分列問題を解くことは、X と Y の最長共通部分列を与える関数LCS(X, Y)を構成することである。この関数は、続く二つの特性を持つ。

二つの列の最後の要素は同じであるとする。これらの最長共通部分列を求めるには、それぞれの要素から最後の要素を取り除いた列の最長共通部分列を見つけ、そしてその最長共通部分列に取り除かれた要素を追加すればよい。

例として、ここに同じ最終要素を持つ二つの列(BANANA)と(ATANA)がある。

共通する最終要素を取り除くことを、共通ではない最終要素が見つかるまで、繰り返す。取り除かれた列は(ANA)である。

考察すべき列は(BAN)と(AT)であり、最後の二つの配列の最長共通部分列は(A)であることが容易にわかる。

取り出した要素(ANA)を追加し(AANA)となる。これが元の配列の最長共通部分列であることは容易に確かめられる。

接頭辞に関して、

if x_n=y_m, then LCS(X_n, Y_m) = (LCS( X_n-1, Y_m-1), x_n)

が成り立つ。ここで最後の括弧は、列の最後にx_nを追加することを表す。 X_nとY_mの最長共通部分列問題が、より短い列 X_n-1と Y_m-1の最長共通部分列問題に帰着されたことに注意せよ。

二つの列 XとYの最後の要素は同じでないとする。その時、XとYの最長共通部分列は、二つの配列LCS(X_n,Y_m-1)とLCS(X_n-1,Y_m)の長い方である。

この特質を理解するため、次の二つの配列について考える:

列 X: ABCDEFG (長さn)

列 Y: BCDGK (長さm)

これら二つの配列の最長共通部分列は、最後がG(列"X"の最後の要素) もしくは、そうではないもののどちらかである。

ケース1：最後がGの最長共通部分列
この場合、最長共通部分列の最後はKではありえない。このとき、もしKが最長共通部分列にあれば、それは最後の文字となるので、Kは最長共通部分列にはない。したがって、YからKを取り除いても問題ないので、こう書くことができる： LCS(X_n,Y_m) = LCS(X_n, Y_m-1).

ケース2：最長共通部分列の最後が、Gではない場合
この場合は、上記と同じ理由により、列Xから G を取り除いても問題ないので、こう書くことができる：LCS(X_n,Y_m) = LCS(X_n-1, Y_m).

いずれにせよ、求めるべき最長共通部分列は、LCS(X_n, Y_m-1) もしくはLCS(X_n-1, Y_m)である。これら二つのLCSは、いずれもXとYの共通部分列である。LCS(X,Y)は定義より最長なので、 LCS(X_n, Y_m-1) と LCS(X_n-1, Y_m) の長い方である。

二つの配列を以下のように定義する:

　X = (x₁, x₂...x_m)　…　X の接頭辞は、 X_{1, 2,...m}
　Y = (y₁, y₂...y_n)　…　Y の接頭辞は、 Y_{1, 2,...n}

LCS(X_i, Y_j) は、X_i と Y_j の接頭辞の最長共通部分列セットを代表する。 この配列セットは、以下を与える。

${\displaystyle LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)\frown x_{i}&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)&{\mbox{ if }}x_{i}\neq y_{j}\\\end{cases}}}$

X_i と Y_j に対する最長共通部分列を見つけるため、x_i と y_j を比較する。もし、それらが同じであれば、その時は配列LCS(X_i-1, Y_j-1) は、要素x_iによって伸長されたものである。もしそれらが同じでなければ、その時は二つの配列の長さLCS(X_i, Y_j-1), と LCS(X_i-1, Y_j)は維持される。(もしそれらが両方とも同じ長さであり、しかし一致していない場合、その時は両方とも維持される)　注釈：添え字は、これらの公式によって1短縮される。結果は0の添え字も可能である。配列要素は、1から開始すると定義し、それは空の最長共通部分列(その時、添え字はゼロ)を追加する必要がある。

これから C = (AGCAT)と R = (GAC)の共通の最長部分列を見つける。最長共通部分列関数は、ゼロ番目の要素を使用する。それは、ゼロ接頭辞を定義するのに便利であり、配列C₀ = Ø; と R₀ = Øは空である。すべての接頭辞は、テーブル上で最初の縦列 C (これは列ヘッダとなる)と、最初の横列 R (これは行ヘッダとなる)である。

このテーブルは、最長共通部分列のそれぞれの計算手順を保存するために使われ、二つ目の縦列と二つ目の横列はØで埋まっている。なぜなら、空配列は非空配列と比較されたとき、最長共通部分列はいつでも空配列である。

LCS(R₁, C₁)は、それぞれの配列の最初の要素と比較することによって決定した。G と A は、同じ長さではない、そう、その最長共通部分列は二つの最長配列、LCS(R₁, C₀) と LCS(R₀, C₁)を得る。(二つ目の特質を使用する)　続くテーブル、それら両方の空白は、LCS(R₁, C₁)も空白である。同じように、以下のテーブルも見えてくる。矢印は、配列が上のセル、LCS(R₀, C₁)と左のセル、LCS(R₁, C₀)の両方のセルから来ることを示している。

LCS(R₁, C₂) は、G と G を比較し決定された。それは一致している、そう、G　は左上の配列LCS(R₀, C₁) に追加される。それは、(Ø)であり、(ØG)を与え、それは、(G)です。

LCS(R₁, C₃) は、G と C を比較し、それは一致しない。上の配列は空である; 左の一つは一つの要素 G を含んでおり、選択する最長のLCS(R₁, C₃)は(G)である。矢の指すのは左であり、二つの配列の最長となる。

LCS(R₁, C₄)も同様に(G)

LCS(R₁, C₅)も同様に(G)

"G" Row Completed

		0	1	2	3	4	5
		Ø	A	G	C	A	T
0	Ø	Ø	Ø	Ø	Ø	Ø	Ø
1	G	Ø	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(G)	${\displaystyle {\overset {\ }{\leftarrow }}}$(G)	${\displaystyle {\overset {\ }{\leftarrow }}}$(G)	${\displaystyle {\overset {\ }{\leftarrow }}}$(G)
2	A	Ø
3	C	Ø

LCS(R₂, C₁)は A と A を比較する。二つの要素は一致し、A は Ø に追加され、(A)となる。

LCS(R₂, C₂)は A と G を比較し、不一致。LCS(R₁, C₂)は上の(G)と左であるLCS(R₂, C₁)の(A)を使用する。この場合は、どちらの要素も含んでおり、その最長共通部分列は、二つの配列(A)と(G)のどちらかとなる。

LCS(R₂, C₃) は A と C を比較し、不一致、LCS(R₂, C₂) は、配列 (A) と (G) を含む。LCS(R₁, C₃) は(G)、それは既に LCS(R₂, C₂) を含んでいる。LCS(R₂, C₃)の結果は、もちろん、配列 (A) と (G) を含んでいる。

LCS(R₂, C₄) は A と A を比較し、一致。それは左上のセルに追加され、(GA)を与える。

LCS(R₂, C₅) は A と T を比較し、不一致。二つの配列(GA)と(G)を比較し、最長は(GA)、LCS(R₂, C₅) は(GA)である。

"G" & "A" Rows Completed

		0	1	2	3	4	5
		Ø	A	G	C	A	T
0	Ø	Ø	Ø	Ø	Ø	Ø	Ø
1	G	Ø	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(G)	${\displaystyle {\overset {\ }{\leftarrow }}}$(G)	${\displaystyle {\overset {\ }{\leftarrow }}}$(G)	${\displaystyle {\overset {\ }{\leftarrow }}}$(G)
2	A	Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(A)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(A) & (G)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(A) & (G)	${\displaystyle {\overset {\nwarrow }{\ }}}$(GA)	${\displaystyle {\overset {\ }{\leftarrow }}}$(GA)
3	C	Ø

LCS(R₃, C₁) は C と A を比較し、不一致。LCS(R₃, C₁) は二つの配列の最長(A)を得る。

LCS(R₃, C₂)は C と G を比較し、不一致。LCS(R₃, C₁) と LCS(R₂, C₂) は、共通の一つの要素を持っている。結果、LCS(R₃, C₂) は二つの配列 (A) と (G) となる。

LCS(R₃, C₃) は C と C を比較し、一致。C は LCS(R₂, C₂) に追加され、それは二つの配列 (A) と (G)、そして、(AC)と (GC) を得る。

LCS(R₃, C₄) は C と A を比較し、不一致。LCS(R₃, C₃) を結合させ、それは (AC) と (GC)、そしてLCS(R₂, C₄)は (GA) を含んでおり、全部で (AC)、(GC)、(GA) の三つの配列を与える。

最後にLCS(R₃, C₅)は C と T を比較し、不一致。結果は、LCS(R₃, C₅)の通り、(AC)、(GC)、そして (GA) の三つの配列を含む。

Completed LCS Table

		0	1	2	3	4	5
		Ø	A	G	C	A	T
0	Ø	Ø	Ø	Ø	Ø	Ø	Ø
1	G	Ø	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(G)	${\displaystyle {\overset {\ }{\leftarrow }}}$(G)	${\displaystyle {\overset {\ }{\leftarrow }}}$(G)	${\displaystyle {\overset {\ }{\leftarrow }}}$(G)
2	A	Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(A)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(A) & (G)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(A) & (G)	${\displaystyle {\overset {\nwarrow }{\ }}}$(GA)	${\displaystyle {\overset {\ }{\leftarrow }}}$(GA)
3	C	Ø	${\displaystyle {\overset {\ \uparrow }{\ }}}$(A)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(A) & (G)	${\displaystyle {\overset {\nwarrow }{\ }}}$(AC) & (GC)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(AC) & (GC) & (GA)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(AC) & (GC) & (GA)

結果として、最後のセルは (AGCAT) と (GAC) に共通なすべての最長部分列を含んでいる。それらは (AC) と (GC) そして (GA) である。またこのテーブルは、最長共通部分列の接頭辞すべての可能な組み合わせを見ることができる。例えば (AGC) と (GA) の最長共通部分列は (A) と (G) である。

最長共通部分列のテーブルにおいて、最長共通部分列の行の計算に唯一要求されるのは、現在の行と次の行である。なお、長い配列の場合、それらの配列はおびただしく長くなるので、たくさんの記憶領域が要求される。記憶領域を節約するには、実際の部分列を保存しない事である。しかし、部分列の長さと方向矢印は保存する必要がある。それは、以下のテーブルのようにである。

Storing length, rather than sequences

		0	1	2	3	4	5
		Ø	A	G	C	A	T
0	Ø	0	0	0	0	0	0
1	G	0	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$0	${\displaystyle {\overset {\nwarrow }{\ }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1
2	A	0	${\displaystyle {\overset {\nwarrow }{\ }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\nwarrow }{\ }}}$2	${\displaystyle {\overset {\ }{\leftarrow }}}$2
3	C	0	${\displaystyle {\overset {\ \uparrow }{\ }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\nwarrow }{\ }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2

実際の部分列は、”トレースバック”手順で推測する。それは続く逆向き矢印であり、テーブルの最後のセルから開始する。トレースバックでは長さは減少する。配列に必須なのは共通の要素である。いくつかの経路が可能であり、その場合、セルに二つの矢印がある。以下は、その解析のためのテーブルである。セルの色の付いた数字は減少についての長さである。太字の数字はトレースした配列 (GA) である。

Traceback example

		0	1	2	3	4	5
		Ø	A	G	C	A	T
0	Ø	0	0	0	0	0	0
1	G	0	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$0	${\displaystyle {\overset {\nwarrow }{\ }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1
2	A	0	${\displaystyle {\overset {\nwarrow }{\ }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\nwarrow }{\ }}}$2	${\displaystyle {\overset {\ }{\leftarrow }}}$2
3	C	0	${\displaystyle {\overset {\ \uparrow }{\ }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\nwarrow }{\ }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2

• レーベンシュタイン距離