基于動(dòng)態(tài)規(guī)劃的基因雙序列比對(duì)研究

羅志兵

（西南林業(yè)大學(xué)大數(shù)據(jù)與智能工程學(xué)院，昆明 650224）

基于動(dòng)態(tài)規(guī)劃的基因雙序列比對(duì)研究

羅志兵

（西南林業(yè)大學(xué)大數(shù)據(jù)與智能工程學(xué)院，昆明 650224）

在生物信息學(xué)的研究中，最基礎(chǔ)的問(wèn)題是對(duì)生物序列進(jìn)行分析，序列比對(duì)是最基本的操作。通過(guò)比對(duì)找出序列間的相似性，根據(jù)相似性進(jìn)行同源性分析，推導(dǎo)出演化過(guò)程。因此，序列比對(duì)常用于研究由共同祖先進(jìn)化而來(lái)的序列，特別是如蛋白質(zhì)序列或DNA序列等生物序列。它對(duì)于發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)和進(jìn)化信息具有非常重要的意義。如何開(kāi)發(fā)出高效、準(zhǔn)確的序列比對(duì)算法是目前序列比對(duì)的一個(gè)重點(diǎn)。經(jīng)過(guò)對(duì)雙序列比對(duì)算法的研究，探索動(dòng)態(tài)規(guī)劃算法在全局比對(duì)和局部比對(duì)中的應(yīng)用以及算法的實(shí)現(xiàn)過(guò)程。

生物信息學(xué)；序列比對(duì)；動(dòng)態(tài)規(guī)劃

1 序列比對(duì)的概念及其意義

序列比對(duì)的定義是：根據(jù)特定的計(jì)分規(guī)則，兩個(gè)或多個(gè)符號(hào)序列按位置比較后排列，盡可能反映序列間的相似性，這一過(guò)程稱為序列比對(duì)。

生物學(xué)上一個(gè)基本問(wèn)題是，一個(gè)基因或者蛋白是否和別的基因或者蛋白存在聯(lián)系。蛋白質(zhì)在序列層次的關(guān)聯(lián)暗示了其同源性，同時(shí)暗示了它們可能有類似的功能。通過(guò)分析多個(gè)DNA或者蛋白質(zhì)序列，我們可能會(huì)發(fā)現(xiàn)一些保守序列和區(qū)域。這種基因序列或者蛋白質(zhì)序列之間關(guān)聯(lián)性的分析就是通過(guò)序列比對(duì)來(lái)完成的[2]。如今，人們完成了許多不同生物體的基因組分析，獲得了大量的基因和蛋白質(zhì)序列數(shù)據(jù)。序列比對(duì)能夠向我們揭示某一生物體中蛋白質(zhì)之間的關(guān)聯(lián)以及蛋白質(zhì)在不同生物體中的關(guān)聯(lián)，從而進(jìn)一步理解生命和進(jìn)化。

序列比對(duì)的主要用途：

（1）用于搜索相似序列,當(dāng)你獲得一段DNA序列或氨基酸序列后，發(fā)現(xiàn)對(duì)它一無(wú)所知時(shí)，可以在已知的核酸序列數(shù)據(jù)庫(kù)中搜索關(guān)于這一序列的信息，一個(gè)有效的方法是采用比對(duì)算法在數(shù)據(jù)庫(kù)中找到一系列與該序列有相似性的序列，并按相似程度由高到低排列。

（2）在基因組測(cè)序中主要用于，通過(guò)比對(duì)算法找到有重疊區(qū)的另外的序列片段，把它們合并起來(lái)還原成原來(lái)的長(zhǎng)核酸序列，得到長(zhǎng)核酸序列的堿基排列順序。

（3）尋找序列中的特定位點(diǎn)。當(dāng)一個(gè)基因的某一位點(diǎn)發(fā)生突變時(shí)，它與原基因進(jìn)行比對(duì)時(shí)就能發(fā)現(xiàn)這個(gè)位點(diǎn)，這在尋找致病基因時(shí)尤為重要。

（4）預(yù)測(cè)蛋白質(zhì)結(jié)構(gòu)，通過(guò)把待測(cè)的序列與已知結(jié)構(gòu)的序列進(jìn)行比對(duì)，根據(jù)相似性去預(yù)測(cè)待測(cè)序列局部或全部的結(jié)構(gòu)。

2 序列比對(duì)與記分規(guī)則

2.1 全局比對(duì)與局部比對(duì)

