基于N-gram相似度增強(qiáng)蛋白質(zhì)肽段組裝的方法

摘要：蛋白質(zhì)肽段組裝是確定蛋白質(zhì)全長序列的重要步驟之一。然而，由于測序數(shù)據(jù)的不完整性及測序錯(cuò)誤，傳統(tǒng)de Bruijn圖方法ALPS在肽段組裝中存在覆蓋率低和準(zhǔn)確率不足的問題。因此，文章提出了一種基于N-gram相似度增強(qiáng)肽段組裝的方法。利用N-gram算法改進(jìn)了ALPS方法的組裝路徑選擇，通過計(jì)算肽段子串之間的相似性，對de Bruijn圖中斷裂子串處進(jìn)行容錯(cuò)性補(bǔ)充，從而提升了肽段組裝序列的覆蓋率與BLAST比對的得分。驗(yàn)證結(jié)果表明，該方法的組裝效果優(yōu)于ALPS，Huamn-H與Mouse-H數(shù)據(jù)集上的序列覆蓋率分別由77%提升至95%和60%提升至82%，BLAST比對的得分分別從702提升至845和從556提升至742。在Human-L與Mouse-L數(shù)據(jù)集上，兩種方法效果相當(dāng)。文章的主要貢獻(xiàn)如下：1） 提出利用N-gram算法改進(jìn)ALPS組裝方法；2） 在4個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證，該方法有效提升了肽段組裝的覆蓋率與BLAST比對的得分。

關(guān)鍵詞：N-gram相似度算法； de Bruijn圖；容錯(cuò)性；肽段組裝；BLAST比對

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

文章編號：1009-3044（2025）18-0001-06

開放科學(xué)（資源服務(wù)） 標(biāo)識碼（OSID） ：

0 引言

蛋白質(zhì)序列是確定蛋白質(zhì)結(jié)構(gòu)與功能的基礎(chǔ)。在自下而上的蛋白質(zhì)組學(xué)研究中，質(zhì)譜技術(shù)已成為主要的分析手段。然而，質(zhì)譜測序技術(shù)產(chǎn)生了大量的碎片化肽段，無法直接得到完整的蛋白質(zhì)序列信息。因此，蛋白質(zhì)肽段組裝是重建蛋白質(zhì)全長序列的核心步驟之一，在蛋白質(zhì)組學(xué)研究中具有重要意義，并且已廣泛應(yīng)用于藥物研發(fā)、病毒研究以及蛋白質(zhì)變異分析等領(lǐng)域。由于氨基酸突變、質(zhì)譜噪聲與實(shí)驗(yàn)環(huán)境的影響，肽段序列組裝面臨著諸多挑戰(zhàn)。

傳統(tǒng)的蛋白質(zhì)肽段組裝方法主要依賴高質(zhì)量質(zhì)譜數(shù)據(jù)庫以及已知的蛋白質(zhì)序列或者基因組，通過參考比對策略推斷出目標(biāo)蛋白質(zhì)的全長序列[1]。這類方法在分析已知蛋白時(shí)表現(xiàn)良好。然而，對于新型病毒或突變的蛋白質(zhì)，由于其部分序列未包含在已知數(shù)據(jù)庫中，傳統(tǒng)方法難以識別匹配新序列，無法有效解析未知蛋白。此外，傳統(tǒng)組裝方法計(jì)算復(fù)雜度高，限制了其在新型蛋白質(zhì)研究中的應(yīng)用。

隨著質(zhì)譜技術(shù)的不斷發(fā)展以及配套算法的迭代，肽段從頭組裝逐漸成為蛋白質(zhì)鑒定的主流技術(shù)。不同于傳統(tǒng)數(shù)據(jù)庫比對方法，從頭組裝不依賴已知序列數(shù)據(jù)庫，而是通過分析原始肽段數(shù)據(jù)之間的重疊關(guān)系與出現(xiàn)頻率直接拼接序列。然而，從頭組裝方法同樣面臨諸多困難。第一，質(zhì)譜測序錯(cuò)誤導(dǎo)致肽段錯(cuò)誤拼接的風(fēng)險(xiǎn)增加；第二，測序過程中肽段丟失導(dǎo)致組裝序列覆蓋率顯著下降。

