中國科技大學(xué)課件系列：《生物信息學(xué)》04學(xué)習(xí)資料

生物(shēngwù)信息學(xué)第三章序列(xùliè)比對(duì)Ⅱ第一頁，共72頁。本章(běnzhānɡ)內(nèi)容提要第一節(jié)：數(shù)學(xué)基礎(chǔ)：概率及概率模型第二節(jié)：雙序列比對(duì)算法的介紹Dotmatrix動(dòng)態(tài)(dòngtài)規(guī)劃算法(Needleman-Wunsch,Smith-Waterman算法)FASTA和BLAST算法第三節(jié)：打分矩陣及其含義第四節(jié)：多序列比對(duì)第二頁，共72頁。第三節(jié)打分矩陣(jǔzhèn)及其含義1，計(jì)分(jìfēn)方法2，Dayhoff:PAM系列矩陣3，Henikoff:BLOSUM系列矩陣第三頁，共72頁。1，計(jì)分(jìfēn)方法匹配計(jì)分：UM矩陣(Unitarymatrix) 相同的氨基酸記1分，否則(fǒuzé)記0分。BLAST中核酸比對(duì)結(jié)構(gòu)域性質(zhì)計(jì)分：SGM矩陣(Structure-GeneticMatrix) 主要根據(jù)氨基酸的結(jié)構(gòu)和化學(xué)性質(zhì)的相似程度來記分(如D和E，S和T，V和I有很高的相似性)，同時(shí)還考慮密碼子之間相互轉(zhuǎn)換的難易程度?？捎^測(cè)變換計(jì)分：PAM矩陣(PointAcceptedMutation)BLOSUM矩陣(BLOcksSUbstitutionMatrix)第四頁，共72頁。2，PAM系列(xìliè)矩陣MargaretDayhoff,1978;通過對(duì)物種進(jìn)化的研究，根據(jù)一種氨基酸被另一種氨基酸替代(tìdài)的頻度而提出的，最常用的是PAM250;Acceptedpointmutation(PAM):可接受的點(diǎn)突變，氨基酸的改變不顯著影響蛋白質(zhì)的功能；第五頁，共72頁。PAM矩陣(jǔzhèn)71個(gè)蛋白質(zhì)家族的1572種變化(biànhuà)；序列相似性>85%；功能同源的蛋白質(zhì)通過中性進(jìn)化(jìnhuà)，引入可接受的點(diǎn)突變；進(jìn)化(jìnhuà)模型：A.基本假設(shè)：中性進(jìn)化(jìnhuà)，Kimura,1968;B.進(jìn)化(jìnhuà)的對(duì)稱性:A->B=B->A;C.擴(kuò)展性：通過對(duì)較短時(shí)間內(nèi)氨基酸替代關(guān)系的計(jì)算來計(jì)算較長(zhǎng)時(shí)間的氨基酸替代關(guān)系；第六頁，共72頁。PAM1矩陣(jǔzhèn)兩個(gè)蛋白質(zhì)序列(xùliè)的~1%氨基酸發(fā)生變化；定義進(jìn)化時(shí)間以氨基酸的變異比例為準(zhǔn)，而不是時(shí)間；因?yàn)楦鱾€(gè)蛋白質(zhì)家族進(jìn)化的速度并不相等；PAM2=PAM1*PAM1PAM3=(PAM1)3PAM250=(PAM1)250第七頁，共72頁。PAMn矩陣(jǔzhèn)的構(gòu)建選取多個(gè)家族的相似性>85%的保守序列；根據(jù)匹配計(jì)分進(jìn)行多重比對(duì)(不含空位)；以比對(duì)結(jié)果構(gòu)建進(jìn)化樹，反映氨基酸替換(tìhuàn)關(guān)系；計(jì)算每種氨基酸轉(zhuǎn)換成其它氨基酸的次數(shù)；計(jì)算每種氨基酸突變率；計(jì)算每對(duì)氨基酸突變率，得到突變概率矩陣，將此矩陣自乘n次；將突變概率矩陣轉(zhuǎn)化為PAMn矩陣。第八頁，共72頁。例6：PAM矩陣(jǔzhèn)的構(gòu)建已知3個(gè)蛋白質(zhì)家族若干保守序列片段(piànduàn)：家族一：FKILK，F(xiàn)KIKK，F(xiàn)FILL，F(xiàn)FIKL家族二：IIFFF，IIFIF，IKFFL，IKFIL家族三：KIFKK，KIFLK，KLFKL，KLFLL按Doyhoff方法構(gòu)建PAM1與PAM2矩陣第九頁，共72頁。Step1：多重比對(duì)位置對(duì)齊，多重比對(duì)（不考慮空位）：統(tǒng)計(jì)(tǒngjì)每種氨基酸出現(xiàn)的頻率； fi=氨基酸i的數(shù)目/總氨基酸數(shù)目fL=12/60=0.2..家族一家族二家族三FKILKIIFFFKIFKKFKIKKIIFIFKIFLKFFILLIKFFLKLFKLFFIKLIKFILKLFLL第十頁，共72頁。Step2：構(gòu)建(ɡòujiàn)進(jìn)化樹最大簡(jiǎn)約法家族一:L和K間相互(xiānghù)轉(zhuǎn)換次數(shù)：N(LK)=3家族二，家族三…FKILKFKIKKFKIKKFFIKLFFILLFFIKL(LK)(KF)(LK)(LK)第十一頁，共72頁。Step3：計(jì)算氨基酸間的轉(zhuǎn)換(zhuǎnhuàn)次數(shù)計(jì)算每種氨基酸轉(zhuǎn)換成其它氨基酸的次數(shù)(cìshù)。假設(shè)兩種氨基酸間相互轉(zhuǎn)換一樣。e.g.N(LK)=3+0+3=6KFILK116F121I121L611第十二頁，共72頁。Step4：計(jì)算(jìsuàn)各氨基酸相對(duì)突變率每種氨基酸相對(duì)(xiāngduì)突變率mii：第i種氨基酸；fi：每種氨基酸出現(xiàn)的頻率；mK=8/(12×2×fK×100)=0.0125…第十三頁，共72頁。Step5：計(jì)算(jìsuàn)氨基酸i替換為j的突變率氨基酸i替換(tìhuàn)為j的突變率mije.g.mKK=1-mK=0.9875mKF=mF×1/4=0.001389…第十四頁，共72頁。Step5：氨基酸一步(yībù)轉(zhuǎn)移概率矩陣氨基酸突變概率——一步轉(zhuǎn)移(zhuǎnyí)概率矩陣M1ij原氨基酸KFIL替換氨基酸K0.98750.0015630.0015630.009375F0.0013890.9944440.0027780.001389I0.0017860.0035710.9928570.001786L0.01250.0020830.0020830.983333第十五頁，共72頁。Step6:計(jì)算(jìsuàn)PAM1計(jì)分矩陣由突變率mij計(jì)算計(jì)分(jìfēn)矩陣中的分值rij：將rij=rji取平均值，再取整數(shù)； （按先前假設(shè)，rij=rji）rKK=10lg(mkk/fk)=5.6857≈6(rKF+rFK)/2=-22.833≈-23…第十六頁，共72頁。Step6:PAM1計(jì)分(jìfēn)矩陣結(jié)果三個(gè)家族序列片段得到(dédào)的PAM1計(jì)分矩陣：KFILK6F-235I-22-196L-13-22-207第十七頁，共72頁。Step7:計(jì)算(jìsuàn)PAM2計(jì)分矩陣將氨基酸突變(tūbiàn)概率矩陣自乘一次，得到兩步轉(zhuǎn)移概率矩陣M2ijM2ij=M1ij×M1ij三個(gè)家族序列片段得到的PAM2計(jì)分矩陣：KFILK6F-205I-19-166L-10-19-187第十八頁，共72頁。PAM250矩陣(jǔzhèn)PAM250:250%期望的突變(tūbiàn)；蛋白質(zhì)序列仍然有15-30%左右的相似性；第十九頁，共72頁。PAM250打分(dǎfēn)矩陣第二十頁，共72頁。打分(dǎfēn)矩陣的使用PAM250:~15-30%的序列(xùliè)相似性；PAM120:~40%的序列(xùliè)相似性；PAM80:~50%PAM60:~60%如何選擇最合適的矩陣？多種嘗試…第二十一頁，共72頁。PAM矩陣(jǔzhèn)的問題及改進(jìn)1.PAM系列矩陣存在的問題：A.氨基酸的打分矩陣，不關(guān)心(guān〃xīn)核酸；B.進(jìn)化模型的構(gòu)建需要系統(tǒng)發(fā)育樹的分析，因此，成為一個(gè)循環(huán)論證的問題：序列比對(duì)矩陣構(gòu)建打分進(jìn)行新的序列比對(duì)；C.數(shù)據(jù)集很小；2.打分矩陣的改進(jìn)A.選用大量的序列數(shù)據(jù)，構(gòu)建PAM矩陣；B.BLOSUM系列矩陣;C.核酸的打分矩陣;第二十二頁，共72頁。3，BLOSUM矩陣(jǔzhèn)最被廣泛使用的氨基酸打分矩陣;根據(jù)蛋白質(zhì)模塊數(shù)據(jù)庫BLOCKS中蛋白質(zhì)序列的高度保守部分(bùfen)的比對(duì)而得到的，最常用的是BLOSUM62;BLOCK:蛋白質(zhì)家族保守的一段氨基酸，無gap，一般幾個(gè)至上百個(gè)氨基酸；Prosite家族：至少有一個(gè)BLOCK存在于該家族的所有蛋白質(zhì)序列中；BLOSUM62:序列的平均相似性為62%的BLOCK構(gòu)建的打分矩陣；第二十三頁，共72頁。BLOSUM62矩陣(jǔzhèn)構(gòu)建步驟：提取Prosite數(shù)據(jù)庫中504個(gè)家族的2萬多蛋白質(zhì)序列，合并(hébìng)其中相似性≥62%的序列；統(tǒng)計(jì)各BLOCK的氨基酸對(duì)數(shù)量f；計(jì)算氨基酸對(duì)的出現(xiàn)頻率q；計(jì)算每種氨基酸的期望頻率p；計(jì)算氨基酸對(duì)出現(xiàn)的期望頻率e；計(jì)算BLOSUM62矩陣分量rij第二十四頁，共72頁。BLOSUM62打分(dǎfēn)矩陣第二十五頁，共72頁。BLOSUM&PAM序列(xùliè)相似性與PAM及BLOSUM矩陣的大致對(duì)應(yīng)關(guān)系：序列相似性%999080706050403020PAM數(shù)值11123385680112159246BLOSUM數(shù)值908062-45第二十六頁，共72頁。第四節(jié)，多序列(xùliè)比對(duì)不同物種中，許多基因的功能保守，序列相似性較高，通過多條序列的比較，發(fā)現(xiàn)保守與變異(biànyì)的部分；可構(gòu)建HMM模型，搜索更多的同源序列；構(gòu)建進(jìn)化的樹的必須步驟；比較基因組學(xué)研究；兩類：全局或局部的多序列比對(duì)；第二十七頁，共72頁。全局性的多序列(xùliè)比對(duì)MadebyGENEDOC第二十八頁，共72頁。雙序列(xùliè)比對(duì)GapVDSCYGap0-11-22-33-44-55V-114-7-18-29-40E-22-76-5-16-27S-33-18-510-1-12L-44-29-16-19-3C-55-40-27-1287Y-66-51-38-23-31542時(shí)間(shíjiān)復(fù)雜度：O(n2)第二十九頁，共72頁。多序列(xùliè)比對(duì)：最優(yōu)算法三條(sāntiáo)序列：時(shí)間復(fù)雜度：O(lmn)=O(n3)四條序列(xùliè)：時(shí)間復(fù)雜度：O(n4)，非多項(xiàng)式時(shí)間！多項(xiàng)式時(shí)間復(fù)雜度要求：≤O(n3)m條序列：時(shí)間復(fù)雜度：O(nm)，NPC問題！…第三十頁，共72頁。動(dòng)態(tài)規(guī)劃(guīhuà)算法：全空間第三十一頁，共72頁。動(dòng)態(tài)(dòngtài)規(guī)劃算法：優(yōu)化算法SequenceASequenceBSequenceC

