李子茂，李　湘

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)

?

EBD(1,2)的參數(shù)化動(dòng)態(tài)規(guī)劃算法改進(jìn)

李子茂，李湘

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)

摘要為了提高Z.Wei和D.Zhu的算法的計(jì)算效率，通過引入全局變量Map數(shù)組避免重復(fù)計(jì)算基因家族的鄰接關(guān)系，將Z.Wei和D.Zhu的固定參數(shù)算法的時(shí)間復(fù)雜度改進(jìn)為O(s24sn)，空間復(fù)雜度保持O(s4sn)；當(dāng)給定基因組是有向時(shí)，適當(dāng)?shù)匦拚?，證明了Z.Wei和D.Zhu的固定參數(shù)動(dòng)態(tài)規(guī)劃算法適合求解有向(1,2)-范例斷點(diǎn)距離.相關(guān)算法可使用C++來實(shí)現(xiàn)，仿真實(shí)驗(yàn)進(jìn)一步驗(yàn)證了改進(jìn)算法的有效性.

關(guān)鍵詞基因組；范例；斷點(diǎn)；動(dòng)態(tài)規(guī)劃

基因組重組問題是近20年來計(jì)算生物學(xué)領(lǐng)域的研究熱點(diǎn)，該問題在生物演化樹重建、生物醫(yī)藥技術(shù)和發(fā)掘生物之間的親緣關(guān)系等方面有重要的應(yīng)用價(jià)值[1].

基因組為基因家族上的基因組成的基因序列，序列上每個(gè)基因都是某個(gè)基因家族的一次出現(xiàn)，有如下定義：假設(shè)X是∑上的一個(gè)基因組，如果X中的每個(gè)基因g僅出現(xiàn)一次，則稱X是平凡的；如果X中的某個(gè)基因g至少出現(xiàn)兩次，該基因組稱為不平凡的[2,3].

斷點(diǎn)距離是為了衡量?jī)蓚€(gè)基因組的相似度才被引入的概念[2,4].對(duì)于不平凡的基因組，D.Sankoff[5]提出范例模型定義兩個(gè)基因組的斷點(diǎn)距離，該模型將不平凡基因組的斷點(diǎn)距離計(jì)算轉(zhuǎn)換為平凡基因組斷點(diǎn)距離計(jì)算.給定∑上一個(gè)不平凡的基因組G，范例Ex(G)是G的子序列且G中每個(gè)基因家族都僅出現(xiàn)一次.∑上兩個(gè)基因組G1和G2的范例斷點(diǎn)距離(簡(jiǎn)稱EBD)即為使得d(Ex(G1),Ex(G2))最小的兩個(gè)范例的距離.

如果基因組G1中每個(gè)基因家族最多出現(xiàn)p次，基因組G2中每個(gè)基因家族最多出現(xiàn)q次，G1和G2的范例斷點(diǎn)距離稱為(p,q)-范例斷點(diǎn)距離，記為EBD(p,q).特殊情況下，如果兩個(gè)基因組存在相同的范例，則其范例斷點(diǎn)距離為0，稱該問題就是零-范例斷點(diǎn)距離問題，簡(jiǎn)稱ZEBD(p,q).

D.Sankoff為解決EBD(p,q)提出了一個(gè)分支定界算法[5].C.Nguyen等人隨后對(duì)EBD(p,q)提出了分而治之的方法，并開發(fā)了一個(gè)結(jié)合分而治之和分支定界技術(shù)的程序[6]，該程序通過使用細(xì)菌的基因序列作為輸入數(shù)據(jù)驗(yàn)證了有效性.

在問題的計(jì)算難度上，D.Bryant首次證明EBD(1,2)是NP-hard[7]，Z.Chen,B.Fu和B.Zhu證明ZEBD(3,3)是NP-hard[8].2010年，G.Blin,G.Fertin,F.Sikora和S.Vialette證明ZEBD(2,2)也是NP-hard，如果p≥2,q≥2，EBD(p,q)也是NP-hard的，而且在多項(xiàng)式時(shí)間內(nèi)任何性能比都不能近似EBD(p,q)[3].S.Angibaud等人證明EBD(1,2)是APX-hard[4]，L.Bulteau和M.Jiang證明使用多種距離度量很難近似EBD(1,2)[9].

