osptBWT：动态增长字符串集合的次优BWT在线计算方法

he Burrows-Wheeler Transform (BWT) is a core technology in many modern compression and bioinformatics applications. Constructing the BWT for dynamically growing string collections remains a challenge. The existing optimal BWT construction algorithm for string collections (optBWT) can significantly reduce the number of BWT runs r for a given string collection. However, it requires reconstructing the entire BWT when new strings are added. To address this issue, this paper proposes an online BWT construction algorithm based on dynamic insertion interval-Online Computation of Suboptimal BWT(osptBWT). This algorithm requires only O(rlogn) bits of space and O(mlogr) time (where n is the dataset length, m is the length of the newly added string, and r is the number of runs) for each new string added to produce a BWT that is suboptimal by only a small margin compared to optBWT in terms of runs r. Experimental results show that, across seven real-world genomic datasets, the average number of runs produced by osptBWT is only 1.41% higher than that of optBWT, outperforming six other BWT construction algorithms. Moreover, the peak memory usage is only 63% of the best-performing online BWT construction algorithm. In scenarios where the newly added strings is significantly smaller than the original string collection, osptBWT achieves faster construction speed and lower peak memory usage compared to the offline optBWT algorithm. Source code is available at https://github.com/xiaoYu0103/osptBWT.git.