PQ-樹斷點(diǎn)距離中心問題的復(fù)雜性和精確算法

劉培霞　姜海濤　朱大銘

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

(liupeixia0629@163.com)

?

PQ-樹斷點(diǎn)距離中心問題的復(fù)雜性和精確算法

劉培霞姜海濤朱大銘

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

(liupeixia0629@163.com)

Complexity and Algorithm for Minimum Breakpoint Median from PQ-trees

Liu Peixia, Jiang Haitao, and Zhu Daming

(ShoolofComputerScienceandTechnology,ShandongUniversity,Jinan250101)

AbstractA PQ-tree is a tree-based data structure which can represent large sets of permutations. Although the uncertainty of complete ancestral genomes is known, the homologous species provide information to determine the relative locations of partial genomes, whereby the PQ-tree can be designed to efficiently store ancestral genomes. In evolutionary biology, phylogenetic trees represent the evolutionary relationships between species. In the construction of phylogenetic trees, the leaves of the trees represent current species whose genomes are annotated by permutations, and the internal nodes represent ancestral genomes whose genomes are annotated by PO-trees. In order to determine the evolutionary relationships between different species, it is necessary to quantify the distances between the known permutations and the permutations in the constructed PQ-trees. Based on the measurement of breakpoint distance, we investigatep-Minimum Breakpoint Median from the PQ-tree. Given a PQ-tree and the correspondingppermutations, the goal is to identify a permutation generated by the PQ-tree that holds the minimum breakpoint distances relative to theppermutations. Our study shows that whenp≥2, thep-Minimum Breakpoint Median problem from PQ-tree is NP-complete. Moreover, whenp=1, the problem is fixed parameters tractable. To solve the 1-Minimum Breakpoint Median from PQ-trees, we propose a Fixed-Parameter Tractable algorithm whose computation complexity isO(3Kn) whereKis the optimized breakpoint distance.

Key wordsPQ-tree; breakpoint distance; fixed-parameter tractable; permutation; NP-complete

摘要PQ-樹是一種樹狀數(shù)據(jù)結(jié)構(gòu)，用來表示元素排列集合.雖然消逝物種完整基因組序列具有不確定性，但是根據(jù)同源物種可以確定部分基因的相對位置，所以可以利用PQ-樹來存儲(chǔ)消逝物種的基因組.在生物學(xué)中，進(jìn)化樹用來表示物種之間的進(jìn)化關(guān)系.當(dāng)構(gòu)建生物進(jìn)化樹時(shí)，葉子結(jié)點(diǎn)表示現(xiàn)存物種，其基因組用排列表示；內(nèi)部結(jié)點(diǎn)為祖先物種，其基因組用PQ-樹表示.為了確定物種間的進(jìn)化關(guān)系，需要確定PQ-樹可以產(chǎn)生的排列與已知排列之間的距離.以斷點(diǎn)距離為標(biāo)準(zhǔn)，研究了p-PQ-樹斷點(diǎn)中心問題，即從給定PQ-樹中產(chǎn)生一個(gè)排列，使之與給定的p個(gè)排列的斷點(diǎn)距離之和最小.證明當(dāng)p≥2時(shí)，p-PQ-樹斷點(diǎn)中心問題是NP-完全的.當(dāng)p=1時(shí)，p-PQ-樹斷點(diǎn)中心問題是參數(shù)化可計(jì)算的，針對1-PQ-樹斷點(diǎn)中心問題，提出了時(shí)間復(fù)雜度為O(3Kn)的參數(shù)化算法，其中K為最優(yōu)解的斷點(diǎn)距離.

關(guān)鍵詞PQ-樹；斷點(diǎn)距離；固定參數(shù)可解；排列；NP-完全

PQ-樹是由Kellogg和George[1]發(fā)現(xiàn)并命名的一種樹狀數(shù)據(jù)結(jié)構(gòu)，可以用來表示元素排列的集合.PQ-樹主要用來解決一些目標(biāo)是尋找滿足各種約束的排列的問題，在這些問題中，通過一次添加一種約束的方式編輯PQ-樹的結(jié)構(gòu)，使得編輯后的PQ-樹能表示滿足約束的排列.PQ-樹的主要應(yīng)用有：驗(yàn)證矩陣是否具有連續(xù)1性質(zhì)[1]、判定圖的平面性[2]等.PQ-樹是字符表Σ={1,2,…,n}上的一棵平面有根樹，它有3類結(jié)點(diǎn)：葉子結(jié)點(diǎn)、P結(jié)點(diǎn)和Q結(jié)點(diǎn)，每個(gè)葉子結(jié)點(diǎn)表示字符表中的一個(gè)元素，任意2個(gè)葉子結(jié)點(diǎn)表示的元素不同，非葉子結(jié)點(diǎn)被標(biāo)記為P結(jié)點(diǎn)或Q結(jié)點(diǎn).

