OCTAL: Optimal Completion of gene trees in polynomial time

Area of Science:

• Phylogenetics
• Computational Biology
• Bioinformatics

Background:

• Gene trees are often incomplete due to various biological and technical factors.
• Incomplete gene trees can negatively impact downstream phylogenetic analyses.
• Accurate completion of gene trees is crucial for reliable downstream studies.

Purpose of the Study:

• Introduce the Optimal Tree Completion problem for inferring missing taxa in gene trees.
• Present OCTAL, an algorithm for optimally completing gene trees using a reference tree.
• Evaluate OCTAL's performance in simulations with incomplete lineage sorting.

Main Methods:

• Defined the Optimal Tree Completion problem as minimizing distance to a reference tree.
• Developed the OCTAL algorithm to find optimal solutions using the Robinson-Foulds (RF) distance.
• Simulated gene trees exhibiting incomplete lineage sorting and completed them using OCTAL.

Main Results:

• OCTAL optimally completes gene trees by adding missing leaves to minimize RF distance.
• OCTAL demonstrated higher accuracy in completing gene trees compared to the ASTRAL-II heuristic.
• Accuracy of OCTAL-completed trees depends on the topological similarity between the reference and true gene trees.

Conclusions:

• OCTAL is a valuable tool for adding missing taxa to incomplete gene trees.
• OCTAL shows good accuracy across diverse model conditions.
• Using species trees as reference trees can limit OCTAL's accuracy under high incomplete lineage sorting.