Re: [問題] dna序列密度

[MisterSmile (Mr.Smile)]

※ 引述《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)
推 march20:這 greedy 似乎成立: 如果多看一些會讓
推 march20:密度變大, 那表示有一邊密度本來就比較大
推 march20:那這邊沒道理不被選到 @@
※ 編輯: MisterSmile     來自: 122.116.204.36       (05/31 14:32)
推 seanwu:反例: CCCTTTCCC  L=4
→ seanwu:step 3中找到的，是CCCTT或TTCCC
→ seanwu:這樣找到的答案是 3/5=0.6
→ seanwu:但最大的應該是 6/9 = 0.667
→ seanwu:而且step 4中不論是CCCTT或TTCCC都無法擴張
推 march20:(還沒驗證)我找反例找很久, 總是差一個@@
推 march20:太強啦 XD
※ 編輯: MisterSmile     來自: 122.116.204.36       (06/02 23:52)
→ MisterSmile:真的有反例，被抓到破綻XD