由于利用現(xiàn)有技術(shù)構(gòu)建祖先基因組時(shí)，只能推測出祖先基因組的連續(xù)遺傳區(qū)，不能確定祖先基因組的全序列，如何構(gòu)建消逝物種的全基因組，已有大量的工作致力于此[3].文獻(xiàn)[3]基于多重?cái)帱c(diǎn)圖的概念，提出了算法MGRA，利用該算法重構(gòu)祖先基因組.文獻(xiàn)[4]提出了基于現(xiàn)代物種區(qū)間鄰接關(guān)系預(yù)測祖先物種區(qū)間順序的算法.

在本文中，利用PQ-樹來存儲(chǔ)祖先基因組[5].在生物學(xué)中，進(jìn)化樹用來表示物種之間的進(jìn)化關(guān)系.生物分類學(xué)家和進(jìn)化論者根據(jù)各類生物間的親緣關(guān)系的遠(yuǎn)近，把各類生物安置在有分枝的樹狀圖表上，簡明地表示生物的進(jìn)化歷程和親緣關(guān)系.當(dāng)構(gòu)建生物進(jìn)化樹時(shí)，葉子結(jié)點(diǎn)表示現(xiàn)存物種，其基因組用排列表示，內(nèi)部結(jié)點(diǎn)為祖先物種，其基因組用PQ-樹表示，祖先基因組跟現(xiàn)存物種基因組的組成元素相同[6].為了確定物種間的進(jìn)化關(guān)系，需要確定PQ-樹可以產(chǎn)生的排列與已知排列之間的距離.文獻(xiàn)[7]證明了2棵PQ-樹的最小斷點(diǎn)距離問題是NP-完全的,本文將證明一棵PQ-樹與已知排列的最小斷點(diǎn)距離問題也是NP-完全的.

本文中，以斷點(diǎn)距離為標(biāo)準(zhǔn)，研究了p排列PQ-樹斷點(diǎn)中心問題[8].p排列PQ-樹斷點(diǎn)中心問題描述如下：給定一棵PQ-樹T和p個(gè)排列s1,s2,…,sp，要求從T生成排列s，使得s與給定的p個(gè)排列s1,s2,…,sp的斷點(diǎn)距離之和最小.如果PQ-樹T可以生成所有可能的排列，則p排列PQ-樹斷點(diǎn)中心問題跟傳統(tǒng)的斷點(diǎn)中心問題就是等價(jià)的.現(xiàn)在已知3個(gè)排列的斷點(diǎn)中心問題是NP-完全的，從而，當(dāng)p≥3時(shí)，p排列PQ-樹斷點(diǎn)中心問題是NP-完全的(這是因?yàn)榭梢詷?gòu)造一棵只有1個(gè)P結(jié)點(diǎn)的PQ-樹，所有元素作為該樹的葉子結(jié)點(diǎn)，這樣的PQ-樹可以產(chǎn)生元素的任意排列[9]).

本文主要工作如下：

1) 對于p排列PQ-樹斷點(diǎn)中心問題，證明當(dāng)p≥2時(shí)，該問題是NP-完全的.

2) 針對1-PQ-樹斷點(diǎn)中心問題，提出時(shí)間復(fù)雜度為O(3Kn)的參數(shù)化算法.

1相關(guān)概念

1.1斷點(diǎn)距離

定義1. 鄰接.Σ表示包含n個(gè)字符的字符表，s是Σ上的所有元素構(gòu)成的排列，s中相鄰2個(gè)元素a和b構(gòu)成一個(gè)鄰接ab或ba.我們認(rèn)為鄰接ab與ba是等價(jià)的.

定義2. 公共鄰接與斷點(diǎn).給定2個(gè)排列s1與s2，如果ab或ba在s1與s2中都出現(xiàn)，則稱ab是公共鄰接;如果ab在s1中出現(xiàn)，但是ab和ba在s2中都不出現(xiàn)，則稱ab是s1的一個(gè)斷點(diǎn);如果ab在s2中出現(xiàn)，但是ab和ba在s1中都不出現(xiàn)，則稱ab是s2的一個(gè)斷點(diǎn).

