柳 楠，朱永琦，李勝華，崔曉宇

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

0 引 言

隨著二十世紀(jì)三大科學(xué)計(jì)劃之一的人類基因組計(jì)劃的實(shí)施，大量的生物學(xué)數(shù)據(jù)有待處理[1-4]，如何利用計(jì)算機(jī)建模、仿真等技術(shù)去提取其中有用的數(shù)據(jù)，進(jìn)而研究其中所蘊(yùn)含的生物學(xué)意義，對(duì)計(jì)算機(jī)科學(xué)技術(shù)來(lái)說(shuō)是一項(xiàng)嚴(yán)峻的挑戰(zhàn)[5-6]。因此在二十世紀(jì)提出了一門新興交叉學(xué)科—計(jì)算生物學(xué)。計(jì)算生物學(xué)運(yùn)用數(shù)學(xué)、計(jì)算機(jī)和生物學(xué)相關(guān)理論解決生物學(xué)問(wèn)題，已經(jīng)成為目前最活躍的研究領(lǐng)域之一[7-9]。

基因組片段填充問(wèn)題[10-12]是計(jì)算生物學(xué)極其經(jīng)典的問(wèn)題之一，其中含重復(fù)基因的基因組片段填充問(wèn)題已經(jīng)被證明為NP-完全問(wèn)題[13-14]，如何優(yōu)化基因組片段填充近似算法是近些年來(lái)的討論熱點(diǎn)。依據(jù)基因樣本序列中是否含有重復(fù)基因，將該基因組填充問(wèn)題分為含重復(fù)基因的基因組片段填充問(wèn)題和無(wú)重復(fù)基因的基因組片段填充問(wèn)題；或依據(jù)基因樣本序列不完整數(shù)量，將該基因組填充問(wèn)題分為單面基因組片段填充和雙面基因組片段填充，其中一條序列完整，另一條序列缺失，稱為單面基因組序列，兩條基因序列均為不完整的，則為雙面基因組序列[15]。

該文重點(diǎn)討論單面重復(fù)基因組片段填充問(wèn)題。Munoz和D. Sankoff等人[12-13]首次提出了基于最小重組距離(DCJ距離)的單面基因組填充方法，使用斷點(diǎn)圖設(shè)計(jì)了多項(xiàng)式時(shí)間算法，并證明了基于DCJ距離的單面基因組片段填充算法是多項(xiàng)式可解的。對(duì)于單面無(wú)重復(fù)基因組片段填充問(wèn)題，H. Jiang等人提出了使用DCJ距離或斷點(diǎn)距離為度量的算法，并證明了其是多項(xiàng)式可解的[14]；對(duì)于含重復(fù)基因的基因組片段填充問(wèn)題，H. Jiang等人證明了其是NP-完全的，并提出了4/3-近似算法[14-16]。隨后N. Liu等人采用局部?jī)?yōu)化和貪婪算法將該類問(wèn)題近似度改善到1.25[17-18]；J. Ma等人采用非盲局部搜索策略將該類問(wèn)題近似度進(jìn)一步改善到1.2[19-20]。

在許多應(yīng)用中，基因組序列通常被定義為一系列連續(xù)的片段重疊群(contig)[21]，其中任何一個(gè)contig都不能被破壞，缺失基因的插入只能在contig的兩端執(zhí)行。在此約束下，當(dāng)不存在重復(fù)基因時(shí)，單面基因組片段填充問(wèn)題是多項(xiàng)式可解的；當(dāng)存在重復(fù)基因時(shí)，H. Jiang等人通過(guò)最大化公共鄰接證明了該類問(wèn)題是NP-完全的，并提出了一個(gè)近似值為2的近似算法[22-23]和一個(gè)雙參數(shù)的FPT算法[22](k，公共鄰接數(shù)，d，基因最大重復(fù)數(shù))；L. Bulteau等人給出了一種基于最大鄰接數(shù)和最小斷點(diǎn)距離的k-Mer參數(shù)的FPT算法[24]；Q. Feng等人通過(guò)構(gòu)造輔助圖和二次尋找最大匹配給出了2.57-近似算法[25]。

