Needleman-Wunsch算法的改進

張玉虎，周 正

（海軍航空大學，山東 煙臺 264001）

0 引言

隨著科技的快速發展，軍事裝備的更新換代日新月異，以相控陣雷達為代表的新體制雷達以其獨特的優勢得到了各個國家的青睞，并迅速應用到武器裝備中。相控陣雷達最突出的特點和優勢就是具有搜索加跟蹤（TAS）的工作模式，在這種工作模式下，二維相控陣雷達能夠在掃描的波位變化序列中，插入一些優先級更高的跟蹤波位和制導波位等，這樣在相控陣雷達完成搜索任務的同時，可以執行一些其他的優先級更高的任務。

Needleman-Wunsch算法是一種全局比對算法[1]，其思路與LCS算法相似，通過二維表格計算兩個序列的匹配度。本算法廣泛地應用到了醫學、計算機技術等多個領域，DNA序列匹配[2]、蛋白質序列匹配等多個方面。當前，在相控陣雷達輻射源工作模式的識別方法研究中，一些學者引入Needleman-Wunsch算法，在文獻[3]中借鑒了生物學中的信息分析比對技術，提出了通過對兩個不同時間偵察得到的序列比對，獲得其中的相似部分，實現了對相控陣雷達工作模式的識別。

但是傳統的Needleman-Wunsch算法的運算量較大，在兩序列的長度較長時尤為明顯，較大的計算量將會拖慢相控陣雷達工作模式的識別速度，影響指揮員對戰況的評估與決策，本文對傳統算法進行了改進，減小了運算量，提高了運算效率。通過仿真實驗證明了本文算法的有效性和實用性。

1 Needleman-Wunsch算法

Needleman-Wunsch算法是一種全局比對的動態規劃算法。對兩個序列進行公共序列的提取就是在兩個序列間尋找最大數量的相同序列。

1.1 建立打分矩陣

打分矩陣是對序列進行匹配打分的標準。打分矩陣是一個對稱矩陣，矩陣的行和列對應于兩個序列中的模式和一個空位，矩陣中的每個元素表示該位置對應行的狀態與對應列狀態配對的得分情況。打分矩陣的得分可以自定義。

1.2 計算匹配得分矩陣

以一條序列e1作為得分矩陣的行，另一條序列e2作為得分矩陣的列，建立得分矩陣，并在矩陣的第1行和第1列對應位置添加一行和一列空位的得分，得分矩陣可以表示為

式中，sij為序列e1的前i項與序列e2的前j項的匹配得分。

式（1）中的sij的計算方法為：

其中，w（A，B）表示在打分矩陣 W 中，行為 A，列為B的元素的值。通過計算得分矩陣Score得到了兩個序列之間在不同的空位插入方式中的得分。

1.3 提取公共序列

通過計算得到的得分矩陣表示了兩個序列在給定打分標準下、不同空位插入情況時的匹配得分。

在確定兩個序列時，遵循以下的原則：

1）以最右下角的最大值點為起始點；

2）每次選擇該點的左側、上側、左上側3個點中的最大值點作為下一個點；

3）一直跳躍到矩陣的最左上角；

4）矩陣中每次橫向跳躍表示在左側序列中對應位置后加入一個空位，同理每次豎向跳躍表示在上側序列對應位置后加入一個空位。

確定完兩個序列后對應位相同的就是兩個序列的公共序列。

例如，對序列e1和序列e2進行公共序列的提取

結果如圖1所示。

圖1 共序列提取

由圖1可知，序列e1轉換為

序列e2轉換為

由圖1可以看出，傳統算法的計算過程中，在矩陣的左下和右上兩處存在大量的無用數據，在矩陣較大時，無用數據的增長速度高于有用數據，并且原算法的計算過程存在一次回溯，這一次回溯的過程中會存在多次數據的查詢過程，同樣會影響運算時間，占用計算資源。

2 Needleman-Wunsch的改進算法

2.1 改進算法步驟

通過圖1可以看出，矩陣中存在著大量的無用數據，會嚴重影響計算速度，而且最終序列的確定還要通過一次回溯。為此，本文對算法進行了相應的改進，實現對公共序列進行提取，基本步驟如圖2所示。

圖2 公共序列提取流程圖

2.1.1 建立匹配矩陣

以一條序列e1作為匹配矩陣的行，另一條序列e2作為匹配矩陣的列，建立匹配矩陣，并在矩陣的第1行和第1列對應位置添加1行和1列對應空位，匹配矩陣可以表示為

式中，sij為序列e1的第i項與序列e2的第j項是否匹配。假定得到的兩個序列為

2.1.2 計算匹配矩陣匹配元素

式（6）中的sij的計算準則為：

