Biomedical Engineering Reference
In-Depth Information
The key contributions of this chapter are:
We develop a Boolean Satisfiability based approach to realize the gene predictor
set from attractor state data.
We modify an existing SAT-solver (MiniSat [
9
]) for efficient all-SAT computation,
and further optimize the decision engine of MiniSat for improved predictor set
inference.
Using the gene expression data from a melanoma study [
3
], we apply our SAT-
based algorithm and present the predictor set, including the predictor for the
cancer gene WNT5a.
Our approach can be used to find the predictor set for any gene related disease,
provided attractor state data is available. The predictor set information obtained
from our algorithm can be used by biologists to fine tune their gene expression
experiments.
2.2
Previous Work
In the context of predictor set inference, [
10
], [
11
] use dynamic Bayesian networks
and probabilistic Boolean networks (PBNs). The GRN is then inferred from this
data, using methods traditionally based on probabilistic transition models [
7
], [
8
].
The method proposed considers gene prediction using multinomial probit regression
with Bayesian variable selection. Genes are selected which satisfy multiple regres-
sion equations, of which the strongest genes are used to construct the predictor set.
The target gene is predicted based on the strongest genes, using the coefficient of
determination to measure predictor accuracy.
Another method proposed by [
12
] also assumes a PBN model. A partial state
transition table is constructed based on available attractor state data. From this state
transition table, predictors with 3 or less regulating genes are selected for each target
gene. All unknown values in the table are randomly set. The Boolean network is
simulated for several iterations using different starting states, observing whether
the states eventually transition to an attractor cycle. If the simulation successfully
transitions to an attractor cycle, the selected predictors are considered as a valid
predictor set. This process is repeated, to build a collection of Boolean Networks
which are combined to form a Probabilistic Boolean Network (PBN).
Our larger goal is to find a small number of
deterministic
GRNs, rather than a
PBN. The key reason for this is that combining BNs into PBNs admits new behavior,
which may be incorrect. For example, the BNs in Fig.
2.1
a and b yield a PBN in
Fig.
2.1
which admits a new behavior
S
0
→
S
1
→
S
0
→
S
1
. Towards this, we need
0.5
S0
S1
S0
S1
S0
S1
a
b
c
0.5
Fig. 2.1
Combination of BNs into PBN
