Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home

Technical Reports

printable version

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

Click here for full text: PDF

On matching nodes between trees

Zhang, Li


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

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.