考慮到固定參數(shù)計(jì)算的棘手性，B.Zhu證明FPT算法不能有效解決EBD(2,2)[10].近年來，許多算法被提出，如G.Blin等人通過顏色編碼技術(shù)[11]為ZEBD設(shè)計(jì)時(shí)間復(fù)雜度O(n2n)的算法[3]，他們也針對(duì)ZEBD給出了一個(gè)時(shí)間復(fù)雜度O(n22ss3)的參數(shù)化算法，其中n是輸入基因組的長(zhǎng)度，s是基因家族的最大跨度.B.Fu和L.Zhang[12]針對(duì)EBD(1,q)給出了一個(gè)時(shí)間復(fù)雜度為O(2nmo(1))的算法，M.Jiang證明ZEBD(1,q)能在多項(xiàng)式時(shí)間內(nèi)被解決[13].D.Zhu和L.Wang[14]針對(duì)ZEBD(2,2)提出了一個(gè)時(shí)間復(fù)雜度為O(n21.86121n)的算法.其他一些EBD算法可見文[2,7,15,16].

EBD(1,2)是最基礎(chǔ)的范例斷點(diǎn)距離問題，該問題是APX-hard，但卻鮮有算法對(duì)該問題進(jìn)行求解.Z.Wei和D.Zhu[17,18]提出固定參數(shù)算法動(dòng)態(tài)規(guī)劃算法解決EBD(1,2)，時(shí)間復(fù)雜度和空間復(fù)雜度分別為O(s4sn2)和O(s4sn)，其中n是基因家族的數(shù)量，s是基因家族的最大跨度.令G=G[1]……G[m]是∑上的一個(gè)串.為了方便，我們用G[i,j]代表G[i]……G[j]的連續(xù)子序列，i≤j.對(duì)于j≥i來說，在G中G[i]和G[j](注意G[j]=G[i])的跨度是j-i.一個(gè)串的跨度是在這個(gè)串中所有基因家族的最大跨度.實(shí)際上，在基因組中，基因家族的跨度都很小[19].

本文使用全局變量改進(jìn)Z.Wei和D.Zhu[17,18]的固定參數(shù)算法計(jì)算兩個(gè)基因組間范例斷點(diǎn)距離的時(shí)間復(fù)雜度，同時(shí)修訂該算法使之適合求解有向不平凡基因組的范例斷點(diǎn)距離.

1無向EBD(1,2)參數(shù)化動(dòng)態(tài)規(guī)劃算法

對(duì)無向不平凡基因組G2=G2[1],G2[2],G2[3],…,G2[m]，每個(gè)∑中基因家族在G2中最多出現(xiàn)兩次，如果G2[1,i-1]中沒有包含與G2[i]相同的基因，則基因G2[i](1≤i≤m)在G2中是第一次出現(xiàn)；否則，基因G2[i](1≤i≤m)在G2中第二次出現(xiàn).

這里簡(jiǎn)要介紹文獻(xiàn)[17，18]提出的無向基因組EBD(1,2)動(dòng)態(tài)規(guī)劃算法并對(duì)算法時(shí)間復(fù)雜度進(jìn)行改進(jìn)，首先定義下述符號(hào)概念如表1.

表1EBD(1,2)的動(dòng)態(tài)規(guī)劃算法中涉及符號(hào)的含義

Tab.1The meaning of symbols in dynamic programming algorithm of EBD(1, 2)

符號(hào)含義基因家族集合X上的串G1上平凡的基因組G2上不平凡的基因組Ex(X)X的范例集合EX相對(duì)于G1的最小范例E1X中的任意范例d(G1,E)E與G1的斷點(diǎn)個(gè)數(shù)x某個(gè)基因X·xX右邊連接基因xXxX中剔除基因x|X|X的長(zhǎng)度,即X中的基因個(gè)數(shù)Φ上平凡串的一個(gè)集合T(Φ,s)Φ的s-terminal集合MΦ的最小s-kernelMK(Φ)返回Φ的最小s-kernel的子程序KEx[i-1]Ex(G2[1,i-1])的最小s-kernelmin(KEx)KEx中找到最小范例的子程序

對(duì)表1作補(bǔ)充說明：d(G1,E)=min{d(G1,E1)|E1∈Ex(X)}為G1和X的范例斷點(diǎn)距離.若X=X[1],X[2],…,X[k]，則X的長(zhǎng)度為k，如果k>t,稱X[k-t,k]為X的t-終端，記為t-terminal；如果k≤t，則X本身是X的t-terminal.T(Φ,s)={E1[|E1|-s,|E1|]︱E1∈Φ}.如果Φ的一個(gè)子集與Φ有相同的s-terminal集合，稱該子集為Φ的一個(gè)s-內(nèi)核，記為s-kernel，基數(shù)為|T(Φ,s)|.M={E2∈Φ︱d(G1,E2)≤d(G1,E1),E1[|E1|-s,|E1|]=E2[|E2|-s,|E2|]，E1∈Φ}，如果|M|=|T(Φ,s)|，那么M是Φ的最小s-kernel.

