（想看高清視頻，請用文章下方的高清視頻連結，在電腦上打開觀看）
字幕內容
到目前為止，我們已經討論了幾種不同的解決精確匹配問題的方法。簡單精確匹配、Boyer-Moore算法、和索引輔助的離線方法。但是精確匹配並不是我們很想要的。
測序序列不一定與基因組上原來位置的序列相匹配。有幾個原因，讓測序序列、與參考基因組的序列之間有差異。
測序序列、與參考序之間有差異的一個原因，是因為我們的測序序列會有錯誤，就像我們之前所討論的那樣，有時序列儀會在判讀一個測序序列時發生鹼基誤讀。當這種發生情況時，鹼基可能不再與參考基因組的序列相匹配。
另一個可能有差異的原因，是因為我們所研究的基因組、與參考基因組，是不一樣的基因組。
我們之前說過，兩個不相關的人，他們的基因組序列相似度是99％、或99.9％，但不是完全相同的，也就是說每一個基因組都會有一些不同。在測序得到的序列鹼基、和參考基因組的鹼基之間，會有差異。這是會有差異的另一個原因。
因此，僅僅只有精確匹配算法是不夠的。我們需要可以進行近似匹配的算法，允許文本、和模式之間有差異。
那麼，我們可能遇到什麼樣的差異？
這是一個例子，這是一個把P對齊到T的例子。用這種對齊方式，我們看到一個區別。而這種特殊的差別，被稱為「錯配」或「鹼基替代」。
這裡是另一種差別。這次的差別是，P對應到T時，多出一個額外的鹼基。可以看到在頂部的紅色的破折號，被稱為「gap」（差距）。因此，以紅色突出顯示的「G」，是模式P相對於文本T的一個「插入」。同樣，我們也可以認為這是在文本T相對於模式P的一個「缺失」。這是另一種我們可以找到的「gap」（差距）。就象這個。這其實就是我們以前看到的（插入的）鏡像。這就是文本T相對於模式P的一個「插入」，也就是模式P相對於文本T的一個「缺失」。
我們想要能夠描述兩個字符串之間的差距。換句話說，我們想要能夠描述它們之間有多少差別，差距是多大。這樣，我們必須要能夠準確地定義這個「距離」。
所以第一種差距，我們將之定義為「漢明距離」（Hamming distance）。所以如果你有兩個字符串，X和Y，這兩個字符串的長度相同，我們可以將X和Y之間的漢明距離定義為：我們需要做的最小的替代次數。也就是把一個字符串，通過替換其中的字符，將之轉換成另一個字符串。
在這個例子中，我們需要做1次、2次、3次替換，才能將X變成Y，反之亦然。這樣，我們就說，這兩個字符串之間的漢明距離為3。
現在，這裡有一個稍微不同的對「距離」的定義。這叫做「編輯距離」，有時也叫做「Levenshtein距離」。兩個字符串之間的「編輯距離」等於：要將一個字符串轉換為另一個字符串，所要做的、最少的編輯次數。
其中單個編輯可以是一個鹼基替換，也可以是插入或缺失一個鹼基，因此，讓我指出「編輯距離」和「漢明距離」之間的差別。
這在個例子中，首要的一點是，（兩個字符串之間的）差異不僅僅是鹼基替換。所以，如果是用編輯距離，我們可以象使用替換一樣，來用插入、缺失。
第二個區別是，對於編輯距離，X和Y不必要是相同的長度。這是有道理的，因為要把一個字符串變長或變短，只能通過插入或缺失。
這裡有一個例子，這個X和Y之間的編輯距離是多少？好。如果我們仔細看，我們可以在這裡看到一個替代，然後，如果我們再往前看一點，可以注意到：在這個位置，這個字符串比那個字符串多了一個A。這意味著有2次編輯，一次是替換，另一次是X相對於Y有一個插入。所以我們會說：編輯距離是2。
這是另一個例子，這個X和Y之間的編輯距離是多少？這個例子有點困難。實際上，編輯距離還是2，但是對比於原來的X和Y，看上去它的編輯距離象是更大。
我會在稍後的講座中，再回過頭來談這個關於找到「編輯距離」的算法。
但本節講座的其餘部分，和關於近似匹配的講座中，我會只談漢明距離和替換。關於插入和缺失，我們會在談編輯距離的時候再談。
這是我們之前看到的簡單精確匹配算法。我們想把簡單精確匹配算法，用到有錯配的情況中去。換句話說，我們想要在一定的漢明距離之內，找出模式P在文本T內的出現情況。
所以，精確匹配是在漢明距離為0（的條件下，找出匹配的情況）。但是現在，我們也要允許在漢明距離大於0的範圍之內，找到匹配的情況。所以我們是否可以通過修改這個算法，來做到這一點？
是的，它其實很簡單。主要要做的事情，是防止內循環一碰到一個錯配，就立即放棄。好。替代的方案是，我們讓內循環來跟蹤：已發現了多少次錯配。然後，只有當超過了最大可容許的錯配數時，才終止內部循環，放棄這個比對。這是實現這個想法的代碼。並將接下來的實踐中，我們將再次看到應用這個實現方法。
所以，我們可以很容易地把簡單精確匹配算法，改成能算做近似匹配的東西。
但如果你仔細地想想它，我想你會同意，要做到下面這一點是有難度的。就是要想把例如Boyer-Moore算法這類算法，適配到能做近似匹配算法。所以，接下來將要研究的，是想出一種用Boyer-Moore算近似匹配的通用算法。這將是一個令人驚訝的方法，它將允許我們使用所有我們已用過精確匹配方法，以作為解決近似匹配問題的工具。
-
高清視頻連結：http://v.qq.com/page/r/z/u/r0347njs4zu.html
原視頻連結：https://www.youtube.com/watch?v=MCvHeW13DsE&t=282s
原始碼連結：https://github.com/BenLangmead/ads1-notebooks
---
如果您有基因、測序、分子診斷方面的問題，可以到分答上來向我提問。
收費標準，目前是30元一個問題。