New scalable measure for comparing phylogenetic trees

The problem of comparing phylogenetic trees is based on finding a distance between different models of evolution. This problem is important because of existing various methods for reconstructing phylogenies, which applied to the same data set result in different trees. In the paper we construct a measure in a polynomial time using new structures called i-clusters. We analyze properties of i-clusters and prove that the measure is a metric in some space of rooted phylogenetic trees. The constructed measure is parametrized and the scalability parameter may be defined by user according to the real data size and complexity. The presented measure is the extension of widely applied error metric, defined by Robinson and Foulds in 1981. The generalization enables us to ommit small mistakes on low level and not to loose similarity of compared trees on high level.