序列比對(duì)根據(jù)對(duì)比對(duì)后要排列的片斷范圍可將比對(duì)分為全局比對(duì)與局部比對(duì)。全局比對(duì)是全部待研究的全部序列的全部符號(hào)參加比較，最后也是全部序列的全部符號(hào)進(jìn)行排列與計(jì)分，比對(duì)的結(jié)果中各序列長(zhǎng)度相同；而局部比對(duì)是全部序列的全部符號(hào)參加比較，最后只將各序列中得分高的片斷中的符號(hào)進(jìn)行排列與計(jì)分，即只排列局部的序列片斷[5]。

相比于全局比對(duì)，局部比對(duì)更能反映序列間的相似性。因?yàn)?，蛋白質(zhì)功能位點(diǎn)往往是由較短的序列片段組成的，盡管在序列的其它部位可能有插入、刪除等突變，但這些關(guān)鍵的功能部位的序列往往具有相當(dāng)大的保守性。而局部比對(duì)往往比整體比對(duì)對(duì)這些功能區(qū)段具有更高的靈敏度，因此其結(jié)果更具生物學(xué)意義。

2.2 最優(yōu)匹配與記分規(guī)則

序列比對(duì)的結(jié)果有很多種可能，而目標(biāo)是要找出最優(yōu)比對(duì)結(jié)果，即使匹配項(xiàng)盡可能地多一點(diǎn)，而引入的空格盡可能地少一些。為此，我們引入了記分規(guī)則，用以給每一個(gè)匹配結(jié)果打分。而分?jǐn)?shù)越高說(shuō)明把序列轉(zhuǎn)換為對(duì)應(yīng)序列的代價(jià)越小，相似性也就越大，所以最后得分最高的匹配即為最優(yōu)匹配。

計(jì)分規(guī)則是比對(duì)的重要條件，計(jì)分方法的生物學(xué)意義常常就決定了比對(duì)所反映的生物學(xué)特征。在使用差異較大的不同計(jì)分方法時(shí)將會(huì)產(chǎn)生不同的比對(duì)結(jié)果。根據(jù)所代表的生物學(xué)意義可以粗略地將計(jì)分方法分為三類：匹配計(jì)分、結(jié)構(gòu)與性質(zhì)計(jì)分、可觀察變換計(jì)分。匹配計(jì)分的規(guī)則是字符進(jìn)行比較時(shí)只有3至4個(gè)分值：兩個(gè)字母相同（匹配）獎(jiǎng)勵(lì)一個(gè)分值、兩個(gè)字母不同（錯(cuò)配）罰一個(gè)分值、字母對(duì)空格罰1至2個(gè)分值。例如常用的生物信息學(xué)軟件BLAST中的核酸比對(duì)計(jì)分就是采用匹配計(jì)分。由于這種方法簡(jiǎn)單，較容易用它說(shuō)明比對(duì)的一般原理，所以本文的核酸序列比對(duì)都采用這種方法。

3 比對(duì)算法

有不少的序列比對(duì)算法已出現(xiàn)在文獻(xiàn)及應(yīng)用軟件中，其中一些得到廣泛的應(yīng)用，如動(dòng)態(tài)規(guī)劃法、累進(jìn)方法等。兩序列比對(duì)與多序列比對(duì)的算法有差異，兩序列比對(duì)的經(jīng)典方法是動(dòng)態(tài)規(guī)劃法。全局比對(duì)動(dòng)態(tài)規(guī)劃法是Needleman與Wunsch在1970年提出[1]，一直沿用至今，這個(gè)算法是生物信息學(xué)的基礎(chǔ)算法之一。局部比對(duì)的動(dòng)態(tài)規(guī)劃法是Temple F.Smith和Michael S.Waterman于1981年提出的[3]。Smith-Waterman算法實(shí)際上是Needle-Wunsch算法的一個(gè)變體。二者都是動(dòng)態(tài)規(guī)劃算法。這一算法的優(yōu)勢(shì)在于可以在給定的打分方法下找出兩個(gè)序列的最優(yōu)的局部比對(duì)。

動(dòng)態(tài)規(guī)劃算法的思想大致上是，若要解一個(gè)給定問(wèn)題，我們需要解其不同部分（即子問(wèn)題），再合并子問(wèn)題的解以得出原問(wèn)題的解。通常許多子問(wèn)題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問(wèn)題一次，從而減少計(jì)算量：一旦某個(gè)給定子問(wèn)題的解已經(jīng)算出，則將其記憶化存儲(chǔ)，以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接查表[4]。這種做法在重復(fù)子問(wèn)題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長(zhǎng)時(shí)特別有用。動(dòng)態(tài)規(guī)劃高效地解決了如何將一個(gè)龐大的數(shù)學(xué)問(wèn)題分解為一系列小問(wèn)題，并且從一系列小問(wèn)題的解決方法重建大問(wèn)題的解決方法的過(guò)程。

