An Improved Algorithm for Compatible Supertree Problem
Date Issued
2009
Date
2009
Author(s)
Cheng, Chih-Chung
Abstract
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.
Subjects
Supertree
evolutionary tree
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R94922110-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):3616acf34de19d13ad41bad71756450c