【ROSALIND】【练Python，学生信】40 最大匹配与RNA二级结构

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

最大匹配与RNA二级结构（Maximum Matchings and RNA Secondary Structures）

Given: An RNA string s of length at most 100.

所给：长度不超过100的一条RNA序列s。

Return: The total possible number of maximum matchings of basepair edges in the bonding graph of s.

需得：共有多少种s形成的最大匹配。

测试数据

>Rosalind_92

AUGCUUC

测试输出

6

生物学背景

        在26 RNA二级结构与完美匹配我们了解了完美匹配的概念。但完美匹配出现的前提是U的数量等于A， G的数量等于C，在现实世界，这样的情况极少出现。如下图，左边的序列可以形成完美匹配，右边的则不可能：

        所以在这里我们引入最大匹配（maximum matching）的概念，即包含尽可能多边数的匹配，如下图，就是一个图的三个最大匹配情况：

        下图就是一个RNA序列的最大匹配之一：

思路

        这道题参考26 RNA二级结构与完美匹配就会非常简单。这里的变化是碱基不再能够全部形成配对，形成配对的数量由一对中数量较少的那个决定，所以我们只需要把较少的那个碱基数量作为控制循环的因素即可。需要注意的是如果只这样做，在整个序列都不能形成一个互补配对这一特殊情况下输出结果是1，显然有问题，所以单独用一个判断控制使输出结果为0。

代码

f = open('input.txt', 'r')
lines = f.readlines()
f.close()

input = lines[1:]
i = 0
seq = ''
while i < len(input):
    seq = seq + input[i].replace('\n', '')
    i += 1

Anum = seq.count('A')
Gnum = seq.count('G')
Cnum = seq.count('C')
Unum = seq.count('U') # 统计各种碱基的数量

GCmax = max(Gnum, Cnum)
GCmin = min(Gnum, Cnum)
AUmax = max(Anum, Unum)
AUmin = min(Anum, Unum) # 把每一对中较大的和较小的分出来

result = 1 # result存储组合情况
while GCmin > 0:
    result *= GCmax
    GCmax -= 1
    GCmin -= 1
while AUmin > 0:
    result *= AUmax
    AUmax -= 1
    AUmin -= 1

if min(Anum, Unum, Gnum, Cnum) == 0: # 用来处理特殊情况，即一个互补配对的都没有
    result = 0

print(result)