@article{10.1145/1279721.1279722,
    Abstract = {A contemporary and exciting application of Gr\"{o}bner bases is their use in computational biology, particularly in the reverse engineering of gene regulatory networks from experimental data. In this setting, the data are typically limited to tens of points, while the number of genes or variables is potentially in the thousands. As such data sets vastly underdetermine the biological network, many models may fit the same data and reverse engineering programs often require the use of methods for choosing parsimonious models. Gr\"{o}bner bases have recently been employed as a selection tool for polynomial dynamical systems that are characterized by maps in a vector space over a finite field.While there are numerous existing algorithms to compute Gr\"{o}bner bases, to date none has been specifically designed to cope with large numbers of variables and few distinct data points. In this paper, we present an algorithm for computing Gr\"{o}bner bases of zero-dimensional ideals that is optimized for the case when the number m of points is much smaller than the number n of indeterminates. The algorithm identifies those variables that are essential, that is, in the support of the standard monomials associated to a polynomial ideal, and computes the relations in the Gr\"{o}bner basis in terms of these variables. When n is much larger than m, the complexity is dominated by nm3. The algorithm has been implemented and tested in the computer algebra system Macaulay 2. We provide a comparison of its performance to the Buchberger-M\"{o}ller algorithm, as built into the system.},
    Address = {New York, NY, USA},
    Author = {Just, Winfried and Stigler, Brandilyn},
    File = {Computing Grobner Bases of Ideals of Few Points in High Dimensions - just2006 - a.pdf},
    ISSN = {1932-2240},
    Journal = {ACM Commun. Comput. Algebra},
    Keywords = {Gr\"{o}bner bases, run-time complexity, essential variables, Buchberger-M\"{o}ller algorithm, computational biology applications},
    Month = {sep},
    Number = {3--4},
    Pages = {67--78},
    Publisher = {Association for Computing Machinery},
    Title = {Computing Gr\"{o}bner Bases of Ideals of Few Points in High Dimensions},
    URL = {https://doi.org/10.1145/1279721.1279722},
    Volume = {40},
    Year = {2006},
    bdsk-url-1 = {https://doi.org/10.1145/1279721.1279722},
    date-added = {2022-12-08 08:56:47 +0100},
    date-modified = {2022-12-08 08:56:47 +0100},
    issue_date = {September-December 2006},
    numpages = {12},
    doi = {10.1145/1279721.1279722}
}

@article{10.1145/1279721.1279722, Abstract = {A contemporary and exciting application of Gr\"{o}bner bases is their use in computational biology, particularly in the reverse engineering of gene regulatory networks from experimental data. In this setting, the data are typically limited to tens of points, while the number of genes or variables is potentially in the thousands. As such data sets vastly underdetermine the biological network, many models may fit the same data and reverse engineering programs often require the use of methods for choosing parsimonious models. Gr\"{o}bner bases have recently been employed as a selection tool for polynomial dynamical systems that are characterized by maps in a vector space over a finite field.While there are numerous existing algorithms to compute Gr\"{o}bner bases, to date none has been specifically designed to cope with large numbers of variables and few distinct data points. In this paper, we present an algorithm for computing Gr\"{o}bner bases of zero-dimensional ideals that is optimized for the case when the number m of points is much smaller than the number n of indeterminates. The algorithm identifies those variables that are essential, that is, in the support of the standard monomials associated to a polynomial ideal, and computes the relations in the Gr\"{o}bner basis in terms of these variables. When n is much larger than m, the complexity is dominated by nm3. The algorithm has been implemented and tested in the computer algebra system Macaulay 2. We provide a comparison of its performance to the Buchberger-M\"{o}ller algorithm, as built into the system.}, Address = {New York, NY, USA}, Author = {Just, Winfried and Stigler, Brandilyn}, File = {Computing Grobner Bases of Ideals of Few Points in High Dimensions - just2006 - a.pdf}, ISSN = {1932-2240}, Journal = {ACM Commun. Comput. Algebra}, Keywords = {Gr\"{o}bner bases, run-time complexity, essential variables, Buchberger-M\"{o}ller algorithm, computational biology applications}, Month = {sep}, Number = {3--4}, Pages = {67--78}, Publisher = {Association for Computing Machinery}, Title = {Computing Gr\"{o}bner Bases of Ideals of Few Points in High Dimensions}, URL = {https://doi.org/10.1145/1279721.1279722}, Volume = {40}, Year = {2006}, bdsk-url-1 = {https://doi.org/10.1145/1279721.1279722}, date-added = {2022-12-08 08:56:47 +0100}, date-modified = {2022-12-08 08:56:47 +0100}, issue_date = {September-December 2006}, numpages = {12}, doi = {10.1145/1279721.1279722} }