Sequence Alignment

Sequence Alignment(Approximate String Matching)

馬馬虎虎的字串比對,只需大致符合,不必完全符合。

主要用途是DNA序列比對。似乎沒有其他用途了。

此處的sequence是指生物學的DNA序列,不是指計算學的數列。此處的sequence其實是連續的字元,也就是字串。

Sequence Assembly

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

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

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

String Distance

Dynamic Time Warping

求出兩個字串的距離。或者說是差異程度、相似程度。

Longest Common Subsequence: Dynamic Programming」加強版。比對成功、比對失敗不是加上1、0,而是加上自訂數值。

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

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

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

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

Edit Distance(Levenshtein Distance)

http://en.wikipedia.org/wiki/String_metric

一個字串,新增、刪除、修改一個字元算做一步,請問需要幾步才能改成另一個指定字串?

這裡定義的「步」恰好是一種距離函數。

UVa 164 526 10739 12351

k-Difference String Matching

允許距離相差k以下。

http://algnotes.wordpress.com/2014/01/10/

http://algnotes.wordpress.com/2014/02/01/k-palindrome-subsequence/

http://maskray.me/blog/2013-02-10-bk-tree

http://shygypsy.com/tools/BkTree.cpp

k-Mismatch String Matching

允許k個字元不符合。

http://algnotes.wordpress.com/2014/01/09/

k-Mismatch Longest Common Substring

https://arxiv.org/abs/1409.1694