經(jīng)典的動(dòng)態(tài)規(guī)劃算法,，如史密斯-沃特曼算法和尼德曼-翁施算法,，常用于處理序列比對(duì)，但由于其時(shí)間復(fù)雜度呈二次函數(shù)式增長(zhǎng),，當(dāng)序列長(zhǎng)度增加時(shí),，算法的處理時(shí)間也隨之變長(zhǎng),，導(dǎo)致其在處理大規(guī)模序列比對(duì)時(shí)效率低下，嚴(yán)重阻礙了其在大規(guī)模序列比對(duì)中的應(yīng)用,。目前并行加速比對(duì)的最優(yōu)算法有三種方法：通過(guò)增加數(shù)據(jù)并行度獲得加速的條紋法,；通過(guò)減少計(jì)算單元的字節(jié)數(shù)從而增加并行度的差分法；通過(guò)減少整體計(jì)算量獲得加速的帶寬法,。然而,，目前并沒有任何方法可以高效地結(jié)合這三種方法，獲得更快速的比對(duì)算法,。

為此,，研究人員提出了條紋移動(dòng)法，該算法在帶寬環(huán)境下實(shí)現(xiàn)了高效運(yùn)算,，并開發(fā)了主動(dòng)F循環(huán)法,，解決了條紋數(shù)據(jù)在長(zhǎng)插入或刪除情況下的多次查詢問題。這一創(chuàng)新顯著提高了比對(duì)速度,。與現(xiàn)有并行算法相比,，BSAlign比對(duì)算法的速度提升了2倍，在長(zhǎng)序列比對(duì)方面,，其效率較基于編輯距離的比對(duì)算法提高了1.5到4倍,。

這種新方法不僅克服了傳統(tǒng)方法的局限性，還在處理大規(guī)模數(shù)據(jù)時(shí)展示了卓越的性能,。條紋移動(dòng)法結(jié)合了數(shù)據(jù)并行度,、計(jì)算單元優(yōu)化和整體計(jì)算量減少的優(yōu)點(diǎn)，顯著提升了計(jì)算效率,。主動(dòng)F循環(huán)法則通過(guò)智能判斷并計(jì)算條紋數(shù)據(jù),，進(jìn)一步提高了處理速度和準(zhǔn)確性。通過(guò)這些創(chuàng)新,，BSAlign算法在多個(gè)實(shí)際應(yīng)用中表現(xiàn)出色,，包括基因組序列比對(duì)和其他需要高效大規(guī)模比對(duì)的領(lǐng)域，其顯著的性能提升,，使其成為大規(guī)模序列比對(duì)中的一種優(yōu)越選擇,。

條紋移動(dòng)算法原理

當(dāng)兩條DNA序列進(jìn)行比對(duì)時(shí)，動(dòng)態(tài)規(guī)劃算法會(huì)構(gòu)建一個(gè)比對(duì)矩陣,，如圖1a中的整個(gè)方形框,。帶寬法只計(jì)算與最優(yōu)路徑相關(guān)的單元，如圖1a中的帶顏色的單元,，其余白色區(qū)域不計(jì)算,。常規(guī)數(shù)據(jù)結(jié)構(gòu)是把連續(xù)的數(shù)據(jù)整齊地放進(jìn)寄存器（圖1b），而條紋數(shù)據(jù)結(jié)構(gòu)是把等間隔的數(shù)據(jù)整齊地放進(jìn)寄存器（圖1c）。對(duì)比常規(guī)數(shù)據(jù)結(jié)構(gòu),，條紋數(shù)據(jù)結(jié)構(gòu)在矩陣的迭代中保持很高的數(shù)據(jù)復(fù)用性,，如圖1c的（3，7,，11,，15）在4次迭代中均保持同樣結(jié)構(gòu)。因此本研究提出的條紋移動(dòng)法大大減少了計(jì)算的復(fù)雜性,。

圖1 | 條紋移動(dòng)算法

主動(dòng)F循環(huán)算法原理

在條紋數(shù)據(jù)結(jié)構(gòu)下，數(shù)據(jù)存在依賴關(guān)系,，增加了計(jì)算的復(fù)雜性,。例如第一個(gè)寄存器（0,4,8,12）里的8，精確的8單元的值是需要先計(jì)算4,，5,，6，7單元的值,，而精確的4單元的值是需要先計(jì)算1,，2，3單元的值,。以前的解決方案是使用被動(dòng)F循環(huán),，即通過(guò)多次循環(huán)，多次矯正以確保數(shù)據(jù)的準(zhǔn)確性（圖2a）,。該研究提出主動(dòng)F循環(huán),，即通過(guò)提前計(jì)算所有可能需要矯正的單元格，提前得出精確的初始值,，實(shí)現(xiàn)只需要兩次循環(huán)即可保證所有數(shù)據(jù)的準(zhǔn)確性（圖2b）,，再次減少計(jì)算的復(fù)雜性。

圖2 | 主動(dòng)F循環(huán)算法

BSAlign與其它序列比對(duì)算法的性能比較

本研究測(cè)試了真實(shí)數(shù)據(jù)和模擬數(shù)據(jù),，BSAlign在所有數(shù)據(jù)集均保持100%的準(zhǔn)確率,。在無(wú)帶寬算法中，BSAlign比同類算法快1.5倍以上,。在編輯距離的比對(duì)算法中,，BSAlign比同類算法快2.1倍以上。在長(zhǎng)插入或刪除的長(zhǎng)帶寬比較中,，BSAlign也優(yōu)于同類算法,。通過(guò)多種數(shù)據(jù)和多種方式的比較，均展示了BSAlign的優(yōu)越性能,，該研究達(dá)到此領(lǐng)域領(lǐng)先水平（表1）,。

表1 | 各種比對(duì)算法的運(yùn)算時(shí)間和準(zhǔn)確性比較

中國(guó)農(nóng)業(yè)科學(xué)院農(nóng)業(yè)基因組研究所阮玨研究員為該論文通訊作者和共同第一作者，邵浩靖副研究員為該論文共同第一作者,。

本研究得到了國(guó)家重點(diǎn)研發(fā)計(jì)劃,、國(guó)家自然科學(xué)基金,、深圳市科技創(chuàng)新委員會(huì)和中國(guó)農(nóng)業(yè)科學(xué)院科技創(chuàng)新工程的資助與支持。

原文鏈接：https://academic.oup.com/gpb/advance-article/doi/10.1093/gpbjnl/qzae025/7628627

BSAlign軟件免費(fèi)開發(fā)使用：https://github.com/ruanjue/bsalign