一個相容超樹問題的改進演算法

Abstract

在演化生物學中，尋找超樹是個重要的主題。一棵半標籤樹T 是一個有以下特性的樹：(1) 每個T 的頂點可以有零到多個標籤；(2) 每個標籤在T 裡只出現一次；(3) 所有的樹葉與無分叉的頂點都至少有一個標籤。如果滿足以下性質，則稱半標籤樹T 遠祖顯示另一棵半標籤樹T ′ ：(1) 如果x 在T ′ 裡是y 的祖先，則x 在T 裡仍是y 的祖先；(2) 各自來說，如果在T ′ 之中，x, y 不在從樹根到y, x 的路徑上，則各自來說x, y 在T 之 中不會在從樹根到y, x 的路徑上。一個排名半標籤樹T 是一棵在每個頂點上都有一個排名值的半標籤樹。如果u 是v 的祖先，則u 的排名會比v 的排名小。如果滿足以下條件，則稱排名半標籤樹T 保存一個相對分歧時刻div(L) < div(L′ )：lca (L) 的排名小於lca (L′ ) 的排名。其中L 及L′ 是兩個標籤集合，lca (L) 則是那些標籤所在頂點的最接近共同祖先。 我們提出一個在O(h log 2 h) 時間與O(h) 空間內找到一個排名半標籤樹的演算法，此樹遠祖顯示輸入的一組半標籤樹P 與一組相對分歧時刻D。其中h是P 中每棵樹的標籤數目總和加上D中每個相對分歧時刻中的標籤數目總和。

Finding supertrees is critical in evolutionary biology. A semi-labeled tree T is a rooted tree satisfies the following: (1) each node in T has zero to multiple labels, (2) each label in T appears only once, and (3) all leaves and non-branching internal nodes have at least one label. A semi-labeled tree T ancestrally displays another semi-labeled tree T ′ if the following are satisfied: (1) if x is an ancestor of y in T ′ , then x is an ancestor of y in T ; and (2) if x, y are not on the path from root to y, x in T ′ , respectively, then x, y are not on the path from root to y, x, respectively. A ranked semi-labeled tree T is a semi-labeled tree with one rank on each node, and if u is an ancestor of v, then the rank of u is smaller than the rank of v. A ranked semi-labeled tree T preserves a relative divergence date div(L) < div(L′ ) where L and L′ are two set of labels, if the rank of lca (L) is smaller than the rank of lca (L′ ) where lca (L) is the least common ancestor of the vertices which the labels l ∈ L is on. We show a O(m log2 m)-time and O(m)-space algorithm to find a ranked semi-labeled tree which ancestrally displays a set P of semi-labeled trees and preserves a set D of relative divergence dates, where m is the sum of the number of labels in each trees in P and of labels in L and L′ in each relative divergence dates in D.