資源描述：
《生物序列數(shù)據(jù)比較與模體發(fā)現(xiàn)算法研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、中國科學(xué)技術(shù)大學(xué)博士學(xué)位論文生物序列數(shù)據(jù)比較與模體發(fā)現(xiàn)算法研究姓名：沈一飛申請學(xué)位級別：博士專業(yè)：計算機軟件與理論指導(dǎo)教師：陳國良20060501摘要生物信息學(xué)是將計算機領(lǐng)域內(nèi)的知識和技術(shù)應(yīng)用于研究DNA(脫氧核糖核酸)、蛋白質(zhì)等生物學(xué)問題的一個迅速發(fā)展的學(xué)科領(lǐng)域，而生物序列比較和模式發(fā)現(xiàn)是生物信息學(xué)的傳統(tǒng)課題，在系統(tǒng)進化、基因調(diào)控、疾病治療、病毒起源等重要領(lǐng)域的研究中處于核心地位。、近年來，隨著生物測序技術(shù)的突飛猛進，生物序列數(shù)據(jù)以前所未有的速度增長。人工分析和處理生物序列數(shù)據(jù)無法再滿足需求，計算機和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，為分析和處理生
2、物序列提供了新的強大手段。本文圍繞生物序列信息比較與模體(motif)發(fā)現(xiàn)算法問題展開研究，完成以下工作：(1)DNA序列模體發(fā)現(xiàn)算法研究DNA序列是最常見的生物序列數(shù)據(jù)，在DNA序列集合中發(fā)現(xiàn)模體的常見方法有統(tǒng)計學(xué)習(xí)方法和組合優(yōu)化方法。本文圍繞目前最常用的FM(FixednumberofMutation)模體發(fā)現(xiàn)模型展開研究，首先給出一種基于樣本序列比較來組合生成候選模體的方法，然后在此基礎(chǔ)上設(shè)計出一種新的基于樣本驅(qū)動的精確算法，與現(xiàn)有的模式驅(qū)動算法相比，在保持精度不變的情況下降低了搜索空間，同時克服了樣本驅(qū)動算法適用面窄的問題。實驗
3、表明，該算法相對目前最優(yōu)的MITRA(MismatchedTreeAlgorithms)精確算法的性能有了較大的提高。(2)納米計算平臺的生物序列處理研究對生物序列進行比較和在生物序列中發(fā)現(xiàn)模體往往涉及大計算量，因此并行化的設(shè)計是必不可少的，但是問題本身的串行處理特性使得并行處理較為困難。目前已提出的一種新的納米計算平臺上的系統(tǒng)結(jié)構(gòu)模型——CellMatrix能較好的解決序列處理問題，其同構(gòu)的二維結(jié)構(gòu)便于生產(chǎn)和擴展，用該結(jié)構(gòu)來實現(xiàn)序列處理算法非常自然。本文實現(xiàn)了可以輸出比對結(jié)果的雙序列比對算法，它克服了CellMatrix模型上已有的雙
4、序列比對算法只能輸出比對得分的缺陷；首次在CellMatrix模型上設(shè)計實現(xiàn)了生物序列模體發(fā)現(xiàn)算法。并用晶格數(shù)量和晶格延遲兩個參數(shù)分析了兩個算法的時空開銷。(3)基因組序列的翻轉(zhuǎn)排序并行算法研究基因組序列在遺傳過程中最常見變異現(xiàn)象為部分子序列翻轉(zhuǎn)。通過對翻轉(zhuǎn)排序問題串行算法的研究，在PRAM模型和LARPBS模型上分別設(shè)計出時間復(fù)雜度為O(192，z)和0(19，z)的并行計算有向符號序列翻轉(zhuǎn)距離算法(訂為序列的長度)；同時在LARPBS模型上設(shè)計出一個線性時間并行翻轉(zhuǎn)排序算法。摘受中岡科學(xué)技術(shù)人學(xué)博㈠．--“7-‘-位論義；(4)計算
5、基于翻轉(zhuǎn)距離的基因組序列的中值序列(簡稱翻轉(zhuǎn)中值)算法研究計算基因組序列的中值序列問題是用基因組信息創(chuàng)建生物進化樹的基礎(chǔ)。本文將有向符號序列的翻轉(zhuǎn)中值問題轉(zhuǎn)化為一個圖論問題，在此基礎(chǔ)上給出一個時間復(fù)雜度為O(n馴+1)精確算法，其中1l為序列的長度、d為給定序列之間的距離的線性函數(shù)：接著將此算法推廣到類似的計算基因組重排的中值序列問題；通過對中值路徑上排列的翻轉(zhuǎn)距離研究，推導(dǎo)出該類排列的性質(zhì)，在其基礎(chǔ)上給出兩個最壞時間復(fù)雜度均為o(i12d+I)的分支限界算法，實驗表明，在大多數(shù)情況下算法具有很好的性能。本文的貢獻與創(chuàng)新之處在于：1、設(shè)
6、計一種新的DNA序列模體發(fā)現(xiàn)精確算法該算法結(jié)合已有的模式驅(qū)動算法和樣本驅(qū)動算法特點，并首次在算法中引入序列比較來組合生成候選模體，大大縮小了搜索空間。實驗表明該算法的性能優(yōu)于目前我們已知的最快精確算法。2、給出計算有向符號序列的翻轉(zhuǎn)距離和翻轉(zhuǎn)排序的并行算法首次采用倍增技術(shù)設(shè)計了計算有向符號序列的翻轉(zhuǎn)距離的并行算法；在LARPBS模型上設(shè)計了使用O(n3)個處理器時間復(fù)雜度為D(19，z)的并行連通分量算法；在O(n!)處理器數(shù)目的LARPBS模型上設(shè)計出翻轉(zhuǎn)排序并行算法，該算法將現(xiàn)有的翻轉(zhuǎn)排序并行算法最快時間復(fù)雜度由O(nlgn)降低到
7、D(，2)。3、提出計算基于翻轉(zhuǎn)操作的有向符號序列中值序列精確算法提出目前最好的精確算法，將時間復(fù)雜度O(n3‘)降為O(n2州)，其中d斂。設(shè)計了計算基于翻轉(zhuǎn)操作的有向符號序列分支限界算法，其最壞情況下時間復(fù)雜度為O(n2水1)，比起直接計算方法，它極大降低了搜索空間規(guī)模，試驗表明分支限界算法具有優(yōu)異的性能。關(guān)鍵詞：生物模體發(fā)現(xiàn)，基因組重排，翻轉(zhuǎn)排序，翻轉(zhuǎn)中值，并行算法，納米計算，序列比對。ABSTRACTBeingoneoftheacadenaicareasthatdeveloprapidly,Bioinfonnaticsusesk
8、nowledgeillcomputersciencetOsolvebiologyproblenlsconcerningDNA，proteinetc．Bio．sequencecomparisouandlnot
