Toric ideals of homogeneous phylogenetic models

ABSTRACT

We consider the model of phylogenetic trees in which every node of the tree is an observed, binary random variable and the transition probabilities are given by the same matrix on each edge of the tree. The ideal of invariants of this model is a toric ideal in ℂ[p;_i1;…i;_n;]. We are able to compute the Göbner basis and minimal generating set for this ideal for trees with up to 11 nodes. These are the first non-trivial Gröbner bases calculations in 2¹¹ = 2048 indeterminates. We conjecture that there is a quadratic Gröbner basis for binary trees, but that generators of degree n are required for some trees with n nodes. The polytopes associated with these toric ideals display interesting finiteness properties. We describe the polytope for an infinite family of binary trees and conjecture (based on extensive computations) that there is a universal bound on the number of vertices of the polytope of a binary tree.

REFERENCES

• 1: E. Allman and J. Rhodes. Phylogenetic invariants for the general markov model of sequence mutation. Mathematical Biosciences, pages 1--33, 2003.
• 2: J. Cavender and J. Felsenstein. Invariants of phylogenies in a simple case with discrete states. Journal of Classification, 4:57--71, 1987.
• 3: S. Collart , M. Kalkbrener , D. Mall, Converting bases with the Gröbner walk, Journal of Symbolic Computation, v.24 n.3-4, p.465-469, Sept./Oct. 1997 [doi>10.1006/jsco.1996.0145]
• 4: W. Fulton. Introduction to toric varieties, volume 131 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, 1993. The William H. Roever Lectures in Geometry.
• 5: E. Gawrilow and M. Joswig. polymake: a framework for analyzing convex polytopes. In G. Kalai and G. M. Ziegler, editors, Polytopes --- Combinatorics and Computation, pages 43--74. Birkhäuser, 2000.
• 6: R. Hemmecke and R. Hemmecke. 4ti2 version 1.1---computation of Hilbert bases, Graver bases, toric Gröbner bases, and more. Available at www.4ti2.de, Sept. 2003.
• 7: A. N. Jensen. Cats, a software system for toric state polytopes. Available at www.soopadoopa.dk/anders/cats/cats.html, 2003.
• 8: E. H. Kuo. Viterbi Sequences and Polytopes, 2004.
• 9: L. Pachter and B. Sturmfels. Parametric Inference for Biological Sequence Analysis, 2004.
• 10: L. Pachter and B. Sturmfels. Tropical Geometry of Statistical Models, 2004.
• 11: M. Steel and Y. Fu. Classifying and counting linear phylogenetic invariants for the jukes-cantor model. Journal of computational biology, 2(1):39--47, 1995.
• 12: M. Steel, L. Székely, P. Erdös, and P. Waddell. A complete family of phylogenetic invariants for any number of taxa under kimura's 3st model. New Zealand Journal of Botany, 31:289--296, 1993.
• 13: B. Sturmfels. Gröbner bases and convex polytopes, volume 8 of University Lecture Series. American Mathematical Society, Providence, RI, 1996.
• 14: B. Sturmfels. Equations defining toric varieties. In Algebraic geometry---Santa Cruz 1995, volume 62 of Proc. Sympos. Pure Math., pages 437--449. Amer. Math. Soc., Providence, RI, 1997.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Experimentation, Theory

Keywords:
Gröbner bases, parametric inference, phylogenetic invariants, toric ideals