Open Access. Powered by Scholars. Published by Universities.®

Operations Research, Systems Engineering and Industrial Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

Departmental Papers (ESE)

Life Sciences

Articles 1 - 1 of 1

Full-Text Articles in Operations Research, Systems Engineering and Industrial Engineering

Discriminative Measures For Comparison Of Phylogenetic Trees, Omur Arslan, Dan P. Guralnik, Daniel E. Koditschek Jan 2017

Discriminative Measures For Comparison Of Phylogenetic Trees, Omur Arslan, Dan P. Guralnik, Daniel E. Koditschek

Departmental Papers (ESE)

In this paper we introduce and study three new measures for efficient discriminative comparison of phylogenetic trees. The NNI navigation dissimilarity $d_{nav}$ counts the steps along a “combing” of the Nearest Neighbor Interchange (NNI) graph of binary hierarchies, providing an efficient approximation to the (NP-hard) NNI distance in terms of “edit length”. At the same time, a closed form formula for $d_{nav}$ presents it as a weighted count of pairwise incompatibilities between clusters, lending it the character of an edge dissimilarity measure as well. A relaxation of this formula to a simple count yields another measure on all ...