Python中的部分子字符串匹配

Question

我想做一个程序，这个程序可以在一个很大的字符串库里查找某个特定的字符串（我们称它为字符串A）。简单来说，如果字符串A在这个库里存在，就把它丢掉，然后再检查另一个字符串是否在库里存在。最后，程序会给我一个最终的字符串列表，这些字符串在这个大库里是不存在的。我已经写了一个可以找到完全匹配的程序，但我需要添加一个模块，让它可以进行部分匹配的子字符串搜索。也就是说，字符串A中的一个或两个字符可以不完全匹配。字符串A的列表（都是由a、t、g、c组成的7个字母的字符串，共有4^7种组合）在面对多样化的库时会遇到困难。

我最初的想法是使用正则表达式和汉明距离算法来找到所有的部分匹配。基本上，这个初步尝试让我可以在字符串A的所有位置（1到7）放一个“？”或通配符，但我只能把它放在第一个位置。这个通配符可以让我搜索特定字符串A的部分匹配。如果这样的方法不对，我很乐意换个思路。我根据另一个问题的建议使用了fnmatch。这是我目前的进展：

from Bio import SeqIO
import fnmatch
import random
import itertools

#Define a splitting string algorithm
def split_by_n(seq,n):
    while seq:
        yield seq[:n]
        seq = seq[n:]

#Import all combinations/permutations from fasta fille, 4^7
my_combinations = []
fasta_sequences = SeqIO.parse(open("Combinations/base_combinations_7.fasta"),'fasta')
for fasta in fasta_sequences:
    name, sequence = fasta.id, str(fasta.seq)
    x = sequence.lower()
    my_combinations.append(x)

primer = "tgatgag"
final = []

#List to make wildcard permutations
wildCard = ['?']

i = list(split_by_n(primer, 1))

for letter in i:
    wildCard.append(letter)

del wildCard[1]

final.append(''.join(wildCard))

#Search for wildcard permutation
for entry in final:
    filtered = fnmatch.filter(my_combinations, entry)

这是我想要的输出：

primer = "tgatgag"

['?', 'g', 'a', 't', 'g', 'a', 'g']
['t', '?', 'a', 't', 'g', 'a', 'g']
['t', 'g', '?', 't', 'g', 'a', 'g']
['t', 'g', 'a', '?', 'g', 'a', 'g']
['t', 'g', 'a', 't', '?', 'a', 'g']
['t', 'g', 'a', 't', 'g', '?', 'g']
['t', 'g', 'a', 't', 'g', 'a', '?']
['agatgag', 'tgatgag', 'cgatgag', 'ggatgag']
['taatgag', 'ttatgag', 'tcatgag', 'tgatgag']
['tgatgag', 'tgttgag', 'tgctgag', 'tggtgag']
['tgaagag', 'tgatgag', 'tgacgag', 'tgaggag']
['tgataag', 'tgattag', 'tgatcag', 'tgatgag']
['tgatgag', 'tgatgtg', 'tgatgcg', 'tgatggg']
['tgatgaa', 'tgatgat', 'tgatgac', 'tgatgag']

Answer 1

这里有一个关于替换两个元素的示例解决方案：

primer = 'cattagc'
bases = ['a','c','g','t']

# this is the generator for all possible index combinations
p = itertools.permutations(range(len(primer)), 2)
# this is the list of all possible base pair combinations
c = list(itertools.combinations_with_replacement(bases, 2))

results = []
for i1, i2 in p:
    for c1, c2 in c:
        temp = list(primer)
        temp[i1], temp[i2] = c1, c2
        results.append(''.join(temp))

这个代码会生成所有可能的方式，用来替换原始数据中的任意两个元素。