Biomedical Engineering Reference
In-Depth Information
the example attractor cycle orderings. To find all valid predictors of a gene, each
next state column is checked against all combinations of the current (present) state
columns. For example, let us explore gene
g
2
and
g
3
as a predictor for gene
g
1
.For
gene
g
1
, the next state bit is
y
1
, while for gene
g
2
and
g
3
, the current (present) state
bits are
x
2
and
x
3
. In the first two rows of Table
2.1
,
<x
2
,
x
3
>
=
10. However, in
row 1,
y
1
=
0, which forms a contradiction (since the same
input cannot result in different outputs). Therefore, gene
g
1
cannot be predicted by
genes
g
2
and
g
3
.
Now, consider genes
g
1
and
g
3
as a predictor for gene
g
1
. There is no contradiction,
and the combination is logically valid. Thus one possible predictor for gene
g
1
is
f
1
=
{
1, while in row 2,
y
1
=
. All valid predictors with
P
(user-defined) or less inputs are exhaustively
searched and recorded for CNF formulation (which is done in the next step). In our
example, gene
g
1
has 2 possible predictors
x
1
,
x
3
}
which we label
v
1
,
v
2
{
x
1
,
x
3
}
,
{
x
1
,
x
2
,
x
3
}
respectively. We assume that a gene cannot self-regulate, so
{
x
1
}
by itself is not a
valid predictor.
2.4.2
SAT Formulation and GRN Constraints
After all predictors are found for each gene, we generate the SAT formula which
encodes logically valid predictor sets. The
j
th
predictor for gene
i
is assigned a
variable
v
j
. Gene
g
1
in our example has two predictor variables
v
1
≡{
x
1
,
x
3
}
,
v
2
≡
{
x
1
,
x
2
,
x
3
}
. Gene
g
2
and
g
3
will have their own corresponding predictor variables
v
1
≡{
x
1
,
x
2
}
,
v
2
≡{
x
1
,
x
3
}
,
v
3
≡{
x
2
,
x
3
}
,
v
4
≡{
x
1
,
x
2
,
x
3
}
and
v
1
≡{
x
1
,
x
3
}
,
v
2
≡
,
v
3
≡{
{
respectively. There are three constraints that we incorporate
while constructing the CNF that encodes valid predictor sets. The conjunction of these
constraints forms our final CNF.
x
2
,
x
3
}
x
1
,
x
2
,
x
3
}
1. The first constraint (
S
1
) is that all genes in the GRN must have a predictor. In other
words, we assume that all genes are highly correlated and are "participating" in
the GRN. For gene
i
, all of its associated predictor variables are written in a single
clause
c
i
(
v
i
1
+···+
v
j
)
=
In our example, for
g
1
,
c
1
=
(
v
1
+
v
2
). For
g
2
and
g
3
,wehave
c
2
=
(
v
1
+
v
2
+
v
3
+
v
3
) respectively.
To satisfy any
c
i
clause, at least one predictor in the clause must be chosen. To
ensure that at least one predictor is chosen for
all
genes, we write the conjunction
of all
c
i
v
4
) and
c
3
=
(
v
1
+
v
2
+
clauses as
S
1
(Eq.
2.1
).
c
1
·
c
2
·
c
3
S
1
=
(2.1)
2. The second constraint (
S
2
) specifies that for each gene, exactly one predictor
is chosen. The assumption is that a gene cannot have multiple predictors. To