嵌套循环来查找Python中所有可能的组合

Question

嗨，我有一个生物信息学的问题需要帮助。它相当长，但我会试着把它分解成更小的部分，任何帮助都很好。在

我有一个由4个字母a，U，C，G组成的RNA长度序列，它被作为一个字符串导入Python，它可以折叠成一个循环。一个循环是通过匹配序列中的一对字母组成的，这样A代表U，C代表G，G代表U，这样字符串就可以自己折叠起来了。在

问题是，必须有三个或更多的字母相邻组成一对，多于或等于三个字母组成一对，并且至少三个字母的部分之间也必须有间隙。在

我试着贴一张照片，但是我没有足够的声望点数：（

在这本杂志中，我引用了作者所说的一种嵌套循环方法，它可以找到所有可能的组合，然后将它们包含在一个组中，以便以后调用。在

我的问题是编写嵌套循环，因为我不熟悉编程和python。以及以一种可以识别成对的方式存储序列，并可能将它们相加。在

再次任何帮助将是伟大的，如果有什么不清楚的，请让我知道

编辑：

一个例子是seq='aggcuugaguu'，其中一个输出显示seq[0:2]与seq[9:11]的配对，这意味着代码的形式类似于U形。在

如果你把绳子想象成一根物理的绳子，把它放在三个不同的点上，然后把它们连在一起，就会使绳子形成一个循环。我想找出使用的6个点。在

我不想为我编写代码，我只想知道一种编写代码的方法。在

我尝试了一种方法，其中seq1=输入代码，seq2=反向输入代码，然后沿着seq1移动seq2，寻找三个相邻的对，但这并没有给我正确的输出。在

Answer 1

如果你的RNA不是很长（一千个碱基可能没问题，几十万个碱基绝对不好），你可以用一个简单的O（n^3）算法来逃避。O（n^3）表示执行时间在最坏的情况下与基数的立方成正比。作者提到了嵌套循环（nested loops），这暗示了这种简单但相当缓慢的方法。在

def find_loops(rna, min_pairs=3, min_loop=3):
    n = len(rna)
    result = []
    for loop_start in xrange(min_pairs, n - min_pairs - min_loop + 1):
        for loop_end in xrange(loop_start + min_loop, n - min_pairs):
            if (loop_end - loop_start < min_loop + 2 or 
                    not base_pair(rna[loop_start], rna[loop_end - 1])):
                max_pairs = min(loop_start, n - loop_end)
                for k in xrange(max_pairs):
                    if not base_pair(rna[loop_start - k - 1], rna[loop_end + k]):
                        break
                else:
                    k = max_pairs
                if k >= min_pairs:
                    result.append((loop_start - k, k, loop_end - loop_start))
    return result

def base_pair(x, y):
    return (x == 'A' and y == 'U' or
            x == 'C' and y == 'G' or
            x == 'G' and y == 'C' or
            x == 'U' and y == 'A')

这会在RNA循环的所有可能的开始和结束处迭代，然后在两个方向上离开潜在环的末端，只要碱基仍然配对。当它到达一对不匹配的碱基时，它停止并检查是否至少有最少的对。如果有，它会将循环添加到结果列表中。在

第一个if是为了避免列出可能被“压缩”得更紧的循环。正如条件所示，如果一个循环太短（少于5个碱基），或者其末端不匹配，则可以将其压缩得更紧。在

结果是一个元组列表，每个可能的循环对应一个，格式为(start_pos, pair_count, loop_length)。这意味着一个pair_count碱基序列，从基数start_pos开始，后面是一个loop_length碱基的循环，然后是相反的互补序列。序列的反义拷贝起始于碱基start_pos + pair_count + loop_length。第一个基数是0，不是1（我们是程序员）。在

一个例子可以让这一点更清楚：print find_loops('GGGGAUUACAGCGUGUAAUCAAUA')返回{}，也就是说，它找到两个循环：

• 在位置4，三个碱基AUU包围一个由13个碱基组成的循环，并在位置20绑定到{}
• 在位置3，七个碱基GAUUACA包围一个由三个碱基组成的循环，并在位置13绑定到UGUAAUC。在

如果没有第一个if，函数还将返回类似（3，6，5）的循环（即在位置3的GAUUAC包含一个五个基的循环，并在位置14绑定到GUAAUC），这是与上面的（3，7，3）相同的循环，只是压缩得不够紧。在

希望这有帮助。如果你需要一个更快的算法，我相信有一个动态编程解决方案可以处理更长的字符串。告诉我，我会考虑的。不过，这几乎不容易理解。。。在

Answer 2

您是否考虑过使用来自itertools的产品。然后，您可以迭代结果并只选择您喜欢的这些结果。在