生物信息學(xué)應(yīng)用：序列比對與數(shù)據(jù)庫搜索匯總課件

第三章序列比對序列比對概念序列比對用途常用術(shù)語序列比對的類型序列比對的策略打分系統(tǒng)---打分矩陣比對算法

-全局比對Needleman-Wunsch算法

-局部比對Smith-Waterman算法序列比對搜索程序序列比對概念序列中的符號在核酸中是A,T/U,C,G，在蛋白質(zhì)中則是20個(gè)氨基酸殘基的單字母。序列比對指將兩個(gè)或多個(gè)序列排列在一起，標(biāo)明最相似的排列方式，計(jì)算其相似度。除匹配外，序列間可以有錯(cuò)配，還可以插入間隔，通常用短橫線“-”表示。序列比對用途基因預(yù)測、基因注釋(annotation)、蛋白質(zhì)結(jié)構(gòu)和功能預(yù)測等基因和蛋白序列的進(jìn)化分析在比對中，錯(cuò)配與突變相應(yīng)，而空位與插入或缺失對應(yīng)根據(jù)物種間基因（或蛋白）序列的比對結(jié)果構(gòu)建系統(tǒng)發(fā)生樹，從分子層次分析物種的進(jìn)化48條染色體〔24對）黑猩猩細(xì)胞色素C的氨基酸順序與人類的相同神經(jīng)功能相關(guān)基因NCAM2和GRIK1黑猩猩中大片段DNA缺失語言能力相關(guān)基因FOXP2序列在人-黑猩猩間存在兩個(gè)氨基酸的差異Pantroglodyteschr22HomoSapienschr2146條染色體〔23對）常用術(shù)語比對常用語插入,Insertion缺失,Deletion替換,Substitution插入缺失,Indel序列相同兩序列所有比對位置上的元素（核酸或氨基酸）完全相同序列相似性兩序列比對位置上的元素（核酸或氨基酸）大部分相同兩序列比對位置上的元素（氨基酸）相似序列同源性兩序列來自一個(gè)共同的祖先序列序列比較?Dotmatrix分析(intuitive)?序列比對計(jì)算DPalgorithm(exact)?Wordork-tuple(FASTA,BLAST)(heuristic)DotMatrixTheaminoacidsequencesofthephageλcI(horizontalsequence)andphageP22c2(verticalsequence)repressors.Thewindowsizeandstringencyareboth1.序列比對的類型序列數(shù)目雙序列比對（pairwisealignment）多序列比對（multiplesequencesalignment）序列種類核酸序列比對蛋白質(zhì)序列比對比對方式全局比對（Needleman-Wunsch）局部比對（Smith-Waterman）Globalvs.Local序列１（待測序列）：AGGVLIIQVG||||||序列２（目標(biāo)序列）：AGGVLIQVG序列１（待測序列）：AGGVLIIQVG|||||||||序列２（目標(biāo)序列）：AGGVLIQVG６match9match序列比對中的兩個(gè)關(guān)鍵點(diǎn)Keypoint1,對齊方式序列１（待測序列）：ATCTG

