我現(xiàn)在有兩個(gè)字符串?dāng)?shù)組，姑且稱為candidates和bg_db，全部都是長(zhǎng)度為20的短字符串，并且每個(gè)字符串的每個(gè)字符只有ATCG四種可能（沒(méi)錯(cuò)！就是基因組序列啦?。?
```
candidates = [
'GGGAGCAGGCAAGGACTCTG',
'GCTCGGGCTTGTCCACAGGA',
'...',
# 被你看出來(lái)啦，這些其實(shí)人類基因的片段
]
bg_db = [
'CTGCTGACGGGTGACACCCA',
'AGGAACTGGTGCTTGATGGC',
'...',
# 這個(gè)更多，有十億左右
]
```
我的任務(wù)是對(duì)candidates的每一個(gè)candidate，找到bg_db中所有與其小于等于4個(gè)差異的記錄，舉個(gè)例子來(lái)說(shuō):
```
# 上面一條為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
```
我的問(wèn)題是如果快速地找到：每一個(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千萬(wàn)個(gè)candidates，10億條bg_db記錄
# 耗時(shí)大約393年
# 完全無(wú)法忍受啊
```
我的想法是，bg_db是高度有序的字符串(長(zhǎng)度固定，每個(gè)字符的可能只有四種)，有沒(méi)有什么算法，可以讓candidate快速比較完所有的bg_db，各位大神，求賜教。
