資源描述：
《試析生物序列比對算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、。j}目差童文等’學(xué)位論文生物序列比對算法研究單位代碼：10019學(xué)號(hào)：B02383ResearchOnbiologysequencealignmentAlgorithms研究生：指導(dǎo)教師：合作指導(dǎo)教師：周志堅(jiān)傅澤田教授王濤研究員申請學(xué)位門類級(jí)別：墨堂豎生農(nóng)業(yè)機(jī)械化工程生物信息掌工學(xué)院2007年05月5乳乳弱皓級(jí)踮漠；叭分密v上稱向院名方學(xué)業(yè)究在專研所摘要隨著多種基因組計(jì)劃的逐步實(shí)施，產(chǎn)生的有關(guān)核酸、蛋白質(zhì)序列和結(jié)構(gòu)的“海量”數(shù)據(jù)，對生物信息學(xué)研究既是機(jī)遇也是挑戰(zhàn)．企圖完全通過生物實(shí)驗(yàn)的方法來確定所有序列的結(jié)構(gòu)、功能非常困難，同時(shí)也不經(jīng)濟(jì)。因
2、而利用序列比對尋找與功能未知序列同源的已知序列，用己知預(yù)測未知就顯得尤為重要。在這個(gè)過程中，提高序列比對的有效性、減少運(yùn)行時(shí)間和存儲(chǔ)空間具有重要的理論意義和實(shí)用價(jià)值。本文利用動(dòng)態(tài)規(guī)劃，概率統(tǒng)計(jì)等方法對多序列比對問題進(jìn)行了研究．在理論方面：提出了相對多序列比對差異性、壓縮矩陣等概念；對算法中部分迭代公式進(jìn)行了歸納、抽象．給出了基于壓縮矩陣的表達(dá)遞推形式。在算法方面：設(shè)計(jì)了具有監(jiān)控機(jī)制的多序列比對遺傳算法；提出了多序列比對的剎面廣義相關(guān)隱馬爾可夫模型。主要工作和研究成果如下：1．為了描述一個(gè)多序列比對是否具有某種特征統(tǒng)計(jì)特性，提出了多序列比對相對
3、于某己知特征統(tǒng)計(jì)矩陣的代價(jià)概念，并給出了具體定義．在此基礎(chǔ)上，定義了一組多序列比對差異性量化指標(biāo)，用于種群多樣性判別。2．針對多序列比對的遺傳算法中缺少利用已知種群先驗(yàn)信息的問題，提出了一種利用種群多樣性監(jiān)控、指導(dǎo)多序列比對的遺傳算法執(zhí)行步驟的比對算法．結(jié)果表明，新算法在避免局部最優(yōu)解方面有較好的表現(xiàn)，且比對結(jié)果宜具有區(qū)塊性。3．針對剖面隱馬爾可夫模型中狀態(tài)轉(zhuǎn)換及符號(hào)輸出的特性，以及目前基于此模型的迭代表達(dá)公式過于繁瑣的問題，提出了壓縮矩陣、向前、向后概率向量等概念。其中狀態(tài)壓縮矩陣是由一個(gè)階數(shù)為3(L+1)×3(L+1)的矩陣壓縮后得到的階
4、數(shù)為9×(￡+1)的矩陣(L為正整數(shù))。且保留原有矩陣的全部信息。顯然，原矩陣階數(shù)越大，壓縮矩陣節(jié)省的存儲(chǔ)空間就越多，為編程實(shí)現(xiàn)提供了節(jié)省存儲(chǔ)空間的理論依據(jù)．此外，給出了基于壓縮矩陣表示的遞推關(guān)系式，使迭代過程直觀化、模塊化。易于編程實(shí)現(xiàn)．4．針對割砸隱馬爾可夫模型沒有考慮輸出的觀測字符依賴前一時(shí)刻輸出的觀測字符，而生物序列中的字符實(shí)際上又不是相互獨(dú)立的這一矛盾，將語音識(shí)別領(lǐng)域的雙重分次約束隱馬爾可夫模型用于多序列比對，建立了用于多序列比對的剖面廣義相關(guān)隱馬爾可夫模型，新模型更符合生物序列固有的特性。5，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于Windows操作
5、系統(tǒng)的序列比對系統(tǒng)。該系統(tǒng)采用VB6．0和EXCEL進(jìn)行開發(fā)·系統(tǒng)界面友好，操作簡單．有便捷的工具欄、系統(tǒng)菜單、幫助等模塊。為研究、利用多序列比對人員提供了一個(gè)平臺(tái)．關(guān)鍵詞：生物信息學(xué)，多序列比對，遺傳算法，跨馬爾可夫模型，剖面隱馬爾可夫模型AbstractDataconcerningwithsequencesandstructuresofDNAandproteinhasascendedexponentiallynowadays,withthegraduallyimplementingoftheHumanGenuineProjectThehu
6、gebioinformaticedatabasebringsupa∞Vc"challengetotheexistedmethodsandabilityofdataprocess噸．TheworkOnbiolnformalicemainlyaimsatdiggingoutthevaluablebioinformatics00dis∞VcffunctionalandstructuralknowledgerationallyinDNAandproteinsequences．Presentlythetechniquesofgenelocating．r
7、epetitivesequencesearch,andgenegroupsplicingareallbasedOnthesequencealigment,whichdemonstratesthesigl吐矗髓n∞ofimprovingsequencealigmentveracityandrunningefficiency．Mainresearchesinthepaperareoomultiplesequencealigmembyemployingdynamicpro舢ming．probabilityandstatistics．The∞州譬州佃
8、sofdifferencesandcompressmatrixformultiplesequencealigmentaredescribedfirst．Andthe
