基因組重測序中序列比對介紹
重測序基因組數(shù)據(jù)比對，是指將測序儀下機fastq數(shù)據(jù)（NGS read序列崇众，通常100-150bp），與人類參考基因組（reference）進(jìn)行匹配，允許錯配（mismatch）签夭，插入缺失（indel），目的是在參考基因組找到序列最相似的位置椎侠，通常是基因組分析(包括 variation calling第租，ChIP-seq，RNA-seq我纪，BS-seq)流程的第一步慎宾。
常用算法
圖一
漢明距離（Hamming distance）表示兩個（相同長度）字對應(yīng)位置不同的數(shù)量，我們以d（x,y）表示兩個字x,y之間的漢明距離宣羊。對兩個字符串進(jìn)行異或運算璧诵，并統(tǒng)計結(jié)果為1的個數(shù)，那么這個數(shù)就是漢明距離仇冯。圖中read1最佳位置的方法之宿，就是通過查找最小漢明距離的實現(xiàn)的。
編輯距離（Edit distance）是針對二個字符串（例如英文字）的差異程度的量化量測苛坚，量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串比被。圖中read3最佳位置色难，通過查找最小編輯距離的方法實現(xiàn)。
圖二
全局比對（Global alignment）：全局比對是指將參與比對的兩條序列里面的所有字符進(jìn)行比對等缀。全局比對在全局范圍內(nèi)對兩條序列進(jìn)行比對打分枷莉，找出最佳比對，主要被用來尋找關(guān)系密切的序列尺迂。其可以用來鑒別或證明新序列與已知序列家族的同源性笤妙，是進(jìn)行分子進(jìn)化分析的重要前提。其代表是Needleman-Wunsch算法噪裕。圖一中蹲盘，read3使用全部比對。
局部比對（Local alignment）：與全局比對不同膳音，局部比對不必對兩個完整的序列進(jìn)行比對召衔，而是在每個序列中使用某些局部區(qū)域片段進(jìn)行比對。其產(chǎn)生的需求在于祭陷、人們發(fā)現(xiàn)有的蛋白序列雖然在序列整體上表現(xiàn)出較大的差異性苍凛，但是在某些局部區(qū)域能獨立的發(fā)揮相同的功能，序列相當(dāng)保守兵志。這時候依靠全局比對明顯不能得到這些局部相似序列的醇蝴。其次，在真核生物的基因中毒姨，內(nèi)含子片段表現(xiàn)出了極大變異性哑蔫，外顯子區(qū)域卻較為保守，這時候全局比對表現(xiàn)出了其局限性弧呐，無法找出這些局部相似性序列闸迷。其代表是Smith-Waterman局部比對算法。圖一中俘枫，read2使用局部比對腥沽。
圖三
Smith-Waterman算法介紹
Smith-Waterman是由Temple F. Smith和Michael S. Waterman于1981年提出的一種進(jìn)行局部序列比對（相對于全局比對）的算法，用于找出兩個核苷酸序列或蛋白質(zhì)序列之間的相似區(qū)域鸠蚪。該算法的目的不是進(jìn)行全序列的比對今阳，而是找出兩個序列中具有高相似度的片段。S-W算法基于動態(tài)規(guī)劃茅信，它接受任意長度盾舌、任意位置、任意序列的對齊蘸鲸，并確定是否能找到最優(yōu)的比對妖谴。
簡單地說就是，動態(tài)規(guī)劃找到問題中較小部分的解，然后把它們放在一起膝舅，形成整個問題的一個完整的最優(yōu)最終解嗡载。
它優(yōu)于BLAST和FASTA算法，因為它搜索了更大的可能性仍稀，具有更高的敏感性洼滚。
S-W算法不是一次查看整個序列，而是對多個長度的片段進(jìn)行比較技潘，尋找能夠最大化得分的片段遥巴。算法本身本質(zhì)上是遞歸的：
圖四
算法步驟如下：
-
確定置換矩陣及空位罰分方法。
如果兩個位點的堿基匹配（MATCH）崭篡，得3分挪哄，出現(xiàn)不匹配(MISMATCH)為-3分吧秕。
如果出現(xiàn)空缺（GAP）懲罰分?jǐn)?shù)做一個線性增長懲罰：W(k) = 2k (k指的是出現(xiàn)GAP的次數(shù)琉闪，初始值為2，也就是每次出現(xiàn)一個GAP懲罰的分?jǐn)?shù)依次為-2砸彬，-4颠毙，-6，遞增)砂碉。
-
初始化得分矩陣蛀蜜。
矩陣的行列同樣是是兩個序列的堿基排列，第一行和第一列為置0增蹭，這是和Needleman-Wunsch算法不同的地方滴某。
得分矩陣的長度和寬度分別為兩序列的長度+1。其首行和首列所有元素均設(shè)為0滋迈。額外的首行和首列得以讓一序列從另一序列的任意位置開始進(jìn)行比對霎奢，分值為零使其不受罰分。
-
打分饼灿。對得分矩陣的每一元素進(jìn)行從左到右幕侠、從上到下的打分，考慮匹配或錯配（對角線得分）碍彭，引入空位（水平或垂直得分）分別帶來的結(jié)果晤硕，取最高值作為該元素的分值。如果分值低于0庇忌，則該元素分值為0舞箍。打分的同時記錄下每一個分?jǐn)?shù)的來源用來回溯。
image 圖五 回溯皆疹。通過動態(tài)規(guī)劃的方法疏橄，從得分矩陣的最大分值的元素開始回溯直至分?jǐn)?shù)為0的元素。具有局部最高相似性的片段在此過程中產(chǎn)生墙基。具有第二高相似性的片段可以通過從最高相似性回溯過程之外的最高分位置開始回溯软族，即完成首次回溯之后刷喜，從首次回溯區(qū)域之外的最高分元素開始回溯，以得到第二個局部相似片段
圖六
基因組分析***** 微信公眾號推出 《50篇文章深入理解NGS》系列文章立砸， 第三篇文章 《基因組序列比對算法介紹（一）》掖疮，爭取每周更新一篇高質(zhì)量生信干貨帖子。
關(guān)注 "基因組分析" 微信公眾號颗祝，了解最新最全生信分析知識浊闪。