1.1動(dòng)態(tài)規(guī)劃算法找到最小范例

如果G2[1,i]的兩個(gè)或兩個(gè)以上的范例有相同的s-terminal，則相對(duì)于G1而言它們中存在一個(gè)最終成長(zhǎng)為G2的最小范例[17].如果用哈希表存儲(chǔ)Φ中的串，則在時(shí)間復(fù)雜度O(k·|Φ|)內(nèi)找到Φ的最小s-kernel.

引理1Ex(G2[1,i])的最小s-kernel肯定包含G2[1,i]相對(duì)于G1而言的最小范例，s為G2的跨度[17].

由引理1可知，通過遞歸計(jì)算Ex(G2[1,i])(1≤i≤m)的最小s-kernel能得到Ex(G2)的最小s-kernel.

定理1當(dāng)1≤i≤m，令KEx[i-1]是Ex(G2[1,i-1])的最小s-kernel，那么Ex(G2[1,i])的最小s-kernelKEx[i]能用如下方法遞歸計(jì)算[17]：

(1) 當(dāng)i=1時(shí)，KEx[i]={G2[1]}；

(2) 當(dāng)i≥2時(shí)，基因家族G2[i]在G2中第一次出現(xiàn)，KEx[i]=MK(KEx[i-1]·G2[i])；

(3) 當(dāng)i≥2時(shí)，基因家族G2[i]在G2中第二次出現(xiàn)，且G2[i]出現(xiàn)在G2[1,i-1]中，KEx[i]=MK(KEx[i-1]∪((KEx[i-1]G2[i])·G2[i])).

由定理1可知，相對(duì)于G1而言，KEx[i]肯定是Ex(G2[1,i])的最小s-kernel.該算法的時(shí)間復(fù)雜度取決于KEx[i]的基數(shù).動(dòng)態(tài)規(guī)劃算法Exemplar(G1,G2)可以在Ex(G2[1,m])即Ex(G2)中找到最小范例，其中MK和min(KEx)含義參照表1，算法描述如下：

Algorithm Exemplar(G1,G2)

Input:∑={1,2,3,…,n}上平凡基因組G1和不平凡基因組G2

Output:相對(duì)于G1而言，G2的最小范例

i=1時(shí)，KEx={G2[1]};

fori=2 tomdo

ifG2[i]是第一次出現(xiàn)

KEx=MK(KEx·G2[i]);

else

KEx=MK(KEx∪((KExG2[i])·G2[i]))

end if

end for

return min(KEx)

1.2優(yōu)化算法的時(shí)間復(fù)雜度

由引理1和定理1可知，如果Ex(G2[1,i])的兩個(gè)或多個(gè)范例有相同的s-terminal，那么這些范例當(dāng)中最多有一個(gè)范例能在KEx[i]中，因此，KEx[i]的s-terminal集合中串的數(shù)目足夠來估算KEx[i]中串的數(shù)目.如果KEx[i]中串的長(zhǎng)度最多是s，也就是說最多有s個(gè)基因家族出現(xiàn)在G2[1,i]中.因?yàn)槊總€(gè)基因家族在G2中最多出現(xiàn)兩次，KEx[i]最多有2s個(gè)串.如果KEx[i]中串的長(zhǎng)度至少是s+1，則KEx[i]最多有4s個(gè)串，有如下引理2.

引理2Ex(G2[1,i])的最小s-kernel最多有4s個(gè)串[17].

計(jì)算Ex(G2[1,i])的最小s-kernel的運(yùn)行時(shí)間是整個(gè)算法的時(shí)間復(fù)雜度基礎(chǔ)，注意KEx[i]是Ex(G2[1,i])的最小s-kernel.為方便起見，我們把在KEx[i-1]中的任意一個(gè)范例E表示為E=E[1],E[2],…,E[k].

