Biomedical Engineering Reference
In-Depth Information
model [
4
] has become popular for representing the GRN. In the Boolean network,
the genes and biochemical pathways are represented as logic functions, much like
logic gates in an integrated circuit (IC). This network can be temporarily modified to
model the effect of signaling failures and defects in the GRN, which are represented
as faulty lines in the circuit [
5
].
The issue of faults in circuits is well understood in electronic testing. For ex-
ample, in chip manufacturing, circuits are typically tested to check that the IC is
defect free before shipment to vendors. Manufacturing defects manifest themselves
as logical faults modeled as lines (wires) stuck-at '1' or '0'. Using this
stuck-at fault
model
, automatic test pattern generation (ATPG) algorithms determine a set of tests
(assignment of values on the inputs of the circuit) to test for stuck-at faults in the
circuit.
In this chapter, we use the stuck-at fault model for the GRN [
5
] and employ ATPG
techniques to determine a drug vector (set of drugs) to rectify the fault. The ATPG
algorithm is developed as a Boolean satisfiability (SAT) based method, where the
Boolean network is transformed into a conjunctive normal form (CNF) expression
and solved for satisfiability to find the drug vector. In therapy, the goal is to treat
the cancer (represented by one or more faults) using drugs with the least negative
impact on the patient, ideally by prescribing the fewest number of drugs necessary
(to avoid unnecessary side-effects and cost). The SAT method is further extended by
assigning weights to the circuit outputs and drug vectors, and solved with a weighted
partial Max-SAT approach to find the optimal set of drugs to fix or rectify the fault.
The key contributions of this chapter are:
In contrast to previous approaches [
5
] which performs an explicit search, we
develop an implicit SAT-based ATPG approach to model and identify detectable
faults (single and multiple) in a Boolean network.
By assigning weights to model output and drug vectors, we use a weighted partial
Max-SAT formulation to determine the optimum selection of drugs to rectify a
specific fault.
Our approach can be trivially extended to scalably handle multiple faults.
We utilize the above techniques for drug therapy to select the minimum set of
drugs to provide the best coverage across all single/multiple faults.
5.2
Previous Work
In the actual GRN, the gene expression or protein concentration is continuous. How-
ever, in our method, the Boolean network (BN) [
4
] is chosen as preferred network
for modeling the GRN. There are several reasons for this choice. First, it has been
observed that many genes exhibit a switch-like ON/OFF activity in terms of their
expression [
6
]. Also, a discrete model like the BN is relatively simple and easy to
analyze and simulate compared to a continuous model. And lastly, there are many
logic synthesis and test algorithms already developed in circuit design and testing
that can be adapted and applied to the Boolean network.
