基于動態規劃的Needleman-Wunsch雙序列比對算法的分析與研究*

甘秋云

(福州理工學院計算與信息科學學院，福建 福州 350014)

1 引言

隨著人類各項基因組計劃的逐漸實施，核酸和蛋白質的數據正呈現指數級增長，如何處理分析龐大的生物數據，成為當今科學家所面臨的一項重大的挑戰，生物信息學也隨之發展。生物信息學是一門將生物學、計算機科學、數學及其他處理技術相結合的學科，在生命科學研究中占有重要的地位，它的主要任務是探尋高效的研究和分析生物數據的工具，找出具有重要價值的生物學知識，從而分析和探究生物數據所蘊含的信息，進一步理解生命和進化關系[1]。

序列比對是生物信息學研究的主要課題之一，是運用特定的算法分析2條或多條序列之間的相似性的過程。通過序列比對，可以判斷2條基因序列之間是否具有相似性，進而分析同源性，推導生物進化的過程，它對于發現生物序列中的功能、結構和進化信息都具有重要的意義[2]。

當今，序列比對算法有很多，主要類型有：雙序列比對和多序列比對、全局比對和局部比對。典型的全局比對算法是Needleman-Wunsch算法，局部比對算法為Smith Waterman算法。雙序列比對算法中較成熟的是基于動態規劃的算法，和由此提出的FASTA(FAST-ALL)和BLAST(Basic Local Alignment Search Tool)算法；多序列比對主要用于識別多條序列的公共特征，主要有clustalW算法、MAFFT(Multiple Alignment using Fast Fourier Transform)算法和MUSCLE(Multiple Protein Sequence Alignment)算法[3]。

由于不同的比對算法具有不同的空間復雜度和時間復雜度，因此在序列比對過程中，數據的存儲和比對結果的精準度也不同，面對呈指數級增長的生物數據，如何研究并設計一種高效精準的DNA序列比對算法，已經成為生物信息學面臨的挑戰之一。

2 Needleman-Wunsch算法原理

動態規劃是用來求解最優化問題的，并且每一部分的解都是最優的。Needleman-Wunsch算法是由Needleman和Wunsch在1970年提出的，也是沿用至今的序列比對算法之一[4]。

Needleman-Wunsch算法主要通過迭代的方式求出2條序列之間的比對得分，并將得分存入二維得分矩陣M中，運用動態規劃算法，采用回溯技術，從而找到序列比對的最佳路徑，即序列比對的最優結果。

實現Needleman-Wunsch算法主要有3個步驟：(1)建立一個二維得分矩陣，根據特定的打分規則(采用迭代方式和空位罰分規則)初始化矩陣；(2)通過得分規則和計算公式，計算二維矩陣每個單元Mi,j的相似性得分，并填充矩陣；(3)利用回溯方法找出比對的最佳路徑，即最佳比對結果[5]。

(1)假設2條序列分別為序列S和序列T，其堿基序列如表1所示。

Table 1 S and T sequences

本文使用最簡單的打分規則，如下所示：

(1)

其中，k1是序列堿基匹配得分，k2是錯配時的得分，k3是插入空位的情況得分，Si表示序列S中第i個堿基符號，Tj表示序列T中第j個堿基符號。即:

(2)

(2)計算填充得分矩陣。

根據Mi,j計算公式，通過水平、垂直和對角線3個方向遞歸計算Mi,j的值。其中，對角線方向的Mi-1，j-1得分加上打分函數score(Si,Tj)的值(若對應堿基相同，score函數得分為1分，不同則為0分)，對于垂直或水平方向的元素Mi-1，j或Mi，j-1是加上k3值(若為空位則打分為-1分)，遞歸計算相似性得分，最終取最大值為Mi,j的值。計算代價矩陣的迭代公式如下所示：

(3)

(3)回溯最佳路徑。

從得分矩陣的右下角開始，一直回溯到左上角為止的路徑，就是Needleman-Wunsch算法求出的序列比對最佳結果。圖1所示為序列S和序列T的矩陣計算得分和回溯得到的路徑圖。

Figure 1 Matrix calculation score and backtracking path

從右下角最后一個單元開始回溯，矩陣單元的回溯路徑方向為對角線，表示當前矩陣橫軸和縱軸的2個堿基符號在同一個位置配對(包括正確匹配和錯配)，若路徑垂直向上說明該單元縱軸方向序列堿基位置缺失，需要插入一個空位，反之，路徑為水平向左表示橫軸對應堿基位置插入一個空位。根據回溯路徑圖1所示的S和T的最佳匹配結果有2種，如圖2所示。