近年來，基于de Bruijn圖的ALPS算法被廣泛應(yīng)用到蛋白質(zhì)肽段組裝領(lǐng)域。ALSP算法通過肽段間的k-mer（即肽段子串） 重疊關(guān)系簡化了組裝路徑的搜索過程，極大地提升了從頭組裝的效率與準(zhǔn)確性[2]。盡管該算法在性能與效果上優(yōu)于傳統(tǒng)組裝方法，但其核心仍然是肽段間的連續(xù)重疊關(guān)系。在實(shí)際應(yīng)用中，質(zhì)譜測序錯(cuò)誤會導(dǎo)致圖中路徑出現(xiàn)錯(cuò)誤分支，而測序中肽段的缺失會直接破壞重疊結(jié)構(gòu)的連續(xù)性，導(dǎo)致組裝結(jié)果出現(xiàn)局部最優(yōu)。

針對上述挑戰(zhàn)，本文提出了一種基于N-gram算法的路徑優(yōu)化策略，旨在修復(fù)de Bruijn圖的斷裂節(jié)點(diǎn)，從而提升肽段組裝的性能。N-gram相似度算法通過計(jì)算劃分子串之間的相似度[3]，能夠識別因測序錯(cuò)誤或者突變導(dǎo)致的非重疊區(qū)域，并通過概率對肽段子串（節(jié)點(diǎn)） 篩選替換。整體流程圖如圖1所示。結(jié)合容錯(cuò)機(jī)制對蛋白質(zhì)序列進(jìn)行擴(kuò)展組裝，顯著提升了組裝序列的覆蓋度與BLAST比對的得分。此研究主要的貢獻(xiàn)如下。

1） 提出了一種基于N-gram相似度增強(qiáng)蛋白質(zhì)肽段組裝的方法，解決de Bruijn圖斷裂節(jié)點(diǎn)問題，該方法有效擴(kuò)展了蛋白質(zhì)組裝序列，為確定蛋白質(zhì)全長序列提供了新思路。

2） 在多個(gè)實(shí)際數(shù)據(jù)集中驗(yàn)證了該方法的有效性，實(shí)驗(yàn)結(jié)果顯示在肽段組裝的覆蓋率與BLAST比對的得分均優(yōu)于傳統(tǒng)組裝方法。

1 相關(guān)研究

近年來，蛋白質(zhì)肽段組裝方法主要依賴于兩種基于圖論的策略：基于de Bruijn圖組裝方法和基于Overlap-Layout-Consensus（OLC） 圖組裝方法。表1對比了這兩種方法的適用場景以及局限性，并在下面介紹了相關(guān)算法。

基于OLC圖的組裝方法包括三個(gè)核心步驟：1） 計(jì)算reads（即原始肽段） 之間的序列相似性，找到其中具有重疊區(qū)域的肽段對；2） 以reads構(gòu)建重疊圖布局，原始reads作為圖的節(jié)點(diǎn)，邊表示reads之間的重疊關(guān)系；3） 尋找共識序列，通過尋找重疊圖的路徑，合并重疊reads，最終輸出肽段組裝序列。該方法更適合長reads的組裝，算法Meta-SPS[4]和MuCS[5]方法采用OLC框架的策略實(shí)現(xiàn)，通過穩(wěn)健的重疊群進(jìn)行延伸和校正。

基于de Bruijn圖的組裝方法則需將reads劃分為k-mers并構(gòu)建de Bruijn圖，通過尋找歐拉路徑推斷出組裝序列。這種方法更適合短reads組裝，相關(guān)的算法有ISEA[6]和ALPS[7]。ISEA在de Bruijn圖中擴(kuò)展種子時(shí)，通過引入基于雙端信息和插入片段分布的精細(xì)評分函數(shù)解決重復(fù)區(qū)域的問題，減少錯(cuò)誤肽段對組裝序列的影響。ALPS則對de Bruijn圖的節(jié)點(diǎn)賦予置信度評分，以貪婪算法尋找最優(yōu)路徑，這種策略表現(xiàn)出更高的容錯(cuò)性與計(jì)算效率。

