近日，中國農(nóng)業(yè)科學(xué)院深圳農(nóng)業(yè)基因組研究所農(nóng)業(yè)基因組學(xué)技術(shù)研發(fā)與應(yīng)用創(chuàng)新團(tuán)隊(duì)提出DNA比對新算法，并研發(fā)出DNA比對軟件“BSAlign”。相比同類并行算法，新算法能夠更快生成最優(yōu)比對結(jié)果，且準(zhǔn)確度更高。相關(guān)研究成果發(fā)表在《基因組蛋白質(zhì)組與生物信息學(xué)報（Genomics, Proteomics & Bioinformatics）》上。
經(jīng)典的動態(tài)規(guī)劃算法，如史密斯-沃特曼算法和尼德曼-翁施算法，常用于處理序列比對，但由于其時間復(fù)雜度呈二次函數(shù)式增長，當(dāng)序列長度增加時，算法的處理時間也隨之變長，導(dǎo)致其在處理大規(guī)模序列比對時效率低下，嚴(yán)重阻礙了其應(yīng)用。
為此，研究人員提出了一種新的DNA序列對比算法——條紋移動法，該算法能夠在帶寬環(huán)境下實(shí)現(xiàn)高效運(yùn)算。經(jīng)測試，與現(xiàn)有并行算法相比，BSAlign算法的速度提升了2倍，在長序列比對方面，其效率較基于編輯距離的比對算法提高了1.5到4倍，在帶寬環(huán)境下實(shí)現(xiàn)了高效運(yùn)算。此外，研究人員還進(jìn)一步提出了主動F循環(huán)法，解決了條紋數(shù)據(jù)在長插入或刪除情況下的多次查詢問題，進(jìn)一步提高了處理速度和準(zhǔn)確性。
該研究得到了國家重點(diǎn)研發(fā)計劃、國家自然科學(xué)基金、中國農(nóng)業(yè)科學(xué)院科技創(chuàng)新工程等項(xiàng)目的資助。（通訊員 馬昕怡）
原文鏈接：https://academic.oup.com/gpb/advance-article/doi/10.1093/gpbjnl/qzae025/7628627
