A Fast Approximate Algorithm for Mapping Long Reads to Large Reference Databases
Open accessThe DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Abstract
Emerging single-molecule sequencing technologies from Pacific Biosciences and Oxford Nanopore have revived interest in long-read mapping algorithms. Alignment-based seed-and-extend methods demonstrate good accuracy, but face limited scalability, while faster alignment-free methods typically trade decreased precision for efficiency. In this article, we combine a fast approximate read mapping algorithm based on minimizers with a novel MinHash identity estimation technique to achieve both scalability and precision. In contrast to prior methods, we develop a mathematical framework that defines the types of mapping targets we uncover, establish probabilistic estimates of p-value and sensitivity, and demonstrate tolerance for alignment error rates up to 20%. With this framework, our algorithm automatically adapts to different minimum length and identity requirements and provides both positional and identity estimates for each mapping reported. For mapping human PacBio reads to the hg38 reference, our method is 290 × faster than Burrows-Wheeler Aligner-MEM with a lower memory footprint and recall rate of 96%. We further demonstrate the scalability of our method by mapping noisy PacBio reads (each ≥5 kbp in length) to the complete NCBI RefSeq database containing 838 Gbp of sequence and >60,000 genomes.
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
Mash: fast genome and metagenome distance estimation using MinHash
Ondov, B. D., Treangen, T. J., Melsted, P., Mallonee, A. B., Bergman, N. H., Koren, S., & Phillippy, A. M. (2016) · Genome biology · doi:10.1186/s13059-016-0997-x · Cited by 3,373
Self-citationSchleimer, S., S, W. D., & Aiken, A. (2003) · Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data · doi:10.1145/872757.872770 · Cited by 1,099 · cited 4×
“Suppose Ww(B) denotes the set of winnowed fingerprints in the reference computed using window size w, then W2w(B) ⊆ Ww(B) [25].”
BackgroundMethodInfluentialFast algorithms for large-scale genome alignment and comparison
Delcher, A. L. (2002) · Nucleic Acids Research · doi:10.1093/nar/30.11.2478 · Cited by 1,036 · cited 1×
“Seed-and-extend mapping heuristics address this limitation for both long and short reads by limiting the search to locations where exact short word or maximal common substring matches occur before executing an alignment algorithm at these locations [1, 8, 5].”
BackgroundA survey of sequence alignment algorithms for next-generation sequencing
Li, H., & Homer, N. (2010) · Briefings in Bioinformatics · doi:10.1093/bib/bbq015 · Cited by 875 · cited 1×
“M apping reads generated by high-throughput DNA sequencers to reference genomes is a fundamental and widely studied problem (Li and Homer, 2010; Ruffalo et al., 2011).”
Reducing storage requirements for biological sequence comparison
Roberts, M., Hayes, W., Hunt, B. R., Mount, S. M., & Yorke, J. A. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth408 · Cited by 485 · cited 1×
“Schleimer et al. (2003) proposed the winnowing algorithm, which picks a minimum hashed item (also known as a minimizer; Roberts et al., 2004) from each consecutive window of text as a means to more quickly estimate local similarity between web documents.”
Real-time selective sequencing using nanopore technology
Loose, M., Malla, S., & Stout, M. (2016) · Nature Methods · doi:10.1038/nmeth.3930 · Cited by 399 · cited 2×
“Such applications include depth-of-coverage analysis, metagenomic read assignment, structural variant detection, and selective sequencing (Loose et al., 2016).”
Cited by
High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries
Jain, C., Rodriguez-R, L. M., Phillippy, A. M., Konstantinidis, K. T., & Aluru, S. (2018) · Nature Communications · doi:10.1038/s41467-018-07641-9 · Cited by 5,748
Self-citationNanopore sequencing and assembly of a human genome with ultra-long reads
Jain, M., Koren, S., Miga, K. H., Quick, J., Rand, A. C., Sasani, T. A., Tyson, J. R., Beggs, A. D., Dilthey, A. T., Fiddes, I. T., et al. (2018) · Nature Biotechnology · doi:10.1038/nbt.4060 · Cited by 1,892
Self-citationJBrowse 2: a modular genome browser with views of synteny and structural variation
Diesh, C., Stevens, G. J., Xie, P., De Jesus Martinez, T., Hershberg, E. A., Leung, A., Guo, E., Dider, S., Zhang, J., Bridge, C., et al. (2023) · Genome Biology · doi:10.1186/s13059-023-02914-z · Cited by 853
Time- and memory-efficient genome assembly with Raven
Vaser, R., & Šikić, M. (2021) · Nature Computational Science · doi:10.1038/s43588-021-00073-4 · Cited by 522
Long-read mapping to repetitive reference sequences using Winnowmap2
Jain, C., Rhie, A., Hansen, N. F., Koren, S., & Phillippy, A. M. (2022) · Nature Methods · doi:10.1038/s41592-022-01457-8 · Cited by 267
Self-citation
Metadata
- Authors
- Jain, C., Dilthey, A., Koren, S., Aluru, S., & Phillippy, A. M.
- Venue
- Journal of Computational Biology
- Publisher
- SAGE Publications
- Published
- 2018-07
- Volume
- 25
- Issue
- 7
- Pages
- 766-779
- ISSN
- 1066-5277 (ISSN-L)
- 1557-8666
- OpenAlex
- W2952609831
- Cited by
- 96
- References
- 6
- FWCI
- 4.32
- Type
- journal article
- Language
- en
- Open access
- green
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
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.