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