柳 楠，李勝華，朱永琦

(山東建筑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250101)

0 引 言

基因測(cè)序是一種新型的生物基因檢測(cè)技術(shù)[1-6]。最早提出基因組片段填充問(wèn)題的是Munoz等[7]。后來(lái)，H.Jiang等[8]研究了基于斷點(diǎn)距離不含重復(fù)基因的雙面填充問(wèn)題，證明了在雙面情況下，每個(gè)片段作為另一個(gè)片段的參考，也是多項(xiàng)式可解的。

當(dāng)允許基因組和片段中出現(xiàn)重復(fù)基因，那么缺失基因可插入的位置就變得更加復(fù)雜，填充問(wèn)題就變得異常棘手。針對(duì)單面片段填充問(wèn)題，相關(guān)研究如文獻(xiàn)[9-13]已經(jīng)將近似比由1.3提高到1.2。針對(duì)雙面片段填充問(wèn)題，相關(guān)研究如文獻(xiàn)[14-17]已經(jīng)將近似比由2提高1.4。實(shí)際上，標(biāo)準(zhǔn)基因組數(shù)據(jù)集中的片段通常由一系列連續(xù)的重疊群(contig)構(gòu)成。目前contig可以由成熟的軟件Celera Assembler[18]計(jì)算獲取。針對(duì)基于contig的重復(fù)基因的單面片段填充問(wèn)題，F(xiàn)eng Q等人[19]基于構(gòu)造的輔助圖和在輔助圖中尋找最大匹配的兩個(gè)應(yīng)用，設(shè)計(jì)了一個(gè)能真正解決這個(gè)問(wèn)題的2.57-近似算法。然而，針對(duì)基于contig的雙面片段填充卻很少有研究。Chunliang L等人[20]針對(duì)基于contig的雙面片段填充問(wèn)題給出了一個(gè)多項(xiàng)式時(shí)間算法并證明了算法的正確性。Chunliang L等人給出的算法只適用于基于contig填充問(wèn)題的一類實(shí)例情況。該文拓寬了Chunliang L的實(shí)例范圍。

該文主要基于contig的無(wú)重復(fù)雙面基因組片段填充問(wèn)題的一類實(shí)例，提出多項(xiàng)式時(shí)間算法，證明合并符合條件的連續(xù)缺失串不會(huì)影響最優(yōu)解，通過(guò)貪婪思想搜索type-1類型缺失串，優(yōu)先插入可以確定位置的缺失基因(一一對(duì)應(yīng)關(guān)系)，并完成了算法測(cè)試程序開(kāi)發(fā)，進(jìn)一步驗(yàn)證了算法的有效性。

1 相關(guān)概念

在研究生物的基因序列過(guò)程中[21]，通常用一個(gè)正整數(shù)來(lái)表示一個(gè)基因，如(1,4,7,3,9)。為了避免使用較大的整數(shù)，該文引用一些英文符號(hào)，甚至區(qū)分英文字母的大小寫，用數(shù)字和英文字符混合來(lái)表示一個(gè)基因片段，如(1,A,b,k,3,D)，一個(gè)數(shù)字或者一個(gè)英文符號(hào)就代表一個(gè)基因。與此同時(shí)，為了方便起見(jiàn)，假設(shè)所有的基因和基因組都是無(wú)符號(hào)的，可以將結(jié)果推廣到有符號(hào)基因組。假設(shè)Σ是一組符號(hào)集合，如果其中的符號(hào)在一個(gè)基因片段中只出現(xiàn)一次，稱這個(gè)基因片段是排列(Permutation),如果Σ中的符號(hào)在一個(gè)基因組片段中出現(xiàn)不止一次，稱這個(gè)基因片段是序列(Sequence)。簡(jiǎn)而言之，不包含重復(fù)基因的基因片段成為排列，包含重復(fù)基因的基因片段成為序列。

每一個(gè)排列或者序列中所有的基因的集合是一個(gè)多重子集。設(shè)G是基于Σ的片段，G=x[1]x[2]…x[n]，記c(G)為G的多重子集，則多重子集c(G)={x[1],x[2],…,x[n]}。例如，∑={a,b,c,d,e,f,g}，G=abcdadf，則G中的符號(hào)集合的多重子集c(G)={a,a,b,c,d,d,f}。含有k個(gè)基因組成的子序列記為k-串(k≥1)，串的長(zhǎng)度等于串中基因數(shù)量。通常稱一個(gè)2-串為一個(gè)匹配對(duì)，定義匹配對(duì)xy和匹配對(duì)yx是相等的(xy=yx)。

