序列比對(duì)與算法

關(guān)于序列比對(duì)與算法第1頁(yè)，共114頁(yè)，2023年，2月20日，星期四第一節(jié)雙序列比對(duì)第2頁(yè)，共114頁(yè)，2023年，2月20日，星期四31.序列比對(duì)基本概念2.空位罰分3.雙序列比對(duì)方法點(diǎn)陣序列比較(DotMatrixSequenceComparison)動(dòng)態(tài)規(guī)劃算法(DynamicProgrammingAlgorithm)4.記分矩陣第3頁(yè)，共114頁(yè)，2023年，2月20日，星期四41.什么是序列比對(duì)？

序列比對(duì)(SequenceAlignment)是通過(guò)在序列中搜索一系列單個(gè)性狀或性狀模式來(lái)比較2個(gè)（雙序列比對(duì)）或更多（多重序列比對(duì)）序列的方法。按比對(duì)序列條數(shù)分類雙序列比對(duì)：兩條序列的比對(duì)多序列比對(duì)：三條或以上序列的比對(duì)第4頁(yè)，共114頁(yè)，2023年，2月20日，星期四51.我們?yōu)槭裁搓P(guān)注序列比對(duì)？相似的序列可能具有相似的功能與結(jié)構(gòu)；發(fā)現(xiàn)一個(gè)基因或蛋白哪些區(qū)域容易發(fā)生突變，哪些位點(diǎn)突變后對(duì)功能沒(méi)有影響；發(fā)現(xiàn)生物進(jìn)化方面的信息。第5頁(yè)，共114頁(yè)，2023年，2月20日，星期四61.序列比對(duì)兩種類型全局序列比對(duì)定義：在全局范圍內(nèi)對(duì)兩條序列進(jìn)行比對(duì)打分的方法。適合于非常相似且長(zhǎng)度近似相等的序列。局部序列比對(duì)定義：一種尋找匹配子序列的序列比對(duì)方法。適合于一些片段相似而另一些片段相異的序列。第6頁(yè)，共114頁(yè)，2023年，2月20日，星期四71.序列比對(duì)兩種類型第7頁(yè)，共114頁(yè)，2023年，2月20日，星期四82.空位罰分(GapPenalties)空位為了獲得兩個(gè)序列最佳比對(duì)，必須使用空位和空位罰分。空位罰分分類：空位開(kāi)放罰分(Gapopeningpenalty)空位擴(kuò)展罰分(Gapextensionpenalty)最優(yōu)的序列比對(duì)通常具有以下兩下特征：盡可能多的匹配盡可能少的空位插入任意多的空位會(huì)產(chǎn)生較高的分?jǐn)?shù)，但找到的并不一定是真正相似序列。第8頁(yè)，共114頁(yè)，2023年，2月20日，星期四91GTGATAGACAC|||1GTGCATAGACAC

2.空位罰分允許空位但不罰分

不允許有空位

match=5mismatch=-41GTG-ATAGACAC|||||||||||1GTGCATAGACAC

1GTG--ATAGACAC|||||||||||1GTGC-ATAGACAC

?Score:-21Score:55第9頁(yè)，共114頁(yè)，2023年，2月20日，星期四102.空位罰分公式

ATGTTATACTATGTGCGTATA

Score=4參數(shù):匹配=1非匹配=0g=3 r=0.1 x=3

score：8-3.2=4.8

Wx=g+r(x-1)Wx: 空位總記分g: 空位開(kāi)放罰分r: 空位擴(kuò)展罰分x: 空位長(zhǎng)度TATGTGCGTATA

insertion/deletionATGT---TATACWx=3+0.1*(3-1)=3.2第10頁(yè)，共114頁(yè)，2023年，2月20日，星期四113.雙序列比對(duì)方法點(diǎn)陣序列比較(DotMatrixSequenceComparison)動(dòng)態(tài)規(guī)劃算法(DynamicProgrammingAlgorithm)詞或K串方法(WordorK-tupleMethods)第11頁(yè)，共114頁(yè)，2023年，2月20日，星期四123.1點(diǎn)陣序列比較點(diǎn)陣(DotMatrix)分析是一種簡(jiǎn)單的圖形顯示序列相似性的方法。沿X軸上序列1中的每一個(gè)單元（核苷酸或氨基酸）與沿Y軸的第二個(gè)序列中的每一個(gè)單元進(jìn)行比較，相同的區(qū)域在點(diǎn)陣圖中顯示為由點(diǎn)組成的對(duì)角線，對(duì)角線之外零散的點(diǎn)為背景噪音。第12頁(yè)，共114頁(yè)，2023年，2月20日，星期四IONIZATIONIONIZATION第13頁(yè)，共114頁(yè)，2023年，2月20日，星期四14點(diǎn)陣分析的應(yīng)用自身比對(duì)尋找序列中的正向或反向重復(fù)序列蛋白質(zhì)的重復(fù)結(jié)構(gòu)域(domain)相同殘基重復(fù)出現(xiàn)的低復(fù)雜區(qū)(LowComplexity)RNA二級(jí)結(jié)構(gòu)中的互補(bǔ)區(qū)域等對(duì)兩條序列的相似性作整體的估計(jì)第14頁(yè)，共114頁(yè)，2023年，2月20日，星期四點(diǎn)陣分析中的插入或刪除TACTGTCAT

