Biomedical Engineering Reference
In-Depth Information
Chapter 2
Predictor Set Inference using SAT
The inference of gene predictors in the gene regulatory network (GRN) has become
an important research area in the genomics and medical disciplines. Accurate predic-
tors are necessary for constructing the GRN model and to enable targeted biological
experiments that attempt to validate or control the regulation process. In this chapter,
we implement a SAT-based algorithm to determine the gene predictor set from steady
state gene expression data (attractor states). Using the attractor states as input, the
states are ordered into attractor cycles. For each attractor cycle ordering, all possible
predictors are enumerated and a conjunctive normal form (CNF) expression is gen-
erated which encodes these predictors and their biological constraints. Each CNF is
solved using a SAT solver to find candidate predictor sets. Statistical analysis of the
resulting predictor sets selects the most likely predictor set of the GRN, correspond-
ing to the attractor data. We demonstrate our algorithm [
1
], [
2
] on attractor state data
from a melanoma study [
3
] and present our predictor set results.
1
2.1
Background
With increasing availability of gene expression data, the focus in computational
biology has shifted to the understanding of gene regulation and its inter-relation with
the biological system. The use of genome information has given rise to the possibility
of “personalized medicine”—targeted and specific disease prevention and treatment
based on individual gene information [
4
], [
5
]. The urgent applications to cancer
and gene-related diseases calls for the genomics field to significantly improve the
algorithms used for accurate inference of the gene regulatory network (GRN).
In an organism, the genome is a highly complex control system wherein proteins
and RNA produced by genes and their products interact with and regulate the activity
of other genes [
6
]. A
predictor
for a target gene
g
i
is the collection of genes directly
1
Part of the data reported in this chapter is reprinted with permission from “Inference of Gene
Predictor Set Using Boolean Satisfiability” by Pey-Chang Kent Lin, Sunil P. Khatri.
IEEE Inter-
national Workshop on Genomic Signal Processing and Statistics (GENSIPS) 2010
, Nov. 2010,
pp. 1-4, Copyright 2010 by IEEE
