Re: [問題] dna序列密度
※ 引述《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)
推
05/30 18:32, , 1F
05/30 18:32, 1F
推
05/30 18:32, , 2F
05/30 18:32, 2F
推
05/30 18:33, , 3F
05/30 18:33, 3F
※ 編輯: MisterSmile 來自: 122.116.204.36 (05/31 14:32)
推
06/02 08:07, , 4F
06/02 08:07, 4F
→
06/02 08:07, , 5F
06/02 08:07, 5F
→
06/02 08:08, , 6F
06/02 08:08, 6F
→
06/02 08:08, , 7F
06/02 08:08, 7F
→
06/02 08:09, , 8F
06/02 08:09, 8F
推
06/02 13:04, , 9F
06/02 13:04, 9F
推
06/02 13:05, , 10F
06/02 13:05, 10F
※ 編輯: MisterSmile 來自: 122.116.204.36 (06/02 23:52)
→
06/03 00:30, , 11F
06/03 00:30, 11F
討論串 (同標題文章)