柳 楠，李勝華，朱永琦

(山東建筑大學 計算機科學與技術學院，山東 濟南 250101)

0 引 言

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

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

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

1 相關概念

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

每一個排列或者序列中所有的基因的集合是一個多重子集。設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中的符號集合的多重子集c(G)={a,a,b,c,d,d,f}。含有k個基因組成的子序列記為k-串(k≥1)，串的長度等于串中基因數(shù)量。通常稱一個2-串為一個匹配對，定義匹配對xy和匹配對yx是相等的(xy=yx)。

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

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

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

圖1 鄰接、斷點以及其他定義的相關示例

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

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

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

最大缺失基因串是一個完整的contig(即缺失串兩端都是·)，下面是一個簡單的例子(例子中用矩形框標識出缺失串)：

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

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

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

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

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

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

最大缺失基因串兩端都沒有·，只能各自插入對應slot中：

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

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

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

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

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

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

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

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

2 基于一類實例的多項式時間算法

因為輸入的兩個排列都是由contig組成的，所以在插入缺失基因時，缺失基因的插入位置會受到影響和限制，填充問題變得異常艱難。該文主要基于contig的無重復雙面片段填充的一類實例，實例中缺失串類型只有type-1類型、type-2的一種類型(一一對應)和type-3類型。并且重點依據(jù)插入type-1類型字符串進行描述，設計了一個多項式時間為O(n2)的算法，為后面進一步解決問題奠定了基礎。

為了保證算法正確性，在設計一類TSSF-max-BC的多項式時間算法前，先證明下面引理。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

首先初始化數(shù)據(jù)，根據(jù)輸入的不完整片段A和B計算出缺失基因集合X=c(B)-c(A)≠?,Y=c(A)-c(B)≠?,然后遍歷兩個排列，將連續(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 處理一一對應關系的缺失基因

由2.1,已經(jīng)合并了所有連續(xù)的缺失串，現(xiàn)在考慮含有一一對應關系的字符串，采用貪婪式搜索，確定插入位置，然后鎖住slot，簡化更新缺失基因集合為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-串無其他相鄰缺失基因)

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

k-串符合一一對應關系，插入slot并刪除該slot

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

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

k-串符合一一對應關系，插入slot并刪除該slot

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

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

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

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

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

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

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

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

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

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

之后，使用局部搜索和貪婪搜索，發(fā)現(xiàn)type-1-I類型字符串，同時從左向右掃描缺失基因集合X''',Y'''，如果兩個最大缺失基因串有相同的公共基因，且slot位于最大缺失基因串的不同側，則兩個缺失串可以扭在一起構成type-1鄰接，鎖定slot，通過剪枝簡化更新缺失基因集合為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-串有不同側slot

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

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

2.5 插入type-3字符串

最后，X''''和Y''''中只剩下type-3類型的缺失基因，從左到右遍歷X'''',Y''''，若缺失基因包含slot，則組成一組，然后把兩組扭在一起。對剩余缺失基因，把缺失基因合并到一起放入排列的尾部的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的雙面片段填充問題的實例可以在O(n2)內(nèi)解決。

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

3 算法測試平臺的實現(xiàn)

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

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

圖2 基因填充界面

如圖2所示，輸入：

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

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

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

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

表1 7類驗證實例

4 算法比較與分析

近年來，越來越多的研究團隊關注到基因組片段填充問題，但大部分都是針對含重復基因的單面基因組片段填充問題和含重復基因的雙面基因組片段填充問題，針對基于contig的基因組片段填充方向少之又少。

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

表2 TSSF-max-BC問題算法比較

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

圖3 文獻[20]算法填充結果

5 結束語

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