重复的DNA序列

Question

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

滚动哈希在这里表示,由一个滑动窗口移动到下一个序列的时候,我们使用之前序列的散列,我们删除以前的序列的第一个字符的贡献,并添加新添加的焦炭的贡献方式即新序列的最后一个字符.

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

这个算法看起来很完美,但我不能去做一个完美的哈希函数,以避免碰撞.如果有人能够在任何情况下解释如何制作完美的哈希值,那将是一个很大的帮助,最重要的是在这种情况下.

Answer 1

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

让我们来看一些事实输入= N,输入长度= | N |

1. 你必须在输入上移动一个尺寸k,这里k=10是滑动窗口.因此,您必须与之共存O(|N|)或更多.
2. 您滚动散列是局部性敏感确定性散列的形式,确定散列的缺点是哈希的好处是大大降低的越难将散列更多的时候,你遇到类似的字符串
3. 输入时间越长,散列效果越差

鉴于这些事实,"滚动的哈希"将很快失败.你不能设计一个甚至可以用于染色体1/10的滚动哈希.

那你有什么替代品？

1. 布隆过滤器.它们比简单的散列更强大.缺点是有时它们会出现误报.但是这可以通过使用几个过滤器来减轻.
2. Cuckoo Hashes类似于bloom过滤器,但使用较少的内存并且具有局部敏感的"散列"和最坏情况下的常量查找时间
3. 只需在后缀trie中添加每个后缀即可.完成此操作后,只输出深度处的每个字符串,10该字符串还包含至少2个子节点,其中一个子节点为叶子.
4. 使用后缀树改进后缀trie .查找不是那么简单,但内存消耗较少.
5. 我最喜欢的FM-Index.在我看来,最干净的解决方案使用Burrows Wheeler Transform.这种技术也用于Bowtie和BWA等工业工具