作者goodday06 (goodday)
看板Perl
标题[问题] 由两个DNA 资料库搜索相同的DNA 序列
时间Mon Jan 19 16:39:55 2015
我有两个DNA database:
database A 有约18 万条序列，每条约500nt
database B 有约5 万条序列，每条约5000nt
我希望让这A、B两个database 互相比对，
以找出A、B两个database中，共有相同20nt 的两笔序列。
我先用 "foreach" 将database A 每条序列分开，
再用 "substr" 每20个nt 搜索 (DNA 的正反股都要搜索)
再用 "foreach" 将database B 的序列逐一检查跟 "substr" 相同者
结果... 我用小一点的database 测试并且估算，
这样用笔电算完，总共要四千天左右 XD
想请教先进们
是否有节省时间的运算方式?
或是换好一点的电脑会算比较快吗?
先谢不吝赐教!!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.89.53
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Perl/M.1421656798.A.E10.html
1F：推 herculus6502: 让我想到cas9啊… 01/19 18:07
2F：推 flu: 对DNA sequencing不熟..只是 用cpan module不会比较方便吗？ 01/19 18:58
3F：推 uper: 用hash 01/19 19:51
4F：推 LiloHuang: 可以考虑在第一层分开後，将 substr 的结果存在 %hash 01/19 20:52
5F：→ LiloHuang: 此时第一层的 %hash 里头就会是摆满着一堆切好的资料 01/19 20:54
6F：→ LiloHuang: 然後把第二层的 foreach 直接提到外面去，别弄成巢状 01/19 20:54
7F：推 LiloHuang: my %hash; 01/19 21:06
8F：→ LiloHuang: foreach (@DB_a) { 01/19 21:06
9F：→ LiloHuang: # do substr to put items in %hash 01/19 21:06
10F：→ LiloHuang: } 01/19 21:07
11F：→ LiloHuang: foreach (@DB_b) { 01/19 21:07
12F：→ LiloHuang: if (exists $hash{$_}) { 01/19 21:07
13F：→ LiloHuang: # found! 01/19 21:08
14F：→ LiloHuang: } 01/19 21:08
15F：→ LiloHuang: } 01/19 21:08
16F：推 LiloHuang: 从时间复杂度的角度来看，原先的做法至少是 O(n^2) 01/19 21:09
17F：→ LiloHuang: 但是其实找寻重复的资料这件事情，不需要弄成巢状 01/19 21:10
18F：→ LiloHuang: 假设记忆体够大，可以使用空间来换时间，就不会跑太久 01/19 21:11
19F：→ LiloHuang: 注意当资料量异常大时，你得使用 64bit 的 Perl 直译器 01/19 21:11
20F：→ LiloHuang: 附带一提， put items in %hash 是把资料当作 key 01/19 21:15
21F：→ LiloHuang: 而不是摆到 value 喔 :) 这点要特别提醒一下 01/19 21:16
22F：推 LiloHuang: 如果还嫌太慢要再做更多加速，可再使用平行计算的技巧 01/19 21:17
23F：→ LiloHuang: 如果觉得机器太慢，也可考虑租用Google Compute Engine 01/19 21:19
24F：→ goodday06: 多谢! 我再试看看! 01/20 09:38
25F：→ LiloHuang: 更正，时间复杂度至少会是 O(m*n) 两层回圈资料数不同 01/21 21:50