匹配2个字符串并允许5%的不匹配

Question

我有2个大约100000000行的文件，需要相互比较。正如标题中所述，我想将文件中的每一行相互比较。我有下面的代码，这是绝对好的工作，但我希望调整它，以便如果不匹配发生在一个长匹配，那么它是接受的错配水平为5%。在

下面是我用来匹配文件行的函数。在

ret1 = []
merging = {} 
def slide_merge(seq1, seq2):
    for i in xrange(min(len(seq1), len(seq2))):
        if seq1[i] == 'N':
            ret1.append(seq1[i])
            print (''.join(ret1))
        elif seq2[i] == 'N':
            ret1.append(seq1[i])
            print (''.join(ret1))
        elif seq1[i] != seq2[i]:
            break
        else:
            ret1.append(seq1[i])
            print (''.join(ret1))
    print ("strings share a longest common prefix of length:", len(ret1), "out of:", len(seq1))
    ret1len = len(ret1)
    merging[''.join(ret1)] = ret1len # Adds details to dictionary
    return merging

下面的代码是如何在代码中使用上述函数以及如何获得最长匹配。在

^{pr2}$

如果有关系的话，我用HTSeq输入基因测序文件。在

所以问题是，我该如何调整这段代码，或者制作另一段代码来比较两个字符串，从一开始就确定最长的匹配序列，同时允许5%的不匹配发生，例如：

string1 = AAAAATTTTTCCCCCGGGGGTTTTT
string2 = AAAAATTTTTCCCCCGGGGATTTTT

代码应该看到两个字符串完全匹配，除了1个字符之外，但是由于这不到总数的5%，所以匹配区域应该声明为： 匹配的 25

Answer 1

您可以计算这些单词之间的Levenshtein distance，然后找到“这些单词之间不匹配”的百分比。在

提供了一个实现的例子here。在

假设计算两个字符串之间距离的函数称为dis_lev，可以这样计算百分比：

from __future__ import division

distance = dis_lev(string1, string2)
mismatch_ratio = distance / len(string1)
if mismatch_ratio > 0.05:
    raise MyAwesomeException("Hey ! These things do not match at all !")

例如，使用您的示例和我提供的链接中提供的迭代实现：

^{pr2}$

编辑：根据您的情况，您可以使用另一个度量，其中一些被列出here