基于動(dòng)態(tài)規(guī)劃的這一基本思想，序列比對(duì)算法的主要過(guò)程大致是：

首先，一個(gè)DNA螺旋由一串被稱為基的分子組成，可能的基包括腺嘌呤（Adenie）、鳥(niǎo)嘌呤（Guanine）、胞嘧啶（Cytosine）和胸腺嘧啶（Thymine）。分別以它們的首字母來(lái)代表這些基，于是，一個(gè)DNA螺旋就可以表示為在有窮集合A,G,C,T上的一個(gè)串。

以全局比對(duì)為例進(jìn)行說(shuō)明，對(duì)序列X=ACT與Y=CGG進(jìn)行比對(duì)，比對(duì)的結(jié)果有很多種可能，其中一部分的可能比對(duì)結(jié)果如下：（規(guī)定空格對(duì)空格無(wú)效?。?/p>

將比對(duì)全過(guò)程分為若干步，每一步增加一個(gè)位置。因?yàn)榭崭駥?duì)空格無(wú)效，所以增加一個(gè)位置時(shí)有三種情況：第一個(gè)序列增加一個(gè)字母而第二個(gè)序列增加一個(gè)空格；第一個(gè)序列增加一個(gè)空格而第二個(gè)序列增加一個(gè)字母；兩個(gè)序列都增加一個(gè)字母。這樣要進(jìn)行n步的話就可能有3n種可能。動(dòng)態(tài)規(guī)劃算法的巧妙之處是把第一序列已比對(duì)字母且第二序列已比對(duì)字母都相同的各種比對(duì)結(jié)果放在一起進(jìn)行判斷，只留最優(yōu)結(jié)果。用這種篩選方面一直進(jìn)行下去，直到所有的字母都進(jìn)行過(guò)比對(duì)為止。最后所得的最優(yōu)解就是動(dòng)態(tài)規(guī)劃算法的最后結(jié)果。以序列GC和序列AT的比對(duì)中間過(guò)程為例：

以上三種中間比對(duì)都是：第一序列的G已比對(duì)且第二序列的A已比對(duì)。而顯然這三種可能中，第三種的比對(duì)最優(yōu)，因?yàn)樗目崭褚胱钌?。于是舍棄了前兩個(gè)可能，只保存第三中可能的結(jié)果。

因此，用動(dòng)態(tài)規(guī)劃算法進(jìn)行兩序列比對(duì)的過(guò)程可用矩陣顯示，矩陣中的每一元素可表示第一序列已比對(duì)字母且第二序列已比對(duì)字母相同的各種比對(duì)結(jié)果的最優(yōu)者，最后的一格（即右下格）的最優(yōu)結(jié)果就是整個(gè)比對(duì)的最優(yōu)結(jié)果。在具體算的過(guò)程中，每一格只用最優(yōu)比對(duì)的得分來(lái)表示。矩陣的計(jì)算過(guò)程可表示如下：

給出的長(zhǎng)度為m的序列x和長(zhǎng)度為n的序列y，建立一個(gè)（n+2）×（m+2）的矩陣，函 數(shù) F（i,j）遞歸求序列 x[1，…，i]和 y[1，…，j]的最佳比配的得分。

其中：

而g=-2（與空格對(duì)齊的話罰兩分）。

4 比對(duì)算法的實(shí)現(xiàn)

4.1 動(dòng)態(tài)規(guī)劃的全局比對(duì)的過(guò)程

算法的整體功能是：

·輸入：將要比對(duì)的兩條序列，x（A,G,C）,y（A,A,A,C）,以及打分函數(shù)

·輸出：最大比對(duì)得分所對(duì)應(yīng)的比對(duì)結(jié)果。主要步驟如下：

（1）建立得分矩陣

建立一個(gè)（n+2）×（m+2）的矩陣，其中，m，n分別為X,Y的長(zhǎng)度。將序列x（欲比較的序列）從第一行的第三列開(kāi)始填入，而序列y（參照序列）從第一列的第三行開(kāi)始填入，如表1所示。

表1 得分矩陣

（2）選擇得分體系