在蛋白質(zhì)組學(xué)研究中，質(zhì)譜技術(shù)因其成本低、高靈敏度和高分辨率等優(yōu)點(diǎn)，是目前普遍使用的測序技術(shù)。質(zhì)譜技術(shù)會產(chǎn)生大量短肽段，更適合de Bruijn圖方法進(jìn)行肽段組裝。其中，ALPS被廣泛應(yīng)用于蛋白質(zhì)鑒定。因此本研究以de Bruijn圖算法作為肽段組裝的核心算法。

2 方法描述

2.1 de Bruijn圖構(gòu)建

de Bruijn圖是蛋白質(zhì)序列組裝的重要工具。基于de Bruijn圖的組裝流程主要包括三個(gè)主要步驟：數(shù)據(jù)預(yù)處理、de Bruijn圖構(gòu)建和最優(yōu)路徑選擇。具體而言，蛋白質(zhì)經(jīng)過酶解后，通過質(zhì)譜儀生成相關(guān)的肽段質(zhì)譜，由數(shù)據(jù)庫搜索或者從頭測序的方法識別得到肽段序列[8]。

首先，在數(shù)據(jù)預(yù)處理階段，對置信度過低的肽段序列以及序列中非氨基酸部分進(jìn)行剔除。以預(yù)處理后的肽段數(shù)據(jù)作為de Bruijn圖構(gòu)建的輸入數(shù)據(jù)。首先，將每一個(gè)肽段劃分為以k為長度的子串[9]，也稱為k-mer。每一個(gè)k-mer的前k-1個(gè)氨基酸和后k-1個(gè)氨基酸作為圖的節(jié)點(diǎn)，也稱為（k-1）-mer節(jié)點(diǎn)。并以每一個(gè)k-mer作為圖的有向邊，同時(shí)為每一個(gè)節(jié)點(diǎn)設(shè)置權(quán)重，最終形成de Bruijn圖，如圖2所示。

節(jié)點(diǎn)權(quán)重是圖路徑選擇的核心參數(shù)，權(quán)重設(shè)置為肽段置信度的加權(quán)幾何平均值，置信度加權(quán)幾何平均值（公式1） 從原始肽段置信度出發(fā)綜合評估（k-1）-mer的整體可信度。其次，節(jié)點(diǎn)（k-1）-mer設(shè)置了位置權(quán)重系數(shù)（公式2） ，位置權(quán)重系數(shù)使得序列組裝更加關(guān)注序列內(nèi)部氨基酸以及重疊關(guān)系。以節(jié)點(diǎn)（k-1）-mer={ai，ai+1，...，ai+k-2}為例，公式（1） （2） 如下所示：

[ωk-1-m?r=k-1-merlogI×j=ii+k-2confajwaj1j=ii+k-2waj] （1）

[waj=1，" j=i or j=i+k-25，" i+1≤j≤i+k-3] （2）

式中，[I]是肽段的強(qiáng)度，反映該肽段的豐度信息；[aj]表示節(jié)點(diǎn)中第j個(gè)氨基酸；[confaj]表示第j位氨基酸的置信度；[w（aj）]為位置權(quán)重系數(shù)，強(qiáng)調(diào)節(jié)點(diǎn)內(nèi)部氨基酸的可靠性。節(jié)點(diǎn)權(quán)重通過公式（1） 計(jì)算每個(gè)（k-1）-mer的累積權(quán)重。相比于傳統(tǒng)ALPS方法直接采用算術(shù)平均置信度的線性模型，本研究設(shè)置了對數(shù)變換放大權(quán)重差異，使不同肽段的權(quán)重差異更加明顯，從而提升圖路徑選擇的準(zhǔn)確性。

傳統(tǒng)基于de Bruijn圖的肽段組裝方法ALPS采用最大權(quán)重種子優(yōu)先策略，通過使用貪婪算法不斷向后和向前迭代新種子以完成蛋白質(zhì)肽段組裝。但由于肽段數(shù)據(jù)集中部分重疊肽缺失以及測序錯(cuò)誤的情況，該方法無法獲得更長的和完整的蛋白質(zhì)序列。

2.2 N-gram相似度計(jì)算

