應用屬性約簡構建含有缺失數據的譜系樹

朱 銳，馮宏偉，馮 筠，王惠亞，劉建妮，韓 健

1.西北大學 信息科學與技術學院，西安 710127

2.西北大學 數學學院，西安 710127

3.西北大學 地質學系，西安 710069

1 引言

隨著生物信息學的發展，譜系樹的構建已成為生物信息學重要的組成部分。通過對譜系演化樹的研究，可以推測生物進化模型，進行生物差異性研究。目前國內外常用的運用形態學數據構建譜系樹的方法有鄰接法[1]、最大簡約法與貝葉斯法[2]，其中最大簡約法是生物進化研究中重要的分析方法，對于處理復雜的生物演化過程有著重要的意義[3]。

最大簡約法（Maximum parsimony）是基于奧卡姆剃刀原則（Occam’srazor）發展起來的一種譜系樹重構方法，基本思想是認為物種之間真實的進化關系應該演化步驟最少[4]。最大簡約法首先由Camin&Sokal提出[5]，在Hein的研究推廣下得到了極大地發展和應用[6-7]。然而，隨著生物屬性數量的增加，譜系樹可能的拓撲結構呈現爆炸式的增長，啟發式尋優應運而生[1]。然而簡約法啟發式搜索可能會產生多棵簡約樹，此時通常選取一棵能概括這些簡約樹的一致樹作為代表[8]，將最大簡約法提升到了新的高度。

但是，隨著生物屬性缺失數據比例的增加，最大簡約法中的啟發式查找的范圍不斷擴大，造成譜系樹的結構極其不穩定。最大簡約法在構建含有缺失數據的譜系樹時會出現兩個問題：（1）物種中的缺失數據的出現會導致其在譜系樹中位置的準確率大大降低；（2）缺失數據物種中的缺失值對譜系樹中其他物種的種間關系產生影響[9]。并且生物形態學數據集一般為小樣本數據，由于數據量少而無法進行回歸分析，對缺失數據的預測填補不具有統計正確性，阻礙著生物類群譜系樹構建的研究和發展[10]。

譜系樹是一種樹狀結構的層次化分類模型，在譜系樹中出現分支時可以把生物物種對應地分類成若干個集合。屬性約簡是處理分類模型重要的分析方法[11]，同時也是一種處理缺失數據的常用方法。屬性約簡是在保證分類能力不變的情況下，刪除其中不相關或不重要的屬性，大大提高系統潛在知識的清晰度[12]。從而用最簡約的屬性保障分類能力，進而在出現缺失數據時保持分類的穩定性。

本文針對含有缺失形態學數據難以建立有效譜系樹的問題，提出應用屬性約簡構建含有缺失數據譜系樹的方法。首先，利用相對完整的物種數據運用最大簡約法構建出一棵初始譜系樹；其次，對初始譜系樹構造層次化分類節點，運用屬性約簡獲得屬性決策組集合，進而建立基于初始譜系樹的先驗決策模型；接著，將有缺失信息的物種嫁接到初始譜系樹中，完成譜系樹的構建。本方法主要特色為：一方面利用了初始譜系樹的先驗信息，提高了含有缺失數據的物種在譜系樹中的準確率；另一方面，避免了缺失數據物種對完整數據構建譜系樹的穩定性影響。

2 應用屬性約簡構建含有缺失數據的譜系樹

為了完成含有大量缺失信息的譜系樹構建，基本思路是：首先，將數據集劃分為兩個部分，一部分為缺失比例較低的物種集，作為初始物種集，運用最大簡約法構建可信度較高的初始譜系樹。另一部分為缺失比例較高的物種，做為待嫁接的物種，接入譜系樹中，最終完成整體譜系樹的構建。

2.1 初始譜系樹的構建以及節點的建立

首先，本文提出在生物形態學數據集中，將不含缺失數據或者含有少量缺失數據的物種提出來合并成一個數據集，運用最大簡約法構建可信度較高的初始譜系樹，或根據研究者自己已有的先驗知識構建初始譜系樹。

其次，對初始譜系樹中出現分支的地方建立節點。如圖1中的N1～N4。初始譜系樹的末端為參與構建譜系樹的物種，如圖1中的A～E。每個節點處都有著從屬于當前節點的物種集合，并且把從屬物種分為幾類。

