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

Question

我有两个文件，每个文件大约有一亿行，我需要把它们进行比较。正如标题所说，我想把每一行进行逐一对比。我下面的代码运行得很好，但我想调整一下，让它在长的匹配过程中，如果出现不匹配的情况，可以接受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

下面的代码展示了如何在代码中使用上述函数，以及我如何找到最长的匹配。

while len(rc1u) >= 50: # So matches of 8 are included
    slide_merge(rc1u, rc2wr)      ### rc1u all cut up here so of no further use
    rc1u = rc1u[1:]
merging
max(merging.iteritems(), key=operator.itemgetter(1))[0]
highest = max(merging.iteritems(), key=operator.itemgetter(1))[0]
highest

如果有关系的话，我使用HTSeq来输入这些文件，它们是基因测序的数据。

所以问题是，我该如何调整这段代码，或者写一段新的代码，来比较两个字符串，并找出从开始位置起最长的匹配序列，同时允许出现5%的不匹配。例如：

string1 = AAAAATTTTTCCCCCGGGGGTTTTT
string2 = AAAAATTTTTCCCCCGGGGATTTTT

这段代码应该能看到这两个字符串几乎完全匹配，只是有一个字符不同，但因为这个不匹配的字符占总字符的比例不到5%，所以匹配的区域应该被标记为：

matched
25

Answer 1

你可以计算这两个词之间的莱文斯坦距离，然后找出这两个词之间的不匹配百分比。

这里有一个实现的例子，详细内容可以在这里找到。

假设计算两个字符串距离的函数叫做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 !")

例如，使用你提供的例子和我给的链接中的迭代实现：

>>> distance = dis_lev("AAAAATTTTTCCCCCGGGGGTTTTT", "AAAAATTTTTCCCCCGGGGATTTTT")
>>> distance
1
>>> mismatch_ratio = distance / len("AAAAATTTTTCCCCCGGGGGTTTTT")
0.04 

补充：根据你的具体情况，你还可以使用其他度量标准，具体可以在这里查看。