Bitap Algorithm
透過 bitwise operation 實現 approximate string matching
精確搜索
給定一個字串 Text 以及欲搜索的內容 Query
Text : CATCATGGA
Query: CATGG
首先先建一個 Bitmask 的表， X 軸是 Query，Y 軸是所有的 Characters，如果 Query[i] == c 就設成 0 其他設成 1
Bitmask[c][i] = 0 if Query[i] == c
C A T G G
A 1 0 1 1 1
C 0 1 1 1 1
T 1 1 0 1 1
G 1 1 1 0 0
演算法一開始初始化一個跟 Query 等長的 state bitmask，裡面全部設定為 1。
1 == mismatch
0 == match
CATCATGGA
state = 11111
每次計算時，將 prevState = state，然後 prevState 左移 1 個 bit，跟 Bitmask[c] 做 OR operation，c 從 Text 最後面的 character iterate 到最前面。
下方 state 的結果其意義對應到上方的 sub-query，如果結果為 1 表示有 sub-query mismatch，結果為 0 表示 sub-query match。
Step 1:
CATCATGGA
G 1
GG 1
TGG 1
ATGG 1
CATGG 1
prevState = 11111
---------------------------
prevState << 1 = 11110
or) Bitmask[“A”] = 10111
---------------------------
state = 11111
Step 2:
CATCATGGA
G 0
GG 1
TGG 1
ATGG 1
CATGG 1
prevState = 11111
---------------------------
prevState << 1 = 11110
or) Bitmask[“G”] = 11100
---------------------------
state = 11110
Step 3:
CATCATGGA
G 0
GG 0
TGG 1
ATGG 1
CATGG 1
prevState = 11110
---------------------------
prevState << 1 = 11100
or) Bitmask[“G”] = 11100
---------------------------
state = 11100
Step 4:
CATCATGGA
G 1
GG 1
TGG 0
ATGG 1
CATGG 1
prevState = 11100
---------------------------
prevState << 1 = 11000
or) Bitmask[“T”] = 11011
---------------------------
state = 11011
Step 5:
CATCATGGA
G 1
GG 1
TGG 1
ATGG 0
CATGG 1
prevState = 11011
---------------------------
prevState << 1 = 10110
or) Bitmask[“A”] = 10111
---------------------------
state = 10111
Step 6: 當做發現 state 的 MSB 為 0 時，就代表找到 Text 中存在的 Query 了。
CATCATGGA
G 1
GG 1
TGG 1
ATGG 1
CATGG 0
prevState = 10111
---------------------------
prevState << 1 = 01110
or) Bitmask[“C”] = 01111
---------------------------
state = 01111
|
`--- query hit!
模糊搜索
設定一個 Edit distance threshold，看 threshold 多少就用多少個 state vector 記錄。只是在有 edit distance tolerance 的 state vector 需要同時考慮以下四種狀況，並將結果 AND 起來（因為只要有任一個情況的 state vector 出現 0，就代表有 sub-query match）
Deletion
考量下一個 Text character 是 Deletion 的情況時，就代表下一個 Text character 不用去做比對，也就代表現在的狀態已經是比對過下一個 character 的狀態了，所以 state = prevState_R{E-1}。
$E-1$ 是因為加上這個 character 的 deletion 就會讓目前的 edit distance 變成 $E$
拿上面範例的 Step 4 來看：
CATCATGGA
_G 0
_GG 0
_TGG 1
_ATGG 1
_CATGG 1
prevState = 11100
---------------------------
state = 11100
Subsitution
考量下一個 Text character 是 Substitution 的情況時，無論下一個 Query character 是什麼結果都會是 match，也就代表不用去 OR bitmask，所以 state = prevState_R{E-1} << 1。
拿上面範例的 Step 4 來看，可以看到沒有 OR Bitmask["T"]，其實就是讓 G, GG 這兩個 sub-query 能夠容忍一個 Subsitution：
CATCATGGA
G 0
GG 0
TGG 0
ATGG 1
CATGG 1
prevState = 11100
---------------------------
prevState << 1 = 11000
Insertion
考量下一個 Text character 是 Insertion 的情況時，因為除了原本就要比的下一個 character，還多了一個 insertion，所以 state = ((prevState_R{E-1} << 1) | Bitmask[c]) << 1。
拿上面範例的 Step 4 來看，需要位移兩個 character 才能完成這輪的比對，一個是原本就要比的 "T" 跟一個 Insertion。
CATCA_TGGA
G 0
GG 1
TGG 1
ATGG 0
CATGG 1
prevState = 11100
---------------------------
prevState << 1 = 11000
or) Bitmask[“T”] = 11011
---------------------------
state = 11011
state << 1 = 10110
Match
考量下一個 Text character 是 Match 的情況時，跟原本的 Exactly match 計算方式相同，所以 state = (prevState_R{E} << 1) | Bitmask[c]
Example
下圖來自 GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis, Damla Senol Cali et al., MICRO 2020
References
GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis, Damla Senol Cali et al., MICRO 2020
SeGraM: A Universal Hardware Accelerator for Genomic Sequence-to-Graph and Sequence-to-Sequence Mapping, Damla Senol Cali et al., ISCA 2022