給定兩個(gè)基于Σ的字符串A=a1a2…an和B=b1b2…bm，定義一個(gè)匹配對(duì)集合，包含序列所有的2-串。p(A)={a1a2,…,an-1an}，p(B)={b1b2,…,bm-1bm}。對(duì)于兩個(gè)匹配對(duì)，aiai+1∈p(A)，bjbj+1∈p(B)(或者bj+1bj∈p(B))，如果aiai+1=bjbj+1(或aiai+1=bj+1bj)，則稱構(gòu)成匹配關(guān)系，構(gòu)成匹配關(guān)系的aiai+1稱為A中相對(duì)于B的一個(gè)公共鄰接，不具有匹配關(guān)系的ajaj+1稱為A中相對(duì)于B的一個(gè)斷點(diǎn)。

可以看出，A和B有相同的鄰接數(shù)，但是斷點(diǎn)數(shù)可不同。用α(A,B)表示A相對(duì)于B的鄰接集合，顯然，|α(A,B)|=|α(B,A)|。用M表示p(A)和p(B)之間的一個(gè)最大匹配，b(A)和b(B)分別表示A和B中的斷點(diǎn)集合。

為了更好地理解上面的定義，相關(guān)示例如圖1所示。

圖1 鄰接、斷點(diǎn)以及其他定義的相關(guān)示例

定義contig是位于基因集∑之上的字符串，其內(nèi)部不能被插入任何缺失基因，對(duì)于一個(gè)片段A，A是由一組連續(xù)的contig序列組成的片段，A=〈C1,C2,…,Cm〉，c(A)=c(C1)∪c(C2)∪…∪c(Cm)。定義αi、βi(i=1,2,…,m)分別是contig中Ci的第一個(gè)和最后一個(gè)符號(hào)，當(dāng)|Ci|=1時(shí)，αi=βi。缺失基因只能插入到〈βi-1,αi〉或者〈βi,αi+1〉之間的區(qū)域，即缺失基因只能插入到每個(gè)contig的第一個(gè)符號(hào)之前(左側(cè))或者最后一個(gè)符號(hào)之后(右側(cè))區(qū)域，可插入的區(qū)域稱為一個(gè)slot(插入槽)，該文用·表示一個(gè)slot。值得注意的是，在A的兩端也是有兩個(gè)可插入slot的(α1左側(cè)和βm右側(cè))，為了方便起見(jiàn)，將其定義為〈·,α1〉和〈βm,·〉。

通常定義，type-1：插入n個(gè)缺失串產(chǎn)生n+1個(gè)鄰接。type-2：插入n個(gè)缺失串產(chǎn)生n個(gè)鄰接。type-3：插入n個(gè)缺失串產(chǎn)生n-1個(gè)鄰接。Li等人在文獻(xiàn)[20]中也給出了類似定義。根據(jù)文獻(xiàn)[20]的研究，該文更加詳細(xì)地劃分type-1類型字符串的種類。

(1)I型type-1：缺失串由X和Y中的基因共同組成。

最大缺失基因串是一個(gè)完整的contig(即缺失串兩端都是·)，下面是一個(gè)簡(jiǎn)單的例子(例子中用矩形框標(biāo)識(shí)出缺失串)：

A: ·1·abc·5·A*:·1abc2345·

B: ·1·234·5·B*: ·1abc2345·

最大缺失基因串的兩端只有一個(gè)·，并且在A和B中，與公共基因在同一個(gè)slot的位置是互補(bǔ)的(A中缺失串左邊有·，那么B中缺失串右邊就要有·)，下面是一個(gè)簡(jiǎn)單的例子：

A: ·1abc·5·A*: ·1abc2345·

B: ·1·2345·B*: ·1abc2345·

(2)II型type-1：缺失串僅由X或者Y中基因組成。

最大缺失基因串兩端都沒(méi)有·，只能各自插入對(duì)應(yīng)slot中：

A: ·1abc5e·f·A*:·1abc5e123f·