序列２（目標(biāo)序列）：ATCAG8分Match2,gap-1,mismatch0Keypoint2,打分方式序列１（待測序列）：ATC_TG||||序列２（目標(biāo)序列）：ATCA_GMatch2,mismatch-1,gap0序列１（待測序列）：ATCTG||||序列２（目標(biāo)序列）：ATCAG序列比對目的和實(shí)現(xiàn)方法目的：通過尋找序列間的最佳匹配，判斷序列間的相似性程度實(shí)現(xiàn)方法：依據(jù)打分系統(tǒng)，利用算法尋找最佳匹配打分系統(tǒng)打分矩陣空位罰分尋找最佳匹配的算法打分系統(tǒng)---打分矩陣打分矩陣（scoringmatrix）描述比對字符間（氨基酸或堿基）的相似性單一打分矩陣（核酸，氨基酸）相同（1）不同（0）AGCTA1000G0100C0010T0001遺傳密碼子矩陣（氨基酸）所有的氨基酸突變都產(chǎn)生于核苷酸的變化，故氨基酸替換的分值應(yīng)取決于由一個(gè)密碼子轉(zhuǎn)變?yōu)榱硪幻艽a子所必需的突變的數(shù)量。一種遺傳密碼子打分矩陣根據(jù)導(dǎo)致密碼子改變所需改變核苷酸的數(shù)量來定義兩個(gè)氨基酸之間的距離，比如PAM矩陣不同氨基酸之間的替換率是不一樣的，原因有密碼子突變，氨基酸間理化性質(zhì)的相似性等。另一種遺傳密碼子打分矩陣則是直接基于實(shí)際氨基酸之間的替換率，比如Blosum矩陣矩陣元素通常為比對中的一對字符（氨基酸或堿基）隨機(jī)發(fā)生的概率（每個(gè)氨基酸出現(xiàn)的獨(dú)立概率）與其實(shí)際出現(xiàn)的概率之比Dayhoff的PAM矩陣PAM（pointacceptedmutation）可為進(jìn)化時(shí)間單位

假設(shè)同一位點(diǎn)不會發(fā)生二次以上的突變，則1PAM等于100個(gè)氨基酸多肽鏈中預(yù)期發(fā)生一次替換所需的時(shí)間。1PAM相當(dāng)于所有的氨基酸平均有1%發(fā)生了變化，經(jīng)過100PAM的進(jìn)化，并非每個(gè)氨基酸的殘基均發(fā)生變化：有一些可能突變多次，甚至又變成原來的氨基酸，而另一些氨基酸可能根本沒有發(fā)生過變化。因此利用大于100PAM的時(shí)間間隔可能達(dá)到區(qū)分同源性蛋白質(zhì)的目的。NPAM表示對原始PAM矩陣N次方250PAM突變概率矩陣(Dayhoff等,1979)

*表中數(shù)值均乘以了100；BLOSUM矩陣BLOSUM（Blockssubstitutionmatrix）矩陣Dayhoff模型假設(shè)基于全序列，且蛋白質(zhì)序列各部位進(jìn)化的速率是均等的。但事實(shí)上并非如此，因?yàn)楸Ｊ貐^(qū)的進(jìn)化速率顯然低于非保守區(qū)。對不同家族蛋白質(zhì)序列片段的區(qū)間(blocks)進(jìn)行比對，不加入gaps，這些序列區(qū)間對應(yīng)于高度保守的區(qū)域。氨基酸匹配率可通過各區(qū)間可能的匹配率得到。再將這些匹配率計(jì)入匹配率表。其進(jìn)化相關(guān)機(jī)率的計(jì)算方法與Dayhoff矩陣相似。矩陣名中的數(shù)字代表產(chǎn)生矩陣所用序列集的相似度BLOSUM62(lowerpart)PAM矩陣和BLOSUM矩陣的比較PAM矩陣的突變率來自一個(gè)明確的進(jìn)化模型,該模型中氨基酸的替換可從近親蛋白質(zhì)的系統(tǒng)發(fā)生樹分支得知,而遠(yuǎn)親蛋白質(zhì)的關(guān)系則可用外推過程建立模型，但BLOSUNM矩陣卻是通過直接觀測保守區(qū)域中氨基酸的替換幾率建立的PAM矩陣基于序列全局比對觀測到的突變,包括了保守區(qū)域和可變區(qū)域,而BLOSUM矩陣僅基于高度保守的序列，不允許有空位的出現(xiàn)一般情況下PAM120矩陣和BLOSUM62矩陣是最好的選擇打分系統(tǒng)---空位罰分序列的改變不僅可由點(diǎn)突變造成，也可因殘基的插入和缺失引起。所以引入空位以產(chǎn)生序列比對是有生物學(xué)基礎(chǔ)的。引入空位罰分來代表比對中加入空位的有效性

