将所有字符串(DNA)分开,距离为Hamming = 1

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(n n k),其中k是序列的长度(因为汉明距离比较需要k步).让我们尝试改进.

1. 创建包含其中所有字符串的hashmap(由于散列,复杂度为O(n*k))
2. 对于输入中的每个字符串,创建距离它1的所有字符串并查看它们是否包含在hashmap中 - 如果是,则找到一对(复杂度O(n k k),因为您需要散列O(k) n个字符串中每个字符串的每个k变体)

就这样,你已经更换为O(n ñ K)为O(N ķ K),这应该是有利的.如果n >> K.

对于k >> n,你可能并不真正关心n ^ 2部分,所以使用琐碎的算法.

对于k附近的k,您可以尝试我在评论中建议的内容

1. 通过将所有字母与0,1,2,3(复杂度O(n*k))相加,为每个序列创建伪哈希
2. 排序它们(复杂度为O(n*LOGN)如果你使用的开箱整理,或者为O(n)与基数/桶排序)
3. 比较通过排序序列的对,仅查看彼此相距最多3的事物(复杂性取决于您的情况,在大多数病理情况下将是O(n n k),但是对于真实世界数据,它可以更接近O (n k f(n))其中f(n)非常小)