該文的主要工作有以下三個(gè)方面：系統(tǒng)歸納了基于contig的單面基因組片段填充問(wèn)題的現(xiàn)有算法并通過(guò)實(shí)例實(shí)現(xiàn)了算法，有助于讀者對(duì)此類問(wèn)題的進(jìn)一步了解；在技術(shù)應(yīng)用和時(shí)間復(fù)雜度等方面對(duì)現(xiàn)有算法做了對(duì)比，并分析了該些算法存在的一些弊端；分析接下來(lái)研究工作中面對(duì)的挑戰(zhàn)和可能的解決方案。

1 相關(guān)定義

該文只關(guān)注基于contig的單面基因組片段填充算法，但其結(jié)果可以推廣到多染色體或環(huán)狀基因組。

首先，給出一些必要的定義。不失一般性，假設(shè)所有的基因和基因組都由無(wú)符號(hào)的字母和整數(shù)組成，給定一個(gè)集合Σ和一個(gè)基因序列S，使用c(S)表示基因序列S中所有符號(hào)的集合。如果Σ中的符號(hào)在基因序列S中出現(xiàn)且只出現(xiàn)一次，則稱S是Σ上的一個(gè)排列，否則稱為序列。對(duì)于Σ中的任意兩個(gè)符號(hào)x,y，如果基因序列S至少包含{xy,yx}中的任意一個(gè)子集，那么則稱x,y在S中鄰接，令P(S)為S中所有鄰接的集合。設(shè)A和B是Σ中的兩個(gè)基因序列，A={a1a2…an}，B={b1b2…bm}。對(duì)于P(A)中的任意一個(gè)鄰接aiai+1和P(B)中的任意一個(gè)鄰接bjbj+1，如果aiai+1=bjbj+1(或aiai+1=bj+1bj)，則稱aiai+1與bjbj+1構(gòu)成了公共鄰接，a(A,B)表示A和B的公共鄰接集合，同時(shí)稱(aiai+1,bjbj+1)為一個(gè)匹配對(duì)。如果P(A)和P(B)中不存在aiai+1=bjbj+1(或aiai+1=bj+1bj)，則稱aiai+1相對(duì)于bjbj+1構(gòu)成了斷點(diǎn)，bp(A,B)和bp(B,A)分別表示A和B的斷點(diǎn)集合，如圖1所示。

定義一個(gè)基因組序列是由一系列contig構(gòu)成的，且contig內(nèi)部不能插入缺失基因，即S=，其中Ci為一個(gè)片段重疊群。

下面具體給出One-Sided-SF-max問(wèn)題的概念：

定義1：One-Sided-SF-max問(wèn)題。

輸入：一個(gè)完整的基因組序列G和一個(gè)不完整的基因組序列S，其中S=，基因組序列G和片段重疊群Ci中的基因元素均來(lái)自于符號(hào)集合∑，且缺失基因集合X=c(G)-c(S)≠?。

輸出：將X=c(G)-c(S)≠?插入S得到S'，使得|a(S',G)|最大。

2 One-Sided-SF-max問(wèn)題

One-Sided-SF-max問(wèn)題已經(jīng)被證明為NP-完全的[22]，此類問(wèn)題不能在有效時(shí)間內(nèi)求出精確解，因此設(shè)計(jì)近似算法更具有實(shí)際意義。本節(jié)主要對(duì)One-Sided-SF-max問(wèn)題進(jìn)行簡(jiǎn)要介紹，概括分析了國(guó)內(nèi)外經(jīng)典的三種算法：2-近似算法、2.57-近似算法以及k-Mer算法。

2.1 One-Sided-SF-max問(wèn)題的2-近似算法

該算法由H. Jiang等人提出，主要使用了貪婪和最大匹配的思想來(lái)實(shí)現(xiàn)基于contig的單面基因組片段填充。首先在該算法中給出以下定義：對(duì)于基因序列S=，定義αi和βi分別是contigCi的首尾元素，其中i∈[1,m]。<βi,αi+1>構(gòu)成一個(gè)slot，缺失基因只能插入到slot中。在S的兩端有兩個(gè)開放slot，分別表示為<-∞,α1>和<βm,+∞>。對(duì)于缺失基因x，如果存在一個(gè)公共鄰接xy(或yx)，其中y=αi或y=βi，則稱公共鄰接xy(或yx)為外部鄰接，否則稱公共鄰接xy(或yx)為內(nèi)部鄰接。

