Rxivist logo

Weighted minimizer sampling improves long read mapping

By Chirag Jain, Arang Rhie, Haowen Zhang, Claudia Chu, Sergey Koren, Adam Phillippy

Posted 11 Feb 2020
bioRxiv DOI: 10.1101/2020.02.11.943241 (published DOI: 10.1093/bioinformatics/btaa435)

Motivation: In this era of exponential data growth, minimizer sampling has become a standard algorithmic technique for rapid genome sequence comparison. This technique yields a sub-linear representation of sequences, enabling their comparison in reduced space and time. A key property of the minimizer technique is that if two sequences share a substring of a specified length, then they can be guaranteed to have a matching minimizer. However, because the k-mer distribution in eukaryotic genomes is highly uneven, minimizer-based tools (e.g., Minimap2, Mashmap) opt to discard the most frequently occurring minimizers from the genome in order to avoid excessive false positives. By doing so, the underlying guarantee is lost and accuracy is reduced in repetitive genomic regions. Results: We introduce a novel weighted-minimizer sampling algorithm. A unique feature of the proposed algorithm is that it performs minimizer sampling while taking into account a weight for each k-mer; i.e, the higher the weight of a k-mer, the more likely it is to be selected. By down-weighting frequently occurring k-mers, we are able to meet both objectives: (i) avoid excessive false-positive matches, and (ii) maintain the minimizer match guarantee. We tested our algorithm, Winnowmap, using both simulated and real long-read data and compared it to a state-of-the-art long read mapper, Minimap2. Our results demonstrate a reduction in the mapping error-rate from 0.14% to 0.06% in the recently finished human X chromosome (154.3 Mbp), and from 3.6% to 0% within the highly repetitive X centromere (3.1 Mbp). Winnowmap improves mapping accuracy within repeats and achieves these results with sparser sampling, leading to better index compression and competitive runtimes. Availability: Winnowmap is built on top of the Minimap2 codebase (Li, 2018) and is available at https://github.com/marbl/winnowmap.

Download data

  • Downloaded 952 times
  • Download rankings, all-time:
    • Site-wide: 13,236 out of 94,912
    • In bioinformatics: 2,075 out of 8,837
  • Year to date:
    • Site-wide: 2,077 out of 94,912
  • Since beginning of last month:
    • Site-wide: 6,023 out of 94,912

Altmetric data


Downloads over time

Distribution of downloads per paper, site-wide


PanLingua

Sign up for the Rxivist weekly newsletter! (Click here for more details.)


News