\chapter{The Genex II System}

The performance of the {\sc Genex I} was probably
as good as it could be considering the simple design of the system.
There were a few additions that  would have been easy to implement and
that would have fit in with the format of the program.  For instance,
it would have been useful to have a procedure which, given a DNA
sequence, located any hairpin loops \footnote{In fact, most commercially
available DNA sequencing programs include such a procedure, which is
why one was not included.}.  The program could then have been
given new rules that depended on knowing the secondary structure of
the DNA (such as those that might have been written for the conditions
of transcription termination).  {\sc Genex I} could also have used a procedure
to determine if a sequence was AT- or GC-rich.  Again, it could
then have been given new rules which used this information.

These additions could have fine-tuned the performance of {\sc Genex I},
but would not have significantly increased its reasoning power.  Any
substantial improvements in the capabilities of the system required a
major redesign of the program control structure and knowledge
representation format.  The improved version would have a model for
each object and mechanism involved in operon control.  The models
would include such information as what the different parts of the
object were, the role that each part plays in the functioning of the
operon, how the parts interact, and how lower-level mechanisms
combine into higher-level behavior.  When presented with a problem,
the system would pass the information through the models in a form of
simulation to reach its conclusions (rather than doing a match between
the observed phenomena and the knowledge in the system, as the
original program did).  The advantage of this model-driven approach is
that the system would have more ``understanding'' of the processes with
which it deals, because more of the details would be captured by the
program (rather than being compiled out as rules by the system
designer, as was done in the original program).  The system would have
access to the details, so it could generate more detailed solutions,
and have the capability to explain the reasoning behind its
conclusions.  Finally, since the models would no longer be
incorporated into the reasoning mechanism, the system would be more
easily extensible.  These significant improvements were implemented in
the {\sc Genex II} program.

{\sc Genex II} was designed using the performance
criteria described above as its goal.  The domain knowledge was
separated from the reasoning mechanisms, the rules used in the
original system were rewritten to capture the underlying mechanistic
details, and a primitive explanation capability was added.  {\sc
Genex II} is currently implemented in Prolog \footnote{For an
introduction to the Prolog language, see Clocksin and Mellish, 1981.}.

\section{Representation of Objects in Genex II}

Since the domain of the system is molecular genetics, the objects that
are manipulated by the system are those that exist inside a cell.
Some of the objects that are represented are shown in figure 5.1.
\begin{figure}
\begin{verbatim}
        operon
        promoter
        operator
        terminator
        binding-site
        regulatory-site
        gene
        structural-gene
        regulatory-gene
        nucleotide
        nucleotide-sequence
        codon
        DNA
        RNA
        amino-acid
        amino-acid-sequence
        protein
        structural-protein
        regulatory-protein
        sugar
        repressor
        activator
        inducer
        corepressor
        enzyme
        polymerase

\end{verbatim}
\caption{The objects represented in {\sc Genex II}}
\end{figure}

The representation of objects is independent of the representation of
cell operations and the reasoning mechanism of the program.  The
representation of an object includes properties of the object, a
description of its parts (which are themselves described) and its
relationship with its environment.  Part of the definition of a
repressible regulatory protein is given in figure 5.2.  For readers
unfamiliar with Prolog, a detailed explanation of the description of a
regulatory protein follows.  

\begin{figure} 
\begin{verbatim}
protein(X) :- reg-protein(X).
reg-protein(X) :- activator(Operon,X).
reg-protein(X) :- repressor(Operon,X).  
reg-protein(X) :- product(Reg-gene,X),
                reg-gene(Reg-gene).
part-of(R, operator-binding-site(R)) :-
                reg-protein(R), normal(R).
part-of(R, operator-binding-site(R)) :-
                reg-protein(R),
                assuming(part-of(R, operator-binding-site(R))).
part-of(R, small-mol-binding-site(R)) :-
                reg-protein(R), normal(R).
part-of(R, small-mol-binding-site(R)) :-
                reg-protein(R),
                assuming(part-of(R, small-mol-binding-site(R))).
active(Reg_protein) :- reg_protein(Reg_protein),
                active_smmol_conform(Reg_protein).
active(Reg_protein)d :- reg_protein(Reg_protein),
                assuming(active_smmol_conform(Reg_protein)).
active-smmol-conform(R) :- repressor(Op,R),
                normal(R),
                repressible(Op),
                corepressor(Op,C),
                bindable(C,small-mol-binding-site(R)).
\end{verbatim}
\caption{Part of the description of a regulatory protein}
\end{figure}

The description of the regulatory protein is made up of eleven {\it
clauses}.  The clause is made up of a {\it head} and a {\it body}.
The head consists of a single {\it goal} and the body consists of a
sequence of zero or more goals \footnote{In this example, no clause
has an empty body.  A clause with no body is called a {\it unit
clause} and is written in the form {\it P.} where {\it P} is the head
goal, and is interpreted to mean ``{\it P} is true.''}.  In the first
clause shown in figure 5.2, ``protein(X)'' is the head and
``reg-protein(X)'' is the body.  This can be interpreted to mean ``to
satisfy the goal {\it protein(X)}, satisfy the goal {\it
reg-protein(X)},'' or, in English, ``any X is a protein if X is a
reg-protein.''  Where there is more than one goal with the same head
clause, Prolog will attempt to satisfy each one in turn, until one
succeeds, or they all fail.  Variables in Prolog are denoted by names
beginning with a capital letter.  The scope of the variable is the
clause in which it appears, so the variable X in the first clause is
independent of the variable named X in the next three clauses.

The second and third clauses state that the activator  or repressor of
an operon is a regulatory protein, i.e. that there are two types of
regulatory protein.  The fourth clause defines a regulatory protein
to be the product of a regulatory gene.

The next four clauses define the important parts of a regulatory
protein: its operator binding site and its small molecule binding
site.  {\sc Genex II} assumes that if the regulatory gene is not mutated, then
the product regulatory protein is normal and has all its parts.  If
the regulatory gene is mutated, then the goal is satisfied if we are
currently assuming \footnote{Assumptions are discussed in section
5.3.1.}  that its parts are intact.

Finally there are clauses for determining whether a regulatory protein
is active, that is, able to bind to the operator.  A normal regulatory protein
is active if it interacts correctly with the associated small molecule
({\sc Genex II} calls this state {\tt active-smmol-conform}).  In the case of a
mutated regulatory protein, the goal is satisfied if we are currently
assuming that {\tt active-smmol-conform} is true.  {\sc Genex II} contains twelve
rules\footnote{The use of the word {\it rule} in this chapter should
be interpreted as referring to a Prolog clause, and should not be
confused with the rules of a ``rule-based system.''}
for determining whether a regulatory protein is in an active
conformation.  Because of space considerations, only one is shown in
figure 5.2 \footnote{Interested readers can consult Appendix B, which
contains a complete listing of the {\sc Genex II} code.}.  This rule states
that a normal repressor is in the active conformation if the
corepressor of the operon is able to bind to the small molecule
binding site of the repressor.

