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: