Reconstructing phylogenies from noisy quartets in polynomial time with a high success probability

Area of Science:

• Computational Biology
• Bioinformatics
• Phylogenetics

Background:

• Quartet-based phylogeny reconstruction methods are gaining attention in computational biology.
• Traditional accuracy assessment relies on simulations, lacking theoretical depth.
• A novel model-based approach is presented to evaluate quartet-based method accuracy.

Purpose of the Study:

• To introduce a new model-based framework for measuring the accuracy of quartet-based phylogeny reconstruction.
• To propose efficient algorithms for reconstructing the true phylogeny.

Main Methods:

• Development of a novel model for assessing phylogeny reconstruction accuracy.
• Design of three distinct algorithms for reconstructing evolutionary trees.
• Analysis of algorithmic efficiency and success probability under varying error conditions.

Main Results:

• An O(n^2) algorithm reconstructs the true phylogeny without errors, querying minimal quartet topologies.
• An O(n^4 log n) algorithm achieves high accuracy (approx. 1-p) with quartet errors.
• A third algorithm improves accuracy to approximately [equation; see text] in O(n^5) time, with a success rate of at least 0.984 for p < 0.05.

Conclusions:

• The proposed algorithms are mathematically guaranteed to reconstruct the true phylogeny with high success probability.
• Experimental results validate theoretical bounds and demonstrate superior speed and accuracy compared to existing methods.
• The study provides a robust theoretical and algorithmic framework for quartet-based phylogeny reconstruction.