本文采用N-gram相似度容錯(cuò)機(jī)制改進(jìn)傳統(tǒng)de Bruijn圖的蛋白質(zhì)肽段組裝策略。N-gram相似度計(jì)算采用了N-gram統(tǒng)計(jì)語言[3]的思想，是一種常用于文本分析和集合匹配的算法，用于衡量兩個(gè)字符串之間的相似程度。其核心思想是將文本序列分割為固定長度N的連續(xù)子序列。例如，“Hello”的2-gram為{“He”， “el”， “l(fā)l”， “l(fā)o”}，并以子序列共同出現(xiàn)頻率計(jì)算兩個(gè)序列之間的相似程度。

根據(jù)de Bruijn肽段組裝方法的特點(diǎn)，將斷裂節(jié)點(diǎn)對應(yīng)的（k-1）-mer序列（如ACDEF，k=6） 劃分為3-gram集合{“ACD”， “CDE”， “DEF”}，因圖節(jié)點(diǎn)的序列長度為5，N取3在計(jì)算內(nèi)存與容錯(cuò)匹配之間達(dá)成平衡。同時(shí)對候選節(jié)點(diǎn)劃分為3-gram集合（如候選節(jié)點(diǎn)ACDEG） ，其集合為{“ACD”， “CDE”， “DEG”}，通過公式（3） 計(jì)算斷裂節(jié)點(diǎn)與候選節(jié)點(diǎn)之間的相似度：

[SimA，B=GA∩GBmaxGA，GB] （3）

式中，[GA]表示斷裂節(jié)點(diǎn)序列的3-gram集合；[GB]表示候選節(jié)點(diǎn)的3-gram集合。[GA∩GB]表示GA與GB的公共3-gram元素?cái)?shù)量，[maxGA，GB]表示兩個(gè)集合元素的最大值。質(zhì)譜測序中常見的單氨基酸錯(cuò)誤，因此斷裂節(jié)點(diǎn)與候選節(jié)點(diǎn)序列只允許容錯(cuò)一位氨基酸以達(dá)成節(jié)點(diǎn)延伸。由于N設(shè)置為3，即相似度計(jì)算的分母為3，容錯(cuò)性機(jī)制要求斷裂節(jié)點(diǎn)集合與候選節(jié)點(diǎn)至少2個(gè)相同子序列，此時(shí)理論相似度閾值為[2∕3≈0.66]。實(shí)際設(shè)定閾值下限為0.6，當(dāng)候選節(jié)點(diǎn)與斷裂節(jié)點(diǎn)相似度大于0.6時(shí)，選擇其中權(quán)重最大的節(jié)點(diǎn)作為新的初始種子。

2.3 組裝過程與優(yōu)化策略

在傳統(tǒng)的de Bruijn圖的組裝過程[7]中，使用貪心算法不斷迭代最大權(quán)重種子以達(dá)成蛋白質(zhì)序列的組裝。受到外部環(huán)境的影響，組裝的蛋白質(zhì)序列長度有限。因此本文引入N-gram相似度容錯(cuò)機(jī)制來修復(fù)圖節(jié)點(diǎn)斷裂（如圖3所示） 而帶來的序列長度不足[10]。具體實(shí)施步驟分為四個(gè)核心階段。

1） 初始種子選擇策略。計(jì)算de Bruijn圖中所有（k-1）-mer節(jié)點(diǎn)的權(quán)重，選擇最大權(quán)重的節(jié)點(diǎn)作為初始種子，并記錄種子序列。對應(yīng)圖3中“權(quán)重最大的（k-1）-mer序列作為種子”。

2） 迭代擴(kuò)展階段。對應(yīng)圖3中，首先判斷種子是否存在后綴種子（節(jié)點(diǎn)） ，如果存在，在初始種子序列后拼接新氨基酸，拼接后刪除已使用的節(jié)點(diǎn)，避免重復(fù)計(jì)算。同時(shí)以后綴種子作為新初始種子，逐步迭代，直至初始種子不存在后綴節(jié)點(diǎn)，即圖節(jié)點(diǎn)斷裂。

