EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Minmers are a generalization of minimizers that enable unbiased local Jaccard estimation

Bryce Kille iD, Erik Garrison iD, Todd J Treangen iD, Adam M Phillippy

Bioinformatics · 02.09.2023 · 39 (9)

DOI: 10.1093/bioinformatics/btad512 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bioinformatics, online erschienen am 21.08.2023. Verfasst von Bryce Kille und 3 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, Rice University, Houston, TX, United States. Hauptthemen laut MEDLINE: Genomics, Computational Biology. Die Arbeit wurde bisher 44-mal zitiert (Crossref) und nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NLM NIH HHS, NIAID NIH HHS, NIDA NIH HHS.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivation The Jaccard similarity on k-mer sets has shown to be a convenient proxy for sequence identity. By avoiding expensive base-level alignments and comparing reduced sequence representations, tools such as MashMap can scale to massive numbers of pairwise comparisons while still providing useful similarity estimates. However, due to their reliance on minimizer winnowing, previous versions of MashMap were shown to be biased and inconsistent estimators of Jaccard similarity. This directly impacts downstream tools that rely on the accuracy of these estimates. Results To address this, we propose the minmer winnowing scheme, which generalizes the minimizer scheme by use of a rolling minhash with multiple sampled k-mers per window. We show both theoretically and empirically that minmers yield an unbiased estimator of local Jaccard similarity, and we implement this scheme in an updated version of MashMap. The minmer-based implementation is over 10 times faster than the minimizer-based version under the default ANI threshold, making it well-suited for large-scale comparative genomics applications. Availability and implementation MashMap3 is available at https://github.com/marbl/MashMap.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

GenomicsComputational Biology

Autor:innen und Institutionen

  • Department of Computer Science, Rice University, Houston, TX, United States.
  • Department of Genetics, Genomics and Informatics, University of Tennessee Health Science Center, Memphis, TN, United States.
  • Genome Informatics Section, Computational and Statistical Genomics Branch, National Human Genome Research Institute, National Institutes of Health, Bethesda, MD, United States.

ORCID-Profile: Bryce Kille, Erik Garrison, Todd J Treangen

Förderung

  • NLM NIH HHS
  • NIAID NIH HHS
  • NIDA NIH HHS
  • NIGMS NIH HHS
  • National Library of Medicine Training Program in Biomedical Informatics and Data Science
  • National Human Genome Research Institute
  • National Institutes of Health

Zitieren

APA

Kille, B., Garrison, E., Treangen, T. J., & Phillippy, A. M. (2023). Minmers are a generalization of minimizers that enable unbiased local Jaccard estimation. Bioinformatics, 39(9). https://doi.org/10.1093/bioinformatics/btad512

Vancouver

Kille B, Garrison E, Treangen TJ, Phillippy AM. Minmers are a generalization of minimizers that enable unbiased local Jaccard estimation. Bioinformatics. 2023;39(9). doi:10.1093/bioinformatics/btad512

BibTeX
@article{Kille2023,
  author = {Kille, Bryce and Garrison, Erik and Treangen, Todd J and Phillippy, Adam M},
  title = {Minmers are a generalization of minimizers that enable unbiased local Jaccard estimation},
  journal = {Bioinformatics},
  year = {2023},
  volume = {39},
  number = {9},
  doi = {10.1093/bioinformatics/btad512}
}
Kostenlos starten →