(1)如果基因家族G2[i]在G2中是第一次出現(xiàn)，由引理2可知，KEx[i-1]·G2[i]最多有4s個(gè)串.在Z.Wei和D.Zhu的算法中，其計(jì)算基因組斷點(diǎn)函數(shù)每次都需要使用O(n)時(shí)間計(jì)算基因組G1的逆函數(shù)Map，即每個(gè)基因家族的所在位置數(shù)組，從而每次在判斷E[k]·G2[i]相對(duì)G1而言是斷點(diǎn)或相鄰時(shí)需要O(n)時(shí)間(E·G2[i]斷點(diǎn)數(shù)為E的斷點(diǎn)數(shù)或E的斷點(diǎn)數(shù)加1，這取決于E[k]·G2[i]是斷點(diǎn)還是鄰接).我們發(fā)現(xiàn)只需經(jīng)過一次基因組G1的逆函數(shù)Map計(jì)算并將之保存為全局變量，就可以在O(1)的時(shí)間來確定E[k]·G2[i]相對(duì)G1而言是斷點(diǎn)或是相鄰.

更進(jìn)一步，假設(shè)所有KEx[i-1]范例集已經(jīng)被確定，則Z.Wei和D.Zhu花O(4sn)的時(shí)間確定KEx[i-1]·G2[i]串中的范例集，而我們只需花O(4s)時(shí)間，使用哈希表來保存KEx[i-1]·G2[i]中的串時(shí)，能在O(s4s)時(shí)間下找到KEx[i-1]·G2[i]的最小s-kernel.因?yàn)殚L(zhǎng)度為s+1的一個(gè)串被當(dāng)做是哈希表的關(guān)鍵值，在KEx[i-1]·G2[i]中串設(shè)置哈希表會(huì)花O(s4s)時(shí)間，這些哈希表占用的空間為O(s4sn).

(2)如果基因家族G2[i]在G2中是第二次出現(xiàn)，則G2[i]出現(xiàn)在G2[1,i-1]中，由引理2可知，(KEx[i-1]G2[i])·G2[i]最多有4s個(gè)串.設(shè)E′=(EG2[i])·G2[i]，E與G1的斷點(diǎn)數(shù)目為d(E,G1)，在Z.Wei和D.Zhu的算法中，同樣其計(jì)算基因組斷點(diǎn)函數(shù)每次都需要使用O(n)時(shí)間計(jì)算基因組G1的逆函數(shù)Map，需用O(n+s)時(shí)間計(jì)算出(EG2[i])·G2[i]相對(duì)G1的斷點(diǎn)個(gè)數(shù).我們發(fā)現(xiàn)同樣只需經(jīng)過一次基因組G1的逆函數(shù)Map計(jì)算并將之保存為全局變量，就可以在O(1)的時(shí)間來確定E[k]·G2[i]相對(duì)G1而言是斷點(diǎn)或是相鄰，計(jì)算E′相對(duì)于G1斷點(diǎn)數(shù)目可以通過計(jì)算E′[k-s,k]和E[k-s,k]的斷點(diǎn)數(shù)目得到，時(shí)間復(fù)雜度為O(s)，從而Z.Wei和D.Zhu花O(4sn)的時(shí)間確定KEx[i-1]·G2[i]串中的范例集，而我們只需花O(s4s)時(shí)間，使用哈希表來保存(KEx[i-1]G2[i])·G2[i]中的串時(shí)，能在O(s24s)時(shí)間下找到(KEx[i-1]G2[i])·G2[i]的最小s-kernel.

考慮到算法的循環(huán)次數(shù)不超過2n次，整個(gè)算法的時(shí)間復(fù)雜度不超過O(s24sn).

定理2優(yōu)化Exemplar(G1,G2)算法總能在O(s24sn)時(shí)間和O(s4sn)空間下返回Ex(G2)的一個(gè)最小范例.

1.3仿真實(shí)驗(yàn)

我們使用C++語言實(shí)現(xiàn)了Exemplar(G1,G2)及其優(yōu)化算法，使用Visual C++ 6.0的編譯環(huán)境在Intel(R) Core(TM) i7-4790 CPU @3.60GHz 4GB Memory個(gè)人計(jì)算機(jī)上運(yùn)行算法.在實(shí)驗(yàn)中記錄Exemplar(G1,G2) 的運(yùn)行時(shí)間，算法平均運(yùn)行時(shí)間結(jié)果如圖1和圖2所示.通過隨機(jī)基因組的仿真對(duì)比實(shí)驗(yàn)表明，我們優(yōu)化后的算法能在1200 s內(nèi)處理5000個(gè)基因家族，G2重復(fù)率為70%，跨度分別為6和10的兩個(gè)基因組斷點(diǎn)距離的計(jì)算，比Z. Wei和D. Zhu的算法更加高效.無向EBD(1, 2)實(shí)例的兩個(gè)基因組G1和G2測(cè)試數(shù)據(jù)產(chǎn)生方法見文[17].

