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

一尘不染

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

algorithm

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

阅读 467

2020-07-28

共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

2020-07-28