| |
Click here for full text:
On matching nodes between trees
Zhang, Li
HPL-2003-67
Keyword(s): phylogenetic tree comparison; lower envelope
Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. Consider two rooted leaf-labeled trees T(subscript 1), T(subscript 2). Define the similarity between two internal nodes, one from each tree, to be the size of A intersecting B over the size of A union B, where A, B are the sets of the leaves under the two nodes, respectively. In this paper, we consider the problem of computing for every node in T(subscript 1), the best matching node in T(subscript 2) under the above similarity measure. Such problem arises in applications such as comparing phylogenetic trees. In this paper, we present an O((n log n) (superscript 1.5) time algorithm for the problem. The major difficulty in solving this problem is that the above similarity measure is non-linear while the traditional algorithms normally deal with linear weights. To overcome the difficulty, one novelty in our solution is to reduce the problem to computing the upper- envelope of pseudo-planes and then apply the results from Computational Geometry to obtain an efficient algorithm.
15 Pages
Back to Index
|
printable version
