史傳杰

摘 要：隨著人類基因組計(jì)劃（HGP）的實(shí)施，產(chǎn)生了大量的有關(guān)生物體核酸、蛋白質(zhì)等數(shù)據(jù)，如何處理這些呈指數(shù)增長(zhǎng)的數(shù)據(jù)，成為一個(gè)難題。其中，基因序列比對(duì)是生物信息學(xué)中最基本的研究方法之一，科學(xué)家通過(guò)序列比對(duì)，來(lái)研究DNA序列的功能、結(jié)構(gòu)以及物種進(jìn)化信息。本文中提介紹了幾種基因比對(duì)算法，并比較了幾種算法各自的優(yōu)點(diǎn)和缺點(diǎn)。

關(guān)鍵詞：DNA序列對(duì)比，算法;

Abstract： with the implementation of human genome project （HGP）， a large number of biological nucleic acid and protein data have been produced. Among them， gene sequence alignment is one of the most basic research methods in bioinformatics. Scientists use sequence alignment to study the function， structure and evolution information of DNA sequence. In this paper， three gene comparison algorithms are introduced， and their advantages and disadvantages are compared.

Key words： DNA sequence comparison， algorithm;

1 引言

人類基因組計(jì)劃（HGP）是美國(guó)在1990年提出實(shí)施的，自那以后，科學(xué)家已經(jīng)獲取了大量的蛋白質(zhì)、基因序列的數(shù)據(jù)。而隨著基因序列數(shù)據(jù)的激增，使用高效率的算法找出序列之間的相似性和同源性已是迫在眉睫的問(wèn)題。

序列對(duì)比指的是運(yùn)用某種數(shù)學(xué)算法或模型，將兩個(gè)或多個(gè)序列排列在一起進(jìn)行比對(duì)，比較兩條或多條序列堿基，標(biāo)明其相似之處。DNA序列對(duì)比指的是比較兩條或多條DNA序列，展示其相似性和同源性。

目前，國(guó)內(nèi)外DNA雙序列對(duì)比的算法主要有三種：動(dòng)態(tài)規(guī)劃算法、點(diǎn)陣法和詞或k串法[1]。用比較兩條序列之間的相似性的算法有Smith-Waterman算法;用于多條序列之間的比對(duì)的算法有HMM算法;用于搜索擁有相似性或者同源性的算法有Blast算法、Fasta算法等。以下，我將介紹幾種算法：動(dòng)態(tài)規(guī)劃算法、點(diǎn)陣法、基于隱馬爾可夫模型算法、智能計(jì)算等。

2 DNA雙序列比對(duì)算法

2.1打分矩陣

在建立的打分矩陣中，替換矩陣和空位罰分對(duì)矩陣得到的結(jié)果有直接影響?；蛐蛄薪?jīng)過(guò)堿基對(duì)或堿基片段的插入、替換或刪除等，會(huì)產(chǎn)生一系列的變化，因此必須對(duì)每個(gè)堿基對(duì)的插入、替換或刪除進(jìn)行運(yùn)算預(yù)置得分值，而替換矩陣[2]則由這些預(yù)置的得分值構(gòu)成。其中，最基本的打分矩陣是等價(jià)矩陣。

例如，如果兩個(gè)堿基匹配，得分為 1，否則，得分為 0[3]。如下圖：

連續(xù)空位罰分的公式為：W + S x （K-1）。其中，K為連續(xù)出現(xiàn)的空位個(gè)數(shù)，W為起始罰分，S為延伸罰分。

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

動(dòng)態(tài)規(guī)劃算法[4]通常被用于雙序列的比對(duì)，假設(shè)存在兩條序列為ATCG和TGCA，則以兩條序列為橫縱坐標(biāo)，組成一個(gè)矩陣。矩陣的求解包括一個(gè)或多個(gè)大小為（m+1）×（n+1）的表格。 表中的單元格[i，j]與單元格[i-1，j-1]和[i-1，j]，[i，j-1]有關(guān)。其中，m、n表示兩條序列的長(zhǎng)度，i表示行，j表示列。如下圖所示：

可以得到最優(yōu)序列：

動(dòng)態(tài)規(guī)劃算法的空間復(fù)雜度為O（m + n），時(shí)間復(fù)雜度為O（mn）[5]。動(dòng)態(tài)規(guī)劃算法是一種最優(yōu)算法。但與此同時(shí)，動(dòng)態(tài)規(guī)劃算法的不足之處也十分明顯：時(shí)間復(fù)雜度、空間復(fù)雜度高。

2.1.2 點(diǎn)陣法：

在使用點(diǎn)陣法時(shí)，需要先建立里一個(gè)矩陣。以兩條序列M和序列N分別為矩陣的橫軸和縱軸。點(diǎn)陣法是從橫軸序列M的第一個(gè)字符開(kāi)始，沿著矩陣的第一行向第二個(gè)字符移動(dòng)，若縱軸序列N為相同字符，則用陰影標(biāo)記出來(lái)。當(dāng)?shù)谝恍斜容^完成后，到第二行比較，以此類推，直至標(biāo)記完成整個(gè)矩陣。矩陣中的陰影部分表示了兩條序列所有可能的匹配。在圖中，斜對(duì)角線方向的一連串的陰影部分表示為相似區(qū)域，而對(duì)角線以外一些孤立的陰影部分表示隨機(jī)匹配的序列，沒(méi)有任何生物學(xué)意義。

假設(shè)序列M=CCTGAATCGA，序列N=CCTGAAGCAC

如下圖：

優(yōu)點(diǎn)：點(diǎn)陣法可以直觀的表示出兩個(gè)序列之間所有可能的匹配。

缺點(diǎn)：點(diǎn)陣法得到的比對(duì)結(jié)果不夠精確，并且點(diǎn)陣法只適用于較短的兩個(gè)序列，而面對(duì)如今數(shù)據(jù)量龐大的生物序列數(shù)據(jù)明顯存在著缺陷[6]。

3 DNA多序列比對(duì)算法

3.1漸進(jìn)比對(duì)

漸進(jìn)比對(duì)算法[7]是將多序列比對(duì)轉(zhuǎn)化為雙序列比對(duì)，之后將雙序列比對(duì)的結(jié)果進(jìn)行整理，進(jìn)而得到最終的結(jié)果。

目前大多數(shù)多序列比對(duì)算法都是采用了漸進(jìn)比對(duì)算法。漸進(jìn)比對(duì)算可以簡(jiǎn)述為有n個(gè)序列需要比對(duì)。先比較最近的兩條序列，然后將兩條序列比對(duì)的結(jié)果和接下來(lái)的一條進(jìn)行比對(duì)。

例如：第一步：將x序列和x+1序列條先行進(jìn)行比對(duì)，得到結(jié)果y序列;

第二步：將y序列和x+2序列進(jìn)行比對(duì)，得到y(tǒng)1序列;

重復(fù)上述第二步過(guò)程，直到比較完所有需要比對(duì)的序列。

如果序列條數(shù)n相對(duì)較小，則初始比對(duì)中產(chǎn)生的錯(cuò)誤越小。反之，序列條數(shù)n越大，則在初始比對(duì)中產(chǎn)生的錯(cuò)誤多，甚至序列無(wú)法繼續(xù)比對(duì)。

3.2迭代比對(duì)、啟發(fā)式對(duì)比

迭代比對(duì)算法是基于局部最優(yōu)思想的比對(duì)算法。迭代比對(duì)算法是用動(dòng)態(tài)規(guī)劃的方法來(lái)改正漸進(jìn)算法中發(fā)生的偏差。以此來(lái)得到較高的得分。相對(duì)于迭代對(duì)比算法，啟發(fā)式算法同樣使用動(dòng)態(tài)規(guī)劃算法，但啟發(fā)式算法得出的結(jié)果是最優(yōu)的多序列比對(duì)結(jié)果。

4基于隱馬爾可夫模型的算法

隱馬爾可夫模型可以被用于多序列基因的測(cè)定。隱馬爾可夫模型可以用于模擬生物DNA基因序列的插入、缺失、突變以及匹配的過(guò)程。生物的DNA序列可以看成有一個(gè)原始的DNA序列，經(jīng)過(guò)若干基因序列或片段的插入、突變、刪除而得到。因此隱馬爾可夫模型在生物DNA基因序列比對(duì)中得到了廣泛的應(yīng)用。

