\chapter{The Genex I Program}

The following represents a brief description of the {\sc Genex I}
program.  Readers interested in further implementational details are
referred to the appendix.

\section{Overview}

The {\sc Genex I} program represented an operon as consisting of a promoter,
operator, possible leader sequence, structural genes, and an
associated regulatory gene.  The operator was assumed to be located
spatially between the promoter and the structural genes.  The promoter
included the CAP site in glucose-sensitive operons, but other positive
regulators were assumed to function at the operator.  The regulatory
gene was represented as having a promoter but no other control sites.
There was no constraint on the location of the regulatory gene relative
to the operon.

To use the {\sc Genex I} program, the user entered the name of the
operon to be examined, the nature of the protein for which it
codes--whether it is involved in an anabolic or catabolic pathway, and
what its substrates or end products are--and whether or not the genes
of the operon are expressed.  Additional information could also be
given to assist the program in determining a model for the operon's
behavior.  This included the nucleotide sequence of all or part of the
operon, the existence and location of any mutations in the operon or
its regulatory gene, and the phenotype of any known diploids.

The more information that was given to the program initially, the more
precise its solution.  Told only that the operon's genes are or are not
expressed, it would suggest every model consistent with the protein
product of the operon.  Given the nucleotide sequence of the operon,
it could give a solution as detailed as pinpointing the exact nucleotide
mutation which was the likely cause of the behavior.

The ``expert knowledge'' in the {\sc Genex I} program consisted of
the information in the preceding chapter encoded as 62 heuristic rules
relating observed phenomena to possible causes.  In each rule, the
information was highly compiled and generally incorporated  several
inference steps.

The rules were grouped into procedures based on their categorization
as being relative to transcriptional or translational control
mechanisms, and further subdivided according to the location of the
mutation which might be affecting the expression of the operon.
Within these procedures, the information was further divided into two
types: factors which enhance gene expression and factors which inhibit
it.  The procedures, which resembled decision trees, were then
systematically applied to the operon given as input.

The flow of control in the original {\sc Genex I} program generally
followed  the protocol for determining the control of gene expression
in bacterial operons shown in figure 4.1.
\begin{figure}
\centering
\setlength{\unitlength}{.25in}
\begin{picture}(29,29)
\put(0,27){\framebox(6,2){\parbox{1.5in}{\centering \small is the operon's \\
product made?}}}
\put(3,27){\vector(0,-1){2}}
\put(3,26){\makebox(2,1){yes}}
\put(6,28){\vector(1,0){3}}
\put(6,28){\makebox(2,1){no}}
\put(9,27){\framebox(6,2){\parbox{1.5in}{\centering \small is the proper \\
transcript made?}}}
\put(12,27){\vector(0,-1){9}}
\put(12,25){\makebox(2,1){no}}
\put(15,28){\vector(1,0){3}}
\put(15,28){\makebox(2,1){yes}}
\put(18,27){\framebox(6,2){\parbox{1.5in}{\centering \small is the gene \\ 
translated?}}}
\put(0,23){\framebox(6,2){\parbox{1.5in}{\centering \small decreased amount?}}}
\put(3,23){\vector(0,-1){2}}
\put(3,22){\makebox(2,1){no}}
\put(6,24){\line(1,0){2}}
\put(8,24){\vector(0,1){4}}
\put(6,24){\makebox(2,1){yes}}
\put(0,19){\framebox(6,2){\parbox{1.5in}{\centering \small inducer absent?\\
corepressor present?}}}
\put(3,19){\vector(0,-1){2}}
\put(3,18){\makebox(2,1){yes}}
\put(6,20){\line(1,0){1.5}}
\put(7.5,20){\line(0,-1){11}}
\put(7.5,9){\vector(-1,0){4.5}}
\put(6,20){\makebox(2,1){no}}
\put(0,11){\framebox(6,6){\parbox{1.5in}{\centering \small regulatory gene \\ 
mutation? \\
operator mutation? \\
mutation eliminating \\ need for positive \\ control element? \\ (yes = QED)}}}
\put(3,11){\vector(0,-1){3}}
\put(3,10){\makebox(2,1){no}}
\put(0,5){\framebox(6,3){\parbox{1.5in}{\centering \small increased affinity
for \\ ribosomes?\\
superpromoter?}}}
\put(21,27){\vector(0,-1){2}}
\put(16,26){\line(1,0){5}}
\put(16,26){\makebox(2,1){yes}}
\put(16,26){\line(0,-1){5}}
\put(16,21){\vector(1,0){2}}
\put(21,25){\makebox(2,1){no}}
\put(18,24){\framebox(6,1){\centering \small stability of message}}
\put(18,19){\framebox(6,4){\parbox{1.5in}{\centering \small nonsense or \\
missense mutation?\\
post-translational \\ control?}}}
\put(9,16){\framebox(6,2){\parbox{1.5in}{\centering \small is transcription
\\initiated?}}}
\put(15,17){\vector(1,0){3}}
\put(18,16){\framebox(6,2){\parbox{1.5in}{\centering \small is attenuation off?
\\ (no = QED)}}}
\put(21,16){\vector(0,-1){1}}
\put(21.5,15){\makebox(1,1){yes}}
\put(18,12){\framebox(6,3){\parbox{1.5in}{\centering \small cleavage? \\
message degraded \\ as it's made?\\ unstable transcript?}}}
\put(12,16){\vector(0,-1){5}}
\put(12,14){\makebox(2,1){no}}
\put(9,9){\framebox(6,2){\parbox{1.5in}{\centering \small misfunction at RNA
\\ pol recognition site?}}}
\put(15,10){\vector(1,0){3}}
\put(15,10){\makebox(2,1){yes}}
\put(18,8){\framebox(6,3){\parbox{1.5in}{\centering \small mutation? \\ site 
blocked? \\ distant effect on \\ secondary structure?}}}
\put(12,9){\vector(0,-1){2}}
\put(12,8){\makebox(2,1){no}}
\put(9,5){\framebox(6,2){\parbox{1.5in}{\centering \small misfunction at \\
promoter?}}}
\put(15,6){\vector(1,0){3}}
\put(15,6){\makebox(2,1){yes}}
\put(18,4.5){\framebox(6,3){\parbox{1.5in}{\centering \small mutation? \\ distant effect on \\ secondary structure?}}}
\put(12,5){\vector(0,-1){1}}
\put(12,4){\makebox(2,1){no}}
\put(9,1){\framebox(6,3){\parbox{1.5in}{\centering \small inducer present? \\
corepressor absent? \\ (no = QED)}}}
\put(15,3){\vector(1,0){3}}
\put(15,3){\makebox(2,1){yes}}
\put(18,1){\framebox(6,3){\parbox{1.5in}{\centering \small operator mutation? 
\\ regulatory gene \\ mutation?}}}
\end{picture}
\caption{Protocol for modeling gene control in bacterial
operons.}
\end{figure}

If there was a possibility that some aspect of the regulatory gene was
causing the observed behavior, the program would call itself
recursively using the regulatory gene as its input, since it too can
be subject to transcriptional and translational control (such as
promoter or structural mutations).  The program would ignore
procedures that do not apply to regulatory genes, for instance, those
that look for positive and negative control structures \footnote{Since, as
mentioned above, regulatory genes are not thought to be themselves
regulated by repressors or activators.}.

{\sc Genex I} could terminate execution under two circumstances:
when it had generated all possible solutions, or when it had found a
solution that was an extremely likely cause of the observed behavior.

The primary data structure in the {\sc Genex I} program was a
two-element list whose first element was an atom representing the
operon being examined and whose second element represented the product
of the operon (i.e. the protein coded for by the structural genes).
Properties of the operon and gene product were attached to the
property list of the corresponding element.  This representation was
chosen purely for the sake of expediency.

As an example of the way that the original system represented and used
the domain information, consider the regulatory protein.  {\sc Genex I} used
the rule that anabolic processes are repressible and catabolic
processes are inducible to determine the interaction of small
molecules with the regulatory protein.  There were also procedures to
determine if any of the substances known to be present are a potential
inducer (or corepressor) of the operon.  Finally, there were rules
which explained the relationship between the presence or absence of an
inducer (or corepressor) and protein synthesis, shown in the {\tt
FIND-INDUCERS} procedure in figure 4.2.
\begin{figure}
\begin{verbatim}
(defun find-inducers (x)
  (cond ((null (get (car x) 'inducer)) 
         ;we have to figure out the inducer
         (let ((inducer 
                (do ((possible-inducers things-present 
                                        (cdr possible-inducers)))
                    ((null possible-inducers) nil)
                    (cond ((inducer? x (car possible-inducers))
                           (return (car possible-inducers)))))))
           (cond ((and (null inducer)(not protein-made?)) 
           ;it seems that nothing present is the inducer, so...
                  (format t
                   "~%~A possibly inactive due to missing inducer" 
                          (car x)))
                 (t (format t
                            "~%assuming ~A is inducer for ~A~@
                             ~A is active in presence of ~A"
                            inducer (car x) (car x) inducer)))))
;if we get to here, we were told what the gene's inducer is.
;first check if it's present, and if not, 
;then maybe that explains bug.
        (t (cond ((member (get (car x) 'inducer) things-present)
                  (format t "~%~A is active in presence of ~A"
                          (car x) (get (car x) 'inducer)))
                 ((not protein-made?)
                  (format t 
                   "~%~A inactive due to missing inducer ~A"
                          (car x) (get (car x) 'inducer))
                          (*throw 'exit 'qed))))))
\end{verbatim}
\caption{the {\tt FIND-INDUCERS} procedure.}
\end{figure}
As can be seen in the above program, {\sc Genex I} could analyze the
operon and determine whether or not it would be active, but the
consequences that it reported were ``canned.''  This is because
{\sc Genex I}'s rules contained highly-compiled knowledge and the
program had no access to the lower-level mechanisms that justify the
information contained in the rules.

The {\sc Genex I} program was tested on three examples taken from the
final exam of an MIT undergraduate genetics course.  These were all
the questions appropriate for the program (dealing with not more than
one mutation, and not requiring calculation of quantities.  See
discussion below).  {\sc Genex I} was {\it not} designed and tested using
these questions as a guide.  In order to present a true picture of the
capabilities of the program, it was evaluated using questions that
were not available at the time the program was designed and
implemented.  A representative question from the exam and the
program's output are shown below.  (Comments on the example are given in 
italics.)
\vspace{.25in}

{\bf
The enzyme {\it uncine synthetase} (USase) of
the hypothetical bacterium {\it Altacoccus profundii} synthesizes the
essential amino acid uncine.  When no uncine is present in the growth
medium USase is made at a high level, allowing cells to grow.  When
uncine is added to the medium, however, very little USase is made (the
cells use the added uncine to grow).}

{\it This information can be represented to the program as follows.
Let the operon be called {\bf unc}.  The gene coding for USase is
labeled {\bf unc-gene}.}

\begin{verbatim}
unc 
(UNC-GENE USASE)
\end{verbatim}

{\it This is what we the program has been told about USase:}

\begin{verbatim}
(plist 'usase)
(PURPOSE SYNTHESIS END-PRODUCT UNCINE INV-PROPORTIONAL-TO (UNCINE))
\end{verbatim}

{\tt THINGS-PRESENT} {\it is a list of the substances present in
the medium at the time of interest.  The substances besides uncine are
acting as red herrings.}

\begin{verbatim}
things-present 
(LACTOSE TRYP UNCINE ARABINOSE)


(initialize unc)
is UNC-GENE product made? NO
\end{verbatim}

{\it The gene product, USase, is not made in the presence of uncine.}

\begin{verbatim}

is there a mutation in UNC-GENE? (yes, no, unknown) NO
is there an unlinked mutation? (yes, no, unknown) NO
was diploid constructed? NO
DONE 
\end{verbatim}
{\it The program now has all the information stated in the above
paragraph.}

{\bf
Outline briefly, at the molecular level, two
simple but different models that would explain why very little USASE
is made in the presence of uncine.  In each, be sure to indicate the
role of uncine.}

\begin{verbatim}

(genex unc)
assuming no misfunction at UNC-GENE promoter
is UNC-GENE a regulatory gene? NO
assuming UNC-GENE can be repressed
assuming UNC-GENE repressor is repressible
assuming UNCINE is corepressor for UNC-GENE--
        UNC-GENE is inactive in presence of UNCINE
\end{verbatim}

{\it {\sc Genex I} has found one model for the behavior of the {\bf unc}
operon--that it is negatively controlled and corepressed by uncine.
It used a rule which states that genes which code for biosynthetic
pathways are repressible by their end-products.}

\begin{verbatim}

assuming no misfunction at UNC-GENE operator
checking positive control of UNC-GENE
assuming UNCINE is corepressor for UNC-GENE--
        UNC-GENE is inactive in presence of UNCINE
done checking positive control of UNC-GENE
\end{verbatim}

{\it A second model has been found, that {\bf unc} is positively
controlled and the activator is inactivated by the presence of the
co-repressor, uncine.}

\begin{verbatim}

message possibly attenuated due to presence of UNCINE
NIL
\end{verbatim}

{\it In fact, {\sc Genex I} has found a third model for the behavior of {\bf
unc}, that uncine acts as an attenuator on the transcription of the
{\bf unc} genes.  It used a rule which states that genes which code
for the synthesis of amino acids can be attenuated.}

{\bf
Certain mutants of {\it A. profundii} make USase
even in the presence of added uncine (which can be shown to penetrate
the cell as effectively as in the wild type).  In each of your models
from part A, indicate two different ways mutants could allow this to
happen.}

{\it In order to answer this question, {\sc Genex I} is run twice.  The
first time, it is told to assume that there is a mutation in the
operon itself, the second time it is told to assume that the mutation
is in the regulatory gene.}

{\it First examine a potential mutation in the operon:}

\begin{verbatim}

(initialize unc)
is UNC-GENE product made? YES
in what amount?  (increased or decreased) INCREASED
is there a mutation in UNC-GENE? (yes, no, unknown) YES
Where is it located? (promoter operator xc-region linked) LINKED
was diploid constructed? NO
DONE 

(genex unc)
is UNC-GENE a regulatory gene? NO
assuming UNC-GENE can be repressed
assuming UNC-GENE repressor is repressible
assuming UNCINE is corepressor for UNC-GENE--
        UNC-GENE is inactive in presence of UNCINE
possible structural mutation in UNC-GENE operator allowing activator 
        to bind despite presence of corepressor
\end{verbatim}

{\it This is one way our second model could be mutated which would
explain the observed behavior.}

\begin{verbatim}

mutation possibly affecting attenuator
NIL 
\end{verbatim}

{\it {\sc Genex I} also suggests that the mutation could be affecting the
attenuator region, consistent with its third model of how the {\bf unc}
operon is regulated.

Now for the regulatory gene mutation:}

\begin{verbatim}

(initialize unc)
is UNC-GENE product made? YES
in what amount?  (increased or decreased) INCREASED
is there a mutation in UNC-GENE? (yes, no, unknown) NO
is there an unlinked mutation? (yes, no, unknown) YES
was diploid constructed? NO
DONE 

(genex unc)
assuming no misfunction at UNC-GENE promoter
assuming UNC-GENE can be repressed
assuming UNCINE is corepressor for UNC-GENE--
        UNC-GENE is inactive in presence of UNCINE
examining UNC-GENE-REGULATORY-GENE
Is the regulatory protein made? (yes, no, unknown) UNKNOWN
assume UNC-GENE-REGULATORY-PROTEIN is not made
\end{verbatim}

{\it First assume that it's a nonsense mutation.}

\begin{verbatim}

operon cannot be switched off without UNC-GENE-REGULATORY-PROTEIN
\end{verbatim}

{\it If the repressor is not made, the operon cannot be turned off.
This is one mutation that may occur in our first model.}

\begin{verbatim}

now assuming UNC-GENE-REGULATORY-PROTEIN is made
possible structural mutation in UNC-GENE-REGULATORY-PROTEIN
        eliminating ability to bind corepressor
possible structural mutation in UNC-GENE-REGULATORY-PROTEIN which 
        prevents it from binding to operator
done examining UNC-GENE-REGULATORY-GENE
\end{verbatim}

{\it These are two more possible mutations which would alter the
behavior of our first model in a way which would explain the
observations.}

\begin{verbatim}

assuming no misfunction at UNC-GENE operator
checking positive control of UNC-GENE
assuming UNCINE is corepressor for UNC-GENE--
        UNC-GENE is inactive in presence of UNCINE
examining UNC-GENE-REGULATORY-GENE
possible structural mutation in UNC-GENE-REGULATORY-PROTEIN 
        eliminating ability to bind corepressor
\end{verbatim}

{\it This is a second mutation that could occur in our second model
which would explain the observed behavior.}

\begin{verbatim}

done examining UNC-GENE-REGULATORY-GENE
done checking positive control of UNC-GENE
NIL
\end{verbatim}

In its limited domain, {\sc Genex I} performed very
well.  The goal of the system was to give every probable model for the
behavior of the operon (within the limits of its knowledge).  For all
the problems on which it was tested, it gave all the correct models,
sometimes more than the problem called for, and did not give any
incorrect models.  In this sense, the program was considered a
success.

\section{Limitations of the Genex I Program}

{\sc Genex I} has certain limitations which
prevent it from answering all types of questions even within the
domain of bacterial operons.

The program is modeled on the investigative course of human experts.
However, this results in a poorly modularized program, because the
domain knowledge is incorporated into the reasoning mechanism.  This
makes it difficult to extend or modify the domain knowledge, because
it would require rewriting all the procedures dealing with the new
or changed information.  This problem is relatively simple to correct,
by rewriting the rules and inference engine as separate entities.

A more critical problem that {\sc Genex I} has is that its knowledge
base consists solely of empirical associations and compiled
knowledge, and the system's reasoning process consists of matching the
right rules to the observed phenomena.  Because the system solves a
problem by matching the current situation against a set of
predetermined situations, the set of rules must {\it anticipate}
situations that may arise.  In a small domain, it may be possible to
enumerate all possible situations and write a rule to handle each
one.\footnote{This technique was used in Puff (Kunz, 1978).}
In a large domain, it may not be feasible to predict every possible
occurrence.  If the current situation does not match any rule, then the
system fails.

Take as an example the observation that {\sc Genex I} could only
handle problems involving one mutation in the operon.  Many real-world
problems in molecular genetics require reasoning about the combined
effect of multiple mutations on gene expression..  In order to expand
the system to consider multiple mutations, it would have been
necessary to add a large number of rules with complicated antecedents,
each rule corresponding to each possible combination of mutation
location, gene product production, and control model.\footnote{To see
why the number of rules necessary would be so large, consider that if
{\sc Genex I} had been given all the information necessary to solve
problems involving two mutations in compiled form, this still would
not have allowed it to solve problems involving three mutations.}
These rules would no longer resemble the simple "rules of thumb" that
the expert uses and on which the program was based.

Another limitation of the way that the domain knowledge is represented
in the original system is that it is implicit in the rules, and thus
inaccessible.  For example, the original version of {\sc Genex} can
only give ``canned'' explanations of its conclusions.  The
information that {\sc Genex} has is already compiled into
high-level rules.  {\sc Genex} has a rule which states
that deleting the promoter causes a decrease in transcription of the
operon.  If given a problem that included a promoter mutation and a
decrease in gene product, {\sc Genex} applies this rule and
suggests that the promoter mutation caused the decrease in gene
product.  However, {\sc Genex} has no knowledge of the mechanism
which makes this true, i.e. that the promoter is where the RNA
polymerase binds, if the promoter is deleted the polymerase cannot
bind, and if the polymerase cannot bind the operon cannot be
transcribed.  The details of how lower-level mechanisms combine to
produce the more complex observed behavior was not included because
the program could solve the problems without them.  As a result of
this, the system cannot be extended to explain its conclusions.
The best it can do is to state which rules it applies.  The
rules that {\sc Genex} uses are not wrong, but each is a
high-level compilation of a more detailed collection of knowledge
about objects and their interactions.  This lower-level information
is not available to {\sc Genex} for use in justifying its
conclusions.

Furthermore, because the knowledge is contained implicitly, it is
inflexible.  One piece of knowledge may be contained in any number of
rules in the system, so in order to change that knowledge it must be
changed in every rule that uses it.  Highly compiled rules do not
permit simple, local changes which are then reflected system-wide.
For example, the original version of {\sc Genex} has an inflexible
model of the operon.  It is constrained to think of the operon as
having exactly one promoter, operator, and regulatory gene.  It cannot
be presented with a problem where, for instance, a second promoter had
been inserted into the operon.  In operons having more than one
structural gene, {\sc Genex} is constrained to deal with the genes as
a group---it cannot reason about them as separate entities.  The
reason for this rigid model is that {\sc Genex} does not actually have
or use any structure which represents ``the operon.''  Instead, the
representation is implicit in the procedures which reason about the
operon, and therefore changing the way that {\sc Genex} models the
operon requires changing most of the rules in the program.  A variable
model of the operon, which could change with each invocation of the
program, is impossible in the initial version of the program.

A final problem with the empirical ``rules of thumb'' used by the original {\sc
Genex I} program is that they often contain implicit preconditions.  For
instance, the heuristic that states that ``deleting the operator
results in increased expression of the operon'' contains the implicit
precondition ``all other things being equal.''  If all other things
are {\it not} equal, the validity of the heuristic's conclusion is
unknown \footnote{This is the difference between an abstraction and a
heuristic.  An abstracted rule {\it X} $ \longrightarrow $ {\it Y}
holds for any {\it x} which can be abstracted to {\it X} via the abstraction
relation.  The same is not necessarily true for a heuristic.}.
Implicit preconditions make it difficult, if not impossible, to
determine the conditions under which a heuristic can be applied
correctly.  However, explicitly stating every precondition may be
tedious -- consider having to explicitly encode ``all other things
being equal'' in a system with hundreds of components.

{\sc Genex} has no mechanisms for reasoning about spatial relationships, for
instance, those between the structural genes, the promoter, and the
operator.  There are types of problems where the ability to do this
kind of reasoning is important.  For example, there is a phenomenon
called the {\it polarity effect} whereby genes closer to the promoter
are transcribed with higher efficiency.  The ability to do spatial
reasoning is essential for dealing with information about tertiary
structure.  

{\sc Genex I} makes no distinction between an increase in the amount
of protein and constitutive production of the protein (or between a
decrease in the amount of protein made vs. no protein made at all).
This is because {\sc Genex I} has no concept of quantity.  For many
problems, relative quantities of substances are not significant to the
solution of the problem.  However, it would be useful to be able to
deal with gross level changes.  Also, the distinction between
increased and constitutive production (and between decreased
production and none at all) is important and should be expressible.

