r-indexing the eBWT

Area of Science:

• Bioinformatics
• String Algorithms
• Data Compression

Background:

• The extended Burrows Wheeler Transform (eBWT) generalizes the Burrows Wheeler Transform to collections of strings.
• Prior work established a linear-time algorithm for eBWT construction, preserving input order independence.
• This algorithm integrates the Suffix Array Induced Sorting (SAIS) and Prefix Free Parsing (PFP) techniques.

Purpose of the Study:

• To demonstrate how the eBWT construction algorithm facilitates efficient r-indexing.
• To show the construction of run-length encoded eBWT and sampled Suffix Arrays (SA) from PFP components.
• To establish efficient support for finding maximal exact matches (MEMs) using the r-indexed eBWT.

Main Methods:

• Leveraging a linear-time eBWT construction algorithm based on SAIS and PFP.
• Utilizing components of the PFP for constructing the r-indexed eBWT.
• Applying the r-indexed eBWT structure for maximal exact match (MEM) queries.

Main Results:

• Efficient construction of the r-indexed eBWT from PFP components.
• Demonstration of efficient computation of run-length encoded eBWT and SA samples.
• Efficient support for finding maximal exact matches (MEMs) against the r-indexed eBWT.

Conclusions:

• The proposed method provides an efficient approach to r-indexing the eBWT.
• This enables practical applications in sequence analysis and data compression.
• The framework efficiently supports critical string matching operations like MEM identification.