定義缺失基因集合X中有一個(gè)長(zhǎng)度為n的子串，如果插入到slot <βi,αi+1>中(1≤i≤m-1)，產(chǎn)生n+1個(gè)新公共鄰接，稱子串為n-Type-1類型串。同樣的，產(chǎn)生n個(gè)新公共鄰接，稱為n-Type-2類型串；產(chǎn)生n-1個(gè)新公共鄰接，稱為n-Type-3類型串。算法大體流程如下：

(1)計(jì)算缺失基因集合X=c(G)-c(S)；

(2)對(duì)于缺失基因集合，采用貪婪策略將1-Type-1類型串插入到相應(yīng)的slot中，并將該slot鎖定，不允許其他缺失基因插入；

(3)構(gòu)造二分圖并求其最大匹配，將1-Type-2類型串插入到可構(gòu)成外部鄰接的slot處，并對(duì)該slot進(jìn)行更新：如果xj插入到slot ?ai前面，那么將此slot更新為?xj，如果?xj插入到slotβi?后面，那么將此slot更新為xj?；

(4)以步驟2后的缺失基因?yàn)轫旤c(diǎn)構(gòu)造多重圖：若x∈X，y∈X且xy為G中一個(gè)內(nèi)部鄰接，那么x和y之間添加一條邊，尋找最大匹配M。對(duì)于最大匹配M中的所有匹配對(duì)xy，如果x為步驟3中插入的元素，則將y插入到相應(yīng)slot處使得xy構(gòu)成鄰接；將其余匹配對(duì)xy任意插入到未鎖定slot中，且不能破壞現(xiàn)有鄰接；

(5)在不破壞現(xiàn)有鄰接關(guān)系的前提下，將所有剩余缺失基因任意插入到S中未鎖定的slot處；

(6)得到近似解S'。

對(duì)于該算法，下面通過(guò)一個(gè)實(shí)例(如圖2所示)來(lái)說(shuō)明算法的執(zhí)行過(guò)程：

(2)搜尋1-Type-2類型串，找到2,d,g為1-Type-2類型串，并以1-Type-2類型串集合和未鎖定slot集合為頂點(diǎn)，構(gòu)造二分圖，建立的二分圖BG1如圖3所示。

(3)以步驟2之后的剩余缺失基因集合為頂點(diǎn)構(gòu)造多重圖Q，建立的多重圖Q并求得最大匹配，將a插入到g之前，將7插入到d之后，將52插入到a之前。

(5)算法結(jié)束，得到填充后的基因序列S'=

<52ag4k1acbd21d727>。

以上可以看出，通過(guò)此算法可以得到8個(gè)新公共鄰接，同時(shí)此例的最優(yōu)解為S*=<2ag4k1acb1d7527d2>，有13個(gè)新公共鄰接。

所以，

所以有近似解：

該算法為一個(gè)2-近似算法，同時(shí)該算法的運(yùn)行時(shí)間主要由步驟2中計(jì)算O(n)個(gè)頂點(diǎn)的二分圖中的最大匹配以及步驟3中計(jì)算O(n)個(gè)頂點(diǎn)的多重圖中的最大匹配決定，兩者都需要O(n2.5)個(gè)時(shí)間，所以2-近似算法的時(shí)間復(fù)雜度為O(n2.5)。

2.2 One-Sided-SF-max問(wèn)題的2.57-近似算法

Q. Feng提出的2.57-近似算法繼續(xù)考慮了冗余塊對(duì)填充過(guò)程存在的影響。該算法主要使用了最大匹配算法構(gòu)造簡(jiǎn)單路徑來(lái)具體實(shí)現(xiàn)基于contig的單面基因組片段填充問(wèn)題。

首先在該算法中給出以下定義：令F(S)為contigCi的首尾元素集合，F(xiàn)(S)=(α1,β1,…,αm,βm)。如果最大匹配M中有塊xy，xy在最大匹配M中出現(xiàn)的次數(shù)稱為xy的指示數(shù)。設(shè)xy與bp(G,S)中塊ab可構(gòu)成匹配對(duì)(xy,ab)，若xy在M中出現(xiàn)次數(shù)大于ab在bp(G,S)中出現(xiàn)次數(shù)，則稱塊xy為一個(gè)冗余塊。定義⊕為對(duì)稱差，A⊕B=(AB)∪(BA)，令K'為此算法中的兩次最大匹配M1和M2的對(duì)稱差，則K'中每個(gè)連通分量必為簡(jiǎn)單路徑或簡(jiǎn)單循環(huán)。算法的大體流程如下：

