查找python中一组字符串的最小汉明距离

Question

我有一组n（~1000000）字符串（DNA序列）存储在列表trans中。我必须找到列表中所有序列的最小汉明距离。我实施了一个天真的暴力算法，它运行了一天多，还没有给出解决方案。我的代码是

dmin=len(trans[0])
for i in xrange(len(trans)):
    for j in xrange(i+1,len(trans)):
            dist=hamdist(trans[i][:-1], trans[j][:-1])
            if dist < dmin:
                    dmin = dist

有没有更有效的方法来做到这一点？ Hamdist是我写的一个函数，用于查找汉明距离。它是

def hamdist(str1, str2):
    diffs = 0
    if len(str1) != len(str2):
        return max(len(str1),len(str2))
    for ch1, ch2 in zip(str1, str2):
        if ch1 != ch2:
          diffs += 1
    return diffs

Answer 1

你可以通过添加一个包含你到目前为止最小距离的可选参数来优化你的hamdist函数，这样如果diffs达到你停止计算距离的值，因为这个比较会给你一个比最小距离更大的距离：

def hamdist(str1, str2,prevMin=None):
    diffs = 0
    if len(str1) != len(str2):
        return max(len(str1),len(str2))
    for ch1, ch2 in zip(str1, str2):
        if ch1 != ch2:
            diffs += 1
            if prevMin is not None and diffs>prevMin:
                return None
    return diffs 

您将需要调整主循环以使用来自None的hamdist返回值：

dmin=len(trans[0])
for i in xrange(len(trans)):
    for j in xrange(i+1,len(trans)):
            dist=hamdist(trans[i][:-1], trans[j][:-1])
            if dist is not None and dist < dmin:
                    dmin = dist

Answer 2

一些想法：

1）sklearn.metrics.hamming_loss可能比你的实现更有效，即使你必须将你的字符串转换为数组。

2）你的所有字符串都是唯一的吗？如果是，请删除重复项。

您也可以尝试sklearn.metrics.pairwise.pairwise_distances，例如：

In [1]: from sklearn.metrics.pairwise import pairwise_distances

In [2]: from sklearn.metrics import hamming_loss

In [3]: a = np.array([[3,4,5], [3,4,4],[3,1,1]])

In [4]: import numpy as np

In [5]: a = np.array([[3,4,5], [3,4,4],[3,1,1]])

In [6]: pairwise_distances(metric=hamming_loss)

In [7]: pairwise_distances(a, metric=hamming_loss)
Out[7]: 
array([[ 0.        ,  0.33333333,  0.66666667],
       [ 0.33333333,  0.        ,  0.66666667],
       [ 0.66666667,  0.66666667,  0.        ]])

我没有看到只能计算上三角形的标志，但这仍然应该比循环更快。

Answer 3

正如this answer所提到的，没有比二次运行时间更好的一般方法。您需要利用数据结构。例如，如果最大允许汉明距离的阈值t与字符串n的长度相比较小（例如t = 100，n = 1000000），则可以执行以下操作：随机选择k列（例如k = 1000），将字符串限制为这些列，并将它们哈希到桶中。然后，您需要在每个桶中进行成对比较，假设两个字符串的汉明距离最小，仅在非选定列中不匹配。例如，大概90％的概率都是如此，并且您可以通过重复该过程来获得任意低的错误概率。

Answer 4

找到所有字符串的汉明距离并将其存储在数组中。就像是

    distance=[]
    for i in trans:
      distance.append(hamdist(i))

然后计算它们的最小值

    minimum =min(distance)