作者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