陳俊濤，鄒 權(quán)

(電子科技大學(xué)基礎(chǔ)與前沿研究院 成都 610054)

多序列比對是生物信息學(xué)研究中重要的課題之一，對于識別未知基因功能、分析物種間的進(jìn)化關(guān)系、識別基因之間的保守區(qū)域等問題有著重要作用。隨著測序技術(shù)的發(fā)展，基因序列數(shù)據(jù)快速增長，現(xiàn)有軟件難以處理大規(guī)模的多序列比對問題。

目前大多數(shù)軟件采用的是漸進(jìn)式比對策略或者迭代式比對策略[1]，如MAFFT[2]、Kalign3[3]、Clustal[4-5]、MUSCLE[6]、T-Coffee[7]、HAlign[8]等。漸進(jìn)式比對需要先計算兩兩序列之間的距離，再根據(jù)距離矩陣使用層次聚類算法，如UPGMA、Neighbor Joining 等構(gòu)建一顆比對的指導(dǎo)樹，沿著指導(dǎo)樹的枝干進(jìn)行兩兩比對與合并，最后得到最終結(jié)果。而迭代式比對策略在此基礎(chǔ)上，還要對合并的最終結(jié)果選取適當(dāng)?shù)牟呗?，如剪枝、局部重新比對和隨機(jī)選取序列重新比對進(jìn)行迭代，直到比對精確收斂或者迭代次數(shù)達(dá)到上限。迭代式比對策略可以解決漸進(jìn)式比對初期可能遺留下的問題。因為漸進(jìn)式比對策略是貪心策略，在初期局部的比對結(jié)果上可能陷入局部最優(yōu)，而錯誤會一直保留至最終結(jié)果中。而通過迭代式比對可以選取適當(dāng)?shù)牟呗?，去更正局部比對的一些錯誤，但迭代式比對增加了時間復(fù)雜度。這兩者都有著較高的時間復(fù)雜度，所以難以在有限時間內(nèi)處理大規(guī)模數(shù)據(jù)的比對。

漸進(jìn)式比對策略的時間復(fù)雜度與序列數(shù)量呈多項式級增長，因此在面對大規(guī)模數(shù)據(jù)的情況下，該策略時間復(fù)雜度太高、比對時間過長。而星比對是一種啟發(fā)性的策略，其時間復(fù)雜度與序列數(shù)量呈線性增長，這有效降低了大規(guī)模序列比對的時間。然而，星比對算法在相似度不高的數(shù)據(jù)集上的比對精度較低，目前只能應(yīng)用到相似度非常高的同源序列上，這大大限制了星比對的應(yīng)用。

針對星比對精度低的問題，本文將漸進(jìn)比對的模式應(yīng)用于星比對中，提出了基于profile 比對的改進(jìn)星比對算法。實驗證明改進(jìn)后的算法提高了比對的精度，同時也節(jié)省了比對時間。

1 算 法

本研究改進(jìn)的星比對算法采用了漸進(jìn)比對的思想，先構(gòu)建一顆比對的指導(dǎo)樹，然后沿著樹的枝干進(jìn)行比對。但是與傳統(tǒng)的構(gòu)建指導(dǎo)樹的方法不同，本研究沿用了星比對的核心思想，即中心比對的思想。為了加快比對速度，引進(jìn)了k-band 策略以加速雙序列之間的比對。

1.1 雙序列比對

對于雙序列比對問題，主要采用動態(tài)規(guī)劃的方法，有全局比對Needleman-Wunsch 算法[9]和局部比對Smith-Waterman 算法[10]。

圖1 展示的是全局比對算法，即先建立一個得分矩陣然后根據(jù)計算規(guī)則計算最大得分(匹配+1、不匹配?1、空格?1)，再從右下角的最大得分回溯至左上角，得到最優(yōu)比對。

圖1 DNA 雙序列比對動態(tài)規(guī)劃算法

