python - DNA 搜索序列正则表达式中存在多个不匹配

Question

我编写了这个野蛮的脚本来创建字符串的排列，其中在字符串中所有可能的位置组合中包含 n 个(最多 n=4)个 $。我最终将 .replace('$','(\\w)') 用于 dna 搜索序列中的不匹配。由于我编写脚本的方式，某些排列的 $ 数量少于请求的数量。然后我编写了一个脚本来删除它们，但它似乎没有效果，并且每次运行删除脚本时，它都会删除更多不需要的排列。在下面粘贴的代码中，您将看到我使用具有 4 个不匹配的简单序列来测试该函数。然后，我运行一系列删除脚本，计算每次删除的表达式数量...根据我的经验，删除所有少于 4 个通配符 $ 的表达式大约需要 8 次。我对此有几个问题:

1. 是否有内置函数可用于搜索“n”个不匹配项？也许甚至在biopython中？到目前为止，我已经看到了 Paul_McGuire_regex 函数:
   Search for string allowing for one mismatch in any location of the string ,
   这似乎只会产生 1 个不匹配。我必须承认，我并不完全理解该页面上其余函数中的所有代码，因为我是一个非常新的编码员。

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

我们可以通过回答问题 1 来消除问题 2 和问题 3，但理解问题 3 很重要，因此我将首先这样做，然后向您展示如何完全避免它:

问题 3

关于问题 3，这是因为当您在 python 中循环列表并在循环内对其进行更改时，循环的列表会发生变化。

来自python docs on control flow (for statement section) :

It is not safe to modify the sequence being iterated over in the loop (this can only happen for mutable sequence types, such as lists).

假设您的列表是[a,b,c,d]，然后使用for el in List循环遍历它。假设 el 当前是 a 并且您执行 List.remove(el)。

现在，您的列表是[b,c,d]。然而，迭代器指向列表中的第二个元素(因为它已经完成了第一个元素)，现在是 c。本质上，您已经跳过了b。所以问题是您正在修改正在迭代的列表。

有几种方法可以解决这个问题:如果您的列表复制起来并不昂贵，您可以制作一个副本。因此，迭代 List[:] 但从 List 中删除。

但是假设一直复制 List 的成本很高。然后你要做的就是向后迭代它。请注意下面的反转:

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) 表示“查找集合中长度为 n 的所有子集 [0,1,2, 3，...，搜索字符串长度-1]。尝试一下

   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$$$$']