TACTGTTCATSequence1Sequence2TACTG

-

TCAT|||||||||TACTGTTCAT插入空位第15頁(yè)，共114頁(yè)，2023年，2月20日，星期四16點(diǎn)陣分析的應(yīng)用人類低脂受體(humanlow-densitylipoproteinreceptor)自身比對(duì)發(fā)現(xiàn)正向重復(fù)序列具有連續(xù)相似區(qū)域的兩條DNA序列的簡(jiǎn)單點(diǎn)陣圖正向重復(fù)第16頁(yè)，共114頁(yè)，2023年，2月20日，星期四17點(diǎn)陣分析實(shí)例編碼噬菌體λcⅠ（水平軸）和噬菌體P22c2（垂直軸）的氨基酸序列間的點(diǎn)陣分析相同的點(diǎn)全部打印，很難找到有用的信息第17頁(yè)，共114頁(yè)，2023年，2月20日，星期四18使用滑動(dòng)窗口技術(shù)降低噪聲TACGGTATGACAGTATCTACGGTATG

ACAGTATCTACGGTATG

ACAGTATCTACGGTATG

ACAGTATCC

T

A

T

G

A

C

A

T A C G G T A T GWindow=3WordSize=3第18頁(yè)，共114頁(yè)，2023年，2月20日，星期四19ATACTACAAGACACGTACCGGCGATGCATTGAGTATCATAWindowsize=5Stringency=3Match=1Mismatch=0第19頁(yè)，共114頁(yè)，2023年，2月20日，星期四20ATACTACAAGACACGTACCGGCGATGCATTGAGTATCATAWindowsize=5Stringency=3Match=1Mismatch=0第20頁(yè)，共114頁(yè)，2023年，2月20日，星期四21ATACTACAAGACACGTACCGGCGATGCATTGAGTATCATAWindowsize=5Stringency=3Match=1Mismatch=0第21頁(yè)，共114頁(yè)，2023年，2月20日，星期四22GCGATGCATTGAGTATCATAATACTACAAGACACGTACCGWindowsize=5Stringency=3Match=1Mismatch=0第22頁(yè)，共114頁(yè)，2023年，2月20日，星期四23GCGATGCATTGAGTATCATAATACTACAAGACACGTACCG第23頁(yè)，共114頁(yè)，2023年，2月20日，星期四24GCGATGCATTGAGTATCATAATACTACAAGACACGTACCG第24頁(yè)，共114頁(yè)，2023年，2月20日，星期四使用滑動(dòng)窗口技術(shù)降低噪聲（a）對(duì)人類（Homosapiens）與黑猩猩（Pongopygmaeus）的β球蛋白基因序列進(jìn)行比較的完整點(diǎn)陣圖（b）利用滑動(dòng)窗口對(duì)以上的兩種球蛋白基因序列進(jìn)行比較的點(diǎn)陣圖，其中窗口大小為10個(gè)核苷酸，相似度閾值為8，即10個(gè)核苷酸中有8個(gè)相同時(shí)就打一個(gè)點(diǎn)ab第25頁(yè)，共114頁(yè)，2023年，2月20日，星期四26點(diǎn)陣分析的優(yōu)缺點(diǎn)優(yōu)點(diǎn)直觀性，整體性；點(diǎn)陣分析不依賴空位(gap)參數(shù)，可尋找兩序列間所有可能的殘基匹配；不依賴任何先決條件，是一種可用于初步分析的理想工具；點(diǎn)陣分析允許隨時(shí)動(dòng)態(tài)地改變最高和最低界限值，可以用來(lái)摸索區(qū)分信號(hào)和背景標(biāo)準(zhǔn)的嚴(yán)格程度。第26頁(yè)，共114頁(yè)，2023年，2月20日，星期四27點(diǎn)陣分析的優(yōu)缺點(diǎn)缺點(diǎn)不能很好地兼容打分矩陣；滑動(dòng)窗口和域值的選擇過(guò)于經(jīng)驗(yàn)化；信噪比低；不適合進(jìn)行高通量的數(shù)據(jù)分析。第27頁(yè)，共114頁(yè)，2023年，2月20日，星期四28點(diǎn)陣分析程序DNAStrider(Macintosh)/soft.htm

