生物序列比對算法的研究現狀

楊潔 劉海 湖南信息職業技術學院 410200

生物序列比對算法的研究現狀

楊潔 劉海 湖南信息職業技術學院 410200

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

生物序列；比對；算法

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

序列比對有雙序列比對和多序列比對之分,常見的雙序列比對算法點陣圖方法和動態規劃算法，而多序列比對算法主要有漸進比對和迭代比對兩大類。

1、點陣圖法

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

圖1 雙序列點陣圖示

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

2、動態規劃算法

動態規劃算法主要有全局排列和局部排列兩大類。

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

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

圖2 相似打分矩陣S

根據上述矩陣可得最優比對如圖3所示：

圖3 例1中最優比對結果

局部排列動態規劃算法是由Temple Smith 和 Michael Waterman 于1981年提出的，同樣算法也是通過比對的兩條序列構建一個相似打分矩陣（記為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、漸進比對算法

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

①兩兩比對：先將比對序列進行兩兩比對分別構建距離矩陣。

②系統發生樹構建：根據計算所獲得的距離矩陣構建系統發生樹。

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

4、迭代比對算法

迭代比對算法的基本思想是基于一個比對算法,通過迭代方式精細多序列比對,直到比對結果不再改變為止。根據迭代策略的不同，迭代比對算法大致可分為Prrp法，隱馬爾科夫法，模擬退火法和遺傳算法等。

小結

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

[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