PTT數位生活區 / Perl

[問題] 由兩個DNA 資料庫搜索相同的DNA 序列

看板Perl作者 (goodday)時間10年前 (2015/01/19 16:39), 編輯推噓7(7推 0噓 18→)
留言25則, 5人參與, 最新討論串1/2 (看更多)
我有兩個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://www.ptt.cc/bbs/Perl/M.1421656798.A.E10.html
推
01/19 18:07, , 1F
讓我想到cas9啊…
01/19 18:07, 1F
推
01/19 18:58, , 2F
對DNA sequencing不熟..只是 用cpan module不會比較方便嗎？
01/19 18:58, 2F
推
01/19 19:51, , 3F
用hash
01/19 19:51, 3F
推
01/19 20:52, , 4F
可以考慮在第一層分開後，將 substr 的結果存在 %hash
01/19 20:52, 4F
→
01/19 20:54, , 5F
此時第一層的 %hash 裡頭就會是擺滿著一堆切好的資料
01/19 20:54, 5F
→
01/19 20:54, , 6F
然後把第二層的 foreach 直接提到外面去，別弄成巢狀
01/19 20:54, 6F
推
01/19 21:06, , 7F
my %hash;
01/19 21:06, 7F
→
01/19 21:06, , 8F
foreach (@DB_a) {
01/19 21:06, 8F
→
01/19 21:06, , 9F
# do substr to put items in %hash
01/19 21:06, 9F
→
01/19 21:07, , 10F
}
01/19 21:07, 10F
→
01/19 21:07, , 11F
foreach (@DB_b) {
01/19 21:07, 11F
→
01/19 21:07, , 12F
if (exists $hash{$_}) {
01/19 21:07, 12F
→
01/19 21:08, , 13F
# found!
01/19 21:08, 13F
→
01/19 21:08, , 14F
}
01/19 21:08, 14F
→
01/19 21:08, , 15F
}
01/19 21:08, 15F
推
01/19 21:09, , 16F
從時間複雜度的角度來看，原先的做法至少是 O(n^2)
01/19 21:09, 16F
→
01/19 21:10, , 17F
但是其實找尋重複的資料這件事情，不需要弄成巢狀
01/19 21:10, 17F
→
01/19 21:11, , 18F
假設記憶體夠大，可以使用空間來換時間，就不會跑太久
01/19 21:11, 18F
→
01/19 21:11, , 19F
注意當資料量異常大時，你得使用 64bit 的 Perl 直譯器
01/19 21:11, 19F
→
01/19 21:15, , 20F
附帶一提， put items in %hash 是把資料當作 key
01/19 21:15, 20F
→
01/19 21:16, , 21F
而不是擺到 value 喔 :) 這點要特別提醒一下
01/19 21:16, 21F
推
01/19 21:17, , 22F
如果還嫌太慢要再做更多加速，可再使用平行計算的技巧
01/19 21:17, 22F
→
01/19 21:19, , 23F
如果覺得機器太慢，也可考慮租用Google Compute Engine
01/19 21:19, 23F
→
01/20 09:38, , 24F
多謝! 我再試看看!
01/20 09:38, 24F
→
01/21 21:50, , 25F
更正，時間複雜度至少會是 O(m*n) 兩層迴圈資料數不同
01/21 21:50, 25F
‣ 更多 goodday06 的文章
文章代碼(AID): #1KlCBUuG (Perl)
Perl 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 goodday06 的文章
文章代碼(AID): #1KlCBUuG (Perl)