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 buckets while assigning dissimilar sequences into distinct buckets. Existing $k$-mer-based bucketing methods have been efficient in processing sequencing data with low-error rate, but encounter much reduced sensitivity on data with high-error rate. 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 gap. Here 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 $(d_1, d_2)$-sensitive if any two sequences within an edit distance of $d_1$ are mapped into at least one shared bucket, and any two sequences with distance at least $d_2$ are mapped into disjoint subsets of buckets. We construct LSB functions with a variety of values of $(d_1,d_2)$ 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 provide theoretical foundations for their practical use in analyzing sequencing data with high error rate while also providing insights for the hardness of designing ungapped LSH functions.
翻译:许多生物信息学应用涉及将每个序列被分配到多个桶的一组序列。 为了达到高度敏感度和精确度, 需要将类似序列分配到同一个桶中, 并将不同序列分配到不同的桶中。 现有的美元- 美元- 美元- 美元- 美元( 美元- 美元- 美元) 桶法在以低摄氏度处理测序数据方面是有效率的, 但是在高摄氏度率处理数据时遇到的敏感度却大大降低。 本地敏感散变( LSH) 计划能够通过将编辑以类似顺序排列到多个桶中来缓解这一问题, 但是, 最新水平的基数仍然有很大的差距。 在这里, 我们将 LSH 函数普遍化, 允许将一个序列分解到不同的桶中。 正式, 将一个序列( 固定长度) 映射到一个桶子( d_ 1 d_ 2 ), 如果在最优的编辑距离内的任何两个序列( $_ 1 美元 ) 内提供至少一个共享的编辑桶中, 而任何两个序列以最短的测序, 以最低的L2x_ 的轨道 数据 显示一个比 。