嵌套循环在Python中找到所有可能的组合

大家好我有一个生物信息学问题，我可以帮忙做。它相当长，但我会尝试将它分解成更小的部分，任何帮助都很棒。嵌套循环在Python中找到所有可能的组合

我有RNA长度的“n”个由4个字母A，U，C，G被导入为一个字符串成Python，即能够折叠，使一个循环的序列。循环是通过匹配序列中的字母对来完成的，以便A与U相连，C与G相交，G与U相交，使字符串折叠回去。

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

我试图张贴图片，但我没有足够的声望值:(

在杂志上，我引用有关嵌套循环方法笔者谈判寻找所有可能的组合，其中这是可能的然后将它们包含在一个组中，稍后再调用

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

再次，任何帮助将是伟大的，如果有什么是叔叔AR请告诉我

编辑：

一个例子是SEQ =“aggcuugaguuu”，其中输出中的一个表现出SEQ的配对[0：2]与序列[9时11]意味着代码形式像U形。

如果你想象中的字符串作为物理一条绳子，并在3点举行，并在三个不同的分稳住它，然后摸了摸分在一起，将导致串，形成一个循环。我期待识别使用的6个点。

我不是找代码为我写我只是想知道组成的代码的方法。

我试过的方法，其中SEQ1 =输入代码和SEQ2 =反向输入代码和移动沿SEQ1 SEQ2寻找三个相邻对，但这并没有给我正确的输出。

来源

2012-04-24 Matthew McGuinness

我不知道你在找什么。你能举一些短期投入和预期的相应产出的例子，推理吗？ – 2012-04-24 22:59:28

这里你不会有太多的运气，要求为你写代码。你尝试了什么？出了什么问题，什么让你感到困惑？ – 2012-04-24 22:59:29

如果这是一个研究问题，而不是作业，我强烈建议biopython。它已经有方便的方法来转录，翻译，反向补充等。 – 2012-04-24 23:59:54

如果你的RNA是不是非常长（基地大概OK千;数十万绝对不是OK），你可以摆脱一个简单的为O（n^3）算法。 O（n^3）意味着执行时间在最坏情况下与基数的立方成正比。作者提到嵌套循环暗示着这个简单但相当慢的方法。

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)的每个可能循环的元组列表。这意味着从碱基编号start_pos开始的pair_count碱基序列后面是碱基的循环，接着是反向的互补序列。序列的反义拷贝从基地start_pos + pair_count + loop_length开始。第一个基数是0，而不是1（我们是程序员）。

一个例子可以说明清楚：print find_loops('GGGGAUUACAGCGUGUAAUCAAUA')回报[(4, 3, 13), (3, 7, 3)]，也就是说，它发现两个循环：

在第4位，三个基地，AUU，附上的13个基地的循环，并绑定到AAU在位置20;
在位置3，7个碱基，GAUUACA，包围的三个基地一个循环，和在位置13

结合UGUAAUC没有第一if，该函数也将返回像（3,6环，5）（即位置3的GAUUAC包含5个碱基的环，并在位置14处与GUAAUC结合），其与上面的（3,7,3）是相同的环，只是没有像将要去除的那样拉紧。

希望这会有所帮助。如果你需要更快的算法，我相信有一个动态编程解决方案可以处理更长的字符串。让我知道，我会考虑它。虽然...

来源

2012-04-25 00:17:42 cvoinescu

我很开心，我只是做了一个小小的舞蹈！如果我见过你，我应该给你一大杯啤酒。正如我前面所说的那样，非常感谢你，我不需要提供代码，我只需要一点点指导，但这太棒了！我在看非编码RNA，所以我远远低于1000个碱基长。我意识到有更快的方法，但我远离动态编程，因为这是每个人都使用（可能是出于很好的原因）。我会在整个晚上给你一个测试，让你知道它是怎么回事。再次感谢您 – 2012-04-25 01:19:15

您是否考虑过使用产品itertools。然后你可以遍历结果并只选择你喜欢的结果。

来源

2012-04-24 23:00:44 gruszczy

嗨，感谢您的快速反应，不幸的是，这不是我正在使用的正确组合发生器。虽然我不知道itertools，所以这很有用谢谢 – 2012-04-24 23:18:11

嵌套循环在Python中找到所有可能的组合

回答

相关问题