B: ·1·5e123f·B*:·1abc5e123f·

最大缺失基因串兩端只包含一個(gè)·，并且·在同一側(cè)：

A: ·1·abc5e·f·A*:·1abc5e123f·

B: ·1·5e·123f·B*:·1abc5e123f·

定義1：基于contig的最大化鄰接的雙面片段填充問(wèn)題(TSSF-max-BC)。

輸入：給定兩個(gè)基于排列〈C1,C2,…,Cm〉的不完整基因組A和B，重疊群Ci是基于∑的集合，X=c(B)-c(A)≠?，Y=c(A)-c(B)≠?。

問(wèn)題：將X=c(B)-c(A)插入到A中得到A*，將Y=c(A)-c(B)插入到B中得到B*，使得|α(A*,B*)|-|α(A,B)|值最大。

2 基于一類實(shí)例的多項(xiàng)式時(shí)間算法

因?yàn)檩斎氲膬蓚€(gè)排列都是由contig組成的，所以在插入缺失基因時(shí)，缺失基因的插入位置會(huì)受到影響和限制，填充問(wèn)題變得異常艱難。該文主要基于contig的無(wú)重復(fù)雙面片段填充的一類實(shí)例，實(shí)例中缺失串類型只有type-1類型、type-2的一種類型(一一對(duì)應(yīng))和type-3類型。并且重點(diǎn)依據(jù)插入type-1類型字符串進(jìn)行描述，設(shè)計(jì)了一個(gè)多項(xiàng)式時(shí)間為O(n2)的算法，為后面進(jìn)一步解決問(wèn)題奠定了基礎(chǔ)。

為了保證算法正確性，在設(shè)計(jì)一類TSSF-max-BC的多項(xiàng)式時(shí)間算法前，先證明下面引理。

引理1：假設(shè)s是插入A(B)的type-1類型缺失串，存在一個(gè)最優(yōu)解A*包含缺失串s。

證明：假設(shè)s是type-1類型缺失串,插入到slot〈βi,αi+1〉中，產(chǎn)生|s|+1個(gè)鄰接。WLOG，假設(shè)在一些解中，s被破壞分割成s1和s2，因此，s1和s2分別插入兩個(gè)不同的slot，至少有一個(gè)slot不是〈βi,αi+1〉。然后，WLOG，把s1t插入slot〈βi,αi+1〉，s2插入另外一個(gè)slot，s最多能夠產(chǎn)生(|s1|+|t|)+(|s2|-1)=|s|+|t|-1個(gè)鄰接。然后交換t和s2的位置，至少能獲得(|s|+1)+(|t|-1)=|s|+|t|個(gè)鄰接。這是因?yàn)閠在slot〈βi,αi+1〉必然是一個(gè)type-2或者type-3的字符串，并且，如果s2不與s1插入相同一個(gè)slot，s2必然也是一個(gè)type-2或者type-3的字符串。這是因?yàn)锽和任何一個(gè)有效解A'中的基因只出現(xiàn)一次。

引理2：假設(shè)s對(duì)于slot〈βi,αi+1〉是一個(gè)type-1類型缺失串，存在一個(gè)最優(yōu)解，若s插入該slot，其他缺失串不可再插入。

證明：WLOG，假設(shè)在一些解A'中，s已經(jīng)被插入到slot〈βi,αi+1〉，之后，字符串t被插入相同的slot。由引理1可知，t僅僅能被插入βi之后或者αi+1之前。顯然，此時(shí)t不是type-2型就是type-3型。然后把t從slot 〈βi,αi+1〉中移除，插入A'的最左邊或者最右邊的slot中。在不減少鄰接數(shù)量的情況下，得到一個(gè)滿足引理?xiàng)l件的新解。

上面的引理基本表明，如果s是一個(gè)type-1類型的缺失串，那么將其插入到相應(yīng)的slot并鎖定，不允許其他缺失串插入，不會(huì)破壞最優(yōu)解。優(yōu)先插入type-1類型字符串，并鎖定slot，這樣對(duì)于后面插入其他字符串帶來(lái)了極大的便利。

引理3：當(dāng)一個(gè)type-2類型缺失基因串s與某slot形成一一對(duì)應(yīng)關(guān)系，那么可以鎖定slot，確定s的最終插入位置，存在一個(gè)最優(yōu)解包含s。