定義3. 端點(diǎn)與公共端點(diǎn).排列2端的2個(gè)元素稱為端點(diǎn)，如果元素a既是排列s1的端點(diǎn)，又是排列s2的端點(diǎn)，則稱a是公共端點(diǎn).

定義4. 斷點(diǎn)距離.令a(s1,s2)表示排列s1與s2的公共鄰接的數(shù)目，t(s1,s2)表示排列s1與s2的公共端點(diǎn)的數(shù)目，則排列s1與s2的斷點(diǎn)距離定義為

(1)

在排列s1與s2的兩端分別加上元素0和n+1，可以得到規(guī)整后的斷點(diǎn)距離：

(2)

1.2PQ-樹

PQ-樹是字符表Σ={1,2,…,n}上的一棵平面有根樹.PQ-樹有3類結(jié)點(diǎn)：葉子結(jié)點(diǎn)、P結(jié)點(diǎn)、Q結(jié)點(diǎn).字符表中的每個(gè)元素用一個(gè)葉子結(jié)點(diǎn)來表示，任意2個(gè)葉子結(jié)點(diǎn)表示的元素不同.非葉子結(jié)點(diǎn)被標(biāo)記為P結(jié)點(diǎn)或Q結(jié)點(diǎn)，1個(gè)P結(jié)點(diǎn)至少有2個(gè)子結(jié)點(diǎn)，1個(gè)Q結(jié)點(diǎn)至少有3個(gè)子結(jié)點(diǎn).P結(jié)點(diǎn)的子結(jié)點(diǎn)的順序可以隨意排列，Q結(jié)點(diǎn)的子結(jié)點(diǎn)的順序只能是正序或者反序.PQ-樹只有2種可行操作，PQ-樹可以通過可行操作實(shí)現(xiàn)等價(jià)變換：

1) 隨意重排P結(jié)點(diǎn)的子結(jié)點(diǎn)順序.

2) 將Q結(jié)點(diǎn)的子結(jié)點(diǎn)順序翻轉(zhuǎn).

當(dāng)且僅當(dāng)存在一系列可行操作能將一棵PQ-樹轉(zhuǎn)化為另一棵PQ-樹，則稱這2棵PQ-樹是等價(jià)的.

按照前序關(guān)系得到的PQ-樹的葉子結(jié)點(diǎn)的排列稱為PQ-樹的標(biāo)簽，與某棵PQ-樹T等價(jià)的所有PQ-樹的標(biāo)簽稱為該P(yáng)Q-樹產(chǎn)生的排列的集合，記為P(T).

1.3問題定義

p排列PQ-樹斷點(diǎn)中心問題(p-minimum break-point median from PQ-trees,p-MBM-PQ).

實(shí)例：字符表Σ上的PQ-樹T和p個(gè)排列s1,s2,…,sp，|Σ|=n，正整數(shù)K.

22-MBM-PQ是NP-完全的

本節(jié)通過將三正則平面無橋連通圖上的哈密頓路徑問題規(guī)約到2-MBM-PQ，證明2-MBM-PQ問題是NP-完全的.已知三正則平面無橋連通圖上的哈密頓路徑問題是NP-完全的[10].

在文獻(xiàn)[6]中，證明了2棵PQ-樹的斷點(diǎn)距離問題是NP-完全的.由于一棵PQ-樹可以產(chǎn)生排列可能有若干個(gè)，因此，本文中研究的問題比文獻(xiàn)[6]中研究的問題要簡單的多，但本文中證明這個(gè)問題仍然是NP-完全的.

各頂點(diǎn)的度均相同的無向簡單圖稱為正則圖.各頂點(diǎn)度均為K的正則圖稱為K正則圖.對于圖G中的邊e，若刪除邊e使得圖G的連通分支數(shù)增加，則邊e是G的橋.

規(guī)約的中心思想如下：對應(yīng)于一個(gè)給定的三正則平面無橋連通圖C，構(gòu)造2-MBM-PQ問題的PQ-樹T及2個(gè)排列s1，s2，其中PQ-樹T的葉子結(jié)點(diǎn)對應(yīng)于圖C的所有頂點(diǎn)，2個(gè)排列s1與s2對應(yīng)于圖C的所有邊.因此圖C中有哈密頓路徑當(dāng)且僅當(dāng)可以從PQ-樹T生成排列s，使得s與s1，s2的公共鄰接數(shù)之和為n-1(其中每個(gè)鄰接對應(yīng)于圖C中的一條邊).