ACTACGTA___CGT空位罰分的計(jì)算:k:空位長度;r:開放空位罰分值;δ:

擴(kuò)展空位罰分值,δ<r比對方法最初采用點(diǎn)陣分析法1950年由Bellman描述的一種優(yōu)化算法，后被Needlman和Wunsch引入生物序列比較計(jì)算，即動(dòng)態(tài)規(guī)劃算法全局比對局部比對全局比對---局部比對全局比對局部比對全局比對Needleman&Wunsch算法：適用于整體相似性程度較高的序列（JMB,48,443-453,1970）的動(dòng)態(tài)規(guī)劃算法全局比對算法：兩條核酸/蛋白質(zhì)序列具有最多匹配堿基/殘基定義為最佳匹配，允許插入與缺失速度慢Needleman-Wunsch算法動(dòng)態(tài)規(guī)劃算法思路：將多級問題劃分成多個(gè)有聯(lián)系的單級問題，并逐級解決對于序列比對而言，將整條序列的比對，劃分為從序列一端逐個(gè)位置比對到另一段的過程AB實(shí)現(xiàn)算法兩序列開端的位置，但不一定是序列第一個(gè)字母的位置??AG????A_????C_????AT??將求解最佳匹配映射成矩陣模型；矩陣中橫行豎列各多一個(gè)，表示序列開端；矩陣中每個(gè)數(shù)值表示到當(dāng)前位置的最佳匹配分值，但單從這個(gè)數(shù)值只能知道當(dāng)前位置的匹配情況；當(dāng)前位置之前的最佳匹配方式必需通過回溯當(dāng)前位置的得分的來源確定。例:步驟1:初始化打分矩陣：S0,0=0S0,j

=-j*gapSi,0=-i*gapSm,n=optimalscore步驟2:計(jì)算Si,j步驟3:回溯最佳對齊路徑打分：Match+2分

mis-match-3分

Gap(insertion&deletion)-1分最佳匹配：1.AGCT_2.A_GCTA__TGATG__局部比對工具Smith-Waterman算法：執(zhí)行局部比對的動(dòng)態(tài)規(guī)劃算法。適用于親緣關(guān)系較遠(yuǎn)、僅具有局部區(qū)域相似性的序列。(JMB,147,195-197,1981)MPSrch程序SSearch速度慢Needleman-Wunsch算法的改造其它基于DP的實(shí)現(xiàn)方法結(jié)構(gòu)-遺傳矩陣CSTPAGNDEQHRKMILVFYW64222321012202222333C6545553333331222332S645242332343323121T65322333322233222P6534432232225222A634421321224123G65334241212130N6543230113120D642241114011E64342122121Q6431131231H652222112R62223011K6454223M655432I65434L6433V653F63Y6WVEDQKLSKCN

VENKLTRPKCD對齊：VEDQKLS

KCNVEN

KLTRPKCD

VEDQKLSKCNV6432352322E4654413403N2353415426K3434623604L5112262221T3323425424R2223523522P3323234222K3434623604C2011024062D3564313315

VEDQKLSKCNV6432352322E4654413403N2353415426K3434623604L5112262221T3323425424R2223523522P33232321222K34346231754C20110245112D3564313315

