A generalized Robinson-Foulds distance for labeled trees

Area of Science:

• Phylogenetics
• Computational Biology
• Evolutionary Biology

Background:

• The Robinson-Foulds (RF) distance is a standard metric for comparing phylogenetic trees.
• However, the traditional RF distance does not account for the biological meaning of internal nodes, such as speciation or duplication events.
• This limitation hinders its application in gene evolution studies where branching event types are crucial.

Purpose of the Study:

• To extend the Robinson-Foulds (RF) distance to incorporate labeled internal nodes in phylogenetic trees.
• To develop a more biologically relevant measure for comparing gene trees by considering the types of evolutionary events.

Main Methods:

• Introduced a node flip operation in addition to edge contractions and extensions to extend the RF distance.
• Explored the properties of this extended RF distance, particularly for binary labeled trees.
• Developed a 2-approximation algorithm for computing the extended RF distance.

Main Results:

• The extended RF distance accounts for labeled internal nodes, offering greater biological insight.
• An optimal edit path for labeled trees may necessitate contracting shared edges, unlike in the unlabeled case.
• The proposed 2-approximation algorithm demonstrates strong empirical performance.

Conclusions:

• The extended Robinson-Foulds distance provides a more biologically meaningful way to compare phylogenetic trees with labeled nodes.
• This advancement opens new algorithmic avenues for analyzing evolutionary relationships, particularly in the context of gene family evolution.
• An implementation and simulation data are publicly available for reproducibility and further research.