竇巖

摘要：為解決生物序列比對算法中主流索引技術(shù)Burrows-Wheeler變換（BWT） 構(gòu)建索引效率低的問題，文章提出了一種利用并行化誘導(dǎo)排序改進BWT索引構(gòu)建的方法。首先，該研究充分發(fā)揮誘導(dǎo)排序的線性時間復(fù)雜度優(yōu)勢，高效地建立后綴數(shù)組。其次，基于此，采用并行化優(yōu)化算法對后綴類型和子串處理過程進行優(yōu)化。最后，通過與主流算法在真實生物數(shù)據(jù)集上的對比實驗，結(jié)果顯示，經(jīng)過優(yōu)化的算法在索引構(gòu)建速度上相較于傳統(tǒng)算法取得了明顯的提升，從而證明了該方法的有效性。

關(guān)鍵詞：BWT索引；后綴數(shù)組；誘導(dǎo)排序；并行化

中圖分類號：TP319 文獻標識碼：A

文章編號：1009-3044（2024）11-0036-03