Lower Bounds on the Sample Complexity of Species Tree Estimation when Substitution Rates Vary Across Loci

Area of Science:

• Computational Biology
• Phylogenetics
• Evolutionary Biology

Background:

• Species tree estimation relies on the multi-species coalescent (MSC) model.
• Gene trees within species often exhibit varying substitution rates, a factor complicating phylogenetic inference.
• Understanding the impact of this rate heterogeneity is crucial for accurate evolutionary history reconstruction.

Purpose of the Study:

• To analyze the effect of substitution rate heterogeneity on the sample complexity of species tree estimation.
• To derive lower bounds on the number of loci and gene trees required for accurate phylogenetic reconstruction under varying rates.
• To compare these bounds with those established for constant substitution rates.

Main Methods:

• Utilizing a multi-species coalescent (MSC) model incorporating random, independent and identically distributed (i.i.d.) substitution rates for gene trees.
• Deriving a lower bound for distinguishing 2-leaf species trees (pairwise distances) under a substitution rate growth condition.
• Establishing a lower bound for reconstructing a 3-leaf species tree with gamma-distributed mutation rates.

Main Results:

• The number of loci required to distinguish pairwise distances differing by 'f' scales as Ω(f⁻²), a substantial increase compared to the constant rate scenario.
• Reconstructing a 3-leaf species tree necessitates a number of gene trees that also scales as Ω(f⁻²), highlighting the impact of rate variation.
• These findings indicate that higher substitution rate heterogeneity leads to increased sample complexity in species tree estimation.

Conclusions:

• Substitution rate heterogeneity significantly inflates the data requirements (number of loci or gene trees) for accurate species tree inference.
• The derived Ω(f⁻²) bounds underscore the importance of accounting for rate variation in phylogenetic studies.
• Future research should consider these complexities to develop more robust and efficient phylogenetic methods.