Biomedical Engineering Reference
In-Depth Information
For the first implication
z
→
x
+
y
(Eq.
3.1
), we write the corresponding clause.
(
z
+
x
+
y
)
(3.3)
This clause is already in CNF format, so no further transformation is needed.
For the second implication
x
+
y
→
z
(Eq.
3.2
), we again write the corresponding
clause.
(
x
+
y
+
z
)
(3.4)
The clause (Eq.
3.4
) is not in CNF format, so we use transformations such as
DeMorgan's laws to convert it into CNF.
(
x y
+
z
)
(3.5)
z
) (3.6)
The CNF formula
G
i
for the 2-input OR gate is the conjunction of the above clauses
(Eqs.
3.3
,
3.6
) and is written as:
(
x
+
z
)(
y
+
G
i
=
(
z
+
x
+
y
)
·
(
x
+
z
)
·
(
y
+
z
)
(3.7)
The CNF for the entire circuit
S
obtained from steps 1) and 2) above is constructed
by forming the conjunction of all CNF formulas for all the gates in the circuit. If
there are
n
gates in the circuit, then the CNF formula for the entire circuit is written
as shown in Eq.
3.8
.
n
S
=
G
i
(3.8)
i
=
1
A gene of a GRN is analogous to a logic function. The predictor of a gene is analogous
to the support of the logic function. In general, the total number of possible functions
is 2
2
N
for a gene with
N
inputs. However, we consider only those functions that have
a
true support
of
N
inputs. The true support of a function are the inputs that a function
is actually dependent on. In our method, we require that a function must depend on
all inputs specified by the predictor.
For example, con
si
der a gene
x
with 2 inputs
y
and
z
, and we are considering the
function
x
=
+
yz
. Since this function can be simplified to
x
=
y
, it depends on
only one input, (and its true support is not
x
,
y
) and will be disregarded in our method.
The function
x
yz
yz
does depend on both inputs, and thus would be considered in
our method. The total number of functions
F
N
with true support of
N
inputs can be
calculated as shown in Eq.
3.9
.
=
F
N
−
1
−
F
N
−
2
−
N
0
F
0
N
N
2
2
N
F
N
=
−
...
−
(3.9)
−
−
N
1
N
2
Where
2
2
0
2 (3.10)
The final CNF consists of all possible functions (with selection MUX) for all the
genes in the GRN.
F
0
=
=
