【ROSALIND】【练Python，学生信】26 RNA二级结构与完美匹配
如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面 谢谢配合~
题目：
完美匹配与RNA的二级结构（Perfect Matchings and RNA Secondary Structures）
Given: An RNA string s of length at most 80 bp having the same number of occurrences of 'A' as 'U' and the same number of occurrences of 'C' as 'G'.
所给：一条不长于80bp的RNA序列s，序列中“A”出现的频率和“U”一样多，“G”出现的频率和“C”一样多。
Return: The total possible number of perfect matchings of basepair edges in the bonding graph of s.
需得：s中由碱基互补配对形成的所有可能的完美匹配数目。
测试数据
>Rosalind_23
AGCUAGUCAU
测试输出
12
生物学背景
在大多数情况下RNA以单链的形式存在，但与DNA一样，RNA也有碱基互补配对现象，即A与U配对，G与C配对。RNA链内的碱基互补配对形成了多种多样的二级结构，这些结构与RNA的生物学功能紧密相关。如果分子内局部序列形成了互补配对，就可以形成发卡结构（hairpin loop），也称茎环结构（stem loop），如下图：
同一个RNA分子的二级结构可能并不是唯一的，在不同的时间点可能出现不同的碱基配对组合，找到实际存在的二级结构是进行研究的最终目的，但第一步我们需要找到所有可能的分子内碱基配对情况。
数学背景
对图的简介请参考12 重叠图与序列拼接。在图论中，一个匹配是一个边的集合，其中没有任何两条边拥有一个共同顶点，如下图中标红的边所示：
如果一个图G有偶数个顶点，以2n表示，当G的一个匹配有n个边时，我们称这个匹配为完美匹配（Perfect Matchings），因为此时匹配数达到了最大。下图所有红边组成一个完美匹配：
为解决完美匹配的问题，我们不妨假设有一个完全图Kn，有2n个顶点，每个顶点都和其他顶点以一条边相连，如下图：
再令pn是Kn所有的完美匹配，对任意一点x，我们有2n-1种方法把它与其他的点连起来，这之后为了得到完美匹配，我们需要在剩下2n-2个点中实现完美匹配，这样就形成了递归公式，pn=(2n−1)⋅pn−1；又因为p1=1，递归公式可以写成pn=(2n−1)(2n−3)(2n−5)⋯(3)(1)。
对于一条RNA序列s（s=s1…sn），我们可以绘制bonding graph，在bonding graph中，顶点是RNA的碱基按照序列排列，边则分为两类：实线边将相邻的碱基连接起来，虚线边连接可以进行互补配对的碱基，如下图所示：
实际上，这幅图中的每一个匹配都代表着一种可能的碱基互补配对情况， 如下图就表示了一个匹配：
当然，要实现完美匹配，需要A和U出现的频率一样，G和C出现的频率一样。
思路
题目所给的序列已经确定A的数目与U相同，G的数目与C相同。我们实际上不需要管具体序列，只需要想：第一个G进行配对有几种情况？第一个确定后第二个G有几个情况？以此类推，即将A-U配对的数目和G-C配对的数目分别进行阶乘再相乘即可。
代码
f = open('rosalind_pmch.txt', 'r')
input = f.readlines()
f.close()
index = input[0].replace('\n', '')
input = input[1:]
i = 0
seq = ''
while i < len(input):
seq = seq + input[i].replace('\n', '')
i += 1
Anum = 0
Gnum = 0
i = 0
while i < len(seq): #记录A-U和G-C的数目，其实用自带count函数即可
if seq[i] == "A":
Anum += 1
elif seq[i] == "G":
Gnum += 1
i += 1
result = 1
i = Anum
while i>= 1: #用循环进行阶乘运算
result *= Anum
Anum -= 1
i -= 1
i = Gnum
while i>= 1:
result *= Gnum
Gnum -= 1
i -= 1
print(result)
