
Click here for full text:
On matching nodes between trees
Zhang, Li
HPL200367
Keyword(s): phylogenetic tree comparison; lower envelope
Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. Consider two rooted leaflabeled 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 nonlinear 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 pseudoplanes and then apply the results from Computational Geometry to obtain an efficient algorithm.
15 Pages
Back to Index
