Locality-sensitive hashing for the edit distance
Locality-sensitive hashing for the edit distance
复制标题
DOI：
10.1093/bioinformatics/btz354
复制
发表时间：
2019-07-15
期刊：
影响因子：
5.8
通讯作者：
Kingsford, Carl
中科院分区：
文献类型：
--
作者：
Marcais, Guillaume;DeBlasio, Dan;Kingsford, Carl
动机序列比对是生物信息学流程中的核心操作，尽管有许多改进，但仍然是一个计算上具有挑战性的问题。局部敏感哈希 (LSH) 是一种用于估计两个序列正确对齐的可能性的方法。使用LSH，可以以高概率和相对低的计算量将不具有高质量比对的序列对与可能具有高质量比对的序列对分开。因此，LSH 降低了总体计算要求，同时不会引入许多假阴性（即省略报告有效的比对）。然而，当前的LSH方法将序列视为一包k聚体，并且没有考虑序列中k聚体的相对顺序。此外，由于缺乏实用的编辑距离LSH方法，在实践中，使用Jaccard相似度或Hamming相似度的LSH方法作为代理。结果我们提出了一种LSH方法，称为Order Min Hash（OMH），用于编辑距离。该方法是对用于近似 Jaccard 相似度的 minHash LSH 的改进，因为 OMH 不仅对序列的 k-mer 内容敏感，而且对序列中 k-mer 的相对顺序敏感。我们提出了 OMH 作为有间隙 LSH 的理论保证。可用性和实现生成结果的代码可在 http://github.com/Kingsford-Group/omhismb2019 上获取。补充信息补充数据可在生物信息学在线获取。
Motivation Sequence alignment is a central operation in bioinformatics pipeline and, despite many improvements, remains a computationally challenging problem. Locality-sensitive hashing (LSH) is one method used to estimate the likelihood of two sequences to have a proper alignment. Using an LSH, it is possible to separate, with high probability and relatively low computation, the pairs of sequences that do not have high-quality alignment from those that may. Therefore, an LSH reduces the overall computational requirement while not introducing many false negatives (i.e. omitting to report a valid alignment). However, current LSH methods treat sequences as a bag of k-mers and do not take into account the relative ordering of k-mers in sequences. In addition, due to the lack of a practical LSH method for edit distance, in practice, LSH methods for Jaccard similarity or Hamming similarity are used as a proxy.Results We present an LSH method, called Order Min Hash (OMH), for the edit distance. This method is a refinement of the minHash LSH used to approximate the Jaccard similarity, in that OMH is sensitive not only to the k-mer contents of the sequences but also to the relative order of the k-mers in the sequences. We present theoretical guarantees of the OMH as a gapped LSH.Availability and implementation The code to generate the results is available at http://github.com/Kingsford-Group/omhismb2019.Supplementary informationSupplementary data are available at Bioinformatics online.