Figure 2 Alignment results of sequence S and sequence T

3 算法優化

Needleman-Wunsch算法是目前比較典型的雙序列比對算法，雖然可以得到最優的匹配結果，但是該算法也有不足之處。通過分析發現，該算法的時間復雜度和空間復雜度較高，為O(m*n)，其中，m和n分別是2條序列的長度。隨著日益增長的生物序列數據，高代價的時間和空間開銷無疑降低了序列比對的效率[6]。

根據Needleman-Wunsch算法的實現過程可以發現，計算得分并填充矩陣的過程是導致算法時間復雜度較高的主要原因，因此本文主要針對計算得分及回溯過程進行優化。

3.1 計算得分算法的改進

在原有算法中，需要通過雙層循環計算得分，根據式(3)，在內層循環中需要分別計算對角線、水平和垂直3個方向的得分值分別加上各自的罰分值的總分，再對3個方向的得分進行比較獲得最大值作為當前單元的得分并賦值給Mi,j。

假設2條序列分別為S={S1,S2,…,Sn}和T={T1,T2,…,Tm},當2條序列的某對應位置上的堿基相同時,即Si=Tj，在原算法的基礎上，只需要將對角線值Mi-1,j-1加上匹配得分score，此時得分為最大值即可作為Mi,j的值，從而省略了對垂直和水平方向的得分計算，減少循環中的計算次數，可有效縮短計算時間。

此外，除了堿基相同時直接將對角方向值加匹配得分score作為Mi,j外，在堿基不同時，改進原算法，在內層循環中，先對3個方向的值進行大小比較，得到最大值，再加上匹配得分即為當前的Mi,j，這樣可以進一步減少3個方向的計算次數。圖3是改進后算法的得分計算示意圖。當對應堿基相同時，Mi,j得分為Mi-1，j-1加上匹配得分k1；當對應堿基不相同時，Mi，j得分為Mi-1，j-1加上給定錯配罰分k2，Mi-1，j和Mi，j-1加上空位罰分k3，最終的最大值即為Mi，j得分。

Figure 3 Calculation scheme of score matrix of improved algorithm

改進后的計算得分算法的關鍵代碼如下所示：

for(i=1;i≤S.length();i++){

for(j=1;j≤T.length();j++){

if(S.charAt(i-1)==T.charAt(j-1)){

M[i][j].score=M[i-1][j-1].score+match;

}else{

score=max(M[i-1][j-1]),M[i-1][j],M[i][j-1]);

if(score==M[i-1][j]||score==M[i][j-1])

M[i][j].score=score+gap;

else

M[i][j].score=score+dismatch;

}

}

}

在循環開始前，對矩陣進行初始化，此時M[0][0]=0，為當前矩陣得分最大值；當進入循環結構開始執行計算得分操作時，每次循環都進行了max函數的求解，得到的均為得分結果最大值；當滿足循環終止條件時，矩陣的計算得分仍為最大。因此，算法設計上滿足循環不變式。

為了進一步驗證算法的正確性，對原算法和改進后算法進行不同輸入矩陣大小和輸出比對時間的對比實驗。

改進前計算得分算法輸入矩陣行為950，列為1 000，執行原算法計算矩陣單元得分，運行時間為58 ms。改進后計算得分算法輸入矩陣行為950，列為1 000，執行改進后的算法計算矩陣單元得分，運行時間為46 ms。

原算法計算得分的時間復雜度度為O(m*n),通過輸入矩陣大小，生成對應大小字符序列，使用改進前后的算法分別對數據進行測試，發現改進后算法在時間上少于原算法，驗證了改進后算法計算得分的時間效率。

3.2 回溯的改進

填充矩陣得分結束后，需要從矩陣的右下角最后一個單元開始回溯，在回溯過程中需要獲取當前得分的來源，從而確定回溯路徑。為了節省回溯時的判斷時間，本文改進算法在原有算法的基礎上，每次計算Mi,j時，只要記錄上一行目標單元的后繼單元。

