作者MisterSmile (Mr.Smile)
看板Programming
標題Re: [問題] dna序列密度
時間Sat May 30 14:12:20 2009
※ 引述《makiyolove (暴力熊)》之銘言：
: 在網路上看到的題目
: DNA序列是由A、T、C、G組成一串字串序列
: 舉例:agGCTGCAatGACAGTTGGG
: 然後找出大於使用者輸入長度L
: 包含C、G密度最高的序列串
: 此題解應輸出gGCTGC (假設L=5)
: 我只有想到用暴力法
: 列出每一種組合 計算密度 比較大小 再輸出
: 應該有更快的方法可以用?
: 懇請板友指教
想到一個作法，不確定有沒有問題，歡迎大家討論
step.1
假設此字串序列是s，長度是k，
先開一個同樣大小的陣列c[k]，紀錄C、G出現的累積次數
s: a g G C T G C A a t G A C A G T T G G G
c: 0 1 2 3 3 4 5 5 5 5 6 6 7 7 8 8 8 9 10 11
step.2
找出的序列長度要大於L，所以長度最小是 L' = L+1
計算長度是L'的序列中，包含C、G的數量
（因為長度一樣，所以C、G次數越多的密度越高）
c'[x]=c[x]-c[x-(L'+1)];
s: a g G C T G C A a t G A C A G T T G G G
c: 0 1 2 3 3 4 5 5 5 5 6 6 7 7 8 8 8 9 10 11
c': - - - - - 4 5 4 3 2 3 2 2 2 3 3 2 3 3 4
^
step.3
把c'掃過一遍找出最大值(範例中的5)
所以 s': aGCTGC 是長度為L'的序列中密度最高的
step.4
再從此序列的頭尾開始擴張，
如果相鄰的是C、G，將其加入此序列s'
往前找到第一個不為C、G的就停止
往後也是找到不是C、G的就停
假設s'長度是m，其中C、G的數量是n，則密度是 n/m
如果隔壁的是C or G，加入後密度變成 (n+1)/(m+1)
如果隔壁的不是C、G，加入後密度變成 n/(m+1)
因為 n/(m+1) < n/m < (n+1)/(m+1)
這樣就可以找到密度最高的序列
但是還要再考慮到step.3最大值不只一個時，序列重疊的情況
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.204.36
※ 編輯: MisterSmile 來自: 122.116.204.36 (05/30 14:13)
1F：推 march20:這 greedy 似乎成立: 如果多看一些會讓 66.75.255.220 05/30 18:32
2F：推 march20:密度變大, 那表示有一邊密度本來就比較大 66.75.255.220 05/30 18:32
3F：推 march20:那這邊沒道理不被選到 @@ 66.75.255.220 05/30 18:33
※ 編輯: MisterSmile 來自: 122.116.204.36 (05/31 14:32)
4F：推 seanwu:反例: CCCTTTCCC L=4 210.70.137.244 06/02 08:07
5F：→ seanwu:step 3中找到的，是CCCTT或TTCCC 210.70.137.244 06/02 08:07
6F：→ seanwu:這樣找到的答案是 3/5=0.6 210.70.137.244 06/02 08:08
7F：→ seanwu:但最大的應該是 6/9 = 0.667 210.70.137.244 06/02 08:08
8F：→ seanwu:而且step 4中不論是CCCTT或TTCCC都無法擴張 210.70.137.244 06/02 08:09
9F：推 march20:(還沒驗證)我找反例找很久, 總是差一個@@ 66.75.255.220 06/02 13:04
10F：推 march20:太強啦 XD 66.75.255.220 06/02 13:05
※ 編輯: MisterSmile 來自: 122.116.204.36 (06/02 23:52)
11F：→ MisterSmile:真的有反例，被抓到破綻XD 122.116.204.36 06/03 00:30