雙序列比對算法綜述

王沛

摘 要：在生物信息學(xué)中，基因序列比對是最基本、最重要的操作。本文首先介紹了序列比對的劃分方式，提出了雙序列比對算法的研究意義；接著對典型的雙序列比對算法的研究現(xiàn)狀進行了較為詳細的闡述，包括算法的原理、對比等；然后通過收集雙序列比對算法的優(yōu)化方案，總結(jié)出當前算法的發(fā)展趨勢，得出結(jié)論。

關(guān)鍵詞：生物信息，序列比對，雙序列比對，動態(tài)規(guī)劃，點陣圖

1 引言

序列比對問題是指將基因序列進行比對，將其中相似性的部分標示出來，通過標示出的序列相似度來確定序列間的同源性關(guān)系。在生物信息學(xué)中，基因序列的比對是最基本、最重要的操作，是進行基因識別、信息分析、結(jié)構(gòu)預(yù)測等問題的前提。本文將介紹一種最基礎(chǔ)的比對方式——雙序列比對。

2 背景與意義

序列比對有多種劃分方式。根據(jù)比對數(shù)量的不同，可分為雙序列比對和多序列比對。雙序列比對即通過兩個基因序列的比對，找到相似的基因片段，從而推測目標基因可能具有的功能以及可能的分子進化關(guān)系。而多序列比對通過多個基因序列的比對，尋找到它們相同的位點、區(qū)域，推測具有共同功能的序列模式。

就序列本身而言，對序列進行整體比對的方式稱為全局比對，對序列進行部分比對的方式稱為局部比對。全局比對適用于總體相似度高的同源序列；局部比對適用于長度差別大、親緣關(guān)系遠的序列，可找出兩條序列中相似度最高的片段。

由于雙序列比對是基因序列比對最早采取的方式，也是生物信息學(xué)最基本的研究方法，所以我決定先從這種最基本的方式入手，了解雙序列比對算法的研究現(xiàn)狀及發(fā)展趨勢，為進一步的學(xué)習(xí)做好鋪墊。

3 雙序列比對算法研究現(xiàn)狀

3.1 典型雙序列比對算法介紹

3.1.1 基于動態(tài)規(guī)劃的雙序列比對算法

Needleman-Wunsch算法

1970年，Needleman和Wunsch最早提出了一種基于動態(tài)規(guī)劃思想的序列全局比對算法：使用迭代的方式求出兩個基因序列之間的對比得分，并把結(jié)果存放在二維得分矩陣里面，然后運用動態(tài)規(guī)劃方法在二維得分矩陣中進行回溯從而找到序列最佳比對路徑，即序列比對的最優(yōu)結(jié)果。

Hirschberg算法

1975年，Hirschberg提出了一種基于動態(tài)規(guī)劃的全局比對算法，采用了分而治之的思想。該算法最大的優(yōu)點是能減少序列聯(lián)配問題的空間需求，其空間復(fù)雜度為O（m+n），但Hirschberg算法的時間需求卻是N.W的兩倍。

Smith-Waterman算法

1981年，Smith和Waterman 提出了一種基于N.W算法的確定局部相似性的動態(tài)規(guī)劃算法，尋找兩條基因序列之間局部范圍內(nèi)的相似性，忽略了匹配區(qū)域之前或之后的錯配。后續(xù)對局部序列比對的研究與改進都是基于本算法進行的。

3.1.2 基于啟發(fā)式的雙序列比對算法

（1）FASTA算法

1985年，Pearson和Lipman共同研究提出了FASTA算法，它是一種 S.W算法的快速近似算法，速度和敏感度介于S.W算法和Blast之間，亦可進行全局比對。

1988年，他們對其進行了改良：序列比對時至少要有一個或一段它們共同擁有的字或片段，將要處理的序列中的所有字編寫成Hash表，以便于數(shù)據(jù)庫的查詢，檢索出有一定關(guān)系的匹配，從而有效地降低查詢命中字的時間。

（2）BLAST算法

1990年，Altschul等人提出了BLAST算法，該算法采用一種短片段匹配算法和一種有效的統(tǒng)計模型來找出目的序列和數(shù)據(jù)庫之間的最佳局部比對效果。這種雙序列局部比對算法被廣泛使用在蛋白質(zhì)DNA序列分析和其他序列相似性比對的問題中。

3.1.3 基于點陣圖的雙序列比對算法

點陣法最早由 Gibb 提出。該算法是在一個坐標中的相應(yīng)位置處進行描點，坐標中兩條序列的連續(xù)相同區(qū)域會形成一條直線。用點陣圖來表示雙序列比對較為直觀。

3.2 典型雙序列比對算法比較

在上述算法中，用于雙序列全局比對的有N.W算法、Hirschberg算法和FASTA算法。其中最早的算法是Needleman-Wunsch算法，它也是最經(jīng)典的雙序列全局比對算法。

