文本比較算法Ⅱ—Needleman/Wunsch算法

本文介紹基於最長公共子串的文本比較算法——Needleman/Wunsch算法。

　　還是以實例說明：字符串A=kitten，字符串B=sitting

　　那他們的最長公共子串為ittn（注：最長公共子串不需要連續出現，但一定是出現的順序一致），最長公共子串長度為4。

　　定義：

　　LCS(A,B)表示字符串A和字符串B的最長公共子串的長度。很顯然，LSC(A,B)=0表示兩個字符串沒有公共部分。

　　Rev(A)表示反轉字符串A

　　Len(A)表示字符串A的長度

　　A+B表示連接字符串A和字符串B

　　性質：

　　LCS(A,A)=Len(A)

　　LCS(A,"")=0

　　LCS(A,B)=LCS(B,A)

　　0≤LCS(A,B)≤Min(Len(A),Len(B))

　　LCS(A,B)=LCS(Rev(A),Rev(B))

　　LCS(A+C,B+C)=LCS(A,B)+Len(C)

　　LCS(A+B,A+C)=Len(A)+LCS(B,C)

　　LCS(A,B)≥LCS(A,C)+LCS(B,C)

　　LCS(A+C,B)≥LCS(A,B)+LCS(B,C)

　　為了講解計算LCS(A,B)，特給予以下幾個定義

　　A=a₁a₂……a_N，表示A是由a₁a₂……a_N這N個字符組成，Len(A)=N

　　B=b₁b₂……b_M，表示B是由b₁b₂……b_M這M個字符組成，Len(B)=M

　　定義LCS(i,j)=LCS(a₁a₂……a_i,b₁b₂……b_j)，其中0≤i≤N，0≤j≤M

　　故：　　LCS(N,M)=LCS(A,B)

　　　　　　LCS(0,0)=0

　　　　　　LCS(0,j)=0

　　　　　　LCS(i,0)=0

　　對於1≤i≤N，1≤j≤M，有公式一

　　若a_i=b_j，則LCS(i,j)=LCS(i-1,j-1)+1

　　若a_i≠b_j，則LCS(i,j)=Max(LCS(i-1,j-1),LCS(i-1,j),LCS(i,j-1))

　　計算LCS(A,B)的算法有很多，下面介紹的Needleman/Wunsch算法是其中的一種。和LD算法類似，Needleman/Wunsch算法用的都是動態規劃的思想。在Needleman/Wunsch算法中還設定了一個權值，用以區分三種操作（插入、刪除、更改）的優先級。在下面的算法中，認為三種操作的優先級都一樣。故權值默認為1。

　　舉例說明：A=GGATCGA，B=GAATTCAGTTA，計算LCS(A,B)

　　第一步：初始化LCS矩陣

Needleman/Wunsch算法矩陣     G A A T T C A G T T A   0 0 0 0 0 0 0 0 0 0 0 0 G 0                       G 0                       A 0                       T 0                       C 0                       G 0                       A 0                      

　　第二步：利用公式一，計算矩陣的第一行

Needleman/Wunsch算法矩陣     G A A T T C A G T T A   0 0 0 0 0 0 0 0 0 0 0 0 G 0 1 1 1 1 1 1 1 1 1 1 1 G 0                       A 0                       T 0                       C 0                       G 0                       A 0                      

　　第三步：利用公式一，計算矩陣的其余各行

Needleman/Wunsch算法矩陣     G A A T T C A G T T A   0 0 0 0 0 0 0 0 0 0 0 0 G 0 1 1 1 1 1 1 1 1 1 1 1 G 0 1 1 1 1 1 1 1 2 2 2 2 A 0 1 2 2 2 2 2 2 2 2 2 2 T 0 1 2 2 3 3 3 3 3 3 3 3 C 0 1 2 2 3 3 4 4 4 4 4 4 G 0 1 2 2 3 3 3 4 5 5 5 5 A 0 1 2 3 3 3 3 4 5 5 5 6

　　則，LCS(A,B)=LCS(7,11)=6

　　可以看出，Needleman/Wunsch算法實際上和LD算法是非常接近的。故他們的時間復雜度和空間復雜度也一樣。時間復雜度為O(MN)，空間復雜度為O(MN)。空間復雜度經過優化，可以優化到O(M)，但是一旦優化就喪失了計算匹配字串的機會了。由於代碼和LD算法幾乎一樣。這裡就不再貼代碼了。

　　還是以上面為例A=GGATCGA，B=GAATTCAGTTA，LCS(A,B)=6

　　他們的匹配為：

　　　　A：GGA_TC_G__A

　　　　B：GAATTCAGTTA