圖1　計(jì)算n個(gè)基因家族G1和G2的范例斷點(diǎn)距離的運(yùn)行時(shí)間，跨度為6，G2中重復(fù)基因家族的概率為70%Fig.1　The running time for computing the exemplar breakpoint distance of G1and G2with n gene families,where the nontrivial gene families of G2are bounded by 70%, and the span of G2is 6

圖2　計(jì)算n個(gè)基因家族G1和G2的范例斷點(diǎn)距離的運(yùn)行時(shí)間，跨度為10，G2中重復(fù)基因家族的概率為70%Fig.2　The running time for computing the exemplar breakpoint distance of G1and G2with n gene families,where the nontrivial gene families of G2are bounded by 70%, and the span of G2is 10

2有向EBD(1,2)參數(shù)化動(dòng)態(tài)規(guī)劃算法

給定∑={1,2,3,…,n}上平凡有向基因組G1=G1[1],G1[2],G1[3],…,G1[n]和不平凡有向基因組G2=G2[1],G2[2],G2[3],…,G2[n]，其中Gi[j]=k或Gi[j]= -k，k∈∑，i= 1,2, 1≤j≤n.一個(gè)在∑中基因家族在G2中最多出現(xiàn)兩次，如果G2[1,i-1]中沒有包含與|G2[i]|相同的基因，則基因家族|G2[i]|( 1≤i≤m)在G2中是第一次出現(xiàn)；否則，基因家族|G2[i]|(1≤i≤m)在G2中第二次出現(xiàn).在G2中G2[i]和G2[j](注意|G2[j]|=|G2[i]|)的跨度是j-i，一個(gè)串的跨度是在這個(gè)串中所有基因家族的最大跨度.這里我們將無向基因組EBD(1,2)求解推廣到有向基因組.有向基因組鄰接和斷點(diǎn)概念見Sankoff[5]提出的范例模型.以下運(yùn)用動(dòng)態(tài)規(guī)劃算法找到最小范例.

引理3E是G2[1,i-1]的一個(gè)范例.如果基因家族|G2[i]|在G2中是第一次出現(xiàn)，那么E·G2[i]是G2[1,i]的一個(gè)范例[17].

引理4E是G2[1,i-1]的一個(gè)范例.如果|G2[i]|家族在G2中是第二次出現(xiàn)，那么G2[i]出現(xiàn)在E中或-G2[i]出現(xiàn)在E中.第一種情況，G2[i]出現(xiàn)在E中，那么E和(EG2[i])·G2[i]都是G2[1,i]的范例；第二種情況，-G2[i]出現(xiàn)在E中，那么E和(E-G2[i])·G2[i]都是G2[1,i]的范例.

引理5令E1和E2是G2[1,i-1]的兩個(gè)范例，E1和E2最少有s+1個(gè)基因.基因家族|G2[i]|在G2中是第一次出現(xiàn).如果E1和E2有相同的s-terminal，同時(shí)d(E1,G1)≤d(E2,G1)，那么E1·G2[i]和E2·G2[i]有相同的s-terminal，并且d(E1·G2[i],G1)≤d(E2·G2[i],G1)[17].

科思創(chuàng)中國(guó)區(qū)總裁盛秉勇（Bjoern Skogum）表示：“可持續(xù)發(fā)展是科思創(chuàng)的核心戰(zhàn)略支柱之一，中國(guó)正對(duì)化工行業(yè)進(jìn)行大規(guī)模整治重組，以實(shí)現(xiàn)可持續(xù)發(fā)展。在這一背景下成為行業(yè)榜樣意義重大。作為一家跨國(guó)企業(yè)，科思創(chuàng)將繼續(xù)為中國(guó)化工行業(yè)的可持續(xù)發(fā)展作貢獻(xiàn)，到2025年將生產(chǎn)每噸產(chǎn)品產(chǎn)生的二氧化碳排放較2005年降低50%，利用我們?nèi)蚧膶I(yè)知識(shí)讓中國(guó)更美好。”