字符的比對(duì)有三種情況：匹配，錯(cuò)配，插入或刪除。因?yàn)椴迦牒蛣h除都是引入空位的操作（在不同序列上）。序列1上某一位置的插入相當(dāng)于在序列2上對(duì)應(yīng)位置的刪除，所以，在實(shí)際計(jì)算中，只需要考慮何時(shí)引入空位即可。

這三種得分情況有很多打分標(biāo)準(zhǔn)，不同的打分標(biāo)準(zhǔn)會(huì)得出不同的比對(duì)結(jié)果。這里將選用的是最簡(jiǎn)單的打分體系，即，匹配得一分，錯(cuò)配罰一分，空格罰兩分。

（3）填充得分矩陣

開(kāi)始于第二行中的第二列，初始值為0。通過(guò)矩陣一行一行,從左向右地移動(dòng)，計(jì)算每個(gè)位置的分?jǐn)?shù)。每一單元格的最佳得分（即最高）是從已有的左側(cè)，頂部或左上方（對(duì)角線）最佳得分計(jì)算而來(lái)，最后取這三者中的最大值與該單元格的得分值相加，并用一個(gè)箭頭指向得分的來(lái)源處（在某些位置，可能存在著兩個(gè)或三個(gè)相同的最大得分）。當(dāng)一個(gè)得分從頂部計(jì)算，或從左邊這代表在對(duì)準(zhǔn)時(shí)發(fā)生的插入缺失。當(dāng)我們從對(duì)角線計(jì)算分?jǐn)?shù)這表示兩個(gè)字母所在位置匹配的對(duì)準(zhǔn)。因?yàn)椴淮嬖凇跋蛏稀被颉白笊稀钡奈恢脤?duì)第二行，我們只能從左側(cè)現(xiàn)有單元求和。因此，我們每一步分?jǐn)?shù)都-2，代表著相對(duì)于上一個(gè)的比分發(fā)生了插入或缺失。這導(dǎo)致在第一行是0，-2，-4，-6。這同樣適用于第二列，因?yàn)閷?duì)于第二列而言，只存在向上的分?jǐn)?shù)。因此，我們有圖1。

圖1 矩陣填充圖

（4）回溯得出最優(yōu)匹配

從矩陣的最右下角的單元格開(kāi)始，根據(jù)指向上一個(gè)位置的箭頭來(lái)回溯取得最佳匹配的路徑。然后根據(jù)從起始位置指向最終位置的路徑來(lái)完成匹配的建立。如果最佳匹配路徑有多個(gè)的話，在回溯開(kāi)始前，先決定好回溯時(shí)優(yōu)先選擇追蹤箭頭的方向，如優(yōu)先選指向高處的箭頭或指向低處的箭頭。如圖2所示：

圖2 回溯圖

如果選擇第一種回溯方式，表明在回溯時(shí)，優(yōu)先選擇指向高處的箭頭（即首先選1箭頭，如果沒(méi)有就選擇2箭頭，如果沒(méi)有則選3箭頭）。選擇第二種回溯方式則反之。選擇不同的回溯方式，最后得出的最佳匹配結(jié)果也不一樣。下面給出以上兩種回溯方式下得出的匹配結(jié)果，如圖3所示。

圖3 結(jié)果圖

若以上面第一種從高到低的偏好來(lái)選擇回溯方式的話，得出的匹配結(jié)果為（圖3綠線途徑）：

最佳匹配得分為-1。而以第二種從低到高的順序選擇回溯方式的話，得出的匹配結(jié)果則為（圖3黃線路徑）：

最佳匹配得分為-1。

（5）具體代碼實(shí)現(xiàn)

首先填充矩陣，即計(jì)算每一個(gè)單元格的得分值。在具體代碼實(shí)現(xiàn)的時(shí)候，實(shí)際上數(shù)組并沒(méi)有保存指向上一個(gè)最優(yōu)值的箭頭，而只是記錄了分值而已。由于矩陣的第一行和第一列分別用來(lái)存儲(chǔ)序列x,y，所以計(jì)算從第二行第二列開(kāi)始。m ←length（x）

n ← length（y）

for j=1 to（m+1）

F（1,j）← g*（j-1）

for i=1 to（n+1）

F（i,1）← g*（i-1）

for i=2 to n+1

for j=2 to m+1

{

Match ← F（i-1,j-1）+S（x_i,y_j）

Delete←F（i-1,j）+g /*代表序列 x在此處發(fā)生了deleted*/

Insert←F（i,j-1）+g /*代表序列 x在此處發(fā)生了inserted*/

F（i,j）← max（Match,Insert,Delete）

}

以下代碼將實(shí)現(xiàn)如何回溯得出最佳匹配

AlignmentX←""

AlignmentY←""

i←n+1

j←m+1

while（i＞ 1 or j＞ 1）

{

if（i＞ 1 and F（i,j）==F（i-1,j）+g）

{

AlignmentX←"-"+AlignmentX

AlignmentY←y_i+AlignmentY

i←i-1

}

else if（j＞ 1 and F（i,j）==F（i,j-1）+g）

{

AlignmentX←x_j+AlignmentX

AlignmentY←"-"+AlignmentY

j←j-1

}

else

{

AlignmentX←x_i+AlignmentX

AlignmentY←y_j+AlignmentY

i←i-1

j←j-1

}

}

4.2 動(dòng)態(tài)規(guī)劃的局部比對(duì)的實(shí)現(xiàn)

基于動(dòng)態(tài)規(guī)劃的局部比對(duì)算法最著名的算法是Smith-Waterman算法。它是一種進(jìn)行局部序列比對(duì)（相對(duì)于全局比對(duì)）的算法，用于找出兩個(gè)核苷酸序列或蛋白質(zhì)序列之間的相似區(qū)域。該算法的目的不是進(jìn)行全序列的比對(duì)，而是找出兩個(gè)序列中具有高相似度的片段。與全局比對(duì)的主要區(qū)別在于該算法不存在負(fù)分（負(fù)分被替換為零），它使得對(duì)序列局部的比對(duì)成為可能。當(dāng)任何位置分?jǐn)?shù)低于0，即表示此前的序列不具有相似性；而此時(shí)將此元素分?jǐn)?shù)設(shè)為0，即達(dá)到了“重置”的效果，使得從此位置開(kāi)始的比對(duì)不受之前位置的影響。初始化階段的區(qū)別使得該算法可從一序列任意位置開(kāi)始匹配另一序列不受罰分。最后，回溯是從分?jǐn)?shù)最高的矩陣元素開(kāi)始，直到遇到分?jǐn)?shù)為零的元素停止。分?jǐn)?shù)最高的局部比對(duì)結(jié)果在此過(guò)程中產(chǎn)生。

以序列 x（A,A,G,A）和序列 y（T,T,A,A,G）為例進(jìn)行局部比對(duì)，直觀效果圖如下：從圖4可看出，局部比對(duì)的結(jié)果為：

圖4 局部比對(duì)圖

得分為3。而如果進(jìn)行全局比對(duì)的話，最大得分則為-3。

（1）局部比對(duì)分值計(jì)算過(guò)程

局部比對(duì)的遞歸函數(shù)與全局比對(duì)的稍有不同，因?yàn)椴淮嬖谪?fù)分，因此將會(huì)引入零進(jìn)行比較。如果從已有的相鄰三個(gè)分值計(jì)算來(lái)的得分均小于零的話，表示此前的序列不具有相似性。于是重置為零，接下來(lái)將重新計(jì)分。

（2）局部比對(duì)的回溯過(guò)程

首先需要找出得分矩陣?yán)锏淖畲蠓种?，然后從最大分值處回溯直到遇上零停止回溯，即得出一個(gè)局部最佳匹配。

max←0

i_{max}←0

j_{max}←0

for（i=2;i＜=n+1;i++）

{

for（j=2;j＜=m+1;j++）

{

if（F[i,j]＞ max）

{

max=F[i,j];i_{max}=i;j_{max}=j;

}

}

}

AlignmentX←""

AlignmentY←""

cur_i←i_{max}

cur_j←j_{max}

while（F[cur_i,cur_j]!=0）

{

if（ cur_i＞1 and F[cur_i,cur_j]==F[cur_i-1,cur_j]+g）

{

AlignmentX←"-"+AlignmentX

AlignmentY←y_i+AlignmentY

cur_i←cur_i-1

}

else if（ cur_j＞1 and F[cur_i,cur_j]==F[cur_i,cur_j-1]+g）

{

AlignmentX←x_j+AlignmentX

AlignmentY←"-"+AlignmentY

cur_j←cur_j-1

}

else

{

AlignmentX←x_i+AlignmentX

AlignmentY←y_j+AlignmentY

cur_i←cur_i-1

cur_j←cur_j-1

}

}

5 結(jié)語(yǔ)

