楊 萍，王海清，王 宇，岳江濤

（沈陽農(nóng)業(yè)大學(xué) 信息與電氣工程學(xué)院，沈陽 110866）

隨著科技的發(fā)展，轉(zhuǎn)基因食物越來越多。僅2017年，我國的轉(zhuǎn)基因大豆消費量為11 196萬t，除自產(chǎn)1 530萬t外，進口量高達9 550萬t。研究表明，進口轉(zhuǎn)基因大豆及制品可能在30 a甚至更長時間后對人類的身體健康產(chǎn)生影響。雖然大豆的基因庫在逐漸完善，基因序列也越來越多，但我國在轉(zhuǎn)基因大豆檢測方面仍存在一些不足。在此情況下，探索轉(zhuǎn)基因大豆的DNA快速檢測方法具有非常重要的意義。

1 轉(zhuǎn)基因大豆檢測方法

轉(zhuǎn)基因大豆技術(shù)是通過基因工程，把其它植物的某些特定基因轉(zhuǎn)移到大豆基因上，從而培育出轉(zhuǎn)基因大豆，但其對人體產(chǎn)生的作用未知。

串的查找運算也稱作串的模式匹配運算，目的是在主串中找出一個與目的串完全相同的子串序列，常見的有布魯特-福斯 （Brute-Force，BF）算法和克努特-莫里斯-普拉特（Knuth-Morris-Pratt，KMP）算法。DNA序列包含生物的所有遺傳信息，對其進行研究是基因檢測領(lǐng)域的重要課題。轉(zhuǎn)基因檢測主要檢測DNA的脫氧核苷酸排列順序，即腺嘌呤，胞嘧啶，鳥嘌呤，胸腺嘧啶（分別用A，C，G，T表示）的順序。

以抗草甘膦轉(zhuǎn)基因大豆 （Roundup Ready Transgenic Soybean，RRS） 的 DNA序列為材料，在DNA序列資源有限的條件下，比較KMP算法和BF算法查找相同基因的效率和準確性，并利用KMP算法進行序列匹配，以期為轉(zhuǎn)基因大豆檢測提供準確高效的方法。

2 模式匹配的BF（Brute-Force）算法

BF算法是簡單的模式匹配算法，其基本思路是：將主串S中某個位置i（i從0開始）起始的子串和模式串T相比，即從j＝0起比較Si+j與Tj，若相等，在S中存在以i為起始位置匹配成功的可能性，繼續(xù)比較（j逐步增1），直至與T中最后一個字符相等；否則，從S的下一個字符起重新進行下一輪匹配，即從i+1，j＝0 開始新一輪匹配。

假設(shè) S＝＂ATATCATCACGAG＂，T＝＂ATCAC＂，則模式串與目標串匹配過程如圖1所示。

圖1 BF算法匹配過程Figure 1 BF algorithm matching process

該算法比較簡單，易于理解，但效率不高，主要是目標串指針回溯消耗大量時間，時間復(fù)雜度為［O（n+m），O（n*m）］。

3 模式匹配的KMP算法

回溯現(xiàn)象是BF算法造成效率不高的主要原因。若匹配過程中目標串指針不回溯，則整個匹配過程中的目標串指針都沒有回溯現(xiàn)象，可大大提高算法效率，如圖2所示。

圖2 不回溯算法的匹配過程示例Figure 2 Matching process example of backtracking algorithm

由圖2可知，在第2次匹配過程中，當(dāng)i＝6，j＝4時，目標串和模式串對應(yīng)字符不相等。若按BF算法，則下一次匹配將從i＝3，j＝0開始。因為目標串中第4，5 和 6 個字符是“T”，“C”，“A”，而模式串中的第一個字符為 “A”，所以僅需將模式串向右滑動3個字符，即第 3行 i＝6，j＝1進行字符比較。此過程中 i指針沒有進行回溯，效率高。

由圖2的第三行匹配可知，模式串j指針并不是從0開始的。若基因的DNA序列 （相對于模式串字符）比較多，可節(jié)省匹配時間，進一步提高效率。

設(shè)目標串s＝＂a0a1a2…an＂， 模式串t＝＂b0b1b2…bn＂，當(dāng)ai≠bi時有

若模式串t中可相互重疊的最大真子串滿足：

下一次匹配可直接從t的第k+1個字符bk起，與s的第i+1個字符ai繼續(xù)進行匹配。若s中不存在＂b0b1…bk-1＂＝＂bj-kbj-k+1bj-1＂，則下一次匹配直接從 s 的第一個字符和s的第i+1個字符開始。

