Data Structures for SMEM-Finding in the PBWT

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• The positional Burrows-Wheeler Transform (PBWT) is crucial for identifying set-maximal exact matches (SMEMs) in haplotype data.
• Efficient storage of the PBWT and its associated divergence array is a key challenge in bioinformatics.
• Previous research has explored run-length encoding for the PBWT, but compressed storage of the divergence array remains less studied.

Purpose of the Study:

• To develop and evaluate a novel, memory-efficient data structure for storing the PBWT and its divergence array.
• To enable efficient computation of SMEMs using compressed data structures.
• To compare the memory usage and performance of the proposed data structure against existing methods.

Main Methods:

• Definition of two key queries for computing SMEMs.
• Design of smaller data structures supporting these queries.
• Combination of data structures for compressed storage of PBWT and divergence array.
• Estimation and comparison of memory usage for different data structures.
• Implementation and performance benchmarking on 1000 Genomes Project datasets.

Main Results:

• Identification of a most memory-efficient data structure for storing the PBWT and divergence array.
• Demonstration of the data structure's capability to support SMEM computation.
• Empirical comparison showing performance advantages over prior methods on real-world haplotype data.

Conclusions:

• The developed data structure offers a significant improvement in memory efficiency for storing PBWT and divergence array data.
• This advancement facilitates more scalable and efficient analysis of haplotype data for SMEM identification.
• The findings have implications for large-scale genomic data processing and analysis.