(1)計(jì)算缺失基因集合X=c(G)-c(S)和斷點(diǎn)集合bp(G,S)；

(2)基于缺失基因集合X、斷點(diǎn)集合bp(G,S)和S中每個(gè)contig首尾元素集合F(S)構(gòu)造一般圖Γ1，尋找最大匹配M1；

(3)對(duì)于M1中的任意塊xy，有以下三種情況：如果x和y分別為同一個(gè)slot的前后兩端，則合并此相鄰的兩個(gè)contig；如果x(或y)屬于F(S)，將y(或x)插入相應(yīng)的slot中使得xy鄰接；如果x和y均不屬于F(S)，則將其置于圖H'中頂點(diǎn)。依據(jù)以上更新基因序列為S1；

(4)基于G、S1和H'，求得斷點(diǎn)集合bp(G,S1)和F(S1)；

(5)更新圖H'：刪除可與bp(G,S1)中斷點(diǎn)構(gòu)成匹配對(duì)的邊；

(6)基于缺失基因集合X、斷點(diǎn)集合bp(G,S1)和集合F(S1)構(gòu)造一般圖Γ2，尋找最大匹配M2；

(7)Δ=H'⊕M2；

(8)對(duì)于圖Δ中的任意路徑k=p1p2…pt-1pt，判斷其是否為簡(jiǎn)單路徑：若為簡(jiǎn)單路徑，插入到相應(yīng)slot中，反之刪除路徑k中任意一條邊得到新的路徑p1p2…pt-1pt，將路徑p1p2…pt-1pt插入到基因序列的最右側(cè)；更新基因序列為S2；

(9)統(tǒng)一將c(G)-c(S2)插入到序列S2的最右側(cè)；

(10)得到填充完成后的基因序列S'。

下面通過(guò)上述2-近似算法的同一個(gè)實(shí)例(見圖2)來(lái)說(shuō)明算法的執(zhí)行過(guò)程：

(1)計(jì)算斷點(diǎn)集合bp(G,S)=<1a,ac,1d,d7,75,52,24,4g,ga,a2,2k,k7,7d,d2>，計(jì)算S中每個(gè)contig首尾元素集合F(S)=<4,1,c,b,1,1>；

(2)構(gòu)造圖Γ1：X∪F(S)中的所有元素被視為頂點(diǎn)，對(duì)于其中任意兩個(gè)元素x,y，如果有x∈X,y∈X或y∈F(S)且存在一個(gè)斷點(diǎn)β使得與xy構(gòu)成一個(gè)匹配對(duì)，則在x與y之間添加一條邊；如果有x,y∈F(S)，假設(shè)x在contigC1中且為C1中最后一個(gè)元素，y在contigC2中且為C2中第一個(gè)元素，C1和C2相鄰且存在一個(gè)斷點(diǎn)β使得與xy構(gòu)成一個(gè)匹配對(duì)，則在x與y之間添加一條邊。在圖Γ1中尋找最大匹配M1，如圖4所示；

(3)刪除M1中的冗余塊：對(duì)于M1中的塊xy，xy與斷點(diǎn)ω可構(gòu)成匹配對(duì)(xy,ω)，如果xy在M1中的出現(xiàn)次數(shù)大于ω在bp(G,S)中的出現(xiàn)次數(shù)，則稱塊xy為冗余塊并將其刪除；

(4)令{α1,α2,…,αr}為M1中刪除冗余塊后剩余塊的集合，H'為{α1,α2,…,αr}中的塊與bp(G,S)中的斷點(diǎn)構(gòu)成匹配對(duì)的集合，則此例中H'={(ac?ac),(d1?1d),(52?52),(g4?4g),(a2?a2),(d2?d2)}；

(7)計(jì)算X'=c(G)-c(S1)得到缺失基因集合X'=<7,5,2,a,2,7,d,2>，計(jì)算S1中每個(gè)contig首尾元素集合F(S1)=；

(8)計(jì)算新的斷點(diǎn)集合bp(G,S1)=；

