查找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