Biology Reference
In-Depth Information
x
2
x
2
x
2
for
I
because
xf
2
−
yf
1
=
∈
I
and so
in
grlex
(
)
=
∈
in
grlex
(
I
)
but
x
2
y
. The Buchberger algorithm (or any of its
improvements, such as the Buchberger-Möller algorithm [
24
]) generates the following
grlex
Gröbner basis:
∈
in
grlex
(
f
2
)
=
x
3
x
2
f
1
),
in
grlex
(
,
x
3
x
2
y
2
y
2
x
2
2
y
2
.
Example 3.5.
In the previous example, we can see that the leading monomials
(disregarding coefficients) of the Gröbner basis are
x
3
{
−
2
xy
,
−
+
x
,
−
,
−
2
xy
,
−
+
x
}
x
2
y
x
2
xy
, and
y
2
.Sothe
,
,
,
initial ideal is generated by
x
2
xy
, and
y
2
: any other leading monomial can be writ-
ten in terms of these generators. Furthermore, we see that the standard monomials
associated to the Gröbner basis are 1,
x
, and
y
.
,
3.4
CONSTRUCTION OF THE MODEL SPACE:
A REVERSE ENGINEERING ALGORITHM
In this section, we consider the problem of constructing PDSs from a given set of data
collected from a biological system on
n
components, called
nodes
.
Let
n
be a set of
m
input states of an
n
-node
F
be a finite field. Let
s
1
,...,
s
m
∈ F
n
a set of corresponding output states, where
n
system, and
t
1
,...,
t
m
∈ F
,
m
∈ N
.
Each of
s
i
and
t
j
has the form
=
s
i
1
,...,
s
in
,
s
i
=
t
j
1
,...,
t
jn
,
t
j
n
and italicized states are elements of
where states in bold are elements of
F
F
.Weaim
such that
F
s
i
=
to find all PDSs
F
=
(
f
1
,...
f
n
)
over
F
t
i
for each 1
i
m
x
n
. We proceed by considering the subproblem of
finding all transition polynomials
f
j
that satisfy
f
j
(
∈ F
x
1
,...,
and where each
f
j
s
1
)
=
t
1
j
f
j
(
s
2
)
=
t
2
j
.
f
j
(
s
m
)
=
t
mj
.
. The identity
a
p
Let
p
be the (prime) characteristic of
∈ F
imposes a degree restriction on polynomials when viewed as functions, namely
x
p
i
F
=
a
for each
a
m
. This equation gives rise to the relation
x
p
i
=
x
i
for 1
i
−
x
i
=
0,
for each 1
m
. Since we are interested in polynomials that can be treated
as functions, the local functions
f
j
are actually polynomials in the quotient ring
i
F
x
1
,...,
x
n
/
x
1
x
n
. This ring contains polynomials that are the
x
n
−
x
1
,...,
−
x
n
upon division by the degree relations,
that is, polynomials whose degree in any variable is less than
p
. In essence, the quo-
tient ring is constructed by “modding out” by the elements of the “divisor” ideal.
Thus we aim to find all polynomials
f
j
F
x
1
,...,
remainders of the elements of
∈ F
x
1
,...,
x
n
/
x
1
x
n
x
n
−
x
1
,...,
−
that map each system state
s
i
to the node state
t
ij
.
Search WWH ::
Custom Search