(9)使用構(gòu)造圖Γ1的同樣方法構(gòu)造圖Γ2；

(10)如果圖Γ2與圖H'中存在相同邊，則在Γ2中刪除此條邊，此例中，無(wú)此類邊；

(11)在圖Γ2中求得最大匹配M2，如圖5所示。

(12)令Δ=H'⊕M2，此例中Δ=(a2,ag,7d)；

(15)將剩余缺失基因插入到序列S2的最右側(cè)；

(16)得到填充完成后的基因序列S'=。

該算法可以得到8個(gè)公共鄰接，同時(shí)其中一個(gè)最優(yōu)解為<2ag4k1acb1d7527d2>，有13個(gè)新公共鄰接。

該算法的近似性能比為2.57。

2.3 One-Sided-SF-max問(wèn)題的k-Mer近似算法

k-Mer算法從參數(shù)化復(fù)雜性的角度研究基因組填充問(wèn)題，相較于H. Jiang等人提出的2-近似算法，主要有以下三個(gè)方面的不同：

(1)不再限制插入的基因集合為c(G)-c(S)，插入集合可以包含比c(G)-c(S)更多或更少的基因集合；

(2)允許將要插入的字符串?dāng)?shù)量預(yù)先指定為輸入約束，t1為要插入的字符串?dāng)?shù)量的下限，t2為要插入的字符串?dāng)?shù)量的上限(t1≤t2)；

(3)作為相似性度量依據(jù)，不局限于最大化公共鄰接的數(shù)量，相反，對(duì)于一個(gè)預(yù)定的參數(shù)k，最大化公共k-mers的數(shù)目，k值越高，結(jié)果越準(zhǔn)確。

L.Bulteau等人對(duì)于此類問(wèn)題給出以下定義：對(duì)于兩個(gè)基因序列G和S，G°S表示二者的串聯(lián)。存在一個(gè)正整數(shù)k，使得ak(G)={S[i,i+k]|i∈[n-k]}為序列G中k-mers的集合，則ak(G,S)=ak(G)∩ak(S)。設(shè)S[i]表示S中第i個(gè)元素，S[i,j]表示序列S中從位置i到j(luò)的基因元素。對(duì)于一個(gè)完整基因序列G和一個(gè)不完整基因序列S，令pk(S,G)=ak(G)ak(S)表示存在于G中但不存在于S中的k-mers集合，并將此類k-mers稱為潛在的公共k-mers。

定義2：k-Mer Scaffold Filling(k-Mer-SF)。

輸入：一個(gè)完整的基因組序列G和一個(gè)不完整的基因組序列S，其中S=，且存在一個(gè)字符集合T和兩個(gè)整數(shù)t1、t2，有t1≤t2≤|T|。

輸出：找到T'?T，t1≤|T'|且填充后的S'∈S+T'，使得|ak(S',G)|最大。

該文給出一個(gè)k-Mer-SF實(shí)例，在此只舉例說(shuō)明了k=2和k=3的填充情況(如圖6所示)。

H. Jiang等人提出的2-近似算法和Q. Feng等人提出的2.57-近似算法均為k-Mer-SF中t1=t2=|T|且k=2時(shí)的特殊情況，并可在多項(xiàng)式時(shí)間O(3·(+m)2)內(nèi)計(jì)算。k-Mer-SF相較于以上兩個(gè)近似算法，不再僅僅參考公共鄰接數(shù)目的多少，主要使用以下評(píng)估參數(shù)：k，k-mers的長(zhǎng)度；：=ak(S*,G)-ak(S,G)，匹配后帶來(lái)的額外公共k-mers數(shù)目；d，一個(gè)基因在G中出現(xiàn)的最大次數(shù)；m，S中重疊群的個(gè)數(shù)；t2，要插入的字符串?dāng)?shù)量的上限；λ，T中字符串長(zhǎng)度的上界。

k-Mer算法主要解決了基于動(dòng)態(tài)規(guī)劃如何在2O()·nO()時(shí)間內(nèi)求得近似解并給出其參數(shù)為k+的FPT算法。首先使用著色法對(duì)k-mers進(jìn)行分類，β:T→[t2]表示潛在的公共k-mers，β:T→[t2]表示可能插入字符。圖著色后，使用動(dòng)態(tài)規(guī)劃算法重建序列S，使得S中有個(gè)潛在的公共k-mers轉(zhuǎn)為已實(shí)現(xiàn)的k-mers，在動(dòng)態(tài)規(guī)劃過(guò)程中逐步找到大小遞增的局部最優(yōu)解，從左到右依次將缺失基因插入到序列S中，并使用局部?jī)?yōu)化策略避免一些缺失基因重復(fù)插入。

