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

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

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

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

生物序列；比對(duì)；算法

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

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

1、點(diǎn)陣圖法

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

圖1 雙序列點(diǎn)陣圖示

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

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

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

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

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

圖2 相似打分矩陣S

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

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

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

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

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

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

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

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

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

4、迭代比對(duì)算法

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

小結(jié)

進(jìn)行序列比對(duì)的目的之一是讓人們能夠判斷兩個(gè)序列之間是否具有足夠的相似性，從而判定二者之間是否具有同源性。值得注意的是，相似性和同源性雖然在某種程度上具有一致性，但它們是完全不同的兩個(gè)概念：相似性是指一種很直接的數(shù)量關(guān)系，比如部分相同或相似的百分比或其它一些合適的度量；而同源性是指從一些數(shù)據(jù)中推斷出的兩個(gè)基因在進(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