Biomedical Engineering Reference
In-Depth Information
The following discussion introduces several genomics research ideas for explo-
ration using logic synthesis.
1. A key issue in genomics is handling data with error and noise, particularly in
measurement of gene expression. One topic is to analyze the GRN behavior
which can lead to measurement of incorrect gene expression. Using the ATPG
method discussed in Chap. 5, one could quantify the sensitivity of a GRN to
N
“faults” in the GRN (where faults represent incorrectly measured data).
2. Another topic of value is to use logical techniques to quantify the degree of
“similarity” of two GRNs (or subsets of the GRN), using functional equivalence
techniques [
1
]. Such a method may be useful to identify subsets of GRN between
two organisms with the same cellular or genetic function, or to compare GRNs
of patients to determine effective treatment strategies.
3. Model checking [
2
], a technique to verify the temporal behavior of logical sys-
tems, can be utilized to query the temporal properties of a GRN in a very efficient
manner. Given the GRN, and given a state that it is currently in, questions such
as “Is there a way to reach state
X
in
k
steps “or” Is there a way in which state
Y
is visited infinitely often in the future” can be answered automatically by model
checking systems. This approach can be useful in cancer therapy to ask questions
about a patients prognosis or determine the effect of drugs on the GRN.
4. Also in the context of uncertainty modeling, probabilistic Boolean Networks
(PBNs) [
3
] are used to model the GRN. Suppose there are
k
BNs which match
some observed data. Then each edge in the PBN has a probability, which is the
average of the corresponding
k
edges in the BNs. This can result in the allowing
of behaviors that are not present in any of the
k
BNs. To avert this issue, Non-
Deterministic Finite State Machine (NDFSM) [
4
] models of the GRN can be
developed. Many techniques from the field of automata theory can be brought to
bear to develop such an NDFSM.
5. Another possible research direction is to perform ATPG on the state transition
graph rather than the logic circuit as we have shown in Chap. 5. Such methods
are used in sequential ATPG and present an a method for drug selection given a
GRN with feedback or sequential properties.
6. As discussed in Chap. 4, gene expression values are initially measured as con-
tinuous values. Gene expressions values can then be thresholded to yield binary
values for use in Boolean logic synthesis algorithms. While Chap. 4 explores using
continuous expression values with Zhelgakin functions, other alternate logic rep-
resentations such as asynchronous logic and multi-valued logic may be valuable
in the context of genomics as well to more accurately represent gene expression
values and regulation.
7. The majority of our algorithms utilizes SAT, and as a consequence, the run time of
our approaches is dominated by the SAT solver. Although our algorithms utilize
efficient SAT solvers, these solvers are optimized for general or circuit based SAT
instances. A possible research topic is understanding and improving SAT solving
for GRN problems. One interesting observation from our SAT implementation
in Chap. 2 and 3, is that the predictors or functions of each gene are encoded in