給定一個(gè)三正則平面無橋連通圖C=(C(V),C(E))，首先構(gòu)造2-MBM-PQ問題的PQ-樹T：T有2層，根結(jié)點(diǎn)是P結(jié)點(diǎn)，它有2個(gè)子結(jié)點(diǎn)：一個(gè)是P結(jié)點(diǎn)，存儲(chǔ)C(V)的所有頂點(diǎn)；一個(gè)是Q結(jié)點(diǎn)，存儲(chǔ)填充元素(填充元素是為了間隔非鄰接頂點(diǎn)而添加的不同于圖C中頂點(diǎn)的元素).

然后，構(gòu)造2個(gè)排列s1與s2，s1，s2包含C(V)中的所有頂點(diǎn)以及填充元素，對于圖C中的每對頂點(diǎn)vivj，如果(vi,vj)∈C(E),那么vivj或vjvi是s1或s2中的一個(gè)鄰接，但不是s1與s2的公共鄰接，如果(vi,vj)?C(E)，則用其他頂點(diǎn)或者填充元素將vi與vj間隔開，使其在s1與s2中不能構(gòu)成鄰接.

引理1[11]. 任何三正則平面無橋連通圖都有完美匹配，其完美匹配可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算得到.

下面，將描述構(gòu)造排列s1，s2的具體步驟，該構(gòu)造過程可以在多項(xiàng)式時(shí)間內(nèi)完成.

步驟1. 計(jì)算三正則平面無橋連通圖C=(C(V),C(E))的完美匹配M，從圖C中刪除M中的邊，得到圖C′=(C(V),C(E)-M)，則C′是由不相交的環(huán)路構(gòu)成.

步驟2. 從任意頂點(diǎn)vi(vi∈C′(V))開始，遍歷C′中vi所在環(huán)路上的所有頂點(diǎn)，得到一條路徑P=vi,…,vj，對于頂點(diǎn)vk(其中(vj,vk)∈M)，如果vk已被某條路徑遍歷過，則重新選擇一個(gè)頂點(diǎn)作為開始頂點(diǎn)，繼續(xù)遍歷C′中的環(huán)路；否則，如果vk還沒被任何路徑遍歷過，那么將路徑P通過邊(vj,vk)擴(kuò)展到其他環(huán)路.循環(huán)迭代這個(gè)過程直到所有的環(huán)路都被遍歷.最后，利用M中的邊連接得到的這些路徑，直到?jīng)]有兩條路徑可以被連接，從而構(gòu)成最長的沒有環(huán)路的路徑，并把最終得到的路徑集合放入s1中,將得到的路徑集合記為P′.

步驟3. 將C中剩余的沒被遍歷的所有路徑(不包含在路徑集合P′中)放入s2.

引理2.C(V)中的每個(gè)頂點(diǎn)在s1中恰好出現(xiàn)1次.

證明. 由于圖C是一個(gè)三正則平面無橋連通圖，M是圖C的完美匹配，那么C′=(C(V),C(E)-M)是由不相交的環(huán)路構(gòu)成.步驟2中，遍歷圖C′中所有環(huán)路得到的路徑集合放入s1中，其中，每個(gè)環(huán)路遍歷且只遍歷1次，所以，C(V)中所有頂點(diǎn)在s1中恰好出現(xiàn)1次.

證畢.

從圖C中刪除路徑集合P′中的邊，得到圖C″.

引理3. 圖C″中沒有環(huán).

證明. 對于圖C″，可以證明結(jié)論：圖C″中每個(gè)度為2的頂點(diǎn)都有1個(gè)度為1的鄰居頂點(diǎn)，若該結(jié)論成立，則圖C″中沒有環(huán).

注意到C″中每個(gè)度為2的頂點(diǎn)必定是P′中某條路徑的端點(diǎn).假設(shè)：1個(gè)度為2的頂點(diǎn)vr連接到2個(gè)度為2的頂點(diǎn)vs，vt，則vs，vt中至少有1個(gè)頂點(diǎn)跟vr不在同一條路徑上，而根據(jù)上述構(gòu)造排列s1與s2的過程，這樣的2條路徑在步驟2中應(yīng)該被連接起來，這與每個(gè)度為2的頂點(diǎn)必定是P′中某條路徑的端點(diǎn)相矛盾，所以圖C″中每個(gè)度為2的頂點(diǎn)都有1個(gè)度為1的鄰居頂點(diǎn)，所以圖C″中沒有環(huán).

證畢.

引理4.C(V)中的每個(gè)頂點(diǎn)在s2中恰好出現(xiàn)1次.