證明：(1)WLOG，假設(shè)在排列A中，s是一個(gè)type-2類型缺失基因串，插入到slot中能夠構(gòu)成|s|個(gè)鄰接。假設(shè)s左側(cè)相鄰的公共基因H1在排列B中其兩側(cè)沒(méi)有slot。假設(shè)s右側(cè)相鄰的公共基因H2不會(huì)與其他公共基因構(gòu)成鄰接并且在排列B中H2兩側(cè)只有一個(gè)slot。A中形式為…H1sH2…，B中形式為…H1H2·H3…，此時(shí)s只能插入到H2的slot構(gòu)成|s|個(gè)鄰接，形式為…H1H2sH3…。(2)WLOG，假設(shè)在排列A中，s是一個(gè)type-2類型缺失基因串，插入到slot中能夠構(gòu)成|s|個(gè)鄰接。假設(shè)s左側(cè)相鄰的公共基因H1在排列B中其兩側(cè)沒(méi)有slot。假設(shè)s右側(cè)相鄰的公共基因H2會(huì)與H3構(gòu)成鄰接并且在排列B中僅有H2與H3之間的一個(gè)slot。排列A中形式為…H1sH2H3…，排列B中形式為…H1H2·H3…，當(dāng)s插入到slot時(shí)，破壞了原有的H2H3鄰接，但是在解A′中，此時(shí)鄰接數(shù)為|s|，形式為…H1H2sH3…，若保持H2H3鄰接不被破壞，那么s放入排列尾部，由type-2類型缺失串變?yōu)閠ype-3類型缺失串，構(gòu)成|s|-1個(gè)鄰接，在解A'中，此時(shí)鄰接數(shù)仍是|s|-1+1=|s|，形式為…H1H2H3…s…，那么可以將其轉(zhuǎn)換成…H1H2sH3…，而保持鄰接數(shù)不變，所以確定符合一一對(duì)應(yīng)關(guān)系的缺失基因串位置，不會(huì)影響最終的最優(yōu)解。

由上面證明可以得出，當(dāng)出現(xiàn)某個(gè)type-2類型缺失串只能插入某個(gè)slot時(shí)，并且此時(shí)slot也只有該缺失串能插入，形成一一對(duì)應(yīng)關(guān)系時(shí)，可以優(yōu)先確定該缺失串的位置，并且不會(huì)影響最終的最優(yōu)解。在該文設(shè)計(jì)的多項(xiàng)式時(shí)間可解算法中，就是優(yōu)先考慮這種一一對(duì)應(yīng)類型的缺失串，先把它們位置確定，這樣就會(huì)為后面其他類型缺失串的插入排除了一些可能。

在介紹可合并連續(xù)最大缺失串之前，對(duì)于每一種類型中的連續(xù)缺失串進(jìn)行說(shuō)明，(a)…LS1·S2·R…；(b)…L·S1·S2·R…；(c)…L·S1·S2R…。L和R是公共基因，S1和S2是連續(xù)缺失基因串，注意，至少有一個(gè)缺失串的左右兩端都有slot。在下文所說(shuō)的符合條件都是指上面三種類型。

引理4：優(yōu)先合并符合條件的連續(xù)最大缺失串不會(huì)影響最優(yōu)解。

證明：假設(shè)有兩個(gè)連續(xù)的最大缺失串S1和S2，串長(zhǎng)分別為d1和d2，再輸入排列A中符合合并條件的形式有三種：(1)…LS1·S2·R…；(2)…L·S1·S2·R…；(3)…L·S1·S2R…。

其中(1)形式和(3)形式是對(duì)稱形式，只需要證明(1)和(2)即可，對(duì)于缺失串S1和S2，在最優(yōu)解中構(gòu)成鄰接的數(shù)量可以是：在最優(yōu)解中最多構(gòu)成的鄰接數(shù)是d1+1+d2+1-1=d1+d2+1。即S1和S2與排列B中的某些缺失串共同構(gòu)成了type-1類型的串，而排列B中必然是連續(xù)最大缺失串最左右兩側(cè)都有slot的情況，即…L·H1·…·Hn·R…的形式。此時(shí)，S1和S2串的左右邊界基因與鄰接基因都構(gòu)成公共鄰接，即…LS1H1…HnS2R…。在最優(yōu)解中最少能構(gòu)成的鄰接數(shù)是d1+d2-1。即S1和S2連接在一起不與排列B中的任何基因構(gòu)成公共鄰接，即…L…R…S1S2…。在最優(yōu)解中，構(gòu)成鄰接數(shù)是d1+d2。即S1和S2在排列B中要么連接在一起與L或R鄰接，要么分開(kāi)分別與L和R鄰接，即…LS1S2…R…，…L…S1S2R…，…LS1…S2R…。