令 next［j］＝k，next［j］表示當(dāng) t中第 j個字符與 s中相對應(yīng)的字符不等時，在t中需要重新和s中該字符進行比較的字符位置：

設(shè)模式串t＝“ATAATCAC”，則next的函數(shù)值如表1所示。

表1 next的函數(shù)值Table 1 Function vablue of next

求出 next函數(shù)后，設(shè) s＝＂ACATAATAATCACAGT G＂，t＝＂ATAATCAC＂，i為目標串的指針、j為模式串 t的指針，next［j］值比配過程圖3所示，圖4為KMP算法的演示圖。

圖3 KMP算法匹配過程Figure 3 Matching process of KMP arithmetic

圖4 用c語言實現(xiàn)KMP算法功能Figure 4 The function of KMP algorithm realized by c language

KMP的核心匹配算法（基于C語言）如下：

voidgetnext（Hstring*t，int next［］

｛

int j，k；

j＝0；

k＝-1；

next［0］＝-1；

while（j＜t.length）

if（t.data［j］＝＝t.data［k］｜｜k＝＝-1）

｛

j++；

k++；

next［j］＝k；

｝

else

k＝next［k］；

｝

int KMPindext（Hstring*s，Hstring*t，int pos）

｛

int next［INITSTRLEN］，i，j；

getnext（t，next）；

i＝pos-1；

j＝0；

while（i＜s.length＆＆j＜t.length）

if（s.data［i］＝＝t.data［j］｜｜j＝＝-1）

｛

i++；

j++；／／對應(yīng)字符相同，指針后移一個位置

｝

else

j＝next［j］；／／i不變，j后退，相當(dāng)于模式串向右移動

if（j＞＝t.length）

return i-t.length+1；／／匹配成功，返回第 1個匹配字符在主串中的位續(xù)

else

return 0；

4 BF與KMP算法的比較

4.1 時間復(fù)雜度

BF與KMP算法的復(fù)雜度比較見表2。

表2 BF與KMP算法的復(fù)雜度比較Table 2 The comparision of complexity of BF and KMP algorithm

由表2可知，BF算法的時間復(fù)雜度為 （N-M+1）*M＝O（N*M），KMP算法的時間復(fù)雜度為 N+M＝O（N+M），運算效率高于BF算法

4.2 運算速度

基于KMP算法建立一種快速高效、結(jié)果可靠的RRS轉(zhuǎn)基因大豆基因檢測方法。通過編寫KMP算法的程序和設(shè)計界面，將待檢測DNA序列導(dǎo)入用戶數(shù)據(jù)庫后，可以與轉(zhuǎn)基因DNA序列進行對比，從而判別待測大豆產(chǎn)品是否為轉(zhuǎn)基因大豆。利用Java實現(xiàn)BF和KMP算法，并且做成網(wǎng)頁形式，比較BF算法和KMP算法的運算速度，初始界面如圖5所示。

圖5 基因檢測初始界面Figure 5 Initial interface of gene detection

圖6 基因檢測界面Figure 6 Gene detection interface

該界面模擬轉(zhuǎn)基因檢測，對總基因庫的文件和轉(zhuǎn)基因文件中基因序列進行BF和KMP對比，能夠解析出樣品是否為轉(zhuǎn)基因。模擬大豆總基因庫有1 0000個脫氧核糖核苷酸和2 500個轉(zhuǎn)基因片段，檢驗結(jié)果如圖6所示。

計算查找相同基因的試驗結(jié)果表明，KMP算法的效率比BF算法高近10倍，能夠大大提高轉(zhuǎn)基因大豆的檢測效率。

5 結(jié)論與討論

通過比較分析KMP算法和BF算法，確定在查找相同基因時，KMP算法用時短，檢測效率高。諸多研究表明，KMP算法檢測速度快，準確度高，成本低，操作簡單，能夠快速判斷大豆的安全性，是一種值得推廣的轉(zhuǎn)基因大豆檢測方法。

KMP算法消除了BF算法中的指針回溯問題，但目標串指針每次只能移動一個字符，應(yīng)進行相應(yīng)改進。因此，提出應(yīng)用KMPP算法進行程序后期改進，以增加目標串指針每次移動的距離，進而提高匹配效率。目前，開發(fā)程序只能針對一種DNA序列進行檢測，后期還應(yīng)對程序進行改善，使其能夠同時對多種轉(zhuǎn)基因大豆的序列進行比對和檢測。同時，還應(yīng)導(dǎo)入基因數(shù)據(jù)庫，實現(xiàn)數(shù)據(jù)共享，使基因數(shù)據(jù)庫更加完善。