證明. 由于C(V)中的每個(gè)頂點(diǎn)在s1中恰好出現(xiàn)1次(引理2)，所以C″中的頂點(diǎn)度數(shù)為1或2.又由于C″中沒有環(huán)(引理3)，所以放入s2中的都是不相交的路徑，所以C(V)中的每個(gè)頂點(diǎn)在s2中恰好出現(xiàn)1次.

證畢.

引理5. 如果邊(vi,vj)∈C(E)，則在s1或s2中，存在鄰接vivj或vjvi，但vivj或vjvi不是s1與s2的公共鄰接.

證明. 根據(jù)s1，s2的構(gòu)造過程，對于圖C中的每條邊(vi,vj)，存在且只存在2種情況中的1種：

1) (vi,vj)或(vj,vi)在步驟2中被放入s1中，則在s1中存在鄰接vivj或vjvi.

2) (vi,vj)或(vj,vi)在步驟3中被放入s2中，則在s2中存在鄰接vivj或vjvi.

(vi,vj)或(vj,vi)或者在步驟2中被放入s1中，或者在步驟3中被放入s2中，但不會(huì)同時(shí)放入s1與s2中，所以鄰接vivj或vjvi只能在s1或s2中存在，但不是s1與s2的公共鄰接，所以該引理成立.

證畢.

引理6. 如果邊(vi,vj)?C(E)，則在s1和s2中，不存在鄰接vivj或vjvi.

證明. 根據(jù)s1，s2的構(gòu)造過程，放入s1，s2中的只能是圖C中的邊，所以如果(vi,vj)?C(E)，則在s1，s2中不存在鄰接vivj或vjvi，所以該引理成立.

證畢.

下面，我們完成三正則平面無橋連通圖上的哈密頓路徑問題到2-MBM-PQ問題的規(guī)約，證明2-MBM-PQ問題是NP-完全的：

1) 利用不同的填充元素將s1以及s2中的路徑分別間隔開.

2) 構(gòu)建4個(gè)子排列x1x2x3x4，x2x4x1x3，x5x6x7x8，x6x8x5x7，分別把x1x2x3x4與x5x6x7x8放在排列s1與s2的兩端；把x2x4x1x3放在PQ-樹T的子Q結(jié)點(diǎn)的最左邊，把x6x8x5x7放在PQ-樹T的子Q結(jié)點(diǎn)的最右邊.

3) 把s2中的所有填充元素放在s1中的x1的左邊，把s1中的所有填充元素放在s2中x8的右邊；把所有既在s1中又在s2中的填充元素放在PQ-樹T的子Q結(jié)點(diǎn)的x2x4x1x3與x6x8x5x7之間，并且保證在s1或s2中鄰接的兩個(gè)填充元素在Q結(jié)點(diǎn)中不能相鄰.

引理7. 三正則平面無橋連通圖C存在一條哈密頓路徑,當(dāng)且僅當(dāng)PQ-樹T可以生成排列s，使得s與s1的公共鄰接數(shù)加上s與s2的公共鄰接數(shù)之和為n-1.

證明. 顯然，沒有公共鄰接涉及填充元素.

充分性.如果三正則平面無橋連通圖C有一條哈密頓路徑，PQ-樹可以產(chǎn)生一個(gè)排列s，排列s中的元素順序與哈密頓路徑中頂點(diǎn)的順序一致，那么排列s中每一個(gè)鄰接對應(yīng)圖C的哈密頓路徑中的一條邊.由于圖C中的每條邊被放入且只放入排列s1或s2中的1個(gè)，所以排列s與s1，s2的公共鄰接數(shù)之和為n-1.

必要性.如果T可以生成排列s使得s與s1的公共鄰接數(shù)加上s與s2的公共鄰接數(shù)之和為n-1，由于T最多可以生成n-1個(gè)公共鄰接，每個(gè)鄰接對應(yīng)于C中的一條邊，所以，所有的這些邊構(gòu)成一條哈密頓路徑.

證畢.

現(xiàn)在舉例說明這個(gè)規(guī)約.給定一個(gè)三正則平面無橋連通圖C，如圖1(a)所示，圖C的完美匹配如圖1(b)所示：

Fig. 1　A cubic plannar bridgeless graph and its perfect matching.圖1　三正則平面無橋連通圖及其完美匹配