搜索有限空間，類似于BLAST算法第三十二頁，共72頁。動(dòng)態(tài)規(guī)劃(guīhuà)算法：Hyperlattice第三十三頁，共72頁。注意(zhùyì)最優(yōu)的多序列(xùliè)比對(duì)，其兩兩序列(xùliè)之間的比對(duì)不一定最優(yōu)。最優(yōu)的多序列(xùliè)比對(duì)非最優(yōu)的雙序列比對(duì)第三十四頁，共72頁。MSA程序(chéngxù)MSA-MultipleSequenceAlignmentDavidLipman等，1989年初始開發(fā)；應(yīng)用(yìngyòng)多維動(dòng)態(tài)規(guī)劃算法，得到最優(yōu)的全局比對(duì)。工具資源：/CBBresearch/Schaffer/msa.html/general/software/packages/msa/manual/manual.php第三十五頁，共72頁。MSA：

打分(dǎfēn)方式第三十六頁，共72頁。多序列比對(duì)：方法(fāngfǎ)改進(jìn)1.漸進(jìn)方法：progressivemethods代表：ClustalW/X,T-Coffee2.迭代方法：iterativemethods代表:PRRP,DIALIGN3.部分有向圖算法(suànfǎ)：PartialOrderAlgorithm(POA)4.全局多序列比對(duì)的隱馬爾科夫模型profileHMM5.整合算法(suànfǎ)：MUSCLE第三十七頁，共72頁。1.Progressivemethods(1)ClustalW/X(2)T-Coffee第三十八頁，共72頁。(1)ClustalW/X1.Clustal:1988年開發(fā)；2.ClustalW:1994年，JulieD.Thompson等人改進(jìn)(gǎijìn)、發(fā)展；3.ClustalX:1997年，圖形化軟件；第三十九頁，共72頁。ClustalW/X：計(jì)算(jìsuàn)過程1.將所有(suǒyǒu)序列兩兩比對(duì)，計(jì)算距離矩陣；2.構(gòu)建鄰接進(jìn)化樹(neighbor-joiningtree)/指導(dǎo)樹(guidetree)；3.將距離最近的兩條序列用動(dòng)態(tài)規(guī)劃的算法進(jìn)行比對(duì)；4.“漸進(jìn)”的加上其他的序列。第四十頁，共72頁。兩兩比對(duì)，構(gòu)建(ɡòujiàn)距離矩陣指導(dǎo)(zhǐdǎo)樹的構(gòu)建漸進(jìn)(jiànjìn)比對(duì)第四十一頁，共72頁。ClustalW的打分(dǎfēn)原則每條序列(xùliè)的權(quán)值Score:BLOSUM62的分?jǐn)?shù)(fēnshù)第四十二頁，共72頁。ClustalX的使用(shǐyòng)1.FASTA序列(xùliè)格式，多序列(xùliè)：第四十三頁，共72頁。ClustalX的使用

