Gröbner Bases Tutorial Part II Phylogenetic Trees

Phylogenetic Trees Gröbner Bases Tutorial Graph Theory Consider a rooted tree with a probability distribution at the root, a binary random variable at each leaf, and a transition matrix along each edge. π0 , π1 Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants α0 α1
α1 α0 t X1 t @ @ @ @ @ β0 β1
γ0 γ1
@ γ1 γ0 β1 β0 @ @ @ t @t X2 X3 This is the Cantor-Jukes binary model for K1,3 . The Probability Distribution Gröbner Bases Tutorial The matrices A1 = α0 α1
α1 α0 , A2 = β0 β1
, β1 β0 A3 = γ0 γ1
γ1 γ0 P(X` = j) = π0 A`0j + π1 A`1j . Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Experimentally, we can measure the probabilities pijk := P(X1 = i, X2 = j, X3 = k). The goal is to determine πi , αi , βi , γi . Note that Phylogenetic Invariants p000 = π0 α0 β0 γ0 + π1 α1 β1 γ1 p001 = π0 α0 β0 γ1 + π1 α1 β1 γ0 , and so on. π0 , π1 α0 α1
α1 α0 s X1 β0 β1 β1
β0 s @ @ γ0 γ1
@ γ1 γ0 @ s @s X2 X3 give Phylogenetic Invariants Gröbner Bases Tutorial The probabilities pijk are not independent. For example, regardless of how we assign πi , αi , βi , γi , the pijk always satisfy the relation Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants p001 p010 + p001 p100 − p000 p011 − p000p101 + p100 p111 − p101 p110 + p010 p111 − p011p110 = 0. This is an example of a binary phylogenetic invariant. Binary phylogenetic invariants form an ideal in k[pijk ]. Note: We can compute this ideal by eliminating πi , αi , βi , γi from the equations defining the pijk . Knowing the phylogenetic invariants is useful since they mean we don’t have to find all pijk —we can find some and solve the above equations for the rest. Once we have the pijk , we can solve for πi , αi , βi , γi . Change Coordinates Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants A Fourier transform gives a linear change of coordinates that transforms both pijk and the parameters πi , αi , βi , γi into new variables qijk and new parameters ri , ai , bi , ci such that q000 = r0 a0 b0 c0 , q001 = r1 a0 b0 c1 , . . . Eliminating the parameters gives the phylogenetic ideal hq001 q110 −q000 q111 , q010 q101 −q000 q111 , q100 q011 −q000 q111 i. This is a example of a toric ideal (a prime ideal generated by differences of monomials). Ordering the variables q000 > q001 > q010 > q011 > q100 > q101 > q110 > q111 , (the reverse of their binary values), a lex Gröbner basis is {q000 q111 −q011q100 , q001 q110 −q011q100 , q010 q101 −q011q100 }. Some Results Gröbner Bases Tutorial Theorem (Sturmfels and Sullivant (2005)) Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants The computation of the binary phylogenetic ideal can be reduced to the case of K1,n . For K1,n , we have: 2n variables qi1 ...in , ij = 0, 1. (j) 2(n + 1) parameters ai , i = 0, 1, j = 0, 1, . . . , n. (0) (1) (n) 2n equations qi1 ...in = ai1 +···+in ai1 · · · ain . Theorem (Sturmfels and Sullivant (2005)) The binary phylogenetic ideal In ⊆ k[qi1 ...in ] obtained by eliminating parameters is generated by degree 2 binomials. A Gröbner basis? Gröbner Bases Tutorial The number of degree 2 generators of In increases with n: Graph Theory Geometric Theorem Discovery n 3 4 5 6 # min gens 3 30 195 1050 The Generic Gröbner Walk Phylogenetic Invariants For n = 3, the degree 2 generators form a Gröbner basis. Question Is this true in general? In other words, does In always have a degree 2 Gröbner basis? Recent work of Chifman and Petrović (2007) says that the answer is yes. Set-up for the Gröbner Basis Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants The degree 2 Gröbner basis Gn of In is described recursively. Rn := k[qi1 ...in ] has lex order with q0...00 > q0...01 > q0...10 > q0...11 > · · · > q1...10 > q1...11 . For 1 ≤ j ≤ n, define πj : Rn → Rn−1 by πj (qi1 ...in ) = qi b 1 ...ij ...in . For A, B, C, D ∈ {0, 1}n with qA > qB , qA > qC > qD , set g = qA qB − qC qD . Goal Given Gn−1 , describe which g’s lie in Gn . Describe the Gröbner Basis Gröbner Bases Tutorial Recall that G3 is David A. Cox Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants {q000 q111 −q011q100 , q001 q110 −q011q100 , q010 q101 −q011q100 }. Definition Assume Gn−1 has been defined for some n ≥ 4. Then Gn consists of the following two types of g = qA qB − qC qD : Type 1: For some j, we have Aj = Bj = Cj = Dj and πj (g) ∈ Gn−1 . Type 2: For all j, we have Aj + Bj = Cj + Dj = 1 and πj (g) ∈ Gn−1 . Theorem (Chifman and Petrović (2007)) Gn is a lex Gröbner basis of In . Consequences Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Corollary For any tree, the binary phylogenetic ideal has a Gröbner basis consisting of degree 2 binomials. Corollary When we regard the field k as graded module over the quotient ring Rn /In , its free resolution is · · · → (Rn /In )β2 (−2) → (Rn /In )β1 (−1) → Rn /In → k → 0. It follows that Rn /In is a Koszul algebra. This corollary is a good example of how Gröbner bases can be used to prove theoretical results in commutative algebra and algebraic geometry. A Final Question Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Question Sequence A032263 from Sloane’s On-Line Encyclopedia of Integer Sequences begins 0, 0, 0, 3, 30, 195, 1050, 5103, 23310, . . . This gives the number of 2-element proper antichains in an n-element set. The formula for the nth term is 1 n n + 3 · 2n − 1). (4 − 3 · 3 2 Is this |Gn |? References Gröbner Bases Tutorial J. A. Cavender, J. Felsenstein, Invariants of phylogenies: a simple case with discrete states, J. Classification 4 (1987), 57–71. Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants J. Chifman, S. Petrović, Toric ideals of phylogenetic invariants for the general group-based model on claw trees K1,n , arXiv:0702368 [math.AC]. S. Evans, T. Speed, Invariants of some probability models used in phylogenetic inference, Ann. Statist. 21 (1993), 355–377. L. Pachter, B. Sturmfels, Algebraic Statistics for Computational Biology, Cambridge University Press, New York, 2005. B. Sturmfels, S. Sullivant, Toric ideals of phylogenetic invariants, J. Comp. Biol. 12 (2005), 204–228.