根據(jù)排列s1，s2的構(gòu)造過程：從頂點(diǎn)v1開始，遍歷環(huán)路v1v2v3v4v1上所有頂點(diǎn)，得到路徑P=v1v2v3v4，對于頂點(diǎn)u4，由于(v4,u4)∈M且u4還沒被遍歷過，將路徑P通過邊(v4,u4)擴(kuò)展到環(huán)路u4u1u2u3u4，得到P′=v1v2v3v4u4u1u2u3，將路徑P′放入s1，將剩余的沒被遍歷的路徑集合{v4v1v3,v2u2,u4u3u1}放入s2，添加填充元素#、$將s2中的路徑間隔開，在s1，s2中添加子排列x1x2x3x4，x5x6x7x8，在s1中添加填充元素#，$，最終得到：

s1=#$x1x2x3x4v1v2v3v4u4u1u2u3x5x6x7x8,

s2=x1x2x3x4v4v1v3#v2u2$u4u3u1x5x6x7x8.

字符#，$是填充元素.PQ-樹T的根結(jié)點(diǎn)是P結(jié)點(diǎn)，根結(jié)點(diǎn)有2個(gè)子結(jié)點(diǎn)，1個(gè)是P結(jié)點(diǎn)，1個(gè)是Q結(jié)點(diǎn).P結(jié)點(diǎn)的葉子結(jié)點(diǎn)為：{v1,v2,v3,v4,u1,u2,u3,u4}，Q結(jié)點(diǎn)的葉子結(jié)點(diǎn)為：x2,x4,x1,#,x3,$,x6,x8,x5,x7.

重排P結(jié)點(diǎn)的葉子結(jié)點(diǎn)可以得到一個(gè)序列：[v1,v2,v3,v4,u4,u1,u2,u3].該序列對應(yīng)C中的一條哈密頓路徑，在得到的序列基礎(chǔ)上添加填充元素#，$，可以得到一個(gè)排列s，使得s與s1，s2的公共鄰接數(shù)之和為7.

引理8. 2-MBM-PQ問題是NP-完全的.

證明. 顯然，2-MBM-PQ是NP的.根據(jù)引理5，可以看到本文的規(guī)約可以在多項(xiàng)式時(shí)間內(nèi)完成，所以2-MBM-PQ是NP-完全的.

證畢.

由于p≥3時(shí)，p排列PQ-樹斷點(diǎn)中心問題是NP-完全的，綜合引理6，可以得出如下結(jié)論：

推論1. 當(dāng)p≥2時(shí)，p-MBM-PQ問題是NP-完全的.

31-MBM-PQ問題的參數(shù)化算法

本節(jié)提出一個(gè)參數(shù)化算法解決1-MBM-PQ問題，該算法的參數(shù)是問題最優(yōu)解的斷點(diǎn)距離.

判定問題Π、參數(shù)p、存在算法可以在O(f(p)nc)時(shí)間內(nèi)解決該問題，其中f是只與p有關(guān)的函數(shù)，n是問題輸入規(guī)模，c是與p無關(guān)的常數(shù)[12].這樣的問題稱為參數(shù)化問題，可以在O(f(p)nc)時(shí)間內(nèi)解決該問題的算法稱為參數(shù)化算法.

3.1PQ-樹的圖表示

首先介紹怎樣圖形化表示PQ-樹.給定1-MBM-PQ問題的PQ-樹T與排列s1，PQ-樹T的每個(gè)結(jié)點(diǎn)對應(yīng)圖G的一個(gè)頂點(diǎn).對應(yīng)于葉子結(jié)點(diǎn)的頂點(diǎn)稱為元素，對應(yīng)于P結(jié)點(diǎn)的頂點(diǎn)稱為超P頂點(diǎn)，對應(yīng)于Q結(jié)點(diǎn)的頂點(diǎn)稱為超Q頂點(diǎn).2個(gè)頂點(diǎn)之間存在邊，當(dāng)且僅當(dāng)它們是某個(gè)Q結(jié)點(diǎn)的相鄰子結(jié)點(diǎn).圖G的邊稱為黑邊.

根據(jù)T的層次關(guān)系，在圖G中增加頂點(diǎn)嵌入信息.如果PQ-樹中一個(gè)結(jié)點(diǎn)X是另一個(gè)結(jié)點(diǎn)Y的子結(jié)點(diǎn)，則在圖G中，X對應(yīng)的頂點(diǎn)嵌入到Y(jié)對應(yīng)的頂點(diǎn)中，如圖2所示.因此，當(dāng)且僅當(dāng)X是Z的子孫結(jié)點(diǎn)時(shí)，X對應(yīng)的頂點(diǎn)嵌入到Z對應(yīng)的頂點(diǎn)中.

