生物信息學(xué)中的序列相似性比對(duì)算法.pdf

1、序列相似性比對(duì)是生物信息學(xué)中基本的信息處理方法，它對(duì)于發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)和進(jìn)化的信息具有非常重要的意義。主要思想就是運(yùn)用某種特定的數(shù)學(xué)模型或算法，找出兩個(gè)或多個(gè)序列之間的最大匹配堿基或殘基數(shù)，比對(duì)的結(jié)果反映了算法在多大程度上反映了序列之間的相似性關(guān)系以及它們的生物學(xué)特征。因此，生物信息學(xué)中分析的序列相似性比對(duì)的簡(jiǎn)單有效算法一直是生物學(xué)家關(guān)心的問題，序列比對(duì)也是計(jì)算生物學(xué)中解決象序列裝配，進(jìn)化樹重構(gòu)及基因組分析等眾多問題的第一步。

2、進(jìn)行序列相似性比對(duì)的算法很多，而這些算法大多數(shù)都是基于動(dòng)態(tài)規(guī)劃算法，只是在其基礎(chǔ)上進(jìn)行了不同程度的改進(jìn)而已。根據(jù)同時(shí)比對(duì)的序列數(shù)目的不同，將序列相似性比對(duì)算法分成雙序列相似性比對(duì)算法和多序列相似性比對(duì)算法。 本文在第二章前三節(jié)詳細(xì)地介紹了這些基于動(dòng)態(tài)規(guī)劃算法的序列相似性比對(duì)算法。所有這些算法有個(gè)共同的特點(diǎn)：算法是字符串比較算法，序列的比較是字符上的比較，它們的差異性體現(xiàn)在彼此間存在不同的子序列或子結(jié)構(gòu)，而相似性體現(xiàn)在它們有共同

3、的子序列或子結(jié)構(gòu)，因此我們很自然的會(huì)想到尋找生物序列的最長(zhǎng)公共子序列，這就是所謂的LCS問題。近兩年國(guó)內(nèi)外一些學(xué)者給出了DNA序列的圖形表示，用幾何的方法比較生物序列，這些理論已經(jīng)基本成熟。我們?cè)诘谒墓?jié)介紹了DNA序列圖形表示的相關(guān)理論并給出了一種基于二維圖形表示的尋找生物序列和生物結(jié)構(gòu)的最長(zhǎng)公共子序列的算法，該算法簡(jiǎn)單并可視化。很適合用于生物序列的比較和分析。在第三章給出了用于尋找mRNA序列和蛋白序列的最優(yōu)局部對(duì)比和全局對(duì)比的對(duì)比算