我有兩個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
想請教先進們
是否有節省時間的運算方式?
或是換好一點的電腦會算比較快嗎?
先謝不吝賜教!!

讓我想到cas9啊…

對DNA sequencing不熟..只是 用cpan module不會比較方便嗎？

用hash

可以考慮在第一層分開後，將 substr 的結果存在 %hash此時第一層的 %hash 裡頭就會是擺滿著一堆切好的資料然後把第二層的 foreach 直接提到外面去，別弄成巢狀my %hash;foreach (@DB_a) {# do substr to put items in %hash}foreach (@DB_b) {if (exists $hash{$_}) {# found!}}從時間複雜度的角度來看，原先的做法至少是 O(n^2)但是其實找尋重複的資料這件事情，不需要弄成巢狀假設記憶體夠大，可以使用空間來換時間，就不會跑太久注意當資料量異常大時，你得使用 64bit 的 Perl 直譯器附帶一提， put items in %hash 是把資料當作 key而不是擺到 value 喔 :) 這點要特別提醒一下如果還嫌太慢要再做更多加速，可再使用平行計算的技巧如果覺得機器太慢，也可考慮租用Google Compute Engine

多謝! 我再試看看!

更正，時間複雜度至少會是 O(m*n) 兩層迴圈資料數不同