基于KMP算法的生物序列模式自動(dòng)識別應(yīng)用研究

關(guān)鍵字：KMP算法；生物序列比對；自動(dòng)識別

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2024）36-0042-03 開放科學(xué)（資源服務(wù)） 標(biāo)識碼（OSID） ：

0 引言

隨著生物科學(xué)技術(shù)的迅猛發(fā)展，生物信息學(xué)逐漸在生命科學(xué)研究中占據(jù)重要地位。生物信息學(xué)是生命科學(xué)與計(jì)算機(jī)科學(xué)等多學(xué)科交叉融合的新興學(xué)科，在基因組學(xué)、蛋白質(zhì)組學(xué)等領(lǐng)域發(fā)揮著越來越重要的作用。目前，生物信息學(xué)已大量應(yīng)用于生物序列的發(fā)現(xiàn)和預(yù)測。隨著基因組計(jì)劃的完成和海量生物序列數(shù)據(jù)的積累，從序列中得到的信息已經(jīng)比迄今為止的所有生物研究積累的信息還要多，而如何高效地識別和分析生物序列模式成為亟待解決的關(guān)鍵問題。

生物序列分析是生物信息學(xué)的核心內(nèi)容之一，而高效的序列模式識別算法對于從海量生物數(shù)據(jù)中提取有用信息至關(guān)重要。本文將從對生物序列模式和KMP算法的研究開始，通過分析生物序列和字符序列的相似性，將復(fù)雜的生物序列分解為對應(yīng)的一段段的字符序列，進(jìn)而采用字符串的模式匹配算法來解決生物序列的比較問題，實(shí)現(xiàn)生物序列模式的自動(dòng)識別。

1 生物序列模式相關(guān)概念

生物序列是指由核苷酸或氨基酸組成的線性序列，攜帶著重要的遺傳信息或蛋白質(zhì)結(jié)構(gòu)信息。其中，核苷酸共有四種，分別為腺嘌呤、胞嘧啶、鳥嘌呤、胸腺嘧啶[1]。由核苷酸聚合而成的生物序列稱為核酸序列，又分為脫氧核糖核酸（deoxyribonucleic acid，DNA） 和核糖核酸（ribonucleic acid，RNA） 兩種[2]。核酸序列攜帶著重要的遺傳信息，該遺傳信息與核苷酸的排列順序有關(guān)；氨基酸共有20種，由氨基酸連接而成的生物序列稱為蛋白質(zhì)序列，蛋白質(zhì)的結(jié)構(gòu)與氨基酸的排列次序有關(guān)。

生物序列模式是指在DNA、RNA或蛋白質(zhì)序列中重復(fù)出現(xiàn)的特定序列或結(jié)構(gòu)特征。這些模式可能在一組相關(guān)的蛋白質(zhì)、DNA或RNA序列中反復(fù)出現(xiàn)，代表著生物系統(tǒng)中非常重要的遺傳信息或結(jié)構(gòu)信息，通常具有特定的生物學(xué)功能。

隨著人類基因組計(jì)劃工程的完成，其他生物基因組的研究也取得了突破性進(jìn)展。某些生物，如酵母菌、果蠅、線蟲等，具有繁殖能力強(qiáng)、生長快、結(jié)構(gòu)簡單等特點(diǎn)。它們的基因組結(jié)構(gòu)和功能已經(jīng)被廣泛研究、了解并應(yīng)用。

核酸序列共由四種核苷酸組成，分別由A（腺嘌呤） 、T（胞嘧啶） 、C（鳥嘌呤） 、G（胸腺嘧啶） 四個(gè)字符表示；蛋白質(zhì)序列由二十種氨基酸組成，其對應(yīng)的字符代碼如圖1所示。因此，生物序列比對可以轉(zhuǎn)化為字符串比對問題。

2 模式匹配算法基本原理

