Sensitivity Analysis of Bipartition Dissimilarity under Tree Rearrangement Operations

Abstract — Trees are a powerful structure for representing hierarchical relations in a natural way. Comparison of trees is a recurrent task in various computer science related fields. The widely used Robinson-Foulds distance for comparing leaf labeled trees is overly sensitive to very small changes in the tree. The measure of bipartition dissimilarity refines Robinson-Foulds metric by comparing the quality of the tree bipartitions instead of their quantity. Sensitivity analysis is used in this paper which shows that bipartition dissimilarity has smaller sensitivity to small modifications in the tree. Keywords- leaf labeled trees; Robinson-Foulds distance; bipartition dissimilarity; sensitivity analysis; tree rearrangement operations I