A New Tree Distance Metric for Structural Comparison of Sequences

Matthias Gallé 1, *
* Corresponding author
1 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
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 dened by a tree and propose a new tree distance metric that capture structural similarity. This metric satises 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 modied copies of trees, outperforming an existing measure.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00559265
Contributor : Matthias Gallé <>
Submitted on : Tuesday, January 25, 2011 - 12:31:53 PM
Last modification on : Friday, November 16, 2018 - 1:24:49 AM
Long-term archiving on : Tuesday, November 6, 2012 - 12:20:15 PM

File

dagstuhl2010.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00559265, version 1

Citation

Matthias Gallé. A New Tree Distance Metric for Structural Comparison of Sequences. Dagstuhl Seminar: Structure Discovery in Biology: Motifs, Networks & Phylogenies, Jun 2010, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. ⟨inria-00559265⟩

Share

Metrics

Record views

207

Files downloads

248