在 Python 中实现 Neighbors 以查找字符串的 d-neighborhood

Question

输入：一个字符串 Pattern 和一个整数 d。输出：字符串 Neighbors(Pattern, d) 的集合。

样本输入：
ACG 1

样本输出：
TCG ACG GCG CCG ACA ACT AGG AAG ATG ACC

解决这个问题的算法是什么？

Answer 1

这是一个快速而肮脏的解决方案：

chars = "ACGT"

def neighbors(pattern, d):
    assert(d <= len(pattern))

    if d == 0:
        return [pattern]

    r2 = neighbors(pattern[1:], d-1)
    r = [c + r3 for r3 in r2 for c in chars if c != pattern[0]]

    if (d < len(pattern)):
        r2 = neighbors(pattern[1:], d)
        r += [pattern[0] + r3 for r3 in r2]

    return r

这是一些示例输出：

>>> neighbors("ACG", 1)
['CCG', 'GCG', 'TCG', 'AAG', 'AGG', 'ATG', 'ACA', 'ACC', 'ACT']

请注意，这给出了在确切 d位置不同的邻居，而不是在大多数 d地方。如果您想要后者（如您的示例输出所示），您可以简单地组合 的不同值的结果d，如下所示：

def neighbors2(pattern, d):
    return sum([neighbors(pattern, d2) for d2 in range(d + 1)], [])

这是一些示例输出：

>>> neighbors2("ACG", 1)
['ACG', 'CCG', 'GCG', 'TCG', 'AAG', 'AGG', 'ATG', 'ACA', 'ACC', 'ACT']