QR-STAR: A Polynomial-Time Statistically Consistent Method for Rooting Species Trees Under the Coalescent

Area of Science:

• Computational Biology
• Phylogenetics
• Evolutionary Biology

Background:

• Rooting unrooted species trees from gene trees is crucial for understanding evolutionary relationships.
• The multispecies coalescent (MSC) model is a standard framework for gene tree evolution.
• Previous algorithms like Quintet Rooting (QR) showed promise but lacked proven statistical consistency.

Purpose of the Study:

• To develop a statistically consistent algorithm for rooting species trees under the MSC model.
• To improve upon the accuracy and theoretical guarantees of existing methods.
• To provide a robust computational tool for phylogenetic inference.

Main Methods:

• Introduced QR-STAR, a novel variant of the Quintet Rooting (QR) algorithm.
• Incorporated an additional step and a modified cost function into QR.
• Proved statistical consistency of QR-STAR under the MSC model.
• Derived sample complexity bounds for QR-STAR, including a variant with polynomial sample complexity using 'short quintets'.

Main Results:

• QR-STAR is statistically consistent for rooting species trees under the MSC.
• The algorithm achieves polynomial sample complexity, particularly the 'short quintets' variant.
• Simulations demonstrate that QR-STAR matches or surpasses the accuracy of the original QR algorithm across various conditions.

Conclusions:

• QR-STAR offers a statistically sound and accurate method for inferring rooted species trees from gene trees.
• The algorithm advances the field of phylogenetics by providing theoretical guarantees and improved performance.
• QR-STAR is available as an open-source tool to facilitate research in evolutionary biology.