Rxivist logo

A Graph Extension of the Positional Burrows-Wheeler Transform and its Applications

By Adam M. Novak, Erik Garrison, Benedict Paten

Posted 02 May 2016
bioRxiv DOI: 10.1101/051409 (published DOI: 10.1186/s13015-017-0109-9)

We present a generalization of the Positional Burrows-Wheeler Transform (PBWT) to genome graphs, which we call the gPBWT. A genome graph is a collapsed representation of a set of genomes described as a graph. In a genome graph, a haplotype corresponds to a restricted form of walk. The gPBWT is a compressible representation of a set of these graph-encoded haplotypes that allows for efficient subhaplotype match queries. We give efficient algorithms for gPBWT construction and query operations. We describe our implementation, showing the compression and search of 1000 Genomes data. As a demonstration, we use the gPBWT to quickly count the number of haplotypes consistent with random walks in a genome graph, and with the paths taken by mapped reads; results suggest that haplotype consistency information can be practically incorporated into graph-based read mappers.

Download data

  • Downloaded 1,433 times
  • Download rankings, all-time:
    • Site-wide: 9,939 out of 118,130
    • In bioinformatics: 1,296 out of 9,572
  • Year to date:
    • Site-wide: 101,241 out of 118,130
  • Since beginning of last month:
    • Site-wide: 110,950 out of 118,130

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)