\chapter{Future Work}

This chapter outlines the broad requirements and approaches for a
generalized problem solving system in molecular genetics.  It
describes several AI mechanisms that may prove useful in developing
later versions of the {\sc Genex II} program.  It assumes that in later
versions of the system, a major concern will be limiting the complexity
of the program and the enormous amount of information with which it
must deal.


\section{Meta-Reasoning}

{\sc Genex II} reasons about uncertainty by using the necessary conditions of
the model it has made to assign values to the uncertain variables.  In
the current implementation, the necessary conditions for each model
are given to the program.  It should be possible for the program
itself to derive these conditions, since all the necessary information
is contained in the knowledge base.  The following example illustrates
why this is difficult.

Assume the system has decided that an operon is repressible.  It does
this by noting an inverse relationship between the product of the
operon and some small molecule, which it assumes is the corepressor.
The necessary conditions for repressibility are (1) that the repressor
can bind to the operator, and (2) that the small molecule can bind to
the repressor.  If the knowledge base contained rules such as ``an
active repressor must bind at the operator to switch the operon off,''
and ``if the operon is repressible and the small molecule is bindable
to the repressor, then the repressor is active,'' then the derivation
of the necessary conditions would be trivial.  The second rule is in
the knowledge base already.  The first rule could be derived from
existing rules by collapsing a chain of inferences, e.g.  R1: an
operon is not expressed if it is not initiated, R2: it is not
initiated if the RNA polymerase cannot bind to the promoter, R3: a
molecule cannot bind to a site if something is already bound there,
R4: the repressor binding site of the operator overlaps the promoter,
and finally, R5: an active repressor binds at the repressor binding
site of the operator.  

Unfortunately, there is no easy way to extract these inferences from
the encoding of the rules.  For instance, R2 is the last clause of the
rule to prove initiation can occur, and the preceding clauses are
only there to restrict the variable in the call to BIND to a promoter.
Many of {\sc Genex II}'s rules mix clauses containing knowledge about operon
structure, about the function of operon subparts, and about processes
involving the operon, instead of representing each of these
separately.  If the different types of knowledge were represented
explicitly, it would be much simpler to recognize necessary conditions
by analysis of the knowledge base.

\section{Analogy and Learning}

The system could decrease searching the problem space by determining
whether the observations presented fit any known mechanism.  If so,
the system can attempt to transfer properties from the known mechanism
to the new situation.  I call this hypothesis formation by analogy.
Indeed, the original goal of this project was to design a system that
would hypothesize about eukaryotic gene regulation based on
information it had about prokaryotic gene regulation.  The system
would do this by attempting to draw analogies between the prokaryotic
and eukaryotic systems.\footnote{Of course, there is no reason why the
system has to be restricted to prokaryotic regulation as a source for
analogy.  It could use information about regulation in lower forms of
eukaryotes, or even information about systems from a totally different
fields.}  The ability to reason by analogy would also enable the system
to explain the structure and behavior of a new system by showing its
similarity to an existing system.

Patrick Winston has done work in the area of learning and reasoning by
analogy.  In an early paper, he introduces the {\it transfer frame} as
a means of acquiring information from simile-like statements.  For
example, from the statement ``John is like a fox,'' the system would
conclude ``John is clever.''  The simile determines a {\it source frame}
and a {\it destination frame}.  For the example given above, {\it John} is
the destination and {\it fox} is the source.  The transfer frame
determines which property-value pairs are allowed to pass from the
source to the destination.  Winston proposes several criteria for
determining which properties should be transferred:  those which are
exhibited to an unusual degree (very high or very low), those which
are deemed globally important (such as {\it purpose}), and those which
are filled in an unusual way relative to other descriptions in the same
class as the source.  If more than one transfer frame is generated,
the frames are filtered according to the following method:  prefer
transfer frames that have properties which are present in the typical
instance or in some sibling of the destination, or prefer those that
are in the context of the last transfer (if all else fails).

A mechanism for hypothesizing by analogy would be very useful to a
molecular genetics expert system.  It might use a mechanism similar to
Winston's transfer frames.  Every process in the prokaryotic system
could have a {\it purpose} or {\it action}.  Then when an explanation was
needed in the eukaryotic domain, the system would look for a process in
the prokaryotic domain that had a purpose or action that matched the
need.  The system would then attempt to match the objects in the
prokaryotic domain to objects in the eukaryotic domain, possibly using
{\it transformations} (for instance, one transformation might state
that it is permissible to substitute one enzyme for another if they
have similar functions) to aid the correspondence.  The role of some
object in the prokaryotic domain might be played by several objects in
the eukaryotic domain; in this case the system would have to perform
some transformation that would enable it to think of the group as a
single entity for the purpose of translating the action of the
mechanism.

