Rxivist logo

Rxivist combines preprints from bioRxiv with data from Twitter to help you find the papers being discussed in your field. Currently indexing 72,923 bioRxiv papers from 317,485 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,370 times
  • Download rankings, all-time:
    • Site-wide: 5,080 out of 72,924
    • In bioinformatics: 964 out of 7,123
  • Year to date:
    • Site-wide: 65,929 out of 72,924
  • Since beginning of last month:
    • Site-wide: 65,929 out of 72,924

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


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