要想證明未合并缺失串S1和S2的原始排列獲得的最優(yōu)解與合并缺失串S1和S2的排列獲得的最優(yōu)解是等價(jià)的，只需要證明上面的結(jié)果排列中將S1和S2串連接在一起的變換排列與最優(yōu)解排列的鄰接數(shù)相等即可。

針對(duì)(1)形式：在最優(yōu)解中最多能構(gòu)成的鄰接數(shù)是d1+d2+1時(shí)，排列B中必然存在…L·H1·…·Hn·R…，可將S1S2插入排列B的L·H1之間的slot構(gòu)成…LS1S2H1…HnR…，將H1…Hn插入排列A中的S2·R之間的slot，亦構(gòu)成…LS1S2H1…HnR…，此時(shí)鄰接數(shù)是d1+1+d2+1-1=d1+d2+1。在最優(yōu)解中最少能構(gòu)成的鄰接數(shù)是d1+d2-1時(shí)，排列B的最終結(jié)果是…L…R…S1S2…，此時(shí)S1S2就連接在一起。在最優(yōu)解中構(gòu)成的鄰接數(shù)是d1+d2時(shí)，當(dāng)排列B的最終結(jié)果是…LS1S2…R…或…L…S1S2R…時(shí)，S1S2就連接在一起；當(dāng)排列B的最終結(jié)果是…LS1…S2R…時(shí)，可以變換為…LS1S2…R…或…L…S1S2R…，因?yàn)镾1S2在原排列A： …LS1·S2·R…中是鄰接，此時(shí)鄰接數(shù)仍是d1+d2。

針對(duì)(2)形式：在最優(yōu)解中最多能構(gòu)成的鄰接數(shù)是d1+d2+1時(shí)，排列B中必然存在…L·H1·…·Hn·R…，可將S1S2插入排列B的L·H1或Hn·R之間的slot構(gòu)成…LS1S2H1…HnR…或…LH1…HnS1S2R…，將H1…Hn插入排列A中的L·S1或S2·R之間的slot，亦構(gòu)成…LH1…HnS1S2R…或…LS1S2H1…HnR…。也可將S1S2插入B的H1·…·Hn之間的slot構(gòu)成…LH1S1S2H2…HnR…，將H1和H2…Hn分別插入L·S1和S2·R之間的slot，亦構(gòu)成…LH1S1S2H2…HnR…，此時(shí)的鄰接數(shù)是d1+1+d2+1-1=d1+d2+1。在最優(yōu)解中最少能構(gòu)成的鄰接數(shù)是d1+d2-1時(shí)，排列B的最終結(jié)果是…L…R…S1S2…，此時(shí)S1S2就連接在一起。在最優(yōu)解中構(gòu)成的鄰接數(shù)是d1+d2時(shí)，當(dāng)排列B的最終結(jié)果是…LS1S2…R…或…L…S1S2R…時(shí)，S1S2就連接在一起；當(dāng)排列B的最終結(jié)果是…LS1…S2R…時(shí)，可以變換為…LS1S2…R…或…L…S1S2R…，因?yàn)镾1S2在原排列A：…LS1·S2·R…中是鄰接，此時(shí)鄰接數(shù)仍是d1+d2。

由引理4的證明可以看出，優(yōu)先合并符合條件的連續(xù)最大缺失串并不會(huì)影響最優(yōu)解。多個(gè)連續(xù)最大缺失串可以先兩兩合并。該文提出的算法優(yōu)化基于此思想提出，在雙面基因組填充問(wèn)題中，算法優(yōu)化思想如下：

