r-Indexing the eBWT

Marinella Sciortino, Christina Boucher, Zsuzsanna Lipták, Massimiliano Rossi, Davide Cenzato

Risultato della ricerca: Conference contribution

Abstract

The extended Burrows Wheeler Transform (eBWT ) was introduced by Mantaci et al. [TCS 2007] to extend the definition of the BWT to a collection of strings. In our prior work [SPIRE 2021], we give a linear-time algorithm for the eBWT that preserves the fundamental property of the original definition (i.e., the independence from the input order). The algorithm combines a modification of the Suffix Array Induced Sorting (SAIS) algorithm [IEEE Trans Comput 2011] with Prefix Free Parsing [AMB 2019; JCB 2020]. In this paper, we show how this construction algorithm leads to r-indexing the eBWT, i.e., run-length encoded eBWT and SA samples of Gagie et al. [SODA 2018] can be constructed efficiently from the components of the PFP. Moreover, we show that finding maximal exact matches (MEMs) between a query string and the r-index of the eBWT can be efficiently supported.
Lingua originaleEnglish
Titolo della pubblicazione ospiteLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pagine3-12
Numero di pagine10
Stato di pubblicazionePublished - 2021

Serie di pubblicazioni

NomeLECTURE NOTES IN ARTIFICIAL INTELLIGENCE

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

Cita questo