字符串匹配算法在生物信息學(xué)、信息檢索等領(lǐng)域具有廣泛的應(yīng)用。所謂字符串匹配算法，是指假設(shè)存在兩個(gè)字符串S和T，其中字符串S的長度為n，字符串T的長度為m。若要查找串T是否是串S的子串，則稱串S為目標(biāo)串，將T稱為模式串，把查找模式串T在目標(biāo)串S中的匹配位置的運(yùn)算稱為模式匹配。如果在目標(biāo)串S中查找到一個(gè)與模式串T相同的字符串，則模式串與目標(biāo)串匹配；如果在目標(biāo)串S中未查找到一個(gè)與模式串T相同的字符串，則不匹配。本文重點(diǎn)介紹BF算法和KMP算法。

2.1 傳統(tǒng)的模式匹配算法

傳統(tǒng)的模式匹配算法即BF（Brute Force） 算法[3]，亦稱簡單匹配算法，采用窮舉的思路，窮舉目標(biāo)串S的所有子串，判斷是否與模式串T匹配。算法的基本思想是從目標(biāo)串S的某個(gè)字符開始，依次與模式串T的每一個(gè)字符進(jìn)行匹配。若相等，則繼續(xù)比較下一個(gè)字符；若不相等，則匹配不成功，目標(biāo)串S回退。下一次比較時(shí)，模式串T回退到首字符，目標(biāo)串S只右移一個(gè)字符，直到模式串T中的每個(gè)字符依次與目標(biāo)串S中的一個(gè)連續(xù)字符序列相等，則匹配成功。BF算法時(shí)間復(fù)雜度高，平均時(shí)間復(fù)雜度為O（n×m）。因此BF算法的匹配過程雖易于理解，但效率一般。

2.2 模式匹配的改進(jìn)算法

模式匹配的改進(jìn)算法即KMP（Knuth-Morris- Pratt） 算法，它充分利用已經(jīng)部分匹配的結(jié)果，盡量避免不必要的字符比較，改進(jìn)了造成BF算法速度慢的回溯特點(diǎn)。在某次匹配過程失敗后，指向目標(biāo)串S的指針不回溯，而是讓模式串T向右移動(dòng)一定的距離，然后繼續(xù)與目標(biāo)串S該位置的字符對齊，依次比較，直到匹配成功為止。整個(gè)匹配過程中，只需要對目標(biāo)串從頭到尾掃描一遍，指向目標(biāo)串的指針不需要回溯，模式串也無須從頭開始。KMP算法具有線性時(shí)間復(fù)雜度O（n+m），與BF算法相比，大大減少了比較次數(shù)，提高了匹配效率。KMP算法比較適合模式串較長并多次出現(xiàn)在目標(biāo)串中的情況，例如在文本編輯器中的查找和替換功能、DNA的序列匹配等，都可以通過采用KMP算法提高匹配效率。

下面通過一個(gè)例子來說明KMP算法的匹配過程。例如，目標(biāo)串S為“ababbabbac”，模式串T為“abbac”，按照KMP算法進(jìn)行匹配。

第1趟匹配過程中，目標(biāo)串S從第1個(gè)字符開始，模式串T的第1個(gè)字符與其對齊，依次向右進(jìn)行匹配。比較到目標(biāo)串的第3個(gè)字符時(shí)第一次出現(xiàn)不匹配，模式串T向右移動(dòng)兩個(gè)字符；第2趟匹配過程中，目標(biāo)串S從第3個(gè)字符開始，模式串T的第1個(gè)字符與其對齊，依次向右進(jìn)行匹配。比較到目標(biāo)串的第7個(gè)字符時(shí)第一次出現(xiàn)不匹配，模式串T向右移動(dòng)三個(gè)字符；第3趟匹配過程中，目標(biāo)串S從第7個(gè)字符開始，模式串T的第2個(gè)字符與其對齊，依次向右進(jìn)行匹配，最終匹配成功。具體匹配過程如圖2所示[4]。

