Biomedical Engineering Reference
In-Depth Information
Table 3.1
Example 3-Gene
state transition table
Current state
Next state
a
b
c
a
b
c
0
0
0
1
1
0
0
0
1
1
1
0
0
1
0
0
0
1
0
1
1
1
0
1
1
0
0
1
0
1
1
0
1
1
0
1
1
1
0
0
0
1
1
1
1
1
0
1
3.3.1.2
Constraining SAT Solution Space Using Gene Expression States
As is, the circuit of the previous step describes all possible BNs. To constrain the
solution space to obtain one or a subset of BNs for our GRN, we constrain the circuit
to make it satisfy gene expression states. A gene expression state is a measurement of
the dynamic behavior of the GRN, containing information of the gene state at a time
point
t
, as well as at the next time point
t
1. In the state transition table (an example
is shown in Table
3.1
), a gene expression state is a row of the table, and consists
of a pair of states (
S
1
,
S
2
). This row mandates that if the GRN is in state
S
1
at time
t
, it will transition to state
S
2
at time
t
+
1. Note that Table
3.1
shows all possible
minterms or observations of the GRN. However in practice, we may only have a
limited number of gene expression states (observations). Our method determines a
SAT solution that satisfies the predictor set and the gene expression observations.
The overall goal of our approach is, for each gene, to select a function which
matches all gene expression states (rows of the state transition table). In our approach,
if there are
M
rows, we duplicate the circuit
M
times. Each circuit copy is assigned
a minterm, with the gene values fixed according to the row. The select signals for all
the MUXes for any gene
x
i
are connected together in each of the
M
copies of the
circuit, to ensure that the same function for
x
i
is selected in all the
M
circuit copies.
The solution is an assignment of the variables of the MUXes such that the CNF is
satisfied. The assignment of the variables corresponding to the MUX select lines for
any gene
x
i
denote which function was selected for the gene
x
i
and hence specifies
the logic function of gene
x
i
. THe assignment of
all
MUX select lines (for all genes)
yields the GRN. Depending on the gene expression states used, there may be more
than one valid solution, in which case performing an All-SAT will generate
all
possible BNs that match the gene expression observations.
Alternatively, the method can be applied on a single copy of the circuit. Each row
is tested in order, and the circuit is solved using All-SAT to find all results that satisfy
the
i
th
row. The conjunction of these results and the CNF
S
form a new circuit
S
i
which is used when the (
i
+
1)
th
row is processed. This computation was found to
require significantly more runtime than the circuit duplication method, so it was not
used.
+