3） N-gram錯(cuò)誤糾正。如圖3中所示，當(dāng)判斷種子的后綴為“False”，則拼接過程中遇到圖斷裂節(jié)點(diǎn)，計(jì)算斷裂節(jié)點(diǎn)與候選節(jié)點(diǎn)之間的N-gram相似度。若存在候選節(jié)點(diǎn)與斷裂節(jié)點(diǎn)的相似度大于設(shè)定閾值0.6，則從滿足條件的候選節(jié)點(diǎn)中選擇其中權(quán)重最大的節(jié)點(diǎn)替換原有的節(jié)點(diǎn)，繼續(xù)序列迭代擴(kuò)展。

4） 組裝終止判斷。若不存在候選節(jié)點(diǎn)與斷裂節(jié)點(diǎn)間相似度大于設(shè)定閾值，則種子結(jié)束向后拼接。以記錄初始種子節(jié)點(diǎn)以同樣的原理向前拼接，最終完成蛋白質(zhì)肽段的組裝。

相比于傳統(tǒng)貪心算法，本研究引入N-gram相似度算法允許單個(gè)氨基酸差異的模糊匹配，能夠有效緩解因重疊肽段缺失以及測序錯(cuò)誤導(dǎo)致的斷裂問題，提高肽段組裝的完整性。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 數(shù)據(jù)集

本文選取人類抗體與小鼠抗體蛋白質(zhì)肽段數(shù)據(jù)集作為實(shí)驗(yàn)測試數(shù)據(jù)。數(shù)據(jù)集來自Tran等人的團(tuán)隊(duì)實(shí)驗(yàn)[7]用于評估ALPS組裝算法。數(shù)據(jù)集可從數(shù)據(jù)庫MassIVE下載，編號為MSV000079801。本研究使用兩種質(zhì)譜測序方法：數(shù)據(jù)庫測序與從頭測序[11]。數(shù)據(jù)庫測序依賴現(xiàn)有的現(xiàn)有數(shù)據(jù)庫進(jìn)行比對，從而識別對應(yīng)肽段，這種方法能夠提供高置信度的肽段鑒定。從頭測序則不依賴數(shù)據(jù)庫，根據(jù)質(zhì)譜中質(zhì)荷比與豐度預(yù)測相應(yīng)的氨基酸。兩種不同測序方法生成的肽段數(shù)據(jù)集，以更加全面評估肽段組裝算法在不同實(shí)際應(yīng)用場景的適用性與魯棒性。

人類抗體數(shù)據(jù)集是由質(zhì)譜數(shù)據(jù)庫搜索測序所得，DS1-H（人類重鏈數(shù)據(jù)集） 包含14 743條肽段，DS1-L（人類輕鏈數(shù)據(jù)集） 包含13 177條肽段。老鼠抗體數(shù)據(jù)集由從頭測序所得，DS2-H（老鼠重鏈數(shù)據(jù)集） 包含14 767條肽段，DS2-L（老鼠輕鏈數(shù)據(jù)集） 包含13 750條肽段。表2展示了兩個(gè)數(shù)據(jù)集的詳細(xì)信息。

3.2 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)處理

實(shí)驗(yàn)在64位Linux操作系統(tǒng)下進(jìn)行，采用python語言編寫。硬件環(huán)境：CPU型號為Gen Intel（R） Core（TM） i9-12900K；GPU為NVIDIA GeForce RTX 3080Ti。軟件工具：VSCode；從頭測序工具采用DeepNovo[12]工具。

實(shí)驗(yàn)數(shù)據(jù)質(zhì)量直接影響蛋白質(zhì)肽段組裝結(jié)果。受到實(shí)驗(yàn)中噪聲以及檢測方式的影響，原始數(shù)據(jù)存在低置信度肽段、強(qiáng)度丟失與序列存在非氨基酸字符等問題。在組裝評估之前需對測序得到的蛋白質(zhì)肽段數(shù)據(jù)進(jìn)行如下預(yù)處理。

1） 置信度過濾

de Bruijn圖節(jié)點(diǎn)權(quán)重計(jì)算涉及肽段置信度。為確保組裝結(jié)果的可靠性，對原始肽段數(shù)據(jù)進(jìn)行置信度過濾。