Dotter(Unix/Linux,X-Windows)COMPARE,DOTPLOT(GCG軟件)PLALIGN(FASTA)Dotlethttp://www.isrec.isb-sib.ch/java/dotlet/Dotlet.html第28頁(yè)，共114頁(yè)，2023年，2月20日，星期四293.2動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法(DynamicProgrammingAlgorithm)是一種計(jì)算方法，它的主要思路是把一個(gè)問(wèn)題分成若干個(gè)小問(wèn)題來(lái)解決。在生物學(xué)中應(yīng)用的兩種動(dòng)態(tài)規(guī)劃算法：Needleman-Wunsch算法（全局比對(duì)）和Smith-Waterman算法（局部比對(duì)）。第29頁(yè)，共114頁(yè)，2023年，2月20日，星期四30序列比對(duì)中某一位點(diǎn)匹配的三種可能性Eg.匹配=1,非匹配=0,空位罰分=-1Sequence1:CACGASequence2:CGA第一個(gè)位點(diǎn)得分剩余序列CC+1ACGAGA-C-1CACGAGAC--1ACGACGA第30頁(yè)，共114頁(yè)，2023年，2月20日，星期四31動(dòng)態(tài)規(guī)劃算法的數(shù)學(xué)形式Sij=max{Si-1,j-1,+s(aibj),

max

x≥1(Si-x,j-wx),

max

y≥1(Si,j-y-wy)

}Sij=max{Si-1,j-1,+s(aibj),

max

x≥1(Si-1,j-wx),max

y≥1(Si,j-1-wy)

}公式一的簡(jiǎn)化公式一公式二說(shuō)明：Sij是序列a在位置i和序列b在位置j的分值，s(aibj)是位置i和j上比對(duì)分值，wx是在序列a中長(zhǎng)度為x的間隔罰分，wy是序列b中長(zhǎng)度為y的間隔罰分第31頁(yè)，共114頁(yè)，2023年，2月20日，星期四32動(dòng)態(tài)規(guī)劃算法實(shí)例ACTTCGACTAG匹配＝3錯(cuò)配＝-1空位＝-2第32頁(yè)，共114頁(yè)，2023年，2月20日，星期四33ACTTCG0ACTAG動(dòng)態(tài)規(guī)劃算法實(shí)例匹配＝3錯(cuò)配＝-1空位＝-2第33頁(yè)，共114頁(yè)，2023年，2月20日，星期四34ACTTCG0-2ACTAG動(dòng)態(tài)規(guī)劃算法實(shí)例匹配＝3錯(cuò)配＝-1空位＝-2第34頁(yè)，共114頁(yè)，2023年，2月20日，星期四35ACTTCG0-2-4-6-8-10-12ACTAG動(dòng)態(tài)規(guī)劃算法實(shí)例匹配＝3錯(cuò)配＝-1空位＝-2第35頁(yè)，共114頁(yè)，2023年，2月20日，星期四36ACTTCG0-2-4-6-8-10-12A-2CTAG動(dòng)態(tài)規(guī)劃算法實(shí)例匹配＝3錯(cuò)配＝-1空位＝-2第36頁(yè)，共114頁(yè)，2023年，2月20日，星期四37ACTTCG0-2-4-6-8-10-12A-2C-4T-6A-8G-10動(dòng)態(tài)規(guī)劃算法實(shí)例?S(2,2)-2+(-2)-2+(-2)0+3匹配＝3錯(cuò)配＝-1空位＝-2第37頁(yè)，共114頁(yè)，2023年，2月20日，星期四38ACTTCG0-2-4-6-8-10-12A-23C-4T-6A-8G-10動(dòng)態(tài)規(guī)劃算法實(shí)例?S(2,3)-4+(-2)3+(-2)-2+(-1)匹配＝3錯(cuò)配＝-1空位＝-2第38頁(yè)，共114頁(yè)，2023年，2月20日，星期四39動(dòng)態(tài)規(guī)劃算法實(shí)例ACTTCG0-2-4-6-8-10-12A-231C-4T-6A-8G-10匹配＝3錯(cuò)配＝-1空位＝-2第39頁(yè)，共114頁(yè)，2023年，2月20日，星期四40動(dòng)態(tài)規(guī)劃算法實(shí)例ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-14?A-8-32G-10-50S(4,4)4+(-2)4+(-2)6+3匹配＝3錯(cuò)配＝-1空位＝-2第40頁(yè)，共114頁(yè)，2023年，2月20日，星期四41動(dòng)態(tài)規(guī)劃算法實(shí)例ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149A-8-32G-10-50匹配＝3錯(cuò)配＝-1空位＝-2第41頁(yè)，共114頁(yè)，2023年，2月20日，星期四ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-327864G-10-505679GGT-CATTCCAA回溯第42頁(yè)，共114頁(yè)，2023年，2月20日，星期四ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-327864G-10-505679GGT-CATTCCAA第43頁(yè)，共114頁(yè)，2023年，2月20日，星期四ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-327864G-10-505679GGTAC-TTCCAA第44頁(yè)，共114頁(yè)，2023年，2月20日，星期四45比對(duì)結(jié)果1. ACTTCG AC-TAG2. ACTTCG ACT-AG3. ACTTCG ACTA-G哪一個(gè)是最優(yōu)比對(duì)(optimalalignment)呢?記分矩陣第45頁(yè)，共114頁(yè)，2023年，2月20日，星期四46記分矩陣與空位罰分DNA計(jì)分矩陣蛋白質(zhì)計(jì)分矩陣廣泛使用的兩種矩陣