VEDQKLSKCNV504640353026191482E424442373122201563N353638363122201576K333432313323201754L343030292527191371T292928292723221574R232323242623201672P202019201920211372K141514151713141754C80110245112D3564313315序列比對搜索程序序列比對程序基于啟發(fā)式算法，用于數(shù)據(jù)庫搜索（Heuristicdatabasesearch）,可保證搜索快速且敏感度高，但不能保證最佳典型程序FastA系列Blast系列在數(shù)據(jù)庫中查詢新序列提交新序列進(jìn)行數(shù)據(jù)庫搜索以確定：數(shù)據(jù)庫中是否已經(jīng)存在該序列結(jié)構(gòu)數(shù)據(jù)功能與機(jī)制活性位點(diǎn)、配體結(jié)合位點(diǎn)、作用位點(diǎn)進(jìn)化關(guān)系啟發(fā)式算法特征Theprincipalheuristicofthesealgorithmsistouse“word”tosearchthedatabaseA“word”canconsistofanymultipleandarrangementofcharactersAwordisalsoknownasak-tupleorw-tuple,whichisessentiallyaderivationoftheword‘multiple’Themainassumptioninaword-basedmethodassumesthatrelatedsequencesaremorelikelytoshareseveralcommonwords.Increasingthewordsize,enablessearchestobeperformedfaster,butreducesthesensitivity操作和評估2-stepprocess:matchessequenceinquerysequencetothesamewordsindatabaseusethematchtoestablishor‘seed’analignmentScoring:ascoreiscalculatedforthesimilarityofthealignmentSensitivity（靈敏度）

theabilitytoidentifydistantlyrelatedsequenceTP/(TP+FN),i.e.Truepositive/ActualpositiveSelectivity（精確度）theabilitytoavoidfalsepositiveTP/(TP+FP),i.e.Truepositive/PredictedpositiveFASTAFASTA(Lipman&Pearson,1990)基于字，利用字寬（k-tuple=1-2殘基，或=6堿基）快速識別匹配的短序列FASTA程序操作分四部根據(jù)字寬打分，并篩選出較好的短匹配利用PAM或BLUSM對篩選出的短匹配精細(xì)評估拼接匹配短序列拼接評估拼接結(jié)果的優(yōu)劣，輸出結(jié)果FASTA找出高相似短序列打分，精細(xì)匹配拼接，去除不可能區(qū)段結(jié)果評估FASTA的快速來源于其在序列庫中進(jìn)行的快速初檢，找出與待檢序列高度相似的序列，但這一快速檢索局限于待檢序列和序列庫序列之間較短的完全相同序列區(qū)段上改進(jìn)的FSATA程序可對結(jié)果進(jìn)行統(tǒng)計(jì)顯著性評估數(shù)據(jù)庫相似性搜索程序FASTA程序名稱待檢序列類型數(shù)據(jù)庫序列類型說明FASTA3pp在某一蛋白質(zhì)序列庫中搜索蛋白質(zhì)相似TFASTA3pn在核酸序列庫(已被即時(shí)翻譯)中比對待檢蛋白質(zhì)序列FASTX3np在蛋白質(zhì)序列庫中比對待檢核酸序列(用6種讀框翻譯)TFASTX3pn在核酸序列庫中比對待檢蛋白質(zhì)序列SSEARCHp/np/n使用Smith-Waterman算法聯(lián)配比對

BLASTBLAST（BasicLocalAlignmentSearchTool,Altschuletal.,1990)BLAST進(jìn)行的是無空位的局部比對，以尋找兩序列間HSP（high-scoresegmentpairs）為目標(biāo)BLAST操作過程根據(jù)給定字寬，尋找HSP區(qū)域，即分值超過閾值T的區(qū)域（初始區(qū)域，字的長度對于蛋白質(zhì)序列默認(rèn)為3，對于DNA序列默認(rèn)為11）拓展HSP區(qū)域，得到高于閾值S的比對結(jié)果對高于閾值S的結(jié)果利用E值（默認(rèn)為10）進(jìn)行統(tǒng)計(jì)性評估輸出最大分值結(jié)果BLAST數(shù)據(jù)庫相似性搜索程序BLAST程序名稱待檢序列類型數(shù)據(jù)庫序列類型說明BLASTPpp在蛋白質(zhì)序列庫中比對待檢蛋白質(zhì)序列BLASTNnn在核酸序列庫中比對待核酸序列BLASTXnp在蛋白質(zhì)序列庫中比對待檢核酸序列(用所有6種讀框翻譯)TBLASTNpn在核酸序列庫(用6種讀框即時(shí)翻譯)中比對待檢蛋白質(zhì)序列TBLASTXnn在核酸序列庫(用6種讀框即時(shí)翻譯)中比對待檢核酸序列(同樣用所有6種讀框翻譯)BLAST的一項(xiàng)重要特性就是所報(bào)告的匹配序列的統(tǒng)計(jì)學(xué)顯著性評分。這一統(tǒng)計(jì)學(xué)顯著性評分是用Karlin-Altschul算法決定的，所算出的Poisson概率表明所得到的序列相似性隨機(jī)出現(xiàn)的可能性。表示僅僅因?yàn)殡S機(jī)性造成獲得聯(lián)配結(jié)果的可能次數(shù)。這一數(shù)值越接近零，發(fā)生這一事件的可能性越小。從搜索的角度看，E值越小，聯(lián)配結(jié)果越顯著。E值(E-value)BLAST2.0版本已有序列過濾器功能。過濾器將鎖定諸如組成低復(fù)雜(lowcompositionalcomplexity)序列區(qū)(如Alu序列)，用一系列N(NNNNNN)替代這些序列。N代表任意堿基(IUB-code)。只有未知待檢序列被過濾替代，而數(shù)據(jù)庫的序列將不被過濾。過濾對絕大多數(shù)序列都是有益的，“Filter”項(xiàng)的缺省選項(xiàng)為ON?？偨Y(jié)

