最長共通部分列問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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

計算量[編集]

汎用的な入力列の数が任意のときには、この問題はNP困難である。入力列の数が一定のときには、この問題は動的計画法によって多項式時間で解く事ができる(後の項参照)。長さが 列が与えられたとする。単純な探索では、最初の列の 個の部分列が残りの列の部分列であるかを確かめる。残りの配列もまた同様にテストを行う。それぞれの配列は、残りの配列長の線形時間で評価される。そして、このアルゴリズムの計算時間は、下記の通りである。

2つの配列 n と m エレメントの場合、動的計画法アプローチによる時間計算量は、O(n × m)である。入力配列が任意の数の場合、動的計画法アプローチによる解法では、下記のようになる。

それらは、さほど複雑ではない計算方法が存在[1]し、それはしばしば、最長共通部分列の配列長か、アルファベットのサイズ、もしくはその両方に依存する。

注意:最長共通部分列は、必ずしも一意ではない。例として ”ABC” と ”ACB” の最長共通部分列は ”AB” と ”AC” の両方である。実際、最長共通部分列はしばしば、見つかった最大長の共通部分列すべてによって、定義される。

この問題は本質的に高い複雑性を有しており、そのような部分列数は最悪の場合[2]、指数関数的であり、2つの配列の場合も同様である。

二つの配列の解法[編集]

最長共通部分列問題は、部分構造最適性である。この問題は、小さくブレイクダウンできる。簡単な部分問題、それはさらに簡単な部分問題にブレイクダウンできる。そして最後には単純な解法となる。 またこの問題は、部分構造重複性である: 上位の解法は、しばしば幾つかの下位の解法に依存している。これら二つの特質を伴う問題 ― 部分構造最適性と部分問題重複性 ― を持つこの問題は、動的計画法と呼ばれる手法で解決できる。どの部分問題解法も、メモ化を繰返し、繰返し計算し、求める。 メモイゼーション  ― ひとつのレベルの部分問題をテーブルに格納して、次のレベルの部分問題が利用できるようにし、計算量を節約する ―  が必要な計算手順である(メモを取ることによく似ている所が、名前の由来である) この解法を次に示す。

接頭辞[編集]

部分問題は単純になり、同じく配列は短くなります。短い配列は、接頭辞を使用して説明すると便利である。 配列の接頭辞は、配列の後ろを削除したものである。S を配列(AGCA)とした時、配列(AG)は、S の接頭辞の一つです。接頭辞は、配列の名前を意味し、後ほど挙げる添え字は、接頭辞がいくつの文字を含んでいるかを表している。[3]

接頭辞(AG)は、S2 を意味し、それは S の最初の2要素を含んでいる。可能な S の接頭辞は、

S1 = (A)
S2 = (AG)
S3 = (AGC)
S4 = (AGCA).

任意の二つの配列 XY の最長共通部分列問題の解法は、いくつかの関数で構築されたLCS(X, Y)に帰結する。それは、XY に共通の最長部分列を与える。この関数は、続く二つの特性によって成り立っています。

最初の特性[編集]

恐らくこの二つの配列の最後は同じ要素である。見つける最長共通部分列は、それぞれから取り出された最後の要素による短い配列であり、短くされた配列の最長共通部分列を見つけ、そしてその最長共通部分列に取り出された要素を追加する。

例として、ここに同じ長さの最終要素を持っている二つの(BANANA)と(ATANA)と言う配列がある。
同じ長さの最終要素を切り取ります。この手順を共通ではない最終要素が見つかるまで、繰り返します。切り出した配列は、(ANA)である。
配列はいま、考察の元に(BAN)と(AT)であり、最後の二つの配列の最長共通部分列は、精査によって(A)である。
取り出した要素(ANA)を追加し(AANA)となる。精査により、これがオリジナル配列の最長共通部分列である。

接頭辞に関して、

if xn=ym, LCS(Xn, Ym) = (LCS( Xn-1, Ym-1), xn)

カンマの部分は、続く要素 xnを表しており、それは追加された配列である。 注釈:XnYmの最長共通部分列は、決定する短い最長共通部分列 Xn-1Ym-1を巻き込む。

第二の特性[編集]

恐らく二つの配列 XYの最後は、同一長の符号ではない。その時、XYの最長共通部分列は、二つの配列の長い部分LCS(Xn,Ym-1)とLCS(Xn-1,Ym)である。

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

sequence X: ABCDEFG (n elements)
sequence Y: BCDGK (m elements)

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

ケース1:最後がGの最長共通部分列
その時は、最長共通部分列の最後は、Kにはできない。したがって、それは Y 配列から K を取り除いても、問題ない。もし、K が最長共通部分列にあれば、それは最後の文字となる。結果として、Kは最長共通部分列に含まれない。わたし達はその時、こう書くことができる: LCS(Xn,Ym) = LCS(Xn, Ym-1).

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

多くの場合、最長共通部分列は、一つの LCS(Xn, Ym-1) もしくは LCS(Xn-1, Ym)を見つける事である。それら二つの最終最長共通部分列は、両方に共通の部分列 X と Y である。LCS(X,Y)は、最長である。それゆえ、その値は最長の LCS(Xn, Ym-1) と LCS(Xn-1, Ym) 配列である。

最長共通部分列関数定義[編集]

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

 X = (x1, x2...xm) … X の接頭辞は、 X1, 2,...m
 Y = (y1, y2...yn) … Y の接頭辞は、 Y1, 2,...n

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

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

計算例[編集]

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

LCS Strings
0 1 2 3 4 5
0 A G C A T
0 0 Ø Ø Ø Ø Ø Ø
1 G Ø
2 A Ø
3 C Ø

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

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

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

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

LCS(R1, C4)も同様に(G)

LCS(R1, C5)も同様に(G)

"G" Row Completed
0 1 2 3 4 5
Ø A G C A T
0 Ø Ø Ø Ø Ø Ø Ø
1 G Ø Ø (G) (G) (G) (G)
2 A Ø
3 C Ø


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

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

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

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

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

"G" & "A" Rows Completed
0 1 2 3 4 5
Ø A G C A T
0 Ø Ø Ø Ø Ø Ø Ø
1 G Ø Ø (G) (G) (G) (G)
2 A Ø (A) (A) & (G) (A) & (G) (GA) (GA)
3 C Ø


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

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

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

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

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

Completed LCS Table
0 1 2 3 4 5
Ø A G C A T
0 Ø Ø Ø Ø Ø Ø Ø
1 G Ø Ø (G) (G) (G) (G)
2 A Ø (A) (A) & (G) (A) & (G) (GA) (GA)
3 C Ø (A) (A) & (G) (AC) & (GC) (AC) & (GC) & (GA) (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 0 1 1 1 1
2 A 0 1 1 1 2 2
3 C 0 1 1 2 2 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 0 1 1 1 1
2 A 0 1 1 1 2 2
3 C 0 1 1 2 2 2

脚註[編集]

[ヘルプ]
  1. ^ L. Bergroth and H. Hakonen and T. Raita (2000). “A Survey of Longest Common Subsequence Algorithms”. SPIRE (IEEE Computer Society) 00: 39–48. doi:10.1109/SPIRE.2000.878178. ISBN 0-7695-0746-8. 
  2. ^ Ronald I. Greenberg (2003年8月6日). “Bounds on the Number of Longest Common Subsequences”. arXiv:cs.DM/0301030. 
  3. ^ Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. New York: Springer. p. 24. ISBN 0-387-71336-0.