In the {\sc Genex I} program, an operon was predefined, and there was
only an implicit representation of the relationship between its parts,
and its interaction with its environment.  In {\sc Genex II}, this is
all explicit.  For instance, the {\it lac} operon would be represented
as shown in figure 5.3 \footnote{The user does not have to enter all
this information by hand.  There are rules for deriving some of the
relationships based on given information.}.
\begin{figure}
\begin{verbatim}

operon(lac-operon).

part-of(lac-operon, lac-operon-promoter).
promoter(lac-operon-promoter).

part-of(lac-operon, lac-operon-operator).
operator(lac-operon-operator).

part-of(lac-operon, lac-operon-reg-gene).
reg-gene(lac-operon-reg-gene).

part-of(lac-operon, b-galactosidase-gene).
struct-gene(lac-operon, b-galactosidase-gene).

part-of(lac-operon, b-galactoside-permease-gene).
struct-gene(lac-operon, b-galactoside-permease-gene).

part-of(lac-operon, b-galactoside-transacetylase-gene).
struct-gene(lac-operon, b-galactoside-transacetylase-gene).

part-of(P,overlap-region(P,O)) :- promoter(P),operator(O).
part-of(O,overlap-region(P,O)) :- operator(O),promoter(P).
next-to(lac-operon-promoter,b-galactosidase-gene).
next-to(b-galactosidase-gene,b-galactoside-permease-gene).
next-to(b-galactoside-permease-gene,
        b-galactoside-transacetylase-gene).

product(b-galactosidase-gene, b-galactosidase).
enzyme(b-galactosidase).
substrate(b-galactosidase, lactose).
purpose(b-galactosidase, catabolic-proc).

...etc
\end{verbatim}
\caption{Representation  of the  {\it lac} operon in {\sc Genex II}.}
\end{figure}

\section{Representation of Operations in Genex II}

The system must also be able to manipulate models of the operations
that can be performed on the objects.  These operations correspond to
the processes that go on inside the cell.  The operations that the
system can use to model the processes of a cell are {\it express},
{\it replicate}, {\it transcribe}, {\it translate}, {\it bind}, and
{\it break}.  A future system might include the operations insert,
react, cut, ligate, polymerize, add-functional-group,
remove-functional-group, replace-functional-group, denature, renature,
and unwind.  The addition of these operations would be very simple.

{\sc Genex II} simulates an operation by proving that all the preconditions
of that operation are satisfied.  If they are, it asserts that any
postconditions  of the operation are true.

{\sc Genex II}'s representation of the bind operation shown in figure  5.4.  
\begin{figure}
\begin{verbatim}
bind(Mol, Site) :- binding-site(Mol, Site), 
                   complementary-conform(Mol,Site),
                   \+ bound(X,Site),
                   free-to-bind(Mol), 
                   assert(bound(Mol,Site)).
\end{verbatim}
\caption{The BIND operation.}
\end{figure}
This operation involves two objects, the molecule being
bound, and the site to which it is being bound.  The operation has
several preconditions:

First, the site must be the binding site for that molecule.  In
general, the binding site is an abstract label corresponding to a
specific region of the operon, for instance, the binding site of the
regulatory protein is the operator.  {\sc Genex II} also has rules to determine
whether a nucleotide sequence can be a binding site for a molecule.
For example, if the molecule is RNA polymerase, it can check to see if
the site has properties which would qualify it as a promoter sequence.

The molecule and the site to which it is being bound must have
complementary conformations.  Since the details of protein folding are
not yet understood, {\sc Genex II} uses the assumption that in their normal
(i.e. non-mutated) state, the molecule and the site have complementary
conformations.  This may be dependent on the presence or absence of a
small molecule for regulatory protein binding operations.  If either of the
objects are mutated, {\sc Genex II} will check to see whether it is currently
assuming that they have complementary conformations, and proceed
accordingly.

Next, the bind operation requires that the site be unoccupied.  In
this respect, {\sc Genex II} uses a simplification of the actual
biological process.  It ignores the possibility that a molecule that
it is attempting to bind has a higher affinity for a site than a
molecule that is already there, in which case the bound molecule would
eventually be displaced.  Since the program works on the {\it micro}
level, reasoning about only one operon through only one cycle of gene
expression, it can avoid dealing with the equilibrium situation by
always binding the molecule with the higher affinity for the site
first.

Finally, the molecule must be free to bind to the site.  This clause
represents the possibility that there is a limited amount of a
molecule present in the system, and there might be none available for
this binding operation.  Other substances are available in essentially
unlimited quantities, and this clause would always be true for bind
operations involving that substance.  This feature is not currently
implemented in {\sc Genex II}, because, as explained in the previous paragraph,
{\sc Genex II} currently only models a single operon at a time, and therefore
does not deal with the quantitative aspects of the problem.

If the preconditions are satisfied, {\sc Genex II} will then assert that  the
molecule is bound to the site, which is  the postcondition  of the
bind operation.


\section{Program Structure}

The {\sc Genex II} program is divided into three parts: a front end, called the
model-maker which gets the information for the current simulation from
the user; an interpreter, which simulates the behavior of the operon
on the input, and the database.

The model-maker asks the user to enter information about the operon,
and constructs the system's physical model of the operon from this
information.  Depending on the input, the model-maker can also decide
that certain variables are {\it uncertain} (discussed below).  The
model-maker sets up all the system variables needed to run the
program.

The second level of the {\sc Genex II} program is the {\sc Genex II}
interpreter.  The clauses that contain the system's domain knowledge
are not run directly by the Prolog interpreter, but rather through
this intermediary, thus allowing more control over the program's
execution.  Explanations are generated by attempting to prove that the
operon is expressed (or not expressed, depending on the observed
behavior), using rules corresponding to the operations that take place
in the cell.  The {\sc Genex II} interpreter decides when a result is
nontrivial and should be reported to the user.  This serves as a
primitive explanation capability in the current system.

The bottom level of the {\sc Genex II} system is the knowledge base
containing facts about prokaryotic operons and rules for reasoning
about their behavior, as described in the previous section.  It
consists of just over 250 clauses, of which about 150 are definitions
(e.g. \verb+protein(x) :- reg_protein(x)+.).  The remaining 100
clauses encode rules for simulating the objects in the domain.

\section{Dealing with Uncertainty}

