甘秋云

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

1 引言

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

序列比對(duì)是生物信息學(xué)研究的主要課題之一，是運(yùn)用特定的算法分析2條或多條序列之間的相似性的過(guò)程。通過(guò)序列比對(duì)，可以判斷2條基因序列之間是否具有相似性，進(jìn)而分析同源性，推導(dǎo)生物進(jìn)化的過(guò)程，它對(duì)于發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)和進(jìn)化信息都具有重要的意義[2]。

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

由于不同的比對(duì)算法具有不同的空間復(fù)雜度和時(shí)間復(fù)雜度，因此在序列比對(duì)過(guò)程中，數(shù)據(jù)的存儲(chǔ)和比對(duì)結(jié)果的精準(zhǔn)度也不同，面對(duì)呈指數(shù)級(jí)增長(zhǎng)的生物數(shù)據(jù)，如何研究并設(shè)計(jì)一種高效精準(zhǔn)的DNA序列比對(duì)算法，已經(jīng)成為生物信息學(xué)面臨的挑戰(zhàn)之一。

2 Needleman-Wunsch算法原理

動(dòng)態(tài)規(guī)劃是用來(lái)求解最優(yōu)化問(wèn)題的，并且每一部分的解都是最優(yōu)的。Needleman-Wunsch算法是由Needleman和Wunsch在1970年提出的，也是沿用至今的序列比對(duì)算法之一[4]。

Needleman-Wunsch算法主要通過(guò)迭代的方式求出2條序列之間的比對(duì)得分，并將得分存入二維得分矩陣M中，運(yùn)用動(dòng)態(tài)規(guī)劃算法，采用回溯技術(shù)，從而找到序列比對(duì)的最佳路徑，即序列比對(duì)的最優(yōu)結(jié)果。

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

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

Table 1 S and T sequences

本文使用最簡(jiǎn)單的打分規(guī)則，如下所示：

(1)

其中，k1是序列堿基匹配得分，k2是錯(cuò)配時(shí)的得分，k3是插入空位的情況得分，Si表示序列S中第i個(gè)堿基符號(hào)，Tj表示序列T中第j個(gè)堿基符號(hào)。即:

(2)

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

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

(3)

(3)回溯最佳路徑。

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

Figure 1 Matrix calculation score and backtracking path

從右下角最后一個(gè)單元開(kāi)始回溯，矩陣單元的回溯路徑方向?yàn)閷?duì)角線(xiàn)，表示當(dāng)前矩陣橫軸和縱軸的2個(gè)堿基符號(hào)在同一個(gè)位置配對(duì)(包括正確匹配和錯(cuò)配)，若路徑垂直向上說(shuō)明該單元縱軸方向序列堿基位置缺失，需要插入一個(gè)空位，反之，路徑為水平向左表示橫軸對(duì)應(yīng)堿基位置插入一個(gè)空位。根據(jù)回溯路徑圖1所示的S和T的最佳匹配結(jié)果有2種，如圖2所示。

Figure 2 Alignment results of sequence S and sequence T

3 算法優(yōu)化

Needleman-Wunsch算法是目前比較典型的雙序列比對(duì)算法，雖然可以得到最優(yōu)的匹配結(jié)果，但是該算法也有不足之處。通過(guò)分析發(fā)現(xiàn)，該算法的時(shí)間復(fù)雜度和空間復(fù)雜度較高，為O(m*n)，其中，m和n分別是2條序列的長(zhǎng)度。隨著日益增長(zhǎng)的生物序列數(shù)據(jù)，高代價(jià)的時(shí)間和空間開(kāi)銷(xiāo)無(wú)疑降低了序列比對(duì)的效率[6]。

根據(jù)Needleman-Wunsch算法的實(shí)現(xiàn)過(guò)程可以發(fā)現(xiàn)，計(jì)算得分并填充矩陣的過(guò)程是導(dǎo)致算法時(shí)間復(fù)雜度較高的主要原因，因此本文主要針對(duì)計(jì)算得分及回溯過(guò)程進(jìn)行優(yōu)化。

3.1 計(jì)算得分算法的改進(jìn)

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

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

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

Figure 3 Calculation scheme of score matrix of improved algorithm

改進(jìn)后的計(jì)算得分算法的關(guān)鍵代碼如下所示：

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;

}

}

}

在循環(huán)開(kāi)始前，對(duì)矩陣進(jìn)行初始化，此時(shí)M[0][0]=0，為當(dāng)前矩陣得分最大值；當(dāng)進(jìn)入循環(huán)結(jié)構(gòu)開(kāi)始執(zhí)行計(jì)算得分操作時(shí)，每次循環(huán)都進(jìn)行了max函數(shù)的求解，得到的均為得分結(jié)果最大值；當(dāng)滿(mǎn)足循環(huán)終止條件時(shí)，矩陣的計(jì)算得分仍為最大。因此，算法設(shè)計(jì)上滿(mǎn)足循環(huán)不變式。

為了進(jìn)一步驗(yàn)證算法的正確性，對(duì)原算法和改進(jìn)后算法進(jìn)行不同輸入矩陣大小和輸出比對(duì)時(shí)間的對(duì)比實(shí)驗(yàn)。

改進(jìn)前計(jì)算得分算法輸入矩陣行為950，列為1 000，執(zhí)行原算法計(jì)算矩陣單元得分，運(yùn)行時(shí)間為58 ms。改進(jìn)后計(jì)算得分算法輸入矩陣行為950，列為1 000，執(zhí)行改進(jìn)后的算法計(jì)算矩陣單元得分，運(yùn)行時(shí)間為46 ms。

