获取以 Hamming = 1 的距离分隔的所有字符串对（DNA）

Question

我有一组 DNA 序列，例如：

AA
TA
AC
CC

然后我搜索了一种更快的方法来计算所有序列对之间的汉明距离（可能通过排序...），然后是朴素的方法 (O(N^2))

For motif1 in array
   For motif2 in array
      calculate Hamming_Distance(motif1 , motif2)
   end
end

我需要汉明距离 = 1 的对序列

Answer 1

如果你的 n >> k，那么你可以尝试以下

你原来的复杂度是O(nnk)，其中k是序列的长度（因为汉明距离比较需要k步）。让我们尝试对此进行改进。

创建包含所有字符串的 hashmap（由于散列，复杂度为 O(n*k)）
对于输入中的每个字符串，创建与它相距 1 的所有字符串，并查看它们是否包含在 hashmap 中 - 如果是，则您找到了一对（复杂度 O(nkk) 因为你需要对 n 个字符串中的每一个的 k 个变体中的每一个进行哈希运算 O(k))

至此，您将 O(nnk) 替换为 O(nkk)，如果n >> k.

对于 k >> n 你可能并不真正关心 n^2 部分，所以使用简单的算法。

对于n附近的k，你可以试试我评论里的建议

通过将所有字母与 0、1、2、3 相加（复杂度 O(n*k)）为每个序列创建伪哈希
对它们进行排序（如果使用开箱即用的排序，复杂度为 O(n*logn)，或者使用 radix/bucket 排序的复杂度为 O(n)）
比较经过排序序列的对，只查看彼此相距最大 3 的事物（复杂性取决于您的情况，将为 O(nnk)大多数病理情况，但对于现实世界的数据，它可以更接近 O(nkf(n)) 其中 f(n) 会非常非常小)

Get all pairs of strings (DNA) seperated by a distance of Hamming = 1