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算法的思路，改进了运算过程，将比对的序列多次截短，减少计算量，省去了大量的无用数据的计算，提高了运算效率，节约了运算时间，仿真试验证明本文改进算法的运算时间较原算法得到了大幅度的提升。