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

[goodday06 (goodday)]

我有兩個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
推 herculus6502: 讓我想到cas9啊…
推 flu: 對DNA sequencing不熟..只是 用cpan module不會比較方便嗎？
推 uper: 用hash
推 LiloHuang: 可以考慮在第一層分開後，將 substr 的結果存在 %hash
→ LiloHuang: 此時第一層的 %hash 裡頭就會是擺滿著一堆切好的資料
→ LiloHuang: 然後把第二層的 foreach 直接提到外面去，別弄成巢狀
推 LiloHuang: my %hash;
→ LiloHuang: foreach (@DB_a) {
→ LiloHuang:    # do substr to put items in %hash
→ LiloHuang: }
→ LiloHuang: foreach (@DB_b) {
→ LiloHuang:    if (exists $hash{$_}) {
→ LiloHuang:       # found!
→ LiloHuang:    }
→ LiloHuang: }
推 LiloHuang: 從時間複雜度的角度來看，原先的做法至少是 O(n^2)
→ LiloHuang: 但是其實找尋重複的資料這件事情，不需要弄成巢狀
→ LiloHuang: 假設記憶體夠大，可以使用空間來換時間，就不會跑太久
→ LiloHuang: 注意當資料量異常大時，你得使用 64bit 的 Perl 直譯器
→ LiloHuang: 附帶一提， put items in %hash 是把資料當作 key
→ LiloHuang: 而不是擺到 value 喔 :) 這點要特別提醒一下
推 LiloHuang: 如果還嫌太慢要再做更多加速，可再使用平行計算的技巧
→ LiloHuang: 如果覺得機器太慢，也可考慮租用Google Compute Engine
→ goodday06: 多謝! 我再試看看!
→ LiloHuang: 更正，時間複雜度至少會是 O(m*n) 兩層迴圈資料數不同