BWT for string collections
Journal:
arXiv
Published Date:
Jun 1, 2025
Abstract
We survey the different methods used for extending the BWT to collections of
strings, following largely [Cenzato and Lipt\'ak, CPM 2022, Bioinformatics
2024]. We analyze the specific aspects and combinatorial properties of the
resulting BWT variants and give a categorization of publicly available tools
for computing the BWT of string collections. We show how the specific method
used impacts on the resulting transform, including the number of runs, and on
the dynamicity of the transform with respect to adding or removing strings from
the collection. We then focus on the number of runs of these BWT variants and
present the optimal BWT introduced in [Cenzato et al., DCC 2023], which
implements an algorithm originally proposed by [Bentley et al., ESA 2020] to
minimize the number of BWT-runs. We also discuss several recent heuristics and
study their impact on the compression of biological sequences. We conclude with
an overview of the applications and the impact of the BWT of string collections
in bioinformatics.
