最長共通部分列問題
計算例

これから C = (AGCAT)と R = (GAC)の共通の最長部分列を見つける。最長共通部分列関数は、ゼロ番目の要素を使用する。それは、ゼロ接頭辞を定義するのに便利であり、配列C0 =  Ø; と R0 =  Øは空である。すべての接頭辞は、テーブル上で最初の縦列 C (これは列ヘッダとなる)と、最初の横列 R (これは行ヘッダとなる)である。
|  |  | 0 | 1> A | 2> G | 3> C | 4> A | 5> 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)
|  |  | 0> Ø | 1> A | 2> G | 3> C | 4> A | 5> T |
| --- | --- | --- | --- | --- | --- | --- | --- |
0: Ø
| 1 | G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }}Ø |  {\overset {\nwarrow }{\ }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(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)である。
|  |  | 0> Ø | 1> A | 2> G | 3> C | 4> A | 5> T |
| --- | --- | --- | --- | --- | --- | --- | --- |
0: Ø
| 1 | G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }}Ø |  {\overset {\nwarrow }{\ }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |
| 2 | A | Ø |  {\overset {\nwarrow }{\ }}(A) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\nwarrow }{\ }}(GA) |  {\overset {\ }{\leftarrow }}(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) の三つの配列を含む。
|  |  | 0> Ø | 1> A | 2> G | 3> C | 4> A | 5> T |
| --- | --- | --- | --- | --- | --- | --- | --- |
0: Ø
| 1 | G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }}Ø |  {\overset {\nwarrow }{\ }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |
| 2 | A | Ø |  {\overset {\nwarrow }{\ }}(A) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\nwarrow }{\ }}(GA) |  {\overset {\ }{\leftarrow }}(GA) |
| 3 | C | Ø |  {\overset {\ \uparrow }{\ }}(A) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\nwarrow }{\ }}(AC) & (GC) |  {\overset {\ \ \uparrow }{\leftarrow }}(AC) & (GC) & (GA) |  {\overset {\ \ \uparrow }{\leftarrow }}(AC) & (GC) & (GA) |

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