在具有汉明距离的较大字符串中搜索子字符串的存在

Question

>我有 2 个文件，文件 1 和文件 2文件 1 包含完整字符串 "abcdef" 的所有 4-mer、5-mer 和 6-mer 子字符串

file2 有更长的字符串，如

ddghtgabcdtttfwe

ddghtgabdatttfwe

hhttaaddsbcdeggd

等。我想看看 file2 中的字符串是否与 file1 中的字符串匹配，允许一些不匹配（最大汉明距离 2）。例如ddghtgabcdtttfwe 和 ddghtgabcdatttfwe 分别是子字符串 ABCD 和 ABCD，ABCDE 的命中。你能建议一个在python中做到这一点的好方法吗

Answer 1

部分解决方案：

def hamming(s1,s2):
    return len([(c1,c2) for (c1,c2) in zip(s1,s2) if c1 != c2])

然后：

def almostIn(s1,s2):
    n = len(s1)
    for s in (s2[i:i+n] for i in range(1 + len(s2)-n)):
        if hamming(s1,s) <= 2: return True
    return False

如果 s1 出现在汉明距离 <= 2 的 s2 中，则后面的函数将返回 True。有一定量的重新扫描相同的字符，所以这可能不是最佳的，但对于你的预期应用程序来说可能已经足够了。