PAMBLOSUM空位罰分第46頁(yè)，共114頁(yè)，2023年，2月20日，星期四47DNA計(jì)分矩陣actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaaggacttaaagactSequence1Sequence2

A G C TA

1 0 0 0G 0 1 0 0C 0 0 1 0T 0 0 0 1匹配:1錯(cuò)配:0分值：5第47頁(yè)，共114頁(yè)，2023年，2月20日，星期四48轉(zhuǎn)換和顛換CTAG嘧啶嘌呤表示轉(zhuǎn)換(transition)，表示顛換(transversions)轉(zhuǎn)換比顛換更容易發(fā)生第48頁(yè)，共114頁(yè)，2023年，2月20日，星期四轉(zhuǎn)換和顛換AGTCA0.99G0.0060.99T0.0020.0020.99C0.0020.0020.0060.99轉(zhuǎn)換速率是顛換3倍時(shí)的模型第49頁(yè)，共114頁(yè)，2023年，2月20日，星期四蛋白質(zhì)計(jì)分矩陣PTHPLASKTQILPEDLASEDLTIPTHPLAGERAIGLARLAEEDFGMSequence1Sequence2記分矩陣T:G =-2T:T =5Score =48 C S T P A G N D

. .C 9 S -1 4T -1 1 5P -3 -1 -1 7A 0 1 0 -1 4G -3 0 -2 -2 0 6N -3 1 0 -2 -2 0 5D -3 0 -1 -1 -2 -1 1 6.. C S T P A G N D