本研究采用的是仿射罰分與k-band 結(jié)合的雙序列全局比對算法[8]。不同于圖1 的線性罰分，仿射罰分的機(jī)制更為合理，這有效地避免了間斷出現(xiàn)缺失的情況，使得比對結(jié)果更傾向于連續(xù)出現(xiàn)缺失，這也更符合生物學(xué)的進(jìn)化過程，即一旦缺失位點(diǎn)出現(xiàn)，那么此位點(diǎn)就會有更大可能性再次出現(xiàn)缺失。k-band 策略指的是兩條序列較為相似時，回溯路線一般會在對角線附近，非對角線附近區(qū)域的值可以不用計算，只用計算對角線附近的寬為k的帶，這個寬為k的帶被稱為k-band。k-band 這一啟發(fā)性策略減少了比對的時間和空間復(fù)雜度，將時空復(fù)雜度由O(pn)降 低到了O(kn)(p和n為序列的長度，k為帶的寬度)。如圖1 所示，回溯路徑只出現(xiàn)在k=1的 灰色帶中。k的 初始值一般為p和n的差值的絕對值，然后進(jìn)行k值的迭代，計算比對的最優(yōu)得分，每次迭代k值翻倍，直到得分最大值收斂則停止迭代。

雖然采用k-band 策略的雙序列比對算法可以減少算法的時間和空間復(fù)雜度，但是不能確保找到最優(yōu)的比對，有可能會陷入局部最優(yōu)解中。為了減少此類情況的發(fā)生，只對序列長度相近的序列采取k-band 策略的比對，對于序列長度相差較大的序列則采取全局比對的方法。因為兩條序列長度相差較大，可能會導(dǎo)致k值迭代后的k-band 的區(qū)域很大，甚至超過原本pn大小的區(qū)域面積，不僅無法節(jié)省時間和空間，反而需要更大的時空復(fù)雜度。

1.2 傳統(tǒng)的星比對算法

傳統(tǒng)的星比對算法主要分為以下3 個步驟：

1)選取中心序列；

2)將中心序列與其余序列一一進(jìn)行比對；

3)根據(jù)“once gap, always gap”的原則，將雙序列比對的結(jié)果合并，得到最終的比對結(jié)果。

中心序列的選取是傳統(tǒng)星比對算法步驟中時間復(fù)雜度最高的，因為需要計算兩兩序列之間的相似度。傳統(tǒng)計算序列兩兩相似度的方法是動態(tài)規(guī)劃，時間復(fù)雜度為O(n2)。但是由于其復(fù)雜度太高，目前使用較為廣泛是使用k-mer 法計算序列相似度，其時間復(fù)雜度為O(n)。使用k-mer 計算序列間的相似度，選取中心序列的總體復(fù)雜度可降為O(m2n)，其中m為序列的條數(shù)，n為序列的長度。步驟2)需要將中心序列與其余序列一一做比對，其算法時間復(fù)雜度為O(kmn)。步驟3)合并序列比對結(jié)果的算法時間復(fù)雜度為O(mn)。結(jié)合3 個步驟的算法時間復(fù)雜度，該算法的總體時間復(fù)雜度為O(m2n+kmn)。

1.3 改進(jìn)的星比對算法

本研究對傳統(tǒng)的星比對算法進(jìn)行了改進(jìn)。首先，參考了cd-hit[11]聚類軟件的思路，將最長的序列作為中心序列。然后，引進(jìn)了漸進(jìn)比對的思想，將構(gòu)建指導(dǎo)樹和profile 比對的策略加入到改進(jìn)的星比對中來。

改進(jìn)的星比對算法主要有以下4 個步驟：

1)選取最長序列；2)計算最長序列與其余序列之間的相似度；

3)根據(jù)步驟2)得到的相似度構(gòu)建比對的指導(dǎo)樹。構(gòu)建指導(dǎo)樹的原則為，先將相似度最高的序列聚合，再依次根據(jù)相似度，將序列加入樹中，最終構(gòu)建一顆單鏈指導(dǎo)樹；

4)沿著指導(dǎo)樹進(jìn)行比對和合并，最終得到比對結(jié)果。

圖2 展示了構(gòu)建指導(dǎo)樹和比對的過程。本研究將序列中的最長序列作為中心序列，這大大降低了選取中心序列的時間。改進(jìn)后的星比對算法，雙序列比對只會在首次比對的時候出現(xiàn)，在指導(dǎo)樹的枝干上都是序列與profile 比對。與雙序列比對不同，序列與profile 比對計算得分耗時會更長，在一定程度上會增加比對的時間。因此，改進(jìn)后的星比對算法的時間復(fù)雜度與序列數(shù)量不呈現(xiàn)線性增長，其增長速度介于漸進(jìn)比對和傳統(tǒng)星比對之間。

圖2 4 條DNA 序列構(gòu)建指導(dǎo)樹

2 實 驗