Research by Tom Mitchell in the areas of learning and problem solving
also has application to the area of hypothesis formation by analogy.
In particular, his recent work on generalization (wherein the problem
solver attempts to formulate a heuristic given an application of an
operator to a rule) describes a means by which the problem solver can
create new terms to use in defining its heuristics.  Generalization
would be used when formulating analogies to produce the transfer
frames described above.  

The new work by Mitchell is particularly interesting because it claims
to give the program the capability to formulate new relationships,
instead of being restricted to those about which it has been told.
The program creates new terms by propagating and combining constraints
on the use of a sequence of operators.  The domain of Mitchell's
program, called LEX, is integral calculus, so the operators consist of
approximately 50 transformations that can be applied to integrals,
such as:
\[ \int  r f(x)dx \longrightarrow r \int f(x)dx \]
where {\it r} indicates a real
number.

Mitchell gives the following example in which the program could create
the new term {\it odd integer}.  Consider the solution path shown in
figure 6.1.
\begin{figure}
\[
\begin{array}{cl}
state1: &  \int \cos^{7}(x)dx  \\
\downarrow & op1: \;  f^{r}(x) \Rightarrow f^{r-1}(x)f(x)  \\
state2: &  \int \cos^{6} (x) \cos(x)dx  \\
\downarrow & op2: \; f^{r}(x) \Rightarrow (f^{2} (x))^{[r/2]}  \\
state3: &  \int (\cos^{2}(x))^{3}\cos(x)dx  \\
\downarrow & op3: \; \cos^{2}(x) \Rightarrow (1-\sin^{2}(x)) \\
state4: & \int (1-\sin^{2}(x))^{3} \cos(x)dx \\
\downarrow & op4: \; \int g(f(x))f'(x)dx \Rightarrow \int g(u)du, u=f(x) \\
state5: & \int(1-u^{2})^{3}du, u=\sin(end)
\end{array}
\]


\caption{Solution path for $ \int \cos ^7 (x)dx $}.
\end{figure}

State5 is a polynomial raised to some {\it integer} power.  By
propagation of this constraint backwards through the sequence of
operators used, the program could determine that state1 must match an
instance of \( \cos (x)dx \), where \( c \) is constrained to satisfy
the predicate \( real(c) and \; integer ((c-1)/2) \), which is the
definition of {\it odd integer}.

Using Mitchell's method, the new terms are created out of terms which
appear in the operator definitions.  There seems to be an {\it
essential set} of terms which must be predefined before any new terms
can be created.  For LEX's domain, this set would include integer,
real number, function, etc.  Any new terms which the system creates
must derive from the basic set of terms provided.  If a potential new
term is truly novel, i.e. not derivable in whole from any pre-existing
definitions, the program will be unable to define it.  There is not
even a way to ensure that a complete set of essential terms has been
provided, for the same reason.  This would limit the power of a
hypothesis-forming system if all the essential terms have not yet been
defined.  However, even a combination of previously-known terms, such
as Mitchell's method could generate, may provide new insight into a
problem.

\section{Abstraction Spaces and Multiple Levels of Representation}

An abstraction space is a simplification of a given problem space in
which unimportant details are ignored.  After a problem is solved in
the abstraction space, all that is needed to complete the solution is
to account for those details in the original problem space, if this is
possible.  A hierarchy of abstraction spaces can be constructed if the
system is able to discriminate among several levels of detail.
Objects appearing in the highest abstraction level are those most
critical to the solution of the problem.  Other objects appear in
lower levels as they become necessary to fill in the gaps in the
partial solutions created in the preceding levels.  If a problem
cannot be solved in a given abstraction space, control reverts to a
higher abstraction space.  The problem solver eliminates the
troublesome step and attempts to complete a new plan starting at that
point in the higher space.  Only then does control return to the lower
space.

In his 1974 paper on ABSTRIPS, Sacerdoti introduced the concept of a
hierarchy of abstraction spaces.  ABSTRIPS solves a problem in one
abstraction space before beginning to plan in a lower space.  In this
way, steps that don't lead to the problem solution or that yield very
inefficient plans can be eliminated early, before a great deal of
effort has gone into planning the details of their execution.  This
saves the problem solver a lot of wasted work.  The difficulty lies in
determining which aspects of a problem are important and which are details.

The concept of multiple levels of representation
is complementary to abstraction spaces.  If the user
presents the system with a problem, the system would first try to
solve it using the least detailed descriptions possible.  If the
details are not needed, they will only complicate the problem-solving
process.  If they are needed, then the system can always choose to use
them.  The system would not always use the least detailed
representation it has available, but it would use the least amount of
detail that is sufficient to solve the problem.  If the user asks for
an elaboration of a solution, it might become necessary for the system
to use a more detailed representation.