首先合并基因組片段中符合條件的連續(xù)最大缺失串，接著采用貪婪搜索方式，把含有一一對(duì)應(yīng)關(guān)系的缺失基因插入并鎖住slot，在采用貪婪搜索方式發(fā)現(xiàn)type-1-II字符串，插入相應(yīng)位置并鎖住slot，采用局部搜索和貪婪搜索發(fā)現(xiàn)type-1-I字符串，插入相應(yīng)位置并鎖住slot，采用最大匹配方法插入type-2字符串，最后插入type-3字符串。

2.1 合并連續(xù)缺失串

首先初始化數(shù)據(jù)，根據(jù)輸入的不完整片段A和B計(jì)算出缺失基因集合X=c(B)-c(A)≠?,Y=c(A)-c(B)≠?,然后遍歷兩個(gè)排列，將連續(xù)的缺失串合并。

算法1：Merge(A,B)。

輸入:A=〈C1,C2,…,Cm〉,B=〈C1,C2,…,Cn〉

輸出:A',B'

(1)X=c(B)-c(A)≠?,Y=c(A)-c(B)≠?

(2)For (k-串在A(B)內(nèi))

(3)if (在A(B)內(nèi)最大連續(xù)缺失串k-串的左右兩邊都是slot: l-slot, r-slot)

(4) if (l-slot的左邊是缺失串)

(5) k-串向左合并，刪除l-slot

(6) if (l-slot的左邊不是缺失串,r-slot的右邊是缺失串)

(7) k-串向右合并，刪除r-slot

(8) if (l-slot的左邊不是缺失串,r-slot的右邊也不是缺失串)

(9) k-串不能合并

(10) Else

(11) k-串不滿足合并要求，不能合并

(12)更新X',Y',A',B'

2.2 處理一一對(duì)應(yīng)關(guān)系的缺失基因

由2.1,已經(jīng)合并了所有連續(xù)的缺失串，現(xiàn)在考慮含有一一對(duì)應(yīng)關(guān)系的字符串，采用貪婪式搜索，確定插入位置，然后鎖住slot，簡(jiǎn)化更新缺失基因集合為X''和Y''，獲得了片段A''和B''。

算法2：One-One(A',B')。

(1)For (k-串在A'(B')內(nèi))

(2)βk-1是k-串左鄰字符，αk+1是k-串右鄰字符

(3)if (βk-1和αk+1在A'(B')中除k-串無(wú)其他相鄰缺失基因)

if (βk-1和αk+1只包含一個(gè)slot,并且slot不在βk-1和αk+1之間)

k-串符合一一對(duì)應(yīng)關(guān)系，插入slot并刪除該slot

(4) else if (βk-1和αk+1在A'(B')中除k-串不同時(shí)相鄰其他缺失基因)

if (βk-1和αk+1只包含一個(gè)slot且slot不屬于有其他缺失基因的字符)

k-串符合一一對(duì)應(yīng)關(guān)系，插入slot并刪除該slot

(5)更新X'',Y'',A'',B''

2.3 搜索并插入type-1-II字符串

然后采用貪婪搜索來(lái)發(fā)現(xiàn)type-1-II字符串，從左到右掃描缺失基因，若缺失基因的兩個(gè)公共基因在另一個(gè)排列上是相鄰且在不同的contig，就認(rèn)為插入其slot構(gòu)成type-1鄰接，鎖定slot，通過(guò)簡(jiǎn)化更新缺失基因集合為X''和Y''，獲得片段A''和B''。

算法3：Insert-type-1-II(A'',B'')。

(1)For (k-串在A''(B'')內(nèi))

(2)βk-1是k-串前一串的最后一個(gè)字符，αk+1是k-串后一串的第一個(gè)字符

(3) if (在B″(A″)中βk-1和αk+1之間沒(méi)有其他基因)

k-串插入βk-1和αk+1之間的slot，并刪除slot

(4)更新X'',Y'',A'',B''

2.4 搜索并插入type-1-I字符串

之后，使用局部搜索和貪婪搜索，發(fā)現(xiàn)type-1-I類型字符串，同時(shí)從左向右掃描缺失基因集合X''',Y'''，如果兩個(gè)最大缺失基因串有相同的公共基因，且slot位于最大缺失基因串的不同側(cè)，則兩個(gè)缺失串可以扭在一起構(gòu)成type-1鄰接，鎖定slot，通過(guò)剪枝簡(jiǎn)化更新缺失基因集合為X''''和Y''''，獲得片段A''''和B''''。

