生物信息學(xué)多序列比對

多序列比對

(MultipleAlignments)分析多個序列的一致序列,識別蛋白質(zhì)家族的序列模式輔助預(yù)測新序列的二級或三級結(jié)構(gòu),相似的蛋白質(zhì)序列往往具有相似的結(jié)構(gòu)與功能PCR引物設(shè)計用于進(jìn)化分析，是用系統(tǒng)發(fā)育方法構(gòu)建進(jìn)化樹的初使步驟,尋找同源基因我們?yōu)槭裁醋龆嘈蛄斜葘?一個多序列比對例子VTISCTGSSSNIGAG-NHVKWYQQLPGVTISCTGTSSNIGS--ITVNWYQQLPGLRLSCSSSGFIFSS--YAMYWVRQAPGLSLTCTVSGTSFDD--YYSTWVRQPPGPEVTCVVVDVSHEDPQVKFNWYVDG--ATLVCLISDFYPGA--VTVAWKADS--AALGCLVKDYFPEP--VTVSWNSG---VSLTCLVKGFYPSD--IAVEWWSNG--多序列比對與進(jìn)化研究例子圖中NYLS為樹根多序列比對方法全局序列比對動態(tài)規(guī)劃算法(DynamicProgrammingAlgorithm)分而治之方法(DivideandConquerMethods)SP方法(SumofPairsMethods)累進(jìn)方法(ProgressiveMethods)迭代方法(IterativeMethods)遺傳算法(GeneticAlgorithms)局部序列比對概形分析(ProfileAnalysis)區(qū)塊分析(BlockAnalysis)統(tǒng)計學(xué)方法

(StatisticalMethods）多序列比對總體思路在多序列比對前要考慮的問題比對的優(yōu)劣與序列條數(shù)正相關(guān)避免在比對中包括相似度差異過大的序列每個亞群應(yīng)分別先比對，然后再整體比對

全局序列比對動態(tài)規(guī)劃算法

(DynamicProgrammingAlgorithm)分而治之方法

(DivideandConquerMethods)SP方法

(SumofPairsMethods)累進(jìn)方法

(ProgressiveMethods)迭代方法

(IterativeMethods)遺傳算法

(GeneticAlgorithms)序列長度為n的雙序列比對n2

比對比對數(shù)目成指數(shù)增長例如：序列長度為n，序列數(shù)為N的多序列比對數(shù)目是nN對于數(shù)目較少且較短的序列來說都不切實際動態(tài)規(guī)劃算法(DynamicProgramming)Sequence1Sequence2Sequence3多維的動態(tài)規(guī)劃算法分而治之

(DivideandConquer,DCA)方法(Stoye,etal,1997)將MSA的空間復(fù)雜度減小DCA在線MSA

http://bioweb.pasteur.fr/seqanal/interfaces/dca-simple.html

分而治之方法Soineffect…Sequence1Sequence2Sequence3SP(SumofPairs)方法為了找到最佳比對，并解決解決動態(tài)規(guī)則算法的計算復(fù)雜問題，Carrillo&Lipman(1988)建立了SP(SumofPairs)方法SP方法通過對一個隨機(jī)數(shù)據(jù)矩陣中氨基酸對的所有可能組合的記分求和來獲得矩陣記分SP方法例子使用BLOSUM62矩陣,空位罰分為-8在第一列,有三種兩兩比對組合方式：-,S-,SS,S

每一列有k(k-1)/2個雙序列比對-IKSIKSSE-8-8+4=-12計算所有雙序列比對的分?jǐn)?shù)用這些分?jǐn)?shù)構(gòu)建進(jìn)化樹基于進(jìn)化樹計算雙序列比對權(quán)重基于進(jìn)化樹構(gòu)建一個啟發(fā)式多序列比對(HeuristicAlignment)計算每一對雙序列比對的最大權(quán)重ε計算比對的空間位置以達(dá)到最佳比對完成最佳比對

輸出與最大權(quán)重ε比較所獲得的ε慢且消耗大量內(nèi)存最大可以比對8-9個長約250的氨基酸殘基基于SP方法的MSA程序?針對基于動態(tài)規(guī)劃算法的MSA程序比對序列數(shù)目有限，F(xiàn)eng&Doolittle(1987)發(fā)明了累進(jìn)算法?主要思想:通過雙序列比對構(gòu)建進(jìn)化關(guān)系,并通過這種關(guān)系來構(gòu)建序列比對?CLUSTAL和PILEUP是目前常用的基于累進(jìn)算法的比對軟件?CLUSTAL是免費軟件,目前應(yīng)用非常廣泛。分為基于文本的CLUSTALW和圖形用戶界面的CLUSTALX

