Finiteness results for abelian tree models. (English) Zbl 1386.13052

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 B. Sturmfels and 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 M. Michałek and E. Ventura [“Phylogenetic complexity of the Kimura 3-parameter model”, 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.


13E05 Commutative Noetherian rings and modules
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
14M12 Determinantal varieties
15A69 Multilinear algebra, tensor calculus
62P10 Applications of statistics to biology and medical sciences; meta analysis


Zbl 1391.13058
Full Text: DOI arXiv


[1] Allman, E. S., Rhodes, J. A.: Phylogenetic ideals and varieties for the general Markov model. Adv. Appl. Math. 40, 127-148 (2008) · Zbl 1131.92046 · doi:10.1016/j.aam.2006.10.002
[2] Bates, D. J., Oeding, L.: Toward a salmon conjecture. Experiment. Math. 20, 358-370 (2011) · Zbl 1262.14056 · doi:10.1080/10586458.2011.576539
[3] Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. 21, 1-46 (1989) · Zbl 0681.03020 · doi:10.1090/S0273-0979-1989-15750-9
[4] Borel, A.: Linear Algebraic Groups. Springer, New York (1991) · Zbl 0726.20030
[5] Buczyńska, W., Wiśniewski, J. A.: On geometry of binary symmetric models of phyloge- netic trees. J. Eur. Math. Soc. 9, 609-635 (2007) · Zbl 1147.14027 · doi:10.4171/JEMS/90
[6] Casanellas, M., Fernández-Sánchez, J.: The geometry of the Kimura 3-parameter model. Adv. Appl. Math. 41, 265-292 (2008) · Zbl 1222.14110 · doi:10.1016/j.aam.2007.09.003
[7] Casanellas, M., Fernández-Sánchez, J.: Relevant phylogenetic invariants of evolutionary models. J. Math. Pures Appl. (9) 96, 207-229 (2011) · Zbl 1230.14063 · doi:10.1016/j.matpur.2010.11.002
[8] Casanellas, M., Sullivant, S.: The strand symmetric model. In: Algebraic Statis- tics for Computational Biology, Cambridge Univ. Press, Cambridge, 305-321 (2005) · Zbl 1374.60139
[9] Cipra, B. A.: Algebraic geometers see ideal approach to phylogenetics. SIAM News 40 no. 6 (2007)
[10] Cohen, D. E.: On the laws of a metabelian variety. J. Algebra 5, 267-273 (1967) · Zbl 0157.34802 · doi:10.1016/0021-8693(67)90039-7
[11] Draisma, J.: Finiteness for the k-factor model and chirality varieties. Adv. Math. 223, 243-256 (2010) · Zbl 1211.13020 · doi:10.1016/j.aim.2009.08.008
[12] Draisma, J., Kuttler, J.: On the ideals of equivariant tree models. Math. Ann. 344, 619- 644 (2009) · Zbl 1398.62338
[13] Draisma, J., Kuttler, J.: Bounded-rank tensors are defined in bounded degree. Duke Math. J. 163, 35-63 (2014) · Zbl 1314.14109 · doi:10.1215/00127094-2405170
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.