根據圖1所示的得分矩陣，首先讀取M0，0單元得分并存入內存，根據打分規則，當讀取M1,1得分為1且得分來源于M0,0時，將M1,1單元作為M0,0的后繼節點存入。后繼單元的選取采用以下規則：當出現對應同一個位置的堿基相同時(如圖1中S1=T1，堿基符號均為A)，此時優先獲取對角線方向的單元作為后繼單元；而對于可能存在的錯配或有空位缺失的情況則記錄各個方向。例如,圖1中M1,1的后繼單元包括了M1,2和M2,2，雖然M2,2是序列S和序列T在對應相同位置(即i=j)堿基的比對得分，但是在該對應位置上的堿基符號不一致，因此需要考慮M1,1的所有可能的后繼單元，將M1,2和M2,2存入內存。循環執行，在計算得分的同時記錄目標得分單元Mi,j，最終構建相關樹形結構，通過記錄有效路徑的得分單元，相較于原算法可以減少回溯的次數。得分單元Mi,j的結構示意圖如圖4a所示，其中，Si和Tj分別表示對應位置的堿基符號，source記錄Mi,j的得分來源單元，index表示當前得分單元的來源方向。index包括垂直向上、水平向左和對角線3個方向，分別以0，1，2表示，如圖4b所示。

當獲得相關路徑的樹形結構后，從最后一個節點Mm,n(m,n為序列的長度)開始回溯到起點M0,0位置，所得路徑即為最佳路徑。雖然前期減少了回溯的次數，但是當序列長度較大時，回溯所消耗的時間仍然較長。因此，進一步改進算法，主要是通過雙向搜索的策略，從起點M0,0和終點Mm,n同時搜索，當搜索過程中出現了交點，那么該從起點到終點的路徑為當前最優路徑，根據節點中的index方向標記可以確定堿基之間的匹配和缺失情況，雙向搜索示意圖如圖4c所示。改進算法在序列數據較大、節點數量較多時可以大大縮短回溯的時間，從而減少了序列比對時間，提高了整體比對效率。

Figure 4 Storage structure of target score unit and scheme of bi-directional search

改進后的雙向搜索算法的關鍵代碼如下所示：

voidbi_directionalSearch(){

while(!Queue1.empty())

Queue1.pop();

while(!Queue2.empty())

Queue2.pop();

Matrix[start.state]=1;

Matrix[end.state]=2;

Queue1.push(start);

Queue2.push(end);

While(!Queue1.empty()||

!Queue2.empty()){

if(!Queue1.empty())

directionalSearch_expand(Queue1.true);

if(found)

return;

if(!Queue2.empty())

directionalSearch_expand(Queue2.false);

if(found)

return;

}

}

改進后的算法為得分單元設計了新的數據結構，同時采用雙向搜索方式減少了回溯的次數，縮短了比對時間。假設起點到終點的深度為h，每次搜索的分支因子為r，使用隊列實現，每訪問一個節點信息的同時將當前節點的子節點(即后繼節點)依次入隊。如果采用單向回溯路徑，依次遍歷隊列中存儲的節點，最大搜索的次數達到rh；若采用雙向搜索策略，設置2個隊列，一個用于存放從起點向終點搜索的節點信息，另一個隊列用于存放從終點向起點搜索的節點信息，從起點到終點，或從終點到起點，只有h/2的深度，則最大搜索次數為2*(rh/2)，理論上搜索次數明顯減少。

為了測試算法理論正確性，初始化矩陣，輸入起點坐標和終點坐標，通過對改進前后的算法進行數據測試，輸出搜索次數。

改進前回溯算法輸入起點坐標(1,1)，終點坐標(10,10)，執行原算法，搜索次數為10次。

改進后回溯算法輸入起點坐標(1,1)，終點坐標為(10,10)，執行改進后算法，搜索次數為8次。

通過比較，改進后的回溯算法搜索次數小于原算法的，驗證了改進后的搜索算法的有效性。

4 實驗結果與分析

為了驗證改進后的Needleman-Wunsch算法在雙序列比對中可以有效縮短比對時間，本文設計了2次序列長度范圍相同和不同的比對實驗。實驗中2條比對序列均從NCBI下載，其中金黃色葡萄球菌(序列大小約2.82 Mb，序列號為NC_007795.1)作為目標序列，銀葡萄球菌(序列大小約為2.79 Mb，序列號為NC_016941.1)作為待比對序列。實驗過程中，為了模擬序列中堿基的插入缺失，設計程序，從第1個堿基位置開始，隨機生成序列長度在450～500 bp的目標序列和5條待比對序列。分別使用改進前和改進后的Needleman-Wunsch算法，依次進行5組比對實驗，分別計算2條序列之間的匹配率(即序列相似性，2條序列中相同匹配堿基數量占整條序列的比例)，以及序列比對時間。表2是5組比對實驗的結果，其中Subject表示目標序列，Query表示待比對序列。如Staphylococcus aurers-457表示金黃色葡萄球菌序列長度為457 bp,Staphylococcus argenteus-466表示待比對的銀葡萄球菌序列長度為466 bp。