圖1 初始譜系樹分支節點的建立

在圖1中，圓表示節點，方框表示物種。根據圖中的4個分支分別建立分支節點，標號依次為N1、N2、N3、N4，每個分支節點都有著從屬于該節點的物種。在N1節點處，從屬物種為A、B、C、D、E，由節點處的分支可把從屬物種分為兩類，A為一類，B、C、D、E為一類。而N2節點下的從屬物種為B、C、D、E，則把從屬物種分為B、C以及D、E兩類。在N3和N4節點處從屬物種分別為B、C和D、E。兩個節點亦被分為兩類，N3節點為B一類以及C一類，N4節點為D一類和E一類。

2.2 應用屬性約簡構建先驗決策模型

利用構建好的初始譜系樹，確定分支節點后，將當前節點的從屬物種分類標簽和從屬物種屬性作為一個決策表。決策表是一類特殊而重要的知識表達系統，有著重要的作用[13]。對決策表進行屬性約簡進而產生屬性決策組，多次建立屬性決策組完成決策點的建立。通過對譜系樹中的每個節點對應決策點的建立，最終建立先驗決策模型。基本流程如圖2所示。

2.2.1 節點對應決策點的建立

圖2 基于初始譜系樹的先驗決策模型構建流程

將節點從屬物種屬性集合與分類標簽看作決策表，進行一次屬性約簡，并沒有充分地利用先驗信息。并且單一屬性決策組很容易因缺失數據的出現使得當前決策失效。因此多次進行屬性約簡操作并得到屬性決策組集合，以此作為當前決策點的決策判斷依據。

算法說明：C={ai,i=1,2,…,m}稱為節點從屬物種形態學屬性集，D={di,i=1,2,…,n}稱為節點從屬物種類標簽屬性集。對整個條件屬性集進行約簡，利用正區域的啟發式信息逐步將該集合中不必要的屬性約去，但仍滿足當前決策點的分類，得到的屬性約簡組，即屬性決策組Reduct1，剔除原來屬性集合中參與建立屬性決策組的屬性，對剩余的條件屬性集繼續進行屬性約簡并得到相應的Reducti，直到條件屬性集不能再構建屬性決策組為止。具體的算法描述如下：

輸入：節點從屬物種信息系統決策表。

輸出：屬性決策組集合reducti(i=1,2,…,n)。

步驟1計算決策點從屬物種分類屬性D對于從屬物種屬性C的正區域POSc(D)。

步驟2對每個當前節點從屬物種屬性ai計算pos=POSC(D)-POS(c-{ai})(D)。

步驟3令Reduct=C；將屬性ai按 pos從小到大的順序排列，對每個屬性執行操作；若POS(Reduct-{ai})(D)=POSC(D)，則屬性 ai應約簡，Reduct=Reduct-{ai}；否則ai不能被約簡，Reduct不變。

步驟4得到屬性決策組Reducti，對參與建立屬性決策組的屬性進行剔除，即residue=C-Reducti。

步驟5把剩余條件屬性集residue賦予C，即C=residue。

步驟6執行步驟1，建立決策點的多屬性組reducti(i=1,2,…,n)直到C條件屬性集無法構建屬性決策組為止。

通過對節點從屬物種決策表進行多次屬性約簡，進而構建屬性決策組集合，得到與節點對應的決策點，最終構建出決策點模型，如圖3所示，reduct1到reductn為決策點中的屬性決策組集合。

圖3 決策點模型

2.2.2 基于決策點的先驗決策模型構建

對初始譜系樹中的每個節點建立對應決策點，進而獲得初始譜系樹的決策先驗模型，模型的樹狀拓撲結構與初始譜系樹的結構一致，如圖4所示，圖中的圓表示決策點，方框表示物種。

圖4 初始譜系樹先驗決策模型

圖2中初始譜系樹共有4個節點，對應建立的決策點為圖4中的P1、P2、P3、P4。決策模型結構的末端為物種，與圖2中物種對應，為A、B、C、D、E。

2.3 基于先驗決策模型的含有缺失數據譜系樹構建

先驗決策模型的構建利用了初始譜系樹中物種間進化關系的先驗信息，將初始譜系樹轉換為了一個層次化結構的分類器。將含有較多缺失數據的嫁接物種帶入到先驗決策模型分類器中，自根決策點出發，逐層地進行決策點嫁接物種歸屬的判斷。由于缺失數據的出現，在判斷的過程中會使當前決策點的某些決策屬性組判斷失效，則判定其無法判斷物種歸屬，進而依據其他的完整數據進行決策屬性組物種歸屬判斷。

