A graph extension of the positional Burrows-Wheeler transform and its applications

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• The positional Burrows-Wheeler transform (PBWT) is a data structure for efficient pattern matching in large sequences.
• Genome graphs offer a compressed representation of multiple genomes, capturing variations and relationships.
• Haplotypes in genome graphs correspond to walks within the graph structure.

Purpose of the Study:

• To generalize the positional Burrows-Wheeler transform (PBWT) to genome graphs, creating the genome graph PBWT (gPBWT).
• To develop efficient algorithms for constructing and querying the gPBWT.
• To demonstrate the utility of gPBWT for haplotype consistency queries in graph-based read mapping.

Main Methods:

• Generalization of the PBWT to represent haplotypes as walks in genome graphs.
• Development of algorithms for gPBWT construction and efficient subhaplotype match queries.
• Application of gPBWT to count haplotype-consistent paths in genome graphs and with mapped reads.

Main Results:

• The gPBWT provides a compressible representation for graph-encoded haplotypes.
• Efficient algorithms for gPBWT construction and querying were developed.
• Haplotype consistency information can be practically integrated into graph-based read mappers.
• The gPBWT can store and search haplotype queries for approximately 100,000 diploid genomes, including structural variations.

Conclusions:

• The gPBWT is an efficient tool for representing and querying haplotypes in genome graphs.
• gPBWT facilitates the incorporation of haplotype information into graph-based read mappers.
• This method has the potential to significantly scale genomic data storage and analysis for haplotype queries.