生物序列比對近似算法及其并行化研究.pdf

1、生物信息學是一門綜合數(shù)學、計算機科學和生物學等學科的交叉學科，是當今科學的研究熱點之一。生物序列比對是生物信息學中的一個基本的、重要的研究問題，是生物信息學的基礎，它是進行系統(tǒng)進化、生態(tài)學、生物保護、疾病控制、病毒起源甚至HIV病毒統(tǒng)計和傳播等方面研究的基本工具，并可用來預測生物序列的功能、結(jié)構(gòu)和進化過程等。所以，進行生物序列比對研究具有重要的理論意義和應用價值。 生物序列比對可分為雙生物序列比對和多生物序列比對。本文在分析生物

2、序列本身的固有特性和常用生物序列比對算法的基礎上，對生物序列比對問題進行了學習和研究，主要研究內(nèi)容包括：(1)基于結(jié)構(gòu)信息預處理的雙生物序列比對算法用于解決雙生物序列比對的常用算法基本上都是用動態(tài)規(guī)劃的方法來逐點計算雙生物序列問的代價，這些方法可以發(fā)現(xiàn)數(shù)學意義上具有最大計分值的比對結(jié)果，但這種比對結(jié)果有時可能忽略了生物序列中所隱含的結(jié)構(gòu)信息。為了在雙序列比對中更好地考慮生物序列的結(jié)構(gòu)信息，本文利用可變長馬爾可夫鏈方法來預測生物序列中所隱

3、含的結(jié)構(gòu)信息，然后再進行雙生物序列的比對，最后給出了一個對經(jīng)典雙生物序列比對的Smith-Waterman算法的修正算法以及一個基于結(jié)構(gòu)信息的啟發(fā)式算法。實驗結(jié)果表明，這可以有效地提高序列比對的準確性。 (2)基于結(jié)構(gòu)信息的多生物序列比對啟發(fā)式算法多生物序列比對是生物序列比對研究中的重點。目前，國際上常用的多序列比對算法一般都是采用漸進比對和迭代比對的方法來設計的，這些多序列比對算法都有其不同的優(yōu)缺點，尤其是在序列間一致性比較低

4、的情況下多序列比對結(jié)果的可信度不高。本文在分析生物序列特征的基礎上，利用可變長馬爾可夫鏈方法來識別多生物序列中的結(jié)構(gòu)信息，并在此基礎上，研究了一個聚類的多序列比對算法。實驗結(jié)果表明，這個算法可以較好的對親緣性比較差的生物序列進行比對，并且可以發(fā)現(xiàn)生物序列問業(yè)已清楚的結(jié)構(gòu)信息。 (3)一種基于熵的多生物序列比對自適應遺傳算法生物序列比對問題最大的障礙在于現(xiàn)在還很難找到一種把生物序列的進化過程進行合理形式化的數(shù)學方法，而遺傳算法能避

5、開問題本身的數(shù)學復雜性，基本不用搜索空間的知識或其它輔助信息來求解問題。所以本文研究用遺傳算法來解決多序列比對問題，并且引入信息論中熵的概念來評價生物序列比對過程中種群的多樣性，提出了一種能綜合考慮生物序列間相似性和結(jié)構(gòu)信息的適應度函數(shù)，用比對過程中熵的動態(tài)變化來自動調(diào)整遺傳算法的交叉和變異概率，并且結(jié)合動態(tài)規(guī)劃算法來設計遺傳操作算子。實驗結(jié)果表明，這個算法具有較強的全局搜索能力和局部搜索能力，并且能有效地克服未成熟收斂問題。

6、(4)生物序列比對并行算法的研究隨著生物技術(shù)的進步和基因組測序的相繼完成，多序列比對問題的計算規(guī)模急劇擴展，現(xiàn)有的一些串行算法已經(jīng)很難跟上序列規(guī)模增大的要求。在實際多序列比對應用中，人們必須要考慮能否將已有的串行算法并行化，或是設計符合實際需要的并行算法，從而大大降低算法運行時間。本文首先介紹了并行算法的一些基本計算模型、雙序列比對中常用的并行算法以及在CellMatrixTM結(jié)構(gòu)上的并行算法，然后在研究多序列比對已有并行算法的基礎上，

7、提出了一個在SMPClusters(SMP集群)上的新的序列搜索并行算法。 本文的貢獻與創(chuàng)新之處主要有：(1)在生物序列比對中結(jié)合了生物序列結(jié)構(gòu)信息，利用可變長馬爾可夫鏈的方法來預測生物序列間的結(jié)構(gòu)信息，提出了一種新的雙序列比對計分機制，并且把這種思想擴展到多序列比對上，提出了一種基于聚類方法的多序列比對方法。 (2)利用遺傳算法來進行多序列比對問題的研究，引入信息論中熵的概念來評價生物序列比對過程中種群的多樣性，提出了