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

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

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

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

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

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

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