- 27 September 2021
- book chapter
- Published by Springer Nature
- Vol. 12944, 3-12
Abstract
The extended Burrows Wheeler Transform (\(\mathrm {eBWT}\)) was introduced by Mantaci et al. [TCS 2007] to extend the definition of the \(\mathrm {BWT}\) to a collection of strings. In our prior work [SPIRE 2021], we give a linear-time algorithm for the \(\mathrm {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 \(\mathrm {eBWT}\), i.e., run-length encoded \(\mathrm {eBWT}\) and \(\mathrm {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 \(\mathrm {eBWT}\) can be efficiently supported.
Keywords
This publication has 23 references indexed in Scilit:
- Optimal Lower and Upper Bounds for Representing SequencesACM Transactions on Algorithms, 2015
- On the combinatorics of suffix arraysInformation Processing Letters, 2013
- Efficient Algorithm for Circular Burrows-Wheeler TransformLecture Notes in Computer Science, 2012
- Storage and Retrieval of Highly Repetitive Sequence CollectionsJournal of Computational Biology, 2010
- Fast and accurate short read alignment with Burrows–Wheeler transformBioinformatics, 2009
- Ultrafast and memory-efficient alignment of short DNA sequences to the human genomeGenome Biology, 2009
- Permuted Longest-Common-Prefix Array2009
- An extension of the Burrows–Wheeler TransformTheoretical Computer Science, 2007
- Counting permutations with given cycle structure and descent setJournal of Combinatorial Theory, Series A, 1993
- Suffix Arrays: A New Method for On-Line String SearchesSIAM Journal on Computing, 1993