這里設屬于A樹的屬性組數為m，屬于B樹的屬性組數為n。

步驟1初始狀態令m=0，n=0。

步驟2通過對嫁接物種在決策點中的每個屬性組的屬性比對，如在對應子樹出現相同屬性組，則判定屬于A樹或者屬于B樹，并對歸屬屬性組數進行累加。

步驟3如果既不屬于A樹也不屬于B樹，或者因缺失數據而導致無法判斷歸屬，則m、n不進行累加。

步驟4完成每個屬性組的歸屬判斷后，最終得出嫁接物種子樹歸屬的屬性組數m、n。則嫁接物種決策點歸屬判斷策略為：

按照上述決策點判斷策略，嫁接物種從先驗決策模型的根決策點開始判斷歸屬，認定歸屬于A子樹或者B子樹后，針對歸屬子樹的根決策點繼續進行歸屬判斷。反復執行此操作直到停止判斷。

嫁接物種停止判斷后，該物種在先驗決策模型中的判斷歷程結束，進行嫁接物種嫁接過程。將嫁接物種嫁接在最終到達的決策點對應的初始譜系樹節點中。嫁接物種嫁接子樹過程如圖5所示，在P決策點停止判斷歸屬歷程，并嫁接在P決策點對應的初始譜系樹中的節點N上，成為初始譜系樹的新分支。

圖5 初始譜系樹節點建立分支示意圖

3 實驗結果和分析

本文采取的實驗環境：Windows 7，8 GB內存，編程語言是MATLAB。為了驗證本文方法的有效性，實驗運用不含缺失數據或者含有少量缺失數據的具有明確譜系的生物形態學數據集作為實驗數據集，對其中的物種進行隨機數據缺失處理，運用本論文提出的方法與最大簡約法譜系樹進行實驗對比得出結論。

3.1 實驗數據集

實驗對象選取了利用形態學構建譜系樹的已發表論文中的三個數據集[14-16]，數據集中的形態學編碼：0為原始性狀，1為進化性狀。有些性狀為多態性狀，則連續的編碼為2、3。多態性狀均為無序性狀，在無序性狀中任何兩個狀態的性狀距離是相等的，例如0～1和0～2之間的進化距離都為1，為缺失性狀，即不明性狀。

3.2 單個物種嫁接實驗及對比分析

以Palaearctic parasite species of Testudinidae數據集為例來說明實驗過程。首先構建用來評價的標準譜系樹，結果如圖6所示。

圖6 《Palaearctic parasite species of Testudinidae》標準譜系樹

對物種T.marocana的形態學數據進行隨機缺失處理，數據缺失率為30%，運用本論文提出的方法構建譜系樹如圖7所示。嫁接點為實心圓處。

圖7 《Palaearctic parasite species of Testudinidae》本文方法構建的譜系樹

本方法的對比實驗是將含有缺失比例為30%的物種T.marocana與其他24個物種運用最大簡約法構建譜系樹。構建的譜系樹如圖8所示。

圖8 《Palaearctic parasite species of Testudinidae》最大簡約法構建的譜系樹

從圖6～8中的結果可以看出，本論文提出的方法相比較最大簡約法，得出了更加接近標準譜系樹的結果。而進行缺失數據處理運用最大簡約法得出的樹不僅使得T.marocana物種的種間關系產生紊亂，如圖8實線框部分，而且還影響了其他樣本的種間關系如圖8虛線框部分。

3.3 方法可靠性驗證及分析

為了進一步說明本方法的優勢，選取三個數據集，分別為 Palaearctic parasite species of Testudinidae、菜花露尾甲屬和木槿屬形態學數據集[14-16]進行實驗。提出了一種基于路徑的物種準確率計算方法，并對每個物種集中的每個物種進行上述實驗，求得當前缺失比例下的平均準確率，缺失率實驗點為0%～70%。

3.3.1 物種準確率計算方法

為了評價生成譜系樹的準確性，本文提出一種基于單個物種節點路徑的準確率判定方法，以譜系樹嫁接物種的種間關系作為評價標準，能充分說明在嫁接物種后譜系樹的樹形結構變化。以嫁接物種為基準，說明嫁接物種與初始譜系樹中物種間的樹形結構關系。

