Weighted minimizer sampling improves long read mapping
Weighted minimizer sampling improves long read mapping
复制标题
DOI：
10.1093/bioinformatics/btaa435
复制
发表时间：
2020-07-01
期刊：
影响因子：
5.8
通讯作者：
Phillippy, Adam M.
中科院分区：
文献类型：
--
作者：
Jain, Chirag;Rhie, Arang;Phillippy, Adam M.
动机：在这个数据呈指数增长的时代，最小化采样已成为快速基因组序列比较的标准算法技术。该技术产生序列的亚线性表示，从而能够在减少的空间和时间中进行比较。最小化器技术的一个关键属性是，如果两个序列共享指定长度的子串，则可以保证它们具有匹配的最小化器。然而，由于真核基因组中的 k-mer 分布非常不均匀，基于最小化器的工具（例如 Minimap2、Mashmap）选择丢弃基因组中最常出现的最小化器，以避免过多的误报。这样做会失去潜在的保证，并且重复基因组区域的准确性会降低。结果：我们引入了一种新颖的加权最小化采样算法。该算法的一个独特之处在于，它在考虑每个 k 聚体的权重的同时执行最小化采样；即 k 聚体的权重越高，它被选择的可能性就越大。通过降低频繁出现的 k 聚体的权重，我们能够实现两个目标：(i) 避免过多的误报匹配；(ii) 保持最小化匹配保证。我们使用模拟和真实的长读数据测试了我们的算法 Winnowmap，并将其与最先进的长读映射器 Minimap2 进行比较。我们的结果表明，在最近完成的人类 X 染色体 (154.3 Mbp) 中，定位错误率从 0.14% 降低到 0.06%，在高度重复的 X 着丝粒 (3.1 Mbp) 中，定位错误率从 3.6% 降低到 0%。 Winnowmap 提高了重复内的映射精度，并通过稀疏采样实现这些结果，从而实现更好的索引压缩和有竞争力的运行时间。
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 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 considering 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.