. .C 9 S -1 4T -1 1 5P -3 -1 -1 7A 0 1 0 -1 4G -3 0 -2 -2 0 6N -3 1 0 -2 -2 0 5D -3 0 -1 -1 -2 -1 1 6..第50頁(yè)，共114頁(yè)，2023年，2月20日，星期四51PAM(PercentAcceptedMutation)矩陣氨基酸容易被其它生化、物理特性相似的氨基酸替換。PAM1(1個(gè)PAM單位）被定義為每100個(gè)殘基出現(xiàn)一個(gè)被接受的點(diǎn)突變(氨基酸的置換不引起蛋白質(zhì)功能上的顯著變化）。PAMn是PAM1自乘n次。PAM250、PAM120、PAM80和PAM60矩陣可用于相似性分別為20%、40%、50%和60%的序列比對(duì)。第51頁(yè)，共114頁(yè)，2023年，2月20日，星期四

ARNDCQEGHILKMFPSTWYVBZA2-200-2001-1-1-2-1-1-3111-6-3021R-260-1-41-1-32-2-330-400-12-4-212N0022-41102-2-31-2-3010-4-2-243D0-124-52311-2-40-3-6-100-7-4-254C-2-4-4-512-5-5-3-3-2-6-5-5-4-30-2-80-2-3-4Q0112-542-13-2-21-1-50-1-1-5-4-235E0-113-52401-2-30-2-5-100-7-4-245G1-301-3-105-2-3-4-2-3-5010-7-5-121H-1221-331-26-2-20-2-20-1-1-30-233I-1-2-2-2-2-2-2-3-252-221-2-10-5-14-1-1L-2-3-3-4-6-2-3-4-226-342-3-3-2-2-12-2-1K-1310-510-20-2-350-5-100-3-4-222M-10-2-3-5-1-2-3-224060-2-2-1-4-22-10F-3-4-3-6-4-5-5-5-212-509-5-3-307-1-3-4P100-1-30-100-2-3-1-2-5610-6-5-111S10100-101-1-1-30-2-3121-2-3-121T1-100-2-100-10-20-1-3013-5-3021W-62-4-7-8-5-7-7-3-5-2-3-40-6-2-5170-6-4-4Y-3-4-2-40-4-4-50-1-1-4-27-5-3-3010-2-2-3V0-2-2-2-2-2-2-1-242-22-1-1-10-6-2400B2145-33423-1-22-1-3122-4-2065Z1234-45513-1-120-4111-4-3056

PAM250第52頁(yè)，共114頁(yè)，2023年，2月20日，星期四

模塊替換矩陣BLOSUM以序列片段為基礎(chǔ),它是基于蛋白質(zhì)模塊(Block)數(shù)據(jù)庫(kù)而建立起來(lái)的

在模塊比對(duì)的每一列中，分別計(jì)算兩兩氨基酸的變化情況,來(lái)自所有模塊的數(shù)值被用來(lái)計(jì)算BLOSUM矩陣矩陣后面的數(shù)字表示構(gòu)建此矩陣所用的序列的相似程度，如BLOSUM62表示由相似度為62%的序列構(gòu)建AACECA-C=0A-E=-1C-E=-4A-A=4C-C=9AACECBLOSUM矩陣

(BlocksSubstitutionMatrix)

第53頁(yè)，共114頁(yè)，2023年，2月20日，星期四54BLOSUM62

第54頁(yè)，共114頁(yè)，2023年，2月20日，星期四55如何選擇合適的評(píng)分矩陣？

一般來(lái)說(shuō),在局部相似性搜索上，BLOSUM矩陣較PAM要好當(dāng)比較距離相近的蛋白時(shí)，應(yīng)選擇低的PAM或高的BLOSUM矩陣；當(dāng)比較距離較遠(yuǎn)的蛋白時(shí)，應(yīng)選擇高的PAM或低的BLOSUM矩陣。對(duì)于數(shù)據(jù)庫(kù)搜索來(lái)說(shuō)一般選擇BLOSUM62矩陣PAM矩陣可用于尋找蛋白質(zhì)的進(jìn)化起源，BLOSUM矩陣用于發(fā)現(xiàn)蛋白質(zhì)的保守域第55頁(yè)，共114頁(yè)，2023年，2月20日，星期四564.相似性與同源性同源性(HomologousGenes)：序列來(lái)自共同的祖先，相似的序列往往具有同源性。相似性(Similarity)：兩序列根據(jù)某種參數(shù)設(shè)定而表現(xiàn)出來(lái)的相近性。第56頁(yè)，共114頁(yè)，2023年，2月20日，星期四57相似性與同源性的區(qū)別相似的序列并不一定同源；相似性是可以被量化的“計(jì)分表”，它是匹配的數(shù)量除以比對(duì)的長(zhǎng)度，通常以百分比%表示；同源性一定是指序列來(lái)自共同的祖先；同源性是一個(gè)定性的概念，不能使用序列間具有百分之多少同源性來(lái)定義。第57頁(yè)，共114頁(yè)，2023年，2月20日，星期四58同源性分類直系同源(Orthologs)：具有共同祖先與相似功能的同源基因（無(wú)基因復(fù)制事件）。旁系同源(Paralogs)：兩個(gè)物種A和B的同源基因，分別是共同祖先基因組中由復(fù)制事件而產(chǎn)生的不同拷貝的后代。第58頁(yè)，共114頁(yè)，2023年，2月20日，星期四59Sothismeans…第59頁(yè)，共114頁(yè)，2023年，2月20日，星期四第二節(jié)多序列比對(duì)

(MultipleAlignments)第60頁(yè)，共114頁(yè)，2023年，2月20日，星期四尋找蛋白質(zhì)家族，識(shí)別多個(gè)序列的保守區(qū)域；相似的蛋白質(zhì)序列往往具有相似的結(jié)構(gòu)與功能；輔助預(yù)測(cè)新序列的二級(jí)或三級(jí)結(jié)構(gòu)；可以直觀地看到基因的哪些區(qū)域?qū)ν蛔兠舾?；PCR引物設(shè)計(jì)；我們?yōu)槭裁醋龆嘈蛄斜葘?duì)?第61頁(yè)，共114頁(yè)，2023年，2月20日，星期四分析多個(gè)序列的一致序列；用于進(jìn)化分析，是用系統(tǒng)發(fā)育方法構(gòu)建進(jìn)化樹(shù)的初使步驟；尋找個(gè)體之間單核苷酸多態(tài)性(SNPs)；通過(guò)序列比對(duì)發(fā)現(xiàn)直系同源(Orthologs)與旁系同源(Paralogs)基因；尋找同源基因(相似的序列往往具有同源性)。我們?yōu)槭裁醋龆嘈蛄斜葘?duì)?第62頁(yè)，共114頁(yè)，2023年，2月20日，星期四多序列比對(duì)與進(jìn)化研究例子圖中NYLS為樹(shù)根第63頁(yè)，共114頁(yè)，2023年，2月20日，星期四一個(gè)多序列比對(duì)例子VTISCTGSSSNIGAG-NHVKWYQQLPGVTISCTGTSSNIGS--ITVNWYQQLPGLRLSCSSSGFIFSS--YAMYWVRQAPGLSLTCTVSGTSFDD--YYSTWVRQPPGPEVTCVVVDVSHEDPQVKFNWYVDG--ATLVCLISDFYPGA--VTVAWKADS--AALGCLVKDYFPEP--VTVSWNSG---VSLTCLVKGFYPSD--IAVEWWSNG--第64頁(yè)，共114頁(yè)，2023年，2月20日，星期四多序列比對(duì)方法全局序列比對(duì)動(dòng)態(tài)規(guī)劃算法

(DynamicProgrammingAlgorithm)分而治之方法

(DivideandConquerMethods)SP方法

(SumofPairsMethods)

累進(jìn)方法

(ProgressiveMethods)迭代方法

(IterativeMethods)局部序列比對(duì)概形分析

(ProfileAnalysis)區(qū)塊分析