Certain concepts with which {\sc Genex II} deals are uncertain to some degree,
due to incomplete input given to the system.  For example, suppose
{\sc Genex II} is told that an operon has a promoter mutation, but is not given
the promoter sequence.  Its hypotheses about the effect of that
mutation have a lower degree of certainty than if the sequence had
been given, since in that case, the program could have compared it
with known promoter up- and down-mutations  \footnote{An up-mutation is
one which increases the efficiency of the promoter.  A down-mutation
decreases the efficiency of the promoter.}.  Other rules in {\sc Genex II}'s
knowledge base are what I term {\it ultimately uncertain} from the
system's point of view: that is, the system has no way to determine
the truth or falsity of that rule, due to an incomplete understanding
within the domain itself (rather than incomplete information within
the system).  An example of ultimate uncertainty is whether a mutation
in the small molecule binding site of the regulatory protein will
leave the protein able to assume an active conformation.  The system
can't tell\footnote{nor can any expert: the relationship between sequence
and conformation is by no means completely understood by biologists.}
if this will cause the regulatory protein to be unable to bind the
small molecule and thus never to be able to assume an active conformation,
or if it makes the small molecule unnecessary, causing the regulatory
protein to always be in an active conformation.  However, these two
cases can be distinguished by their effect on the {\it behavior} of the
operon.  This observation led to the introduction of {\it likely
models}, discussed below.

The number of uncertain variables depends on the number and location
of mutations given in the problem statement.  {\sc Genex II} decides that a
given variable is uncertain before running the main program.  If any
part of the operon is mutated, then any rules relating to the
conformation of that part are uncertain, as are any rules relating to
whether or not that part, or any of its subparts, even is part of the
operon (as might be the case in a deletion mutation).  Mutations in
the transcribed portion of the operon are dealt with by the transcribe
and translate operations.  The worst case (in terms of number of
uncertain variables) occurs when it is not even known whether or not
the operon contains a mutation.  Then every uncertain variable for
every part of the operon is activated, as well as an uncertain
variable corresponding to the presumed intactness of each operon part.

{\sc Genex II} initially dealt with ultimately uncertain
clauses by initiating two paths of computation {\it a priori} for each
ultimately uncertain variable: one for possible value {\it true}, and one
for possible value {\it false}.  It then simulated the behavior of the
operon for each possible set of values.  Of course, not every possible
state yielded a simulation result consistent with the observed
behavior of the operon.  Only those which did were proposed as
possible explanations to the user \footnote{{\sc Genex II} does not rank the
potential solutions in order of plausibility.  This requires knowledge
of molecular biology that the author has not yet acquired.}. However,
the total number of computations that would be generated is
exponential in the number of uncertain variables, and for any but the
most trivial problems, this is an unmanageable number.  For instance, a
problem containing a regulatory gene mutation and an operator mutation
would require  seven uncertain variables, and thus 128 distinct
possible states \footnote{While this may not seem like an unmanageable
number, the reader must consider that we are still discussing
relatively simple problems in a simplified problem space.  In a more
general molecular genetics problem solver, an exponential growth rate
would be overwhelming.}.

In order to reduce the number of possible states that the system had
to examine, several new rules were added to the knowledge base.
Before {\sc Genex II} begins to search for possible explanations,
these rules use the {\it observed behavior} of the operon to derive a
{\it likely model} of its behavior.  {\sc Genex II} restricts its
search for explanations to those which fit with the likely model.
This model is one of the following mutually exclusive, collectively
exhaustive possibilities: constitutive, uninducible, or
``regulatable''\footnote{The system does not use these terms in the
literal biological sense.  For instance, an operon which was lacking a
promoter would be considered ``uninducible'' because the gene product
was not made despite the presence or absence of the small molecule.}.
Each of these models requires certain conditions to be true.  For
example, in order for an operon's product to be produced
constitutively, either the regulatory protein cannot bind to the
operator, or the small molecule cannot bind to the regulatory protein.
{\sc Genex II} compares the conditions of the model with the known
structure of the operon and the uncertain variables.  A condition for
a model can be satisfied in one of two ways.  The condition may be
known to be true -- for instance, the user could tell the system that
a regulatory protein does not bind to the operator based on
experimental evidence, or may be provable based on known information.
If a condition is not provable based on known information, but is
possibly true (depending on the state of one or more uncertain
variables) then the system will assume that the uncertain variables
are in the proper state to make the model work.  {\sc Genex II} then
simulates the behavior of the operon under the combination of known
and assumed conditions.

In many cases there are still a number of possible states which must
be checked, since there is more than one assignment of uncertain
variables that will satisfy the model.  The number of states is much
smaller than in the unrestricted case, however.  It is not possible
for the system to overlook a solution which fits the model, since it
will try every state which is consistent with the model, and exactly
one model is consistent with the observed behavior of the operon.  If
it happens that a model exists with which the system is unfamiliar, of
course, the system will be unable to find a correct solution.

The use of likely models reduces the number of possible states that
the program must verify by reducing the number of uncertain variables
generated from the initial problem statement.  Each likely model has a
list of sets associated with it.  Each set is an assignment of
uncertain variables that would make the likely model true.  The number
of possible states which must be examined is halved for each uncertain
variable for which we can assign a value.  The result of using likely
models to control the size of the search space is shown in table 5.1.
\begin{center} 
\begin{table}
\begin{tabular}{cccc}
\hline
{\parbox{1in}{{\small genotype}}} & 
{\parbox{1in}{{\small no. of uncertain variables}}} & 
{\parbox{1in}{{\small no. of possible states}}} & 
{\parbox{1in}{{\small no. of states generated}}} \\ 
\hline
$i^c,o^c$ & 7 & 128 & 32 \\ 
$i^c$ & 5 & 32 & 8 \\ 
$i^s$ & 5 & 32 & 8 \\ 
\end{tabular} 
\caption{Reduction in possible states using likely models.} 
\end{table} 
\end{center} 
For the problems tested the use of likely models reduces the number of
states that must be searched by 75 per cent.

