License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-27375
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2737/
Gallé, Matthias

A New Tree Distance Metric for Structural Comparison of Sequences

pdf-format:
Dokument 1.pdf (285 KB)

Abstract

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.

BibTeX - Entry

@InProceedings{gall:DSP:2010:2737,
  author =	{Matthias Gall{\'e}},
  title =	{A New Tree Distance Metric for Structural Comparison of Sequences},
  booktitle =	{Structure Discovery in Biology: Motifs, Networks & Phylogenies},
  year =	{2010},
  editor =	{Alberto Apostolico and Andreas Dress and Laxmi Parida},
  number =	{10231},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2737},
  annote =	{Keywords: Tree distance, structure discovery, Parseval metric, Tanimoto distance}
}

Keywords: Tree distance, structure discovery, Parseval metric, Tanimoto distance
Seminar: 10231 - Structure Discovery in Biology: Motifs, Networks & Phylogenies
Issue date: 2010
Date of publication: 23.08.2010

DROPS-Home | Fulltext Search | Imprint Published by LZI