首先進(jìn)行置信度匹配處理。對測序過程中肽段氨基酸個(gè)數(shù)與相應(yīng)置信度個(gè)數(shù)不匹配的肽段進(jìn)行處理。當(dāng)置信度的數(shù)量多于肽段氨基酸數(shù)量時(shí)，對多余的置信度數(shù)值進(jìn)行剔除；當(dāng)肽段氨基酸數(shù)量大于對應(yīng)置信度數(shù)量時(shí)，使用均值插值法[13]補(bǔ)充缺失的置信度。其次對低置信度肽段過濾。當(dāng)肽段中所有氨基酸置信度低于0.3時(shí)，我們認(rèn)為此肽段是不可信的，直接剔除。

2） 肽段強(qiáng)度處理

由于質(zhì)譜儀檢測靈敏度不足以及實(shí)驗(yàn)噪聲的影響，無論是質(zhì)譜數(shù)據(jù)庫測序或是使用深度學(xué)習(xí)的從頭測序，總會出現(xiàn)肽段強(qiáng)度數(shù)值丟失的狀況[14]。為確保組裝實(shí)驗(yàn)的完整性，對所有缺失的肽段強(qiáng)度值均以固定值100進(jìn)行補(bǔ)充。因?yàn)榕c實(shí)驗(yàn)中常見的肽段強(qiáng)度范圍（100 000以上） 相比，固定值100僅為強(qiáng)度下限的0.1%，可視為背景噪聲水平，對節(jié)點(diǎn)的權(quán)重計(jì)算影響也很小，并且在數(shù)據(jù)集中缺失強(qiáng)度的肽段很少，這種處理不會顯著影響組裝結(jié)果。

3） 肽段序列處理

測序得到的肽段序列有一部分帶有修飾信息[15]，如EGKHN（+0.98）HHT，表示氨基酸N存在質(zhì)量偏移修飾。在組裝肽段序列過程中，對肽段中非氨基酸部分使用正則表達(dá)式進(jìn)行合理剔除，只保留肽段氨基酸序列，以確保數(shù)據(jù)的規(guī)范性與一致性。

3.3 評價(jià)指標(biāo)

本文使用線上NCBI中的BLAST系統(tǒng)用于蛋白質(zhì)序列比對[16]。以其中序列覆蓋度（Query Cover） 、精確度（Per. Identity） 和BLAST比對的得分（Total Score） 作為組裝結(jié)果的評估指標(biāo)[17]。評價(jià)指標(biāo)的具體說明如下。

1） Query Cover反映出組裝序列中參與比對的部分占整個(gè)目標(biāo)序列總長度的百分比。Query Cover值越大，說明肽段組裝結(jié)果覆蓋目標(biāo)序列的范圍更廣。如公式（4） 所示：

[Query Cover=LbLq×100%] （4）

式中：[Lb]代表組裝結(jié)果實(shí)際比對區(qū)域的總長度，[Lq]代表目標(biāo)序列的總長度。

2） Per. Identity反映出組裝序列與目標(biāo)序列完全匹配的氨基酸占實(shí)際比對區(qū)域長度的百分比。Per. Identity越高，說明組裝結(jié)果更準(zhǔn)確，錯(cuò)誤率低。如公式（5） 所示：

[Per. Identity=MLb×100%] （5）

式中：[M]表示比對區(qū)域內(nèi)與目標(biāo)序列完全匹配的氨基酸個(gè)數(shù)，[Lb]代表組裝結(jié)果實(shí)際比對區(qū)域的總長度。

3） Total Score反映出組裝結(jié)果與目標(biāo)序列的整體相似度，是所有高得分片段（HSP） 的得分總和。得分計(jì)算基于BLOSUM62計(jì)分矩陣和間隙（gap） 懲罰，BLOSUM62計(jì)分矩陣是一種基于進(jìn)化信息的氨基酸替換矩陣，用于評估兩個(gè)氨基酸之間的相似性得分。在序列比對中，引入間隙懲罰來避免過多插入間隙，以保持序列的連貫性。如公式（6） 所示：

[Total Score=i=1nSi] （6）

式中：[Si]為第i個(gè)HSP的得分，[n]為比對過程中檢測到的HSP數(shù)量。

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

為了驗(yàn)證本文提出的基于N-gram相似度增強(qiáng)蛋白質(zhì)序列組裝算法的有效性，我們引入基于de Bruijn圖的算法ALPS在相同的數(shù)據(jù)集上進(jìn)行驗(yàn)證，通過Total Score、Query Cover和Per. Identity這三個(gè)評估指標(biāo)進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表3所示。