The flow of control and information in the {\sc Genex II} is
summarized in figure 5.5.
\begin{figure} 
\centering
\setlength{\unitlength}{0.25in}
\begin{picture}(30,10)
\put(0,3){\makebox(3,3){\parbox{.75in}{\small observed \\ behavior}}}
\put(3,4.5){\vector(1,0){1}}
\put(4,3){\framebox(3,3){\parbox{.75in}{\centering model \\ maker}}}
\put(7,4.5){\vector(1,0){4}}
\put(7.5,4){\makebox(3,2){\parbox{.75in}{\footnotesize conditions of}}} 
\put(7.5,3){\makebox(3,2){\parbox{.75in}{\footnotesize likely model}}}
\put(11,3){\framebox(3,3){ }}
\put(12.5,7.5){\vector(0,-1){1.5}}
\put(11,7){\makebox(3,3){\parbox{.75in}{\small known \\ structure}}}
\put(12.5,2){\vector(0,1){1}}
\put(11,0){\makebox(3,2){\parbox{.75in}{\small uncertain \\ variables}}}
\put(14,4.5){\vector(1,0){4}}
\put(14.5,4){\makebox(3,2){\footnotesize assumptions}}
\put(18,3){\framebox(3,3){simulate}}
\put(18,7){\makebox(3,3){\parbox{.75in}{\small known \\ structure}}}
\put(19.5,7.5){\vector(0,-1){1.5}}
\put(19.5,2){\vector(0,1){1}}
\put(21,4.5){\vector(1,0){1}}
\put(22,3){\framebox(3,3){compare}}
\put(23.5,7.5){\vector(0,-1){1.5}}
\put(22,7){\makebox(3,3){\parbox{.75in}{\small observed \\ behavior}}}
\put(23.5,3){\line(0,-1){1}}
\put(19.5,2){\line(1,0){4}}
\put(19.5,0){\makebox(5,2){\parbox{1.25in}{\small try next state}}}
\end{picture}
\caption{A flowchart for the {\sc Genex II} system.} 
\end{figure} 
I believe that this is the same way in which molecular biologists
approach problems.  A hypothesis is proposed based on previous
problems which had similar behavior (corresponding to the model-making
phase of the program).  The biologist attempts to fit the details of
the current problem to the hypothesis.  The program does the same by
making a set of assumptions from the uncertain variables.  Finally,
the biologist attempts to verify the hypothesis.  {\sc Genex II} also
attempts to verify the hypothesis, by simulating the behavior of the
operon, and checking if it agrees with the observed behavior.

In some of the possible states, certain variables may be unimportant,
i.e. the result of the simulation is the same whether they are true or
false.  For example, given an unexpressed operon with a mutation in
the promoter and a mutation in the structural genes, the latter
mutation may be unimportant if we assume that the promoter is unable
to bind RNA polymerase.  If the program were able to recognize this,
it could generate a more informative explanation.

{\sc Genex II}'s model-maker is similar to heuristic DENDRAL's Planner.
DENDRAL had a Structure Generator which could generate all chemically
plausible isomers, given a chemical formula, and a Predictor which
determined if a candidate structure's mass spectrum fit the given
data.  Because of the enormous size of the problem space, the
designers wanted to reduce the number of candidate structures
generated.  They achieved this by requiring the generator to generate
only those classes of structures which met some criteria obtained from
the problem data.  The Planner consists of a group of {\it specialists},
one for each chemical family.  Each specialist determines the class of
allowable candidates within its family by using a collection of
``special facts and special-purpose heuristics'' \footnote{Feigenbaum, p.
175.} applied to the given data.  {\sc Genex II}'s four likely models
correspond to DENDRAL's specialists.

\section{Generating Explanations and Justifications}

The {\sc Genex II} interpreter recognizes certain operations and circumstances
as important.  When important operations are simulated, or important
circumstances are noted, the system reports this to the user.  The
designation of operations as important is done by the system, and can
change with each invocation of the program.

A rule is said to be important if it depends on an uncertain variable,
or if it is non-trivial.  All unit clauses are trivial (this inhibits
the system from continually informing the user that it has determined
that the input operon is indeed an operon, for instance).  A rule is
also trivial if it relates to a model of the operon that is not the
one that the system has assumed is true.  For instance, the system will
not inform the user of any attempts to prove that the system has some
inducer X if the model of the system is repressible.

In addition, the procedures {\small EXPRESSED}, {\small INITIATED},
{\small ATTENUATED}, {\small TRANSCRIBE}, {\small TRANSLATE}, {\small
TERMINATE}, and {\small PROCESS} are permanently designated as being
important.  These seven procedures serve as milestones during
execution.

{\sc Genex II} currently explains its reasoning to the user by informing the
user of important results during the course of execution.  This is
essentially a trace of the program, and is meaningful simply because
all rules have been given mnenonic names.  Since the system now has a
finely detailed model of operons and operon behavior, this trace is
informative without resorting to the use of canned text, and has the
potential to be upgraded, using techniques such as those described by
Swartout (1981).

At the present time, {\sc Genex II} cannot respond to requests for
justification from the user; however, the design of the system permits
this as a possible future modification.

\section{Types of Problems that Genex II Can Solve}

{\sc Genex II} can solve all the problems
that were solved by the original program.  The new encoding of the
domain knowledge allows the system to represent more objects and
relationships, so the system is more powerful than it was before.

It was difficult to expand {\sc Genex I} to reason about
problems involving more than one mutation in the operon, because it
would have required adding a complicated conditional statement
corresponding to each combination of mutation sites, gene expression,
and control model in the system.  {\sc Genex II} can now reason about
the combined effect of multiple mutations on gene expression.  The
model-maker computes the set of all possible states corresponding to
the mutation sites, etc., and then simulates the operon on each of the
possible states.  This allows the system to be easily expanded, since
the set of possible states is dynamic: it is created by the system
when the program is invoked, rather than being written into the
program.

{\sc Genex II} now has an explicit model of the operon, which allows the system
to represent non-standard operons.  This allows it to solve another
large class of problems.  For instance, it can now model an operon
which has two promoters.  {\sc Genex II} can also model diploids, \footnote{a
operon in which some parts are represented twice.} allowing the system
to determine, for instance, whether a mutation is {\it trans}-dominant or {\it
trans}-recessive.

The system still has no concept of quantity.  {\sc Genex II} cannot solve any
problem relating to equilibrium states, enzyme assays, or any abstract
type of quantitative measurement, such as {\it less than} or {\it a small
amount.}  It was decided at the inception of this project by the
molecular biology expert that the more interesting genetics research
questions involved micro-level reasoning rather than
reasoning about quantities, and the system reflects that bias.

The system currently takes in a description of behavior and structure,
and explains the behavior of the operon.  With a minor modification to
the system, it could also take in a structure and predict the
behavior.

\section{``Understanding'' Molecular Genetics}

This section contains two examples which demonstrate the increased
capabilities of the system.  The first example deals with a double
mutant containing mutations in both the regulatory gene and the
operator.  This example is again taken from the MIT undergraduate
genetics exam \footnote{For this example, the program generated 32
possible states, two of which were shown to be consistent with the model.
The explanation for only one state is shown here, due to space 
considerations.  The output of the program has been edited to
omit redundancy in the proofs.  Places where editing has occurred and
comments inserted are marked by the symbol ``$ \rangle \rangle $.''}.

\vspace{.25in}

