Biomedical Engineering Reference
In-Depth Information
sequence can be stopped. For a BN, the number of frames
m
can be bounded by the
sum of the number of steps it takes to reach an attractor cycle and the maximum
length of the attractor cycles for all combinations of drugs under consideration. In
the worst case, the number of frames required would equal to the number of possible
states, which is 2
n
+
d
for a BN with
n
target genes and
d
drugs.
5.6
Chapter Summary
In this chapter, we have presented an efficient and extensible SAT-based ATPG
methodology for cancer therapy. We approach this problem by representing the BN
and cancer as a logic circuit stuck-at fault model. This circuit, along with the testing
conditions, is converted into a CNF. The CNF is then augmented with output and
drug vectors weights and solved using a weighted partial Max-SAT solver for four
different usage cases: (1) single stuck-at fault identification, (2) fault rectification
with fewest drugs, (3) fault rectification with minimum drug cost, and (4) determining
therapy with fewest drugs and best coverage. We demonstrate these methods on the
growth factor signaling pathway, and have presented results that are applicable to
cancer therapy. While the GF network example in the case study is a combinational
network, our algorithm can easily be extended to address sequential networks, like
those found in transcriptional GRNs, by simply unrolling the sequential circuit in
time and applying the same methods. Furthermore, all nets, inputs, outputs, and
drugs can be assigned weights, which can be made variable, allowing the user to
fine-tune the network or design therapies for any number of test situations.
References
1. Lin, P. K., Khatri, S.P.: Efficient cancer therapy using Boolean networks and Max-SAT-
based ATPG. Genomic Signal Processing and Statistics (GENSIPS), 2011 IEEE International
Workshop on. IEEE, 87-90 (2011)
2. Lin, P. K., Khatri, S.: Application of Max-SAT-based ATPG to optimal cancer therapy design.
BMC Genomics
13
(6) S5 (2012)
3. Guelzim N. et al.: Topological and causal structure of the yeast transcriptional regulatory
network, Nat. Genet. (
31
), 60-63 (2002)
4. Kauffman, S.A.: Metabolic stability and epigenesis in randomly constructed genetic nets. J.
Theor. Biol.
22
(3), 437-467 (1969)
5. Layek R., Datta, A., Bittner, M., Dougherty, E.R.: Cancer therapy design based on pathway
logic. Bioinformatics.
27
(4), 548-555 (2011)
6. Jacob, F., Monod, J., Genetic regulatory mechanisms in the synthesis of proteins. J. Mol. Biol.
3
(3), 318-356 (1961)
7. Larrabee, T., Efficient Generation of Test Patterns Using Boolean Difference. Proc. of the Intl.
Test Conf. 795-801 (1989)
8. Stephan, P., Brayton, R.K., Sangiovanni-Vincentelli, A.L.: Combinational test generation using
satisfiability, Comput.-Aided Des. Integr. Circuits Syst. IEEE Trans.
15
(9) 1167-1176, Sept.
(1996)
