Needleman-Wunsch算法的改進(jìn)

張玉虎，周 正

（海軍航空大學(xué)，山東 煙臺 264001）

0 引言

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

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

但是傳統(tǒng)的Needleman-Wunsch算法的運(yùn)算量較大，在兩序列的長度較長時尤為明顯，較大的計算量將會拖慢相控陣?yán)走_(dá)工作模式的識別速度，影響指揮員對戰(zhàn)況的評估與決策，本文對傳統(tǒng)算法進(jìn)行了改進(jìn)，減小了運(yùn)算量，提高了運(yùn)算效率。通過仿真實(shí)驗(yàn)證明了本文算法的有效性和實(shí)用性。

1 Needleman-Wunsch算法

Needleman-Wunsch算法是一種全局比對的動態(tài)規(guī)劃算法。對兩個序列進(jìn)行公共序列的提取就是在兩個序列間尋找最大數(shù)量的相同序列。

1.1 建立打分矩陣

打分矩陣是對序列進(jìn)行匹配打分的標(biāo)準(zhǔn)。打分矩陣是一個對稱矩陣，矩陣的行和列對應(yīng)于兩個序列中的模式和一個空位，矩陣中的每個元素表示該位置對應(yīng)行的狀態(tài)與對應(yīng)列狀態(tài)配對的得分情況。打分矩陣的得分可以自定義。

1.2 計算匹配得分矩陣

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

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

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

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

1.3 提取公共序列

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

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

1）以最右下角的最大值點(diǎn)為起始點(diǎn)；

2）每次選擇該點(diǎn)的左側(cè)、上側(cè)、左上側(cè)3個點(diǎn)中的最大值點(diǎn)作為下一個點(diǎn)；

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

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

確定完兩個序列后對應(yīng)位相同的就是兩個序列的公共序列。

例如，對序列e1和序列e2進(jìn)行公共序列的提取

結(jié)果如圖1所示。

圖1 共序列提取

由圖1可知，序列e1轉(zhuǎn)換為

序列e2轉(zhuǎn)換為

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

2 Needleman-Wunsch的改進(jìn)算法

2.1 改進(jìn)算法步驟

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

圖2 公共序列提取流程圖

2.1.1 建立匹配矩陣

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

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

2.1.2 計算匹配矩陣匹配元素

式（6）中的sij的計算準(zhǔn)則為：

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

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

矩陣中的第1行和第1列元素?zé)o需計算

因?yàn)槿魏卧嘏c空位都不匹配。

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

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

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

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

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

轉(zhuǎn)至第2步中再次計算。

重建匹配矩陣Score（1）

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

再次截短后其中一個序列沒有元素，循環(huán)計算終止。進(jìn)入下一步。

2.1.4 公共序列的重現(xiàn)

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

2.2 識別算法性能評價

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

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

圖3 計算的矩陣元素

公共序列識別算法的效果可以由序列相似度Pm和誤識別率Pf兩個標(biāo)準(zhǔn)衡量。

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

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

3 仿真分析

以相控陣?yán)走_(dá)[4-5]的搜索模式提取為例，進(jìn)行仿真實(shí)驗(yàn)，仿真實(shí)驗(yàn)分為兩部分，實(shí)驗(yàn)1分析本文算法的識別效果，實(shí)驗(yàn)2對比本文算法與原算法的改進(jìn)效果。

實(shí)驗(yàn)1識別效果研究

仿真實(shí)驗(yàn)研究相控陣?yán)走_(dá)搜索序列類型固定，跟蹤模式數(shù)變化的識別效果。

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

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

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

實(shí)驗(yàn)2算法的改進(jìn)效果

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

圖6 算法的運(yùn)行時間對比

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

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

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

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

4 結(jié)論

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