全局比對(duì)與局部比對(duì)都各有優(yōu)勢(shì)，因此，在現(xiàn)實(shí)生活中，如果進(jìn)行匹配的兩條序列的長(zhǎng)度相差很大的話，當(dāng)進(jìn)行全局性配對(duì)時(shí)，匹配程度將會(huì)很低。因?yàn)樵撆鋵?duì)方法要求將兩個(gè)序列的所有堿基都進(jìn)行配對(duì)，所以當(dāng)兩序列長(zhǎng)度相差很大時(shí)，將會(huì)造成配對(duì)結(jié)果含有很長(zhǎng)的間隔。盡管在某處，配對(duì)序列和參考序列的匹配程度相當(dāng)高，在全局性配對(duì)時(shí)，將不會(huì)把這兩個(gè)片段直接進(jìn)行配對(duì)，而是盡量嘗試讓參考序列內(nèi)的所有堿基都參與匹配，造成結(jié)果與局部性配對(duì)方法有極大差別。因此，在選擇配對(duì)算法的時(shí)候，必須參考兩序列的具體長(zhǎng)度和配對(duì)的實(shí)際意義和需要，選擇適當(dāng)?shù)姆椒?，才能得到有生物學(xué)意義的結(jié)果。一般來(lái)說(shuō)，全局性配對(duì)主要應(yīng)用于比較同源性的基因的相似性而局部性配對(duì)主要應(yīng)用于在非同源性的基因序列中尋找具有相似性的同源的基因域。

當(dāng)堿基對(duì)或殘基對(duì)之間匹配會(huì)導(dǎo)致更低分?jǐn)?shù)時(shí)，需要空位的引入，即讓堿基或殘基與空位匹配?？瘴涣P分決定了插入或者刪除的分值。無(wú)論是全局比對(duì)或局部比對(duì)，本文在選擇打分機(jī)制時(shí)都是采用的是最簡(jiǎn)單的線性打分機(jī)制，即：

w（k）=k × g

其中，k為空位的個(gè)數(shù)，g為每一個(gè)空位的罰分值。這種線性空位罰分方式為每次插入或者刪除的得分相同。然而在生物學(xué)上，兩序列之間一般存在著具有不同相似度的區(qū)域。另外，單個(gè)基因突變事件可能導(dǎo)致一長(zhǎng)串空位的插入。因此，一個(gè)連續(xù)的較長(zhǎng)的空位優(yōu)于多個(gè)分散的小的空位。雖然多個(gè)分散的小的空位可以產(chǎn)生更多匹配，但一個(gè)連續(xù)的較長(zhǎng)的空位代表這個(gè)區(qū)域只在一個(gè)序列中出現(xiàn)，使用后者可以避免為了得到高分而過(guò)度匹配這段序列。

[1]Saul B.;Needleman and Christian D Wunsch.A General Mmethod Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins.Journal of Molecular Biology,1970.

[2]Durbin R,Eddy S,Krogh A et al.生物序列分析,蛋白質(zhì)和核酸的概率論模型[M].北京清華大學(xué)出版社,2002.

[3]Michael S.Waterman Temple F.Smith.Identi fi cation of Common Molecular Subsequences.Journal of Molecular Biology,1981.

[4]Charles E.Leiserson Thomas H.Cormen.Introduction to algorithms.機(jī)械工業(yè)出版社出版,2002.

[5]David W.Mount.Bioinformatics Sequence and Genome Analysis.科學(xué)出版社,2002.

Dynamic Programming in Pair Sequences Alignment

LUO Zhi-bing
（College of Big Data and Intelligence Engineering,Southwest Forestry University,Kunming 650224）

DNA or Protein sequences analysis is the most important job in bioinformatics and sequences alignment is the most fundamental operation.Similarities between the sequences are found by sequences alignment.Those similarities can be used to analyze homology in DNA or protein sequences and derivate evolution information.Therefore,sequences alignment is really important in derivation of information about protein function and structures.Nowadays,improving correction and reducing time consumption in searching algorithms has become the main problem in this field.By doing research in algorithms about solving pair sequences alignment,puts forward dynamic programming algorithm in solving both global alignment and local alignment,and also gives an implementation of dynamic programming.

Bioinformatics;Sequences Alignment;Dynamic Programming

1007-1423（2017）32-0028-07

10.3969/j.issn.1007-1423.2017.32.007

羅志兵（1989-），女，廣西壯族自治區(qū)貴港人，在讀碩士研究生，研究方向?yàn)椴僮飨到y(tǒng)研發(fā)、算法分析

2017-08-29

2017-10-25