Inferring the Topology of Gene Regulatory Networks: An Algebraic Approach to Reverse Engineering - Mathematical Concepts and Methods in Modern Biology - page 93

Example 3.10. Consider the ideal

z 2

x y 2 x 2

I = − z , − y , xz + 1 − z − y + yz − x , xy − yz , − ⊆ Z 3 [ x , y , z ] .

This ideal has three distinct marked reduced Gröbner bases,

G 1 , G 2 , G 3 (below), that
correspond to the given weight vectors (monomial orderings), ω i . In other words, the

Gröbner fan of I consists of three cones and each of the given weight vectors is an
element of a different cone.

z 2 y 2 x 2

G 1 ={

− z , − y , xz + yz − x − y − z + 1 , xy − yz , − x } ,

ω 1 ={ 2 , 1 , 1 } ,

z 2 x 2

G 2 ={

− z , − x , yz + xz − y − x − z + 1 ,

y 2 xy + xz − y − x − z + 1 , − y } ,ω 2 ={ 1 , 2 , 1 } ,

y 2 x 2 z 2

G 3 ={

− y , − x , yz − xy , xz + xy − z − x − y + 1 , − z } ,

ω 3 ={ 1 , 1 , 2 } .

One can compute the first Gröbner basis, for instance, using the following Macaulay
2 code. Note that the ideal generators do not have to be a Gröbner basis.

R=ZZ/3[x,y,z, MonomialOrder=>{Weights=>{2,1,1}}]
I=ideal(zˆ2-z, yˆ2-y, x*z+y*z-x-y-z+1, x*y-y*z, xˆ2-x)
flatten entries gens gb I
The following are the normal forms of the polynomial

f =− xy + y + z ∈

Z 3 [ x , y , z ] , calculated with respect to the Gröbner bases and monomial orderings

above:

f 1 =− yz + y + z , f 2 = xz − x + 1 , f 3 =− xy + z + y .

The software packages Gfan and others implement a special type of Gröbner basis
conversion, known as the Gröbner walk [ 32 ]. Unless, however, the dimension of the
fan is low or the number of its cones happens to be small, computing the entire fan
is computationally expensive and some of its components do not have polynomial
bounds. The following is an example that illustrates how infeasible computing the
entire Gröbner fan could be.
Example 3.11. For illustrative purposes, we will work over Q in this example. The

Gröbner fan of the ideal

x 1 −

x 1

x 3 + x 2 , x 2 − x 1 , x 3 − x 2 + I = 1 + 1 + x 3 + 1 + ⊆ Q[ x 1 , x 2 , x 3 ]

has 360 full-dimensional cones. The intersection of the fan with the standard simplex
in

3 is shown in Figure 3.2 [ 31 ].
Fortunately, in order to compute polynomial normal forms, the only informa-
tion that we need to extract from the Gröbner cones of a fan is their corresponding
reduced Gröbner bases and/or their relative volumes, where “relative” refers to the

R