基于并行化诱导排序快速实现Burrows-Wheeler 变换算法

窦岩

摘要：为解决生物序列比对算法中主流索引技术Burrows-Wheeler变换（BWT） 构建索引效率低的问题，文章提出了一种利用并行化诱导排序改进BWT索引构建的方法。首先，该研究充分发挥诱导排序的线性時间复杂度优势，高效地建立后缀数组。其次，基于此，采用并行化优化算法对后缀类型和子串处理过程进行优化。最后，通过与主流算法在真实生物数据集上的对比实验，结果显示，经过优化的算法在索引构建速度上相较于传统算法取得了明显的提升，从而证明了该方法的有效性。

关键词：BWT索引；后缀数组；诱导排序；并行化

中图分类号：TP319 文献标识码：A

文章编号：1009-3044（2024）11-0036-03