通過計算匹配矩陣Score得到了兩個序列之間在不同的空位插入方式中的得分。

得分矩陣中元素的計算是按照一定的順序，從左上角開始按斜線進行計算，首先計算元素，然后計算元素，再之后計算元素，直至在某一斜線元素的計算中得到了第1個匹配的元素，將該值記為1，然后進入下一步處理。

矩陣中的第1行和第1列元素無需計算

因為任何元素與空位都不匹配。

通過上述步驟的計算，得到序列e1和序列e2的得分矩陣如式（10）

此時在一條斜線中檢測到了矩陣元素s3，4=1，得到一個公共元素C，然后進入下一步。

2.1.3 兩個對比序列長度的截短

在得分矩陣中計算得到的第1個匹配的元素后，將匹配的元素記錄下來，再以該元素為界將兩個序列截短，將后面的兩個序列重新標記為，再轉到第2步計算匹配元素。重復兩步直至在第2步中沒有匹配元素為止。

將序列e1和序列e2以公共元素C為界截短，得到新序列

轉至第2步中再次計算。

重建匹配矩陣Score（1）

經過多次的序列截短和匹配元素計算，直至得到最后一個匹配矩陣

再次截短后其中一個序列沒有元素，循環計算終止。進入下一步。

2.1.4 公共序列的重現

通過步驟2和步驟3的循環計算，將記錄下來的公共元素按照先后順序排列，就得到了兩個序列的公共序列。

2.2 識別算法性能評價

本文的改進算法計算的矩陣的元素如下頁圖3所示，原算法需要將整個矩陣進行計算且每個元素的計算依賴于該元素左側、上側和左上側3個元素的值。

本文改進方法的計算過程中，序列的不斷截短，減小了計算量，省略了大量的無用元素的計算，節約了計算成本，提高了計算效率。

圖3 計算的矩陣元素

公共序列識別算法的效果可以由序列相似度Pm和誤識別率Pf兩個標準衡量。

其中，M表示算法識別出的公共序列與實際公共序列相同的元素個數，N表示算法識別出的公共序列的元素個數，A表示實際公共序列的元素個數。

序列相似度Pm描述了算法對公共序列的識別能力；誤識別率Pf則描述了算法識別的準確度。

3 仿真分析

以相控陣雷達[4-5]的搜索模式提取為例，進行仿真實驗，仿真實驗分為兩部分，實驗1分析本文算法的識別效果，實驗2對比本文算法與原算法的改進效果。

實驗1識別效果研究

仿真實驗研究相控陣雷達搜索序列類型固定，跟蹤模式數變化的識別效果。

實驗選定序列的搜索模式有8個，分別對5種跟蹤模式情況進行對比實驗，這5種情況包括：跟蹤模式類型數為 4、6、8、10、12。計算搜索序列相似度Pm和誤識別率Pf。得到的仿真實驗結果如圖4、圖5所示。

圖4 不同跟蹤序列比例下的序列相似度

圖5 不同跟蹤序列比例下的誤識別率

實驗2算法的改進效果

仿真實驗通過用兩個算法對同一組序列的公共序列進行提取，計算兩種算法的運行時間。改變序列的長度和跟蹤序列比例，進行多次的蒙特卡洛實驗，得到結果如圖6所示。

圖6 算法的運行時間對比

由實驗1的結果可以看出，序列相似度Pm均在90%以上，而誤識別率Pf控制在了16%以下，與原算法的效果基本一致。

由圖4和圖5對比可知，在待對比序列的公共序列類型一定時，序列長度對公共序列相似度Pm和誤識別率Pf幾乎沒有什么影響；而在隨機序列比例一定時，其類型數越多，識別的序列相似度Pm越高，誤識別率Pf越低；在隨機序列的類型數一定時，其比例越低，識別的序列相似度Pm越高，誤識別率Pf越低。

這是由于同樣隨機序列比例下，隨機序列類型數越多，隨機序列元素相同的機率就越低，從而序列相似度Pm越高，誤識別率Pf越低；而隨機序列類型數相同時，其比例越高，元素相同的機率就越高，使序列相似度Pm越低，誤識別率Pf越高。

由實驗2的結果可以明顯地看出本文改進方法的優勢。在對相同的序列進行計算時，原算法與本文方法的計算時間均隨序列長度的增加而增加，但是兩者的運算時間對比可以明顯地看出本文算法極大地節省了運算時間，提高了運算效率。

4 結論

本文通過分析Needleman-Wunsch算法的思路，改進了運算過程，將比對的序列多次截短，減少計算量，省去了大量的無用數據的計算，提高了運算效率，節約了運算時間，仿真試驗證明本文改進算法的運算時間較原算法得到了大幅度的提升。