引理6令E1和E2是G2[1,i-1]的兩個(gè)范例，E1和E2最少有s+1個(gè)基因，而且基因家族|G2[i]|在G2中是第二次出現(xiàn).如果E1和E2有相同的s-terminal，而且d(E1,G1)≤d(E2,G1)，這里有兩種情況，第一種情況，G2[i]出現(xiàn)在E1和E2中，那么(E1G2[i]·G2[i]和(E2G2[i])·G2[i]有相同的s-terminal，而且d((E1G2[i])·G2[i],G1)≤d((E2G2[i])·G2[i],G1)；第二種情況，-G2[i]出現(xiàn)在E1和E2中，那么(E1-G2[i])·G2[i]和(E2-G2[i])·G2[i]有相同的s-terminal，而且d((E1-G2[i])·G2[i],G1)≤d((E2-G2[i])·G2[i],G1).

證明第一種情況和第二種情況本質(zhì)是相同的.我們不妨證明第二種情況.令E1=E1[1],E1[2],…,E1[k],E2=E2[1],E2[2],…,E2[k],E1′=(E1-G2[i])·G2[i],E2′=(E2-G2[i])·G2[i].因?yàn)榛蚣易鍇G2[i]|在G2中是第二次出現(xiàn)，而且跨度是s，那么-G2[i]必定在E1[k-s,k]和E2[k-s,k]中.因?yàn)镋1[k-s,k]=E2[k-s,k]，那么(E1[k-s,k]-G2[i])·G2[i]=(E2[k-s,k]-G2[i])·G2[i]，也就是E1′[k-s,k]=E2′[k-s,k].因?yàn)镚2[i]的跨度是s，-G2[i]≠E1[k-s]，-G2[i]≠E2[k-s].那么d(E1′,G1)=d(E1,G1)-d(E1[k-s],G1)+d(E1′[k-s,k],G1)和d(E2′,G1)=d(E2,G1)-d(E2[k-s],G1)+d(E2′[k-s,k],G1).因?yàn)閐(E1,G1)≤d(E2,G1)，那么d(E1′,G1)≤d(E2′,G1).

引理7Ex(G2[1,i])的最小s-kernel肯定包含G2[1,i]相對(duì)于G1而言的最小范例[17].

定理3當(dāng)1≤i≤m，令KEx[i-1]是Ex(G2[1,i-1])的最小s-kernel，那么Ex(G2[1,i])的最小s-kernelKEx[i]能用如下方法遞歸計(jì)算：

(1)當(dāng)i=1時(shí)，KEx[i]={G2[1]}；

(2)當(dāng)i≥2時(shí)，基因家族|G2[i]|在G2中第一次出現(xiàn)，KEx[i]=MK(KEx[i-1]·G2[i])；

(3)當(dāng)i≥2時(shí)，基因家族|G2[i]|在G2中第二次出現(xiàn)，且G2[i]出現(xiàn)在G2[1,i-1]中，KEx[i]=MK(KEx[i-1]∪((KEx[i-1]G2[i])·G2[i]))；

(4)當(dāng)i≥2時(shí)，基因家族|G2[i]|在G2中第二次出現(xiàn)，且-G2[i]出現(xiàn)在G2[1,i-1]中，KEx[i]=MK(KEx[i-1]∪((KEx[i-1]-G2[i])·G2[i])).

證明當(dāng)i=1時(shí)，KEx[i]={G2[1]}是顯而易見的.當(dāng)i≥2時(shí)，有以下兩種情況.

(a) 如果基因家族|G2[i]|在G2中第一次出現(xiàn)，由引理3可知，G2[1,i]的每個(gè)范例都在Ex(G2[1,i-1])·G2[i]中.因?yàn)镵Ex[i-1]是Ex(G2[1,i-1])的s-kernel，每個(gè)在Ex(G2[1,i-1]·G2[i])串都對(duì)應(yīng)于一個(gè)在KEx[i-1]·G2[i]的串，這些對(duì)應(yīng)的串都有相同的s-terminal.也就是說，MK(KEx[i-1]·G2[i])肯定是Ex(G2[1,i-1])的s-kernel.對(duì)于任意一個(gè)范例E，E∈Ex(G2[1,i-1])，令E′是在KEx[i-1]中的范例，而且與E有相同的s-terminal.因?yàn)镵Ex[i-1]是Ex(G2[1,i-1])的最小s-kernel，d(E′,G1)≤d(E,G1).由引理5可知，E′·G2[i]與E·G2[i]有相同的s-terminal，而且d(E′·G2[i],G1)≤d(E·G2[i],G1).也就是說，MK(KEx[i-1]·G2[i])肯定是Ex(G2[1,i-1])的最小s-kernel.

