近似模式匹配？

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。您可能无法解释从文本的第一个索引开始的模式。在

测试数据集：

^{pr2}$

您的输出：

['[]', '0']

正确输出：

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

我不知道我做错了什么，因为我正在尝试学习python，所以对编程没有任何想法。需要帮助吗？在

Answer 1

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

具体地说，您的代码目前只检查字符子串的精确匹配，而没有使用您还包括的hamming距离定义。在

下面将返回您期望的结果：

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))

Answer 2

def ApproximatePatternMatching(Pattern, Text, d):
    positions = [] 


    for i in range(len(Text)-len(Pattern)+1):
        x = Text[i:i+len(Pattern)+1]
        if x != Pattern:
            y = HammingDistance(Pattern,x)
            if y <= d:
                positions.append(i)
    return positions    




def HammingDistance(p, q):


   count = 0

   for i in range(len(p)):
       x = p[i]
       y = q[i]
       if x != y:
           count = count + 1
   return count