DNA搜索序列正则表达式中的多个不匹配

Question

我写了一个比较粗糙的脚本，用来生成一个字符串中包含 n 个 $ 的所有可能排列（最多 n=4）。最后我会用 .replace('$','(\\w)') 来处理 DNA 搜索序列中的不匹配情况。因为我写这个脚本的方式，有些排列的 $ 的数量少于我要求的数量。于是我又写了一个脚本来删除这些排列，但效果似乎不太好，每次运行删除脚本时，反而会删除更多不需要的排列。在下面的代码中，你会看到我用一个简单的序列测试这个函数，这个序列有 4 个不匹配的地方。然后我运行了一系列删除脚本，统计每次删除了多少个表达式……根据我的经验，通常需要大约 8 次才能删除所有少于 4 个通配符 $ 的表达式。我有几个问题想问：

1. 有没有内置的函数可以处理 'n' 个不匹配的搜索？也许在 biopython 中有？到目前为止，我看到的 Paul_McGuire_regex 函数：
   允许在字符串的任何位置有一个不匹配的字符串搜索,
   似乎只能生成一个不匹配。我必须承认，我对那页上其他函数的代码并不是很理解，因为我还是个新手。

2. 我觉得这是个不错的练习，有没有更好的方法来写这个脚本？……我可以根据需要多次调用 Paul_McGuire_regex 函数吗？

3. 让我最困惑的是，为什么删除脚本第一次运行时不能 100% 有效？

谢谢你能提供的任何帮助！

def Mismatch(Search,n):
    List = []
    SearchL = list(Search)
    if n > 4:
        return("Error: Maximum of 4 mismatches")
    for i in range(0,len(Search)):
        if n == 1:
            SearchL_i = list(Search)
            SearchL_i[i] = '$'
            List.append(''.join(SearchL_i))
        if n > 1:
            for j in range (0,len(Search)):
                if n == 2:
                    SearchL_j = list(Search)
                    SearchL_j[i] = '$'
                    SearchL_j[j] = '$'
                    List.append(''.join(SearchL_j))
                if n > 2:
                    for k in range(0,len(Search)):
                        if n == 3:
                            SearchL_k = list(Search)
                            SearchL_k[i] = '$'
                            SearchL_k[j] = '$'
                            SearchL_k[k] = '$'
                            List.append(''.join(SearchL_k))
                        if n > 3:
                            for l in range(0,len(Search)):
                                if n ==4:
                                    SearchL_l = list(Search)
                                    SearchL_l[i] = '$'
                                    SearchL_l[j] = '$'
                                    SearchL_l[k] = '$'
                                    SearchL_l[l] = '$'
                                    List.append(''.join(SearchL_l))
    counter=0
    for el in List:
        if el.count('$') < n:
            counter+=1
            List.remove(el)
    return(List) 

List_RE = Mismatch('abcde',4)

counter = 0
for el in List_RE:
    if el.count('$') < 4:
        List_RE.remove(el)
        counter+=1

print("Filter2="+str(counter))

Answer 1

我们可以通过回答第一个问题来解决第二和第三个问题，但理解第三个问题很重要，所以我先解释一下，然后再告诉你如何完全避免这个问题：

第三个问题

关于第三个问题，原因在于当你在 Python 中遍历一个列表并在循环中对它进行修改时，正在遍历的列表会发生变化。

根据Python 文档中的控制流部分：

在循环中修改正在遍历的序列是不安全的（这只会发生在可变序列类型，比如列表）。

假设你的列表是 [a,b,c,d]，你用 for el in List 来遍历它。假设此时 el 是 a，然后你执行 List.remove(el)。

现在，你的列表变成了 [b,c,d]。但是，迭代器指向列表中的第二个元素（因为它已经处理过第一个），现在是 c。实际上，你跳过了 b。所以问题在于你在修改正在遍历的列表。

有几种方法可以解决这个问题：如果你的 List 复制起来不太费劲，你可以先复制一份。这样就可以遍历 List[:]，但从 List 中删除。

但假设复制 List 的成本很高。那么你可以选择反向遍历。注意下面的 reversed：

for el in reversed(List):
    if el.count('$') < n:
        counter+=1
        List.remove(el)
return(List) 

在上面的例子中，假设我们反向遍历 List。迭代器从 d 开始，然后到 c。假设我们删除了 c，这样 List=[a,b,d]。由于迭代器是反向进行的，它现在指向元素 b，所以我们没有跳过任何元素。

基本上，这样可以避免修改你还没有遍历到的列表部分。

问题 1 和 2

如果我理解你的问题没错，你基本上是想从 m 个位置中选择 n 个，其中 m 是字符串的长度（比如 abcde），并在这 n 个位置上放一个 '$'。

在这种情况下，你可以使用 itertools 模块来实现。

import itertools
def Mismatch(Search,n):
    SearchL = list(Search)
    List     = [] # hold output
    # print list of indices to replace with '$'
    idxs = itertools.combinations(range(len(SearchL)),n)        
    # for each combination `idx` in idxs, replace str[idx] with '$':
    for idx in idxs:
        str = SearchL[:] # make a copy
        for i in idx:
            str[i]='$'
        List.append( ''.join(str) ) # convert back to string
    return List

让我们看看这是怎么工作的：

1. 把 Search 字符串变成一个列表，这样就可以遍历了，创建一个空的 List 来存放结果。

2. idxs = itertools.combinations(range(len(SearchL)),n) 的意思是“在集合 [0,1,2,3,...,字符串长度-1] 中找到所有长度为 n 的子集”。试试看。

   idxs = itertools.combinations(range(5),4)
   for idx in idxs: 
       print idx
   

   看看我说的是什么意思。

3. idxs 的每个元素是一个包含从 0 到 len(SearchL)-1 的 n 个索引的元组（例如 (0,1,2,4)）。对于元组中的每个 i，将 SearchL 中的第 i 个字符替换为 '$'。

4. 将结果转换回字符串并添加到 List 中。

举个例子：

Mismatch('abcde',3)
['$$$de', '$$c$e', '$$cd$', '$b$$e', '$b$d$', '$bc$$', 'a$$$e', 'a$$d$', 'a$c$$', 'ab$$$']
Mismatch('abcde',4) # note, the code you had made lots of duplicates.
['$$$$e', '$$$d$', '$$c$$', '$b$$$', 'a$$$$']