Completing gene trees without species trees in sub-quadratic time.

Area of Science:

• Phylogenetics
• Computational Biology
• Bioinformatics

Background:

• Phylogenomic datasets often contain missing data, particularly in gene trees.
• Incomplete gene trees limit downstream applications in evolutionary studies.
• Rooting gene trees is crucial but challenging without a reference species tree.

Purpose of the Study:

• To develop a method for completing gene trees without relying on a reference species tree.
• To address the challenge of missing data in phylogenomic reconstruction.
• To provide an unbiased approach for gene tree completion.

Main Methods:

• Formulated an optimization problem to complete gene trees by minimizing quartet distance.
• Extended a seminal algorithm by Brodal et al. for efficient computation.
• Developed the tripVote method for gene tree completion.

Main Results:

• The tripVote method accurately completes gene trees using other gene trees.
• The approach demonstrates unbiased results, even without a reference species tree.
• The method achieves quasi-linear time complexity.

Conclusions:

• tripVote offers an effective solution for reconstructing complete gene trees from incomplete data.
• The method overcomes limitations of existing approaches that require a reference species tree.
• tripVote is a valuable tool for advancing phylogenomic analyses.