將排列s1的信息增加到圖G中.對于s1中每個(gè)鄰接xy，如果圖G中不存在黑邊(x,y)，則在圖G中增加一條藍(lán)邊(x,y)，令得到的新的圖為G′，如圖3所示.圖G′中超頂點(diǎn)X的度定義為：連接X內(nèi)頂點(diǎn)與X外頂點(diǎn)的藍(lán)邊的數(shù)目.

可以看到1-MBM-PQ問題跟最小路徑覆蓋問題關(guān)系密切.最小路徑覆蓋問題描述如下：給定一個(gè)圖，尋找數(shù)目最少的路徑，使之覆蓋圖的所有頂點(diǎn)，并且任何一個(gè)頂點(diǎn)有且只有一條路徑與之關(guān)聯(lián)[14].

Fig. 2　A PQ-tree and its graphical representation.圖2　PQ-樹及其圖表示

3.21-MBM-PQ問題的參數(shù)化算法

通過下面的引理來描述如何求解問題的最優(yōu)解.

引理9. 通過對圖G′完成以下操作，可以得到1-MBM-PQ問題的最優(yōu)解：

1) 如果元素x是Q結(jié)點(diǎn)Y的中間的子結(jié)點(diǎn)(其中Y的所有子結(jié)點(diǎn)都是葉子結(jié)點(diǎn))，則刪除所有與x關(guān)聯(lián)的藍(lán)邊.

2) 如果元素x的度數(shù)超過2，則至多保留2條與x關(guān)聯(lián)的藍(lán)邊，其余藍(lán)邊都刪除.

3) 如果超頂點(diǎn)X的度數(shù)超過2，則至多保留2條與X內(nèi)元素相關(guān)聯(lián)的藍(lán)邊，其余藍(lán)邊都刪除.

證明. 這里只討論第3種情況.如果X度數(shù)超過2，為了將X嵌入某條路徑，則必須刪除與X相關(guān)聯(lián)的多余邊.如果連接到X內(nèi)元素的藍(lán)邊超過2條，則不可能將X嵌入某條路徑.

證畢.

在執(zhí)行了引理9的步驟1操作之后，令r表示圖G′中超頂點(diǎn)的最大度數(shù)，如果r≤2，則問題是平凡的，所以假定r≥3.該FPT算法利用有限搜索樹的原理，處理度數(shù)超過2的超頂點(diǎn).令K表示1-MBM-PQ問題的最優(yōu)解的斷點(diǎn)距離，f(K)表示搜索樹的葉子結(jié)點(diǎn)數(shù)目，可以得到如下遞推關(guān)系：

(3)

主要遞推關(guān)系式可以化簡為

(4)

利用生成函數(shù)求解遞推關(guān)系的方法，對式(4)進(jìn)一步化簡得到：

(5)

可以看到，當(dāng)r=3時(shí)，取得最大值，則：

(6)

因此f(K)≤3K.

算法描述如下：

算法1.One-MBP-PQ(T，s1).

輸入：PQ-樹T、排列s1、整數(shù)K；

輸出：由T生成的排列s，s與s1之間的斷點(diǎn)距離不超過K.

步驟1. 根據(jù)T，計(jì)算得到圖G；

步驟2. 根據(jù)T的層次關(guān)系，在圖G中增加嵌入信息；

步驟3. 對應(yīng)于s1中的所有鄰接，在圖G中添加藍(lán)邊，得到圖G′；

步驟4. 令U表示從G′中刪除的藍(lán)邊的集合；

步驟5. while |U|≤K

步驟5.1. 如果元素x是Q結(jié)點(diǎn)Y的中間的子結(jié)點(diǎn)(其中Y的所有子結(jié)點(diǎn)都是葉子結(jié)點(diǎn))，則刪除所有與x關(guān)聯(lián)的藍(lán)邊，并把刪除的藍(lán)邊放入U(xiǎn)；

步驟5.2. 如果元素x的度數(shù)超過2，保留2條與x關(guān)聯(lián)的藍(lán)邊，刪除其余藍(lán)邊，并把刪除的藍(lán)邊放入U(xiǎn)；

步驟5.3. 如果超頂點(diǎn)X的度數(shù)超過2，保留2條與X內(nèi)元素關(guān)聯(lián)的藍(lán)邊，刪除其余藍(lán)邊，并把刪除的藍(lán)邊放入U(xiǎn)；

步驟6. 如果最終得到的圖由路徑組成，則返回排列s，否則，返回“無解”.

