Discriminative measures for comparison of phylogenetic trees

详细信息    查看全文

• 作者：Omur Arslan ; ^{omur@seas.upenn.edu} ; Dan P. Guralnik ^{guralnik@seas.upenn.edu} ; Daniel E. Koditschek ^{kod@seas.upenn.edu}
• 关键词：Phylogenetic trees ; Evolutionary trees ; Nearest Neighbor Interchange ; Comparison of classifications ; Tree metric
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P3
• 页码：405-426
• 全文大小：705 K
• 卷排序：217

文摘

In this paper we introduce and study three new measures for efficient discriminative comparison of phylogenetic trees. The NNI navigation dissimilarity  dnavdnav 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 dnavdnav 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 trees — the crossing dissimilarity  dCMdCM. Both dissimilarities are symmetric and positive definite (vanish only between identical trees) on binary hierarchies but they fail to satisfy the triangle inequality. Nevertheless, both are bounded below by the widely used Robinson–Foulds metric and bounded above by a closely related true metric, the cluster-cardinality metric  dCCdCC. We show that each of the three proposed new dissimilarities is computable in time O(n2) in the number of leaves nn, and conclude the paper with a brief numerical exploration of the distribution over tree space of these dissimilarities in comparison with the Robinson–Foulds metric and the more recently introduced matching-split distance.