在DNA的多重序列對(duì)比中，可以將隱馬爾可夫模型看做在DNA序列上前進(jìn)，從某個(gè)狀態(tài)開(kāi)始進(jìn)入插入或刪除或匹配。如果插入或匹配，則產(chǎn)生一個(gè)新的堿基序列;如果刪除，則返回到前一個(gè)堿基。當(dāng)這個(gè)狀態(tài)結(jié)束后，則進(jìn)行到下一個(gè)狀態(tài)，在下一個(gè)狀態(tài)中重復(fù)如上操作。

當(dāng)馬爾可夫鏈從開(kāi)始狀態(tài)到結(jié)束狀態(tài)后，我們便可以得到一條由A、G、C、T四個(gè)字母組成的基因序列和一條看不見(jiàn)的狀態(tài)序列。

優(yōu)點(diǎn)：模型中的每一個(gè)位置都考慮了所有的殘基的分布，能夠有效地修復(fù)DNA序列演變中的殘基的缺失。

缺點(diǎn)：隱馬爾可夫模型需要大量的相似的DNA序列進(jìn)行比對(duì)，需要占有大量的資源。

5智能計(jì)算

在DNA基因?qū)Ρ鹊闹悄苡?jì)算方面，常見(jiàn)的算法有粒子群算法（PSO），遺傳算法（GA），模擬退火算法（SA）。[8]

5.1粒子群算法

粒子群算法在設(shè)計(jì)上比較簡(jiǎn)單，計(jì)算量也相對(duì)較小，收斂速度較快。相對(duì)于其他算法，對(duì)適應(yīng)函數(shù)沒(méi)有求導(dǎo)的要求，因此計(jì)算更加簡(jiǎn)單效率。但是這種算法由于搜索的隨機(jī)性不夠，容易陷入局部最優(yōu)。

5.2遺傳算法

遺傳算法初始值范圍較廣，避免了局部最優(yōu)的問(wèn)題，并且減少了計(jì)算次數(shù)，從而降低了運(yùn)算難度。但此算法容易由于過(guò)早的收斂性而得到一個(gè)局部最優(yōu)。此外，初始值的范圍設(shè)定也決定了計(jì)算的難度。

5.3模擬退火算法

模擬退火算法是圍繞著“產(chǎn)生新的序列→計(jì)算當(dāng)前的序列與新的序列之差→判斷是否接受新的序列→接受或舍棄新的序列”這個(gè)過(guò)程迭代的。這種算法存在的問(wèn)題是計(jì)算的效率低，速度慢。

3 結(jié)論

本文主要介紹了幾種用于DNA基因序列比對(duì)的算法。隨著人類基因組計(jì)劃（HGP）的進(jìn)行與實(shí)施，由此而來(lái)的大量DNA序列等遺傳物質(zhì)等待著科學(xué)家們通過(guò)序列比對(duì)，來(lái)研究DNA序列的功能、蛋白質(zhì)的結(jié)構(gòu)以及物種進(jìn)化得信息。本文總結(jié)并希望為研究人員提供合適的比較分析工具提供參考。

參考文獻(xiàn)：

[1]曹雪卉.DNA詞序列比對(duì)及應(yīng)用[D]. 哈爾濱工業(yè)大學(xué)，碩士學(xué)位論文 2013：1-2

[2]Paten B， Earl D， Nguyen N， et al. Cactus： Algorithms for genome multiple sequence alignment[J]. Genome research， 2011， 21（9）： 1512-1528.

[3]Aniba? M? R，? Poch? O，? Marchler-Bauer? A，? et? al.? AlexSys：? a knowledge-based expert? system? for? multiple? sequence? alignment? construction? and? analysis[J].? Nucleic acids research， 2010， 38（19）： 6338-6349.

[4]Sarkar? S，? Kulkarni? G? R，? Pande? P? P，? et? al.? Network-on-Chip? hardware accelerators? for? biological? sequence? alignment[J].? Computers，? IEEE? Trans actions on， 2010， 59（1）： 29-41.

[5]唐玉榮，汪懋華.基于動(dòng)態(tài)規(guī)劃的快速序列比對(duì)算法[R].生物數(shù)學(xué)學(xué)報(bào)2005.8：207-212

[6]Sery O. Enhanced Property Specification and Verification in BLAST[J]. Fundamental Approaches to Software Engineering， Proceedings，2009（5503）：456-469