(BlockAnalysis)統(tǒng)計(jì)學(xué)方法

(StatisticalMethods）第65頁(yè)，共114頁(yè)，2023年，2月20日，星期四在多序列比對(duì)前要考慮的問(wèn)題比對(duì)的優(yōu)劣與序列條數(shù)正相關(guān)每個(gè)亞群應(yīng)分別先比對(duì)，然后再整體比對(duì)第66頁(yè)，共114頁(yè)，2023年，2月20日，星期四一、全局序列比對(duì)

動(dòng)態(tài)規(guī)劃算法

(DynamicProgrammingAlgorithm)分而治之方法

(DivideandConquerMethods)SP方法

(SumofPairsMethods)

累進(jìn)方法

(ProgressiveMethods)迭代方法

(IterativeMethods)遺傳算法

(GeneticAlgorithms)第67頁(yè)，共114頁(yè)，2023年，2月20日，星期四序列長(zhǎng)度為n

的雙序列比對(duì)n2

比對(duì)比對(duì)數(shù)目成指數(shù)增長(zhǎng)例如：序列長(zhǎng)度為n，序列數(shù)為N

的多序列比對(duì)數(shù)目是nN對(duì)于數(shù)目較少且較短的序列來(lái)說(shuō)都不切實(shí)際1.動(dòng)態(tài)規(guī)劃算法(DynamicProgramming)第68頁(yè)，共114頁(yè)，2023年，2月20日，星期四Sequence1Sequence2Sequence3多維的動(dòng)態(tài)規(guī)劃算法第69頁(yè)，共114頁(yè)，2023年，2月20日，星期四分而治之

(DivideandConquer,DCA)方法將MSA（MeasurementSystemAnalysis）的空間復(fù)雜度減小DCA在線MSAhttp://bioweb.pasteur.fr/seqanal/interfaces/dca-simple.html

2.分而治之方法第70頁(yè)，共114頁(yè)，2023年，2月20日，星期四Soineffect…Sequence1Sequence2Sequence3第71頁(yè)，共114頁(yè)，2023年，2月20日，星期四3.SP(SumofPairs)方法為了找到最佳比對(duì)，并解決動(dòng)態(tài)規(guī)則算法的計(jì)算復(fù)雜問(wèn)題，Carrillo&Lipman(1988)發(fā)明了SP(SumofPairs)方法SP方法通過(guò)對(duì)一個(gè)隨機(jī)數(shù)據(jù)矩陣中氨基酸對(duì)的所有可能組合的記分求和來(lái)獲得矩陣記分第72頁(yè)，共114頁(yè)，2023年，2月20日，星期四4.累進(jìn)算法(ProgressiveMethods)針對(duì)基于動(dòng)態(tài)規(guī)劃算法的MSA程序比對(duì)序列數(shù)目有限，F(xiàn)eng&Doolittle(1987)發(fā)明了累進(jìn)算法CLUSTAL和PILEUP是目前常用的基于累進(jìn)算法的比對(duì)軟件CLUSTAL是免費(fèi)軟件,目前應(yīng)用非常廣泛

http://www-igbmc.u-strasbg.fr/BioInfo/ClustalX/Top.html第73頁(yè)，共114頁(yè)，2023年，2月20日，星期四1對(duì)所有序列做雙序列比對(duì)，構(gòu)建距離矩陣計(jì)算相似性分?jǐn)?shù)值2基于雙序列距離矩陣，構(gòu)建一個(gè)進(jìn)化樹(shù)

Scer

Cele

Dmel

Mouse

Human3依據(jù)進(jìn)化樹(shù)進(jìn)行漸進(jìn)比對(duì)

?依據(jù)進(jìn)化樹(shù)，開(kāi)始對(duì)關(guān)系較近的序列進(jìn)行兩兩比對(duì)

?逐漸加入關(guān)系較遠(yuǎn)的序列進(jìn)行比對(duì)

?構(gòu)建多序列比對(duì)MultiplealignmentScerevisiae[1]Celegans[2]0.640Drosophia[3]0.6340.327Human[4]0.6300.4080.420Mouse[5]0.6190.4050.4690.289累進(jìn)算法原理第74頁(yè)，共114頁(yè)，2023年，2月20日，星期四一般累進(jìn)比對(duì)方法132513131325254droot第75頁(yè)，共114頁(yè)，2023年，2月20日，星期四果仁糖累進(jìn)方法

(Pralineprogressivestrategy)13213131325254d4第76頁(yè)，共114頁(yè)，2023年，2月20日，星期四累進(jìn)算法的一些問(wèn)題比對(duì)的準(zhǔn)確性高度依賴于開(kāi)始選擇的雙序列比對(duì)序列關(guān)系越遠(yuǎn)發(fā)生的錯(cuò)誤可能越高選擇合適的打分矩陣和罰分準(zhǔn)則較困難第77頁(yè)，共114頁(yè)，2023年，2月20日，星期四ClLUSTALW/X簡(jiǎn)介ClLUSTAL最初初由Higgins等于1988年創(chuàng)立并不斷完善用來(lái)多序列比對(duì)、概形(Profile)分析和創(chuàng)建進(jìn)化樹(shù)ClLUSTAL分為ClLUSTALW和CLUSTALX兩種類型ClLUSTAL有用于WINDOWS和UNIX/LINUX的各種版本第78頁(yè)，共114頁(yè)，2023年，2月20日，星期四CLUSTAL方法進(jìn)行所有序列間的雙序列比對(duì)基于雙序列比對(duì)分?jǐn)?shù)產(chǎn)生一個(gè)相鄰連接進(jìn)化樹(shù)(neighbor-jointree)根據(jù)進(jìn)化樹(shù)提供的序列間關(guān)系按順序?qū)π蛄羞M(jìn)行比對(duì)比對(duì)可以用以下兩種方法：-slow/accurate-fast/approximate第79頁(yè)，共114頁(yè)，2023年，2月20日，星期四********CLUSTALW(1.8)MultipleSequenceAlignments********

