Biomedical Engineering Reference
In-Depth Information
Chapter 3
Determining Gene Function in Boolean
Networks using SAT
There are many instances where the circuit topology of the GRN is known, but
the logic function of each node in this topology is not. In addition, a number
N
of
measurements on the gene expression states of the GRN are given or are known.
Using this information, this chapter will derive SAT based algorithms which yield
the logic of every node in the GRN so that the
N
gene expression measurements and
topology are satisfied. If
N
is too small, then a multitude of GRNs may satisfy the
observed behavior, yielding a reduced certainty in the final result due to lack of data.
We will also study the behavior of the number of satisfying GRNs with respect to
the number of observations
N
.
1
3.1
Background
In the cell, genes interact and communicate using a complex interconnected network
called the gene regulatory network (GRN) [
1
]. The GRN and gene expression states
defines cell function and behavior. An accurate model of the GRN is necessary
for understanding cell behavior, for learning how genetic diseases arise and for
developing intervention strategies to treat such diseases.
In many situations, biologists can produce gene predictor sets or connectivity
graphs, denoting which genes act upon or regulate each other. Chapter 2 describes a
SAT based approach for predictor set inference. While gene predictor sets or connec-
tivity graphs show how genes are interconnected, they do not provide any information
about the regulating function of the genes. Predictor sets are generally useful, but
without information about the regulating function, they cannot be used to simulate
the dynamic interaction between genes which is crucial for the intervention and con-
trol of the GRN. Thus, a major goal for the genomics and the medical field is to
determine the regulating function of the genes in the GRN.
1
Part of the data reported in this chapter is reprinted with permission from “Determining Gene
Function in Boolean Networks using Boolean Satisfiability” by Pey-Chang Kent Lin, Sunil P.
Khatri.
IEEE International Workshop on Genomic Signal Processing and Statistics (GENSIPS)
2012
, Dec. 2012, pp. 1-4, Copyright 2012 by IEEE