當(dāng)從圖G′中刪除K條藍(lán)邊后，要做的就剩下驗(yàn)證所得的圖是否由路徑組成，如果在刪除K條藍(lán)邊后，所有頂點(diǎn)度數(shù)都不超過2，那么驗(yàn)證所得的圖是否由路徑組成，就可以轉(zhuǎn)化為驗(yàn)證圖中是否有環(huán)路存在.在刪除K條藍(lán)邊后，如果沒有找到可行解，則返回“無解”.這可以在O(n)的時(shí)間內(nèi)完成.因此，一旦計(jì)算得到G′，可以利用有限搜索樹[15]原理實(shí)現(xiàn)一個(gè)時(shí)間復(fù)雜度為O(3kn)的算法.

在圖3中，針對上述算法舉一個(gè)簡單的例子.圖3(a)中，給定PQ-樹T，給定排列s1=“0123456789”，圖3(b)中，圖G′是計(jì)算所得(圖中虛線邊代表算法中添加的藍(lán)邊).該實(shí)例最優(yōu)解的斷點(diǎn)距離K=1.根據(jù)上述算法，需要在圖G′中刪除一條藍(lán)邊，例如，對于超頂點(diǎn)“105”，其度數(shù)為3，所以至少刪除(2,1)(5,6)(4,5)的一條邊，為了使最終得到的圖由路徑組成，刪除藍(lán)邊(4,5)，此時(shí)可以得到最優(yōu)解排列s=“4321056789”，且s與s1之間恰好有一個(gè)斷點(diǎn).

Fig. 3　An example for the FPT algorithm.圖3　參數(shù)化算法示例

根據(jù)上述算法，可以得到結(jié)論：1-MBM-PQ問題存在時(shí)間復(fù)雜度為O(3kn)的算法，其中n是元素個(gè)數(shù)，K是最優(yōu)解的斷點(diǎn)距離.

4結(jié)束語

本文主要分析討論了p-PQ-樹斷點(diǎn)中心問題，在介紹了PQ-樹、斷點(diǎn)距離等相關(guān)概念后，證明了當(dāng)p≥2時(shí)，p-PQ-樹斷點(diǎn)中心問題是NP-完全的，然后針對1-PQ-樹斷點(diǎn)中心問題，提出了時(shí)間復(fù)雜度為O(3kn)的參數(shù)化算法.

目前，1-MBM-PQ問題的復(fù)雜性還是未知，設(shè)計(jì)PQ-樹斷點(diǎn)距離問題的有效算法也值得繼續(xù)研究.

參考文獻(xiàn)

[1]Booth K S, Lueker G S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms[J]. Journal of Computer and System Sciences, 1976, 13(3): 335-379

[2]Ou Liancheng. Testing for graph planarity using PQ-tree algorithms[J]. Computer Engineering and Science, 1990, 12(2): 44-50 (in Chinese)(歐連成. 用 PQ-樹算法判定圖的平面性[J]. 計(jì)算機(jī)工程與科學(xué), 1990, 12(2): 44-50)

[3]Alekseyev M A, Pevzner P A. Breakpoint graphs and ancestral genome reconstructions[J]. Genome Research, 2009, 19(5): 943-957

[4]Ma J, Zhang L, Suh B B, et al. Reconstructing contiguous regions of an ancestral genome[J]. Genome Research, 2006, 16(12): 1557-1565

[5]Rascol V L, Pontarotti P, Levasseur A. Ancestral animal genomes reconstruction[J]. Current Opinion in Immunology, 2007, 19(5): 542-546

[6]Chauve C, Tannier E. A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes[J]. PLoS Computational Biology, 2008, 4(11): e1000234

[7]Jiang H, Chauve C, Zhu B. Breakpoint distance and PQ-trees[C]Proc of the 21st Annual Symp on Combinatorial Pattern Matching. Berlin: Springer, 2010: 112-124

[8]Watterson G A, Ewens W J, Hall T E, et al. The chromosome inversion problem[J]. Journal of Theoretical Biology, 1982, 99(1): 1-7

[9]Sankoff D, Blanchette M. Multiple genome rearrangement and breakpoint phylogeny[J]. Journal of Computational Biology, 1998, 5(3): 555-570

中圖法分類號(hào)TP301.6

通信作者：姜海濤(htjiang@sdu.edu.cn)

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61202014，61472222)；山東省自然科學(xué)基金項(xiàng)目(ZR2012FQ008)；中國博士后科學(xué)基金項(xiàng)目(2011M5001133，2012T50614)

收稿日期：2014-11-17；修回日期：2015-01-27

This work was supported by the National Natural Science Foundation of China (61202014，61472222), the Natural Science Foundation of Shandong Province of China (ZR2012FQ008), and the China Postdoctoral Science Foundation (2011M5001133，2012T50614).