Algorithms for Computing Cluster Dissimilarity between Rooted Phylogenetic Trees

ABSTRACT

Phylogenetic trees represent the historical evolutionary relationships between different species or organisms. Creating and maintaining a repository of phylogenetic trees is one of the major objectives of molecular evolution studies. One way of mining phylogenetic information databases would be to compare the trees by using a tree comparison measure. Presented here are a new dissimilarity measure for comparing rooted trees and three algorithms to efficiently compute it. This new measure operates on clusters of compared trees as in the case of standard Robinson-Foulds distance, but extracts more subtle differences between clusters, and thus may offer better discrimination than the Robinson-Foulds distance.

Keywords:

Cluster dissimilarity, combinatorial algorithms, phylogenetic trees, robinson-foulds distance, tree comparison.