CoChat

CHOP: haplotype-aware path indexing in population graphs

Open access
Mokveld, Tom, Linthorst, Jasper, Al-Ars, Zaid, Holstege, Henne, Reinders, Marcel · 2020 · Genome Biology

Published version of a preprint

Cited by 20

The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.

Abstract

The practical use of graph-based reference genomes depends on the ability to align reads to them. Performing substring queries to paths through these graphs lies at the core of this task. The combination of increasing pattern length and encoded variations inevitably leads to a combinatorial explosion of the search space. Instead of heuristic filtering or pruning steps to reduce the complexity, we propose CHOP, a method that constrains the search space by exploiting haplotype information, bounding the search space to the number of haplotypes so that a combinatorial explosion is prevented. We show that CHOP can be applied to large and complex datasets, by applying it on a graph-based representation of the human genome encoding all 80 million variants reported by the 1000 Genomes Project.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1186/s13059-020-01963-y

Cites

7 of 7 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 7 references

Research works printed but not linked: 35

  1. Paten B, et al.Genome graphs and the evolution of genome inference. Genome Res. 2017; 27(5):665–76. · DOI · Paper page
  2. Brandt DY, et al.Mapping bias overestimates reference allele frequencies at the HLA genes in the 1000 Genomes Project phase I data. G3 Genes Genomes Genet. 2015; 5(5):931–41. · DOI · Paper page
  3. Li H, Durbin R. Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinformatics. 2010; 26(5):589–95. · DOI · Paper page
  4. Dilthey A, et al.Improved genome inference in the MHC using a population reference graph. Nat Genet. 2015; 47(6):682–8. · DOI · Paper page
  5. Liu Y, et al.Discovery of common sequences absent in the human reference genome using pooled samples from next generation sequencing. BMC Genomics. 2014; 15(1):685. · DOI
  6. DePristo MA, et al.A framework for variation discovery and genotyping using next-generation DNA sequencing data. Nat Genet. 2011; 43(5):491. · DOI · Paper page
  7. Church D, et al.Extending reference assembly models. Genome Biol. 2015; 16(1):13. · DOI · Paper page
  8. Rumble SM, et al.SHRiMP: accurate mapping of short color-space reads. PLoS Comput Biol. 2009; 5(5):1000386. · DOI · Paper page
  9. Broder AZ. On the resemblance and containment of documents. In: Proceedings Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171). IEEE: 1997. p. 21–29.
  10. Popic V, Batzoglou S. A hybrid cloud read aligner based on MinHash and kmer voting that preserves privacy. Nat Commun. 2017; 8:15311. · DOI
  11. Ferragina P, Manzini G. Opportunistic data structures with applications. In: Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE: 2000. p. 390–398.
  12. Lippert RA. Space-efficient whole genome comparisons with Burrows–Wheeler transforms. J Comput Biol. 2005; 12(4):407–15. · DOI
  13. Schneeberger K, et al.Simultaneous alignment of short reads against multiple genomes. Genome Biol. 2009; 10(9):98. · DOI · Paper page
  14. Huang L, et al.Short read alignment with populations of genomes. Bioinformatics. 2013; 29(13):361–70. · DOI · Paper page
  15. Eggertsson HP, et al.Graphtyper enables population-scale genotyping using pangenome graphs. Nat Genet. 2017; 49:1654–1660. · DOI · Paper page
  16. Rautiainen M, et al.Bit-parallel sequence-to-graph alignment. Bioinformatics. 2019. https://doi.org/10.1093/bioinformatics/btz162. · DOI · Paper page
  17. Kim D, et al.Graph-based genome alignment and genotyping with HISAT2 and HISAT-genotype. Nat Biotechnol. 2019; 37(8):907–15. · DOI · Paper page
  18. Sirén J. Indexing variation graphs. In: 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM: 2017. p. 13–27. · DOI · Paper page
  19. Lee C, et al.Multiple sequence alignment using partial order graphs. Bioinformatics. 2002; 18(3):452–64. · DOI · Paper page
  20. Sirén J, et al.Indexing graphs for path queries with applications in genome research. IEEE/ACM Trans Comput Biol Bioinforma. 2014; 11(2):375–88. · DOI · Paper page
  21. Novak AM, et al.A graph extension of the positional Burrows–Wheeler transform and its applications. Algorithms Mol Biol. 2017; 12(1):18. · DOI · Paper page
  22. Sirén J, et al.Haplotype-aware graph indexes In: Parida L, Ukkonen E, editors. 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 2018. p. 4–1413. https://doi.org/10.4230/LIPIcs.WABI.2018.4. http://drops.dagstuhl.de/opus/volltexte/2018/9306. · doi:10.4230/lipics.wabi.2018.4
  23. Durbin R. Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT). Bioinformatics. 2014; 30(9):1266–72. · DOI · Paper page
  24. Gunady MK, et al.Yanagi: transcript segment library construction for RNA-Seq quantification. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 88. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: 2017.
  25. Li H. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. 2013. arXiv preprint arXiv:1303.3997. · arXiv
  26. Langmead B, Salzberg SL. Fast gapped-read alignment with Bowtie 2. Nat Methods. 2012; 9(4):357–9. · DOI · Paper page
  27. Genomes Project Consortium, et al.A global reference for human genetic variation. Nature. 2015; 526(7571):68–74. · DOI · Paper page
  28. Cohen KA, et al.Evolution of extensively drug-resistant tuberculosis over four decades: whole genome sequencing and dating analysis of Mycobacterium tuberculosis isolates from KwaZulu-Natal. PLoS Med. 2015; 12(9):1001880. · DOI · Paper page
  29. Manson AL, et al.Genomic analysis of globally diverse Mycobacterium tuberculosis strains provides insights into emergence and spread of multidrug resistance. Nat Genet. 2017; 49(3):395. · DOI · Paper page
  30. Walker BJ, et al.Pilon: an integrated tool for comprehensive microbial variant detection and genome assembly improvement. PloS ONE. 2014; 9(11):112963. · DOI · Paper page
  31. Ghaffaari A, Marschall T. Fully-sensitive seed finding in sequence graphs using a hybrid index. bioRxiv. 2019:587717. Cold Spring Harbor Laboratory. · DOI
  32. Pritt J, et al.FORGe: prioritizing variants for graph genomes. Genome Biol. 2018; 19(1):220. · DOI · Paper page
  33. Linthorst J, et al.Scalable multi whole-genome alignment using recursive exact matching. BioRxiv. 2015:022715. Cold Spring Harbor Laboratory. · DOI
  34. Chin C-S, et al.Phased diploid genome assembly with single-molecule real-time sequencing. Nat Methods. 2016; 13(12):1050. · DOI · Paper page
  35. Tae H, et al.Improved variation calling via an iterative backbone remapping and local assembly method for bacterial genomes. Genomics. 2012; 100(5):271–6. · DOI

Cited by

See all 20

Metadata

Authors
Mokveld, T., Linthorst, J., Al-Ars, Z., Holstege, H., & Reinders, M.
Venue
Genome Biology
Published
2020-03-11
Volume
21
Issue
1
Pages
65-65
ISSN
  • 1465-6906 (ISSN-L)
  • 1474-760X
OpenAlex
W3011984892
Cited by
20
References
7
FWCI
0.83
Type
journal article
Language
en
Open access
gold
Licence

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

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: CHOP: haplotype-aware path indexing in population graphs. https://app.cochat.ai/papers/10.1186/s13059-020-01963-y
The paper
Mokveld, T., Linthorst, J., Al-Ars, Z., Holstege, H., & Reinders, M. (2020). CHOP: haplotype-aware path indexing in population graphs. Genome Biology. https://doi.org/10.1186/s13059-020-01963-y

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.