而針對局部比對問題，可用的算法有S.W算法、FASTA算法、BLAST算法等。其中最具代表性的雙序列局部比對算法是Smith-Waterman算法，其靈敏度非常高。

如果已知待比較的序列非常相似，一般采用點陣法來比較。因為這種方法可以通過觀察矩陣的對角線，迅速發(fā)現(xiàn)可能的序列比對，并且可以很容易地發(fā)現(xiàn)插入、刪除序列和重復(fù)序列。

但由于絕大多數(shù)點陣計算機程序不能顯示出精確的序列，所以其他兩種算法的使用更為普遍。當序列條數(shù)不太多、序列長度不太長時，建議選擇動態(tài)規(guī)劃算法；當需要進行大規(guī)模序列比對時，啟發(fā)式算法則可得到更優(yōu)的結(jié)果。

4 雙序列比對算法的優(yōu)化

根據(jù)觀察上述算法，我們不難發(fā)現(xiàn)：雙序列比對算法在得到最優(yōu)結(jié)果的同時，普遍存在著增加時間、空間復(fù)雜度的問題，較高的復(fù)雜度是該算法研究的一個難題。為此，在上述典型算法的基礎(chǔ)上，人們陸續(xù)提出了許多改進方法，如：

（1）基于遺傳算法的雙序列比對

由于序列比對問題可以看成是一個組合優(yōu)化問題，而遺傳算法是一種求解大規(guī)模問題的全局性優(yōu)化算法，因此可以用來解決序列比對問題。

在遺傳算法中，存在著幾個關(guān)鍵的設(shè)計：個體編碼方法的設(shè)計，初始種群的設(shè)計，適應(yīng)度函數(shù)的設(shè)計，選擇算子的設(shè)計，遺傳算子的設(shè)計，算法停止準則的設(shè)計。

（2）基于蟻群算法的雙序列比對

蟻群算法是一種現(xiàn)代智能仿生算法，它通過模擬蟻群在覓食過程中尋找最短路徑的方法來求解最優(yōu)化問題。在利用蟻群算法求解 TSP 問題的基礎(chǔ)上，將其算法思想用于求解序列比對問題上。雙序列比對問題可以歸結(jié)于：在分值矩陣中，求解出一條分值最大且路徑最短的問題。

（3）對Needleman-Wunsch算法的分布式并行優(yōu)化

針對高性能計算設(shè)備昂貴、資源有限、N.W算法中比對數(shù)據(jù)存在依賴性的特點，可在MPI編程技術(shù)巧異構(gòu)機群上將算法進行分布式并行化。

該算法將比對得分矩陣進行劃分，通過確定最優(yōu)迭代次數(shù)與子節(jié)點獲得的子序列長度來充分利用各個節(jié)點計算資源，使得計算任務(wù)連續(xù)執(zhí)行?；厮葜胁捎肔IFO通信策略，有效降低算法整體的時間及空間復(fù)雜度。

綜上，雙序列比對主要可通過引入遺傳算法、蟻群算法以及并行分布式的方式對算法進行提速優(yōu)化，目前已有較多研究成果。

5 結(jié)論

本文從雙序列比對入手，首先介紹了序列比對的兩種劃分方式；接著對基于動態(tài)規(guī)劃、基于啟發(fā)式和基于點陣圖的雙序列比對算法的研究現(xiàn)狀進行了較為詳細的闡述；最后，介紹了基于遺傳算法、蟻群算法等優(yōu)化方法，用于解決雙序列比對算法普遍存在的時間、空間復(fù)雜度較大的問題。

另外，在完成論文的過程中，筆者發(fā)現(xiàn)很多優(yōu)化算法都是在已有算法的基礎(chǔ)上，結(jié)合另一種新思想發(fā)展而來。在這個信息技術(shù)高速發(fā)展的時代，利用好身邊的工具，跳出固有思維，不囿于傳統(tǒng)，也許就能有新的收獲。

參考文獻

[1] 汪浩.基因序列比對算法的優(yōu)化研究[D].中國農(nóng)業(yè)科學(xué)院.2015.

[2] 李丹.雙序列比對算法的研究與改進.電子技術(shù)與軟件工程[J]，2017：148.

[3] 范慧.基于遺傳算法的序列比對方法的研究[D].湖南大學(xué)，2012.

[4] 李川.雙序列比對算法研究與并行優(yōu)化[D].西安電子科技大學(xué)，2011.

[5] 馮百龍.雙序列比對Needleman-Wunsch算法的分布式并行優(yōu)化研究[D].內(nèi)蒙古農(nóng)業(yè)大學(xué)，2015.F0C3FF2E-AF10-4176-B2EA-13349B00E34F