http://www-igbmc.u-strasbg.fr/BioInfo/ClustalX/Top.html

?T-Coffee是一種新的基于CLUSTAL的程序，它在比對關(guān)系較遠(yuǎn)的系列上較CLUSTAL更具優(yōu)勢，但速度較CLUSTAL要慢累進(jìn)算法(ProgressiveMethods)1

對所有序列做雙序列比對，構(gòu)建距離矩陣計算相似性分?jǐn)?shù)值2

基于雙序列距離矩陣，構(gòu)建一個進(jìn)化樹

ScerCele

DmelMouse

Human

3

依據(jù)進(jìn)化樹進(jìn)行漸進(jìn)比對?依據(jù)進(jìn)化樹，開始對關(guān)系較近的序列進(jìn)行兩兩比對?逐漸加入關(guān)系較遠(yuǎn)的序列進(jìn)行比對?構(gòu)建多序列比對MultiplealignmentScerevisiae[1]Celegans[2]0.640Drosophia[3]0.6340.327Human[4]0.6300.4080.420Mouse[5]0.6190.4050.4690.289累進(jìn)算法原理一般的累進(jìn)比對方法132513131325254droot果仁糖累進(jìn)方法

(Pralineprogressivestrategy)13213131325254d4累進(jìn)算法的一些問題比對的準(zhǔn)確性高度依賴于開始選擇的雙序列比對序列關(guān)系越遠(yuǎn)發(fā)生的錯誤可能越高選擇合適的打分矩陣和罰分準(zhǔn)則較困難ClLUSTALW/X簡介ClLUSTAL是用于MSA分析的最為流行的軟件用來多序列比對、概形(Profile)分析和創(chuàng)建進(jìn)化樹ClLUSTAL最初初由Higgins等于1988年創(chuàng)立并不斷完善

ClLUSTAL分為ClLUSTALW和CLUSTALX兩種類型，這兩種軟件核心功能完全相同，區(qū)別在于ClLUSTALX為圖形界面，而ClLUSTALW保留以前的非圖形平臺ClLUSTAL有用于WINDOWS和UNIX/LINUX的各種版本CLUSTAL方法進(jìn)行所有序列間的雙序列比對基于雙序列比對分?jǐn)?shù)產(chǎn)生一個相鄰連接進(jìn)化樹(neighbor-jointree)根據(jù)進(jìn)化樹提供的序列間關(guān)系按順序?qū)π蛄羞M(jìn)行比對先排最相近序列，再添加其它的序列產(chǎn)生一個MSA來顯示每列的序列變異初期比對可通過一種與FASTA相似的較快的k-tuple模型尋找或動態(tài)規(guī)則算法來進(jìn)行產(chǎn)生進(jìn)化樹的過程中需要計算序列間的遺傳距離（錯配對位置的數(shù)目與比對位置的總數(shù)的比值，空位除外）比對可以用以下兩種方法：-slow/accurate-fast/approximateClustalXClustalXClustalXClustalXClustalXExampleMultiplesequencealignmentof7neuroglobinsusingclustalxPILEUPPILEUP是GCG(GeneticsComputerGroup)軟件包中的MSA分析工具與CLUSTAL一樣使用累進(jìn)式整體比對方法(ProgressiveGlobalAlignment)PILEUP開始的雙序列比對使用Needleman-Wunsch動態(tài)規(guī)劃算法，所以是全局序列比對，善于比較相似度較高的序列OutputofPileup

401