(b) 如果基因家族|G2[i]|在G2中第二次出現(xiàn)，也就是說可能G2[i]出現(xiàn)在G2[1,i-1]中，可能-G2[i]出現(xiàn)在G2[1,i-1]中，這兩種情況肯定有一種情況發(fā)生.不妨假設(shè)-G2[i]出現(xiàn)在G2[1,i-1]中.由引理4可知，G2[1,i]的每個(gè)范例肯定在Ex(G2[1,i-1])和(Ex(G2[1,i-1])-G2[i])·G2[i]并集中.因?yàn)镵Ex[i-1]是Ex(G2[1,i-1])的s-kernel.對(duì)于一個(gè)在Ex(G2[1,i])中的串，肯定在KEx[i-1]或(KEx[i-1]-G2[i])·G2[i]中有一個(gè)串和它對(duì)應(yīng)，這兩個(gè)串有相同的s-terminal.令E是Ex(G2[1,i-1])中任意一個(gè)范例，令E′是在KEx[i-1]中的范例，而且與E有相同的s-terminal.因?yàn)镵Ex[i-1]是Ex(G2[1,i-1])的最小s-kernel，d(E′,G1)≤d(E,G1).由引理7可知，E′和(E′-G2[i])·G2[i]都是G2[1,i]的范例.由引理6可知，(E′-G2[i])·G2[i]與(E-G2[i])·G2[i]有相同的s-terminal，而且d((E′-G2[i])·G2[i],G1)≤d((E-G2[i])·G2[i],G1).總結(jié)一下，MK(KEx[i-1]∪((KEx[i-1]-G2[i])·G2[i]))肯定是返回Ex(G2[1,i])的一個(gè)最小s-kernel.同理可得，如果G2[i]出現(xiàn)在G2[1,i-1]，MK(KEx[i-1]∪((KEx[i-1]G2[i])·G2[i]))肯定是返回Ex(G2[1,i])的一個(gè)最小s-kernel.

由定理3知，Z.Wei和D.Zhu的固定參數(shù)化算法可以用來解決有向基因組EBD(1,2).相對(duì)于G1而言，有向動(dòng)態(tài)規(guī)劃算法可以在Ex(G2[1,m])即Ex(G2)中找到最小范例.這個(gè)算法稱為SignedExemplar(G1,G2)，其中MK和min(KEx)含義參照表1，算法描述如下.

Algorithm SignedExemplar(G1,G2)

Input:∑={1,2,3,…,n}上平凡有向基因組G1和不平凡有向基因組，其中Gi[j]=k或Gi[j]=

-k，k∈∑，i=1,2,1≤j≤n.

Output:相對(duì)于G1而言，G2的最小范例

當(dāng)i=1時(shí)，KEx={G2[1]};

fori=2 tomdo

if |G2[i]|是第一次出現(xiàn)

KEx=MK(KEx·G2[i]);

else

ifG2[i]出現(xiàn)在G2[1,i-1]中

KEx=MK(KEx∪((KExG2[i])·G2[i]))

else-G2[i]出現(xiàn)在G2[1,i-1]中

KEx=MK(KEx∪((KEx-G2[i])·G2[i]))

end if

end if

end for

return min(KEx)

3結(jié)語

Z.Wei和D.Zhu的固定參數(shù)化動(dòng)態(tài)規(guī)劃算法可解決無向EBD(1,2)，我們優(yōu)化了該算法的時(shí)間復(fù)雜度，通過對(duì)比試驗(yàn)，驗(yàn)證了我們算法的高效性.當(dāng)給定基因序列是有向時(shí)，通過適當(dāng)?shù)匦拚覀冏C明Z.Wei和D.Zhu的固定參數(shù)動(dòng)態(tài)規(guī)劃算法適合求解有向(1,2)-范例斷點(diǎn)距離.因?yàn)闆]有遇到任何一個(gè)EBD(1,2)實(shí)例有O(4s)個(gè)s-kernel范例集，所以固定參數(shù)化算法是否能給出一個(gè)更好的復(fù)雜度分析有重要的意義.

參考文獻(xiàn)

[1]LiZM,WangLS.ZhangKZ.Algorithmicapproachesforgenomerearrangement:areview[J].IEEETransactionsonSystems,Man,andCybernetics,PartC(ApplicationandReviews),2006,36(5): 636-648.

[2]BlinG,ChauveC,FertinG,etal.Comparinggenomeswithduplications:acomputationalcomplexitypointofview[J].IEEE/ACMTransanctionsonComputationalBiologyandBioinformatics,2010,4(4):523-534.

[3]BlinG,FertinG,SikoraF,etal.Theexemplarbreakpointdistancefornontrivialgenomescannotbeapproximted[M].Heidelberg:Springer,2009:357-368.

[4]AngibaudS,FertinG,RusuI,etal.Ontheapproximabilityofcomparinggenomeswithduplicatess[J].JournalofGraphAlgorithmsandApplications,2009,13(1): 19-53.

[5]SankoffD.Genomerearrangementwithgenefamilies[J].Bioinformatics,1999,15(11): 909-917.