{\bf
{\it Bacterium pedantia}  produces a protein,
Sporulin, that makes other bacteria sporulate...Sporulin synthesis is
inducible by chalk.  In the absence of chalk a repressor produced by
gene {\it spoR} prevents  expression of the Sporulin structural gene
spoS.

Haploids carrying two mutations can be made in {\it B. pedantia} by
recombination.  Most haploid double mutants that carry both a
constitutive {\it spoR} and a constitutive {\it spoO} mutation are
constitutive, as expected.  However, one particular double --- the
haploid carrying {\it spoR}43 and {\it spoO}97 --- is anomalous: it
produces Sporulin {\it only} when chalk is {\it absent}.  {\it spoR}43
is known to be missense.  Explain briefly how the repressor and
operator are functioning in the double mutant.}

{\it The program is started up and the information stated in the
problem is given as input.}

\begin{verbatim}
| ?- genex.
end every answer with a period followed by a CR!

solution mode (terse or verbose): verbose.
name of operon: spo.
spo structural genes: enter one at a time, 5prime - 3prime order
 -- end with ``done.''
structural gene:
|: spos.
what is product of spos
|: sporulin.
what is purpose of sporulin: (synthesis, digestion, or other)
|: other.
structural gene:
|: done.
enter sequence of spo or [ ]
|: [ ].
are there any mutations in spo or reg-gene (yes, no, or unknown) ?
|: yes.
mutation site known (yes or no) ?
|: yes.
mutation in promoter (yes or no) ?
|: no.
mutation in reg-gene (yes or no) ?
|: yes.
mutation in operator (yes or no) ?
|: yes.
mutation in struc-genes (yes or no) ?
|: no.
is spo gene product made?
|: no.
enter any other information available 
e.g. proportional-to(X,Y), inv-proportional-to(X,Y),
present(Substance), etc.
-- end with ``done.''
|: present(chalk).
|: inv-rel(chalk,sporulin).
|: done.
\end{verbatim}
{\it The program now lists the assumptions that it is making based on
the input.  ``smbs'' stands for ``small molecule binding site.''}
\begin{verbatim}

assuming: mutated(operator_specific(spo_operator))
assuming: mutated(overlap_region(spo_promoter,spo_operator))
assuming: active_smmol_conform(spo_reg_protein)
assuming: mutated(spo_reg_protein)
assuming: part_of(spo_reg_protein,smbs(spo_reg_protein))
assuming: complementary_conform(_1145,smbs(spo_reg_protein))
assuming: smmol(_1858)
assuming: reg_protein(spo_reg_protein)
assuming: operator(spo_operator)
assuming: complementary_conform(_1858,smbs(spo_reg_protein))
assuming: complementary_conform(spo_reg_protein,
                                overlap_region(spo_promoter,spo_operator))

\end{verbatim} {\it The following trace is printed out by the program.
Each time a new goal is encountered, the program prints out the rule
or rules it uses to try to prove that goal.} 
\begin{verbatim} 
goal: expressed(spo)
  attempting to prove: 
  [operon(spo),
   initiated(spo),
   \+attenuated(spo),
   xcribe(get_gene_seq(spo),_1721),
   xlate(_1721,_1722)]
   goal: initiated(spo)
     attempting to prove: 
     [operon(spo),
      part_of(spo,_1772),
      promoter(_1772),
      bindable(rna_pol,_1772)]
\end{verbatim}
{\it Expression initiates when RNA polymerase binds to the promoter.
The system first checks to see if polymerase is  already bound to the
promoter, otherwise it checks  if RNA polymerase is able to bind.}
\begin{verbatim}
     goal: bindable(rna_pol,spo_promoter)
       attempting to prove: 
       [bound(rna_pol,spo_promoter)]
       goal: bound(rna_pol,spo_promoter)
         attempting to prove: 
         [promoter(spo_promoter),
          part_of(spo_promoter,_1951),
          bound(rna_pol,_1951)]
         goal: bound(rna_pol,overlap_region(spo_promoter,
                                            spo_operator))
         >>failed goal: bound(rna_pol,
                              overlap_region(spo_promoter,
                                             spo_operator))
       >>failed goal: bound(rna_pol,spo_promoter)
     goal: bindable(rna_pol,spo_promoter)
       attempting to prove: 
       [bind(rna_pol,spo_promoter)]
       goal: bind(rna_pol,spo_promoter)
         attempting to prove: 
         [binding_site(rna_pol,spo_promoter),
          complementary_conform(rna_pol,spo_promoter),
          \+bound(_1951,spo_promoter),
          asserta(genex_clause(bound(rna_pol,spo_promoter)))]
          goal: binding_site(rna_pol,spo_promoter)
            attempting to prove: 
            [promoter(spo_promoter)]
          proved: binding_site(rna_pol,spo_promoter)
          goal: complementary_conform(rna_pol,spo_promoter)
            attempting to prove: 
            [operon(_2039),
             assoc(_2039,_2040),
             product(_2040,spo_promoter),
             smmol(_2039,rna_pol),
             present(rna_pol),
             normal(spo_promoter)]
\end{verbatim}
{\it This rule is inapplicable because the spo promoter is not the
product of any operon.}
\begin{verbatim}
          goal: complementary_conform(rna_pol,spo_promoter)
            attempting to prove: 
              [promoter(spo_promoter),
               \+bad_rna_conform(spo_promoter)] 
\end{verbatim} 

{\it ``Bad rna conform'' is {\sc Genex}'s term for a promoter not in the
proper conformation to bind RNA polymerase.  An active regulatory
protein bound to the operator prevents the polymerase from binding to
the promoter, in negative-control systems.  {\sc Genex} will try to
determine if the regulatory protein can bind to the operator.}
\begin{verbatim}
              goal: normal(spo_promoter)
                attempting to prove: 
                [\+mutated(spo_promoter),
                 \+assuming(mutated(spo_promoter))]
              proved: normal(spo_promoter)
              goal: bindable
                    (spo_reg_protein,
                     overlap_region(spo_promoter,spo_operator))
                attempting to prove: 
                [bound(spo_reg_protein,
                       overlap_region(spo_promoter,spo_operator))]
                >>failed goal: bound(spo_reg_protein,
                                   overlap_region(spo_promoter,
                                                  spo_operator))
              goal: bindable
                    (spo_reg_protein,
                     overlap_region(spo_promoter,spo_operator))
                attempting to prove: 
                [bind(spo_reg_protein,
                      overlap_region(spo_promoter,spo_operator))]
                goal: bind(spo_reg_protein,
                           overlap_region(spo_promoter,spo_operator))
                  attempting to prove: 
                  [binding_site
                        (spo_reg_protein,
                         overlap_region(spo_promoter,spo_operator)),
                   complementary_conform
                        (spo_reg_protein,
                         overlap_region(spo_promoter,spo_operator)),
                   \+bound(_2718,
                           overlap_region(spo_promoter,spo_operator)),
                   asserta(genex_clause
                        (bound(spo_reg_protein,
                               overlap_region(spo_promoter,
                                              spo_operator))))]
                  goal: binding_site(spo_reg_protein,
                                     overlap_region(spo_promoter,
                                                    spo_operator))
                    attempting to prove: 
                    [reg_protein(spo_reg_protein),
                     operator(spo_operator),
                     promoter(spo_promoter)]
                  proved: binding_site(spo_reg_protein,
                                       overlap_region(spo_promoter,
                                                      spo_operator))
                  goal: complementary_conform
                          (spo_reg_protein,
                           overlap_region(spo_promoter,spo_operator))
\end{verbatim} {\it Based on its likely model of the operon, the
system is already assuming that the regulatory protein and the overlap
region have complementary conformations.  In order to see the details
of the solution, we have told the program to ignore its assumption by
telling it to use ``verbose'' mode.  (``Terse'' mode would be used to
quickly verify a solution without having to see all the details).  It
will have to show that the regulatory protein and the overlap region
have complementary conformations using model-based reasoning.}
\begin{verbatim}
                    attempting to prove: 
                    [operator(spo_operator),
                     promoter(spo_promoter),
                     reg_protein(spo_reg_protein),
                     normal(overlap_region(spo_promoter,spo_operator)),
                     active(spo_reg_protein)]
\end{verbatim}
{\it The system assumes that if the overlap region is normal, then the
regulatory protein can bind to it.  This goal fails because the
system is assuming that the overlap region is mutated.}
\begin{verbatim}
                    goal: normal(overlap_region(spo_promoter,
                                                spo_operator))
                      attempting to prove: 
                      [\+mutated(overlap_region(spo_promoter,
                                                spo_operator)),
                       \+assuming(mutated(overlap_region(spo_promoter,
                                                         spo_operator)))]
                      goal: normal(overlap_region(spo_promoter,
                                                  spo_operator))
                        attempting to prove: 
                        [gene(_3432),
                         product(overlap_region
                                  (spo_promoter,spo_operator),_3432),
                         normal(_3432)]
                      >>failed goal:normal(overlap_region(spo_promoter,
                                                          spo_operator))
\end{verbatim}
{\it The system now tries an empirical rule, which states that if the
regulatory protein demonstrates an increased affinity for the
operator, the two must have complementary conformations, without the need
for the small molecule to ``turn on'' the repressor.}
\begin{verbatim}
                  goal: complementary_conform
                            (spo_reg_protein,
                             overlap_region(spo_promoter,spo_operator))
                    attempting to prove: 
                    [reg_protein(spo_reg_protein),
                     promoter(spo_promoter),
                     operator(spo_operator),
                     inc_affinity(spo_reg_protein,spo_operator)]
                    goal: inc_affinity(spo_reg_protein,spo_operator)
                      attempting to prove: 
                      [operon(_3433),
                       part_of(_3433,spo_operator),
                       operator(spo_operator),
                       mutated(spo_operator),
                       assoc(_3433,_3434),
                       reg_gene(_3434),
                       product(_3434,spo_reg_protein),
                       phenotype(_3433,uninducible)]
                      goal: phenotype(spo,uninducible)
                        attempting to prove: 
                        [operon(spo),
                         assoc(spo,_3740),
                         reg_gene(_3740),
                         mutated(_3740),
                         observed_not_expressed(spo),
                         no_influence(_3741,spo),
                         asserta(genex_clause(phenotype
                                                 (spo,uninducible)))]
                        goal: no_influence(_3741,spo)
                          attempting to prove: 
                          [operon(spo),
                           structural_gene(spo,_3945),
                           product(_3945,_3946),
                           \+dir_rel(_3741,_3946),
                           \+inv_rel(_3741,_3946)]
                        >>failed goal: no_influence(_3741,spo)
\end{verbatim}
{\it This goal failed because the system was told that chalk inhibits 
the production of sporulin.}
\begin{verbatim}
                      >>failed goal: phenotype(spo,uninducible)
                      goal: inc_affinity(spo_reg_protein,
                                         spo_operator)
                        attempting to prove: 
                        [operon(_3433),
                         part_of(_3433,spo_operator),
                         operator(spo_operator),
                         mutated(spo_operator),
                         assoc(_3433,_3434),
                         reg_gene(_3434),
                         product(_3434,spo_reg_protein),
                         phenotype(_3433,superrepressed)]
                        goal: phenotype(spo,superrepressed)
                          attempting to prove: 
                          [operon(spo),
                           assoc(spo,_3740),
                           reg_gene(_3740),
                           mutated(_3740),
                           observed_not_expressed(spo),
                           no_influence(_3741,spo),
                           asserta(genex_clause
                                     (phenotype(spo,superrepressed)))]
                          goal: no_influence(_3741,spo)
                          >>failed goal: no_influence(_3741,spo)
                       >>failed goal: phenotype(spo,superrepressed)
                     >>failed goal: inc_affinity(spo_reg_protein,
                                                 spo_operator)
                goal: active(spo_reg_protein)
                  attempting to prove:
                  [reg_protein(Reg_protein),
                   active_smmol_conform(Reg_protein)])
\end{verbatim}
{\it {\sc Genex} now tries several rules in an attempt to show that the
regulatory protein is in an active conformation.  They will fail
because they either depend on a normal regulatory protein, or because
they require a different control model than the one exhibited by SPO
(i.e. repressible).}
\begin{verbatim}
                  goal: active_smmol_conform(spo_reg_protein)
                    attempting to prove: 
                    [repressor(_3823,spo_reg_protein),
                    normal(spo_reg_protein),
                     inducible(_3823),
                     \+inducer(_3823,_3824)]
                    goal: normal(spo_reg_protein)
                      attempting to prove: 
                      [\+mutated(spo_reg_protein),
                      \+assuming(mutated(spo_reg_protein))]
                    goal: normal(spo_reg_protein)
                      attempting to prove: 
                      [gene(_4083),
                       product(spo_reg_protein,_4083),
                       normal(_4083)]
                    >>failed goal: normal(spo_reg_protein)
                  goal: active_smmol_conform(spo_reg_protein)
                    attempting to prove: 
                    [repressor(_3823,spo_reg_protein),
                    normal(spo_reg_protein),
                    inducible(_3823),
                    inducer(_3823,_3824),
                    \+bindable(_3824,smbs(spo_reg_protein))]
                    goal: normal(spo_reg_protein)
                    >>failed goal: normal(spo_reg_protein)
                  goal: active_smmol_conform(spo_reg_protein)
                    attempting to prove: 
                    [repressor(_3823,spo_reg_protein),
                    phenotype(_3823,inducible),
                    \+inducer(_3823,_3824)]
                    goal: phenotype(spo,inducible)
                      attempting to prove: 
                      [operon(spo),
                       structural_gene(spo,_4083),
                       product(_4083,_4084),
                       dir_rel(_4085,_4084),
                       asserta(genex_clause(phenotype(spo,inducible)))]
                    >>failed goal: phenotype(spo,inducible)
                  goal: active_smmol_conform(spo_reg_protein)
                    attempting to prove: 
                    [repressor(_3823,spo_reg_protein),
                     phenotype(_3823,inducible),
                     inducer(_3823,_3824),
                     \+bindable(_3824,smbs(spo_reg_protein))]
                    goal: phenotype(spo,inducible)
                    >>failed goal: phenotype(spo,inducible)
                  goal: active_smmol_conform(spo_reg_protein)
                    attempting to prove: 
                    [repressor(_3823,spo_reg_protein),
                     normal(spo_reg_protein),
                     repressible(_3823),
                     corepressor(_3823,_3824),
                     bindable(_3824,smbs(spo_reg_protein))]
                    goal: normal(spo_reg_protein)
                    >>failed goal: normal(spo_reg_protein)
                  goal: active_smmol_conform(spo_reg_protein)
                    attempting to prove: 
                    [repressor(_3823,spo_reg_protein),
                     phenotype(_3823,repressible),
                     corepressor(_3823,_3824),
                     bindable(_3824,smbs(spo_reg_protein))]
\end{verbatim}
{\it This rule will succeed.}
\begin{verbatim}
                    goal: phenotype(spo,repressible)
                      attempting to prove: 
                      [operon(spo),
                       structural_gene(spo,_4083),
                       product(_4083,_4084),
                       inv_rel(_4085,_4084),
                       asserta(genex_clause
                                (phenotype(spo,repressible)))]
                    proved: phenotype(spo,repressible)
                    goal: corepressor(spo,_3824)
                      attempting to prove: 
                      [operon(spo),
                       structural_gene(spo,_4231),
                       product(_4231,_4232),
                       end_product(_4232,_3824),
                       inv_proportional_to(_4232,_3824),
                       repressor(spo,_4233),
                       bindable(_3824,_4233)]
\end{verbatim}
{\it The previous rule encoded a real-world heuristic for determining
the corepressor of a repressible operon, however it fails on this
``toy'' example.  The system uses a more general, simplified rule:  if
the gene product is made only in the absence of some substance, then
that substance is a likely corepressor of the operon.}
\begin{verbatim}
                      goal: corepressor(spo,_3824)
                      attempting to prove: 
                      [operon(spo),
                       structural_gene(spo,_4231),
                       product(_4231,_4232),
                       inv_rel(_3824,_4232)]
                      proved: corepressor(spo,chalk)
                    goal: bindable(chalk,smbs(spo_reg_protein))
\end{verbatim}
{\it The system tries to determine if chalk is binding to the
regulatory protein and putting it in an active conformation.}
\begin{verbatim}
                      attempting to prove: 
                      [bound(chalk,smbs(spo_reg_protein))]
                    >>failed goal: bound(chalk,smbs(spo_reg_protein))
                    goal: bindable(chalk,smbs(spo_reg_protein))
                      attempting to prove: 
                      [bind(chalk,smbs(spo_reg_protein))]
                      goal: bind(chalk,smbs(spo_reg_protein))
                        attempting to prove: 
                        [binding_site(chalk,smbs(spo_reg_protein)),
                         complementary_conform(chalk,
                                               smbs(spo_reg_protein)),
                         \+bound(_4396,smbs(spo_reg_protein)),
                         asserta(genex_clause
                                   (bound(chalk,
                                          smbs(spo_reg_protein))))]
                        goal: binding_site(chalk,smbs(spo_reg_protein))
                          attempting to prove: 
                          [reg_protein(spo_reg_protein),
                           part_of(spo_reg_protein,smbs(spo_reg_protein)),
                           assoc(_4422,_4423),
                           reg_gene(_4423),
                           product(_4423,spo_reg_protein),
                           inducible(_4422),
                           inducer(_4422,chalk)]
                          goal: inducible(spo)
                          >>failed goal: inducible(spo,_4863)
\end{verbatim}
{\it This rule failed because the SPO operon is not inducible.  This
rule and the following state that small molecule of an operon binds to
the small molecule binding site of the operon's regulatory protein.}
\begin{verbatim}
                        goal: binding_site(chalk,smbs(spo_reg_protein))
                          attempting to prove: 
                          [reg_protein(spo_reg_protein),
                           part_of(spo_reg_protein,
                                   smbs(spo_reg_protein)),
                           assoc(_4422,_4423),
                           reg_gene(_4423),
                           product(_4423,spo_reg_protein),
                           repressible(_4422),
                           corepressor(_4422,chalk)]
                          goal: repressible(spo)
                            attempting to prove: 
                            [operon(spo),
                             structural_gene(spo,_4863),
                             product(_4863,_4864),
                             purpose(_4864,_4865),
                             anabolic_proc(_4865)]
                            goal: repressible(spo)
                              attempting to prove: 
                              [operon(spo),
                               corepressor(spo,_4863)]
                              goal: corepressor(spo,_4863)
                                attempting to prove: 
                                [operon(spo),
                                 structural_gene(spo,_4914),
                                 product(_4914,_4915),
                                 end_product(_4915,_4863),
                                 inv_proportional_to(_4915,_4863),
                                 repressor(spo,_4916),
                                 bindable(_4863,_4916)]
                                goal: corepressor(spo,_4863)
                                  attempting to prove: 
                                  [operon(spo),
                                   structural_gene(spo,_4914),
                                   product(_4914,_4915),
                                   inv_rel(_4863,_4915)]
                                proved: corepressor(spo,chalk)
                          proved: repressible(spo)
                        proved: binding_site(chalk,
                                             smbs(spo_reg_protein))
                        goal: complementary_conform
                                  (chalk,smbs(spo_reg_protein))
                          attempting to prove: 
                          [operon(_5220),
                           assoc(_5220,_5221),
                           reg_gene(_5221),
                           product(_5221,spo_reg_protein),
                           reg_protein(spo_reg_protein),
                           smmol(_5220,chalk),
                           phenotype(_5220,repressible)]
\end{verbatim}
{\it An empirical rule.  The corepressor must be in the proper
conformation to bind to the regulatory protein if  the operon is
observed to be repressed in the presence of the corepressor.}
\begin{verbatim}
                          goal: smmol(spo,chalk)
                            attempting to prove: 
                            [corepressor(spo,chalk)]
                            goal: corepressor(spo,chalk)
                            proved: corepressor(spo,chalk)
                          proved: smmol(spo,chalk)
                          goal: phenotype(spo,repressible)
                            attempting to prove: 
                            [operon(spo),
                             structural_gene(spo,_5146),
                             product(_5146,_5147),
                             inv_rel(_5148,_5147),
                             asserta(genex_clause
                                       (phenotype(spo,repressible)))]
                          proved: phenotype(spo,repressible)
                        proved: complementary_conform
                                    (chalk,smbs(spo_reg_protein))
                        proved: bind(chalk,smbs(spo_reg_protein))
                    proved: bindable(chalk,smbs(spo_reg_protein))
                  proved: active_smmol_conform(spo_reg_protein)
                proved: active(spo_reg_protein)
              proved: complementary_conform
                          (spo_reg_protein,
                           overlap_region(spo_promoter,spo_operator))
             proved: bind(spo_reg_protein,
                          overlap_region(spo_promoter,spo_operator))
           proved: bindable(spo_reg_protein,
                            overlap_region(spo_promoter,spo_operator))
         >>failed goal: bind(rna_pol,spo_promoter)
transcription cannot initiate
>>failed goal: expressed(spo)
checking other explanations
no sequence given...
no message to translate...
done.
\end{verbatim}

{\it Briefly, the system has decided that the {\bf spo} operon is no longer
inducible, but is now repressible by chalk.  When chalk is bound to
the mutated regulatory protein, it is in the proper conformation to
bind to the mutated operator, thus RNA polymerase cannot bind.
Transcription cannot initiate, and the product is not made.}

\medskip

The following is another example of the system's more detailed knowledge
of the mechanisms of molecular genetics.  In this example, {\sc Genex} has
been told that the promoter has been deleted,and is then asked to
explain why the operon is not expressed.

\begin{verbatim} 
name of operon: op.  

op structural genes: enter one at a time, 5prime - 3prime order
 -- end with "done"
structural gene:
|: done.
enter sequence of op or [ ]
|: [ ].
are there any mutations in op or reg_gene (yes, no, or unknown) ?
|: yes.
mutation site known (yes or no) ?
|: yes.
mutation in promoter (yes or no) ?
|: deletion.
mutation in reg_gene (yes or no) ?
|: no.
mutation in operator (yes or no) ?
|: no.
mutation in struc_genes (yes or no) ?
|: no.
is op gene product made?
|: no.
enter any other information available 
e.g. proportional_to(X,Y), inv_proportional_to(X,Y), present(Substance), etc.
-- end with "done"
|: done.
goal: expressed(op)
  attempting to prove: 
  [operon(op),
   initiated(op),
   \+attenuated(op),
   xcribe(get_gene_seq(op),_853),
   xlate(_853,_854)]
  goal: initiated(op)
    attempting to prove: 
    [operon(op),
     part_of(op,_904),
     promoter(_904),
     bindable(rna_pol,_904)]
    goal: promoter(_904)
      attempting to prove: 
      [sequence(_904,_999),
       \+sequence(_904,[]),
       length(_999,_1000),approx(_1000,40),
       contains_subseq(_904,[t,t,g,a,c,a]),
       contains_subseq(_904,[t,a,t,a,a,t,g])]
\end{verbatim}
{\it Since the  system does  not have any part of the operon labeled
as the promoter, it checks the sequence to see if any section of the
sequence qualifies as the promoter.  In this example, no sequence was
given so it fails.  It then checks to see if any part of the operon that it
knows about is the promoter.  This will also fail.}
\begin{verbatim}
      goal: promoter(op_operator)
      >>failed goal: promoter(op_operator)
      goal: promoter(op_terminator)
      >>failed goal: promoter(op_terminator)
>>failed goal: promoter(_904)
>>failed goal: initiated(op)
transcription cannot initiate
>>failed goal: expressed(op)
checking other explanations
checking other explanations
goal: xcribe([],[])
no sequence given...
goal: xlate([],[])
no message to translate...
done.
\end{verbatim}


{\it With no promoter there is no place for the RNA polymerase to bind so
the operon cannot be transcribed.}

\section{What Makes a Problem Complex?}

In many domains, some interesting problems cannot be solved using
heuristics alone.  In the domain of bacterial operons, only problems
involving prototypical operons (e.g. those whose structure corresponds
to that shown in figure 3.1) with a single mutation are guaranteed to be
solved correctly by the original {\sc Genex} system using the heuristics
given.  Some might claim that this is the fault of the system
designer, for giving the wrong heuristics, or an insufficient number
of heuristics.

Certainly, any given problem which is currently unsolvable could be
solved by giving a new heuristic (or set of heuristics).  This does
not improve the performance of the system in general, but only on that one
type of problem.  Only if we could give the system a heuristic for
every type of problem would its overall performance improve.  This is
not always possible, as discussed in the previous chapter.

The original version of {\sc Genex} was given heuristics to deal
with operons having no more than one mutation.  Supposed we tried to
improve the system by giving the heuristics sufficient to deal with
all pairs of mutations.  Then there would still be the problem of
three mutations, etc., until we find that we have created a set of
heuristics whose size is the exponential of the size of our original
heuristics.  We have transformed the problem to one of choosing the
correct heuristic--not always so easy, and possibly intractable now,
due to the number of heuristics.

When model-based reasoning is used, the system creates its solution
anew for each problem, based on its model of the domain, rather than
relying on pre-compiled solutions.  There cannot be a situation which
the system cannot handle as long as it is derivable from the model.
We trade off time for space\footnote{The ideas presented in this and
the preceding paragraphs are due to Ramesh Patil, personal
communication.}.  Model-based reasoning has several other advantages,
which were discussed in this chapter.

The problem of when to use heuristics and when to use model-based
reasoning is not restricted to the case given above, i.e. which
problem can be solved using {\it only} heuristics.  For some problems
heuristics may work for part of the solution, and the remainder of the
problem is solved using model-based reasoning.  In the solution of
other problems, heuristic and model-based reasoning may be
interspersed.  This is an issue in expert systems: when is the use of
empirical or heuristic knowledge appropriate, and when is it necessary
to return to an approach based on more general principles?

As discussed in the previous chapter, heuristic rules often contain
implicit preconditions which make it difficult to determine the exact
conditions under which a heuristic can be applied correctly.  The
human expert can usually recognize a situation as being one to which a
certain heuristic applies.  Furthermore, a human expert can often {\it
reduce} a complicated problem to a more simple one to which a known
heuristic applies.  If the rule was applied mistakenly, the expert
recognizes that subsequent conditions are incorrect or inconsistent.
This is certainly a topic for further study.  The experiment described
in this paper demonstrates the need for a system which can use
both heuristics and model-based reasoning.
