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

An Improved Algorithm for Compatible Supertree Problem

鄭智中(Chih-Chung Cheng)

指導教授 ： 呂學一

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.01859

摘要

在演化生物學中，尋找超樹是個重要的主題。一棵半標籤樹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.

並列關鍵字

Supertree ； evolutionary tree

參考文獻

[1] A. V. Aho, Y. Sagiv, T. G. Szymanski, and J. D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing, 10(3):405–421, 1981.

[2] V. Berry and C. Semple. Fast computation of supertrees for compatible phylogenies with nested taxa. Systematic Biology, 55(2):270–288, 2006.

Beck, R. Grenyer, S. A. Price, R. A. Vos, J. L. Gittleman, and A. Purvis. The delayed rise of present-day mammals. Nature, 446(7135):507–512, 2007.

[4] M. Bordewich, G. Evans, and C. Semple. Extending the limits of supertree methods. Annals of Combinatorics, 10(1):31–51, 2006.

[6] D. Bryant and M. Steel. Extension operations on sets of leaf-labelled trees. Advances in Applied Mathematics, 16(4):425–453, 1995.