Ramesh Patil's 1981 work on electrolyte and acid-base disorders
examined multiple levels of representation.  Patil argued that
knowledge represented at several levels of detail is necessary for
complex reasoning.  Patil implemented a system which used a
multi-level model for representing diseases and causal phenomena.  The
deepest level consisted of pathophysiological knowledge about disease,
while higher levels contained more syndromic knowledge.  Patil states

\begin{quotation}
The aggregate syndromic knowledge provides us 
with a concise global perspective and helps in 
the efficient exploration of diagnostic alternatives.
The physiological knowledge, on the other hand, 
provides us the capabilities of handling complex 
clinical situations ..., evaluating the physiological
validity of the diagnostic possibilities being 
explored, and organizing a number of fragmented
and seemingly unrelated facts into a coherent 
causal description \footnote{Patil 1981, p. 44.}.
\end{quotation}

Each level of description can be viewed as a collection of nodes,
each representing some state of a physiological parameter, and 
links, representing the relationships between different nodes.
Some nodes can be defined in terms of a network of states, called 
the elaboration structure, at the next lower (more detailed)
level of description.  The multi-level description scheme also
allows a single link in a higher level to represent a chain of links
in a lower level.  These are useful mechanisms for controlling the 
amount of detail that is dealt with at any given time.

Three levels of representation -- {\it genetic}, {\it molecular}, and
{\it atomic} -- should be sufficient for an expert system in molecular
genetics.  For example, the action of enzymes can be understood on
several levels.  On the least detailed level, the function of an
enzyme is to catalyze the reaction of two chemicals (called {\it
substrates}).  If both substrates are present, it is assumed that the
reaction will take place.  On a more detailed level, the way an enzyme
works is that each of the substrates binds to the enzyme, and then
since they are physically close to each other, the reaction is more
likely to occur.  Thus the preconditions for the enzyme working at
this level of detail are not only that the substrates are present, but
that they are able to bind to the enzyme (i.e. their binding site is
not blocked by anything).  On the atomic level the conformations of
all three elements involved and the thermodynamics of the reaction are
important  \footnote{Much of the information required to model molecular
genetics on the atomic level is still unknown in the domain.}.  In
attempting to explain some problem involving enzymes, the system will
first use the least detailed model, and if it can complete the
solution on that level, it will attempt to work out the solution in
the more detailed model.  {\sc Genex II} currently makes models and does
simulation on the genetic level, except in the case of the BIND
operation which is simulated on the molecular level.  This is because
{\sc Genex II} has no means of switching between levels, and most interesting
events (i.e. those that the system would want to describe in more
detail) occur during the bind operation.

PEPTIDE (Weld, 1984) is a system which predicts genetic activity
by simulating a combination of five basic processes (BIND, FOLD,
SLIDE, DROP, and REACT).  The five processes are discrete; ``they
either happen completely or not at all.''  A continuous process is
generated from a repeated cycle of discrete processes.  PEPTIDE can
determine what will happen when a continuous process is run to the
limit, i.e. until ``a currently active discrete process will stop or an
inactive one will start.''  For instance, PEPTIDE would represent
transcription as a BIND operation, followed by a continuous simulation
of a REACT-SLIDE cycle, followed by a DROP.

