Logic Techniques Applied to Genomics

 

The progression of cancer (or any genetically rooted disease) goes through a sequence of non-cancerous genetic states, which terminate in a cycle of cancerous genetic states (also referred to as an attractor cycle). Biologists have identified these attractor states in cancerous patients through laboratory experiments. These sequences of states can be modeled as a Finite State Machine (FSM), and a slew of design and analysis techniques in the area of Logic Synthesis can be used to understand and model the problem. However, unlike an FSM design problem in VLSI, the FSM for cancer is not known, and has to be determined. In VLSI design, we first design the FSM, and then reason about its reachable states, terminal (attractor) cycles etc. In the context of cancer, the FSM (also called the gene regulatory network or GRN) has to be derived from observed data corresponding to the genetic states that are visited in an attractor cycle.

 

We have developed a powerful Boolean Satisfiability (SAT) based approach to infer the genes that regulate a particular gene in the GRN Using this information, we are now working on techniques to develop the FSM (GRN) in a cancerous patient, using GPUs to accelerate the computation. Previous approaches to this problem have taken a brute force approach, and produced a “probabilistic” GRN as their output. However, the generation of probabilistic edges inadvertently allows spurious transitions. As a result, our approach models the GRN as a set of Boolean relations, rather than a single probabilistic GRN.

We have also developed techniques to find the least cost drug regime for cancer, which yields the “best” cure. This is based on a partial max-SAT framework, using concepts from VLSI testing. Our formulation is general, implicit and extremely fast.

Other ongoing work in this space is to model the GRN using “analog” gates, and also to find the logic of each of the nodes in the GRN, given its structure.

Publications, patents and artefacts:

• “Application of Logic Synthesis to the Understanding and Cure of Genetic Diseases”. Lin, Khatri. Invited paper for special session on non-traditional applications of CAD algorithms, IEEE/ACM Design Automation Conference (DAC) 2012. To appear. In this paper, we will discuss our work on predictor inference, GRN inference, and targeted cancer drug delivery.
• “Efficient Cancer Therapy using Boolean Networks and Max-SAT-based ATPG”, Lin, Khatri. 2010 IEEE International Workshop on Genomic Signal Processing and Statistics (GENSIPS). Dec 2011, San Antonio, TX. This paper reports our work on a partial max-SAT based approach to find minimum number (or cost) of drugs that can force the GRN into a state which is closest (in a Hamming distance sense) to a normally functioning individual’s GRN.
• “Inference of Gene Predictor Set using Boolean Satisfiability”, Lin, Khatri. 2010 IEEE International Workshop on Genomic Signal Processing and Statistics (GENSIPS). Nov 2010, Cold Spring Harbor, NY. pp 1-4. In this paper, we utilize logic synthesis ideas to find all compatible sets of genes (predictors) that can influence the behavior of a particular gene in the state machine. From this information, we perform a back-end statistical analysis to provide the most likely predictor for each gene in the GRN
• “Using Boolean Networks and Max-SAT-based ATPG for Efficient Cancer Therapy”. Lin, Khatri. Invited submission for special issue of BMC Genomics. This paper is an extended version of our GENSIPS-11 paper.
• “Logic Synthesis applied to Genetic Disease Modeling and Cure”, Lin, Khatri. Contract for this brief research monograph submitted to Springer Publishers. The brief is expected to be published in 2012.