在生物信息學(xué)研究中连锯，序列比對是一個(gè)非常基礎(chǔ)的問題用狱，在很多研究中都會用到运怖。主要幾種算法包括全局比對算法（Needleman-Wunsch算法），局部比對算法（Smith-Waterman 算法）夏伊，Blast等摇展。開展一個(gè)課題時(shí)難免要構(gòu)建克隆，尋找同源蛋白等署海，那當(dāng)你在使用 NTI , MEGA 等進(jìn)行比對時(shí)吗购，你了解過序列比對的原理嗎？
序列比對基本原理
-
輸入數(shù)據(jù)
—— 序列 seq1砸狞，seq2捻勉，seq[n]
根據(jù)打分表打分
輸出結(jié)果，選擇最優(yōu)比對
序列比對方法
枚舉
進(jìn)行序列比對最簡單的辦法就是自行對給定序列進(jìn)行多種排列組合
比如有兩條序列 seq1：LSPADK seq2：LTPEDK
這兩條序列比對時(shí)會產(chǎn)生多種可能刀森，如：
我們可以看到當(dāng)序列比較短時(shí)我們確實(shí)能夠一一列舉得到最優(yōu)的比對結(jié)果踱启，但是當(dāng)序列長度為300甚至更長時(shí)怎么辦？
總結(jié)比對的規(guī)律，其實(shí)一對殘基之間只有三種比對可能埠偿，比對上或比對到空位透罢，如 T,S
S S -
T - T
由此就產(chǎn)生了動態(tài)規(guī)劃算法，其實(shí)就是先得到局部最優(yōu)比對冠蒋，最后得到全局最優(yōu)比對羽圃，也就是 好的+好的=最好的
Needleman-Wunsch 算法 - 基于動態(tài)規(guī)劃的序列全局比對
Needleman-Wunsch算法是序列全局比對的核心算法，會將給定的兩條序列從頭到尾進(jìn)行比對
概念：打分表
對于不完全匹配的序列抖剿，會存在空位或者不匹配的位點(diǎn)朽寞，打分表是表示一種氨基酸（或核苷酸）變?yōu)榱硗庖环N氨基酸（核苷酸）的打分，對于空位則要罰分斩郎，最終綜合所有位點(diǎn)的打分結(jié)果脑融，獲得兩個(gè)序列的匹配分值，分值越高的表示兩個(gè)序列相似度越高
對于蛋白質(zhì)序列缩宜，常用的打分表有PAM250和BLOSUM62肘迎，其中PAM250是基于高同源序列構(gòu)建，BLOSUM62基于遠(yuǎn)程同源序列構(gòu)建锻煌，因此尋找遠(yuǎn)程同源序列一般用BLOSUM62
計(jì)算步驟
以核苷酸序列為例妓布，核酸序列共四種堿基ATCG
-
定義打分表
A C G T A 2 -7 -5 -7 C -7 2 -7 -5 G -5 -7 2 -7 T -7 -5 -7 2 指A比對到A分?jǐn)?shù)為2，A比對到C分?jǐn)?shù)為-5炼幔，A比對到空位為 -5秋茫，如以下一種比對組合：
GAC-AT
C-ACAT分?jǐn)?shù)依次為：(-7)+(-5)+(-7)+(-5)+(2)+(2) = -20
當(dāng)序列長度過長時(shí)計(jì)算量很大，為了不一個(gè)個(gè)進(jìn)行計(jì)算乃秀，就有了隨后的打分規(guī)則
-
打分規(guī)則
圖2
-
打分結(jié)果
根據(jù)不同組合得到不同的打分結(jié)果肛著，分?jǐn)?shù)最高的則為最優(yōu)比對結(jié)果
Smith-Waterman 算法 - 基于動態(tài)規(guī)劃的序列局部比對
但是隨著越來越多的蛋白序列被測定，研究人員發(fā)現(xiàn)功能相關(guān)的蛋白之間雖然整體序列上相差甚遠(yuǎn)跺讯，卻常常具有相同的功能域枢贿，這些序列片段能夠獨(dú)立發(fā)揮特定的生物學(xué)功能，在不同蛋白之間相當(dāng)保守（如圖中的 SR 功能域）刀脏，這僅靠全局比對是無法發(fā)現(xiàn)這些片段的局荚。由此就出現(xiàn)了局部比對算法，相比于全局比對愈污，局部比對算法是基于全局比對的打分規(guī)則表增加了一個(gè)下限 0
參考：http://www.chinesemooc.org/live/875136
微信公眾號：生信自修室
