Sorry, you need to enable JavaScript to visit this website.

On different variants of the Burrows-Wheeler-Transform of string collections

Citation Author(s):
Davide Cenzato, Zsuzsanna Lipták
Submitted by:
Davide Cenzato
Last updated:
5 March 2022 - 8:18am
Document Type:
Poster
Document Year:
2022
Event:
Presenters:
Davide Cenzato
Paper Code:
217
 

The extended Burrows-Wheeler-Transform (eBWT), introduced by Mantaci et al. [Theor. Comput. Sci., 2007], is a generalization of the Burrows-Wheeler-Transform (BWT) to multisets of strings. While the original BWT is based on the lexicographic order, the eBWT uses the omega-order, which differs from the lexicographic order in important ways. A number of tools are available that compute the BWT of string collections; however, the data structures they generate in most cases differ from the one originally defined, as well as from each other. In this paper, we review the differences between these BWT variants, both from a theoretical and from a practical point of view, comparing them on several real-life data sets with different characteristics.

up
0 users have voted: