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

題目：

完美匹配與RNA的二級(jí)結(jié)構(gòu)（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'.

所給：一條不長(zhǎng)于80bp的RNA序列s，序列中“A”出現(xiàn)的頻率和“U”一樣多，“G”出現(xiàn)的頻率和“C”一樣多。

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

需得：s中由堿基互補(bǔ)配對(duì)形成的所有可能的完美匹配數(shù)目。

?

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

>Rosalind_23

AGCUAGUCAU

測(cè)試輸出

12

?

生物學(xué)背景

? ? ? ? 在大多數(shù)情況下RNA以單鏈的形式存在，但與DNA一樣，RNA也有堿基互補(bǔ)配對(duì)現(xiàn)象，即A與U配對(duì)，G與C配對(duì)。RNA鏈內(nèi)的堿基互補(bǔ)配對(duì)形成了多種多樣的二級(jí)結(jié)構(gòu)，這些結(jié)構(gòu)與RNA的生物學(xué)功能緊密相關(guān)。如果分子內(nèi)局部序列形成了互補(bǔ)配對(duì)，就可以形成發(fā)卡結(jié)構(gòu)（hairpin loop），也稱莖環(huán)結(jié)構(gòu)（stem loop），如下圖：

? ? ? ? 同一個(gè)RNA分子的二級(jí)結(jié)構(gòu)可能并不是唯一的，在不同的時(shí)間點(diǎn)可能出現(xiàn)不同的堿基配對(duì)組合，找到實(shí)際存在的二級(jí)結(jié)構(gòu)是進(jìn)行研究的最終目的，但第一步我們需要找到所有可能的分子內(nèi)堿基配對(duì)情況。

?

數(shù)學(xué)背景

? ? ? ? 對(duì)圖的簡(jiǎn)介請(qǐng)參考12 重疊圖與序列拼接。在圖論中，一個(gè)匹配是一個(gè)邊的集合，其中沒有任何兩條邊擁有一個(gè)共同頂點(diǎn)，如下圖中標(biāo)紅的邊所示：

? ? ? ? 如果一個(gè)圖G有偶數(shù)個(gè)頂點(diǎn)，以2n表示，當(dāng)G的一個(gè)匹配有n個(gè)邊時(shí)，我們稱這個(gè)匹配為完美匹配（Perfect Matchings），因?yàn)榇藭r(shí)匹配數(shù)達(dá)到了最大。下圖所有紅邊組成一個(gè)完美匹配：

? ? ? ? 為解決完美匹配的問題，我們不妨假設(shè)有一個(gè)完全圖Kn，有2n個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)都和其他頂點(diǎn)以一條邊相連，如下圖：

? ? ? ? 再令pn是Kn所有的完美匹配，對(duì)任意一點(diǎn)x，我們有2n-1種方法把它與其他的點(diǎn)連起來，這之后為了得到完美匹配，我們需要在剩下2n-2個(gè)點(diǎn)中實(shí)現(xiàn)完美匹配，這樣就形成了遞歸公式，pn=(2n?1)?pn?1；又因?yàn)閜1=1，遞歸公式可以寫成pn=(2n?1)(2n?3)(2n?5)?(3)(1)。

? ? ? ? 對(duì)于一條RNA序列s（s=s1…sn），我們可以繪制bonding graph，在bonding graph中，頂點(diǎn)是RNA的堿基按照序列排列，邊則分為兩類：實(shí)線邊將相鄰的堿基連接起來，虛線邊連接可以進(jìn)行互補(bǔ)配對(duì)的堿基，如下圖所示：

? ? ? ? 實(shí)際上，這幅圖中的每一個(gè)匹配都代表著一種可能的堿基互補(bǔ)配對(duì)情況， 如下圖就表示了一個(gè)匹配：

? ? ? ? 當(dāng)然，要實(shí)現(xiàn)完美匹配，需要A和U出現(xiàn)的頻率一樣，G和C出現(xiàn)的頻率一樣。

?

思路

題目所給的序列已經(jīng)確定A的數(shù)目與U相同，G的數(shù)目與C相同。我們實(shí)際上不需要管具體序列，只需要想：第一個(gè)G進(jìn)行配對(duì)有幾種情況？第一個(gè)確定后第二個(gè)G有幾個(gè)情況？以此類推，即將A-U配對(duì)的數(shù)目和G-C配對(duì)的數(shù)目分別進(jìn)行階乘再相乘即可。

?

代碼

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的數(shù)目，其實(shí)用自帶count函數(shù)即可
??? if seq[i] == "A":
??????? Anum += 1
??? elif seq[i] == "G":
??????? Gnum += 1
??? i += 1
result = 1
i = Anum
while i>= 1: #用循環(huán)進(jìn)行階乘運(yùn)算
??? result *= Anum
??? Anum -= 1
??? i -= 1
i = Gnum
while i>= 1:
??? result *= Gnum
??? Gnum -= 1
??? i -= 1

print(result)

?