Structure and Function of the CRYSALIS System

1 Introduction

In this paper we present an application of Artificial Intelligence methodology to the domain of Protein Crystallography. 3 The long term practical goal of this work Is the creation of a fully automated system for protein structure determination, starting with data collection and ending with an accurate 3-D model of the molecule. Most of the software already exists at the two ends of the process. At the "front end", programs exist for reducing and transforming the x-ray diffraction data, and estimating phases. The result of this processing Is an electron density map (EOM), which gives a blurred view of the electron cloud surrounding the molecule. At the "back end" ore a variety of numerical techniques for taking a full or partial model of the protein and Iteratively refining the atomic coordinates so that the model Is a best compromise between one which best fits the data and one which best matches Ideal stereochemical constraints [Hermans74] [Agarwal77]. The "middle" portion of the process Is the generation of a first-order model of the protein, based on on lnteropretotlon of the EDM and the amino acid sequence (when known). EDM Interpretation has traditionally been a manual process of visual pattern recognition, for which CRT displays have become a significant aid In recent years.

1 Present address Is DARPA/IPTO, 1400 Wilson Blvd.,

Arlington, Va. 22209

2 Present address Is Dept. of Computer Science, Stanford University, Stanford Ca 94306

3 This work , was supported by the National Science Foundation lMCS74-23461-A01) and the Advanced Research Projects Agency (MDA 903·77-C-0322). Use of the SUMEX computer facility was made possible by the Biotechnology Resources Program of the NIH under Grant RR-00786.

STRUCTURE AND FUNCTION OF THE CRVSALIS SYSTEM

Robert Engelmore 1 Computer Science Department Stanford University

Stanford, California 94306

Allan Terry 2 Dept. of Information and Computer Science University of California, Irvine

Irvine, California 92717

ABSTRACT

CRVSALIS Is a knowledge-based system whose goal Is to Infer the three-dimensional structures of proteins from x-ray crystallographic data. The system uses both formal and judgmental knowledge from experts to select appropriate procedures and to constrain the space of plausible protein structures. The hypothesis generating and testing procedures operate upon a variety of representations of the data, and work with several different descriptions of the structure being inferred. This paper focuses on the architecture of the system, and points out some of Its Interesting features. An example of the system's performance Is given.

Although the use of a large computing system In conjunction with a graphical display has mode a significant reduction In EDM Interpretation time [Tsernoglou77], the knowledge used In matching the molecule to the EDM remains In the head of the model builder. Our aim Is to capture that knowledge within an automated EOM Interpretation program, thereby closing the gap which

remains In building a fully automated system.

Many diverse sources of knowledge contribute to the Inference of a protein structure from an EDM and associated data. Examples: chemical knowledge about protein composition Is used to estimate overall size and to generate expectations about special features that should be present In the data; stereochemical knowledge about protein conformation Is used to constrain the relative positions of atoms (e.g. certain subsets of atoms form rigid groups); X-ray crystallographic knowledge Is used to detect symmetries, or to match a hypothesized structure against the data; specific heuristics for Interpreting EDMa are continually Invoked to match features In the EDM with

expectations from the model.

In order to use the knowledge sources efficiently, a global data base -- the "blackboard" -- Is constructed which contains the currently active hypothesis elements, at all levels of description. The decision to activate a particular knowledge source Ia not pre-established, but depends on the current state of the solution and what available knowledge source Is most likely to make further progress. The control Is, to a large extent, determined by what has just been learned: a small change In the state of the "blackboard" may establish a new Island of opportunity, providing the preconditions to Instantiate further knowledge sources.

Figure 1 shows the types of data and hypotheses that are used In CRYSALIS. As In Heorsay-11 [Erman76], the hypotheses ore re1>resented In o hierarchically organized clots structure. In our case the different Information levels can be partitioned Into two distinctly different "planes", but the concept of a globally accessible space of hypotheses and data abstractions Is essentially the same for both systems. Knowledge sources ploy the same role os In Heorsay-11, adding, changing, or testing hypothesis elements on the blackboard. for further discussion see [Engelmore77]. The processes of generating or modifying hypotheses and of Invoking knowledge sources are nearly Identical to those described for the AGE system [NII79].

