Haplotype-aware graph indexes
Open Access
- 26 July 2019
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 36 (2) , 400-407
Abstract
The variation graph toolkit (VG) represents genetic variation as a graph. Although each path in the graph is a potential haplotype, most paths are non-biological, unlikely recombinations of true haplotypes. We augment the VG model with haplotype information to identify which paths are more likely to exist in nature. For this purpose, we develop a scalable implementation of the graph extension of the positional Burrows–Wheeler transform. We demonstrate the scalability of the new implementation by building a whole-genome index of the 5008 haplotypes of the 1000 Genomes Project, and an index of all 108 070 Trans-Omics for Precision Medicine Freeze 5 chromosome 17 haplotypes. We also develop an algorithm for simplifying variation graphs for k-mer indexing without losing any k-mers in the haplotypes. Our software is available at https://github.com/vgteam/vg, https://github.com/jltsiren/gbwt and https://github.com/jltsiren/gcsa2. Supplementary data are available at Bioinformatics online.Keywords
All Related Versions
Funding Information
- National Institutes of Health (5U41HG007234, 1U01HL137183-01)
- Wellcome Trust (WT206194, WT207492)
- W. M. Keck Foundation (DT06172015)
This publication has 24 references indexed in Scilit:
- Indexing Graphs for Path Queries with Applications in Genome ResearchIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2014
- Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT)Bioinformatics, 2014
- Short read alignment with populations of genomesBioinformatics, 2013
- Lightweight algorithms for constructing and inverting the BWT of string collectionsTheoretical Computer Science, 2013
- Exploring single-sample SNP and INDEL calling with whole-genomede novoassemblyBioinformatics, 2012
- The variant call format and VCFtoolsBioinformatics, 2011
- Storage and Retrieval of Highly Repetitive Sequence CollectionsJournal of Computational Biology, 2010
- Simultaneous alignment of short reads against multiple genomesGenome Biology, 2009
- Compressed indexes for dynamic text collectionsACM Transactions on Algorithms, 2007
- Indexing compressed textJournal of the ACM, 2005