=Paper=
{{Paper
|id=Vol-3273/paper2
|storemode=property
|title=Degröbnerization and Its Applications: Reverse Engineering of Gene Regulatory Networks (poster paper)
|pdfUrl=https://ceur-ws.org/Vol-3273/paper2.pdf
|volume=Vol-3273
|authors=Michela Ceria,Samuel Lundqvist,Ferdinando Mora
|dblpUrl=https://dblp.org/rec/conf/scsquare/CeriaLM21
}}
==Degröbnerization and Its Applications: Reverse Engineering of Gene Regulatory Networks (poster paper)==
https://ceur-ws.org/Vol-3273/paper2.pdf
Degröbnerization and Its Applications: Reverse
Engineering of Gene Regulatory Networks
Michela Ceria1,*,† , Samuel Lundqvist2,† and Ferdinando Mora3,†
1
Dipartimento di Meccanica, Matematica e Management, Politecnico di Bari, Via Orabona 4, I-70125 Bari, Italy
2
Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden
3
Dipartimento di Matematica, Università di Genova, Via Dodecaneso 35, 16146, Genova, Italy
Abstract
In this short note, we consider an application of ideals of points in biology and algebraic statistics
proposed by Laubenbacher and Stigler. We do this from the Degröbnerization perspective, avoiding
unnecessary computations of Gröbner bases, and instead, when possible, leaning on linear algebra and
combinatorial methods.
Keywords
Ideals of points, normal forms, vector space bases, Degröbnerization
1. Introduction
Following the convention of [13], let 𝒫 := k[𝑥1 , ..., 𝑥𝑛 ] be the polynomial ring over a field k,
and let 𝐼 be a zero-dimensional ideal in 𝒫. Then 𝒫/𝐼 is finite as a vector space over k. Let 𝐴
denote a set of polynomials such that its image under the map 𝒫 → 𝒫/𝐼 is a vector space basis
for 𝒫/𝐼.
Having a∑︀basis for 𝒫/𝐼 means that we can define a normal form for elements in 𝒫 as
Nf(𝑝,∑︀𝐴) = 𝑡∈𝐴 𝑐𝑡 𝑡, where the coefficients {𝑐𝑡 } are uniquely determined by requiring that
𝑝 − 𝑡∈𝐴 𝑐𝑡 𝑡 is zero under the map 𝒫 → 𝒫/𝐼.
The most common way of choosing a vector space basis for 𝒫/𝐼 is as the image of the Gröbner
escalier with respect to a fixed term order under the map 𝒫 → 𝒫/𝐼. Recall that the Gröbner
escalier, sometimes referred to as the Gröbner staircase, or the standard monomials, is the set of
monomials outside the leading monomial ideal with respect to the term order.
We denote the Gröbner escalier of 𝐼 by 𝑁 (𝐼). The border of 𝑁 (𝐼) is the set of terms
{𝑥𝑖 𝑡 : 𝑡 ∈ 𝑁 (𝐼)} ∖ 𝑁 (𝐼). With this notation, the set {𝑡 − Nf(𝑡, 𝑁 (𝐼)) : 𝑡 on the border of
𝑁 (𝐼)} becomes a Gröbner basis for 𝐼.
Given a finite set of points X = {𝑃1 , ..., 𝑃𝑁 } ⊂ k𝑛 , let us denote by 𝑃𝑖 = (𝑎1𝑖 , ..., 𝑎𝑛𝑖 ),
1 ≤ 𝑖 ≤ 𝑁 , the coordinates of the points and by 𝐼(X) the zero dimensional ideal of all
polynomials vanishing on X; the vanishing ideal with respect to X.
SC2 2021: 6th International Workshop on Satisfiability Checking and Symbolic Computation, August 19–20, 2021
*
Corresponding author.
†
These authors contributed equally.
$ michela.ceria@gmail.com (M. Ceria); samuel@math.su.se (S. Lundqvist); 5919@unige.it (F. Mora)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
One important feature of a Gröbner basis is that it provides a way to compute normal forms
via Buchberger’s reduction. We stress, however, that for vanishing ideals of points, the tools
provided by this reduction process should be considered non-optimal, and we will in Proposition
1 recall an alternative way of efficiently computing the coefficients of the normal form 𝑡∈𝐴 𝑐𝑡 𝑡,
∑︀
which goes in line with the idea of Degröbnerization.
There are several algorithms available for computing a vector space basis for 𝒫/𝐼. For our
purposes the most important ones are the Buchberger-Möller algorithm and the Cerlienco-Mu-
reddu Correspondence. We point the reader to the paper [1] for a discussion of other methods,
in particular the Möller algorithm. We remark also that the treatment of the Buchberger-Möller
algorithm and the Cerlienco-Mureddu Correspondence is done in a more careful way in [1].
sation
The Buchberger-Möller algorithm [12] is a method based on linear algebra that determines
𝑁 (𝐼(X)), the border, and the Gröbner basis (by computing the normal form of the border
elements).
The Cerlienco and Mureddu algorithm [3, 4, 5] computes 𝑁 (X) combinatorially by defining
a bijection (the Cerlienco-Mureddu Correspondence) Φ : X → 𝑁 (𝐼(X)) between X and
𝑁 (𝐼(X)), with respect to the lexicographical term ordering.
The main ways of implementing the Cerlienco-Mureddu Correspondence is by means of the
Lex Game [6], and the Iterative Lex Game [1, 2]. The number of comparisons needed in the Lex
Game, which iterates over the coordinates, is bounded by 𝑛𝑁 + 𝑁 2 , see [10]. However, for
many purposes it is important to be able to iterate over the points, and the Iterative Lex Game
does this with complexity 𝑂(𝑁 2 𝑛 log(𝑁 )).
Le us finally recall the following proposition.
Proposition 1 ([10]). Let X = {𝑃1 , ..., 𝑃𝑁 } be a finite set of points, let 𝐼 = 𝐼(X) ⊆
k[𝑥1 , ..., 𝑥𝑛 ] be the vanishing ideal with respect to X, and let 𝐴 = {𝑡1 , ..., 𝑡𝑁 } ⊂ k[𝑥1 , ..., 𝑥𝑛 ] be
such that its image under the map 𝒫 → 𝒫/𝐼 is a vector space basis for 𝒫/𝐼.
Then, for each 𝑓 ∈ k[𝑥1 , ..., 𝑥𝑛 ], we have
Nf(𝑓, 𝐴) = (𝑡1 , ..., 𝑡𝑁 )(𝐴[X]−1 )𝑡 (𝑓 (𝑃1 ), ..., 𝑓 (𝑃𝑁 ))𝑡 , (1)
where 𝐴[X] is the matrix whose rows are the evaluations of 𝐴 at the elements of X, and where
Nf(𝑓, 𝐴) is the normal form of 𝑓 with respect to 𝐼(X) and the basis.
The above Proposition 1 shows that, as soon as we have X and a basis of the quotient algebra
𝒫/𝐼(X), computing the normal form of any polynomial modulo 𝐼(X) is only a matter of
evaluations and linear algebra.
2. Gröbner technologies for gene regulatory networks
We now briefly describe the model for gene regulatory networks introduced by Laubenbacher
and Stigler [8]. For a more detailed treatment, we refer to [1].
Let 𝑝 be a prime and let X = {𝑃1 , ..., 𝑃𝑁 } ⊆ (Z𝑝 )𝑛 be a set of points, and consider the map
𝐹 : (Z𝑝 )𝑛 , → (Z𝑝 )𝑛 , 𝐹 (𝑃𝑖 ) = (𝑓1 (𝑃𝑖 ), . . . , 𝑓𝑛 (𝑃𝑖 )), where
𝑓𝑗 : (Z𝑝 )𝑛 → Z𝑝 , 1 ≤ 𝑗 ≤ 𝑛 : (𝑓1 (𝑃𝑖 ), . . . , 𝑓𝑛 (𝑃𝑖 )) = 𝑃𝑖+1 , 𝑖 = 1, . . . , 𝑁 − 1. (2)
These functions represent the dynamical system in question, where the variables represent
the genes, and the points represent the states the genes can be in.
What is done in [8] is to separately compute the functions 𝑓𝑗 , 1 ≤ 𝑗 ≤ 𝑛, as polynomials in
normal form, namely in reduced form modulo the ideal 𝐼(X).
In a further paper [9] Lauenbacher and Stigler apply their tool to the design of experiments
[14] remarking that their algorithm can be applied simply adapting Eq.(2) after redefining 𝐹 as
𝐹 (𝑃𝑖 ) = (𝑓1 (𝑃𝑖 ), . . . , 𝑓𝑛 (𝑃𝑖 )) = 𝑄𝑖 , 𝑖 = 1, . . . , 𝑁
for specific given points 𝑄𝑖 ∈ k𝑛 , 𝑖 = 1, . . . , 𝑁.
3. The Gröbnerian approach versus the Degröbnerization
approach
To solve both problems, Laubenbacher and Stigler propose to first determine a particular solution
for each 𝑓𝑗 , then compute a Gröbner basis 𝒢 of 𝐼(X), via the Buchberger-Möller algorithm, and
finally determine the normal form of each particular solution using Buchberger’s reduction.
The complexity of this procedure is reported, see [8], to be quadratic in the number of
variables and exponential in the number 𝑁 of time points, but in fact, using a trick in the
reduction process, see [1], the algorithm of [8] can be improved to work within the complexity
𝑂(𝑛2 𝑁 3 ((log(𝑝))2 )).
In the Degröbnerization approach, the evaluation 𝐹 (𝑃𝑖 ) of a particular solution is directly
read from X, a linear basis for k[𝑥1 , ..., 𝑥𝑛 ]/𝐼 is computed by the Lex Game, or the iterative
Lex Game algorithm, and Proposition 1 is used for the normal form computation.
Even if we use the slower iterative Lex Game algorithm for computing the linear basis, we
obtain an improvement by a factor 𝑛; the complexity using the iterative Lex Game algorithm
is 𝑂(𝑛𝑁 3 (log(𝑝))2 ) [1]. As we usually have 𝑛 > 𝑁 in these biological applications [7], this
improvement is substantial.
Let us remark that both the algorithm by Laubenbacher and Stigler [8] and our Degröb-
nerization approach share the same input and output, but uses alternative and in some sense
dual approaches to describe and process the data. The major practical advantage of the latter
approach is the shortcut achieved by skipping the computation of a Gröbner basis. But the
two approaches represent a real change of perspective. In the Gröbner framework, data are
represented via the polynomial ideal. On the other hand, Degröbnerization represents data via
the quotient algebra, with its multiplicative structure.
We have discussed the problem in the original setting where the coefficients are considered
in the finite field Z𝑝 ; however both algoritms hold (and in principle could have important
applications [14]) in the general case of an arbitrary field. We refer the reader to [1] for a careful
analysis of this approach.
References
[1] Michela Ceria, Samuel Lundqvist, Teo Mora, Degröbnerization: A political manifesto. To
appear in Applicable Algebra in Engineering, Communication and Computing (2022).
[2] Michela Ceria, Teo Mora, Combinatorics of ideals of points: a Cerlienco-Mureddu-like
approach for an iterative lex game, available in arxiv as arXiv:1805.09165 [math.AC].
[3] Luigi Cerlienco , Marina Mureddu, Algoritmi combinatori per l’interpolazione polinomiale
in dimensione ≥ 2, Publ. I.R.M.A. Strasbourg, 461/S-24 Actes 24𝑒 Séminaire Lotharingien
(1993), 39–76.
[4] Luigi Cerlienco, Marina Mureddu, From algebraic sets to monomial linear bases by means of
combinatorial algorithms, Discrete Math. 139 (1995), 73–87.
[5] Luigi Cerlienco, Marina Mureddu, Multivariate Interpolation and Standard Bases for
Macaulay Modules, J. Algebra 251 (2002), 686–726.
[6] Bálint Felszeghy, Balázs Ráth, Lajos Rónyai, The lex game and some applications, Journal of
Symbolic Computation 41, no 6 (2006), 663–681.
[7] Winfried Just, Brandilyn Stigler, Computing Gröbner bases of ideals of few points in high
dimensions, Communications in Computer Algebra 40, no. 3 (2006), 65–96.
[8] Reinhard Laubenbacher, Brandilyn Stigler, A computational algebra approach to the reverse
engineering of gene regulatory networks, Journal of Theoretical Biology, 229, no. 4 (2004),
523–537, Academic Press.
[9] Reinhard Laubenbacher, Brandilyn Stigler, Design of experiments and biochemical network
inference in Algebraic and Geometric Methods in Statistics. Eds: Gibilisco, Riccomagno,
Rogantin, Wynn, Cambridge University Press (2008).
[10] Samuel Lundqvist, Vector space bases associated to vanishing ideals of points, Journal of
Pure and Applied Algebra 214 no. 4 (2010), 309–321.
[11] Samuel Lundqvist, Complexity of comparing monomials and two improvements of the
Buchberger-Möller algorithm, MMISC 2008, Lecture Notes in Comput. Sci. 5393 (2008),
105–125.
[12] Hans Michael Möller, Bruno Buchberger, The construction of multivariate polynomials with
preassigned zeros, in European Computer Algebra Conference (1982), 24–31, Springer.
[13] Teo Mora, Solving Polynomial Equation Systems 4 Vols., Cambridge University Press,
I DOI: 10.1017/𝐶𝐵𝑂9780511542831 (2003), II DOI: 10.1017/𝐶𝐵𝑂9781107340954
(2005),
III DOI: 10.1017/𝐶𝐵𝑂9781139015998 (2015), IV DOI:10.1017/𝐶𝐵𝑂9781316271902
(2016).
[14] Giovanni Pistone, Eva Riccomagno, Maria Piera Rogantin, Methods in algebraic statistics
for the design of experiments, in Optimal Design and Related Areas in Optimsation and
Statistics (2009), 97–132, Springer.