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