[問題] dna序列密度

看板Programming作者 (暴力熊)時間16年前 (2009/05/18 11:20), 編輯推噓6(6推 0噓 1→)
留言7則, 3人參與, 最新討論串1/8 (看更多)
在網路上看到的題目 DNA序列是由A、T、C、G組成一串字串序列 舉例:agGCTGCAatGACAGTTGGG 然後找出大於使用者輸入長度L 包含C、G密度最高的序列串 此題解應輸出gGCTGC (假設L=5) 我只有想到用暴力法 列出每一種組合 計算密度 比較大小 再輸出 應該有更快的方法可以用? 懇請板友指教 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 192.192.199.49
推
05/18 15:35, , 1F
DP
05/18 15:35, 1F
推
05/18 15:38, , 2F
先求出 A1~Ai 的CG 個數合, 然後對所有
05/18 15:38, 2F
推
05/18 15:40, , 3F
max (S_i - S_(i-L+1)) for L<i<n
05/18 15:40, 3F
推
05/18 15:46, , 4F
啊, 直接回文
05/18 15:46, 4F
推
05/18 18:32, , 5F
李家同Algorithms的書 多的是這種解題～
05/18 18:32, 5F
→
05/18 18:32, , 6F
沒記錯的話是LCS problem
05/18 18:32, 6F
推
05/19 11:34, , 7F
對阿 不是趙老師和呂學一老師論文嗎
05/19 11:34, 7F
‣ 更多 makiyolove 的文章
文章代碼(AID): #1A4DGRTh (Programming)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 8 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共8篇)
‣ 更多 makiyolove 的文章
文章代碼(AID): #1A4DGRTh (Programming)