FASTA和BLASTScience(NO.5507,2001)人類基因組?？幸黄}為“生物信息學(xué)：努力在數(shù)據(jù)的海洋里暢游”的文章中寫到：“我們身處急速上漲的數(shù)據(jù)海洋中…我們?nèi)绾伪苊鉀]頂之災(zāi)？”一條可靠的辦法可能是趕緊找到“一葉輕舟”，而且在輕舟上裝上先進(jìn)的電子設(shè)備，諸如衛(wèi)星定位系統(tǒng)．衛(wèi)星信息傳輸系統(tǒng)等等……BLAST和FASTA便是這樣的一條“輕舟”。AltschulS.F.等人（1997）提出了一個(gè)通過尋找蛋白質(zhì)家族保守序列來提高算法敏感性的PSI-BLAST（Position-SpecificIteratedBLAST）算法。PSI-BLAST可以對數(shù)據(jù)庫進(jìn)行多輪循環(huán)檢索，每一輪的檢索速度都大約是BLAST的兩倍，但每一輪都能提高檢索的敏感性。FASTA和BLAST系列程序FASTA程序BLAST程序適用數(shù)據(jù)描述FASTABLASTNDNA水平將核苷酸查詢序列與核苷酸序列數(shù)據(jù)庫進(jìn)行比較FASTABLASTP蛋白質(zhì)水平將蛋白質(zhì)查詢序列與蛋白質(zhì)序列數(shù)據(jù)庫進(jìn)行比較FASTXBLASTX蛋白質(zhì)水平將核苷酸查詢序列的六讀碼框（兩條鏈）翻譯序列與蛋白質(zhì)數(shù)據(jù)庫進(jìn)行比較TFASTATBLASTN蛋白質(zhì)水平將蛋白質(zhì)查詢序列與核苷酸數(shù)據(jù)庫的六讀碼框翻譯序列進(jìn)行比較TBLASTX蛋白質(zhì)水平將核苷酸查詢序列的六讀碼框（兩條鏈）翻譯序列與核苷酸數(shù)據(jù)庫的六讀碼框翻譯序列進(jìn)行比較TFASTX蛋白質(zhì)水平TFASTA的增強(qiáng)版本，考慮了移框誤差因?yàn)锽LAST和FASTA采用不同的算法，可同時(shí)用這兩種搜索引擎重新檢索某一特定序列，如果用其中一種找不到顯著相似序列，不妨試一試另一程序。如果BLAST和FASTA均找不到顯著匹配的序列，還可以選擇第3條比較費(fèi)時(shí)的搜索策略。一些網(wǎng)站允許用戶使用基于Smith-Waterman算法的搜索程序，如BLITZ。BLITZ(www.ebi.ac.uk/searchs/b