1.SequenceInputFromDisc2.MultipleAlignments3.Profile/StructureAlignments

4.PhylogenetictreesS.ExecuteasystemcommandH.HELPX.EXIT(leaveprogram)Yourchoice:1<rtn>CLUSTALW第80頁(yè)，共114頁(yè)，2023年，2月20日，星期四Sequencesshouldallbein1file.7formatsaccepted:NBRF/PIR,EMBL/SwissProt,Pearson(Fasta),GDE,Clustal,GCG/MSF,RSF.Enterthenameofthesequencefile:anti.fasta<rtn>SequenceformatisPearsonSequencesassumedtobePROTEINSequence1:ANP4_PSEAM 85aaSequence2:ANP_LIMFE 97aaSequence3:ANPA_PSEAM 82aaSequence4:ANPX_PSEAM 91aaSequence5:ANPY_PSEAM 91aa

CLUSTALW第81頁(yè)，共114頁(yè)，2023年，2月20日，星期四********CLUSTALW(1.8)MultipleSequenceAlignments********1.SequenceInputFromDisc2.MultipleAlignments3.Profile/StructureAlignments4.PhylogenetictreesS.ExecuteasystemcommandH.HELPX.EXIT(leaveprogram)Yourchoice:2<rtn>

CLUSTALW第82頁(yè)，共114頁(yè)，2023年，2月20日，星期四Clustal

W*********************MULTIPLEALIGNMENTMENU******

***************1.Docompletemultiplealignmentnow(Slow/Accurate)2.Produceguidetreefileonly3.Doalignmentusingoldguidetreefile4.ToggleSlow/Fastpairwisealignments=SLOW5.Pairwisealignmentparameters6.Multiplealignmentparameters7.Resetgapsbetweenalignments?=OFF8.Togglescreendisplay=ON9.OutputformatoptionsS.ExecuteasystemcommandH.HELPorpress[RETURN]togobacktomainmenuYourchoice:1<rtn>第83頁(yè)，共114頁(yè)，2023年，2月20日，星期四EnteranamefortheCLUSTALoutputfile[anti.aln]:<rtn>

EnternamefornewGUIDETREEfile[anti.dnd]:<rtn>StartofPairwisealignmentsAligning...Sequences(1:2)Aligned.Score:62Sequences(1:3)Aligned.Score:59Sequences(1:4)Aligned.Score:84Sequences(1:5)Aligned.Score:83Sequences(2:3)Aligned.Score:68Sequences(2:4)Aligned.Score:80Sequences(2:5)Aligned.Score:79Sequences(3:4)Aligned.Score:81Sequences(3:5)Aligned.Score:80Sequences(4:5)Aligned.Score:98Guidetreefilecreated:[anti.dnd]StartofMultipleAlignmentThereare4groupsAligning...Group1:Sequences:2Score:1476Group2:Sequences:3Score:1499Group3:Sequences:4Score:1190Group4:Sequences:5Score:1404AlignmentScore3470Consensuslength=102CLUSTAL-Alignmentfilecreated[anti.aln]

第84頁(yè)，共114頁(yè)，2023年，2月20日，星期四MacVector界面的ClustalW第85頁(yè)，共114頁(yè)，2023年，2月20日，星期四Clustal

X介紹第86頁(yè)，共114頁(yè)，2023年，2月20日，星期四ClustalX介紹第87頁(yè)，共114頁(yè)，2023年，2月20日，星期四ClustalX介紹第88頁(yè)，共114頁(yè)，2023年，2月20日，星期四ClustalX介紹第89頁(yè)，共114頁(yè)，2023年，2月20日，星期四ClustalX介紹第90頁(yè)，共114頁(yè)，2023年，2月20日，星期四ExampleMultiplesequencealignmentof7neuroglobinsusingclustalx第91頁(yè)，共114頁(yè)，2023年，2月20日，星期四PILEUPPILEUP是GCG(GeneticsComputerGroup)軟件包中的MSA分析工具；與CLUSTAL一樣使用累進(jìn)式整體比對(duì)方法(ProgressiveGlobalAlignment)；PILEUP開(kāi)始的雙序列比對(duì)使用Needleman-Wunsch動(dòng)態(tài)規(guī)劃算法，所以是全局序列比對(duì)，善于比較相似度較高的序列。第92頁(yè)，共114頁(yè)，2023年，2月20日，星期四OutputofPileup

