在Python中寻找一组字符串的最小汉明距离

Question

我有一组大约一百万个字符串（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

找出所有字符串之间的汉明距离，并把结果存储在一个数组里。就像这样：

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

然后计算这些距离中的最小值，像这样：

    minimum =min(distance)

Answer 2

正如在这个回答中提到的，想要比平方级别的运行时间更快的方法并不多。你需要利用数据的结构。比如说，如果允许的最大汉明距离阈值t相对于字符串的长度n来说很小（例如t=100，n=1000000），你可以这样做：随机选择k列（比如k=1000），只关注这些列中的字符串，然后把它们分到不同的桶里。接下来，你只需要在每个桶内进行字符串的两两比较，假设这两个字符串在未选择的列中才会有不同的地方。对于这个例子，这种假设大约有90%的概率是对的，而且通过重复这个过程，你可以把错误的概率降到非常低。

Answer 3

一些建议：

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 4

你可以通过添加一个可选参数来优化你的 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 

你还需要调整你的主循环，以便能够处理 hamdist 返回的 None 值。

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