A Linear Time Solution to the Labeled Robinson-Foulds Distance Problem

Area of Science:

• Phylogenetics and evolutionary biology
• Computational biology and bioinformatics
• Algorithms and combinatorics

Background:

• Comparing phylogenetic trees is crucial for understanding evolutionary relationships.
• The Robinson-Foulds (RF) distance is widely used but does not account for internal node labels like gene duplication or speciation events.
• Comparing event-labeled gene trees requires methods beyond standard tree edit distances.

Purpose of the Study:

• To develop a novel distance metric for comparing event-labeled phylogenetic trees.
• To extend the Robinson-Foulds (RF) distance to accommodate internal node labels representing evolutionary events.
• To enable new analyses of reconciled gene trees and the impact of sampling strategies.

Main Methods:

• Proposed an extension of the Robinson-Foulds (RF) distance, termed the Labeled Robinson-Foulds (LRF) distance.
• Defined LRF distance based on edit operations: node insertion, deletion, and label substitution.
• Developed a linear-time algorithm for computing the LRF distance.

Main Results:

• The Labeled Robinson-Foulds (LRF) distance is a metric, reduces to RF for unlabeled trees, and is computationally efficient (linear time).
• The LRF distance provides a framework for analyzing event-labeled trees, such as reconciled gene trees.
• Analysis using LRF showed that denser taxon sampling improves tree topology but can negatively impact event labeling accuracy.

Conclusions:

• The Labeled Robinson-Foulds (LRF) distance is a valuable new tool for comparing complex phylogenetic trees with event labels.
• This metric facilitates deeper insights into gene tree reconciliation and evolutionary event inference.
• The findings highlight a trade-off between topological accuracy and event labeling accuracy influenced by taxon sampling in phylogenetics.