Scaling of accuracy in extremely large phylogenetic trees

Area of Science:

• Computational Biology
• Evolutionary Biology
• Bioinformatics

Background:

• Phylogenetic inference is crucial for understanding evolutionary relationships.
• Scaling accuracy with increasing taxa is a key challenge in molecular phylogenetics.
• Existing molecular sequence databases contain large sets of homologous genes.

Purpose of the Study:

• To examine the accuracy of phylogenetic inference with simulated data sets up to 10,000 taxa.
• To determine how the number of characters required for accurate tree estimation scales with the number of taxa.
• To investigate the impact of substitution rates and node depth on phylogenetic accuracy.

Main Methods:

• Simulated data sets with up to 10,000 taxa were generated.
• Maximum parsimony without branch swapping was used as the primary search algorithm.
• The number of characters needed for accurate tree estimation was analyzed in relation to the number of taxa.
• Scaling of accuracy was assessed under varying substitution rates and for different tree depths.

Main Results:

• Phylogenetic accuracy scales favorably (logarithmically) with the number of taxa under optimal substitution rates.
• Doubling the number of taxa requires only an arithmetic increase in characters to maintain accuracy.
• Higher substitution rates had a manageable adverse effect on scaling.
• Shallow nodes showed favorable log-linear scaling, while deep nodes proved difficult to reconstruct accurately, exhibiting poor scaling.

Conclusions:

• Sequencing large numbers of homologous genes can improve phylogenetic accuracy, but scaling is not always better than log N for high accuracy.
• Deep phylogenetic nodes present significant reconstruction challenges.
• Alternative strategies beyond simply increasing gene numbers may be required for resolving complex phylogenetic problems.