In the course of deriving a protein structure which Is a best explanation of the given data, the crystallographer generates a three-dimensional description of the electron density distribution of the molecule, often called an electron density mop (EDM). Due to the resolution Imposed by the experimental conditions, the EDM Is an Indistinct Image of the structure, which does not reveal the positions of Individual atoms. The crystallographer must Interpret the mop In light of auxiliary data and general principles of protein chemistry In order to derive a complete description of the molecular structure.

The most Important piece of auxiliary data Is the amino acid sequence, along with a specification of any special chemical groups attached to the protein chain. This Information defines the set of atoms which comprise the structure, and their Interconnections, but gives little or no Information on how the protein folds and twists from one end of Its polypeptide chain tQ the other. The EDM, on the other h11nd, shows where the protein must lie In 3-space, but gives little Information on which atoms go where. Thus the amino acid sequence and and the EDM are complementary sources of Information.

By carefully studying the mop, and guided by the amino acid sequence, the experienced protein crystallographer can find features which allow him to Infer approximate atomic locations, molecular boundaries, groups of atoms, the polypeptide b11ckbone, etc. Typically, several weeks to months of tedious effort are required to build, manually, a model of the molecular structure which conforms to the electron density map and Is also consistent with the sequence, his knowledge of protein chemistry, stereochemical constraints and other available chemical and physical data.

2 Structure of the CRYSALIS system

In the CRYSflliS system the data, the hypothesis and the knowledge base are all hlerorchically structured. The data have several levels of abstraction, the hypothesis Is described ot three levels of detoll, and the knowledge bose Is divided Into domain knowledge, task knowledge and strategy knowledge. These three hierarchies are discussed below.

2.1 The data hierarchy

The Electron Density Map

The primary Input data source Is the EDM, which Is derived from X-ray diffraction studies of the crystallized protein. The EDM Is an Image of the electron cloud surrounding the atoms of the molecule. Its representation Is a set of Intensity values defined on a three-dimensional grid of 1 00,000 to 300,000 points. Usually 1 ~ to 6~ of the Intensities are significant to a model builder. The usefulness of the mop can be characterized by Its resolution and Its quality. CRYSALIS Is Intended to Interpret EDMs of resolution In the range of 2.0 to 2.6 Ang. (for comparison, an average distance between atoms Is 1. 7 Ang.), and of relatively high signal to noise ratio.

Because of the size of the data base, and the relatively small number of significant points, the system uses several abstractions of these data.

The Peak List

The most obvious abstraction of the map Is a list of local maxima. These maxima (peaks) are calculated from the map by a process of Interpolation, and are thus ntlt constrained to lie on the EDM grid points. A peak usually Indicates the position of an atom, or an average position of a small grou1> of atoms. The height of a peak Ia a rough linear function of the atomic number of the atom(s) producing the peak. While the Inability to resolve Individual atoms means there Is an error In this correspondence, one can distinguish between various classes of peaks.

'The Skeleton

The second major abstraction Ia the skeleton. By a method first developed by Greer (Greer74] and later refined by us, the EDM Is repeatedly scanned, discarding Intensities at oil grid points which are below a given threshold and not required for preserving continuity of the electron density cloud. What finally remains Is a list of grid point locations, coiled nodP.s, and their connections to other nodes. In this woy one reduces the number of data points by two to three orders of magnitude. The skeleton preserves the general to1>ology of the protein, at the price of losing some of the fino detail that distinguishes one amino acid side

chain from another.

The Segment List

