The phase-transition conjecture for phylogenetic reconstruction

Let mutation matrices be governed by a single order parameter $\theta$, and let $\theta(e)$ denote the parameter of the mutation matrix $M^e$ on edge $e$. Consider the Markov random field on the $(b+1)$-regular tree whose edge mutation matrices all have parameter $\theta$. Suppose there is a critical value $\theta_c$ such that the field is in an ordered phase when $\theta>\theta_c$ and in an unordered phase when $\theta<\theta_c$. Phase-transition conjecture. The minimal number of samples needed to reconstruct phylogenies for the family of all trees on $n$ leaves whose internal degrees are at least $b+1$ is

$$k=(c(\theta)+o(1))\log n,$$

if every edge of the phylogenetic tree satisfies $\theta(e)\geq\theta>\theta_c$, whereas

$$k=n^{c(\theta)+o(1)},$$

if every edge satisfies $\theta(e)\leq\theta<\theta_c$. This conjecture predicts a sharp change from logarithmic to polynomial sample complexity at the ordered–unordered phase transition, subject to the technical meanings of those phases.