Knowledge-Based Experiment Design in Molecular Genetics

KNOWLEDGE-BASED EXPERIMENT DESIGN IN MOLECULAR GENETICS*

Peter Friedland Heuristic Programming Project Computer Science Department Stanford University

Stanford, CA 94305

A system to produce practical experimental plans in the domain of molecular genetics is in development. It makes use of a large, expert-entered knowledge base containing object-level and strategy knowledge about the domain. The system works by refining general strategies or "skeletal plans," to the level of detail desired by the system user.

l. INTRODUCTION

A large percentage of the experiments carried out in a genetic laboratory fall into the class of structural analysis. The goal of these ex­ periments is to learn something about the phy­ sical structure of a particular type of DNA molecule. The experimenter uses his knowledge of fundamental molecular biology, laboratory methods, and basic analytic strategies, com­ bined with what is already known about the structures under study, in order to design an appropriate experiment.

This paper will describe and illustrate one of the methods scientists employ in the experiment design process. It will then discuss a heuris­ tic program which implements this method using a knowledge base entered directly by domain ex­ perts.

2. A THEORY OF EXPERIMENT DESIGN

2.1 ~Method Scientists Employ

Much of the intellectual effort of experiment design can be characterized as an "encyclope­ dia-dictionary" loop. Faced with an analytic task, the scientist first picks an appropriate strategy from his collected personal knowledge, from the knowledge of colleagues, or from the literature--his "encyclopedia." The strategy consists of an abstracted or "skeletal" plan which has proven useful for this type of ex­ periment in the past. It may be as general as "label the structural feature you are looking for and then look for the label," or as speci­ fic as a detailed laboratory protocol for using an electron microscope to locate loops.

*This research is supported by NSF

MCS 78-02777.

The experimenter than instantiates each of the steps of his skeletal plan with a specific lab­ oratory tool. He does this by first referring to his encyclopedia again, looking for informa­ tion to help him chose which of the possible techniques is most suitable to the particular problem conditions. Three types of information are useful in making this selection. First, can the technique accomplish the goal of the plan-step? For example, if the specific plan­ step were to degrade (break into small pieces) all single-stranded DNA, which techniques are known to have accomplished that task on previ­ ous problems. Second, will the technique work on the particular molecule under the particular laboratory conditions? For example, a given enzyme may be able to degrade single-stranded DNA, but it may fail on this particular problem because the molecule is circular or because in­ hibitors are present in the sample. Finally, which of the remaining techniques is best? This involves using a heuristic based on para­ meters like convenience, reliability, accuracy,

time, and cost.

The refinement process may occur in several hierarchical steps. For the example of degrad­ ing all single-stranded material on the mole­ cule, the experimenter might first decide to use enzymatic means of digestion, then decide to use a single-strand specific endonuclease, and finally choose Sl endonuclease. The advan­ tage of this hierarchical approach is that the experimenter does not have to consider all techniques as independent, instance-level enti­ ties. Instead of making a choice among, say, one hundred different degradation methods, he can first make use of heuristics to choose be­ tween two basic classes, enzymatic and nonenzy­ matic. After selecting enzymatic, he decides between endonucleases and exonucleases, and then between double-strand-specific and single­ strand-specific endonucleases. His final deci­ sion is among only half a dozen or so particular enzymes.

Sometimes the experiment designer will not be able to locate a suitable instantiation of a skeletal plan step. Then he refers to his "dictionary," attempting to understand what is the purpose of the step so that he can break it up into its component parts. For example, sup­ pose the experimenter cannot find a workable instantiation for a denaturation step. He uses his dictionary to find that denaturation really means breaking the hydrogen bonds between the two strands of DNA. He then attempts to find a new skeletal plan for the subgoal of hydrogen bond breaking and repeats the experiment de­ sign process for that skeletal plan. The idea is that he is now treating denaturation as the goal of an experiment design problem, i.e. that subgoals are generated when instantiation fai~.

2.2 An Example of Plan Instantiation

An example of how a single, general skeletal plan can lead to the design of different ex­ periments can be seen in the problem of se­ quencing. Sequencing is the process of deter­ mining the location on a molecule of specific sites, usually either bases or specific strings of bases. A general strategy for sequencing is as follows:

1. Label one end of the structure.
2. Treat the structure so that on the average one site is cut per molecule.
3. Determine the length of the labeled fragments.

This strategy has been instantiated in differ­ ent ways for the two problems of total base se­ quencing and restriction site mapping. For to­ tal base sequencing the problem is to determine which of the four bases, A, G, C, or T, is pres­ ent at each position on the molecule. The first step in the plan is refined to labeling with radioactive Phosphorus 32, the current best method. The second step is instantiated either by a series of chemical reactions or by a carefully controlled enzymatic reaction. The final step is accomplished by separating the fragments by electrophoresis and locating the labels with autoradiography. The process is known as Maxam-Gilbert sequencing (1) in the chemical case and Sanger-Coulson sequencing (2) in the enzymatic case. Both are thought of as major advances, decreasing by over an order of magnitude the time required to deter­ mine the base sequence of moderately complex molecule from the previous best method,