——導(dǎo)入序列(xùliè)文件第四十四頁，共72頁。執(zhí)行(zhíxíng)比對(duì)第四十五頁，共72頁。文件(wénjiàn)導(dǎo)出第四十六頁，共72頁。多序列(xùliè)比對(duì)：結(jié)果處理BioEdit,GeneDoc等軟件(ruǎnjiàn)GeneDoc軟件(ruǎnjiàn)，導(dǎo)入.aln文件第四十七頁，共72頁。選擇(xuǎnzé)文件格式第四十八頁，共72頁。成功(chénggōng)導(dǎo)入文件第四十九頁，共72頁。選擇需要(xūyào)拷貝的行第五十頁，共72頁。(2)T-Coffee1.采用Clustal程序計(jì)算兩兩序列之間的全局最優(yōu)比對(duì)結(jié)果；2.采用LALIGN程序計(jì)算兩兩序列之間的局部最優(yōu)比對(duì)的結(jié)果；3.設(shè)計(jì)加權(quán)系統(tǒng)，綜合考慮以上兩類結(jié)果的因素，構(gòu)建指導(dǎo)庫；4.最后(zuìhòu)，采用漸進(jìn)式比對(duì)算法，得到最終的結(jié)果。第五十一頁，共72頁。同時(shí)進(jìn)行(jìnxíng)全局和局部的雙序列比對(duì)對(duì)以上打分的結(jié)果設(shè)計(jì)(shèjì)權(quán)重系統(tǒng)，找到序列中最保守的部分漸進(jìn)方法的比對(duì)，基于(jīyú)上述計(jì)算的primarylibrary第五十二頁，共72頁。ClustalW/X：存在(cúnzài)的問題1.距離最近的，有兩組序列AB和CD，哪組最先比對(duì)？?jī)煞N方案：A.分別、同時(shí)比對(duì)。但是，是以AB為準(zhǔn)，加入(jiārù)CD，然后再加上其他序列，還是CD為準(zhǔn)？結(jié)果可能出入很大B.隨機(jī)挑選一組作為基準(zhǔn)2.當(dāng)序列差異較大時(shí)，上述問題更加明顯。第五十三頁，共72頁。例如(lìrú)1.三條(sāntiáo)序列：2.若Seq1,2先比對(duì)，再加入Seq3：3.Seq1,3先比對(duì)，再加入Seq2:4.Seq2,3先比對(duì)，再加入Seq1:Seq1:ARKCVSeq2:ARCVSeq3:AKCVARKCVAR-CVA-KCVARKCVA-RCVA-KCVARKCVAR-CVAK-CV第五十四頁，共72頁。2.迭代(diédài)方法1.部分解決(jiějué)漸進(jìn)算法存在的問題,主要是ClustalW/X存在的問題；2.PRRP3.DIALIGN第五十五頁，共72頁。(1)PRRP1.先用“漸進(jìn)”算法進(jìn)行多序列比對(duì);2.基于多序列比對(duì)的結(jié)果構(gòu)建進(jìn)化樹；3.重新計(jì)算序列之間的距離，再用“漸進(jìn)”算法進(jìn)行多序列比對(duì)；4.重復(fù)(chóngfù)上述步驟，直到結(jié)果不再發(fā)生改變?yōu)橹?。第五十六頁，?2頁。(2)DIALIGN1.對(duì)所有序列進(jìn)行兩兩之間的局部最優(yōu)化的比對(duì)；2.找到所有能夠匹配的部分M1；將重疊的、前后連續(xù)(consistency)的匹配部分連接起來(diagonals)，為M2；3.將剩下(shènɡxià)的未比對(duì)的序列重新比對(duì)，再發(fā)現(xiàn)能夠匹配的部分，構(gòu)成新M1，將consistency部分構(gòu)成M2；4.重復(fù)上述步驟，直到結(jié)果收斂。第五十七頁，共72頁。DIALIGN:算法(suànfǎ)流程第五十八頁，共72頁。3.部分(bùfen)有向圖算法第五十九頁，共72頁。第六十頁，共72頁。激酶(jīméi)的多序列比對(duì)第六十一頁，共72頁。4.隱馬爾科夫模型(móxíng):ProbCons主要(zhǔyào)改進(jìn)：1.所有序列的兩兩比對(duì)，通過profileHMM的方法進(jìn)行雙序列比對(duì)；2.將漸進(jìn)算法與迭代算法整合；3.目前，性能最優(yōu)。第六十二頁，共72頁。5.整合(zhěnɡhé)算法MUSCLE算法分為三個(gè)部分，每個(gè)部分相對(duì)獨(dú)立；1.Draftprogressive:(1)對(duì)兩條序列，計(jì)算距離采用(cǎiyòng)k-mer的思想；(2)用UPGMA算法構(gòu)建引導(dǎo)樹；