生物序列比對算法的研究現(xiàn)狀

楊潔 劉海 湖南信息職業(yè)技術(shù)學(xué)院 410200

生物序列比對算法的研究現(xiàn)狀

楊潔 劉海 湖南信息職業(yè)技術(shù)學(xué)院 410200

本文綜述了生物序列比對的基本思想和主要方法。通過序列比較可以發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)和進(jìn)化的信息。進(jìn)行序列比對的目的是讓人們能夠判斷兩個序列之間是否具有足夠的相似性，從而判定二者之間是否具有同源性。

生物序列；比對；算法

生物序列的比較是計算分子生物學(xué)或生物信息學(xué)中最基本的操作。其作用有：同源性的判斷、相似性的搜索、功能區(qū)的預(yù)測、基因突變的判斷、復(fù)制區(qū)域的判斷等。在分子生物學(xué)中，序列之間的相似性是多方面的，可能是序列之間的相似，可能是結(jié)構(gòu)的相似，也可能是功能的相似。一個普遍的規(guī)律是序列決定結(jié)構(gòu)，結(jié)構(gòu)決定功能。研究序列相似性的目的之一是通過相似的序列得到相似的結(jié)構(gòu)或相似的功能，另一個目的是通過序列的相似性，判別序列之間的同源性，推測序列之間的進(jìn)化關(guān)系。

序列比對有雙序列比對和多序列比對之分,常見的雙序列比對算法點陣圖方法和動態(tài)規(guī)劃算法，而多序列比對算法主要有漸進(jìn)比對和迭代比對兩大類。

1、點陣圖法

點陣圖法[1]的基本思想是通過將一條序列排在上端，另一條序列縱列在左端，兩個序列在任何位置上若出現(xiàn)相同殘基，就在兩個序列對應(yīng)位置上標(biāo)注一個點，做成一個圖。排列成對角線的點列體現(xiàn)出兩條序列間具有相同的字符串，從而形象地表明序列間的相似性，雙序列點陣圖示如圖1所示。

圖1 雙序列點陣圖示

點陣圖法的主要優(yōu)點在于可以找到序列間的所有可能的殘基匹配，但主要的局限是點陣計算機(jī)程序并不能顯示真實的比對排列。

2、動態(tài)規(guī)劃算法

動態(tài)規(guī)劃算法主要有全局排列和局部排列兩大類。

全局排列動態(tài)規(guī)劃算法是由Needleman和Wunsch于1970年首先提出的[2]，算法的基本思想是：用比對的兩條序列構(gòu)建一個相似打分矩陣S，矩陣中的元素可通過公式（1.1）獲得。

例1:對序列a=GCTGATATAGCT,b=GGGTGATTAGCT,選擇參數(shù)s(a,a)=1,s(a,b)=-1，插入刪除單個字母的罰分為2，計算相似打分矩陣S如圖2。

圖2 相似打分矩陣S

根據(jù)上述矩陣可得最優(yōu)比對如圖3所示：

圖3 例1中最優(yōu)比對結(jié)果

局部排列動態(tài)規(guī)劃算法是由Temple Smith 和 Michael Waterman 于1981年提出的，同樣算法也是通過比對的兩條序列構(gòu)建一個相似打分矩陣（記為H），矩陣中的元素Hi,j可通過公式（1.2）獲得。

這里，Hi,j是序列a在位置i和序列b在位置j的分值。w（ai，bj）是序列a位置i和序列b位置j上排列性狀的分值。Wx是序列a中長度為x的間隔罰分，Wy是序列b中長度為y 的間隔罰分。

3、漸進(jìn)比對算法

漸進(jìn)比對算法屬于啟發(fā)式的多序列比對算法。最常見的漸進(jìn)比對算法就是由Feng和Doolittle提出的Clustal算法，Clustal的基本思想是基于相似序列通常具有進(jìn)化相關(guān)性這一假設(shè)。比對過程中，先對所有的序列進(jìn)行兩兩比對并計算它們的相似性分?jǐn)?shù)值，然后根據(jù)相似性分?jǐn)?shù)值將它們分成若干組，并在每組之間進(jìn)行比對，計算相似性分?jǐn)?shù)值。根據(jù)相似性分?jǐn)?shù)值繼續(xù)分組比對，直到得到最終比對結(jié)果。比對過程中，相似程度較高的序列先進(jìn)行比對，而相似性較低的序列則添加在后面。Clustal算法的主要三個步驟如下：

①兩兩比對：先將比對序列進(jìn)行兩兩比對分別構(gòu)建距離矩陣。

②系統(tǒng)發(fā)生樹構(gòu)建：根據(jù)計算所獲得的距離矩陣構(gòu)建系統(tǒng)發(fā)生樹。

③進(jìn)化式比對：對關(guān)系密切的序列進(jìn)行加權(quán)，然后從緊密的兩條序列開始，逐步引入臨近的序列并不斷重新構(gòu)建比對，直到所有序列都被加入為止。

4、迭代比對算法

迭代比對算法的基本思想是基于一個比對算法,通過迭代方式精細(xì)多序列比對,直到比對結(jié)果不再改變?yōu)橹?。根?jù)迭代策略的不同，迭代比對算法大致可分為Prrp法，隱馬爾科夫法，模擬退火法和遺傳算法等。

小結(jié)

進(jìn)行序列比對的目的之一是讓人們能夠判斷兩個序列之間是否具有足夠的相似性，從而判定二者之間是否具有同源性。值得注意的是，相似性和同源性雖然在某種程度上具有一致性，但它們是完全不同的兩個概念：相似性是指一種很直接的數(shù)量關(guān)系，比如部分相同或相似的百分比或其它一些合適的度量；而同源性是指從一些數(shù)據(jù)中推斷出的兩個基因在進(jìn)化上曾具有共同祖先的結(jié)論，它是質(zhì)的判斷?；蛑g要么同源，要么不同源，絕不像相似性那樣具有多或少的數(shù)量關(guān)系。

[1] Gilbert DG. Dot plot sequence comparisons on Macintosh computers. Comput. Appl.Biosci., 1990, 6(2): 117-117;

[2] Smith TF, Waterman MS. Identification of common molecular subsequences. J Mol Biol.1981. 147(1): 195-197.

10.3969/j.issn.1001-8972.2011.09.021