python - 近似模式匹配？

Question

我正在尝试编写近似模式匹配的代码，如下所示:

def HammingDistance(p, q):
    d = 0
    for p, q in zip(p, q): # your code here
        if p!= q:
            d += 1
    return d
Pattern = "ATTCTGGA"
Text = "CGCCCGAATCCAGAACGCATTCCCATATTTCGGGACCACTGGCCTCCACGGTACGGACGTCAATCAAAT"
d = 3
def ApproximatePatternMatching(Pattern, Text, d):
    positions = [] # initializing list of positions
    for i in range(len(Text) - len(Pattern)+1):
        if Pattern == Text[i:i+len(Pattern)]:
            positions.append(i)# your code here
    return positions
print (ApproximatePatternMatching(Pattern, Text, d))

我不断收到以下错误:测试 #3 失败。您可能无法考虑从第一个文本索引开始的模式。

测试数据集:

GAGCGCTGG
GAGCGCTGGGTTAACTCGCTACTTCCCGACGAGCGCTGTGGCGCAAATTGGCGATGAAACTGCAGAGAGAACTGGTCATCCAACTGAATTCTCCCCGCTATCGCATTTTGATGCGCGCCGCGTCGATT
2

你的输出:

['[]', '0']

正确输出:

['0', '30', '66']

无法弄清楚我做错了什么，因为我正在尝试学习Python，所以对编程没有任何想法。需要帮助吗？

Answer 1

我不确定为什么你会得到一个空列表作为你的输出之一 - 当我运行上面的代码时，我只得到 [0] 作为打印输出。

具体来说，您的代码目前仅检查字符子字符串的精确匹配，而不使用您还包含的汉明距离定义。

以下内容应返回您期望的结果:

Pattern = "GAGCGCTGG"
Text = "GAGCGCTGGGTTAACTCGCTACTTCCCGACGAGCGCTGTGGCGCAAATTGGCGATGAAACTGCAGAGAGAACTGGTCATCCAACTGAATTCTCCCCGCTATCGCATTTTGATGCGCGCCGCGTCGATT"
d = 3

def HammingDistance(p, q):
    d = 0
    for p, q in zip(p, q): # your code here
        if p!= q:
            d += 1
    return d

def ApproximatePatternMatching(Pattern, Text, d):
    positions = [] # initializing list of positions
    for i in range(len(Text) - len(Pattern)+1):
        # and using distance < d, rather than exact matching
        if HammingDistance(Pattern, Text[i:i+len(Pattern)]) < d:
            positions.append(i)
    return positions

print (ApproximatePatternMatching(Pattern, Text, d))