Haplotype-aware graph indexes
Open accessPublished version of a preprint
Abstract
MOTIVATION: 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. RESULTS: 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. AVAILABILITY AND IMPLEMENTATION: Our software is available at https://github.com/vgteam/vg, https://github.com/jltsiren/gbwt and https://github.com/jltsiren/gcsa2. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
vg map aligns read kmers against all kmers in the reference graph, including those not in constituent haplotypes, leading to exponential growth in novel kmers during indexing and storage/complexity issues.
“The subcommand vg map aligns read kmers against all kmers in the reference graph, including those that do not exist in any constituent haplotypes, which can lead to exponential growth in novel kmers during indexing of the graph and therefore significant storage and complexity issues.”
From <tt>SAFARI</tt> : pangenome alignment of ancient DNA using purine/pyrimidine encodings (2025) · cites this paper as [20]
The Introduction (page unavailable) says graphs contain paths that recombine constituent haplotypes and that indexing all possible paths can be too complex. Results §3.3 (page unavailable) reports a risk of exponential growth during index construction and billions of recombination k-mers. But the paper says VG indexes a simplified, pruned graph—not all k-mers in the reference graph—so the claim overstates what vg map indexes. (LLM, conf=0.88)
Experimental — accuracy not yet measuredvg giraffe maps only to kmers traversed by the graph's embedded walks with a GBWT or GBZ index, reducing false positives.
“A faster alternative, vg giraffe, was developed to map only to kmers traversed by the graph’s embedded walks with the help of a GBWT or GBZ index, thus reducing false positives [20–22].”
From <tt>SAFARI</tt> : pangenome alignment of ancient DNA using purine/pyrimidine encodings (2025) · cites this paper as [20]
The Methods (§2.4) and Discussion (§4; page numbers unavailable) describe using GBWT haplotype paths to retain haplotype k-mers while pruning recombination k-mers that may cause false positives. They do not describe vg giraffe or a GBZ index. The Results (§3.3) also note that some recombination k-mers may remain, so the source does not support mapping only to k-mers traversed by embedded walks. (LLM, conf=0.88)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
References 31 · Cited by 92
Research works printed but not linked: 1
- Kuhnle A. et al (2019) Efficient construction of a complete index for pan-genomics read alignment. In: Proceedings of RECOMB 2019, Vol. 11467 of LNCS, Springer, Washington, DC, pp. 158– 173.
- Authors
- Sirén, J., Garrison, E., Novak, A. M., Paten, B., & Durbin, R.
- Affiliations
- University of California, Santa Cruz (US)
- Wellcome Sanger Institute (GB)
- University of Cambridge (GB)
- Corresponding author
- Sirén, Jouni
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2019-07-26
- Volume
- 36
- Issue
- 2
- Pages
- 400-407
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- PMC
- PMC7223266
- OpenAlex
- W2802134368
- Cited by
- 92
- References
- 31
- Citations by year
- 2026: 6 · 2025: 17 · 2024: 11 · 2023: 8 · 2022: 13 · 2021: 14 · 2020: 15 · 2019: 7 · 2012: 1
- FWCI
- 5.59
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Bioinformatics (publishedVersion, cc-by)
- bioRxiv (Cold Spring Harbor Laboratory) (acceptedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) (submittedVersion, cc-by)
- eScholarship (California Digital Library) (submittedVersion, cc-by)
- Apollo (University of Cambridge) (submittedVersion)
- arXiv (Cornell University)
- Leibniz international proceedings in informatics (cc-by)
- Apollo
- Funders
- National Institutes of Health (5U41HG007234, 1U01HL137183-01)
- Wellcome Trust (WT206194, WT207492)
- W. M. Keck Foundation (DT06172015)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Genome Rearrangement Algorithms
- Keywords
- variation graphs, graph indexing, haplotype reconstruction, k-mer indexing, graph simplification, 1000 Genomes Project
- MeSH terms
- Algorithms, Haplotypes, Software, Genome, Sequence Analysis, DNA
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
