如何提高大量的字符串比較速度？

我現(xiàn)在有兩個(gè)字符串?dāng)?shù)組，姑且稱為candidates和bg_db，全部都是長度為20的短字符串，并且每個(gè)字符串的每個(gè)字符只有ATCG四種可能（沒錯(cuò)！就是基因組序列啦?。? ``` candidates = [ 'GGGAGCAGGCAAGGACTCTG', 'GCTCGGGCTTGTCCACAGGA', '...', # 被你看出來啦，這些其實(shí)人類基因的片段 ] bg_db = [ 'CTGCTGACGGGTGACACCCA', 'AGGAACTGGTGCTTGATGGC', '...', # 這個(gè)更多，有十億左右 ] ``` 我的任務(wù)是對candidates的每一個(gè)candidate，找到bg_db中所有與其小于等于4個(gè)差異的記錄，舉個(gè)例子來說: ``` # 上面一條為candidate，即candidates的一個(gè)記錄 # 中間|代表相同，代表不相同 # 下面一條代表bg_db的一條記錄 A T C G A T C G A T C G A T C G A T C G | | | | | | | | | | | | | | | | | | | | # 差異為0 A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G | | | | | | | | | | | | | | | | | | | # 差異為1 T T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G | | | | | | | | | | | | | | | | | | # 差異為2 T T C G T T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G | | | | | | | | | | | | | | | | | # 差異為3 T T C G T T C G A T C C A T C G A T C G A T C G A T C G A T C G A T C G A T C G | | | | | | | | | | | | | | | | # 差異為4 T T C G T T C G A T C C A T C A A T C G ``` 我的問題是如果快速地找到：每一個(gè)candidate在bg_db中與之差異小于等于4的所有記錄,如果采用暴力遍歷的話，以Python為例: ``` def align(candidate, record_from_bg_db):mismatches = 0for i in range(20):if candidate[i] != record_from_bg_db[i]:mismatches += 1if mismatches >= 4:return Falsereturn True candidate = 'GGGAGCAGGCAAGGACTCTG'record_from_bg_db = 'CTGCTGACGGGTGACACCCA' align(candidate, record_from_bg_db) # 1.24微秒左右 # 總時(shí)間: 10000000 1000000000 * 1.24 / 1000 / 1000 / 60 / 60 / 24 / 365 # = 393 # 1千萬個(gè)candidates，10億條bg_db記錄 # 耗時(shí)大約393年 # 完全無法忍受啊 ``` 我的想法是，bg_db是高度有序的字符串(長度固定，每個(gè)字符的可能只有四種)，有沒有什么算法，可以讓candidate快速比較完所有的bg_db，各位大神，求賜教。