401

OATNFA1TTCAG......ACACTCAGGTCATCTTCTCAAGCOATNFARTTCAG......ACACTCAGGTCATCTTCTCAAGCBSPTNFATTCAA......ACACTCAGGTCCTCTTCTCAAGCCEU14683TTCAG......ACCCTCAGGTCATCTTCTCAAGCHSTNFRCCCAG......GCAGTCAGATCATCTTCTCGAACSYNTNFTRPCCCAG......GCAGTCAGATCATCTTCTCGAACCATTNFAACCCAG......ACACTCAGATCATCTTCTCGAACCFTNFATCCAG......ACAGTCAAATCATCTTCTCGAACRABTNFMCCCAGATGGTCACCCTCAGATCAGCTTCTCGGGCRNTNFAACCCAGACCCTCACACTCAGATCATCTTCTCAAAA第93頁(yè)，共114頁(yè)，2023年，2月20日，星期四OutputofPileup第94頁(yè)，共114頁(yè)，2023年，2月20日，星期四ClUSTAL和PILEUP存在的問(wèn)題最終的比對(duì)結(jié)果取決于最初的雙序列比對(duì)，起初的序列相似度越高比對(duì)越準(zhǔn)確；如果比對(duì)序列間長(zhǎng)度差異較大則會(huì)生成異常的引導(dǎo)樹(shù)(guidetrees)從而嚴(yán)重影響多序列比對(duì)；所選的記分與罰分標(biāo)準(zhǔn)并不一定適合一組序列中的所有序列。第95頁(yè)，共114頁(yè)，2023年，2月20日，星期四對(duì)累進(jìn)比對(duì)方法的改進(jìn)迭代方法策略在比對(duì)過(guò)程中不斷重新比對(duì)各亞組序列把亞組序列再排成包括所有序列在內(nèi)的整體比對(duì)獲得最優(yōu)的總比對(duì)分?jǐn)?shù)（由成對(duì)比對(duì)分?jǐn)?shù)相加而成）5.迭代方法

(IterativeMethods)第96頁(yè)，共114頁(yè)，2023年，2月20日，星期四二、局部序列比對(duì)局部比對(duì)(LocalAlignment)方法能夠確定序列中高度保守的區(qū)域。概形分析(ProfileAnalysis)區(qū)塊分析(BlockAnalysis)第97頁(yè)，共114頁(yè)，2023年，2月20日，星期四1.概形分析

(ProfileAnalysis)通過(guò)對(duì)一組序列進(jìn)行整體MSA分析，把其中高度保守的區(qū)域提出分成小的MSA。這些小的MSA根據(jù)其序列與結(jié)構(gòu)的比對(duì)得到一個(gè)記分矩陣。根據(jù)這個(gè)矩陣列出每個(gè)位置上的殘基分?jǐn)?shù)，稱為位置特異記分表(PositionSpecificScoringTable)或概形(Profile)。概形(Profile)類似于一個(gè)小的MSA，包括匹配、錯(cuò)配、插入和缺失。第98頁(yè)，共114頁(yè)，2023年，2月20日，星期四概形分析

(ProfileAnalysis)優(yōu)勢(shì)：用來(lái)尋找一個(gè)可能與之匹配的目標(biāo)序列；用來(lái)在一個(gè)數(shù)據(jù)庫(kù)中搜索一個(gè)可能的新的蛋白(pfsearch)；通過(guò)搜索一個(gè)profile數(shù)據(jù)庫(kù)來(lái)找到提交的序列屬于哪一家族(pfscan)；比對(duì)兩個(gè)MSA(profiletoprofile)。缺點(diǎn)：所產(chǎn)生的概形僅僅代表MSA本身的序列族變異，如果MSA中的幾個(gè)序列相似，則衍生的概形將偏向于這些序列。

第99頁(yè)，共114頁(yè)，2023年，2月20日，星期四不同物種HSP70蛋白的profile圖左邊第一列為一致序列(consensussequence),其余的行的數(shù)值表示一致序列中每一個(gè)氨基酸出現(xiàn)的頻率的對(duì)數(shù)與隨機(jī)頻率對(duì)數(shù)的比值，如出現(xiàn)空位，則必須減去空位行在相應(yīng)位置上的數(shù)值。如用其尋找一個(gè)長(zhǎng)度為100aa的序列，則檢查的串為1~10,2~11,…，最高記分區(qū)段將是概形最相似部分。圖中Z表示谷氨酸or谷氨酰胺;B表示天