PEPTIDE represents processes on the molecular level described above.
This level of detail is suitable for simulating a subpart of some
larger process within the cell.  It would not be appropriate for {\sc
Genex II}
to solve problems entirely on this level \footnote{but note that Weld
never claims that PEPTIDE should be used to solve any entire real
problems.} for several reasons.  First, the molecular level often is too
finely-grained to produce a satisfactory solution.  Consider a problem
in which a molecule is bound to DNA and blocks the movement {\it
along} the DNA strand of an enzyme such as RNA polymerase.  The exact
location of binding is probably not essential to the solution of the
problem; the general region of the DNA strand (e.g. transcribed
region) is.  A program which reasoned {\it only} on
the molecular level might have to simulate the consequences of
blocking the RNA polymerase at every one of 1000 specific sites along
the DNA strand \footnote{PEPTIDE shifts its focus to the larger scale in
this instance, too: its ``qualitative representation of quantities
(including positions on a chain) only contains information like `a
repressor is bound between the promoter and the gene.' ''}.

The second reason why it is difficult to reason entirely on the
molecular level is that there is not enough fundamental knowledge
about the physical chemistry of these processes to predict the
interaction of two macromolecules.  Therefore any solution reached by
simulation alone would have to simulate every possible interaction.

Finally, many of the heuristics used by molecular biologists (and by
{\sc Genex II}'s model-maker) to select a likely model for the operon's
behavior deal with objects on the genetic level.  A higher-level view
of the system is needed to reduce the complexity of the solution
space, and also to resolve the potentially conflicting results of the
multiple simulations.  The lower-level view would allow the system to
elaborate on its solutions.

\section{Constraints}

Constraints can sometimes be used to cut off a particular branch of
speculation.  Suppose the system hypothesized that a protein was
preventing DNA from being transcribed by binding to the DNA and
blocking the binding site for RNA Polymerase II.  The typical binding
site is between 15 and 40 nucleotides in length, so the binding site
of the protein would have to be approximately that size to cover it.
Now perhaps the system had previously constrained the protein to be
smaller than this, to support the hypothesis
that the protein got into the nucleus by passing through the nuclear
membrane.  These two constraints are not simultaneously satisfiable,
so the system can abandon this line of reasoning.

Constraints are a very common device in artificial intelligence
reasoning systems.  MOLGEN (Stefik, 1981), a program that plans gene
cloning experiments in molecular genetics \footnote{In addition to the
work reported by Stefik, there has been a considerable amount of
additional work done in the areas of representing the knowledge needed
to do planning in molecular genetics, building up knowledge bases
(Friedland, 1982), and experiment planning.} uses constraints to
coordinate separate subproblems because MOLGEN breaks up a problem
into subproblems that are solved independently.  Constraints that
represent the interactions of these subproblems ensure that the
various solutions interface correctly.  A typical constraint might
state that the endonuclease used in step six should not cut the gene
inserted in step two.  MOLGEN identifies three operations on
constraints: formulation, propagation, and satisfaction.  Constraint
formulation is the adding of new constraints as the design process
progresses.  Usually, the constraints become more detailed during the
solution process.  Constraint propagation brings together constraints
from the separate subproblems.  MOLGEN uses a least commitment
strategy--it avoids instantiating variables in the constraints for as
long as possible.  This gives it the greatest number of options for
constraint satisfaction, finding values that satisfy the constraints
on the problem.


\section{Representation}

There are two problems of knowledge representation that must be
considered in any expert system: how the knowledge is represented
internally and how the knowledge is represented for the user.  In a
molecular genetics expert system, the internal representation must
facilitate the representation of several kinds of knowledge: facts
about molecular biology (which can be as diverse as strings of letters
representing nucleotide sequences or a procedure that encodes the
behavior of a polymerase), knowledge about processes and how to reason
about them, and knowledge of how to formulate hypotheses.  

As discussed in the section on meta-knowledge, {\sc Genex II}'s reasoning power
is restricted by a representation which does not distinguish between
different types of knowledge (about structure, processes, and
interactions).  A knowledge representation system proposed by Brian
Smith in 1978 seems suited to encoding knowledge about the objects and
operations of molecular genetics.  The representation was based on a
division of knowledge between the ``anatomical'' (how is {\it x}
structured?) and ``physiological'' (how does {\it x} work?).  The
representation could also be used to encode processes.  Smith
classified potential questions that might be asked of the system into
requests for information (e.g. ``what is X?'' and ``how do X and Y
relate?''), verification of suggestions (``is it true that ...?''), and
hypotheticals (``what would happen if ...?'').

Smith's proposed knowledge representation system seems to clarify the
distinction between the different types of knowledge in the system.
The capability to answer the above types of questions could serve as
the framework for the hypothesis-forming mechanism in a molecular
genetics expert system.

A representation such as the one described by Smith would also
facilitate the representation of spatial and quantitative information.

How an expert system's knowledge is represented to the user is a
serious consideration.  I believe that new domain information should be
entered by the experts themselves.  Molecular biology knowledge that
must first pass through the computer scientist is subject to possible
oversimplification, misinterpretation and plain errors.  A related
problem is that in a field where new information is being discovered
rapidly, the knowledge base of a system such as the one proposed can
easily become obsolete.  Facilitating addition of new information by
the experts themselves should be a primary goal of the
knowledge-acquisition mechanism of a molecular genetics expert system.

\section{Control Structure}

In a system as complex as this, there is an advantage to separating
solving the problem from planning the strategy of how to solve the
problem.  This is called a {\it layered control structure}. 

Stefik described a layered control structure that separated decisions
about planning steps in the laboratory from decisions about what
strategy to use in planning the problem solving process.  MOLGEN
divided the problem solver into three levels, called planning spaces.

The lowest level, the domain space, in a molecular genetics system
contains knowledge about the objects and operations inside the nucleus
of a cell.  The operations are actions that would be carried out in a
real cell (for example, REPLICATE).  The domain space is not a control
level.  The {\sc Genex II} knowledge base corresponds to MOLGEN's
domain space.

The design space is a control level that contains knowledge about how
to solve a problem.  The operators (such as PROPOSE-OPERATOR and
PROPAGATE-CONSTRAINT) create and arrange steps in domain space.  

The highest control level is strategy space.  The strategizer controls
the design operators that solve the problem.  It contains operators
such as USE-ANALOGY and USE-MORE-DETAIL.  This level also controls the
use of abstraction spaces.  The model-maker in {\sc Genex II} is a simplified
version of MOLGEN's strategy space.  If {\sc Genex II} encoded some expert
techniques for formulating hypotheses, these would be used at the
strategy level.

An advantage of this approach is that by dividing the different levels
of the planning process into separate domains, the complexity of the
problem solving process is reduced.  Another advantage is that being
able to reason about the planning process makes the problem solver
better at setting priorities and scheduling subgoals.

\section{The Role of Complexity Reducing Mechanisms in Genex}

It would be useful for a molecular genetics expert system to include
features from the systems described above.  I assume that the
knowledge base will be sufficiently complex that attempting to solve
the problem in a very detailed fashion right away is not
efficient--there are just too many possibilities at each point in the
process.  Rather, a molecular genetics expert system would have to
work out the broad outlines of the solution first, and add the details
gradually.  I think that this is the way that human experts work, too.
Such a system would use techniques from truth maintenance to keep
track of what things it believed to be true while it examined
different possible explanations for a problem.  None of the systems
described above contain all the mechanisms that the molecular genetics
system should incorporate.  For instance, neither ABSTRIPS nor MOLGEN
use the idea of truth maintenance which would allow them to reason
about a projected course of action or events.  This is necessary to
examine the consequences of proposed hypotheses. ABEL has the
limitation that all relationships between states are represented by
causal links.  This is not sufficient to represent all possible
interactions.  For example, it has been observed that regions of DNA
that are hypermethylated tend not to be transcribed.  It is not known
whether the relationship between hypermethylation and reduced gene
activity is causal, but in Patil's system we would have no choice but
to represent it as such.

Issues that should be addressed when designing a molecular genetics
expert system include:

\begin{itemize} \item What knowledge do experts use to select the most
promising refinements (and rule out the least likely) at each step in
the problem solving process.
\item How to control the amount of detail.  When do you need more detail 
and when do you need to step back and look at the larger picture?
\item How to limit the search space of possible hypotheses.  Can some
possibilities be eliminated {\it a priori}, and if so, how do you
identify them?  How to ``zero in'' on an answer.
\item How can analogies help in formulating hypotheses?
\end{itemize}

\section{Analyzing Laboratory Data}

It may become desirable to extend {\sc Genex II} so that it would be capable of
understanding biological data; e.g, interpretation of gel patterns and
enzyme activity studies, etc.  While the inability to interpret
laboratory data does necessarily prevent {\sc Genex II} from solving a given
problem, it makes it necessary for the problem to be pre-processed
into a form that {\sc Genex II} will understand.  This is time-consuming and
might limit the system's usefulness.

In order to analyze laboratory data, {\sc Genex II} must have the ability to do
macro-level reasoning, as described above.  Weld (1984) introduces a
process called aggregation which could give {\sc Genex II} this capability.  As
Weld describes it, 


\begin{quotation}
The system starts by simulating the effects of
discrete processes until it recognizes a cycle...where all discrete
processes are repeated.  It then aggregates the trace of a single
iteration of the cycle of discrete process executions, producing a
continuous process.
\end{quotation}

Although Weld demonstrates aggregation on his molecular-level
operations, there appears to be no reason why the same technique could
not be applied to {\sc Genex II}'s genetic-level operations, so that
the system could reason about approximate amounts of gene product
made, etc.
Some technique for reasoning about the results of aggregation is
necessary for {\sc Genex II} to do macro-level reasoning.  For example, the
aggregation of a continuous process of DNA replications would result
in all the resulting DNAs being identical, if the original replication
(the one that started the cycle going) produced two identical strands.
Given a DNA molecule with both strands methylated \footnote{having methyl
groups attached to the cytosine residues.} and if told that there was
no maintainance methylase, the system could correctly conclude that
the net result would be unmethylated DNA, since the original
replication would produce one methylated and one non-methylated strand
in each copy.  The actual implementation of Weld's aggregation system
in {\sc Genex II} would not require major system redesign, and is a possible
future improvement to the system.
