Finiteness results for abelian tree models (Q2344494): Difference between revisions

This article studies equivariant tree models on evolutionary trees. An equivariant model is specified by a rooted tree \(T\), a finite alphabet \(B\) and a group \(G\) acting on \(B\). There is a random variable \(X_v\) associated to each vertex \(v \in \text{vert}(T)\). These random variables take values in the alphabet \(B\). The model parameters are the distribution \(\pi\) at the root \(r\) and transition matrices \(A_e\) for each edge \(e \in \text{edge}(T)\). The transition matrices satisfy \(A_e(gb,gb') = A_e(b,b')\) for all \(g \in G\) and \(b,b' \in B\). The probability of observing a word \(\mathbf{b}\) at the leaves of \(T\) is \[ P(\mathbf{b}) = \sum_{\mathbf{b}' \in B^{\text{vert(T)}} \text{ extending } \mathbf{b}} \pi(b'_r) \prod_{e=(v,v') \in \text{edge}(T)} A_e(b'_v,b'_{v'}). \] An equivariant model is the set of joint probability distributions in \(\mathbb{R}^{B^{\text{leaf}(T)}}\) for all parameter values for fixed \(T, B\) and \(G\). The first main result of this paper states that if \(G\) is an abelian group, then there exists a bound \(D(B,G)\) such that the Zariski closure of the equivariant model for any \(T\) and given \(B\) and \(G\) is defined by polynomial equations of degree at most \(D(B,G)\). If \(G\) is abelian, \(B=G\) and \(G\) is acting by left multiplication on itself, then the resulting model is a group-based model and this Zariski closure of the model is a toric variety. It was conjectured by \textit{B. Sturmfels} and \textit{S. Sullivant} [J. Comp. Biol. 12, 204--228 (2005; Zbl 1391.13058)] that the toric ideal of the toric variety is generated by polynomials of degree at most \(|G|\). The original conjecture was proven for \(G=\mathbb{Z}_2\) by Sturmfels and Sullivant and for \(G=\mathbb{Z}_2 \times \mathbb{Z}_2\) by \textit{M. Michałek} and \textit{E. Ventura} [``Phylogenetic complexity of the Kimura 3-parameter model'', \url{arXiv:1704.02584}]. The result in this paper is the first general result for any abelian group \(G\) towards the conjecture by Sturmfels and Sullivant. The difference from the conjecture is that the result in this paper does not give an explicit bound and it is for the generators of the radical of the ideal (this is a set-theoretic result whereas the original conjecture is ideal-theoretic). The second main result of the paper states that there exists an algorithm that decides in polynomial time whether a joint probability vector lies in the Zariski closure of the equivariant model for \(T,B\) and \(G\), where \(G\) is an abelian group. This proof is nonconstructive and it does not give an explicit algorithm.