OATNFA1TTCAG......ACACTCAGGTCATCTTCTCAAGCOATNFARTTCAG......ACACTCAGGTCATCTTCTCAAGCBSPTNFATTCAA......ACACTCAGGTCCTCTTCTCAAGCCEU14683TTCAG......ACCCTCAGGTCATCTTCTCAAGCHSTNFRCCCAG......GCAGTCAGATCATCTTCTCGAACSYNTNFTRPCCCAG......GCAGTCAGATCATCTTCTCGAACCATTNFAACCCAG......ACACTCAGATCATCTTCTCGAACCFTNFATCCAG......ACAGTCAAATCATCTTCTCGAACRABTNFMCCCAGATGGTCACCCTCAGATCAGCTTCTCGGGCRNTNFAACCCAGACCCTCACACTCAGATCATCTTCTCAAAAOutputofPileupClUSTAL和PILEUP存在的問題最終的比對結(jié)果取決于最初的雙序列比對，起初的序列相似度越高比對越準(zhǔn)確如果比對序列間長度差異較大則會生成異常的引導(dǎo)樹(guidetrees)從而嚴(yán)重影響多序列比對所選的記分與罰分標(biāo)準(zhǔn)并不一定適合一組序列中的所有序列針對累進(jìn)比對方法的不足產(chǎn)生了迭代方法迭代方法策略在比對過程中不斷重新比對各亞組序列把亞組序列再排成包括所有序列在內(nèi)的整體比對獲得最優(yōu)的總比對分?jǐn)?shù)（由成對比對分?jǐn)?shù)相加而成）迭代方法(IterativeMethods)迭代方法程序MultAlin(Corpet1988)在累進(jìn)比對的過程中重新計算成對比對的分?jǐn)?shù)根據(jù)這些分?jǐn)?shù)來完善比對記分的進(jìn)化樹DIALIGN在雙序列比對中使用對角點陣圖找到不包含空位的局部比對區(qū)域找到不同長度的對角線找到可以使比對產(chǎn)生最大權(quán)重和的加權(quán)過的對角線一種由計算機(jī)科學(xué)家發(fā)明的普通機(jī)器學(xué)習(xí)算法一種很好的解決進(jìn)化改變問題的方法原理：通過重排模擬進(jìn)化過程中空位的插入與重組來嘗試多種的MSA方案，以達(dá)到越來越高的MSA記分缺點：序列超過20條時會變的非常慢與模擬退火算法相近，模擬退火算法是通過其概率途徑來調(diào)整已有的比對來獲得高記分的MSA遺傳算法(GeneticAlgorithms)局部序列比對

局部比對(LocalAlignment)方法能夠確定序列中高度保守的區(qū)域概形分析

(ProfileAnalysis)區(qū)塊分析

(BlockAnalysis)概形分析(ProfileAnalysis)優(yōu)勢：用來尋找一個可能與之匹配的目標(biāo)序列用來在一個數(shù)據(jù)庫中搜索一個可能的新的蛋白

(pfsearch)通過搜索一個profile數(shù)據(jù)庫來找到提交的序列屬于哪一家族(pfscan)比對兩個MSA(profiletoprofile)缺點：所產(chǎn)生的概形僅僅代表MSA本身的序列族變異，如果MSA中的幾個序列相似，則衍生的概形將偏向于這些序列概形分析(ProfileAnalysis)通過對一組序列進(jìn)行整體MSA分析，把其中高度保守的區(qū)域提出分成小的MSA這些小的MSA根據(jù)其序列與結(jié)構(gòu)的比對得到一個記分矩陣根據(jù)這個矩陣列出每個位置上的殘基分?jǐn)?shù)，稱為位置特異記分表(PositionSpecificScoringTable)或概形(Profile)概形(Profile)類似于一個小的MSA，包括匹配、錯配、插入和缺失不同物種HSP70蛋白的profile圖左邊第一列為一致序列(consensussequence),其余的行的數(shù)值表示一致序列中每一個氨基酸出現(xiàn)的頻率的對數(shù)與隨機(jī)頻率對數(shù)的比值，如出現(xiàn)空位，則必須減去空位行在相應(yīng)位置上的數(shù)值。如用其尋找一個長度為100aa的序列，則檢查的串為1~10,2~11,…，最高記分區(qū)段將是概形最相似部分。圖中Z表示谷氨酸or谷氨酰胺;B表示天冬氨酸or丙氨酸ACD……VWYsequenceprofileProfile-sequencealignmentACD..YACD……VWYprofileprofileProfile-profilealignment用CLUSTALX進(jìn)行Profile比對區(qū)塊分析與概形分析相似，區(qū)塊也代表MSA中的保守區(qū)區(qū)塊無插入與缺失，每一個位置只有匹配與錯配每一條序列中的同一區(qū)塊具有相同的長度BLOCKS數(shù)據(jù)庫/MSA中的統(tǒng)計學(xué)方法