原算法計(jì)算得分的時(shí)間復(fù)雜度度為O(m*n),通過(guò)輸入矩陣大小，生成對(duì)應(yīng)大小字符序列，使用改進(jìn)前后的算法分別對(duì)數(shù)據(jù)進(jìn)行測(cè)試，發(fā)現(xiàn)改進(jìn)后算法在時(shí)間上少于原算法，驗(yàn)證了改進(jìn)后算法計(jì)算得分的時(shí)間效率。

3.2 回溯的改進(jìn)

填充矩陣得分結(jié)束后，需要從矩陣的右下角最后一個(gè)單元開(kāi)始回溯，在回溯過(guò)程中需要獲取當(dāng)前得分的來(lái)源，從而確定回溯路徑。為了節(jié)省回溯時(shí)的判斷時(shí)間，本文改進(jìn)算法在原有算法的基礎(chǔ)上，每次計(jì)算Mi,j時(shí)，只要記錄上一行目標(biāo)單元的后繼單元。

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

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

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

改進(jìn)后的雙向搜索算法的關(guān)鍵代碼如下所示：

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;

}

}

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

為了測(cè)試算法理論正確性，初始化矩陣，輸入起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)，通過(guò)對(duì)改進(jìn)前后的算法進(jìn)行數(shù)據(jù)測(cè)試，輸出搜索次數(shù)。

改進(jìn)前回溯算法輸入起點(diǎn)坐標(biāo)(1,1)，終點(diǎn)坐標(biāo)(10,10)，執(zhí)行原算法，搜索次數(shù)為10次。

改進(jìn)后回溯算法輸入起點(diǎn)坐標(biāo)(1,1)，終點(diǎn)坐標(biāo)為(10,10)，執(zhí)行改進(jìn)后算法，搜索次數(shù)為8次。

通過(guò)比較，改進(jìn)后的回溯算法搜索次數(shù)小于原算法的，驗(yàn)證了改進(jìn)后的搜索算法的有效性。

4 實(shí)驗(yàn)結(jié)果與分析

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

從表2中可以看到，改進(jìn)前后的Needleman-Wunsch算法對(duì)5組比對(duì)序列的比對(duì)時(shí)間出現(xiàn)了差異。在不改變序列相似性前提下，改進(jìn)后的算法在比對(duì)時(shí)間消耗上普遍少于改進(jìn)前的算法的。圖5是改進(jìn)前后Needleman-Wunsch算法關(guān)于5組長(zhǎng)度范圍相同的序列比對(duì)結(jié)果的折線(xiàn)圖。從圖5中可以更加明顯地看到，改進(jìn)后的算法在序列比對(duì)上所消耗的時(shí)間明顯少于改進(jìn)前的算法的。

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

為了進(jìn)一步驗(yàn)證改進(jìn)后算法的有效性，增加了一組隨機(jī)生成不同長(zhǎng)度范圍的序列的比對(duì)實(shí)驗(yàn)。2條比對(duì)序列同樣以金黃色葡萄球菌作為目標(biāo)序列，銀葡萄球菌作為待比對(duì)序列。生成的5組序列長(zhǎng)度分別為1000～2000 bp,2500～3500 bp,4500～5500 bp,6500～7500 bp,8500～9500 bp。表3所示為5組不同長(zhǎng)度范圍的序列比對(duì)結(jié)果。

從表3中可以看到，改進(jìn)前后的Needleman-Wunsch算法對(duì)5組不同長(zhǎng)度范圍的序列的比對(duì)時(shí)間同樣也出現(xiàn)了差異。改進(jìn)后的算法在序列比對(duì)時(shí)間上普遍少于改進(jìn)前的算法的，而改進(jìn)前后的算法并不影響序列的相似性。圖6是改進(jìn)前后Needleman-Wunsch算法關(guān)于5組長(zhǎng)度范圍不同的序列比對(duì)結(jié)果的折線(xiàn)圖。從圖6中可以更加明顯地看到，改進(jìn)后的算法在運(yùn)行時(shí)間上少于原算法的。

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

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

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

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

5 結(jié)束語(yǔ)

序列比對(duì)是生物信息研究中最基礎(chǔ)、最重要的研究。通過(guò)序列比對(duì)可以獲取不同生物之間序列的相似性程度，揭示基因序列之間的同源性，探索發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)和進(jìn)化信息[7]。

基于動(dòng)態(tài)規(guī)劃的Needleman-Wunsch雙序列比對(duì)算法雖然可以獲得序列的最優(yōu)比對(duì)結(jié)果，但是時(shí)間開(kāi)銷(xiāo)和空間開(kāi)銷(xiāo)都較大。伴隨著海量生物數(shù)據(jù)的增長(zhǎng)，對(duì)序列比對(duì)的運(yùn)行時(shí)間的要求也越來(lái)越嚴(yán)格。本文改進(jìn)了Needleman-Wunsch計(jì)算得分算法及回溯策略，結(jié)合實(shí)驗(yàn)驗(yàn)證了算法的有效性。結(jié)果表明，改進(jìn)后的算法在一定程度上縮短了序列比對(duì)的時(shí)間，提高了比對(duì)效率。但是，在序列數(shù)據(jù)較大的情況下，該算法的空間復(fù)雜度較大，且序列比對(duì)效率仍然有待提高，在后續(xù)的研究中將繼續(xù)探討該算法的改進(jìn)問(wèn)題，以進(jìn)一步提高程序運(yùn)行效率，縮短序列比對(duì)運(yùn)行時(shí)間，降低空間復(fù)雜度[8]。