• Omur.NNITechReport2013

Kod*lab Menu

Internal Links (Login Required)

<< Kod*lab Publications

Discriminative Measures for Comparison of Phylogenetic Trees

ESE Technical Report, 2013

arXiv:1310.5202 [q-bio.PE], 2013

OmurArslan*, Dan P. Guralnik *, D. E. Koditschek*
*: Electrical and Systems Engineering, University of Pennsylvania
Full PDF | arXiv

Navigation in the Space of Trees
Navigation in the Space of Trees
       Efficient and informative comparison of trees is a common essential interest of both computational biology and pattern classification. In this paper, we introduce a novel dissimilarity measure on non-degenerate hierarchies (rooted binary trees), called the NNI navigation distance, that counts the steps along the trajectory of a discrete dynamical system defined over the Nearest Neighbor Interchange(NNI) graph of binary hierarchies. The NNI navigation distance has a unique unifying nature of combining both edge comparison methods and edit operations for comparison of trees and is an efficient approximation to the (NP-hard) NNI distance. It is given by a closed form expression which simply generalizes to nondegenerate hierarchies as well. A “relaxation” on the closed form of the NNI navigation distance results a simpler dissimilarity measure on all trees, named the crossing dissimilarity, counts pairwise cluster incompatibilities of trees. Both of our dissimilarity measures on nondegenerate hierarchies are positive definite (vanishes only between identical trees) and symmetric but are not a true metric because they do not satisfy the triangle inequality. Although they are not true metrics, they are both linearly bounded below by the widely used Robinson-Foulds metric and above by a new tree metric, called the cluster-cardinality distance — the pullback metric of a matrix norm along an embedding of hierarchies into the space of matrices. All of these proposed tree measures can be efficiently computed in time O(n2) in the number of leaves, n.
This work was funded in part by the Air Force Office of Science Research under the MURI FA9550–10–1−0567.
BibTeX entry
author       = {Arslan, O. and Guralnik, D. P.  and Koditschek, D. E.},
title        = {Discriminative Measures for Comparison of Phylogenetic Trees},
institution  = {University Of Pennsylvania},
year         = {2013}

Copyright Kodlab, 2017