從表2中可以看到，改進前后的Needleman-Wunsch算法對5組比對序列的比對時間出現了差異。在不改變序列相似性前提下，改進后的算法在比對時間消耗上普遍少于改進前的算法的。圖5是改進前后Needleman-Wunsch算法關于5組長度范圍相同的序列比對結果的折線圖。從圖5中可以更加明顯地看到，改進后的算法在序列比對上所消耗的時間明顯少于改進前的算法的。

Table 2 Comparison results of 5 groups sequence alignment with the same length range for Needleman-Wunsch algorithm before and after improvement

Figure 5 Time comparison of 5 groups sequence alignment time line graphs with the same length range for Needleman-Wunsch algorithm before and after improvement

為了進一步驗證改進后算法的有效性，增加了一組隨機生成不同長度范圍的序列的比對實驗。2條比對序列同樣以金黃色葡萄球菌作為目標序列，銀葡萄球菌作為待比對序列。生成的5組序列長度分別為1000～2000 bp,2500～3500 bp,4500～5500 bp,6500～7500 bp,8500～9500 bp。表3所示為5組不同長度范圍的序列比對結果。

從表3中可以看到，改進前后的Needleman-Wunsch算法對5組不同長度范圍的序列的比對時間同樣也出現了差異。改進后的算法在序列比對時間上普遍少于改進前的算法的，而改進前后的算法并不影響序列的相似性。圖6是改進前后Needleman-Wunsch算法關于5組長度范圍不同的序列比對結果的折線圖。從圖6中可以更加明顯地看到，改進后的算法在運行時間上少于原算法的。

Table 3 Comparison results of 5 groups sequence alignment with the different length range for Needleman-Wunsch algorithm before and after improvement

Figure 6 Time comparison of 5 groups sequence alignment time line graphs with the different length range for Needleman-Wunsch algorithm before and after improvement

通過以上2組實驗可以驗證改進后的Needleman-Wunsch算法有效地縮短了序列比對時間。為了進一步驗證改進后的算法在縮短實際生物全基因組序列的比對時間上同樣有效，采用2019年新型冠狀病毒和2003年的SARS病毒序列進行比對實驗。新型冠狀病毒信息從國家生物信息中心(NGDC)下載，SARS病毒信息從NCBI下載，將文本形式的2條基因序列讀入程序中并進行測試。實驗中，對2種不同病毒的核酸序列同樣進行了5次比對測試，最終獲得序列比對的平均相似性和平均比對執行時間。表4是改進前后Needleman-Wunsch算法關于新型冠狀病毒和SARS病毒全序列的比對相似性和比對運行時間。其中2019-nCov表示新型冠狀病毒，序列總長度為29.9 kb，SARS-Cov表示SARS病毒,序列長度為29.7 kb。

從表4中可以看到，改進后的Needleman-Wunsch算法相較于原算法，在全局序列比對下得到的序列相似性為78.6%，與實際公布的序列比對結果相近，說明該算法計算生物序列的相似性是可靠的。實驗中，改進后算法在序列比對時間上少于改進前算法的時間，因此，改進后的Needleman-Wunsch算法在不影響序列相似性的前提下，可以有效地縮短序列比對時間，提高比對效率。

Table 4 Results of novel coronavirus and SARS virus sequence alignment for Needleman-Wunsch algorithm before and after improvement

5 結束語

序列比對是生物信息研究中最基礎、最重要的研究。通過序列比對可以獲取不同生物之間序列的相似性程度，揭示基因序列之間的同源性，探索發現生物序列中的功能、結構和進化信息[7]。

基于動態規劃的Needleman-Wunsch雙序列比對算法雖然可以獲得序列的最優比對結果，但是時間開銷和空間開銷都較大。伴隨著海量生物數據的增長，對序列比對的運行時間的要求也越來越嚴格。本文改進了Needleman-Wunsch計算得分算法及回溯策略，結合實驗驗證了算法的有效性。結果表明，改進后的算法在一定程度上縮短了序列比對的時間，提高了比對效率。但是，在序列數據較大的情況下，該算法的空間復雜度較大，且序列比對效率仍然有待提高，在后續的研究中將繼續探討該算法的改進問題，以進一步提高程序運行效率，縮短序列比對運行時間，降低空間復雜度[8]。