-1

问题是找出给定 DNA 序列中出现不止一次的所有长度为 k 的序列。我找到了一种使用滚动散列函数的方法，其中对于每个长度为 k 的序列，计算散列并将其存储在映射中。为了检查当前序列是否是重复的，我们计算它的散列并检查散列映射中是否已经存在散列。如果是，那么我们将这个序列包含在我们的结果中，否则将其添加到哈希映射中。

这里的滚动哈希是指，当通过将窗口滑动一个移动到下一个序列时，我们使用前一个序列的哈希，我们移除前一个序列的第一个字符的贡献并添加新添加的字符的贡献即新序列的最后一个字符。

Input: AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT
and k=10
Answer: {AAAAACCCCC, CCCCCAAAAA}

这个算法看起来很完美，但我无法制作一个完美的哈希函数来避免冲突。如果有人可以解释如何在任何情况下以及在这种情况下最重要的是如何制作完美的哈希，那将是一个很大的帮助。

4

4 回答 4

5

这实际上是一个研究问题。

让我们来看看一些事实 Input = N, Input length = |N|

  1. 你必须在输入上移动一个大小k，这里k=10，滑动窗口。因此，您必须忍受O(|N|)或更多。
  2. 您的滚动哈希是局部敏感的确定性哈希的一种形式，确定性哈希的缺点是哈希的好处大大减少，因为您遇到类似字符串的次数越多，哈希就越难
  3. 您的输入越长，哈希的效率就越低

鉴于这些事实，“滚动哈希”很快就会失败。你不能设计一个滚动散列，它甚至适用于 1/10 的染色体。

那么你有什么选择？

  1. 布隆过滤器。它们比简单的散列更健壮。缺点是有时他们有误报。但这可以通过使用多个过滤器来缓解。
  2. Cuckoo Hashes类似于布隆过滤器，但使用更少的内存并且具有局部敏感的“散列”和最坏情况下的常量查找时间
  3. 只需将每个后缀都粘贴在后缀 trie中。完成此操作后，只需在深度处输出每个字符串，10该字符串还具有至少 2 个孩子，其中一个孩子是叶子。
  4. 使用后缀树改进后缀树。查找不是那么简单，但内存消耗更少。
  5. 我最喜欢的FM-Index。在我看来，最干净的解决方案使用 Burrows Wheeler 变换。这种技术也用于工业工具，如 Bowtie 和 BWA
于 2018-07-18T18:03:01.463 回答
3

单挑：这不是一个通用的解决方案，而是一个在k规模不大时可以使用的好技巧。

诀窍是通过位操作将序列加密为整数。

如果您的输入k相对较小，比如说大约 10 个。那么您可以int通过位操作加密您的 DNA 序列。因为对于序列中的每个字符，只有 4 种可能性，A, C, G, T。您可以简单地制作自己的映射，使用 2 位来表示一个字母。

例如：00 -> A, 01 -> C, 10 -> G, 11 -> T。

这样，如果k是 10，则不需要 10 个字符的字符串作为哈希键。相反，您只能使用整数中的 20 位来表示前一个密钥字符串。

然后，当您进行滚动哈希时，将存储先前序列的整数左移 2 位，然后使用任何位操作，例如|=用新字符设置最后两位。记住要清除你刚刚移动的最左边的 2 位，这意味着你正在从滑动窗口中删除它们。

通过这样做，一个字符串可以存储在一个整数中，并且就哈希函数计算的复杂性而言，使用该整数作为哈希键可能会更好、更便宜。如果您的输入长度k略长于 16，您可以使用一个long值。否则，您也许可以使用 bitset 或 bitarray。但是将它们散列成为另一个问题。

因此，当序列长度相对较小时，我会说这个解决方案是解决这个问题的一个很好的尝试，即可以存储在单个整数或长整数中。

于 2018-07-18T18:46:50.127 回答
2

您可以构建后缀数组和LCP 数组。遍历LCP数组，每次看到大于等于k的值，报告那个位置引用的字符串（使用后缀数组判断子字符串来自哪里）。

由于 LCP 大于或等于 k ​​而报告子字符串后，忽略所有后续值，直到达到小于 k 的值（这样可以避免报告重复值）。

后缀阵列和 LCP 的构建都可以在线性时间内完成。因此，总体而言，该解决方案相对于输入加输出的大小是线性的。

于 2018-07-20T21:13:55.147 回答
1

你可以做的是使用中国剩余定理并选择几个大的素数模数。如果您还记得，CRT 意味着与互质模量的同余系统具有一个独特的解决方案，它是您所有模量的乘积。因此，如果您有三个模数 10^6+3、10^6+33 和 10^6+37，那么实际上您的模数或多或少为 10^18。有了足够大的模数，您可以或多或少地完全忽略发生碰撞的想法——正如我的导师所说的那样，您的计算机更有可能自发着火而不是发生碰撞，因为您可以将碰撞概率尽可能地小。

于 2018-07-18T17:23:27.303 回答