ATPG for Cancer Therapy - Logic Synthesis for Genetic Diseases - page 73

Chapter 5
ATPG for Cancer Therapy

Cancer and other gene related diseases are usually caused by a failure in the signaling
pathway between genes and cells. These failures can occur in different areas of the
gene regulatory network, but can be abstracted as faults in the regulatory function.
For effective cancer treatment, it is imperative to identify faults and select appro-
priate drugs to treat the faults. In this chapter, we present an extensible Max-SAT
based automatic test pattern generation (ATPG) algorithm for cancer therapy [ 1 ],
[ 2 ]. This ATPG algorithm is based on Boolean Satisfiability (SAT) and utilizes the
stuck-at fault model for representing signaling faults. A weighted partial Max-SAT
formulation is used to enable efficient selection of the most effective drug(s).
Several usage cases are presented for fault identification and drug selection.
These cases include the identification of testable faults, optimal drug selection for
single/multiple known faults, and optimal drug selection for overall fault coverage.
Experimental results on growth factor (GF) signaling pathways demonstrate that
our algorithm is flexible, and can yield an exact solution for each feature in much
less than 1 s. 1

5.1 Background

In all organisms, cell function is supported by the interaction of genes and protein
products, forming an interconnected network called the gene regulatory network
(GRN) [ 3 ]. The interaction or communication between genes and cells is highly com-
plex and multivariate. Cancer and gene-related diseases are often the result of a failure
in the signaling, leading to incorrect gene regulation and its associated functions.
The modeling of the gene interactions is thus highly important for understanding
the mechanism and therapy of cancer. Because genes are observed to have a switch-
like expression (active (expressed) or inactive (repressed)), the Boolean network

1 Part of the data reported in this chapter is reprinted with permission from “Efficient Cancer Therapy
using Boolean Networks and Max-SAT-based ATPG” by Pey-Chang Kent Lin, Sunil P. Khatri. IEEE
International Workshop on Genomic Signal Processing and Statistics (GENSIPS) 2011 , Dec. 2011,
pp. 97-90, Copyright 2011 by IEEE.