DNA基因序列快速比對算法

史傳杰

摘 要：隨著人類基因組計劃（HGP）的實施，產生了大量的有關生物體核酸、蛋白質等數據，如何處理這些呈指數增長的數據，成為一個難題。其中，基因序列比對是生物信息學中最基本的研究方法之一，科學家通過序列比對，來研究DNA序列的功能、結構以及物種進化信息。本文中提介紹了幾種基因比對算法，并比較了幾種算法各自的優點和缺點。

關鍵詞：DNA序列對比，算法;

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 引言

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

序列對比指的是運用某種數學算法或模型，將兩個或多個序列排列在一起進行比對，比較兩條或多條序列堿基，標明其相似之處。DNA序列對比指的是比較兩條或多條DNA序列，展示其相似性和同源性。

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

2 DNA雙序列比對算法

2.1打分矩陣

在建立的打分矩陣中，替換矩陣和空位罰分對矩陣得到的結果有直接影響。基因序列經過堿基對或堿基片段的插入、替換或刪除等，會產生一系列的變化，因此必須對每個堿基對的插入、替換或刪除進行運算預置得分值，而替換矩陣[2]則由這些預置的得分值構成。其中，最基本的打分矩陣是等價矩陣。

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

連續空位罰分的公式為：W + S x （K-1）。其中，K為連續出現的空位個數，W為起始罰分，S為延伸罰分。

2.1.1 動態規劃算法：

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

可以得到最優序列：

動態規劃算法的空間復雜度為O（m + n），時間復雜度為O（mn）[5]。動態規劃算法是一種最優算法。但與此同時，動態規劃算法的不足之處也十分明顯：時間復雜度、空間復雜度高。

2.1.2 點陣法：

在使用點陣法時，需要先建立里一個矩陣。以兩條序列M和序列N分別為矩陣的橫軸和縱軸。點陣法是從橫軸序列M的第一個字符開始，沿著矩陣的第一行向第二個字符移動，若縱軸序列N為相同字符，則用陰影標記出來。當第一行比較完成后，到第二行比較，以此類推，直至標記完成整個矩陣。矩陣中的陰影部分表示了兩條序列所有可能的匹配。在圖中，斜對角線方向的一連串的陰影部分表示為相似區域，而對角線以外一些孤立的陰影部分表示隨機匹配的序列，沒有任何生物學意義。

假設序列M=CCTGAATCGA，序列N=CCTGAAGCAC

如下圖：

優點：點陣法可以直觀的表示出兩個序列之間所有可能的匹配。

缺點：點陣法得到的比對結果不夠精確，并且點陣法只適用于較短的兩個序列，而面對如今數據量龐大的生物序列數據明顯存在著缺陷[6]。

3 DNA多序列比對算法

3.1漸進比對

漸進比對算法[7]是將多序列比對轉化為雙序列比對，之后將雙序列比對的結果進行整理，進而得到最終的結果。

目前大多數多序列比對算法都是采用了漸進比對算法。漸進比對算可以簡述為有n個序列需要比對。先比較最近的兩條序列，然后將兩條序列比對的結果和接下來的一條進行比對。

例如：第一步：將x序列和x+1序列條先行進行比對，得到結果y序列;

第二步：將y序列和x+2序列進行比對，得到y1序列;

重復上述第二步過程，直到比較完所有需要比對的序列。

如果序列條數n相對較小，則初始比對中產生的錯誤越小。反之，序列條數n越大，則在初始比對中產生的錯誤多，甚至序列無法繼續比對。

3.2迭代比對、啟發式對比

迭代比對算法是基于局部最優思想的比對算法。迭代比對算法是用動態規劃的方法來改正漸進算法中發生的偏差。以此來得到較高的得分。相對于迭代對比算法，啟發式算法同樣使用動態規劃算法，但啟發式算法得出的結果是最優的多序列比對結果。

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

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

在DNA的多重序列對比中，可以將隱馬爾可夫模型看做在DNA序列上前進，從某個狀態開始進入插入或刪除或匹配。如果插入或匹配，則產生一個新的堿基序列;如果刪除，則返回到前一個堿基。當這個狀態結束后，則進行到下一個狀態，在下一個狀態中重復如上操作。

當馬爾可夫鏈從開始狀態到結束狀態后，我們便可以得到一條由A、G、C、T四個字母組成的基因序列和一條看不見的狀態序列。

優點：模型中的每一個位置都考慮了所有的殘基的分布，能夠有效地修復DNA序列演變中的殘基的缺失。

缺點：隱馬爾可夫模型需要大量的相似的DNA序列進行比對，需要占有大量的資源。

5智能計算

在DNA基因對比的智能計算方面，常見的算法有粒子群算法（PSO），遺傳算法（GA），模擬退火算法（SA）。[8]

5.1粒子群算法

粒子群算法在設計上比較簡單，計算量也相對較小，收斂速度較快。相對于其他算法，對適應函數沒有求導的要求，因此計算更加簡單效率。但是這種算法由于搜索的隨機性不夠，容易陷入局部最優。

5.2遺傳算法

遺傳算法初始值范圍較廣，避免了局部最優的問題，并且減少了計算次數，從而降低了運算難度。但此算法容易由于過早的收斂性而得到一個局部最優。此外，初始值的范圍設定也決定了計算的難度。

5.3模擬退火算法

模擬退火算法是圍繞著“產生新的序列→計算當前的序列與新的序列之差→判斷是否接受新的序列→接受或舍棄新的序列”這個過程迭代的。這種算法存在的問題是計算的效率低，速度慢。

3 結論

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

參考文獻：

[1]曹雪卉.DNA詞序列比對及應用[D]. 哈爾濱工業大學，碩士學位論文 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]唐玉榮，汪懋華.基于動態規劃的快速序列比對算法[R].生物數學學報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