The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
A fast adaptive algorithm for computing whole-genome homology maps
Open accessAbstract
Motivation: Whole-genome alignment is an important problem in genomics for comparing different species, mapping draft assemblies to reference genomes and identifying repeats. However, for large plant and animal genomes, this task remains compute and memory intensive. In addition, current practical methods lack any guarantee on the characteristics of output alignments, thus making them hard to tune for different application requirements. Results: We introduce an approximate algorithm for computing local alignment boundaries between long DNA sequences. Given a minimum alignment length and an identity threshold, our algorithm computes the desired alignment boundaries and identity estimates using kmer-based statistics, and maintains sufficient probabilistic guarantees on the output sensitivity. Further, to prioritize higher scoring alignment intervals, we develop a plane-sweep based filtering technique which is theoretically optimal and practically efficient. Implementation of these ideas resulted in a fast and accurate assembly-to-genome and genome-to-genome mapper. As a result, we were able to map an error-corrected whole-genome NA12878 human assembly to the hg38 human reference genome in about 1 min total execution time and <4 GB memory using eight CPU threads, achieving significant improvement in memory-usage over competing methods. Recall accuracy of computed alignment boundaries was consistently found to be >97% on multiple datasets. Finally, we performed a sensitive self-alignment of the human genome to compute all duplications of length ≥1 Kbp and ≥90% identity. The reported output achieves good recall and covers twice the number of bases than the current UCSC browser’s segmental duplication annotation. Availability and implementation: https://github.com/marbl/MashMap
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
Minimap2: Pairwise alignment for nucleotide sequences
Li, H. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty191 · Cited by 14,807
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-citationVersatile and open software for comparing large genomes
Kurtz, S., Phillippy, A., Delcher, A. L., Smoot, M., Shumway, M., Antonescu, C., & Salzberg, S. L. (2004) · Genome Biology · doi:10.1186/gb-2004-5-2-r12 · Cited by 5,254
Self-citationMash: 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-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-citationSchneider, 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
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
Delcher, A. L., Kasif, S., Fleischmann, R. D., Peterson, J., White, O., & Salzberg, S. L. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.11.2369 · Cited by 893
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 by
The complete sequence of a human genome
Nurk, S., Koren, S., Rhie, A., Rautiainen, M., Bzikadze, A. V., Mikheenko, A., Vollger, M. R., Altemose, N., Uralsky, L., Gershman, A., et al. (2022) · Science · doi:10.1126/science.abj6987 · Cited by 3,136
Self-citationTowards complete and error-free genome assemblies of all vertebrate species
Rhie, A., McCarthy, S. A., Fedrigo, O., Damas, J., Formenti, G., Koren, S., Uliano-Silva, M., Chow, W., Fungtammasan, A., Kim, J., et al. (2021) · Nature · doi:10.1038/s41586-021-03451-0 · Cited by 3,097
Self-citationTowards complete and error-free genome assemblies of all vertebrate species
Rhie, A., McCarthy, S. A., Fedrigo, O., Damas, J., Formenti, G., Koren, S., Uliano-Silva, M., Chow, W., Fungtammasan, A., Gedman, G. L., et al. (2020) · doi:10.1101/2020.05.22.110833 · Cited by 3,097
Self-citationWenger, A. M., Peluso, P., Rowell, W. J., Chang, P.-C., Hall, R. J., Concepcion, G. T., Ebler, J., Fungtammasan, A., Kolesnikov, A., Olson, N. D., et al. (2019) · Nature Biotechnology · doi:10.1038/s41587-019-0217-9 · Cited by 1,841
Self-citationNanopore sequencing technology, bioinformatics and applications
Wang, Y., Zhao, Y., Bollas, A., Wang, Y., & Au, K. F. (2021) · Nature Biotechnology · doi:10.1038/s41587-021-01108-x · Cited by 1,753
Nurk, S., Walenz, B. P., Rhie, A., Vollger, M. R., Logsdon, G. A., Grothe, R., Miga, K. H., Eichler, E. E., Phillippy, A. M., & Koren, S. (2020) · Genome Research · doi:10.1101/gr.263566.120 · Cited by 741
Self-citationPathways for horizontal gene transfer in bacteria revealed by a global map of their plasmids
Redondo-Salvo, S., Fernández-López, R., Ruiz, R., Vielva, L., de Toro, M., Rocha, E. P. C., Garcillán-Barcia, M. P., & de la Cruz, F. (2020) · Nature Communications · doi:10.1038/s41467-020-17278-2 · Cited by 433
Telomere-to-telomere assembly of diploid chromosomes with Verkko
Rautiainen, M., Nurk, S., Walenz, B. P., Logsdon, G. A., Porubsky, D., Rhie, A., Eichler, E. E., Phillippy, A. M., & Koren, S. (2023) · Nature Biotechnology · doi:10.1038/s41587-023-01662-6 · Cited by 409
Self-citationGarrison, E., Guarracino, A., Heumos, S., Villani, F., Bao, Z., Tattini, L., Hagmann, J., Vorbrugg, S., Marco-Sola, S., Kubica, C., et al. (2024) · Nature Methods · doi:10.1038/s41592-024-02430-3 · Cited by 277
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-citationGarrison, E., & Guarracino, A. (2023) · Bioinformatics · doi:10.1093/bioinformatics/btac743 · Cited by 95
Structurally divergent and recurrently mutated regions of primate genomes
(2024) · doi:10.1016/j.cell.2024.01.052 · Cited by 73
Multiple genome alignment in the telomere-to-telomere assembly era
Kille, B., Balaji, A., Sedlazeck, F. J., Nute, M., & Treangen, T. J. (2022) · Genome Biology · doi:10.1186/s13059-022-02735-6 · Cited by 47
Scalable pairwise whole-genome homology mapping of long genomes with BubbZ
Minkin, I., & Medvedev, P. (2020) · iScience · doi:10.1016/j.isci.2020.101224 · Cited by 15
He, J., Zhou, T., Hu, L.-F., Jiao, Y., Wang, J., Yan, S., Jia, S., Chen, Q., Zhu, W., Zhang, J., et al. (2026) · Nature Communications · doi:10.1038/s41467-026-72351-6
Metadata
- Authors
- Jain, C., Koren, S., Dilthey, A., Phillippy, A. M., & Aluru, S.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2018-09-01
- Volume
- 34
- Issue
- 17
- Pages
- i748-i756
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2892689606
- Cited by
- 164
- References
- 9
- FWCI
- 4.39
- Type
- journal article
- Language
- en
- Open access
- hybrid
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.