生物序列數(shù)據(jù)比較與模體發(fā)現(xiàn)算法研究.pdf

1、生物信息學(xué)是將計(jì)算機(jī)領(lǐng)域內(nèi)的知識(shí)和技術(shù)應(yīng)用于研究DNA(脫氧核糖核酸)、蛋白質(zhì)等生物學(xué)問題的一個(gè)迅速發(fā)展的學(xué)科領(lǐng)域，而生物序列比較和模式發(fā)現(xiàn)是生物信息學(xué)的傳統(tǒng)課題，在系統(tǒng)進(jìn)化、基因調(diào)控、疾病治療、病毒起源等重要領(lǐng)域的研究中處于核心地位。 近年來，隨著生物測序技術(shù)的突飛猛進(jìn)，生物序列數(shù)據(jù)以前所未有的速度增長。人工分析和處理生物序列數(shù)據(jù)無法再滿足需求，計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，為分析和處理生物序列提供了新的強(qiáng)大手段。本文圍繞生物序

2、列信息比較與模體(motif)發(fā)現(xiàn)算法問題展開研究，完成以下工作： (1)DNA序列模體發(fā)現(xiàn)算法研究DNA序列是最常見的生物序列數(shù)據(jù)，在DNA序列集合中發(fā)現(xiàn)模體的常見方法有統(tǒng)計(jì)學(xué)習(xí)方法和組合優(yōu)化方法。本文圍繞目前最常用的FM(FixednumberofMutation)模體發(fā)現(xiàn)模型展開研究，首先給出一種基于樣本序列比較來組合生成候選模體的方法，然后在此基礎(chǔ)上設(shè)計(jì)出一種新的基于樣本驅(qū)動(dòng)的精確算法，與現(xiàn)有的模式驅(qū)動(dòng)算法相比，在保持精

3、度不變的情況下降低了搜索空間，同時(shí)克服了樣本驅(qū)動(dòng)算法適用面窄的問題。實(shí)驗(yàn)表明，該算法相對(duì)目前最優(yōu)的MITRA(MismatchedTreeAlgorithms)精確算法的性能有了較大的提高。 (2)納米計(jì)算平臺(tái)的生物序列處理研究對(duì)生物序列進(jìn)行比較和在生物序列中發(fā)現(xiàn)模體往往涉及大計(jì)算量，因此并行化的設(shè)計(jì)是必不可少的，但是問題本身的串行處理特性使得并行處理較為困難。目前已提出的一種新的納米計(jì)算平臺(tái)上的系統(tǒng)結(jié)構(gòu)模型——CellMatr

4、ix能較好的解決序列處理問題，其同構(gòu)的二維結(jié)構(gòu)便于生產(chǎn)和擴(kuò)展，用該結(jié)構(gòu)來實(shí)現(xiàn)序列處理算法非常自然。本文實(shí)現(xiàn)了可以輸出比對(duì)結(jié)果的雙序列比對(duì)算法，它克服了CellMatrix模型上已有的雙序列比對(duì)算法只能輸出比對(duì)得分的缺陷；首次在CellMatrix模型上設(shè)計(jì)實(shí)現(xiàn)了生物序列模體發(fā)現(xiàn)算法。并用晶格數(shù)量和晶格延遲兩個(gè)參數(shù)分析了兩個(gè)算法的時(shí)空開銷。 (3)基因組序列的翻轉(zhuǎn)排序并行算法研究基因紐序列在遺傳過程中最常見變異現(xiàn)象為部分子序列翻轉(zhuǎn)

5、。通過對(duì)翻轉(zhuǎn)排序問題串行算法的研究，在PRAM模型和LARPBS模型上分別設(shè)計(jì)出時(shí)間復(fù)雜度為O(lg2n)和O(lgn)的并行計(jì)算有向符號(hào)序列翻轉(zhuǎn)距離算法(n為序列的長度)；同時(shí)在LARPBS模型上設(shè)計(jì)出一個(gè)線性時(shí)間并行翻轉(zhuǎn)排序算法。 (4)計(jì)算基于翻轉(zhuǎn)距離的基因組序列的中值序列(簡稱翻轉(zhuǎn)中值)算法研究計(jì)算基因組序列的中值序列問題是用基因組信息創(chuàng)建生物進(jìn)化樹的基礎(chǔ)。本文將有向符號(hào)序列的翻轉(zhuǎn)中值問題轉(zhuǎn)化為一個(gè)圖論問題，在此基礎(chǔ)上給

6、出一個(gè)時(shí)間復(fù)雜度為O(n2d+1)精確算法，其中n為序列的長度、d為給定序列之間的距離的線性函數(shù)；接著將此算法推廣到類似的計(jì)算基因組重排的中值序列問題；通過對(duì)中值路徑上排列的翻轉(zhuǎn)距離研究，推導(dǎo)出該類排列的性質(zhì)，在其基礎(chǔ)上給出兩個(gè)最壞時(shí)間復(fù)雜度均為O(n2d+1)的分支限界算法，實(shí)驗(yàn)表明，在大多數(shù)情況下算法具有很好的性能。 本文的貢獻(xiàn)與創(chuàng)新之處在于：1、設(shè)計(jì)一種新的DNA序列模體發(fā)現(xiàn)精確算法該算法結(jié)合已有的模式驅(qū)動(dòng)算法和樣本驅(qū)動(dòng)算

7、法特點(diǎn)，并首次在算法中引入序列比較來組合生成候選模體，大大縮小了搜索空間。實(shí)驗(yàn)表明該算法的性能優(yōu)于目前我們已知的最快精確算法。 2、給出計(jì)算有向符號(hào)序列的翻轉(zhuǎn)距離和翻轉(zhuǎn)排序的并行算法首次采用倍增技術(shù)設(shè)計(jì)了計(jì)算有向符號(hào)序列的翻轉(zhuǎn)距離的并行算法；在LARPBS模型上設(shè)計(jì)了使用O(n3)個(gè)處理器時(shí)間復(fù)雜度為O(lgn)的并行連通分量算法；在O(n2)處理器數(shù)目的LARPBS模型上設(shè)計(jì)出翻轉(zhuǎn)排序并行算法，該算法將現(xiàn)有的翻轉(zhuǎn)排序并行算法最