A New Tree Distance Metric for Structural Comparison of Sequences

Matthias Gallé 1, *
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
Dagstuhl Seminar: Structure Discovery in Biology: Motifs, Networks & Phylogenies, Jun 2010, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. 2010
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00559265
Contributeur : Matthias Gallé <>
Soumis le : mardi 25 janvier 2011 - 12:31:53
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : mardi 6 novembre 2012 - 12:20:15

Fichier

dagstuhl2010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 2010. 〈inria-00559265〉

Partager

Métriques

Consultations de la notice

185

Téléchargements de fichiers

231