The Open Cybernetics & Systemics Journal

2015, 9 : 110-114
Published online 2015 April 17. DOI: 10.2174/1874110X01509010110
Publisher ID: TOCSJ-9-110

Matching Similar Splits between Unrooted Leaf-labeled Trees

Li Shuguang and Xin Xiao
College of Computer Science and Technology, Shandong Institute of Business and Technology, Yantai, 264005, P.R. China.

ABSTRACT

Tree comparison is ubiquitous in many areas. The simplest way for tree comparison is to define a pairwise distance measure. In a more refined comparison, one can establish a mapping between similar parts in two trees according to certain similarity measure. The best match problem for rooted leaf-labeled trees has been studied in the literature. However, no result has been found for the best match problem for unrooted leaf-labeled trees. The problem of mapping similar splits between unrooted leaf-labeled trees is considered in this paper. Based on a new similarity measure obtained from the classical Jaccard coefficient, the mapping can be computed in quadratic time.

Keywords:

Jaccard coefficient , leaf-labeled trees , similarity measure , splits, tree comparison.