CHOP: haplotype-aware path indexing in population graphs
Open accessPublished version of a preprint
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.
Integrity signals
Registry
Cites
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.
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
Schneider, V. A., Graves-Lindsay, T., Howe, K., Bouk, N., Chen, H.-C., Kitts, P. A., Murphy, T. D., Pruitt, K. D., Thibaud-Nissen, F., Albracht, D., et al. (2017) · Genome Research · doi:10.1101/gr.213611.116 · Cited by 1,193
Variation graph toolkit improves read mapping by representing genetic variation in the reference
Garrison, E., Sirén, J., Novak, A. M., Hickey, G., Eizenga, J. M., Dawson, E. T., Jones, W., Garg, S., Markello, C., Lin, M. F., et al. (2018) · Nature Biotechnology · doi:10.1038/nbt.4227 · Cited by 821
Personalized copy number and segmental duplication maps using next-generation sequencing
Alkan, C., Kidd, J. M., Marques-Bonet, T., Aksay, G., Antonacci, F., Hormozdiari, F., Kitzman, J. O., Baker, C., Malig, M., Mutlu, O., et al. (2009) · Nature Genetics · doi:10.1038/ng.437 · Cited by 748
Effect of read-mapping biases on detecting allele-specific expression from RNA-sequencing data.
Degner, J. F., Marioni, J. C., Pai, A. A., Pickrell, J. K., Nkadori, E., Gilad, Y., & Pritchard, J. K. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp579 · Cited by 502
The fragment assembly string graph
Myers, E. W. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti1114 · Cited by 424 · cited 1×
“In other words, by extending and subsequently removing edges in G we introduce overlapping sequence as if we were converting G to the repeat-resolved string graph representation of a joint assembly of all genomes in G from all possible reads of length k [35].”
MethodA new strategy to reduce allelic bias in RNA-Seq readmapping
Vijaya Satya, R., Zavaljevski, N., & Reifman, J. (2012) · Nucleic Acids Research · doi:10.1093/nar/gks425 · Cited by 101
Sirén, J., Garrison, E., Novak, A. M., Paten, B., & Durbin, R. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btz575 · Cited by 92
Research works printed but not linked: 35
- Paten B, et al.Genome graphs and the evolution of genome inference. Genome Res. 2017; 27(5):665–76. · DOI · Paper page
- 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
- Li H, Durbin R. Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinformatics. 2010; 26(5):589–95. · DOI · Paper page
- 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
- 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
- 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
- Church D, et al.Extending reference assembly models. Genome Biol. 2015; 16(1):13. · DOI · Paper page
- Rumble SM, et al.SHRiMP: accurate mapping of short color-space reads. PLoS Comput Biol. 2009; 5(5):1000386. · DOI · Paper page
- 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.
- Popic V, Batzoglou S. A hybrid cloud read aligner based on MinHash and kmer voting that preserves privacy. Nat Commun. 2017; 8:15311. · DOI
- Ferragina P, Manzini G. Opportunistic data structures with applications. In: Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE: 2000. p. 390–398.
- Lippert RA. Space-efficient whole genome comparisons with Burrows–Wheeler transforms. J Comput Biol. 2005; 12(4):407–15. · DOI
- Schneeberger K, et al.Simultaneous alignment of short reads against multiple genomes. Genome Biol. 2009; 10(9):98. · DOI · Paper page
- Huang L, et al.Short read alignment with populations of genomes. Bioinformatics. 2013; 29(13):361–70. · DOI · Paper page
- Eggertsson HP, et al.Graphtyper enables population-scale genotyping using pangenome graphs. Nat Genet. 2017; 49:1654–1660. · DOI · Paper page
- Rautiainen M, et al.Bit-parallel sequence-to-graph alignment. Bioinformatics. 2019. https://doi.org/10.1093/bioinformatics/btz162. · DOI · Paper page
- 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
- 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
- Lee C, et al.Multiple sequence alignment using partial order graphs. Bioinformatics. 2002; 18(3):452–64. · DOI · Paper page
- 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
- 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
- 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
- Durbin R. Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT). Bioinformatics. 2014; 30(9):1266–72. · DOI · Paper page
- 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.
- Li H. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. 2013. arXiv preprint arXiv:1303.3997. · arXiv
- Langmead B, Salzberg SL. Fast gapped-read alignment with Bowtie 2. Nat Methods. 2012; 9(4):357–9. · DOI · Paper page
- Genomes Project Consortium, et al.A global reference for human genetic variation. Nature. 2015; 526(7571):68–74. · DOI · Paper page
- 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
- 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
- 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
- Ghaffaari A, Marschall T. Fully-sensitive seed finding in sequence graphs using a hybrid index. bioRxiv. 2019:587717. Cold Spring Harbor Laboratory. · DOI
- Pritt J, et al.FORGe: prioritizing variants for graph genomes. Genome Biol. 2018; 19(1):220. · DOI · Paper page
- Linthorst J, et al.Scalable multi whole-genome alignment using recursive exact matching. BioRxiv. 2015:022715. Cold Spring Harbor Laboratory. · DOI
- Chin C-S, et al.Phased diploid genome assembly with single-molecule real-time sequencing. Nat Methods. 2016; 13(12):1050. · DOI · Paper page
- 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
The Human Pangenome Project: a global resource to map genomic diversity
Wang, T., Antonacci-Fulton, L., Howe, K., Lawson, H. A., Lucas, J. K., Phillippy, A. M., Popejoy, A. B., Asri, M., Carson, C., Chaisson, M. J. P., et al. (2022) · Nature · doi:10.1038/s41586-022-04601-8 · Cited by 494
Eizenga, J. M., Novak, A. M., Sibbesen, J. A., Heumos, S., Ghaffaari, A., Hickey, G., Chang, X., Seaman, J. D., Rounthwaite, R., Ebler, J., et al. (2020) · Annual Review of Genomics and Human Genetics · doi:10.1146/annurev-genom-120219-080406 · Cited by 320
“CHOP (96) takes the paths corresponding to haplotypes and breaks them into smaller pieces.”
BackgroundGraphAligner: rapid and versatile sequence-to-graph alignment
Rautiainen, M., & Marschall, T. (2020) · Genome Biology · doi:10.1186/s13059-020-02157-2 · Cited by 242
Sirén, J., Garrison, E., Novak, A. M., Paten, B., & Durbin, R. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btz575 · Cited by 92
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
- creativecommons.org/licenses/by/4.0/ (tdm)
- creativecommons.org/licenses/by/4.0/ (vor)
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.