The Burrows-Wheeler transform of an elastic-degenerate string and its application to pattern matching
Lapo Cioni, Veronica Guerrini, Giovanna Rosone · Theoretical Computer Science · 2025
In recent times there has been an increase in the amount of individual genomes sequenced for species, which are highly repetitive sequence collections known as pangenomes. Pangenomes can be represented in different ways, from strings to graphs, each with its own advantages and disadvantages. We focus on one of these representations: elastic-degenerate strings. An elastic-degenerate string (EDS) is a string whose symbols, called degenerate symbols , are comprised of one or more strings of any length, including the empty string (hence, we can have several alternatives per symbol). In this paper, we generalize to EDS the Burrows-Wheeler transform extended to a string collection. We define the Burrows-Wheeler transform of an Elastic-Degenerate String (called EDS-BWT), and show that it is a reversible transformation and it can be used for pattern matching, i.e., for finding the occurrences of a standard string pattern within an EDS. In particular, the inner properties of the classical Burrows-Wheeler transform are adapted in order to design a backward search strategy for pattern matching on an EDS. Furthermore, we analyze the worst-case complexity of that backward search. Thanks to our prototype edsBWTSearch , we experimentally compare our pattern matching approach to other existing tools managing elastic degenerate strings.