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.

The Burrows-Wheeler transform of an elastic-degenerate string and its application to pattern matching

Cioni L.;Guerrini V.;Rosone G.
2026-01-01

Abstract

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.
2026
Cioni, L.; Guerrini, V.; Rosone, G.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1377387
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact