TL;DR
This paper introduces the first polynomial-time algorithms for optimally completing and comparing incomplete phylogenetic trees using the Robinson-Foulds (RF) distance. They provide both a linear-time 2-approximation algorithm and an exact $O(nk^2)$ algorithm, demonstrating that this "completion-based" RF distance can lead to significantly different conclusions about tree similarity compared to traditional methods.
What Problem Does This Paper Address?
Phylogenetic trees are crucial for understanding evolutionary relationships. Comparing these trees often involves measuring their similarity using distance metrics. A common challenge is that phylogenetic trees inferred from different datasets may not share the exact same set of "leaves" (e.g., species or genes). The traditional approach to compare such trees is to prune them down to their common leaf set, which can discard valuable evolutionary information.
This paper tackles the problem of comparing trees with non-identical leaf sets by proposing an alternative: "completion." This involves adding missing leaves to each tree to create identical leaf sets, and then minimizing the distance between these completed trees. Specifically, the authors focus on the Robinson-Foulds (RF) distance, a widely used metric. The core challenge is that computing the optimal completion that minimizes RF distance has, until now, lacked efficient polynomial-time algorithms. This paper aims to fill that gap.
Methods
The authors develop two main algorithmic contributions:
- 2-Approximation Algorithm: They show that a previously proposed "Extraneous-Clade-Free" (EF-RF(+)) distance measure serves as a 2-approximation for the optimal completion-based RF distance (RF(+)). Since EF-RF(+) can be computed in linear time, this provides a fast, albeit approximate, solution. The core idea is to modify optimal completions to avoid certain "extraneous clades" (subtrees containing leaves from both original trees but no common leaves), which surprisingly bounds the increase in RF distance.
- Exact Algorithm: They present an exact $O(nk^2)$ algorithm for the RF(+) problem, where $n$ is the total number of distinct leaf labels and $k$ is related to the number of maximal subtrees unique to each input tree. This algorithm is based on a dynamic programming approach that recursively computes optimal "costs" associated with completing subtrees. The algorithm leverages a novel tree transformation (T") and a recurrence relation to efficiently calculate these costs.
Both algorithms are developed for rooted trees and then extended to unrooted trees.
Datasets
The authors evaluated their algorithms using three real biological phylogenetic tree datasets:
- Marsupials (158 trees)
- Legumes (22 trees)
- Placental Mammals (726 trees)
They also used simulated datasets generated by the birth-death model in SaGePhy for comparing the EF-RF(+) and RF(+) distances. No new benchmarks were introduced; existing biological datasets were used.
Key Insights and Ideas
- Completion vs. Restriction: The most striking insight is that comparing trees after optimal completion (RF(+)) can lead to drastically different conclusions about their similarity compared to the traditional restriction-based RF distance (RF(-)). This highlights the potential information loss in the traditional method.
- EF-RF(+) as a Good Heuristic: The EF-RF(+) distance, which is linear-time computable, is shown to be a good 2-approximation and, in practice, often yields results very close to the optimal RF(+) distance. This makes it a practical heuristic for large datasets.
- The Power of Dynamic Programming: The exact algorithm demonstrates how dynamic programming can be effectively applied to solve complex combinatorial optimization problems on trees, even when dealing with the nuances of optimal completions.
- Extraneous Clades Matter: The concept of "extraneous clades" is central to both the approximation and exact algorithms. Understanding how to manage or avoid these structures is key to achieving optimal or near-optimal results.
Key Results
- First Polynomial-Time Algorithms: The paper presents the first polynomial-time algorithms for optimal completion-based RF distance (RF(+)) for both rooted and unrooted trees.
- 2-Approximation: A linear-time 2-approximation algorithm for RF(+) is provided.
- Exact Algorithm: An exact $O(nk^2)$ algorithm for RF(+) is developed.
- Significant Differences in Similarity: Experimental results show that RF(+) distance can lead to substantially different inferences of phylogenetic similarity compared to RF(-) distance, particularly for trees with high leaf-overlap. For instance, at least 10% of triples showed conflicts (Type 1, 2, or 3) when leaf-overlap ratio was 0.7 or greater.
- EF-RF(+) Close to Optimal: For biological datasets, EF-RF(+) distances were found to be very close to RF(+) distances (average ratio of RF(+) to EF-RF(+) was around 0.998 for marsupials, 0.993 for legumes, and 0.995 for placental mammals).
- Impact on Applications: The study suggests that using RF(+) distance can substantially impact phylogenetic database search and clustering, especially when trees have large leaf-overlap.
Limitations and Future Work
- Binary Trees: The current work is restricted to comparison of binary trees. Future work could extend these methods to non-binary trees.
- Other Distance Measures: The authors suggest extending completion-based methods to other distance/similarity measures like triplet/quartet distances, NNI, SPR, and nodal distances.
- Multi-labeled Trees: The idea of computing optimal completions could be extended to multi-labeled trees, which arise in scenarios like gene duplication.
- Practical Performance: While the exact algorithm is polynomial, its $O(nk^2)$ complexity might still be prohibitive for extremely large trees. The strong performance of the EF-RF(+) approximation suggests it as a practical alternative.
Summary updated