算法4：Insert-type-1-I(A''',B''')。

(1)For (k-串在A'''內(nèi))

(2)For (m-串在B'''內(nèi))

βk-1是k-串左鄰的公共基因，αk+1是k-串右鄰的公共基因，βm-1是m-串左鄰的公共基因，αm+1是m-串右鄰的公共基因

if (βk-1=βm-1andαk+1=αm+1) or (βk-1=αm+1andαk+1=βm-1) and k-串和m-串有不同側(cè)slot

k-串和m-串可扭在一起，刪除slot

(3)更新X'''',Y'''',A'''',B''''

2.5 插入type-3字符串

最后，X''''和Y''''中只剩下type-3類型的缺失基因，從左到右遍歷X'''',Y''''，若缺失基因包含slot，則組成一組，然后把兩組扭在一起。對(duì)剩余缺失基因，把缺失基因合并到一起放入排列的尾部的slot，獲得最終解A*和B*。

算法5：Insert-type-3(A'''',B'''')。

(1)For (k-串在A''''內(nèi), m-串在B''''內(nèi))

(2)if (k-串包含slot, m-串包含slot)

將k-串和m-串扭在一起

if (k-串包不包含slot, m-串不包含slot)

將k-串和m-串放置B''''(A'''')末尾

(3)更新A*,B*

定理1：一類基于contig的雙面片段填充問(wèn)題的實(shí)例可以在O(n2)內(nèi)解決。

在算法Merge(A,B)中，遍歷兩個(gè)排列，在O(n2)時(shí)間內(nèi)可完成，在算法One-One(A,B)中采用貪婪搜索方式發(fā)現(xiàn)一一對(duì)應(yīng)關(guān)系的缺失基因并插入，可在O(n2)時(shí)間內(nèi)可完成，算法Insert-type-1-II(A',B')，Insert-type-1-I(A'',B'')中，都是采用貪婪搜索的方法去發(fā)現(xiàn)type-1類型字符串，在O(n2)時(shí)間內(nèi)可以完成搜索并且插入相應(yīng)位置。在算法Insert-type-3(A''',B''')中，搜索type-3型字符串并插入，可以在O(n)時(shí)間內(nèi)完成，綜上，算法運(yùn)行時(shí)間為O(n2)。

3 算法測(cè)試平臺(tái)的實(shí)現(xiàn)

該文在完成了這類TSSF-max-BC問(wèn)題的多項(xiàng)式時(shí)間算法后，基于python平臺(tái)實(shí)現(xiàn)了可視化程序用來(lái)驗(yàn)證算法的有效性。在測(cè)試中，可以在程序輸入框中輸入基因組片段A和B，然后程序會(huì)根據(jù)該文設(shè)計(jì)的算法自動(dòng)完成基因組片段填充，在輸出框會(huì)給片段A和B的缺失基因，給出合并缺失基因后的片段，并用紅色標(biāo)記出缺失基因，接著給出最終填充結(jié)果，最后給出鄰接數(shù)。

程序的執(zhí)行如圖2所示。用戶在“基因A”和“基因B”中分別輸入基因組片段A和B，然后點(diǎn)擊“填充”按鈕，會(huì)根據(jù)設(shè)計(jì)的算法自動(dòng)完成填充，在輸出框中顯示，其中缺失基因會(huì)被紅色標(biāo)記。點(diǎn)擊“清空”按鈕會(huì)將主程序界面所有輸入和輸出清空，可以再次輸入并且輸出。點(diǎn)擊“輸出日志”按鈕將會(huì)把界面顯示結(jié)果導(dǎo)出到txt文件。

圖2 基因填充界面

如圖2所示，輸入：

在片段A中，合并缺失基因〈b,cd〉，〈bcd〉是type-1-II類型缺失串，〈st〉與片段B中〈234〉扭在一起形成type-1-I類型缺失串，〈xy〉在contig內(nèi)，并且無(wú)slot可以插入形成鄰接，形成type-3類型缺失串，所以放在片段A末尾，〈n〉是形成一一對(duì)應(yīng)關(guān)系。在片段B中，〈234〉和片段A中〈st〉扭在一起形成type-1-I類型缺失串，〈wz〉在contig內(nèi)，并且無(wú)slot可以插入形成鄰接，形成type-3類型缺失串，所以放在片段B末尾。

填充后的結(jié)果如圖2所示的最優(yōu)解之一，缺失基因在片段中用紅色標(biāo)記：

生成的鄰接總數(shù)為13，這正是最優(yōu)解可以生成的最大鄰接數(shù)。

基于上面實(shí)例之外，還驗(yàn)證了其余100個(gè)實(shí)例，其中包括驗(yàn)證合并符合條件缺失串、type-1-I、type-1-II、type-2(一一對(duì)應(yīng))和type-3以及它們的反轉(zhuǎn)實(shí)例，這7類實(shí)例包括了上述所有驗(yàn)證，結(jié)果全部正確，證明了算法的可行性，如表1所示。

表1 7類驗(yàn)證實(shí)例

4 算法比較與分析

近年來(lái)，越來(lái)越多的研究團(tuán)隊(duì)關(guān)注到基因組片段填充問(wèn)題，但大部分都是針對(duì)含重復(fù)基因的單面基因組片段填充問(wèn)題和含重復(fù)基因的雙面基因組片段填充問(wèn)題，針對(duì)基于contig的基因組片段填充方向少之又少。

Liu等人[22]針對(duì)不含重復(fù)基因的基于contig的單面基因組片段填充問(wèn)題提出了多項(xiàng)式時(shí)間可解算法。其后，F(xiàn)eng Q等人[19]針對(duì)含重復(fù)基因的基于contig的單面片段填充問(wèn)題提出了適用于所有實(shí)例的2.57-近似算法。目前，針對(duì)contig的雙面片段填充問(wèn)題，Chunliang L等人[20]提出了一類基于特殊實(shí)例的多項(xiàng)式時(shí)間可解算法。算法分析對(duì)比如表2所示。

表2 TSSF-max-BC問(wèn)題算法比較

表2展示的是基于contig的雙面基因組片段填充問(wèn)題與基于contig的單面基因組片段填充問(wèn)題的算法對(duì)比，可見(jiàn)針對(duì)單面片段問(wèn)題已可以實(shí)現(xiàn)全部實(shí)例的填充。由于雙面基因組片段填充問(wèn)題更具有普遍性，在文獻(xiàn)[22]和文獻(xiàn)[19]中并沒(méi)有對(duì)雙面填充情況作說(shuō)明。相比文獻(xiàn)[20]中算法，實(shí)例中并沒(méi)有針對(duì)type-2類型缺失串，在該文提出的算法中，擴(kuò)展了文獻(xiàn)[20]中的實(shí)例范圍，使其更加具有普適性。該文也是首次提出優(yōu)先合并連續(xù)缺失串定理的證明，可以在一定程上減少基因組片段填充問(wèn)題的復(fù)雜性。在關(guān)鍵技術(shù)方面，相比文獻(xiàn)[20]，使用最大匹配技術(shù)可以解決一類含有type-2(一一對(duì)應(yīng))的特例填充問(wèn)題。在擴(kuò)展實(shí)例范圍后，算法的時(shí)間復(fù)雜度仍可以保持O(n2)，具有一定優(yōu)勢(shì)。

圖3 文獻(xiàn)[20]算法填充結(jié)果

5 結(jié)束語(yǔ)

針對(duì)基于contig的無(wú)重復(fù)基因的雙面基因組片段填充問(wèn)題的一類實(shí)例，設(shè)計(jì)了一個(gè)采用貪婪策略思想的多項(xiàng)式時(shí)間算法，注意到基因組可能存在缺失基因與slot一一對(duì)應(yīng)的關(guān)系，優(yōu)先解決這一類缺失基因的插入問(wèn)題且不會(huì)破壞最優(yōu)解，然后考慮到type-1類型缺失基因的特殊性，也要優(yōu)先插入且不會(huì)破壞最優(yōu)解，證明了時(shí)間復(fù)雜度為O(n2)和算法的正確性。該文是基于一類實(shí)例研究，接下來(lái)將進(jìn)一步對(duì)一般性實(shí)例進(jìn)行研究以及針對(duì)基于contig的重復(fù)基因的雙面片段填充問(wèn)題進(jìn)行研究。