r-Indexing the eBWT

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

r-Indexing the eBWT

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

Matematica e Informatica

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 originale	English
Titolo della pubblicazione ospite	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pagine	3-12
Numero di pagine	10
Stato di pubblicazione	Published - 2021

Serie di pubblicazioni

Nome	LECTURE NOTES IN ARTIFICIAL INTELLIGENCE

All Science Journal Classification (ASJC) codes

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

Altri file e collegamenti

OA Link

Cita questo

@inproceedings{cd8c8c692dc94c73ab5fe07eb9bb6a11,

title = "r-Indexing the eBWT",

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.",

author = "Marinella Sciortino and Christina Boucher and Zsuzsanna Lipt{\'a}k and Massimiliano Rossi and Davide Cenzato",

year = "2021",

language = "English",

isbn = "978-3-030-86691-4; 978-3-030-86692-1",

series = "LECTURE NOTES IN ARTIFICIAL INTELLIGENCE",

pages = "3--12",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - GEN

T1 - r-Indexing the eBWT

AU - Sciortino, Marinella

AU - Boucher, Christina

AU - Lipták, Zsuzsanna

AU - Rossi, Massimiliano

AU - Cenzato, Davide

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10447/526397

M3 - Conference contribution

SN - 978-3-030-86691-4; 978-3-030-86692-1

T3 - LECTURE NOTES IN ARTIFICIAL INTELLIGENCE

SP - 3

EP - 12

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -