<p>In this paper we analyze the effect of substitution rate heterogeneity on the sample complexity of species tree estimation. We consider a model based on the multi-species coalescent (MSC), with the addition that gene trees exhibit random i.i.d. rates of substitution. Our first result is a lower bound on the number of loci needed to distinguish 2-leaf trees (i.e., pairwise distances) with high probability, when substitution rates satisfy a growth condition. In particular, we show that to distinguish two distances differing by length <i>f</i> with high probability, one requires <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11538_2025_1533_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (f^{-2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msup> <mi>f</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> loci, a significantly higher bound than the constant rate case. The second main result is a lower bound on the amount of data needed to reconstruct a 3-leaf species tree with high probability, when mutation rates are gamma distributed. In this case as well, we show that the number of gene trees must grow as <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11538_2025_1533_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (f^{-2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msup> <mi>f</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

期刊论文
发表日期：

2025年9月27日

查看全文

Max Hill,
Sebastien Roch

摘要

In this paper we analyze the effect of substitution rate heterogeneity on the sample complexity of species tree estimation. We consider a model based on the multi-species coalescent (MSC), with the addition that gene trees exhibit random i.i.d. rates of substitution. Our first result is a lower bound on the number of loci needed to distinguish 2-leaf trees (i.e., pairwise distances) with high probability, when substitution rates satisfy a growth condition. In particular, we show that to distinguish two distances differing by length f with high probability, one requires $\Omega (f^{-2})$ $Ω (f^{- 2})$ loci, a significantly higher bound than the constant rate case. The second main result is a lower bound on the amount of data needed to reconstruct a 3-leaf species tree with high probability, when mutation rates are gamma distributed. In this case as well, we show that the number of gene trees must grow as $\Omega (f^{-2})$ $Ω (f^{- 2})$ .