License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10231.3
URN: urn:nbn:de:0030-drops-27375
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2737/
|
Go to the corresponding Portal |
Gallé, Matthias
A New Tree Distance Metric for Structural Comparison of Sequences
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{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/opus/volltexte/2010/2737},
URN = {urn:nbn:de:0030-drops-27375},
doi = {10.4230/DagSemProc.10231.3},
annote = {Keywords: Tree distance, structure discovery, Parseval metric, Tanimoto distance}
}
|
Keywords: |
|
Tree distance, structure discovery, Parseval metric, Tanimoto distance |
|
Collection: |
|
10231 - Structure Discovery in Biology: Motifs, Networks & Phylogenies |
|
Issue Date: |
|
2010 |
|
Date of publication: |
|
23.08.2010 |