3 KMP 算法設(shè)計(jì)與實(shí)現(xiàn)

根據(jù)以上分析可知，KMP算法在匹配失敗時(shí)，能快速定位到下一個(gè)可能的匹配位置，解決模式串向右移動(dòng)的最大距離問題是關(guān)鍵。

定義目標(biāo)串S和模式串T，設(shè)指針i和j分別指向S 和T中正待比較的字符Si和Tj。根據(jù)KMP算法的思想[5]，當(dāng)Si不等于Tj時(shí)，目標(biāo)串S的指針i不動(dòng)，模式串T向右移動(dòng)。此時(shí)，模式串T的前j-1個(gè)字符已經(jīng)與目標(biāo)串S 的前i-1 個(gè)字符相匹配，即“Si-j+1…Si-1”==“T1…Tj-1”（1） 。假設(shè)模式串向右最多移動(dòng)到Tk時(shí)，Si==Tk，并且有“Si-k+1…Si-1Si”==“T1…Tk-1Tk”（2） ，此時(shí)應(yīng)繼續(xù)比較下一個(gè)字符Si+1和Tk+1。因?yàn)閗 必然小于j，由（1） 等式可以得到部分匹配“Si-k+1… Si-1”==“Tj-k+1…Tj-1”（3） ，由（2） 和（3） 兩個(gè)等式可以推出“T1…Tk-1”==“Tj-k+1…Tj-1”（4） ，其中“Tj-k+1 T…kT-j1-”1表”表示示模模式式串串T中Tj前的的相同最字長符后的綴前子綴串子，而串“。T1…因此，當(dāng)目標(biāo)串Si與模式串Tj不匹配時(shí)，模式串T向右移動(dòng)的距離僅與模式串T自身有關(guān)，而與目標(biāo)串S無關(guān)。為此，在KMP算法中引入數(shù)組next[]，用next[j]的值表示這個(gè)最長后綴子串的長度，核心問題是求解數(shù)組next[j]的值。

3.1 next[]數(shù)組

由以上分析可知，next[]數(shù)組是針對模式串T構(gòu)建的一個(gè)輔助數(shù)組，其長度與模式串T 的長度相同。next[j]用于表示模式串T中第j個(gè)字符位置之前的子串（從模式串T的第一個(gè)字符開始到第j個(gè)字符的子串） 的最長公共前后綴長度。

由于模式串T的第一個(gè)字符前沒有子串，因此有next[1]=0。用指針i遍歷模式串T，比較模式串T的第i 個(gè)字符和第j個(gè)字符（即Ti和Tj） 。如果Ti等于Tj，則說明當(dāng)前位置的子串的最長公共前后綴長度可以在前一個(gè)位置（i-1） 的基礎(chǔ)上增加1，即next[i]=next[j]+1，然后i和j都向后移動(dòng)一位，繼續(xù)判斷下一個(gè)位置。如果Ti不等于Tj，則可將求next[j]值的問題繼續(xù)看作一個(gè)模式匹配的問題，整個(gè)模式串既是目標(biāo)串又是模式串，查找最長公共前后綴子串。若沒有公共前后綴子串，則next[j]=1。

3.2 KMP算法實(shí)現(xiàn)

在已經(jīng)求得模式串的部分匹配結(jié)果即next[]數(shù)組值的前提下，進(jìn)行KMP算法實(shí)現(xiàn)。

4 KMP 算法在生物序列模式自動(dòng)識別中的應(yīng)用