1） 結(jié)果分析

從表3可以得出，改進(jìn)的組裝方法N-gram+de Bruijn在Query Cover與Total Score方面優(yōu)于ALPS。特別是當(dāng)目標(biāo)蛋白質(zhì)序列較長的情況，改進(jìn)方法的組裝效果更加的顯著。

在DS1-H數(shù)據(jù)集上，Query Cover從77%提升至95%，提升了18個(gè)百分點(diǎn)；Total Score從702提升至845，提升了143；但Per. Identity略微下降，從99.71%降至95.41%。

在DS2-H數(shù)據(jù)集上，Query Cover從60%提升至82%，提升了22個(gè)百分點(diǎn)；Total Score從556提升至742，提升了186；但Per. Identity從92.78%下降至92.27%。

盡管該方法在這兩個(gè)數(shù)據(jù)集精度有所下降，這是由于引入N-gram機(jī)制在優(yōu)化覆蓋率的同時(shí)會引入部分錯(cuò)配肽段，但整體上該方法有效提升了組裝結(jié)果的覆蓋率與BLAST比對的得分。在DS1-L和DS2-L（目標(biāo)序列長度不超過219） 的數(shù)據(jù)集上，實(shí)驗(yàn)結(jié)果表明，兩種方法的蛋白質(zhì)組裝效果基本一致，說明在較短的序列上，N-gram機(jī)制影響較小。

2） 圖示分析

為了更加直觀地展示本文方法的肽段組裝的性能，將N-gram+de Bruijn方法與ALPS方法在DS1-H的組裝結(jié)果進(jìn)行可視化展示。結(jié)果如圖4所示。

圖4（a） 與圖4（b） 分別展示了ALPS與N-gram+de Bruijn在DS1-H數(shù)據(jù)集上的組裝效果。從圖4（a） 與圖4（b） 可以得出，相比于ALPS組裝結(jié)果，本文方法組裝的蛋白質(zhì)序列幾乎覆蓋目標(biāo)蛋白質(zhì)序列，斷裂點(diǎn)明顯減少。圖4（c） 進(jìn)一步展示了組裝細(xì)節(jié)，其中紅色表示正確匹配的氨基酸，藍(lán)色表示錯(cuò)配區(qū)域。相比于ALPS，該方法在組裝結(jié)果上存在更多錯(cuò)配氨基酸。

N-gram+de Bruijn方法與ALPS方法在DS2-H數(shù)據(jù)集上的組裝可視化結(jié)果如圖5所示。

圖5（a） 與圖5（b） 分別展示了ALPS與N-gram+de Bruijn在DS2-H數(shù)據(jù)集上的組裝效果。從圖5（a） 與圖5（b） 可以得出，相比于ALPS組裝結(jié)果，本文方法組裝結(jié)果覆蓋率明顯提升，在原有的基礎(chǔ)上向前進(jìn)行了擴(kuò)展延伸。圖5（c） 進(jìn)一步展示了組裝細(xì)節(jié)，同樣隨著覆蓋率提升，錯(cuò)配氨基酸有所增加，組裝精度輕微下降。

本文方法在DS1-L與DS2-L數(shù)據(jù)集上的肽段組裝效果與ALPS相當(dāng)，組裝序列基本覆蓋整個(gè)目標(biāo)序列，組裝效果如圖6所示。

整體來看，本文提出的方法有效減少了斷裂點(diǎn)的產(chǎn)生，并提高了肽段組裝的連貫性和完整性。在全長蛋白質(zhì)序列組裝領(lǐng)域，該方法展示了較高的準(zhǔn)確性與魯棒性，為了蛋白質(zhì)鑒定分析提供了參考。

4 結(jié)束語

