自相關(guān)基因算法

基因識(shí)別算法的研究進(jìn)展基因識(shí)別算法的研究進(jìn)展基因識(shí)別算法的研究進(jìn)展基因識(shí)別算法的研究進(jìn)展學(xué)生：鄧馳林（生物安全科學(xué)技術(shù)學(xué)院生物信息一班級(jí)學(xué)號(hào)：200841634113）摘摘摘摘要要要要：隨著人類基因組計(jì)劃的完成，生物基因數(shù)據(jù)呈指數(shù)形式增長(zhǎng)，找出蛋白質(zhì)編碼基因，即基因識(shí)別，是進(jìn)行基因組分析的基礎(chǔ)，在生物信息處理中占有非常重要的地位。通常的基因識(shí)別方法大致可以分為如下三類：序列相似性方法、從頭預(yù)測(cè)方法、序列相似性和從頭預(yù)測(cè)方法相結(jié)合的第三類方法。由于物種的多樣性，生物基因數(shù)據(jù)的指數(shù)型增長(zhǎng)和人類對(duì)其有限的認(rèn)識(shí)等原因，第一類方法的缺陷不僅速度較慢，而且準(zhǔn)確率不高;相較第一類來(lái)說(shuō)，第二類方法具有更堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，模型的物理意義也更加明顯直觀，而且，在實(shí)驗(yàn)當(dāng)中對(duì)若干基因預(yù)測(cè)軟件的測(cè)試表明，具有最高正確率的幾種基因預(yù)測(cè)軟件都屬于這一種方法。譜分析是信號(hào)處理的常用方法，其中的統(tǒng)計(jì)相關(guān)分析、傅里葉變換、小波變換和數(shù)字濾波等手段已逐漸應(yīng)用到DNA序列的分析中，屬于第二類基因識(shí)別方法。本文是對(duì)前人在生物信息學(xué)方面發(fā)表的數(shù)篇論文進(jìn)行簡(jiǎn)單歸納，并發(fā)表一點(diǎn)自己的看法。關(guān)鍵詞關(guān)鍵詞關(guān)鍵詞關(guān)鍵詞：：：：基因識(shí)別、從頭預(yù)測(cè)法、譜分析一、研究動(dòng)機(jī)與意義隨著人類基因組序列測(cè)序的最終完成，人類進(jìn)入了后基因組時(shí)代，這是人來(lái)歷史上一個(gè)偉大的成就，也是基因組研究的轉(zhuǎn)折點(diǎn)和關(guān)鍵時(shí)刻，意味著人類基因組的研究將全面進(jìn)入信息提取和數(shù)據(jù)分析階段，即生物信息學(xué)發(fā)揮重要作用的階段。生物信息學(xué)是再次背景下發(fā)展起來(lái)的綜合運(yùn)用生物學(xué)、數(shù)學(xué)、物理學(xué)、信息科學(xué)以及計(jì)算機(jī)科學(xué)等諸多科學(xué)的理論方法的嶄新的交叉學(xué)科。生物信息學(xué)是內(nèi)涵非常豐富的學(xué)科，其核心是基因組信息學(xué)，包括基因組信息的獲取、處理、存儲(chǔ)、分配和解釋?；蚪M信息學(xué)的關(guān)鍵是讀懂基因組的核苷酸順序，即全部基因在染色體上的確切位置以及各DNA片段的功能；同時(shí)在發(fā)現(xiàn)了新基因信息之后進(jìn)行蛋白質(zhì)空間結(jié)構(gòu)模擬和預(yù)測(cè)，然后依據(jù)特定蛋白質(zhì)的功能進(jìn)行藥物設(shè)計(jì)。在上述研究中，編碼區(qū)與非編碼區(qū)的識(shí)別即基因識(shí)別，是進(jìn)一步研究DNA和蛋白質(zhì)序列的前提和基礎(chǔ)。核苷酸全序列中一個(gè)個(gè)具有生物功能的片段成為基因，它是生物遺傳信息的載體。非基因部分是不編碼蛋白質(zhì)，與生物性狀無(wú)直接關(guān)系。給定一段DNA序列，一旦編碼區(qū)確定，一級(jí)結(jié)構(gòu)也就清楚了，這位預(yù)測(cè)它的結(jié)構(gòu)與功能奠定了基礎(chǔ)，因而基因識(shí)別也成為生物信息學(xué)的核心問(wèn)題之一。隨著基因組研究和信息技術(shù)的發(fā)展，現(xiàn)代生物學(xué)研究方法在生物研究中發(fā)生了深刻的變化。從生物學(xué)、細(xì)胞生物學(xué)到分子生物學(xué)，現(xiàn)代生物研究更多地依賴信息技術(shù)的分析結(jié)果提供進(jìn)一步研究的線索和依據(jù)，強(qiáng)有力的數(shù)據(jù)處理分析工具成為現(xiàn)代生物科學(xué)研究發(fā)展的關(guān)鍵。生物信息的分析成為計(jì)算機(jī)研究人員的重要課題。在早期，基因識(shí)別的主要手段是基于獲得細(xì)胞或生物的實(shí)驗(yàn)。通過(guò)對(duì)若干種不同基因的同源重組的速率和統(tǒng)計(jì)分析，我們能夠獲知它們?cè)谌旧w上的順序。若進(jìn)行大量類似的分析，我們可以確定各個(gè)基因的大致位置?，F(xiàn)在，由于人類已經(jīng)獲得了巨大數(shù)量的基因組信息，依靠較慢的實(shí)驗(yàn)分析已經(jīng)不能滿足基因識(shí)別的需要，而基于計(jì)算計(jì)算法的基因識(shí)別得到了長(zhǎng)足的發(fā)展，成為了基因識(shí)別的準(zhǔn)確率和性能，成為研究的關(guān)鍵。如果說(shuō)數(shù)據(jù)是生物信息學(xué)處理的原材料，對(duì)它的理解是人們獲得的最終產(chǎn)品，那么，算法就是實(shí)現(xiàn)這個(gè)生產(chǎn)工程的工具，采用更有效的工具是提高生產(chǎn)速率的必然途徑。今天，當(dāng)人們面臨生物數(shù)據(jù)的黑洞的時(shí)候，有效地算法就更顯出其重要性?？梢哉f(shuō)，生物信息學(xué)上的每一個(gè)飛躍，都伴隨著一個(gè)經(jīng)典的算法，而算法上的一個(gè)突破，也往往一位這生物信息學(xué)的一個(gè)進(jìn)展。正因?yàn)槿绱?，算法研究一直是人們研究的重點(diǎn)。二、國(guó)內(nèi)外研究發(fā)展現(xiàn)基因識(shí)別方面的程序在國(guó)外已較成熟，如廣泛應(yīng)用的Grail,Genemark等，其識(shí)別率已經(jīng)相當(dāng)高。但是也存在明顯的缺點(diǎn)：Grail程序嘗嘗丟失較短的外顯子，而且其整合的同源比較算法完全依賴于已知的序列；Genemark使用HMM算法，需要對(duì)一直的基因結(jié)構(gòu)信號(hào)進(jìn)行學(xué)習(xí)或訓(xùn)練，對(duì)那些與學(xué)習(xí)過(guò)的基因結(jié)構(gòu)不大相似的基因，其預(yù)測(cè)效果不佳。國(guó)內(nèi)在基因識(shí)別方面的研究比較之后，目前多為識(shí)別方法的研究和針對(duì)其方法的是研修程序，還未見較成熟的整合多種算法的基因識(shí)別程序。近年來(lái)，主要研究成果有張春霆原始的幾何學(xué)方法，陳潤(rùn)生等的神經(jīng)網(wǎng)絡(luò)方法，孟捷等用加權(quán)距離判別法。三、三種基因識(shí)別算法通常的計(jì)算機(jī)基因識(shí)別方法大致可以分為如下三類：序列相似性方法、從頭預(yù)測(cè)方法、序列相似性和從頭預(yù)測(cè)方法相結(jié)合的第三類方法。3.1序列相似性方法序列相似性方法給予序列保守性的特點(diǎn)，通過(guò)搜索已知的數(shù)據(jù)庫(kù)中與待分析序列的相似性序列來(lái)進(jìn)行比較和判定，并給出標(biāo)注的結(jié)果。這一類方法的基本算法是局部比對(duì)算法，從最基本的Smith-Waterman動(dòng)態(tài)規(guī)劃算法到快速的啟發(fā)式搜索算法FASTA和BLAST，都可以用來(lái)實(shí)現(xiàn)這種基因結(jié)構(gòu)識(shí)別算法。這樣的算法非常多，其利用的生物序列數(shù)據(jù)的類型也各不相同，比如Procrustes，ORFgene，ALN，ICE主要采用蛋白質(zhì)序列作為已知序列進(jìn)行比較，GeneSeger，SIM4采用cDNA數(shù)據(jù)，而EbEST，TAP則采用EST數(shù)據(jù)進(jìn)行比較?？傮w而言，這一類方法的識(shí)別正確率取決于是否存在已知的相似序列：如果存在，則能夠達(dá)到較高的識(shí)別正確率，反之則正確率很低。雖然目前已知的生物序列的數(shù)據(jù)量很大，而且新產(chǎn)生的序列數(shù)據(jù)也與日俱增，但是目前的研究表明，只有大約一半新測(cè)序的基因能夠找到已知的同源基因或蛋白質(zhì)，剩余的基因只能采用其它的方法來(lái)識(shí)別。同時(shí)，由于方法本身的限制，這一類方法不能獲得對(duì)基因結(jié)構(gòu)規(guī)律的認(rèn)識(shí)，這也限制了這一類方法的作用3.2從頭預(yù)測(cè)方法從頭預(yù)測(cè)方法的基本思想是：由于基因比非編碼區(qū)域部分更加保守，因而兩者的統(tǒng)計(jì)特征明顯不同。例如，在真核生物中的編碼序列偏好使用S-W語(yǔ)言，而非編碼區(qū)與序列偏好使用R-Y語(yǔ)言。這樣，基因結(jié)構(gòu)識(shí)別就類似于在噪聲背景中進(jìn)行信號(hào)識(shí)別，可以采用統(tǒng)計(jì)特征來(lái)區(qū)分這兩者。利用這一特性對(duì)未知序列進(jìn)行統(tǒng)計(jì)學(xué)分析可以發(fā)現(xiàn)編碼區(qū)的粗略位置。這一類方法大致有如下兩種實(shí)現(xiàn)方式：第一種實(shí)現(xiàn)方式是尋找序列中所有可能的編碼區(qū)，并以這些可能的編碼區(qū)作為節(jié)點(diǎn)，以節(jié)點(diǎn)之間的相容關(guān)系作為邊，構(gòu)造出一個(gè)五環(huán)圖，然后使用動(dòng)態(tài)規(guī)劃算法從中尋找一條最優(yōu)路徑。這種算法分為兩個(gè)階段：在第一階段，使用編碼區(qū)的統(tǒng)計(jì)特征構(gòu)造得分函數(shù)，并使用者得分函數(shù)為所有可能的編碼區(qū)打分，挑選出其中滿足一定條件的編碼區(qū)片段作為無(wú)環(huán)圖的節(jié)點(diǎn)，并利用編碼區(qū)片段之間的相同性為這些節(jié)點(diǎn)建立連接。算法的第二階段是一個(gè)標(biāo)準(zhǔn)的無(wú)環(huán)圖優(yōu)化問(wèn)題。顯然第一階段中的的得分函數(shù)決定了算法的效果，第二階段的優(yōu)化算法則決定了這個(gè)算法的計(jì)算復(fù)雜度。采用這種實(shí)現(xiàn)方式的算法包括Geneld，F(xiàn)GENE，DAGGER等。從頭預(yù)測(cè)方法的第二種實(shí)現(xiàn)方式則并不顯式地構(gòu)造出無(wú)環(huán)圖，而是建立一個(gè)能夠描述基因結(jié)構(gòu)的Markov模型，其中具有最大出現(xiàn)概率的通路就是可能的基因結(jié)構(gòu)。為了準(zhǔn)確地描述基因的結(jié)構(gòu)，這種Markov模型通常是隱Markov模型。這樣的算法包括GenScan，DENIE，HMMGene，GENEMARK，GeneMark，Hmm以及EHMM等等。與前一種算法相比，這種算法具有更堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，模型的物理意義也更加明顯直觀，而且，對(duì)若干基因預(yù)測(cè)軟件的測(cè)試表明，具有最高正確率的幾種基因預(yù)測(cè)軟件都屬于這一種方法。事實(shí)上它們正是目前人們使用得最為廣泛的幾種基因預(yù)測(cè)軟件。目前，從頭預(yù)測(cè)方法對(duì)較簡(jiǎn)單的序列能夠以較高的正確率識(shí)別出其中的完整基因結(jié)構(gòu)，但是對(duì)復(fù)雜的序列，比如包含多個(gè)基因或者基因結(jié)構(gòu)不規(guī)則的序列，其識(shí)別的準(zhǔn)確率仍然是比較低的3.3序列相似性和從頭預(yù)測(cè)方法相結(jié)由于序列相似性方法和從頭預(yù)測(cè)方法具有明顯的互補(bǔ)性，近年來(lái)，人們又開始研究把這兩類方法結(jié)合起來(lái)的第三類方法。這類方法的思路是把序列相似性信息融合到從頭預(yù)測(cè)的系統(tǒng)中，從而提高對(duì)基因結(jié)構(gòu)識(shí)別的準(zhǔn)確率。比如，GenomeScan就是在GenScan的基礎(chǔ)上加入了蛋白質(zhì)相似性信息得到的新的基因結(jié)構(gòu)識(shí)別軟件，在待識(shí)別的序列存在相似性序列的情況下，它能夠獲得高于后者的識(shí)別正確率。另外的例子包括FGENSH+、FGENSN_C和Twinscan等。然而，由于這一類方法涉及到多種來(lái)源的信息的融合問(wèn)題，而信息融合目前還缺乏公認(rèn)有效地度量指標(biāo)和融合方法，因此，這一類方法在日前還處于研究的階段三、譜分析法譜分析作為信號(hào)處理的常用方法，今年來(lái)也被用于DNA序列的分析。譜分析用于DNA序列分析有自身的優(yōu)勢(shì)，可以將原始數(shù)據(jù)中局部的、潛在的周期性信息變得清晰和可觀察。盡管DNA序列的譜分析已有很多重要結(jié)論，但還未成為主要研究手段。下面對(duì)目前統(tǒng)計(jì)相關(guān)譜、功率譜和傅里葉變換等譜分析方法在DNA序列分析中的應(yīng)用情況作一簡(jiǎn)單介紹4.1DNA序列的統(tǒng)計(jì)相關(guān)分析信號(hào)理論中常用自相關(guān)函數(shù)來(lái)測(cè)量線性關(guān)系和周期性。1992年在DNA序列中發(fā)現(xiàn)了幕律相關(guān)后，自相關(guān)函數(shù)在DNA序列分子中逐漸流行起來(lái)。直接檢測(cè)DNA序列逐漸流行起來(lái)。直接檢測(cè)DNA序列中和尺度無(wú)關(guān)的相關(guān)性，可能對(duì)里金額基因組的組成和進(jìn)化具有深刻意義。文獻(xiàn)［3］定義了自相關(guān)函數(shù)C(L)，研究了它在DNA序列分析中的應(yīng)用，并對(duì)應(yīng)用效果和序列的尺寸限度作了討論。計(jì)算自相關(guān)函數(shù)前先將DNA序列數(shù)值為S=｛X1,X2,…,Xn｝；將DNA序列的四種堿基(A、T、G、C)分成兩類，一類賦值1，另一類賦值0.有幾種可能的分類方法：SW賦值法(C或G賦值1，A或T賦值0)、RY賦值法(A或G賦值1，C或T賦值0)、KM賦值法(G或T賦值1，A或C賦值0)、T賦值法(T賦值1，其它賦值0)、C賦值法(C賦值1，其它賦值0)。其方法得到的結(jié)果是相互獨(dú)立的，反映了DNA序列的不同方面，例如RY賦值法描述了A和G在序列中的分布，而A賦值法只描述A的分布。其中SW賦值法更適合基因范圍的相關(guān)性研究。4.2自相關(guān)函數(shù)在DNA序列中的應(yīng)用自相關(guān)函數(shù)C(l)可作為度量DNA成分不均勻性的一個(gè)特征量，研究表明：DNA序列存在幕律相關(guān)。由于序列是有限長(zhǎng)，計(jì)算結(jié)果受統(tǒng)計(jì)波動(dòng)的影響，這是計(jì)算C(l)中的一個(gè)重要問(wèn)題。C(l)波動(dòng)越大，這在序列相關(guān)性較弱時(shí)會(huì)嚴(yán)重影響計(jì)算結(jié)果。因此直接應(yīng)用C(l)有一定困難，于是提出7C(l)的簡(jiǎn)介應(yīng)用：堿基成分變化的分析、功率譜分析和小波分析等。堿基成分變化分析的過(guò)程為：在序列開始處取長(zhǎng)度為l的窗，計(jì)算窗中的序列總和Si，然后將窗移動(dòng)一格或l格計(jì)算S2,最后計(jì)算這些數(shù)組｛Si｝的方差；對(duì)不同窗長(zhǎng)度l重復(fù)上述過(guò)程。若序列是穩(wěn)態(tài)的，則可通過(guò)來(lái)計(jì)算得到C(l)。功率譜也可用來(lái)間接計(jì)算自相關(guān)函數(shù)，但是要求序列是問(wèn)題的，利用小波分析則可客服這個(gè)限制條件。4.3自相關(guān)分析在基因組中的應(yīng)用原核生物基因組的C(l)研究表明：在短序列中，相關(guān)性受三密碼子組成中的堿基非均勻性控制。而對(duì)于序列，如分支結(jié)核桿菌的基因組，C(l)幾乎為零。值得注意的是，在分支枯草桿菌基因組的很大范圍內(nèi)并不等于零。前者超過(guò)基因特征長(zhǎng)度的行為和隨機(jī)序列相似，也就是說(shuō)基因組特征長(zhǎng)度的行為和隨機(jī)序列相似，也就是說(shuō)基因組在大范圍里是均勻的。但是后一類基因組表現(xiàn)相關(guān)性，說(shuō)明了不均勻性的存在，用密碼子三個(gè)位置處堿基的不均勻含量無(wú)法解釋，可能和其它基因組中成分有差異的積陰德大量橫向轉(zhuǎn)移甚至自然選擇有關(guān)。對(duì)人類基因組，用RY賦值法計(jì)算自相關(guān)函數(shù)，看到有超過(guò)四次的幕指數(shù)相關(guān)，這和短序列中的研究一直。用SW賦值法計(jì)算的C(l)在22條染色體的序列中找到超過(guò)5次系數(shù)的幕律相關(guān)，但這不是人類連續(xù)克隆分析中的普遍行為。這個(gè)染色體中出現(xiàn)的尺度不變的結(jié)構(gòu)，說(shuō)明這可能屬于新基因組，是在進(jìn)化過(guò)程中的更接近時(shí)候出現(xiàn)的。四、譜分析法研究的結(jié)論DNA序列具有高度的復(fù)雜性，通過(guò)譜分析方法可識(shí)別和描述序列的一些特征。統(tǒng)計(jì)相關(guān)分析指出了DNA序列的長(zhǎng)程相關(guān)呈1/f特性，短程相關(guān)強(qiáng)度大，且存在不均勻性，氨基酸內(nèi)部的堿基關(guān)聯(lián)比氨基酸之間的強(qiáng)。分子進(jìn)化必須在核酸序列才能最清楚顯示出來(lái)，序列的相關(guān)性隨著進(jìn)化程度改變，因此統(tǒng)計(jì)相關(guān)分析將成為描述DNA序列的同源性的一種方法。由于傳統(tǒng)的統(tǒng)計(jì)分析不可避免地帶來(lái)隨即漲落，這使得預(yù)測(cè)存在較大誤差。采用光學(xué)小波分析方法可有效地去除漲落引起的高頻“噪音”，是的預(yù)測(cè)更加直觀。但是，