Logic Techniques Applied to Genomics
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.