作者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/m.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