如果第一次閱讀本系列文檔請(qǐng)先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫在前面 ?謝謝配合~

題目：

最大匹配與RNA二級(jí)結(jié)構(gòu)（Maximum Matchings and RNA Secondary Structures）

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

所給：長(zhǎng)度不超過100的一條RNA序列s。

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

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

?

測(cè)試數(shù)據(jù)

>Rosalind_92

AUGCUUC

測(cè)試輸出

6

?

生物學(xué)背景

????????在26 RNA二級(jí)結(jié)構(gòu)與完美匹配我們了解了完美匹配的概念。但完美匹配出現(xiàn)的前提是U的數(shù)量等于A， G的數(shù)量等于C，在現(xiàn)實(shí)世界，這樣的情況極少出現(xiàn)。如下圖，左邊的序列可以形成完美匹配，右邊的則不可能：

????????所以在這里我們引入最大匹配（maximum matching）的概念，即包含盡可能多邊數(shù)的匹配，如下圖，就是一個(gè)圖的三個(gè)最大匹配情況：

????????下圖就是一個(gè)RNA序列的最大匹配之一：

思路

????????這道題參考26 RNA二級(jí)結(jié)構(gòu)與完美匹配就會(huì)非常簡(jiǎn)單。這里的變化是堿基不再能夠全部形成配對(duì)，形成配對(duì)的數(shù)量由一對(duì)中數(shù)量較少的那個(gè)決定，所以我們只需要把較少的那個(gè)堿基數(shù)量作為控制循環(huán)的因素即可。需要注意的是如果只這樣做，在整個(gè)序列都不能形成一個(gè)互補(bǔ)配對(duì)這一特殊情況下輸出結(jié)果是1，顯然有問題，所以單獨(dú)用一個(gè)判斷控制使輸出結(jié)果為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') # 統(tǒng)計(jì)各種堿基的數(shù)量

GCmax = max(Gnum, Cnum)
GCmin = min(Gnum, Cnum)
AUmax = max(Anum, Unum)
AUmin = min(Anum, Unum) # 把每一對(duì)中較大的和較小的分出來

result = 1 # result存儲(chǔ)組合情況
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: # 用來處理特殊情況，即一個(gè)互補(bǔ)配對(duì)的都沒有
??? result = 0

print(result)