Locality-sensitive bucketing functions for the edit distance.
Locality-sensitive bucketing functions for the edit distance.
复制标题
DOI：
10.1186/s13015-023-00234-2
复制
发表时间：
2023-07-24
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
许多生物信息学应用涉及对一组序列进行分类，其中允许将每个序列分配到多个存储桶中。为了实现高灵敏度和高精度，需要使用分组法将相似的序列分配到相同的桶中，同时将不同的序列分配到不同的桶中。现有的基于k-mer的分组法在处理低错误率的测序数据方面一直是有效的，但在高错误率的数据上遇到的敏感度大大降低。位置敏感散列算法(LSH)能够通过容忍相似序列中的编辑来缓解这一问题，但最先进的方法仍然存在很大差距。在本文中，我们推广了LSH函数，允许它将一个序列散列到多个桶中。在形式上，将一个序列(固定长度)映射到一个桶的子集的巴特化函数被定义为敏感的，如果在的编辑距离内的任何两个序列被映射到至少一个共享桶中，并且任何两个至少具有距离的序列被映射到不相交的桶的子集。我们构造了具有不同值的位置敏感的分组码(LSB)函数，并分析了它们相对于所需的存储桶总数以及特定序列映射到的存储桶数量的效率。我们还证明了这两个参数在不同设置下的下界，并证明了我们构造的一些LSB函数是最优的。这些结果为它们在分析高错误率序列中的实际应用奠定了理论基础，同时也为设计无映射LSH函数的难度提供了见解。
Many bioinformatics applications involve bucketing a set of sequences where each sequence is allowed to be assigned into multiple buckets. To achieve both high sensitivity and precision, bucketing methods are desired to assign similar sequences into the same bucket while assigning dissimilar sequences into distinct buckets. Existing k-mer-based bucketing methods have been efficient in processing sequencing data with low error rates, but encounter much reduced sensitivity on data with high error rates. Locality-sensitive hashing (LSH) schemes are able to mitigate this issue through tolerating the edits in similar sequences, but state-of-the-art methods still have large gaps. In this paper, we generalize the LSH function by allowing it to hash one sequence into multiple buckets. Formally, a bucketing function, which maps a sequence (of fixed length) into a subset of buckets, is defined to be -sensitive if any two sequences within an edit distance of are mapped into at least one shared bucket, and any two sequences with distance at least are mapped into disjoint subsets of buckets. We construct locality-sensitive bucketing (LSB) functions with a variety of values of and analyze their efficiency with respect to the total number of buckets needed as well as the number of buckets that a specific sequence is mapped to. We also prove lower bounds of these two parameters in different settings and show that some of our constructed LSB functions are optimal. These results lay the theoretical foundations for their practical use in analyzing sequences with high error rates while also providing insights for the hardness of designing ungapped LSH functions.
登录
查看更多内容
影响因子：
5.8
作者：
Li, Heng
通讯作者：
Li, Heng
影响因子：
5.8
作者：
Marcais, Guillaume;DeBlasio, Dan;Kingsford, Carl
通讯作者：
Kingsford, Carl
影响因子：
46.9
作者：
Berlin, Konstantin;Koren, Sergey;Phillippy, Adam M.
通讯作者：
Phillippy, Adam M.
影响因子：
46.9
作者：
Jain M;Koren S;Miga KH;Quick J;Rand AC;Sasani TA;Tyson JR;Beggs AD;Dilthey AT;Fiddes IT;Malla S;Marriott H;Nieto T;O'Grady J;Olsen HE;Pedersen BS;Rhie A;Richardson H;Quinlan AR;Snutch TP;Tee L;Paten B;Phillippy AM;Simpson JT;Loman NJ;Loose M
通讯作者：
Loose M
DOI：
10.1016/j.gpb.2015.08.002
发表时间：
2015-10
期刊：
Genomics, proteomics & bioinformatics
影响因子：
--
作者：
Rhoads A;Au KF
通讯作者：
Au KF