本文設(shè)計(jì)了一種基于N-gram相似度算法增強(qiáng)蛋白質(zhì)肽段組裝的方法，通過引入N-gram相似度容錯(cuò)策略有效修復(fù)了因測序錯(cuò)誤或者重疊肽缺失造成的de Bruijn節(jié)點(diǎn)斷裂的狀況。試驗(yàn)結(jié)果表明，該方法顯著提升了蛋白質(zhì)肽段組裝的覆蓋率與BLAST比對的得分，但Per. Identity有所下降。這表明仍然需要優(yōu)化錯(cuò)配區(qū)域的處理策略，進(jìn)一步提高序列的準(zhǔn)確性。未來肽段組裝可以使用深度學(xué)習(xí)模型或者錯(cuò)誤校正機(jī)制，在保持序列覆蓋度的同時(shí)保證準(zhǔn)確性不下降。該方法為蛋白質(zhì)組學(xué)研究中的蛋白質(zhì)鑒定提供了有力的支持，并為后續(xù)研究提供了重要參考。

參考文獻(xiàn)：

[1] BESLIC D，TSCHEUSCHNER G，RENARD B，et al.Current state，existing challenges，and promising progress for de novo sequencing and assembly of monoclonal antibodies[J]. bioRxiv， 2022： 2022.07. 21.500409.

[2] 陸翼，葛成，徐晴，等.序列組裝在蛋白質(zhì)測序技術(shù)中的方法[J].現(xiàn)代計(jì)算機(jī)， 2023， 29 （4）： 18-24，48.

[3] 尹寶生，安鵬飛.通過N-gram增強(qiáng)局部上下文視野感知的中文生成式摘要[J].中文信息學(xué)報(bào)，2022，36（8）：135-143，153.

[4] GUTHALS A，CLAUSER K R，BANDEIRA N.Shotgun protein sequencing with meta-contig assembly[J].Molecular amp; Cellular Proteomics，2012，11（10）：1084-1096.

[5] MAI Z B，ZHOU Z H，HE Q Y，et al.Highly robust de novo full-length protein sequencing[J].Analytical Chemistry，2022，94（8）：3467-3475.

[6] LI M，LIAO Z，HE Y，et al.ISEA：iterative seed-extension algorithm for de novo assembly using paired-end information and insert size distribution[J].IEEE/ACM Trans Comput Biol Bioinform，2017，14（4）：916-925.

[7] TRAN N H，RAHMAN M Z，HE L，et al.Complete de novo assembly of monoclonal antibody sequences[J].Scientific Reports，2016，6：31730.

[8] COX J.Prediction of peptide mass spectral libraries with machine learning[J].Nature Biotechnology，2023，41（1）：33-43.

[9] 翟海霞，蔡文達(dá)，劉小燕，等.利用HiFi讀數(shù)和k-mer分布特征的序列組裝方法[J].小型微型計(jì)算機(jī)系統(tǒng)，2024，45（6）：1376-1383.

[10] LU Z L，LI R P，LU K，et al.Semantics-empowered communications：a tutorial-cum-survey[J].IEEE Communications Surveys amp; Tutorials，2024，26（1）：41-79.

[11] NG C C A，ZHOU Y，YAO Z P.Algorithms for de-novo sequencing of peptides by tandem mass spectrometry：a review[J].Analytica Chimica Acta，2023，1268：341330.

[12] TRAN N H，ZHANG X，XIN L，et al.De novo peptide sequencing by deep learning[J].Proceedings of the National Academy of Sciences of the United States of America，2017，114（31）：8247-8252.

[13] KONG W J，HUI H W H，PENG H，et al.Dealing with missing values in proteomics data[J].Proteomics，2022，22（23/24）：e2200092.

[14] VITORINO R，GUEDES S，TRINDADE F，et al.De novo sequencing of proteins by mass spectrometry[J].Expert Review of Proteomics，2020，17（7/8）：595-607.

[15] FOREMAN R E，GEORGE A L，REIMANN F，et al.Peptidomics：a review of clinical applications and methodologies[J].Journal of Proteome Research，2021，20（8）：3782-3797.

[16] ZARU R，ORCHARD S，CONSORTIUM U.UniProt tools：BLAST，align，peptide search，and ID mapping[J].Current Protocols，2023，3（3）：e697.

[17] SAMAL K C，SAHOO J P，BEHERA L，et al.Understanding the BLAST （basic local alignment search tool） program and a step-by-step guide for its use in life science research[J].Bhartiya Krishi Anusandhan Patrika， 2021， 36（1）： 55-61.

【通聯(lián)編輯：李雅琪】