生物序列數據比較與模體發(fā)現算法研究.pdf

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

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

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

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

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

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

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