生物信息學多序列比對

多序列比對

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

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

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

(DynamicProgrammingAlgorithm)分而治之方法

(DivideandConquerMethods)SP方法

(SumofPairsMethods)累進方法

(ProgressiveMethods)迭代方法

(IterativeMethods)遺傳算法

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

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

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

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

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

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

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

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

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

對所有序列做雙序列比對，構建距離矩陣計算相似性分數值2

基于雙序列距離矩陣，構建一個進化樹

ScerCele

DmelMouse

Human

3

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

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

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

401

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

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

(ProfileAnalysis)區(qū)塊分析

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

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

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

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

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

/meme/website/meme.html

MASTSearchsequencedatabasesusingmotifs

/meme/website/mast.html

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

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

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

來訓練HMM模型。訓練過程中包括的序列越多，分析的精確性越高隱馬爾可夫模型(HMM)優(yōu)點：植根于概率論，無須序列的順序信息，無需插入/缺失和罰分，可以用到很多先驗信息缺點：需要至少20條序列，有時需要更多才能了解進化歷史分析工具：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，一個轉換的平均值為0.33，因為大多存在3種轉換方式（只有從M4和D4上離開時有2種方式，平均概率為0.5）HowtocreateaHMM多序列比對相關序列選取模型構建模型訓練參數調整應用確立模型Example:1.Sequenceselection選取相關的序列2.AlignmentSaveresultasmsformat多序列比對模型建立3.Hmmbuild4.Hmmt5.Hmmcalibrate模型建立用相關序列對模型進行訓練參數調整位置特異性記分矩陣對于序列保守區(qū)進行MSA分析可以產生位置特異記分矩