本研究采用了模擬的RNA 數(shù)據(jù)來驗證算法的有效性。根據(jù)序列數(shù)量將數(shù)據(jù)集分5 個組，序列數(shù)量 分 別 為：256 條、512 條、1024 條、2048 條、4096 條，序列平均長度約為1500 個堿基對。每個組分別有20 個不同數(shù)據(jù)集，測試多數(shù)據(jù)集以求取精度的平均值，可以驗證算法的魯棒性，避免因為偶然性影響實驗結(jié)果的有效性。實驗數(shù)據(jù)來自于公開數(shù)據(jù)集網(wǎng)站https://kim.bio.upenn.edu/software/csd.shtml.

實驗采用了SP score 來衡量多序列比對的效果，該值是多序列比對中所有雙序列組合的比對得分之和。雙序列計算得分規(guī)則為：相同位置字符匹配則得1 分，不匹配或者兩者都是空格則得0 分。SP 分值越高則代表比對的效果越好。而在數(shù)據(jù)較大的時候，SP 值過大不能準(zhǔn)確展示其精度，因此本研究采用了SP 值的平均值來展示比對精度。

本研究對傳統(tǒng)的星比對算法做了兩項改進(jìn)：1)改進(jìn)選取“中心序列”的策略，以降低選取算法的時間復(fù)雜度；2)引進(jìn)了漸進(jìn)比對的思想，構(gòu)造一棵特殊的指導(dǎo)樹，加入profile 比對的策略。為了研究兩項改進(jìn)對比對精度的影響，本文設(shè)計了4 種實驗的算法組合：傳統(tǒng)的星比對算法+傳統(tǒng)的中心序列選取策略、傳統(tǒng)的星比對算法+選取最長序列、改進(jìn)的星比對算法+傳統(tǒng)的中心序列選取策略、改進(jìn)的星比對算法+選取最長序列，比對4 組實驗的精度和時間。4 組實驗都是在CPU 為Xeon E3-1230，內(nèi)存為32 G 的Ubuntu 20.04 系統(tǒng)環(huán)境下進(jìn)行的。

實驗結(jié)果如圖3 和圖4 所示。圖3 展示了4 組算法在不同數(shù)據(jù)集上的精度?？梢钥吹诫S著數(shù)據(jù)集的增大，比對的精度也隨之降低。

圖3 不同數(shù)據(jù)集的比對精度對比

圖4 不同數(shù)據(jù)集的比對時間對比

在使用傳統(tǒng)的星比對算法的基礎(chǔ)上，對比使用不同的選取中心序列的策略。使用k-mer 法計算相似度選取中心序列的策略明顯優(yōu)于使用最長序列計算相似度的策略，可以觀察到在5 組數(shù)據(jù)集中，使用最長序列策略的比對精度都要比傳統(tǒng)的策略低。而在使用改進(jìn)的星比對算法的基礎(chǔ)上，兩種選取中心序列的策略得到的比對效果近乎一致，無論是在比對精度的均值還是在比對精度的范圍上，兩者并無明顯差異。

在使用傳統(tǒng)策略選取中心序列的基礎(chǔ)上，改進(jìn)的星比對算法的比對精度明顯要優(yōu)于傳統(tǒng)的星比對算法。同樣，在使用最長序列作為中心序列的基礎(chǔ)上，改進(jìn)的星比對算法的比對精度也明顯優(yōu)于傳統(tǒng)的星比對算法。

由圖3 可知，在4 組實驗中，可以看到改進(jìn)的星比對算法的比對效果優(yōu)于傳統(tǒng)的星比對算法。從圖4 可知，使用最長序列作為中心序列的策略，可在一定程度上減少比對的時間。因此改進(jìn)的星比對算法加上使用最長序列作為中心序列的策略是最佳的組合方式，此組合可以得到最好的比對精度，同時不會顯著提升星比對的比對時間。

3 結(jié) 束 語

本文將傳統(tǒng)的星比對與漸進(jìn)比對相結(jié)合，提出了基于profile 比對的改進(jìn)星比對算法，改進(jìn)后的星比對算法顯著提高了比對的精度。為了減少比對時間，本研究還簡化了中心序列的選取，直接將最長序列作為中心序列。改進(jìn)前后的算法時間復(fù)雜度是一致的，但實際時間不一定一致，改進(jìn)的星比對算法運(yùn)行時間要略大于傳統(tǒng)的星比對算法。同時，兩者運(yùn)行時間隨著數(shù)據(jù)量級增大的增長速度是一致的。由此可見，本文提出的基于profile 比對的改進(jìn)星比對算法不僅提高了比對的精度，又通過簡化中心序列的選取減少了星比對中選取中心序列的時間，同時也并未增加比對算法的時間復(fù)雜度。