TY - GEN
T1 - The generalized Robinson-Foulds metric
AU - Böcker, Sebastian
AU - Canzar, Stefan
AU - Klau, Gunnar W.
N1 - Funding Information:
This work is supported in part by the National Institutes of Health under grant R01 HG006677.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84884379594&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84884379594&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40453-5_13
DO - 10.1007/978-3-642-40453-5_13
M3 - Conference contribution
AN - SCOPUS:84884379594
SN - 9783642404528
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 156
EP - 169
BT - Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings
T2 - 13th Workshop on Algorithms in Bioinformatics, WABI 2013
Y2 - 2 September 2013 through 4 September 2013
ER -