Linear-time algorithms for phylogenetic tree completion under Robinson-Foulds distance.

Area of Science:

• Computational Biology
• Phylogenetics
• Algorithm Development

Background:

• Comparing phylogenetic trees with non-identical leaf sets presents computational challenges.
• Traditional methods restrict trees to common leaves, potentially losing information.
• Tree completion, by adding missing leaves, offers an alternative approach.

Purpose of the Study:

• To develop efficient algorithms for comparing phylogenetic trees with non-identical leaf sets.
• To address tree comparison problems where one tree's leaves are a subset of another's, and where leaf sets partially overlap.
• To introduce and solve a restricted version of the more general tree completion problem.

Main Methods:

• Developed optimal linear-time algorithms for tree completion under the Robinson-Foulds (RF) distance.
• Improved existing algorithms for subset leaf set comparison from quadratic to linear time complexity.
• Proposed and solved a restricted version of the general partial overlap leaf set problem.

Main Results:

• Achieved linear-time complexity for comparing trees with subset leaf sets, a significant improvement.
• Provided the first algorithms for a restricted version of the general problem of comparing trees with partially overlapping leaf sets.
• Experimental results indicate completion-based RF distances differ substantially from traditional RF distances.

Conclusions:

• Optimal linear-time algorithms for tree completion problems enhance phylogenetic tree comparison.
• Tree completion provides a valuable alternative to traditional methods, yielding potentially different evolutionary insights.
• The developed algorithms advance the field of computational phylogenetics, particularly for non-identical leaf set comparisons.