隨著基因組計(jì)劃和大量模式基因組工程的完成，目前已經(jīng)建立了與基因組信息相關(guān)的數(shù)據(jù)庫，絕大部分的生物序列也根據(jù)其不同的生物學(xué)意義采用不同的數(shù)據(jù)庫進(jìn)行存放。由于生物序列通常很長，并存在許多具有特定功能的模式，自動(dòng)識別這些模式對于理解基因的結(jié)構(gòu)和功能、基因表達(dá)調(diào)控以及疾病相關(guān)基因的發(fā)現(xiàn)等方面具有極其重要的意義。例如，當(dāng)研究人員研究一種新出現(xiàn)的病毒時(shí)，通過基因組計(jì)劃所提供的信息，可能會(huì)找到某個(gè)或某些相關(guān)基因，從而較快速地確定病毒序列的結(jié)構(gòu)和特點(diǎn)。這就需要在這樣長的生物序列中查找特定的模式序列，找出具有相似性的同源序列。KMP算法與無回溯的線性時(shí)間復(fù)雜度相比BF算法具有更高的效率，能夠在相對較短的時(shí)間內(nèi)處理大量的生物序列數(shù)據(jù)。KMP算法在生物序列模式自動(dòng)識別中的應(yīng)用可以分為預(yù)處理和匹配識別兩個(gè)階段。

4.1 預(yù)處理階段

首先，根據(jù)要識別的生物序列模式特征，組合構(gòu)建對應(yīng)的模式序列。將構(gòu)建好的模式序列作為模式串，將要查找的基因主序列作為目標(biāo)串，分別轉(zhuǎn)化為對應(yīng)的字符序列。然后，根據(jù)模式串計(jì)算其部分匹配表（next[]數(shù)組） ，在后續(xù)的匹配過程中用于快速跳過已經(jīng)匹配過的部分，從而提高匹配效率。

4.2 匹配識別階段

將模式序列與基因主序列進(jìn)行匹配， 當(dāng)模式序列完全匹配基因主序列中的某一段時(shí)，就確定了基因模式的位置。具體實(shí)現(xiàn)過程在KMP算法基礎(chǔ)上做了進(jìn)一步擴(kuò)展，當(dāng)匹配成功后不停止搜索，而是繼續(xù)在主序列中查找直到主序列遍歷完為止，實(shí)現(xiàn)了在主序列中查找模式序列的所有位置并輸出。當(dāng)查找成功時(shí)將匹配位置記錄在數(shù)組indices 中，同時(shí)將j 更新為next[j-1]，以繼續(xù)搜索下一個(gè)可能的匹配。以下為匹配過程的核心代碼部分：

以上為KMP算法在生物序列模式自動(dòng)識別中的應(yīng)用的具體實(shí)現(xiàn)，該算法可以應(yīng)用于疾病診斷、微生物鑒定、生物進(jìn)化研究等多個(gè)生物學(xué)方向。例如，在微生物鑒定方面，針對已知的致病性微生物基因序列模式，使用自動(dòng)識別算法在未知微生物的基因組序列中進(jìn)行搜索，可以快速鑒定微生物是否為致病性菌株。以識別大腸桿菌的志賀毒素基因（stx） 為例，將stx 基因序列模式作為模式序列，將從臨床樣本中分離出的大腸桿菌基因組序列作為目標(biāo)序列進(jìn)行匹配。如果識別出stx基因序列，那么就可以初步判定該大腸桿菌菌株具有致病性，這對于及時(shí)采取治療措施和公共衛(wèi)生防控具有重要意義。

5 結(jié)束語

綜上所述，本文在介紹生物序列模式和模式匹配算法的基礎(chǔ)上，通過將生物序列轉(zhuǎn)化為字符序列，實(shí)現(xiàn)了KMP算法在生物序列自動(dòng)識別中的應(yīng)用。該算法能夠高效且準(zhǔn)確地識別生物序列中的序列模式，為生物信息學(xué)研究提供了重要的技術(shù)支持。未來，隨著生物序列數(shù)據(jù)量的持續(xù)增長，KMP算法還可與其他先進(jìn)的生物信息學(xué)技術(shù)深度融合，不斷提高處理大規(guī)模生物序列數(shù)據(jù)時(shí)的效率和準(zhǔn)確性，進(jìn)一步推動(dòng)生物信息學(xué)的發(fā)展。