Rxivist logo

Rxivist combines preprints from bioRxiv with data from Twitter to help you find the papers being discussed in your field. Currently indexing 60,239 bioRxiv papers from 267,831 authors.

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,335 times
  • Download rankings, all-time:
    • Site-wide: 4,253 out of 60,239
    • In bioinformatics: 842 out of 6,078
  • Year to date:
    • Site-wide: 43,900 out of 60,239
  • Since beginning of last month:
    • Site-wide: 42,942 out of 60,239

Altmetric data


Downloads over time

Distribution of downloads per paper, site-wide


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


News