Dynamic μ-PBWT: Dynamic Run-length Compressed PBWT for Biobank Scale Data.

Area of Science:

• Bioinformatics
• Computational Biology
• Genetics

Background:

• Positional Burrows-Wheeler Transform (PBWT) is crucial for haplotype analysis but lacks dynamic update capabilities.
• Existing dynamic solutions (d-PBWT) are memory-intensive, while static compressed versions (Syllable-PBWT, mu-PBWT) lack update functionality or have limited query types.

Purpose of the Study:

• To develop a memory-efficient and dynamically updatable compressed PBWT.
• To enable efficient haplotype matching and queries on large genetic datasets.

Main Methods:

• Run-length compression of PBWT to improve compression rates.
• Utilizing self-balancing trees to store compressed runs, facilitating dynamic updates (insertions/deletions).
• Implementing a long match query algorithm compatible with dynamic updates.

Main Results:

• Dynamic mu-PBWT achieves significant memory savings compared to d-PBWT.
• Updates (insertions/deletions) are constant time per site and can be performed without decompressing the index.
• The data structure supports dynamic updates and efficient long match queries.

Conclusions:

• Dynamic mu-PBWT offers a flexible and space-efficient indexing solution for large-scale genetic data analysis.
• It addresses the limitations of previous PBWT variants, enabling dynamic operations on compressed data.
• This method is well-suited for applications like statistical phasing, imputation, and IBD detection in biobanks.