回分類題庫
d056: 5.RNA序列摺疊
關鍵字: 101年台中區複賽

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 47 Times / 44 Users | Submit : 86 Times / 48 Users | Accepted rate : 92%
題目加入時間 : 2013-09-13 13:51

Content: 简体中文

RNA (Ribonucleic acid)是一個相當長的序列,序列成分主要是由四種核甘酸組成,分別以四個字母表示:A, C, G, U。且根據RNA性質:A與U會形成鍵結,而C與G會形成鍵結,其他配對則不會形成鍵結。RNA序列會藉由摺疊(folding)的方式讓序列中的核甘酸形成鍵結。根據這些有鍵結以及沒鍵結所產生的核甘酸序列,可以形成各式各樣的二級結構。在RNA序列中求出最穩定的二級結構的方法中,Nussinov演算法是常被廣泛使用。此演算法會找出最大鍵結數的二級結構,當作是最穩定的二級結構,尋找的方式如下。

假設一RNA序列長度為L,每個序列中的每一個核甘酸依序表示成dk,1≤k≤L,且dk是A, C, G, U中的某一個字母。令D(i, j)代表DNA子序列(subsequence) di到dj的鍵結總數;W(i,j)表示di與dj是否會形成鍵結,是的話W(i,j)=1,否則的話W(i,j)=0。D(i, j)可以從下面的遞迴式推導出來。

 

其中已知 

 

 從以上式子可知:欲求一D(i, j),必須先分別求出右邊四個式子的值,然後再求出這四個值的最大值;而右邊的第四個式子又必須先求出(j-i-1)項的最大值。以序列ACGUGUCU為例,L為8,其各D(i, j)的值如下表所示。以D(1, 5)為例,

第一式:D(2, 5)=1

第二式:D(1, 4)=2

第三式:D(2, 4)+W(d1,d5)=1+0=1  (其中W(d1,d5)=W(A, G)=0,因為A與G)無法鍵結。

第四式:max{D(d1,d2)+D(d3,d5), D(d1,d3)+D(d4,d5) , D(d1,d4)+D(d5,d5) } = max{0+0,1+0,2+0} = max{0,1,2} = 2 

最後從這四式取出最大值即為D(d1,d5)之值,也就是2。而整個RNA序列的最大鍵結數是3,也就是D(d1,d8)之值。 

 

請寫出一個Nussinov演算法之程式,輸入一RNA序列,求出該RNA序列所可以形成的最穩定的二級結構的鍵結數。 

Input:

輸入資料只有一行,內容為一RNA序列:由A, C, G, U組成之長字串。(最大長度100)

Output:

請輸出此RNA序列可形成的最大鍵結數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
ACCGUACG

輸入2:
ACGUAGUCAAACGU

Sample Output :

輸出1:
3

輸出2:
5

Hint :

Author :

101年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum