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

Question

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

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

- Devil

1

除了优化汉明函数之外，关于比较次数并没有太多可以做的。然而，如果您告诉我们您想要实现什么，也许有一种启发式解决方案，不需要进行所有比较。 - Korem

谢谢。我需要找出一组DNA序列的最小距离是否高于一个阈值。（如果是，那么我知道估计算法返回了可靠的值。） - Devil

1

你可以使用一些itertools的好处来缩短你的代码；你的嵌套循环可以只是for s1, s2 in combinations(trans, 2)。hamdist函数可以使用return sum(islice(1 for ch1, ch2 in izip(str1, str2) if ch1 != ch2), prevMin))。 - Frerich Raabe

@FrerichRaabe 非常感谢。Itertools 帮助我显著加速了我的实现。 - Devil

4个回答

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

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

- Akavall

2

数组中的所有字符串都是不同的。当 i < j 时，我只比较字符串 i 和字符串 j。因此，我不理解第三点。谢谢。我会看一下第一点。 - Devil

OP不是已经在看左上角的三角形了吗？他的第二个循环是for j in xrange(**i+1**,len(trans)): 。 - Korem

3

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

- Falk Hüffner

-1

找到所有字符串的汉明距离并将其存储在数组中。类似这样的东西

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

然后像这样计算它们的最小值

    minimum =min(distance)

- Dileep Kumar

1

汉明距离是两个字符串之间的距离，不是一个字符串的属性。 - Korem

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pablo Francisco Pérez Hidalgo · Accepted Answer

你可以通过添加一个可选参数，该参数包含到目前为止获得的最小距离，来优化你的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