DROPS

Document

A New Tree Distance Metric for Structural Comparison of Sequences

Authors: Matthias Gallé

Published in: Dagstuhl Seminar Proceedings, Volume 10231, Structure Discovery in Biology: Motifs, Networks & Phylogenies (2010)

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.

Cite as

Matthias Gallé. A New Tree Distance Metric for Structural Comparison of Sequences. In Structure Discovery in Biology: Motifs, Networks & Phylogenies. Dagstuhl Seminar Proceedings, Volume 10231, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{galle:DagSemProc.10231.3,
  author =	{Gall\'{e}, Matthias},
  title =	{{A New Tree Distance Metric for Structural Comparison of Sequences}},
  booktitle =	{Structure Discovery in Biology: Motifs, Networks \& Phylogenies},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10231},
  editor =	{Alberto Apostolico and Andreas Dress and Laxmi Parida},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10231.3},
  URN =		{urn:nbn:de:0030-drops-27375},
  doi =		{10.4230/DagSemProc.10231.3},
  annote =	{Keywords: Tree distance, structure discovery, Parseval metric, Tanimoto distance}
}

Search Results

Documents authored by Gallé, Matthias

A New Tree Distance Metric for Structural Comparison of Sequences

Abstract

Cite as

Thanks for your feedback!

Could not send message