王沛

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

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

1 引言

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

2 背景與意義

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

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

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

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

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

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

Needleman-Wunsch算法

1970年，Needleman和Wunsch最早提出了一種基于動(dòng)態(tài)規(guī)劃思想的序列全局比對算法：使用迭代的方式求出兩個(gè)基因序列之間的對比得分，并把結(jié)果存放在二維得分矩陣?yán)锩妫缓筮\(yùn)用動(dòng)態(tài)規(guī)劃方法在二維得分矩陣中進(jìn)行回溯從而找到序列最佳比對路徑，即序列比對的最優(yōu)結(jié)果。

Hirschberg算法

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

Smith-Waterman算法

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

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

（1）FASTA算法

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

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

（2）BLAST算法

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

3.1.3 基于點(diǎn)陣圖的雙序列比對算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

該算法將比對得分矩陣進(jìn)行劃分，通過確定最優(yōu)迭代次數(shù)與子節(jié)點(diǎn)獲得的子序列長度來充分利用各個(gè)節(jié)點(diǎn)計(jì)算資源，使得計(jì)算任務(wù)連續(xù)執(zhí)行。回溯中采用LIFO通信策略，有效降低算法整體的時(shí)間及空間復(fù)雜度。

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

5 結(jié)論

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

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

參考文獻(xiàn)

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

[2] 李丹.雙序列比對算法的研究與改進(jìn).電子技術(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