Haplotype Matching with GBWT for Pangenome Graphs

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Linear reference genomes and the positional Burrows-Wheeler transform (PBWT) have been standard for haplotype analysis.
• Pangenome graphs offer a more comprehensive representation of genomic variation than linear references.
• Haplotype matching in pangenome graphs presents challenges not directly addressed by linear genome methods.

Purpose of the Study:

• To formally define and generalize haplotype matches within pangenome graph-based haplotype sets.
• To adapt and evaluate efficient matching capabilities, similar to PBWT, for the graph Burrows-Wheeler transform (GBWT).
• To develop algorithms for various match types (set maximal, long, locally maximal, text maximal) on pangenome graph structures.

Main Methods:

• Generalization of haplotype match definitions from linear genomes to pangenome graphs.
• Application of the r-index data structure to the GBWT for efficient query processing.
• Development and analysis of algorithms for set maximal and long match queries on the GBWT.

Main Results:

• Formal definition of haplotype matches in pangenome graph contexts.
• Demonstration of set maximal and long match queries on the GBWT in almost linear time.
• Achieved query space complexity close to linear in the number of runs within the GBWT.
• Identified that long match algorithms also perform efficiently on the standard Burrows-Wheeler transform (BWT).

Conclusions:

• The proposed algorithms significantly enhance the efficiency of haplotype matching in pangenome graph data structures.
• This work bridges the gap between traditional linear genome analysis and advanced pangenome graph representations.
• The developed methods provide a foundation for more comprehensive and efficient genomic variation analysis using pangenomes.