For restriction site mapping, the goal is to locate specific four-, five-, or six-base strings on a structure. (These are the active cutting site for enzymes known as restriction enzymes). The first and third steps of the skeletal plan are instantiated as above; the second step is refined to cutting with a par­ tial digest of the desired restriction enzyme (3).

2.3 Relation to other AI Work

The basic idea of maintaining a collec tion of abstracted plans relates closely to Schank's concept of scripts in understanding natural language (4). The human scientist, in the typical experiment design case, does not plan from scratch; instead he makes use of a li­ brary of knowledge about how classes of labora­ tory methods fit together to accomplish certain design goals. Maintaining a collection of pa­ rameterized plans was first discussed in AB­ STRIPS with the name of MACROPS (5). The bene­ fits of hierarchical plan refinement lllive evolved from ABSTRIPS (6) planning work through the robot planning systems of many other includ­ ing Sacerdoti (7).

3. IMPLEMENTATION

3.1 The Experiment Design Heuristic

The planning method has been impl emented in a straightforward manner. An experimenter de­ scribes his problem by telling what he already knows about the structure and its surrounding environment and providing a goal for the exper­ iment. The system searches its library of strategies for skeletal plans that have proven useful for satisfying the given goal or ones like it in the past.

The experiment design system then refines a skeletal plan by working through a detailed taxonomy of laboratory techniques. It uses do­ main-specific rules to carry out the three-fold selection process described above: goal-orien­ ted rules to choose te~hniques which can accom­ plish the desired task, rules relating tech­ nique parameters to molecular and sample condi­ tions to eliminate those techniques which will not ''go" for the given problem, and heuristics for making a final selection based on the rela­ tive convenience, reliability, accuracy, and cost of the competing techniques.

The system also makes use of rules which point out possible interactions between plan-steps, When it encounters an applicable rule of this sort 1 it postpones further refinement c>f the step until enough information is known to mini­ mize an unfavorable interaction or (the more common case) maximize the favorabl e effects of an interaction.

If an appropriate technique cannot be found to instantiate any plan-step, the system recurs as described above. A subgoal is created to de­ sign an experimental plan to provide a new method for accomplishing the plan step.

3.2 The Knowledge Base

All three of the processes described above-­ problem description, skeletal plan finding, and plan-step refinement--are heavily dependent upon a detailed knowledge base. This knowledge base is being constructed by molecular biolo­ gists and biochemists through the facilities of the Unit Package developed at Stanford (8).

In the problem description phase of the process the user is guided in creating an instance of a unit for a DNA structure. The prototypical DnA structure unit contains slots for all the pos-­ sible kinds of information that could be known for DNA structures. It also contains rules for checking consistency of information and for filling in additional slots from given ones-­ users don't always realize how much they really know about their structures. The user then describes other laboratory conditions by creat­ ing an instance of a prototypical sample-condi­ tions unit.

The skeletal plans are each described as units in the knowledge base. The units contain a slot listing the possible general and specific utilities of the plan, as well as a step-by­ step description of the plan. For example, the skeletal plan for locating inverse complemen­ tary regions on all types of structures is:

1. DENATURE
2. RENATURE RAPIDLY
3. DEGRADE SINGLE-STFANDED
4. DETECT LARGE-MOLECULAR-WEIGHT DNA

The bulk of the knowledge base consists of the descriptions of laboratory techniques used by the plan-refinement part of the experiment de­ sign system. The technique descriptions are arranged in a tree with the major branches be­ ing sequence-analysis, modification, separation and detection. Each class of techniques or in­ dividual technique is described in a unit con-. taining declarative information about utility, optimal laboratory conditions, allowable sub­ strates and the like, as well as the selection rules that are relevant to that technique.

The knowledge base was constructed by several Stanford molecular biologists using the inter­ active facilities of the Unit Package. It currently contains approximately 25 skeletal plan units and 200 laboratory technique units. There are about 250 rules for plan-step instan­ tiation, consistency checking, and modelling the consequences of modification techniques.

4. RESULTS AND CONCLUSIONS -

The experiment design system is currently oper­ ational and seems to give satisfactory (i.e., plausible) results for a variety of analysis experiments. The particular experimental pro­ blems of finding self-complementary regions (inverted repeats), and mapping intervening se­ quences between genes have received the most attention. As the knowledge base continues to grow in scope and complexity, the range of ex­ perimental plans produced should also increase.

An automated experiment design system will serve two major functions: throughness and variety. Some instantiations of experimental strategies are missed either because a scien­ tist is not aware of all relevant technqieus or because of prejudices toward certain techniques. The design system will be as thorough as its knowledge base--the product of many experts's efforts. The system will promote variety, as it is able to combine the best strategies of different experimenters through the recursive encyclopedia-dictionary process.