python - 如何用d-mismatches生成所有字符串，python

Question

我有以下字符串 - “AACCGGTTT”(字母表是 ["A","G","C","T"])。我想在任何两个位置生成所有与原始字符串不同的字符串，即

GAGCGGTTT
^ ^ 
TATCGGTTT
^ ^

如何在 Python 中完成？

我只有蛮力解决方案(它正在工作):

1. 在给定的字母表上生成具有相同长度的所有字符串

2. 追加与给定字符串有 2 个不匹配的字符串

但是，您能建议更有效的方法吗？

Answer 1

我可能会选择使用 itertools。也许像

from itertools import combinations, product

def generate(s, d=2):
    N = len(s)
    letters = 'ACGT'
    pool = list(s)

    for indices in combinations(range(N), d):
        for replacements in product(letters, repeat=d):
            skip = False
            for i, a in zip(indices, replacements):
                if pool[i] == a: skip = True
            if skip: continue

            keys = dict(zip(indices, replacements))
            yield ''.join([pool[i] if i not in indices else keys[i] 
                           for i in range(N)])

然后就

list(generate("AACCGGTTT"))