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
Search WWH ::




Custom Search