String Partition for Building Long Burrows-Wheeler Transforms

2024/06/15 by Enno Adler, Adler, Enno, Stefan Böttcher +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2406.10610

openalex publication_date 2024/06/15 · openalex created_date 2024/06/19 · openalex updated_date 2026/07/28

Abstract

Constructing the Burrows-Wheeler transform (BWT) for long strings poses significant challenges regarding construction time and memory usage. We use a prefix of the suffix array to partition a long string into shorter substrings, thereby enabling the use of multi-string BWT construction algorithms to process these partitions fast. We provide an implementation, partDNA, for DNA sequences. Through comparison with state-of-the-art BWT construction algorithms, we show that partDNA with IBB offers a novel trade-off for construction time and memory usage for BWT construction on real genome datasets. Beyond this, the proposed partitioning strategy is applicable to strings of any alphabet.

Related

• IBB: Fast Burrows-Wheeler Transform Construction for Length-Diverse DNA Data
• A New Lightweight Algorithm to compute the BWT and the LCP array of a Set of Strings
• Computing the optimal BWT of very large string collections
• Efficient Construction of the BWT for Repetitive Text Using String Compression
• Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform