生物信息學(xué)的算法

生物信息學(xué)的算法第1頁/共30頁初級層面基于現(xiàn)有的生物信息數(shù)據(jù)庫和資源，利用成熟的生物信息學(xué)工具（專業(yè)網(wǎng)站、軟件）解決生物信息學(xué)問題——生物信息數(shù)據(jù)庫（NCBI、EBI等）——基因組序列分析、序列比對軟件（GCG、BLAST、CLUSTAL等）——系統(tǒng)發(fā)育樹構(gòu)造軟件（PHYLIP、PALM、MEGA等）——分子動力學(xué)模擬軟件（GROMACS、NAMD等）——搜集、整理有特色的生物信息學(xué)數(shù)據(jù)集第2頁/共30頁中級層面利用數(shù)值計算方法、數(shù)理統(tǒng)計方法和相關(guān)的工具，研究生物信息學(xué)問題——概率、數(shù)理統(tǒng)計基礎(chǔ)——科學(xué)計算基礎(chǔ)——現(xiàn)有的數(shù)理統(tǒng)計和科學(xué)計算工具（EXCEL、SPSS、SAS、MATLAB等）——建立有特色的生物信息學(xué)數(shù)據(jù)庫第3頁/共30頁高級層面提出有重要意義的生物信息學(xué)問題；自主創(chuàng)新，發(fā)展新型方法，開發(fā)新型工具，引領(lǐng)生物信息學(xué)領(lǐng)域研究方向。——面向生物學(xué)領(lǐng)域，解決生物學(xué)問題——數(shù)學(xué)、物理、化學(xué)、計算科學(xué)等思想和方法——建立模型，發(fā)展算法——自行編程，開發(fā)軟件，建立網(wǎng)頁（Linux系統(tǒng)、C/C++、PERL、數(shù)據(jù)庫技術(shù)）第4頁/共30頁從事生物信息學(xué)研究應(yīng)具備多方面的科學(xué)基礎(chǔ)：（1）、一定的計算能力，包括相應(yīng)的軟、硬設(shè)備。要有各種數(shù)據(jù)庫或者能與國際、國內(nèi)的數(shù)據(jù)庫系統(tǒng)進(jìn)行有效的交流。要有發(fā)達(dá)、穩(wěn)定的互聯(lián)網(wǎng)絡(luò)系統(tǒng)；（2）、強(qiáng)有力的創(chuàng)新算法和軟件。沒有算法創(chuàng)新，生物信息學(xué)就無法獲得持續(xù)的發(fā)展；（3）、與實(shí)驗科學(xué)，特別是與自動化的大規(guī)模高通量的生物學(xué)研究方法與平臺技術(shù)建立廣泛、緊密的聯(lián)系。這些技術(shù)，既是產(chǎn)生生物信息數(shù)據(jù)的主要方法，又是驗證生物信息學(xué)研究結(jié)果的關(guān)鍵手段。從事生物信息學(xué)研究的人員必須具備多學(xué)科交叉的知識。第5頁/共30頁1.2生物信息學(xué)的“降龍十八掌”第6頁/共30頁第一式見龍在田（1）要掌握生物信息數(shù)據(jù)庫及其查詢搜索方法(Database&searching)——對分子生物信息數(shù)據(jù)庫的種類以及某些具體數(shù)據(jù)庫的掌握和了解——從現(xiàn)有數(shù)據(jù)庫中熟練獲得需要的數(shù)據(jù)信息（尤其是二級數(shù)據(jù)庫）——能熟練地進(jìn)行數(shù)據(jù)庫查詢和數(shù)據(jù)庫搜索（數(shù)據(jù)庫查詢系統(tǒng)Entrez、SRS；搜索工具BLAST等）——數(shù)據(jù)庫技術(shù)、互聯(lián)網(wǎng)技術(shù)第7頁/共30頁第二式飛龍在天（2）要學(xué)會生物信息學(xué)軟件和工具的應(yīng)用(Software&application)利用成熟的生物信息學(xué)工具（專業(yè)網(wǎng)站、軟件）解決生物信息學(xué)問題——基因組序列分析、序列比對軟件（GCG、BLAST、CLUSTAL等）——系統(tǒng)發(fā)育樹構(gòu)造軟件（PHYLIP、PALM等……）——基因芯片檢測分析軟件（商業(yè)軟件ScanArray、Array-Pro等……）——分子動力學(xué)模擬軟件（GROMACS、NAMD等……）第8頁/共30頁第三式鴻漸于陸（3）概率論基礎(chǔ)(Probabilitytheory)——隨機(jī)事件、概率——隨機(jī)變量、概率分布——大數(shù)定律、中心極限定理——幾乎用于生物信息學(xué)的各個方面“Mostoftheproblemsincomputationalsequenceanalysisareessentiallystatistical.”——“Biologicalsequenceanalysis”第9頁/共30頁第四式或躍在淵（4）數(shù)理統(tǒng)計基礎(chǔ)(Statisticalmethods)——樣本和統(tǒng)計量（方差、均值……）——參數(shù)估計、假設(shè)檢驗——基本的統(tǒng)計分析（方差分析、協(xié)方差分析、回歸分析）——常用統(tǒng)計軟件的運(yùn)用（SPSS、SAS）——幾乎用于生物信息學(xué)的各個方面第10頁/共30頁第五式羚羊觸藩（5）基于頻率的組分分析方法和權(quán)重矩陣方法(Compositionanalysis&weightmatrixmethod)——符號（如堿基）頻率反映具有生物學(xué)意義的序列特征，如內(nèi)含子剪接位點(diǎn)的發(fā)現(xiàn)，KOZAK規(guī)則的發(fā)現(xiàn)等——核酸組分、氨基酸組分、密碼子使用頻率——主要用于具有特定生物學(xué)意義的序列特征的分析第11頁/共30頁權(quán)重矩陣分析方法舉例——針對序列信號（一段核酸、蛋白），計算每一位點(diǎn)所使用的詞匯或叫符號（堿基、氨基酸）頻率，頻率的偏好性反映信號的序列特征（sequencepattern）。例：人類基因內(nèi)含子/外顯子剪接位點(diǎn)的序列特征分析R=AorGY=CorUN=A,G,CorU供體位點(diǎn)受體位點(diǎn)第12頁/共30頁Bayesian打分函數(shù)用于剪接位點(diǎn)預(yù)測的公式Thelikelihoodthatapropertyvaluev

(ofanewstructure)isdrawnfromthesplicingsiteis:Scorefortheoveralllikelihoodofthequerysequence

beingasiteis:SaywehaveasequenceS=S1S2…Sn.ThenoneneedtocalculateSotolookforadonorsiteinthesequence,wemightcalculate第13頁/共30頁第六式潛龍勿用（6）信息論方法(Informationmethod)——信息熵——信息的度量：是信息符號出現(xiàn)何種狀態(tài)的一種不確定性程度，信息的獲得要對不確定性進(jìn)行否定?！镄畔⒌姆柸鏏CGT四種符號，狀態(tài)空間即其所有可能的排列——用于結(jié)構(gòu)預(yù)測——信息熵H刻畫了由{pi}表示的隨機(jī)試驗結(jié)果的先驗不確定性，或觀察到輸出時所獲得的信息量。第14頁/共30頁第七式利涉大川（7）期望最大化（EM）方法(ExpectationMaximization)——EM算法是一種在不完全數(shù)據(jù)情況下計算極大似然估計或者后驗分布的迭代算法?！m用于具有隱變量的模型和問題，——用于結(jié)構(gòu)的識別，如Motif識別的MEME方法、HMM中的Baum-Welch算法第15頁/共30頁第八式神龍擺尾（8）動態(tài)規(guī)劃方法(DynamicProgramming)——一種常用的多階段決策的尋優(yōu)算法——動態(tài)規(guī)劃用得最多的方面是DNA序列或者蛋白質(zhì)序列比對第16頁/共30頁第九式密云不雨（9）迭代方法(Iteration)——迭代的目的通常是在狀態(tài)空間找到目標(biāo)函數(shù)收斂的穩(wěn)定解——在運(yùn)用模式識別方法時，對系統(tǒng)參數(shù)的學(xué)習(xí)通常要經(jīng)過迭代來實(shí)現(xiàn)——迭代必須能夠不斷逼近穩(wěn)定解——用于上述某些方法的方法第17頁/共30頁第十式突如其來（10）回歸、擬合、相關(guān)性分析、關(guān)聯(lián)分析(Regression,fitting,correlation&association)——經(jīng)典的統(tǒng)計分析方法——主要目的：描述和預(yù)測自變量與因變量間的關(guān)系——用于上述某些方法的方法第18頁/共30頁第十一式雙龍取水（11）判別分析方法(Discriminantanalysis)——用于判別樣品所屬類型的統(tǒng)計分析方法條件：已知研究對象總體的類別數(shù)目及其特征（如：分布規(guī)律，或各類的訓(xùn)練樣本）目的：判斷未知類別的樣本的歸屬類別——用于基因識別、醫(yī)學(xué)診斷、人類考古學(xué)第19頁/共30頁第十二式魚躍于淵（12）聚類分析方法(Clusteringmethod)——聚類分析（群分析）是實(shí)用多元統(tǒng)計分析的一個新分支，正處于發(fā)展階段。理論上尚未完善，但應(yīng)用十分廣泛。實(shí)質(zhì)上是一種分類問題，目的是建立一種分類方法，將一批數(shù)據(jù)按照特征的親疏、相似程度進(jìn)行分類?！獥l件：研究對象總體的類別數(shù)目未知，也不知總體樣本的具體分類情況——目的：通過分析，選定描述個體相似程度的統(tǒng)計量、確定總體分類數(shù)目、建立分類方法；對研究對象給出合理的分類。(“物以類聚”是聚類分析的基本出發(fā)點(diǎn))第20頁/共30頁——定性、經(jīng)驗的分類的局限分類較粗、數(shù)據(jù)量小、憑借經(jīng)驗——譜系聚類法（系統(tǒng)聚類法）、動態(tài)聚類法、模糊聚類法——生物信息學(xué)中的聚類分析問題：根據(jù)DNA芯片獲得的基因表達(dá)數(shù)據(jù)進(jìn)行基因聚類（數(shù)據(jù)量龐大）蛋白質(zhì)相互作用網(wǎng)絡(luò)的分類根據(jù)不同物種的大分子序列進(jìn)行相似性比較并構(gòu)建系統(tǒng)發(fā)育樹X(1)X(2)X(3)X(4)X(5)GibbonSymphalangusHumanGorillaChimpanzee黑猩猩猩猩猿猴第21頁/共30頁第十三式震驚百里（13）Markov模型的應(yīng)用(Markovmodel)——Markov過程：從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)時，過程僅取決于前面n種狀態(tài)，是一種有序n模型。n是影響下一個狀態(tài)選擇的狀態(tài)數(shù)?！詈唵蔚腗arkov過程是一階過程，狀態(tài)的選擇完全取決于前一狀態(tài)，這種選擇是依照概率來選擇的?！獱顟B(tài)的選擇是概率的，而非確定的。故Markov過程本質(zhì)上是一種隨機(jī)過程。第22頁/共30頁第十四式損則有孚（14）隱Markov模型方法(HMMmethod)——將核苷酸序列看成一個隨機(jī)序列，DNA序列的編碼部分與非編碼部分在核苷酸的選用頻率上對應(yīng)著不同的Markov模型。由于這些MarkovC+G+CGCGC–G–C+C–G+G–BE340.0100.0120.0030.00320.0002模型的統(tǒng)計規(guī)律是未知的，而HMM能夠自動尋找出它們隱藏的統(tǒng)計規(guī)律。對于高等生物這樣復(fù)雜的DNA序列，HMM必須學(xué)習(xí)不同的基因結(jié)構(gòu)的信號。第23頁/共30頁隱Markov模型(HMM)語音識別(Speechrecognition)光字符識別(Opticalcharacterrecognition)生物序列分析(Biologicalsequenceanalysis)（1）序列比較與搜尋（尤其是多序列比對）（2）基因及信號的識別、預(yù)測（包括DNA編碼與非編碼區(qū)的識別、真核基因剪接位點(diǎn)信號識別、非編碼區(qū)的轉(zhuǎn)錄調(diào)控信號識別、信號肽識別……）（3）蛋白質(zhì)二級結(jié)構(gòu)、家族、超家族預(yù)測、分類等……生物特征識別(Biometrics)第24頁/共30頁第十五式時乘六龍（15）感知器與人工神經(jīng)網(wǎng)絡(luò)方法(Perceptron&ANNmethod)——計算機(jī)人工神經(jīng)網(wǎng)絡(luò)是對大腦神經(jīng)網(wǎng)絡(luò)的模擬，在生物信息學(xué)研究中，無論是基因識別還是蛋白質(zhì)結(jié)構(gòu)預(yù)測，神經(jīng)網(wǎng)絡(luò)都取得了比其它方法更為準(zhǔn)確的結(jié)果。第25頁/共30頁第26頁/共30頁第十六式龍戰(zhàn)于野（16）決策樹、支持向量機(jī)及其它模式識別方法(Decisiontree&SVMmethod)——模式識別是在輸入樣本中尋找特征并識別對象的一種方法?！Ｊ阶R別主要有兩種方法，一種是根據(jù)統(tǒng)計特征進(jìn)行識別，另一種是根據(jù)對象的結(jié)構(gòu)特征進(jìn)行識別，而后者常用的方法為句法識別?！诨蜃R別中，對于DNA序列上的功能位點(diǎn)和特征信號的識別都需要用到模式識別。第27頁/共30頁第十七式履霜冰至（17）微分方程的數(shù)值方法(Numericalmethods)——分子動力學(xué)模擬：研究生物大分子的構(gòu)象，主要還是用基于半經(jīng)驗勢函數(shù)的分子動力學(xué)方法，而量