對(duì)于k-Mer-SF問(wèn)題，首先對(duì)序列G，S及插入基因集合T做約簡(jiǎn)操作。刪除T中多余基因元素，如果T中存在一個(gè)基因元素出現(xiàn)次數(shù)大于t2，將刪除一個(gè)元素；其次，對(duì)G中的鄰接關(guān)系分類，并只保留潛在公共鄰接，假設(shè)x為不出現(xiàn)在S和T中的基因，y為不出現(xiàn)在G中的基因，令P1°x°P2°…°Pq-1°x°Pq替換G且用Ci[1]°y°Ci[|Ci|]表示S。如果有一個(gè)潛在鄰接在G中出現(xiàn)次，則在G中刪除一個(gè)該鄰接，刪除后若鄰接滿足以下條件之一，則稱為可實(shí)現(xiàn)鄰接：

(1)b∈T且c∈T；

(2)存在一個(gè)contigCi使得b∈Ci[|Ci|]且c∈T；

(3)存在一個(gè)contigCi使得b∈Ci[|Ci|]和c∈Ci[1]；

(4)存在一個(gè)contigCi使得b∈T且c∈Ci[1]。

建立鄰接圖H=(V,E)：令T，G和S中的基因元素作為H中的頂點(diǎn)，如果鄰接bc或鄰接cb均為可實(shí)現(xiàn)鄰接，則令兩個(gè)頂點(diǎn)b和c相鄰，求得最大匹配M。

令V(M)表示匹配的端點(diǎn)，建立兩個(gè)二分圖H1和H2且頂點(diǎn)分別為B:=V(M)和C:=(VV(M))。在H1中，當(dāng)bc是一個(gè)可實(shí)現(xiàn)鄰接時(shí)，在b∈B和c∈C之間添加一條邊。在H2中，當(dāng)cb是一個(gè)可實(shí)現(xiàn)鄰接時(shí)，在b∈B和c∈C之間添加一條邊。如果H1中存在頂點(diǎn)b∈B且度數(shù)至少為2+m+1，則將鄰接bc從G中移除；如果H2中存在頂點(diǎn)b∈B且度數(shù)至少為2+m+1，則將鄰接bc從G中移除，其中c是b的任意鄰接。

完成約簡(jiǎn)操作后，這些頂點(diǎn)的數(shù)量最多為|V(M)|·2·(2+m+1)。這給出了G中頂點(diǎn)數(shù)量的界限，從而給出了實(shí)例大小的界限且所有約簡(jiǎn)規(guī)則可以在多項(xiàng)式時(shí)間內(nèi)執(zhí)行。

從更廣泛的角度來(lái)看，k-Mer-SF考慮了字符串的基本插入問(wèn)題。事實(shí)上，可以將該算法擴(kuò)展到更一般的情況，即給定一個(gè)字符串G和一個(gè)部分字符串S，完成部分字符串S的插入得到新的字符串S'，使得G和S'的相似度最優(yōu)，因此其包含了H. Jiang等人的問(wèn)題作為特例。

3 One-Sided-SF-max問(wèn)題的總結(jié)

該文發(fā)現(xiàn)2-近似算法沒(méi)有考慮斷點(diǎn)對(duì)填充過(guò)程的影響和長(zhǎng)度大于1的缺失串的插入情況，2.57-近似算法則沒(méi)有考慮n-Type-3類型串的插入情況，k-Mer算法也僅僅介紹了固定基因子串長(zhǎng)度的一般處理情況，然而不同長(zhǎng)度以及不同類型串的插入都會(huì)對(duì)公共鄰接數(shù)造成影響，從而影響到算法近似比。

序列中存在連續(xù)長(zhǎng)缺失基因串，在完成1-Type-1類型串的插入后，假設(shè)存在可構(gòu)成n-Type-1類型串的缺失基因串a(chǎn)1a2…an，如若按照2-近似算法中分別處理，則該缺失基因串中1-Type-1類型串被破壞，有以下2種情況：

