论文标题
多项式POSET的计算线性扩展受到代数约束的约束
Computing linear extensions for polynomial posets subject to algebraic constraints
论文作者
论文摘要
在本文中，我们考虑了计算给定POSET的线性扩展的经典问题，这是一个困难的问题。但是，在我们的设置中，POSET的要素是多元多项式，并且仅由评估图隐含地确定的这些线性扩展的一个小的“可允许”子集。这个看似新颖的问题出现在对基因调节网络的全球动态研究中，在这种情况下，POSET是布尔晶格。我们提供了一种使用线性编程来解决此问题的算法，以进行任意的线性多项式部分。 该算法利用了从多项式继承的这种附加代数结构，以有效计算可允许的线性扩展。与生物学相关的问题涉及多项式多项式，我们提供了将其嵌入线性问题实例的结构。
In this paper we consider the classical problem of computing linear extensions of a given poset which is well known to be a difficult problem. However, in our setting the elements of the poset are multivariate polynomials, and only a small "admissible" subset of these linear extensions, determined implicitly by the evaluation map, are of interest. This seemingly novel problem arises in the study of global dynamics of gene regulatory networks in which case the poset is a Boolean lattice. We provide an algorithm for solving this problem using linear programming for arbitrary partial orders of linear polynomials. This algorithm exploits this additional algebraic structure inherited from the polynomials to efficiently compute the admissible linear extensions. The biologically relevant problem involves multilinear polynomials and we provide a construction for embedding it into an instance of the linear problem.