以嫁接物種為基準，從根節點到嫁接物種的最后一個嫁接節點構建一個物種序列，每次遇到節點時構建的序列為當前節點另一分支的物種編號集合。以圖2中的譜系樹為標準，建立以E物種為基準的物種序列，節點路徑依次為1、2、4，則物種的序列對應為（（（A）B，C）D）。

以未經過缺失數據處理的物種運用最大簡約法構建的譜系樹做為標準，建立該物種的序列，稱為標準序列。對該物種進行屬性隨機缺失處理后，分別運用本論文方法和最大簡約法生成新樹，并分別建立該物種的序列，并與標準序列進行比對。與標準序列匹配的物種個數稱為路徑匹配物種數，標準序列物種總數稱為路徑物種總數。則準確率的計算公式為：

3.3.2 驗證過程

依次統計本文方法與最大簡約法生成樹的每個物種的準確率，進而求得兩種方法在此缺失率下的所有物種的平均準確率。在此基礎上對數據集中的數據繼續進行隨機缺失處理并逐步提高缺失數據率，數據缺失率實驗點分別為0%、10%、20%、30%、40%、50%、60%、70%。

將數據集中的嫁接物種進行隨機缺失處理，利用文中提出的方法與最大簡約法構建的譜系樹進行準確率比較。在圖9～11中，橫坐標表示物種的缺失數據比例，從0%到70%。縱坐標表示物種的平均準確率。

圖9 木槿屬缺失數據比例與物種平均準確率

圖10 菜花露尾甲屬缺失數據比例與物種平均準確率

圖11 《Palaearctic parasite species of Testudinidae》缺失數據比例與物種平均準確率

3.3.3 結果分析

從以上實驗結果可以看出，相比最大簡約法構建的譜系樹，本論文提出方法可以更準確地預測含有缺失數據物種所在譜系樹中的位置。缺失數據比例超過10%時，本方法構建的譜系樹中的樣本準確率明顯地高于最大簡約法。

當缺失數據比例大于10%時，本文提出的方法在實驗過程中隨著缺失數據比例的不斷上升，某些個別物種會出現表現不佳的情況，這時最大簡約法的表現也隨著降低。最大簡約法在某些個別物種上的表現優于本論文提出的方法，但是總體物種的平均準確率卻比本論文的方法低。

圖9和圖11中，缺失數據比例小于10%時，最大簡約法的準確率高于本論文提出的方法。而圖10則表明缺失數據比例小于10%，本論文方法準確率高于最大簡約法，但無缺失時最大簡約法的準確率要高于本論文方法。

兩種方法在缺失數據比例為10%到50%時，準確率是趨于平穩的；在缺失比例小于10%或大于50%時，兩種方法的準確率都會出現比較大的波動。

綜上所述，在運用生物形態學數據構建譜系樹時，單個物種缺失數據比例超過10%時，本論文方法的表現是優于最大簡約法的；而在缺失數據比例小于10%時，最大簡約法則表現更好。實驗結果表明在生物形態學數據缺失值比例大于10%時，運用本論文提出的方法所構建的譜系樹有著較高的準確率。

3.4 方法穩定性驗證及分析

本論文提出的基于先驗決策的譜系樹構建方法在判斷物種間的進化關系時依賴著判斷歸屬決策點的屬性決策組，嫁接物種屬性的隨機缺失影響著物種歸屬的判斷，對本方法的穩定性產生了一定的影響，為此實驗對單一物種的屬性進行多次的隨機缺失處理，并對本方法的穩定性進行評估。

在穩定性方面，運用Palaearctic parasite species of Testudinidae數據集中的單個物種在每個實驗點中進行多次隨機缺失處理，并求得準確率方差，來說明本方法在不同缺失率下的穩定性。從0%～70%共8個實驗點分別進行多次隨機缺失處理，每個實驗點隨機處理次數為100次，計算相對應的缺失數據物種準確率，并進行方差的計算。則單個物種多次隨機缺失處理準確率方差如圖12所示。

圖12 單個物種多次隨機缺失準確率方差