[6]NguyenCT,TayYC,ZhangL.Divide-and-conquerapproachfortheexemplarbreakpointdistance[J].Bioinformatics,2005,21(10):2171-2176.

[7]BryantD.Thecomplexityofcalculatingexemplardistances[M].Berlin:SpringerNetherlands,2000:207-211.

[8]ChenZ,FuB,ZhuB.Theapproximabilityoftheexemplarbreakpointdistanceproblem[M].Heidelberg:Springer,2006: 291-302.

[9]BulteauL,JiangM.Inapproximabilityof(1,2)-exemplardistance[J].IEEE/ACMTransactionsonComputationalBiology&Bioinformatics,2012,10(6):1384-1390.

[10]ZhuB.Approximabilityandfixed-parametertractabilityfortheexemplargenomicdistanceproblems[C]//ZhuBinhai.TheoryandApplicationsofModelsofComputation.Heidelberg:Springer,2009:71-80.

[11]AlonN,YusterR,ZwickU.Colorcoding[J].JournaloftheACM,1995,42(4): 844-856.

[12]FuB,ZhangL.Apolynomialalgebramethodforcomputingexemplarbreakpointdistance[C]//FuBin,ZhangLouxin.BioinformaticsResearchandApplications.Heidelberg:Springer,2011:297-305.

[13]JiangM.Thezeroexemplardistanceproblem[J].JournalofComputationalBiology,2011,18(9): 1077-1086.

[14]ZhuDM,WangLS.Anexactalgorithmforthezeroexemplarbreakpointdistanceproblem[J].IEEE/ACMTransanctionsonComputationalBiologyandBioinformatics,2013,10(6): 1469-1477.

[15]AngibaudS,FertinG,RusuI,etal.Efficienttoolsforcomputingthenumberofbreakpointsandthenumberofadjacenciesbetweentwogenomeswithduplicategenes[J].JournalofComputationalBiology,2008,15(8):1093-1115.

[16]BonizzoniP,VedovaGD,DondiR,etal.Exemplarlongestcommonsubsequence[J].IEEE/ACMTransactionsonComputationalBiologyandBioinformatics,2007,4(4): 535-543.

[17]WeiZX,ZhuDM,WangLS.Aparameterizedalgorithmfor(1,2)-exemplarbreakpointdistance[C]//IEEE.2014IEEEInternationalConferenceonBioinformaticsandBiomedicine(BIBM).Washington:IEEEComputerSociety,2014:11-16.

[18]WeiZX,ZhuDM.Adynamicprogrammingalgorithmforunsigned(1,2)-exemplarbreakpointdistanceproblemwithspanconstraint[C]//IEEE.2013SixthInternationalConferenceonBusinessIntelligenceandFinancialEngineering.Washington:IEEEComputerSociety,2013:39-43.

[19]ShiG,ZhangL,JiangT.MSOAR2.0:Incorporatingtandemduplicationsintoorthologassignmentbasedongenomerearrangement[J].BMCBioinformatics,2010,11(1):1-14.

AnImprovedParameterizedDynamicProgrammingAlgorithmfor(1,2)-ExemplarBreakpointDistance

Li Zimao, Li Xiang

(CollegeofComputerScience,South-CentralUniversityforNationalities,Wuhan430074,China)

AbstractInordertoimprovethecomputationalefficiencyofZ.WeiandD.Zhu′salgorithm,thispaperimprovesthetimecomplexityofZ.WeiandD.Zhu′salgorithmtoO(s24sn)byintroducinganglobalarrayMaptoavoidrepeatedlycomputingoftheadjacenciesofgenefamilies,whilethespacecomplexitykeepsO(s4sn).Ifthegivengenomesissigned,weshowthatZ.WeiandD.Zhu′sfixedparameterdynamicprogrammingalgorithmissuitabletocomputethesigned(1, 2)-exemplarbreakpointdistanceafterminorrevision.ThealgorithmsareimplementedbyusingC++language,andsimulationsindicatetheproposedalgorithms′effectiveness.

Keywordsgenome;exemplar;breakpoint;dynamicprogramming

收稿日期2016-03-18

作者簡(jiǎn)介李子茂(1974-)，男，副教授，博士，研究方向：算法設(shè)計(jì)與分析、計(jì)算復(fù)雜性，E-mail：3030207@mail.scuec.edu.cn

基金項(xiàng)目湖北省自然科學(xué)基金資助項(xiàng)目(61379059)

中圖分類號(hào)TP312

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1672-4321(2016)02-0116-06