7

我有一组 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
4

4 回答 4

7

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
于 2014-07-08T06:12:54.127 回答
4

一些想法：

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.        ]])

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

于 2014-07-08T06:03:44.637 回答
3

正如这个答案中提到的，没有比二次运行时间更好的通用方法。您需要利用数据的结构。例如，如果最大允许汉明距离的阈值 t 与字符串 n 的长度相比较小（例如 t=100，n=1000000），您可以执行以下操作：随机选择 k 列（例如 k=1000），将字符串限制为这些列，并将它们散列到存储桶中。然后，您只需要在每个存储桶内进行成对比较，前提是两个具有最小汉明距离的字符串仅在未选择的列中不匹配。例如，大约 90% 的概率是这样，通过重复这个过程，你可以得到任意低的错误概率。

于 2014-07-08T07:34:55.777 回答
-1

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

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

然后计算它们的最小值

    minimum =min(distance)
于 2014-07-08T05:50:46.680 回答