(1)最多有n個(gè)1-Type-2類型串，產(chǎn)生n個(gè)鄰接；

(2)最少有2個(gè)1-Type-2類型串，剩余為n-Type-3類型串，產(chǎn)生2個(gè)鄰接。

產(chǎn)生鄰接數(shù)k為2≤k≤n，若將其合并后插入基因序列中，則會(huì)產(chǎn)生n+1個(gè)鄰接。以上證明合并插入n-Type-1類型串具有更優(yōu)效果。

在處理n-Type-2類型串時(shí)，假設(shè)存在可構(gòu)成n-Type-2類型串的缺失基因串b1b2…bn，如若按照2-近似算法分別處理，則該缺失基因串中n-Type-2類型串被破壞，有以下2種情況：

(1)最多有2個(gè)1-Type-2類型串，同時(shí)bi(2≤i≤n-1)均可與其相鄰缺失基因bi-1或bi+1(2≤i≤n-1)構(gòu)成內(nèi)部鄰接，產(chǎn)生n個(gè)鄰接；

(2)最少有1個(gè)1-Type-2類型串，同時(shí)剩余n-1個(gè)缺失基因均為n-Type-3類型串，產(chǎn)生1個(gè)鄰接；產(chǎn)生鄰接數(shù)k為1≤k≤n，如若將其合并后插入基因序列中，會(huì)產(chǎn)生n個(gè)鄰接。以上證明合并插入n-Type-2類型串具有更優(yōu)效果。

對(duì)于2.57-近似算法，雖然n-Type-3類型串會(huì)產(chǎn)生n-1個(gè)鄰接，但是如果不對(duì)其進(jìn)行處理，任其插入未鎖定的slot，存在破壞已有鄰接的可能，其中最多會(huì)破壞2個(gè)鄰接，n-Type-3類型串產(chǎn)生鄰接數(shù)k為n-3≤k≤n-1，明顯降低最后的填充效率，所以對(duì)其進(jìn)行插入處理十分必要。

k-Mer算法固定了基因子串的長(zhǎng)度，2-近似算法就是一個(gè)特例，其固定長(zhǎng)度為2的公共鄰接數(shù)目作為算法性能參考依據(jù)，以上也證明了此時(shí)并不是最優(yōu)算法，進(jìn)而說(shuō)明了基因填充過(guò)程中限制基因子串長(zhǎng)度存在影響近似性能比的可能。

4 總結(jié)與展望

重點(diǎn)介紹了基于contig的單面重復(fù)基因組片段填充問(wèn)題的研究現(xiàn)狀。對(duì)該些算法在近似性能比等方面做出了詳細(xì)的對(duì)比(見表1)，直觀地看出各個(gè)算法現(xiàn)存在的一定不足，說(shuō)明此類算法仍有改進(jìn)空間，同時(shí)提出了該類問(wèn)題的改進(jìn)思路。

表1 三種算法分析比較

4.1 面臨的挑戰(zhàn)

(1)現(xiàn)有算法依賴于公共鄰接數(shù)目，鄰接的定義沒(méi)有考慮基因序列不存在逆序關(guān)系的情況，因此存在兩個(gè)基因序列的鄰接均為公共鄰接但二者完全不相似的情況，不利于后續(xù)對(duì)算法近似比的研究。

(2)現(xiàn)有算法對(duì)度量依據(jù)的選擇較少，并過(guò)度依賴于最大匹配算法，因此對(duì)此類問(wèn)題的研究較為片面。

4.2 前景展望

針對(duì)目前單面重復(fù)基因組片段填充問(wèn)題的研究工作，發(fā)現(xiàn)基因組填充問(wèn)題有以下發(fā)展前景。

(1)目前One-Sided-SF-max問(wèn)題的最佳性能近似比為2，日后還需要進(jìn)一步優(yōu)化。

(2)現(xiàn)有算法均是在最大化鄰接基礎(chǔ)上考慮其近似比，基于最小斷點(diǎn)數(shù)層面有待研究。

(3)雙面基因組填充問(wèn)題也被證為NP-完全的，但沒(méi)有提出近似比算法，此類算法可推廣到雙面基因組填充問(wèn)題，有利于雙面此問(wèn)題的近似比優(yōu)化。