The minimizer Jaccard estimator is biased and inconsistent

Motivation: Sketching is now widely used in bioinformatics to reduce data size and increase data processing speed. Sketching approaches entice with improved scalability but also carry the danger of decreased accuracy and added bias. In this article, we investigate the minimizer sketch and its use to estimate the Jaccard similarity between two sequences.

Results: We show that the minimizer Jaccard estimator is biased and inconsistent, which means that the expected difference (i.e.The bias) between the estimator and the true value is not zero, even in the limit as the lengths of the sequences grow. We derive an analytical formula for the bias as a function of how the shared k-mers are laid out along the sequences. We show both theoretically and empirically that there are families of sequences where the bias can be substantial (e.g.The true Jaccard can be more than double the estimate). Finally, we demonstrate that this bias affects the accuracy of the widely used mashmap read mapping tool.

This is a pre-copyedited, author-produced PDF of an article accepted for publication in Bioinformatics following peer review. The version of record [The minimizer Jaccard estimator is biased and inconsistent. Bioinformatics 38, Supplement_1 pi169-i176 (2022)] is available online at: https://doi.org/10.1093/bioinformatics/btac244.

Files

Metadata

Work Title The minimizer Jaccard estimator is biased and inconsistent
Access
Open Access
Creators
  1. Mahdi Belbasi
  2. Antonio Blanca
  3. Robert S. Harris
  4. David Koslicki
  5. Paul Medvedev
License In Copyright (Rights Reserved)
Work Type Article
Publisher
  1. Bioinformatics
Publication Date June 27, 2022
Publisher Identifier (DOI)
  1. https://doi.org/10.1093/bioinformatics/btac244
Deposited January 25, 2024

Versions

Analytics

Collections

This resource is currently not in any collection.

Work History

Version 1
published

  • Created
  • Added 2022.01.14.476226v1.full-1.pdf
  • Added Creator Mahdi Belbasi
  • Added Creator Antonio Blanca
  • Added Creator Robert S. Harris
  • Added Creator David Koslicki
  • Added Creator P Medvedev
  • Published
  • Updated Description, Publication Date Show Changes
    Description
    • Motivation: Sketching is now widely used in bioinformatics to reduce data size and increase data processing speed. Sketching approaches entice with improved scalability but also carry the danger of decreased accuracy and added bias. In this article, we investigate the minimizer sketch and its use to estimate the Jaccard similarity between two sequences. Results: We show that the minimizer Jaccard estimator is biased and inconsistent, which means that the expected difference (i.e.The bias) between the estimator and the true value is not zero, even in the limit as the lengths of the sequences grow. We derive an analytical formula for the bias as a function of how the shared k-mers are laid out along the sequences. We show both theoretically and empirically that there are families of sequences where the bias can be substantial (e.g.The true Jaccard can be more than double the estimate). Finally, we demonstrate that this bias affects the accuracy of the widely used mashmap read mapping tool.
    • Motivation: Sketching is now widely used in bioinformatics to reduce data size and increase data processing speed. Sketching approaches entice with improved scalability but also carry the danger of decreased accuracy and added bias. In this article, we investigate the minimizer sketch and its use to estimate the Jaccard similarity between two sequences.
    • Results: We show that the minimizer Jaccard estimator is biased and inconsistent, which means that the expected difference (i.e.The bias) between the estimator and the true value is not zero, even in the limit as the lengths of the sequences grow. We derive an analytical formula for the bias as a function of how the shared k-mers are laid out along the sequences. We show both theoretically and empirically that there are families of sequences where the bias can be substantial (e.g.The true Jaccard can be more than double the estimate). Finally, we demonstrate that this bias affects the accuracy of the widely used mashmap read mapping tool.
    Publication Date
    • 2022-06-22
    • 2022-06-27
  • Renamed Creator Paul Medvedev Show Changes
    • P Medvedev
    • Paul Medvedev
  • Updated