(StatisticalMethods）最大期望運(yùn)算法則(ExpectationMaximizationAlgorithm,EM)吉布斯取樣器(GibbsSampler)隱馬爾可夫模型(HiddenMarkovModel,HMM)位置特異性記分矩陣(Position-SpecificScoringMatrix,PSSM)序列標(biāo)語(SequenceLogo)最大期望運(yùn)算法則

用來從未比對的蛋白序列中尋找保守功能域從DNA序列中找蛋白質(zhì)結(jié)合位點通過EM算法找到的這些模體(Motif)允許空位的存在EM算法策略

先對模體所在每一個序列中的位置和大小進(jìn)行一個大致預(yù)測，并將序列中的這些部分比對，這一比對估計模體中每一位置上的殘基或核甘酸的大致組成使用期望步驟：從上述已有的模體中通過每列中的組成來估算每一序列的每一位置上找到這一位點的概率，這些概率又反過來為該位點期望的堿基和氨基酸分布提供新的信息使用最大化步驟：使用以上所得數(shù)據(jù)重復(fù)上面的步驟，直到期望步驟的數(shù)據(jù)不再發(fā)生變化為止，這樣就得到了每個序列的最好比對和每列殘基的最好估計MEME(MultipleEMforMotifElicitation)MEME程序是由加州大學(xué)sanDiego分校的超級計算中心所創(chuàng)立MEME可對單個DNA或蛋白質(zhì)序列或一系列DNA或蛋白質(zhì)序列中對一個或多個無間隔的模式(Pattern)定位MEME的三種模體(Motif)模型：OOPS－每條序列中預(yù)期出現(xiàn)一次motifZOOPS－每條序列出現(xiàn)零次或一次motifTCM－每條序列中出現(xiàn)任意次數(shù)的motif在線MEME工具：MEMEDiscovermotifs(highlyconservedregions)ingroupsofrelatedDNAorproteinsequences

/meme/website/meme.html

MASTSearchsequencedatabasesusingmotifs

/meme/website/mast.html

MEME結(jié)果吉布斯取樣器(GibbsSampler)隨機(jī)地從所有序列中抽出一個或幾個作為外圍序列用來計算背景噪音，然后對剩下的序列隨機(jī)地選擇假設(shè)存在的模體的開始位置，并來回移動其位置，直到模體概率相對于背景概率之比達(dá)到最大值，來發(fā)現(xiàn)所有序列共有的最可能模式調(diào)整序列比對以獲得較好的記分，但保留尋找其它更好位置的余地。當(dāng)在幾個序列中選擇了模體的正確開始位置后，模體的組成便開始反映在其余序列中所能找到的模體集合最佳模體，并確定模體在每一序列中的精確位置被廣泛應(yīng)用于蛋白序列中發(fā)現(xiàn)復(fù)雜和可變的模體/gibbs/gibbs.html

隱馬爾可夫模型(HMM)定義：一種統(tǒng)計模型，它考慮有關(guān)匹配、錯配和間隔的所有可能的組合來生成一組序列排列HMM用來序列分析、產(chǎn)生概形HMM、分析序列組成和模式并通過預(yù)測開放閱讀框(OpenReadingFrame,ORF）來定位基因及預(yù)測蛋白質(zhì)結(jié)構(gòu)

原理：先產(chǎn)生一個序列家族模型，并用先驗信息初始化，然后用一組序列(序列條數(shù)≥20)

來訓(xùn)練HMM模型。訓(xùn)練過程中包括的序列越多，分析的精確性越高隱馬爾可夫模型(HMM)優(yōu)點：植根于概率論，無須序列的順序信息，無需插入/缺失和罰分，可以用到很多先驗信息缺點：需要至少20條序列，有時需要更多才能了解進(jìn)化歷史分析工具：HMMER(/)Pfam:

http://www.sanger.ac.uk/Software/Pfam/(proteindomainalignmentsandprofileHMMs)HMM示意圖圖示：NKYLT是通過BEG-M1-I1-M2-M3-M4-END.每個氨基酸的概率為:0.33×0.05×0.33×0.05×0.33×0.05×0.33×0.05×0.33×0.05×0.5，一個轉(zhuǎn)換的平均值為0.33，因為大多存在3種轉(zhuǎn)換方式（只有從M4和D4上離開時有2種方式，平均概率為0.5）HowtocreateaHMM多序列比對相關(guān)序列選取模型構(gòu)建模型訓(xùn)練參數(shù)調(diào)整應(yīng)用確立模型Example:1.Sequenceselection選取相關(guān)的序列2.AlignmentSaveresultasmsformat多序列比對模型建立3.Hmmbuild4.Hmmt5.Hmmcalibrate模型建立用相關(guān)序列對模型進(jìn)行訓(xùn)練參數(shù)調(diào)整位置特異性記分矩陣對于序列保守區(qū)進(jìn)行MSA分析可以產(chǎn)生位置特異記分矩