A New Tree Distance Metric for Structural Comparison of Sequences

Structure Discovery in Biology: Motifs, Networks & Phylogenies

计算机科学;物理学;数学

Matthias Gallé

Others  :  http://drops.dagstuhl.de/opus/volltexte/2010/2737/pdf/10231.GalleMatthias.Paper.2737.pdf
PID  :  42841

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

In this paper we consider structural comparison of sequences, that is, to compare sequences not by their content but by their structure. We focus on the case where this structure can be defined by a tree and propose a new tree distance metric that capture structural similarity. This metric satisfies non-negativity, identity, symmetry and the triangle inequality. We give algorithms to compute this metric and validate it by using it as a distance function for a clustering process of slightly modified copies of trees, outperforming an existing measure.