Prefix-free parsing for merging big BWTs.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Compression

Background:

• Prefix-free parsing (PFP) is essential for constructing Burrows-Wheeler Transforms (BWTs) of large datasets.
• Standard PFP methods require substantial memory, posing challenges for extremely large datasets.

Purpose of the Study:

• To develop a memory-efficient approach for building BWTs of massive datasets.
• To address the high memory footprint of PFP in bioinformatics applications.

Main Methods:

• Decomposition of large datasets into smaller, dissimilar subsets.
• Independent construction of BWTs for each subset.
• Merging of individual BWTs to form the complete dataset's BWT.

Main Results:

• Demonstrated significant reduction in memory requirements for PFP.
• Successfully applied the method to datasets with biological relevance (e.g., genomic collections).
• The merging strategy proved effective for large-scale BWT construction.

Conclusions:

• The proposed method offers a practical solution for memory-intensive BWT construction.
• This approach is particularly beneficial for fragmented biological datasets.
• Efficient BWT generation is crucial for advancing large-scale genomic data analysis.