基于分治算法的DNA序列比對成本模型

劉欣睿 四川大學(xué)軟件學(xué)院

引言

DNA序列比對是生物信息學(xué)中的一項(xiàng)重要任務(wù)，在實(shí)際應(yīng)用中，DNA序列比對可用于DNA親代測試，同時(shí)有助于了解物種和個(gè)體差異之間的變化。本文將提供最佳的DNA序列比對，旨在減少任何給定序列的缺失匹配和缺口的數(shù)量。算法實(shí)現(xiàn)的第一個(gè)挑戰(zhàn)是巨大的搜索空間，因此本文建立了優(yōu)化數(shù)學(xué)模型以修剪搜索方法。其次，不能用蠻力來找到比較的最佳方法。綜上本文算法基于這兩個(gè)挑戰(zhàn)而引入。

1 分治算法

對于分治算法需要確定何時(shí)退出遞歸。例如，對于兩個(gè)DNA序列：X（0，m）和Y（0，n），如果要計(jì)算opt（i，j），那么遞歸的退出可以分為兩種情況：

但該算法存在兩個(gè)缺陷。首先，該算法僅提供最佳成本懲罰，而不是最佳對齊。其次，算法的復(fù)雜度非常大并且呈指數(shù)增長，在最壞的情況下，該算法的時(shí)間復(fù)雜度將為O（3 ^ max（m，n））。

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

為克服上述分治算法的缺陷，本文引入動(dòng)態(tài)規(guī)劃算法。在設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法時(shí)，通?？梢宰裱韵聨讉€(gè)步驟：

1.分析和比較最優(yōu)解的特征；

2.遞歸定義最優(yōu)值；

3.通過自上而下的邏輯運(yùn)算得到最優(yōu)解，得到函數(shù)的最大值或最小值。

這種方法是以時(shí)間交換空間。首先，建立一個(gè)m乘n的矩陣。然后將opt（i，j）的結(jié)果存儲(chǔ)到第i行第j列。例如，設(shè)有兩個(gè)DNA序列 X（0,10）和 Y（0,8）：

根據(jù)遞歸的終止條件，可以得出以下結(jié)論：

3 算法實(shí)現(xiàn)結(jié)果

由上述算法原理可進(jìn)一步實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法，最終得到已知DNA序列的成本矩陣11*9，如下所示：

i/j 0T 1A 2A 3G 4G 5T 6C 7A 8 -0A 7 8 10 12 13 15 16 18 201A 6 6 8 10 11 13 14 16 182C 6 5 6 8 9 11 12 14 163A 7 5 4 6 7 9 11 12 144G 9 7 5 4 5 7 9 10 125T 8 8 6 4 4 5 7 8 106T 9 8 7 5 3 3 5 6 87A 11 9 7 6 4 2 3 4 68C 13 11 9 7 5 3 1 3 49C 14 12 10 8 6 4 2 1 210- 16 14 12 10 8 6 4 2 0

根據(jù)上述矩陣，已知array [0] [0]=7，即可利用tracepath來獲得最佳對齊。

（1）如果（0,1）屬于路徑，則 opt（0,0）= opt（0,1）+ 2 = 6+ 2 = 8＞ 7，因此這種情況不會(huì)退出。

（2）如果（0,1）屬于路徑，則 opt（0,0）= opt（1,0）+ 2 = 8+ 2 = 10＞ 7，因此這種情況不會(huì)退出。（x0與a對齊間隙）

（3）如果（1,1）屬于路徑，則 opt（0,0）= opt（1,1）+ 1 = 6 +1 = 7，因此本情況是最佳對齊。（x0與y0對齊，但是x0與y0不匹配）

4 結(jié)論

序列比對是生物信息學(xué)中最基本的問題。為了進(jìn)一步研究DNA序列比對問題，本文建立了一個(gè)新模型，稱為成本模型，以確定比對優(yōu)化的程度?；谶@個(gè)新模型，使用Divide and Conquer算法來解決這個(gè)問題。但本文選擇動(dòng)態(tài)規(guī)劃算法來克服時(shí)間復(fù)雜性的缺陷。最后，創(chuàng)建了后向跟蹤算法，以找到最佳對齊的軌跡。