從圖12中可以看出，缺失數據比例小于50%時，單個物種的準確率方差較低，因此本論文提出的方法有著較好的穩定性。在缺失數據比例較低的情況下，缺失數據的數量還不足以打破決策點多屬性組的歸屬判斷，因而在多次隨機缺失處理的情況下本方法還保持著較低的準確率方差。而在缺失比例大于50%時，單個物種的準確率方差會出現猛然的上升趨勢，本方法的穩定性有所降低。隨著缺失數據比例的上升，隨機抽取得到的缺失數據導致的多屬性組歸屬判斷的穩定性會大大的降低，因此導致了準確率方差的突然提高。綜上所述，本方法在缺失比例小于50%時有著較好的穩定性，而在缺失數據比例大于50%穩定性的表現則欠佳。

4 結束語

本文提出方法，充分利用了初始譜系樹的先驗知識。能在物種含有較多缺失數據的情況下保持良好的準確率。并且由于含有缺失數據物種都是在初始譜系樹的基礎上進行嫁接，因而在構建進樹的過程中都能夠保證含有完整數據的譜系樹的穩定性。解決了在缺失數據不斷上升的情況下而導致的生成譜系樹的紊亂的問題。

本論文方法的不足之處：（1）相比最大簡約法，本方法需要初始譜系樹的先驗信息，先驗先驗信息越多，本方法的預測效果也就越好。（2）本模型只會在當前缺失數據的比例下給出物種在譜系樹中的位置，而不是像最大簡約法，即使含有缺失數據也會給最終啟發式搜索的最終結果。將在后續的工作中繼續探索和研究。

：

[1]Mucherino A，Seref O.Modeling and solving real-life global optimization problems with meta-heuristic methods[M]//Advances in Modeling Agricultural Systems.US：Springer，2009：403-419.

[2]Yang Z，Rannala B.Molecular phylogenetics：Principles and practice[J].Nature Reviews Genetics，2012，13（5）：303-14.

[3]鄭巍，羅阿蓉，史衛峰，等.系統發育分析中的最大簡約法及其優化[J].昆蟲學報，2013，56（10）：1217-1228.

[4]Bj?rklund M.Sober，E.1988.Reconstructing the Past.Parsimony，Evolution，and Inference.MIT Press，Cambridge（Mass），London，265 pp.$37.25[J].Journal of Evolutionary Biology，1990，3（5/6）：477.

[5]Camin J H，Sokal R R.A method for deducing branching sequences in phylogeny[J].Evolution，1965，19（3）：311-326.

[6]Hein J.Reconstructing evolution of sequences subject to recombination using parsimony[J].Mathematical Biosciences，1990，98（2）：185-200.

[7]Hein J.A heuristic method to reconstruct the history of sequences subject to recombination[J].Journal of Molecular Evolution，1993，36（4）：396-405.

[8]Taylor M P，Wedel M J，Cifelli R L.A new sauropod dinosaur from the Lower Cretaceous Cedar Mountain Formation，Utah，USA[J].Acta Palaeontologica Polonica，2011，56（1）：75-98.

[9]Wiens J J.Missing data and the design of phylogenetic analyses[J].Journal of Biomedical Informatics，2006，39（1）：34-42.

[10]Wiens J J.Missing data，incomplete taxa，and phylogenetic accuracy[J].Systematic Biology，2003，52（4）：528-538.

[11]Ma X，Wang G，Yu H，et al.Decision region distribution preservation reduction in decision-theoretic rough set model[J].Information Sciences，2014，278：614-640.

[12]張智磊，劉三陽.基于回溯搜索算法的決策粗糙集屬性約簡[J].計算機工程與應用，2016，52（10）：71-74.

[13]張騰飛，肖健梅，王錫淮.粗糙集理論中屬性約簡算法[J].電子學報，2005，33（11）：2080-2083.

[14]Bouamer S，Morand S.Phylogeny of palaearctic pharyngodonidae parasite species of testudinidae：A morphological approach[J].Canadian Journal of Zoology，2003，81（11）：1885-1893.

[15]林曉麗.中國菜花露尾甲屬分類及系統發育初探（鞘翅目：露尾甲科：訪花露尾甲亞科）[D].陜西咸陽：西北農林科技大學，2015.

[16]唐麗丹，原蒙蒙，李妍，等.基于形態學性狀的木槿屬系統發育分類研究[J].河南農業科學，2014，43（2）：105-111.