The seoment list condenses the skeleton (without losing any Information) by hiding nodes with only two neighbors. A se[1ment Is the set of connected nodes starting at a tip (one nelohbor) or branch point (three or more neighbors) and terminating at another tip or branch point.

Once the dote have been condensed to the level of segments, one can frequently identify topological features that correspond to structural elements of the protein molecule. For example, there ore usually some long, connected segments that correspond to the backbone of the protein. This backbone is sometimes "clean" In that It shows n simple alteration of objects that appear to be sidechoins and main chain (peptide) links. Skeletonlzation Is a heuristic procedure, however, ond often at least some portions of the skeleton are difficult to Interpret.

Subgraphs of the Segment List

It Is often useful to think In terms of subgraphs of segments. Since in many cases these subgraphs correspond to superatoms (see below), many of the heuristics for EOM Interpretation can be expressed In terms of subgraphs. There are two major kinds of sub9rophs : sldechains and peptldes. Sldechaln subgraphs are collections of segments which look like they might be representations of real sldechains (a bit of nomenclature: a "sidechoin" Is the physical entity the system Is trying to model, o "sldechaln subgraph" is a port of the segment list thnt one suspects Is the skeletal re1>resentation of the sidcchain). Thus for we hove Identified six kinds of sidechaln subgraphs. Peptide subgraphs are defined as all segments between one sidechaln subgraph (or bridge) and

the next.

2.2 The hypothesis hierarchy

The goal hypothesis In our system Is a model of a protein molecule which bost explains the given experimental data and Is consistent with accepted principles of stereochemistry and protein chemistry. As mentioned earlier, many diverse sources of knowledge are brought to bear on the problem of EDM Interpretation. Each knowledge source (KS) may use different descriptions of the objects on which It operates. For example, a helix locater works with an abstraction of o molecule consisting of a specification of the backbone shape, omitting all other dotolls. A side chain template matcher, on the other hand, uses a full specification of all atomic positions to define the side chnln template. In order to cope with this diversity, the hypothesis Is represented as hierarchically organized levels of descriptions, as shown In Figure 1. A KS Is o collection of rules which makes Inferences either within or between levels In the hypothesis space.

There are three levels of description In the model plane. The most detailed level Is the atomic level, a specification of the spatial coordinates of all atoms In the model with respect to some arbitrary origin (the coordinates of hydrogen atoms are generally omitted). Proteins exhibit well-defined topological constraints which permit descriptions at hl{ther levels of aggregation. Thus, proteins consist of a linear polymeric chain and, In many cases, attached atomic groups coiled co-factors. The level of description which describes the model In terms of familiar groups of atoms such as peptide links, side chains, and cofactors, Is celled the superatomlc level. These units may be aggregated still further Into whet Is generally coiled a "secondary structure", I.e., a specification of the relative locations of large Identifiable portions of the protein. Examples ore the alpha helix and the beta sheet conformations, well known to protein chemists. Many other such "stereotypes" exist, although they may bA associated with o specific family of proteins. This level of description Is labelled stereotyplc In Figure t .

1\ partial or complete h'ypothesls consists of linked hypothesis elements. A hypothesis element (HE) Is a labelled entity In the space of hypotheses. Attached to each entity Is a set of attributes which define the HE in terms appropriate to the level of description on which It resides. HEs at the three levels are defined as follows: Stereotype Hypothesis Element

LI\BEL - STn, n = 1, 2, ...

TYPE.- e.g. 01\CKOONE

RANGE - (a . b) where a and bore sequ~VJce numbers, and a < b

OLOCK - (x . y) ; x (or y) Is non-NIL If the backbone Is blocked at a (or b) . A backbone Is blocked ot on end when the trace that created It Is blocked by something In the skeleton It can't Interpret.

• MEMBERS - a list of superatoms that make up the backbone
• CF - a certainty factor equal to the average of all the MEMBER's CFs

Superatom Hypothesis Element

LAOEL - SAn, n = 1 , 2, ... TYPE - e.o. PEPTIDE or SIDECHAIN BELONGSTO - (acid . seq ), example Is (MET. 3) MEMBEROF - points to BACKBONE ST, If any MEMBERS - a list of any atom hypotheses that are part of this superatom SEGS - list of subgraphs of the segment list and their associated CFs

Atomic Hypothesis Element

LAOEL - 1'1n, n = 1, 2, ... TYPE - one of C, N, 0, S, Ca, Mg, Fe, CO, Zn, H NAME - standard name designating position In the residue such as: CA, SO, NE 1 BELONGSTO - as In PEPTIDE MEMOEROF - list of superetoms this atom Is In D.PEAKS - links to peakllst with associated CFs NODES · links to skeleton with associated Cfs SPACE.LOC - list of possible positions for the atom and their CFs

Note that there may be multiple data links. For Instance, en atom may have links to several peaks In the peek list on the data plane, Indicating that Its position has not been established uniquely. A measure of certainty Is associated with each link as It Is generated. These certainty factors are used to compare and merge alternate hypotheses.

2.3 The rule hierarchy

The formal and Informal procedures which comprise the knowledge sources are expressed as rules. These rules are collected Into sets of rules, each set being appropriate to use when particular classes of events occur. The correspondence between event classes and rule sets Is .established by another set of rules, the task rules. The task rules are used to decide which KS or sequence of KSs to call In order to perform one of the typical tasks In building the structure, e.g., tracing the protein backbone between two anchor points. The decision Is based on the state of the blackboard and the Items on an event list. The task rules thus form a second Ioyer of rules which direct the system's selection of an appropriate method for proceeding.

Once a task Is completed, or If the task fails, the system rnust look to a higher level of control to determine what to do next. At this higher level -- the strategy level -- the structure building process can either try to solve the current subproblem by another method, or shift the focus of a ttentlon to another region of the structure. Strategy knowledge Is expressed as rules which make use of the current state of the blackboard and the event list.

We thus have a completely rule-based control structure, employing three distinct levels of rules (or knowledge): the specialists, commonly called the knowledge sources, the tnsk rules for method selection, an!f the strategy rules for controlling the focus of attention. Although this pyramidal structure of rules and meta-rules could continue Indefinitely, a three-tiered system of control appears to offer sufficient flexibility In choosing and deploying the resident knowledge sources.

The following subsections discuss In greater detail the structure and content of CRYSALIS at the three levels of control.

The strategy level The overall control of the system Is assigned to the strategy level. A set of strategy rules governs the choice of task to perform and a region of the hypothesis In which to work. Examples are:

1. IF there are no hypothesis elements THEN do INITIALIZATION task
2. IF there are two toeholds A and B ond 1\ has certainty greater than 400 ond B has certainty greater than 400 and the number of residues In the sequence separating the toeholds Is less than five THEN do TWO.POINT.TRACE task

(Notes: Certainty Is 11 measure of belief associated with the properties of each hypothesis element. Its range of values Is -1 000 to 1 000. Certainty factors are established and/or modified by KSs as they find support for a hypothesis element In the underlying dota. A "toehold" Is a hypothesis clement that Is linked to both the amino acid sequence and to the density plane with a relatively high certainty, I.e. an "Identified" part of the EOM.)

and A has certainty oreater than 400 and the direction of the backbone at that toehold Is known

1. IF there Is a toehold, A THEN do EXPANSION.TRACE task

The task level At the task level decisions are made on how to best accomplish a specific task, I.e. which KS or combination of KSs should be used. This knowledge Is embodied In a set of task rules, whose conditions are predicates operating on the event list, and whose actions Invoke specific KSs. Eight tasks have been formulated thus far, of which the following are examples :

INITII\LIZI\TION The Invocation of this task reads Input data Into system, puts any given Information on the blackboard, tries to Identify all Iorge atoms, finds dlsulphlde links, predicts occurrences of helical regions, tries to discover a set of chalnends, and performs nn "Interesting sequence" analysis. If the protein contains cofoctors, they are located and removed from the segment list In order to simplify the data. The end result of performing this task Is the establishment of a few toeholds In the data from which further Inferences can be made.

EXTENSION.TRACE This task Is applicable If the system has established the direction of the backbone at a given toehold. When this task Is Invoked, the model Is extended, at the superatomlc level, In a given direction until the cumulative certainty drops below a given threshold.

TWO.POINT.TRACE Chain tracing between two {liven toeholds Is In many ways the most certain of the various chain tracing tasks because the limits ore known. By tracing from each toehold toward the other and comparing the results, very high certainty values can be generated. This task uses many of the same KSs used In the EXTENSION.TRACE task. The main differences ore In the task rules, e.g., determining the conditions for stopping the troco ot one side and beolnnlng the trace at the other.

MODEL.DRIVEN.TRACE If It con be established that the current location Is part of a known secondary structure (such as alpha helix or beta sheet), o model of that structure can be used to predict successive atomic positions. The trace becomes a very hl9hly constrained loop of prediction and verification. Unlike other tracing tasks, the predictive model allows the trace to skip residues that do not appear In the data.

The knowledge source level The most detailed knowledge of the domain Is contained at the KS level. Each KS Is a "chunk" of formal or Informal knowledge used to solve somo pnrtlcular sub-problem In EDM Interpretation. Exomplns nrc matching a sldechaln subgraph to a template, mntchlno peaks In the EDM with large atoms Inferred from the amino ocld sequence, or simplifying the skeleton by removing the cofactor contribution. KSs are typically represented as a set of productions, but In some cases It has been more efficient to represent the knowledge as a procedure (particularly when heavy numerical computing Is Involved). About two dozen KSs have been Implemented In the CRYSALIS system thus far.

2.4 Event·drlven control

The CRYSALIS system uses an event-driven control structure. An event Is a description of a change In the hypothesis, e.g., the addition of a new hypothesis element or the establishment of now links between existing hypothesis elements. In this scheme the current state of the hypothesis space determines what to do next. The normal Iterative cycle of problem solving uses the event list to trigger knowledge sources, which create or change hypothesis elements and place new events on the event list. Each tnsk Is executed until It Is explicitly finished or until no further rulos are fired, after which control passes up to the strategy level to shift attention to 11 new task. The portlculor hypothesis element under Investigation, or the particular KS Invoked, are determined by the type of event selected from the event list. Thus, under normal conditions, the monitor always has a means for choosing Its next move. Items may be selected from the event list accordln9 to a specified processing mode, e.g., FIFO, LIFO or some priority scheme for choosing the "best" event.

The system's behavior Is "OI>Portunlstlc" In that It Is guided primarily by whot was most recently discovered, rather thon by a necessity to satisfy sub-goals. The choice of an event-driven control structure Is based partly on efficiency In selecting Ol>proprlate knowledge sources and portly on conformity with the structure modeling process normally employed by protein crystallographers.

2.6 Focus of Attention Mechanisms

There ore two levels of attention focussing, corresponding to the two levels of control In CRYSALIS. At the strategy level, a "conrse" focus of attention Is created by assigning a task to a region of the hypothesis space. The conditions on strategy rules refer to global features of the current hypothesis, such as the presence of solved and unsolved reolons along the amino acid sequence. A finer degree of focusslno Is 1>rovlded at the task level, where task rules focus on specific events, and specific KSs (where the real model building Is accomplished) to process those events.

3 Discussion

The sheer volume ond variety of knowledge that crystallographers bring to beor on the EDM Interpretation problem Implies o correspondingly large and varied automated system. CRYSALIS employs many Ideas developed over the post decode for representation and utilization of knowledge In ex1>ert systems. Although none of these features by Itself brooks new ground In AI research, their conjunction In one system makes an Interesting case study.

3.1 Flexible architecture

An essential requirement of CRYSALIS Is flexibility: the addition of new facts and procedures must be done easily and quickly, as nearly every new protein structure presents new problems and ad hoc knowledge. The modularity of the rules, the multi-level control and the multiple blackboard planes for hypotheses and data are all Incorporated In the system In order to accommodate expansion or modification. Modularity also allows us as system builders to experiment with alternate designs for the components, e.g. using a strictly procedural knowledge source In place of a rule-based one, with no external change In the system.

3.2 Rule-based control of strategy and task levels

The method of Interpreting protein EDM's Is, at Its critical points. opportunistic. Where to start, when to leave one port of the structure ond focus uron another, what level of dotnll to look at, when to stop -- these questions are continually presented to tho expert as he builds his structure. Tho knowledge needed to answer them Is almost entirely heuristic, and as subject to change as any other task-specific knowledge. It thus seems natural, and Indeed has shown to be practical, that this strategic knowledge, which controls the order In which various tasks are performed, be represented as rules. Moreover, the tasks moy be executed In various ways, depending upon what J<.Ss are available and the particular situation encountered, so control at the task level Is also facilitated by a rule-based representation.

The use of two levels of control has been found to be an efficient alternative to using one large rule set.

3.3 Event-driven processing

The opportunities which arise In EDM Interpretation are dynamic, I.e., they flow not only from the Initial data but from the partially built structure. Thinking of the solution process os one of recognition and verification, the recognition phose operates on both the data and the partial hypothesis. As the hypothesis changes, new Islands of opportunity arise. By specifically recording these events, the focus-of-attention problem Is ameliorated.

3.4 Multi-level hypothesis/data structure

Use of the blackboard concept was suggested by the similarity of this problem with that of other signal understandln~l tasks, specifically in the need for a common store accessible to many diverse and independent KSs. The representation of both the hypothesis and the data In the uniform way discussed earlier makes It easier to add or modify the various levels. For example, It might be useful at some time to add a "glob" level of description of the EDM, which would capture some visual Information, along with a new level of description of the model, such as families of amino acids. The multi-level planes facilitate

this kind of modification.

The multiple levels of description ore also necessitated by the lock of o common language for describing the objects and operators of the domain, In contrast, soy, to the Heuristic DENDRAL program which uses a uniform language of chemical subgraphs for this purpose. The domain knowledge In CRYSALIS Is expressed most naturally at several levels, e.g. Inferences can be drawn from peaks In the EDM to atoms In the model, but !nferences about a skeletal se"ment are related to superatoms.

Moreover, the li1dlvlctual levels of detail In the model plane have an Intrinsic Interest. As Is evident from the protein crystallographic literature, there is more of Interest to a molecular structure than the coordinates of Its constituent atoms. Announcements of new structures usually contain visual representations of the backbone alone, secondary structure, hydrogen bonding, active site geometry, etc. Often the model Is Incompletely specified at the atomic level, so that descriptions of the structure In some regions must be couched In the language of side chains or other abstractions. The multi-leveled hypothesis structure In CRYSALIS permits this variety of descriptions.

3.6 111-structuredness

Two characteristics of the task domain are particularly lnterestill{l In that they provide on 111-structuredness which Is normally not found In AI applications. The first Is the lock of a well defined termination criterion. One can, of course, stop the program when the position of oil atoms Is known, but this Is almost never the case. In practice, one stops when no further progress con be made, as for example when no strategies available to the system are applicable, or If further model building effort yields diminishing returns (the recoqnltlon of which Is an Interesting ond thus for unsol~ed theoretical problem). Moreover, to the extent that one can lay down some rules for terminating the process, those rules are usually dependent on the quality of the data.

A second characteristic Is thnt the detail of the resulting model, I.e. the solution, varies with the quality and resolution of the given data. Different knowledge sources ore Invoked for different ranges of resolution, and moy either draw different Inferences or link different levels of the .model plane with the dato. In any case the detail of the model Is adjusted to fit the experimental Information, and can degrade gracefully with decreasing resolution. Thus If some data are particularly poor, or not given at all (e.g. on Incomplete sequence) It still should be possible to get some results.

4 ConcluslonJ Current status and activities

As It currently exists, CRYSALIS Is In Its early adolescence, capable of Interpreting relatively obvious features In o (lood EDM, but not yet worthy of attracting serious attention In the protein-crystallographic community. We are currently working toward a more extensive knowledge-based system capable of complete Interpretation of medium-quality, medium-resolution (2 to 2.5 Ang.) EDMs. During the next year or two we expect to bring the system's level of performance to the point where It will be noteworthy, by helping In a major way to solve a new protein structure. That goal will be reached, we believe, by Incorporating more detailed knowledge about protaln chemistry and stereochemistry, and by Improving the heuristics for matching the abstracted EDM with structural features determined by the amino acid sequence. We are also extending our preprocessing pro{Jrams so that more meaningful and/or less ambiguous features can be extracted from the dote. Another current activity Is a re-design of the system to Improve Its understnndoblllty, modularity and flexibility.

ACKNOWLEDGMENTS

We wish to acknowledge the assistance of our colleagues In the crystallographic community, specifically Dr. Stephan Freer, Dr. Richard Alden and Prof. Joseph Kraut of UCSD, and Dr. Carroll Johnson of ORNL. At Stanford, Ms. H. Penny Nil was Instrumental In the Initial construction of CRYSALIS; Mr. Eric Grosse assisted In developing algorithms for abstracting the data.

Appendix A

An Illustrative example

Space limitations prevent a full example from being Included In these proceedings. An annotated typescript, Illustrating the performance of CRYSALIS on a typical Interpretation problem, will be available at the conference or from the authors upon written request.