The generalized Robinson-Foulds metric

Sebastian Böcker, Stefan Canzar, Gunnar W. Klau

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

The Robinson-Foulds (RF) metric is arguably the most widely used measure of phylogenetic tree similarity, despite its well-known shortcomings: For example, moving a single taxon in a tree can result in a tree that has maximum distance to the original one; but the two trees are identical if we remove the single taxon. To this end, we propose a natural extension of the RF metric that does not simply count identical clades but instead, also takes similar clades into consideration. In contrast to previous approaches, our model requires the matching between clades to respect the structure of the two trees, a property that the classical RF metric exhibits, too. We show that computing this generalized RF metric is, unfortunately, NP-hard. We then present a simple Integer Linear Program for its computation, and evaluate it by an all-against-all comparison of 100 trees from a benchmark data set. We find that matchings that respect the tree structure differ significantly from those that do not, underlining the importance of this natural condition.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings
Pages156-169
Number of pages14
DOIs
StatePublished - 2013
Event13th Workshop on Algorithms in Bioinformatics, WABI 2013 - Sophia Antipolis, France
Duration: Sep 2 2013Sep 4 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8126 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th Workshop on Algorithms in Bioinformatics, WABI 2013
Country/TerritoryFrance
CitySophia Antipolis
Period9/2/139/4/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'The generalized Robinson-Foulds metric'. Together they form a unique fingerprint.

Cite this