Online Heuristic Computation of Near-Optimal BWT for Dynamically Growing String Collections

The 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 (optBWT) construction algorithm for string collections 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 — onptBWT (Online Computation of Near-Optimal BWT). This algorithm requires onlyO (r log n) bits of space andO (m log r) time (where n is the dataset length, mis 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 near-optimal 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 onptBWT is only 1.41% higher than that of optBWT, outperforming six other BWT construction algorithms. In scenarios where the newly added strings are significantly smaller than the original string collection, onptBWT achieves faster construction speed and lower peak memory usage compared to the offline optBWT algorithm. Source code is available at https://github.com/xiaoYu0103/onptBWT.git.