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

2023/08/21 by Bryce Kille, Erik Garrison, Todd J. Treangen +1 · 1 voice · 41 citations
Biochemistry, Genetics and Molecular Biology · Engineering · Mathematics · #Artificial intelligence #Computer science #Engineering #Estimation #Generalization #Genetic Associations and Epidemiology #Genome Rearrangement Algorithms #Genomics and Rare Diseases #Jaccard index #Mathematics #Pattern recognition (psychology)

paper · pdf · doi:10.1093/bioinformatics/btad512

published in Bioinformatics 39(9) (Oxford University Press)

openalex publication_date 2023/08/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

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.

Cited by

• Long-read transcriptome assembly reveals vast transcriptional complexity in the placenta associated with metabolic and endocrine function
• Complete sequencing of ape genomes
• ModDotPlot—rapid and interactive visualization of tandem repeats
• The origin of the octoploid cloudberry ( Rubus chamaemorus ) genome is the result of multiple and complex polyploidization events
• PneumoBrowse 2: an integrated visual platform for curated genome annotation and multiomics data analysis of Streptococcus pneumoniae
• A near-tight lower bound on the density of forward sampling schemes
• Graph-based pangenomes and pan-phenome provide a cornerstone for eggplant biology and breeding
• Sketching Methods with Small Window Guarantee Using Minimum Decycling Sets. [europepmc]
• k-nonical space: sketching with reverse complements. [europepmc]
• PneumoBrowse 2: an integrated visual platform for curated genome annotation and multiomics data analysis of Streptococcus pneumoniae. [europepmc]
• A near-tight lower bound on the density of forward sampling schemes. [europepmc]
• Polyploidization-driven transcriptomic dynamics in Medicago sativa neotetraploids: mRNA, smRNA and allele-specific gene expression. [europepmc]
• The open-closed mod-minimizer algorithm. [europepmc]
• Complete sequencing of ape genomes. [europepmc]
• Verkko2 integrates proximity-ligation data with long-read De Bruijn graphs for efficient telomere-to-telomere genome assembly, phasing, and scaffolding. [europepmc]
• Phylogenetic reconstruction and species delimitation in Stipeae with special reference to Stipa (Poaceae, Pooideae) using mitochondrial genomes. [europepmc]
• KPop: accurate and scalable comparative analysis of microbial genomes by sequence embeddings. [europepmc]
• Analysis of a Novel Human Protein, ORF3, Encoded by Spacer rDNA. [europepmc]
• Complete genome assemblies of two mouse subspecies reveal structural diversity of telomeres and centromeres. [europepmc]
• CRISPRi-seq in Haemophilus influenzae reveals genome-wide and medium-specific growth determinants. [europepmc]
• Graph-based pangenomes and pan-phenome provide a cornerstone for eggplant biology and breeding. [europepmc]
• SAFARI: pangenome alignment of ancient DNA using purine/pyrimidine encodings. [europepmc]
• Puzzler: scalable one-command platinum-quality genome assembly from HiFi and Hi-C. [europepmc]
• krepp: a k-mer-based maximum pseudo-likelihood method for estimating read distances and genome-wide phylogenetic placement. [europepmc]
• Long-read assembly reveals vast transcriptional complexity in the placenta associated with metabolic and endocrine function. [europepmc]
• An improved Solanum verrucosum genome provides insight into potato centromeres and epigenetic regulation. [europepmc]
• A k-mer-Based Estimator of the Substitution Rate Between Repetitive Sequences. [europepmc]
• An improved Solanum verrucosum genome provides insight into potato centromeres and epigenetic regulation [europepmc]
• Biobank-scale genotyping of Robertsonian translocations reveals hidden structural variation on the human acrocentric chromosomes [europepmc]

Discussions

• "Minmers are a generalization of minimizers that enable unbiased local jaccard estimation" aka MashMap3 with Bryce Kille, @erikg.bsky.social, and @treangen.bsky.social is now accepted in Bioinformatic [bsky, 27 points, 0 comments]

Related

• SuperMinHash - A New Minwise Hashing Algorithm for Jaccard Similarity Estimation
• C-MinHash: Rigorously Reducing K Permutations to Two
• C-MinHash: Practically Reducing Two Permutations to Just One
• Minwise-Independent Permutations with Insertion and Deletion of Features
• Sampling-Based Estimation of Jaccard Containment and Similarity