approximate string searching（approximate string matching）

馬馬虎虎的字串搜尋，只需大致符合，不必完全符合。

string distance

兩個字串的距離。字串差異程度。反過來就是字串相似程度。

經典的字串距離是edit distance（Levenshtein distance）：新增、刪除、修改一個字元皆算做一步，一個字串變成另一個字串的最少步數。

演算法（dynamic time warping）

「longest common subsequence: dynamic programming」，比對成功、比對失敗不是加上1、0，而是加上自訂數值。

一、小心設定數值，讓計算結果是距離函數，以客觀衡量多個字串之間的差異程度，避免AB很像、BC很像、AC卻不像的情況。

二、自訂表格計算範圍，加快計算速度。例如只算索引值i j很接近的格子、不算數值太大太小的格子。

三、只取鄰近格子，有時太單純。多取幾格，設定代價。

四、比對字元，有時太瑣碎。字串切成一段一段，以段為單位進行比對，變成兩層。

UVa 164 526 10739 12351

演算法（BK-tree）

允許距離相差k以下。

允許k個字元不符合。

sequence alignment

對齊DNA。此處的sequence源自生物學的DNA序列，也就是字串。

sequence assembly

目前的生化技術沒有辦法確認一個細胞的DNA序列有多長、每個字元為何。折衷的做法是把細胞溶解了攪一攪，打散DNA序列，得到許多零散片段，進一步確認字元。

DNA sequencing：將大量片段拼接成一個長串，得到完整的生物DNA。片段數量極多，經常重疊。

DNA profiling：給定大量片段，找到相符的生物DNA。