基于并行化誘導排序快速實現(xiàn)Burrows-Wheeler 變換算法
2024-06-03 07:59:45竇巖
電腦知識與技術 2024年11期
竇巖
摘要：為解決生物序列比對算法中主流索引技術Burrows-Wheeler變換（BWT） 構建索引效率低的問題，文章提出了一種利用并行化誘導排序改進BWT索引構建的方法。首先，該研究充分發(fā)揮誘導排序的線性時間復雜度優(yōu)勢，高效地建立后綴數(shù)組。其次，基于此，采用并行化優(yōu)化算法對后綴類型和子串處理過程進行優(yōu)化。最后，通過與主流算法在真實生物數(shù)據(jù)集上的對比實驗，結果顯示，經過優(yōu)化的算法在索引構建速度上相較于傳統(tǒng)算法取得了明顯的提升，從而證明了該方法的有效性。
關鍵詞：BWT索引；后綴數(shù)組；誘導排序；并行化
中圖分類號：TP319 文獻標識碼：A
文章編號：1009-3044（2024）11-0036-03
