Computing the original eBWT faster, simpler, and with less memory

Area of Science:

• Bioinformatics
• Computational Biology
• String Algorithms

Background:

• The Burrows-Wheeler Transform (BWT) is vital for genomic data analysis, enabling compression and substring queries.
• The extended Burrows-Wheeler Transform (eBWT) was defined to handle collections of strings, maintaining order independence.
• Existing eBWT methods often disregard the original order-independent property, necessitating improved algorithms.

Purpose of the Study:

• To present a novel, linear-time algorithm for constructing the original extended Burrows-Wheeler Transform (eBWT).
• To develop an efficient method for computing the BWT of a single string without special symbols or Lyndon rotations.
• To enable the construction of eBWT on large genomic sequence collections by combining the new eBWT algorithm with prefix-free parsing (PFP).

Main Methods:

• A new linear-time algorithm for the original eBWT construction, avoiding preprocessing steps.
• A linear-time algorithm for single-string BWT computation, omitting end-of-string symbols and Lyndon rotations.
• Integration of the eBWT algorithm with a prefix-free parsing (PFP) variation for large-scale genomic data.

Main Results:

• The developed algorithm (pfpebwt) achieves the fastest construction times for eBWT on large genomic collections, with speedups up to 7.6x.
• Peak memory usage of pfpebwt is at most 2x that of the second-best method.
• Compared to methods reporting suffix array samples, pfpebwt offers a 57.1x improvement in peak memory.

Conclusions:

• The new eBWT construction algorithm is efficient and practical for analyzing large genomic datasets.
• pfpebwt provides a significant advancement in speed and memory efficiency for genomic sequence analysis tasks.
• The publicly available source code facilitates further research and application of these improved BWT algorithms.